Hierarchy Data

A lightweight, framework-agnostic ESM TypeScript library for managing hierarchical tree structures, parent-child relationships, node lookups, automatic sorting, and flattened list transformations for frontend applications.

中文 | English

Architecture Principles & Contracts

• Single Source of Truth (HierarchyTree): All structural mutations (add, appendChild, insertAt, move, update, remove, clear) must be performed through HierarchyTree.
• Readonly Node Interface (IHierarchyData): HierarchyData nodes expose readonly properties (parent, children, level, isLeaf) and Readonly<T> data view. Node keys are immutable snapshot properties.
• Maximum Depth Limit Contract (maxDepth):
  • Default maximum depth is 1000 (configurable from 1 to 1000).
  • Root node level is 0, maximum allowed node level is 999.
  • Exceeding the maximum allowed depth throws HierarchyDepthExceededError. This can be thrown by setData, add, appendChild, insertAt, move, and update — not just setData — since any of these can attach a (sub)tree deep enough to breach the limit. Catch it in the UI layer around any call that mutates the tree.
• Transactional Safety: setData, add/appendChild/insertAt, move, update, and sort pre-validate key immutability, cycles, max depth limits, and user callbacks (getKey/getParentKey/setParentKey/compare) entirely in a pre-commit phase; the commit phase itself never calls back into user code, so it cannot fail partway through. compare is never run as a "dry validation" pass followed by a second real sort — each commit performs exactly one real sort, so a stateful or non-idempotent comparator can't pass validation and then fail (or disagree with itself) on the real run. (This doesn't mean every callback fires only once overall — a single Array.sort() naturally invokes compare several times, and cycle detection may read getParentKey more than once — only that no callback is ever re-run across a validate-then-commit boundary.) On error, existing tree structures — including previously-adopted out-of-order children and their original root ordering — remain 100% untouched.
• Stack-Overflow Prevention: All traversals (walk, descendants, getVisibleList, recomputeLevel) use explicit iterative stacks, guaranteeing zero stack overflows even on deep trees.

Installation

npm install @ticatec/hierarchy-data

Quick Start

import { HierarchyTree, HierarchyDepthExceededError } from '@ticatec/hierarchy-data';

interface Dept {
  id: string;
  parentId?: string | null;
  name: string;
  order?: number;
}

const tree = new HierarchyTree<Dept>({
  getKey: (d) => d.id,
  getParentKey: (d) => d.parentId,
  // Configured to keep item.parentId in sync with structural movements
  setParentKey: (d, newParentKey) => ({ ...d, parentId: newParentKey as string }),
  compare: (a, b) => (a.order ?? 0) - (b.order ?? 0),
  maxDepth: 1000 // Default 1000 (allows levels 0...999)
});

try {
  tree.setData([
    { id: '1', name: 'Engineering', order: 1 },
    { id: '2', parentId: '1', name: 'Frontend Team', order: 10 },
    { id: '3', parentId: '1', name: 'Backend Team', order: 20 }
  ]);

  // Single entry point for moving nodes (updates structural hierarchy and item.parentId)
  tree.move('3', '2'); // Move Backend Team under Frontend Team

  // Single entry point for updating data
  tree.update('2', (old) => ({ ...old, name: 'Web Engineering' }));
} catch (err) {
  if (err instanceof HierarchyDepthExceededError) {
    console.error(`Depth limit ${err.maxDepth} exceeded at node:`, err.nodeKey);
  }
}

// Render flattened list for TreeView / Tree DataGrid components
const expandedKeys = new Set(['1', '2']);
const visibleList = tree.getVisibleList(expandedKeys);

Constructor Options (HierarchyTreeOptions<T>)

| Option | Type | Required | Description | |---|---|---|---| | getKey | (item: T) => string \| number | Yes | Extracts the unique key from a data item. | | getParentKey | (item: T) => string \| number \| null \| undefined | Yes | Extracts the parent key. Return null/undefined for root items. | | setParentKey | (item: T, newParentKey: string \| number \| null \| undefined) => T | Only if you call move() | Returns a new data object with parentKey synced to the new structural parent. Called once per affected node, only during the pre-commit validation phase, never during commit. Must not change the value getKey returns for the item — throws otherwise. | | compare | (a: T, b: T) => number | No | Sibling ordering comparator (same contract as Array.prototype.sort). When set, siblings are kept sorted automatically after every structural mutation. | | maxDepth | number | No | Maximum tree depth, 1–1000, default 1000. Throws TypeError at construction time if out of range, not an integer, or NaN. | | duplicateKeyStrategy | 'throw' \| 'replace' \| 'warn' | No | What happens when inserting a key that already exists. Default 'throw'. See Duplicate keys below. | | cycleStrategy | 'as-root' \| 'throw' | No | What happens when a mutation would create a parent/child cycle. Default 'as-root'. See Cycle detection below. | | onDiagnostic | (event: HierarchyDiagnosticEvent) => void | No | Called for non-fatal situations (duplicate-key warn, cycle-detected as-root, invalid-parent) instead of the default console.warn. event.type, event.key, event.message. |

API Reference

All structural mutation goes through the HierarchyTree instance; nodes returned from it (IHierarchyData<T>) are read-only views.

Bulk load

• setData(list: T[]): void — Replaces the entire tree from a flat list in one atomic operation. Fully rebuilds an internal candidate structure (parsing keys, resolving parents, running setParentKey, checking cycles and depth, sorting) and only swaps it in if every step succeeds. Items whose parent key doesn't resolve to another item in the same list become roots and are tracked as pending (see Out-of-order loading). Throws on duplicate keys (per duplicateKeyStrategy), cycles (per cycleStrategy), or HierarchyDepthExceededError — in every case the previous tree is left completely untouched.

Insertion

• add(item: T): IHierarchyData<T> — Inserts item as a root, or under the parent resolved from getParentKey(item) if that parent already exists in the tree (otherwise the item is registered as pending, waiting for that parent to show up later).

• appendChild(parent: IHierarchyData<T> | string | number, item: T): IHierarchyData<T> — Inserts item as the last child of parent (accepts a node, a key, or undefined/omitted for root).

• insertAt(parent: IHierarchyData<T> | string | number | undefined, index: number | undefined, item: T): IHierarchyData<T> — Same as appendChild, with an explicit insertion index (undefined = append). If compare is configured, the explicit index is only the initial position — the sibling list is immediately re-sorted afterward.

  All three go through the same pre-validation pipeline before touching the tree: duplicate-key check → setParentKey/key-immutability check → cycle check → HierarchyDepthExceededError check. Only after every check passes does the method mutate structure, adopt any pending children waiting for this key (see below), and re-sort siblings. Any failure at any stage — including a compare throw after a successful pending-adoption — leaves the tree exactly as it was before the call (adopted pre-existing nodes are put back in their original position, not merely reparented back).

Moving & updating

• move(targetKey: string | number, newParentKey?: string | number, index?: number): boolean — Moves an existing node (and its whole subtree) to a new parent (or to root if newParentKey is omitted) and/or a new index among its new siblings. Requires setParentKey to be configured — throws immediately otherwise, since there would be no way to keep item.parentKey in sync with the move. Returns false (without throwing) if targetKey/newParentKey doesn't resolve, or if the move would create a cycle under cycleStrategy: 'as-root'. Throws HierarchyDepthExceededError if moving the subtree would push any of its descendants past maxDepth — this check accounts for the full height of the subtree being moved, not just the moved node itself.
• update(target: string | number | T, dataOrUpdater: T | ((oldData: T) => T)): IHierarchyData<T> | undefined — Replaces a node's data (or transforms it via an updater function). getKey on the new data must equal the existing node's key — throws otherwise (keys are immutable after insertion; remove and re-add to change one). If the new data's parent key differs from the old one, this is treated as an implicit move (same depth/cycle checks as move(), and setParentKey is invoked if configured). Returns undefined if target doesn't resolve to an existing node.

Removal

• remove(itemOrKey: T | string | number): boolean — Removes a node and its entire subtree. Returns false if the key doesn't resolve.
• clear(): void — Empties the tree completely (roots, index, and any pending registrations).

Sorting

• sort(comparator?: (a: T, b: T) => number): void — Re-sorts every level of the whole tree (roots and every subtree), using comparator if given, otherwise the configured compare. No-op if neither is available. Computes every level's sorted order first and only commits once all of them succeed — a comparator throwing partway through a large tree leaves the entire tree's ordering untouched, not just the level that failed.
• sortSiblings(parent?: HierarchyNode<T>): void — Re-sorts a single level (the children of parent, or the roots if omitted) using the configured compare. Mostly for internal use; exposed for advanced cases.

Lookup & traversal

• find(key: string | number): IHierarchyData<T> | undefined — O(1) lookup by key.
• get roots(): readonly IHierarchyData<T>[] — A fresh shallow-copy array of root nodes on every access; mutating the returned array never affects the tree (same is true of node.children).
• walk(cb: (node: IHierarchyData<T>, depth: number) => void | false): void — Depth-first pre-order traversal over the whole forest. Return false from the callback to skip that node's subtree. Uses an explicit stack, not recursion — safe at any configured maxDepth.
• map<U>(cb): U[] / filter(predicate): IHierarchyData<T>[] — Convenience wrappers around walk.
• getVisibleList(expandedKeys: ReadonlySet<string | number>): IHierarchyData<T>[] — Flattens the tree into the list a virtualized TreeView/DataGrid would render, given a set of currently-expanded node keys. Collapsed nodes' children are excluded (but the collapsed node itself is included).

Node view (IHierarchyData<T>)

Every node handed back to you (from find, add, roots, walk, etc.) exposes: data (readonly view of T), parent, children (readonly array copy), level, isLeaf, plus walk/map/filter/descendants/ancestors/path/siblings scoped to that node's own subtree. There is no way to mutate the tree through a node — every mutation goes through the HierarchyTree instance.

Error Handling

import { HierarchyDepthExceededError } from '@ticatec/hierarchy-data';

try {
  tree.appendChild(deeplyNestedNode, newItem);
} catch (err) {
  if (err instanceof HierarchyDepthExceededError) {
    // err.maxDepth: the configured limit; err.nodeKey: the node that triggered it
    console.error(`Depth limit ${err.maxDepth} exceeded at node "${err.nodeKey}"`);
  } else {
    throw err; // key-immutability violation, missing setParentKey on move(), etc.
  }
}

HierarchyDepthExceededError can be thrown by setData, add, appendChild, insertAt, move, and update — wrap any call site that mutates the tree if depth-limit violations are a realistic user action (e.g. dragging a node deep into a tree in a UI).

Besides HierarchyDepthExceededError, methods can throw a plain Error for: inserting a duplicate key under duplicateKeyStrategy: 'throw'; a cycle under cycleStrategy: 'throw'; violating node-key immutability (via update()'s new data, or a setParentKey callback that changes the key); or calling move() without setParentKey configured.

Duplicate keys

Controlled by duplicateKeyStrategy:

• 'throw' (default) — inserting an existing key throws.
• 'replace' — the existing node (and its subtree) is deleted and replaced by the new item. This is only done once every pre-check for the new node has passed (key immutability, cycle, depth) — if a later step fails (pending-adoption depth check, or a compare throw while re-sorting), the old node and its subtree are restored to their exact original position rather than left deleted.
• 'warn' — same as 'replace', but also reports a duplicate-key diagnostic (via onDiagnostic, or console.warn if not configured).

Cycle detection

Controlled by cycleStrategy, checked on every structural mutation (add, move, update, and when adopting a pending child):

• 'as-root' (default) — a mutation that would create a cycle is skipped; the node involved is left as (or becomes) a root instead, and an invalid-parent/cycle-detected diagnostic is reported. For pending adoption specifically, a cycle means that parent/child relationship is considered permanently unworkable under the current tree shape — the child stops waiting for that parent (its pending registration is cleared, not left dangling).
• 'throw' — a plain Error is thrown instead, and no state changes.

Out-of-order loading

Data doesn't have to arrive parent-first. If an item's parent key doesn't resolve to anything currently in the tree, the item becomes a root and is registered as pending — as soon as a node with that key is later inserted, all matching pending children (and their own subtrees) are adopted under it automatically, subject to the same cycle/depth checks as any other mutation:

tree.add({ id: 'child', parentId: 'not-yet-added', name: 'Child' }); // becomes a temporary root
tree.add({ id: 'not-yet-added', name: 'Parent' }); // 'child' is now adopted under it automatically

If adopting a batch of pending children would exceed maxDepth, or a later step in the same add() call fails (e.g. compare throwing while re-sorting), none of the pending children are lost or left in a broken state — they're restored to their pre-adoption position and pending status, and the new parent's own insertion is rolled back.

License

MIT License - see LICENSE for details.