components/tree/tree-model.ts

Functions

Imports

It imports no other module of this repo. Imported by components/tree/tree.ts.

Source

1// The tree's rows, keys and moves, pure (tree.ts).
2
3// ---------------------------------------------------------------------------------------
4// Pure functions, over plain nodes. A node with `children` (even an empty list) is a
5// branch and can hold others; a node without is a leaf.
6
7export interface TreeNodeLike {
8  id: string;
9  label?: string;
10  disabled?: boolean;
11  children?: readonly TreeNodeLike[];
12}
13
14export interface VisibleRow {
15  id: string;
16  parent: string | null;
17  // One-based, as aria-level, aria-posinset and aria-setsize count.
18  level: number;
19  posinset: number;
20  setsize: number;
21  branch: boolean;
22  expanded: boolean;
23  disabled: boolean;
24  label: string;
25}
26
27// The rows a person can reach, in order: every top node, and the children of each open branch.
28export function visibleRows(nodes: readonly TreeNodeLike[], expanded: ReadonlySet<string>): VisibleRow[] {
29  const out: VisibleRow[] = [];
30  const walk = (list: readonly TreeNodeLike[], parent: string | null, level: number) => {
31    list.forEach((n, i) => {
32      const branch = n.children !== undefined;
33      const open = branch && expanded.has(n.id);
34      out.push({ id: n.id, parent, level, posinset: i + 1, setsize: list.length, branch, expanded: open, disabled: !!n.disabled, label: n.label ?? n.id });
35      if (open) walk(n.children ?? [], n.id, level + 1);
36    });
37  };
38  walk(nodes, null, 1);
39  return out;
40}
41
42// Every branch's id, for "open everything".
43export function branchIds(nodes: readonly TreeNodeLike[]): string[] {
44  const out: string[] = [];
45  const walk = (list: readonly TreeNodeLike[]) => {
46    for (const n of list) {
47      if (n.children === undefined) continue;
48      out.push(n.id);
49      walk(n.children);
50    }
51  };
52  walk(nodes);
53  return out;
54}
55
56// What a key does to the tree, as data: the row to focus, a branch to open or close, the
57// branches to open at once (`*`), a row to choose, or a move.
58export interface TreeKeyResult {
59  focus?: string;
60  expand?: string[];
61  collapse?: string;
62  select?: string;
63  move?: MoveDir;
64}
65
66export interface KeyMods {
67  altKey?: boolean;
68  ctrlKey?: boolean;
69  metaKey?: boolean;
70  shiftKey?: boolean;
71}
72
73// The tree pattern's keys, from the WAI-ARIA Authoring Practices: Down and Up move between
74// visible rows; Right opens a closed branch or goes to its first child; Left closes an open
75// branch or goes to the parent; Home and End go to the first and last row; `*` opens every
76// sibling branch; Enter and Space choose. With `movable`, Alt with an arrow moves the row.
77// Letters (typeahead) are the caller's, with the listbox's `nextTypeahead`.
78export function treeKey(rows: readonly VisibleRow[], current: string | null, key: string, mods: KeyMods = {}, movable = false): TreeKeyResult | null {
79  if (rows.length === 0) return null;
80  const i = Math.max(0, rows.findIndex((r) => r.id === current));
81  const row = rows[i]!;
82  if (mods.ctrlKey || mods.metaKey) return null;
83  if (mods.altKey) {
84    if (!movable || row.disabled) return null;
85    const dir = ({ ArrowUp: "up", ArrowDown: "down", ArrowRight: "in", ArrowLeft: "out" } as const)[key as "ArrowUp"];
86    return dir ? { move: dir } : null;
87  }
88  switch (key) {
89    case "ArrowDown":
90      return { focus: rows[Math.min(rows.length - 1, i + 1)]!.id };
91    case "ArrowUp":
92      return { focus: rows[Math.max(0, i - 1)]!.id };
93    case "ArrowRight":
94      if (!row.branch) return {};
95      if (!row.expanded) return { expand: [row.id] };
96      return rows[i + 1]?.parent === row.id ? { focus: rows[i + 1]!.id } : {};
97    case "ArrowLeft":
98      if (row.branch && row.expanded) return { collapse: row.id };
99      return row.parent !== null ? { focus: row.parent } : {};
100    case "Home":
101      return { focus: rows[0]!.id };
102    case "End":
103      return { focus: rows[rows.length - 1]!.id };
104    case "*":
105      return { expand: rows.filter((r) => r.parent === row.parent && r.branch && !r.expanded).map((r) => r.id) };
106    case "Enter":
107    case " ":
108      return row.disabled ? {} : { select: row.id };
109    default:
110      return null;
111  }
112}
113
114// ---- moving
115
116export type MoveDir = "up" | "down" | "in" | "out";
117
118// Where a node sits: its parent (null at the top) and its zero-based position there.
119export interface TreePlace {
120  parent: string | null;
121  index: number;
122}
123
124// A move: `from` is the place before it, `to` the place in the tree once the node has left
125// `from`, so applying it is "take out, then put in at `to`".
126export interface TreeMove {
127  id: string;
128  from: TreePlace;
129  to: TreePlace;
130}
131
132const childrenOf = (nodes: readonly TreeNodeLike[], parent: string | null): readonly TreeNodeLike[] | undefined =>
133  parent === null ? nodes : findNode(nodes, parent)?.children;
134
135export function findNode<T extends TreeNodeLike>(nodes: readonly T[], id: string): T | undefined {
136  for (const n of nodes) {
137    if (n.id === id) return n;
138    const hit = n.children ? findNode(n.children as readonly T[], id) : undefined;
139    if (hit) return hit;
140  }
141  return undefined;
142}
143
144export function findPlace(nodes: readonly TreeNodeLike[], id: string, parent: string | null = null): TreePlace | null {
145  const i = nodes.findIndex((n) => n.id === id);
146  if (i >= 0) return { parent, index: i };
147  for (const n of nodes) {
148    const hit = n.children ? findPlace(n.children, id, n.id) : null;
149    if (hit) return hit;
150  }
151  return null;
152}
153
154// Whether `id` is `ancestor` or sits anywhere under it.
155export function isWithin(nodes: readonly TreeNodeLike[], id: string, ancestor: string): boolean {
156  if (id === ancestor) return true;
157  const a = findNode(nodes, ancestor);
158  return !!a?.children && !!findNode(a.children, id);
159}
160
161// A keyboard move: up and down among its siblings; in, to the end of the branch just above
162// it; out, to just after its parent. Null where it cannot go (the first row up, a row with
163// no branch above it in).
164export function planMove(nodes: readonly TreeNodeLike[], id: string, dir: MoveDir): TreeMove | null {
165  const from = findPlace(nodes, id);
166  if (!from) return null;
167  const siblings = childrenOf(nodes, from.parent) ?? [];
168  if (dir === "up") return from.index > 0 ? { id, from, to: { parent: from.parent, index: from.index - 1 } } : null;
169  if (dir === "down") return from.index < siblings.length - 1 ? { id, from, to: { parent: from.parent, index: from.index + 1 } } : null;
170  if (dir === "in") {
171    const above = siblings[from.index - 1];
172    if (!above?.children) return null;
173    return { id, from, to: { parent: above.id, index: above.children.length } };
174  }
175  if (from.parent === null) return null;
176  const up = findPlace(nodes, from.parent);
177  return up ? { id, from, to: { parent: up.parent, index: up.index + 1 } } : null;
178}
179
180export type DropZone = "before" | "after" | "inside";
181
182// A drop of `id` on `target`: before it, after it, or inside it (at the end; a branch only).
183// Null for a drop on itself or anywhere under itself, and for one that changes nothing.
184export function dropMove(nodes: readonly TreeNodeLike[], id: string, target: string, zone: DropZone): TreeMove | null {
185  const from = findPlace(nodes, id);
186  const at = findPlace(nodes, target);
187  if (!from || !at || isWithin(nodes, target, id)) return null;
188  let to: TreePlace;
189  if (zone === "inside") {
190    const kids = findNode(nodes, target)?.children;
191    if (!kids) return null;
192    to = { parent: target, index: kids.filter((k) => k.id !== id).length };
193  } else {
194    // The target's position once `id` has left its old place.
195    const shift = from.parent === at.parent && from.index < at.index ? 1 : 0;
196    to = { parent: at.parent, index: at.index - shift + (zone === "after" ? 1 : 0) };
197  }
198  if (to.parent === from.parent && to.index === from.index) return null;
199  return { id, from, to };
200}
201
202// Where on a row a drop at height `y` lands: the top quarter before it, the bottom quarter
203// after it, the middle inside it when it is a branch (otherwise the nearer half).
204export function zoneAt(y: number, top: number, height: number, branch: boolean): DropZone {
205  const f = height > 0 ? (y - top) / height : 0.5;
206  if (branch) return f < 0.25 ? "before" : f > 0.75 ? "after" : "inside";
207  return f < 0.5 ? "before" : "after";
208}
209
210// The nodes with the move made. Immutable: new arrays along the changed paths only.
211export function applyMove<T extends TreeNodeLike>(nodes: readonly T[], move: TreeMove): T[] {
212  const node = findNode(nodes, move.id);
213  if (!node) return [...nodes];
214  const without = (list: readonly T[]): T[] =>
215    list.filter((n) => n.id !== move.id).map((n) => (n.children ? ({ ...n, children: without(n.children as readonly T[]) } as T) : n));
216  const insert = (list: readonly T[], parent: string | null): T[] => {
217    if (parent === move.to.parent) {
218      const out = [...list];
219      out.splice(Math.max(0, Math.min(out.length, move.to.index)), 0, node);
220      return out;
221    }
222    return list.map((n) => (n.children ? ({ ...n, children: insert(n.children as readonly T[], n.id) } as T) : n));
223  };
224  return insert(without(nodes), null);
225}
226
227// The move that puts it back (for Undo).
228export function reverseMove(move: TreeMove): TreeMove {
229  return { id: move.id, from: move.to, to: move.from };
230}
231
232// What the live region says after a move, from the tree as it is after it.
233export function movedText(nodes: readonly TreeNodeLike[], move: TreeMove): string {
234  const label = (id: string) => findNode(nodes, id)?.label ?? id;
235  const count = childrenOf(nodes, move.to.parent)?.length ?? 0;
236  const where = move.to.parent === null ? "at the top level" : `in ${label(move.to.parent)}`;
237  return `Moved ${label(move.id)} to position ${move.to.index + 1} of ${count} ${where}.`;
238}
239
240export function cannotMoveText(label: string, dir: MoveDir): string {
241  return {
242    up: `${label} is already first here.`,
243    down: `${label} is already last here.`,
244    in: `${label} cannot go in: there is no branch just above it.`,
245    out: `${label} is already at the top level.`,
246  }[dir];
247}