https://ratfactor.com/cards/fake-trees

vector ratfactor rat logo
Home | About | Now | Repos | Cards | Contact | RSSrss feed icon
This is a card in Dave's Virtual Box of Cards.

Fake Trees: Using Indents For Simpler UIs

Created: 2023-12-29

This is a technique I've used in actual for-pay software, but most
recently in my text adventure game editor, Hiss.

The problem: you want a tree-like list in your UI

Let's say you have this fantastic dynamic list of Foo and Bar data
and you would like to display it in a tree view of some sort in your
application:

My Foos
    Foo 1
        Foo 1.a
        Foo 1.b
    Foo 2
    Foo 3
My Bars
    Bar I
        Baz baz baz
    Bar II
    Bar III
    Bar IV
...

This obviously you need to implement some sort of parent-child
relationship between these items, right?

That sounds like a lot of work and potentially awkward-to-work-with
data structure, especially if stored in a database. But surely there
is no way around it. It's "obviously" the only way to go.

Okay, so let's do that. You could express this with a parent ID.
Something like this, if you're using a database:

  id | sort | name    | parent
 ----+------+---------+-------
  13 | 1    | Foo     | null
  78 | 1    | Foo 1   | 13
  98 | 1    | Foo 1.a | 78
  99 | 2    | Foo 1.b | 78
  ...

Now how to do we work with this?

Well, for example, one way to get tree-structured data from a
relational database with a SQL query is to write a recursive CTE
(Common Table Expressions), which are just as fun as they sound.

If you're a programmer, you're probably already thinking about how
you would display this data... 

Wait, but does your data really need to be a tree?

Do your items actually have to have a parent-child relationship, or
do they just need to look like they do?

I find that these lists are often just formatted this way for human
organization. There's no actual need for a formal relationship
between them.

If that's the case, a vastly simpler method for storing this tree is:

  id | sort | indent | name
 ----+------+--------+-------
  13 | 1    | 0      | Foo
  78 | 2    | 1      | Foo 1
  98 | 3    | 2      | Foo 1.a
  99 | 4    | 2      | Foo 1.b
  ...

Why is this simpler? Because it literally describes what you see on
the screen. Which means it's easy as pie to render. Note how the sort
order is now absolute for the entire list, not for sub-item order.
The indent is quite literally how much space to put before the item.

And it's not just display the list that becomes easier - making an
interface to edit this tree can also be much simpler now. You can
simply let the user move items up and down and indent/unindent them
to their heart's content (or put in some simple rules to enforce
correct indenting - that's up to you). It becomes more like editing a
list in a word processor than interfacing with a data structure
straight out of a computer science text book.

Another example using "namespacing"

Here's an example straight out of Day 18 of my Hiss December
Adventure Log:

I've got items with these names from a silly example game:

Start
banana
banana.eat
banana.peel
banana.sniff
banana.throw away
monkey
...

And these render in the interface like so:

a things list contains sub-items under the banana thing: eat

It appears I implemented some sort of namespacing feature to
HissScript.

But I didn't!

I'm just sorting the items alphabetically and if I see a dot (".") in
a name, I chop off the first part and indent the item.

As with the Foo and Bar list in the previous example, it looks like
the game editor "understands" the relationship, but that's just an
illusion.

Just to give a sense of how simple this is, here's the entirety of
the list drawing code (JavaScript):

var names = Object.keys(objs).sort();

return names.map(function(n){
    if(m = /^.+(\..+)$/.exec(n)){
        return ["a.indent", {onclick:link(n)}, m[1]];
    }
    return ["a", {onclick:link(n)}, n];
});

And that's raw editor code that sets up click handlers and
everything. The pseudocode logic is just:

names = sort(things.keys)
each names as name:
    if contains('.', name):
        print_indent chop_before('.', name)
    else
        print name

(I later added a check to make sure a "parent" item with the given
prefix exists before doing the indent/chop. But that was just another
couple lines. Also, it would be no problem to add arbitrarily deep
nesting levels to this namespacing feature but I'm waiting for an
actual need.)

The "namespacing" appearance is very important for a human trying to
organize a game. But it means nothing to the game editor and player.
Names with dots in them are just names. The namespacing keeps them
unique, but that's it.

I learned the hard way long ago: more often than not, people don't
actually want (or need) trees, they just need the appearance of them.

Bonus tree-as-list

Update: Dave Long writes:

    "Low-tech real trees: store path + info in a flat list (like the
    output of find)."

That's definitely true and is essentially the insight behind my
"banana.eat" example above. Here's some fake find output:

./foo/zonk
./foo/bonk
./bar/boop/bop
./bar/boop/bleep

    "Want a depth-first traversal? lexically sort by the path."

For sure:

./bar/boop/bleep
./bar/boop/bop
./foo/bonk
./foo/zonk

    "Want a breadth-first traversal? sort by the (properly padded)
    reversal of the path"

Hmmm... let's see:

bleep/boop/bar
bonk/foo
bop/boop/bar
zonk/foo

That's interesting.

You know, flat lists are great to work with in general. If possible,
I love putting things in plain old lists. This reminds me of my other
recent card: Interpreting if/else logic with a simple flat list of
booleans.

Physical analogy

Just to hammer on the point, let's say you're working on your
personal scrapbook. You're starting to put boxes of photos, notes,
postcards, ticket stubs, etc. into some sort of order. You're laying
everything out on the floor and you're making some really nice
groupings of items and you've even made little folded paper signs to
label the groups.

Even though it is glaringly obvious to you, the human, how these
groups work, is there actually any physical mechanism built into your
floor to enforce this relationship? Of course not. The floor has no
idea what's going on.

(Or if it does, you have accidentally moved into a home built over an
ancient burial ground and are in immediate danger. Pack a bag and
leave now. Sleep in a hotel tonight and you can think about how to
get your belongings and find a new home when you've got a clear head
tomorrow morning. The scrapbook can wait for a better time when
you're less likely to be eaten by skeletons.)

Caution: One size does not fit all

I'm sure there are infinite variations on this and I'm sure I'm not
the first person to think either of the above two example techniques.
But I have never seen anyone mention it before. So anything like this
will probably count as a "hack" in most programming circles.

You will almost definitely need to heavily adapt it to your specific
scenario.

And for the love of all that is good, if you actually need a tree,
use a tree. Do the whole parent ID thing (or separate parent/child
join table or whatever makes sense to your data model).

In the physical analogy above, if you're cataloging a massive
research project and you need the organizing power of physical filing
cabinets and neatly-labeled folders, the floor method is not going to
cut it! (Just make sure you're not using haunted filing cabinets.)

Do not hack something with indents or counting symbols in strings or
some nonsense like that if you will ever need to actually know the
relationship between your items. Yes, you can do it, but it will be a
path of suffering for the lifetime of the project and all of its
maintenance forever after. Don't say I didn't warn you.

This page was last generated 2023-12-29 23:58:27 -0500
All content (c) Copyright Dave Gauer