DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

Your Outliner Should Not Store a Tree. A Flat Array Makes Tab-to-Indent One Integer

#programming #javascript #webdev #frontend

The obvious model for nested toggle blocks is a tree of nodes with children arrays. It works until you want the thing that makes an outliner an outliner: Tab to indent the block you are typing in.

In a tree that is a graph rewrite. Detach from the parent, find the previous sibling, append to its children, re-parent every descendant — and the blocks after you have to become your children too. Every step can leave the tree inconsistent halfway through.

Flat, the same document is:

[ { id:1, text:"Trip",      depth:0, open:true  },
  { id:2, text:"Flights",   depth:1, open:true  },
  { id:3, text:"Outbound",  depth:2, open:true  },
  { id:4, text:"Hotels",    depth:1, open:false } ]
Enter fullscreen mode Exit fullscreen mode

Indent block 4 is b[3].depth++. One integer. Nothing can dangle because there are no pointers.

Live, type in it: https://dev48.infy.uk/design/day63-toggle-blocks.html

One rule keeps a flat list a tree

[0, 2] is meaningless — block two claims a grandparent that does not exist. So exactly one invariant is enforced:

depth[i] <= depth[i-1] + 1, and depth[0] === 0

Indent is refused when it would break that. The Tab key sometimes doing nothing is not a missing feature; it is the invariant holding.

A subtree is a range, not a traversal

Because depth rises by at most 1, everything nested under block i is contiguous:

function subtreeEnd(b, i){
  let j = i + 1;
  while (j < b.length && b[j].depth > b[i].depth) j++;
  return j;                       // subtree is [i, j)
}
Enter fullscreen mode Exit fullscreen mode

Collapse hides [i+1, j). Delete splices [i, j). Drag moves [i, j). One function, four features, and it is a scan rather than a recursion.

Visibility must be derived

The tempting bug is a stored hidden flag. Collapse a parent, collapse a child inside it, expand the parent — the child comes back expanded, because two sources of truth drifted. Instead:

function visible(b, i){
  let need = b[i].depth;
  for (let k = i - 1; k >= 0 && need > 0; k--){
    if (b[k].depth < need){        // an ancestor
      if (!b[k].open) return false;
      need = b[k].depth;
    }
  }
  return true;
}
Enter fullscreen mode Exit fullscreen mode

One backward scan. No stored state, no possible drift.

The bug the fuzz test found

I checked the flat model against an independently written parent-pointer tree, applying the same random operations to both and comparing outlines after every step.

It broke after 89 operations. move() re-seated a dragged subtree against the block before it — and never looked at the block after. Dropping into the middle of someone else's subtree produced …3, 1, 4…: a depth-4 block hanging off a depth-1 one. The render would have silently re-parented content the user never touched.

The fix is to validate and roll back rather than re-parent behind their back. 4,000 operations now, 0 divergences.

Visibility is checked two ways as well — the flat backward scan against walking parent pointers upward. 3,000 states, no disagreement. Two algorithms that share no code cannot agree for the wrong reason.

Repo: https://github.com/dev48v/design-from-zero

Top comments (0)