normalizeHierarchy<TKey, TItem> function

NormalizedTreeInput<TKey, TItem> normalizeHierarchy<TKey, TItem>({ required Iterable<TItem> roots, required TKey keyOf(TItem item), required Iterable<TItem> childrenOf(TItem item), })

Normalizes nested domain objects (the .hierarchy input mode).

The walk itself establishes every invariant on the way past: cycles via visiting, global key uniqueness via the nodeByKey guard (which is also what rejects a node under two parents, and a root that reappears as a child), sibling uniqueness via seenChildren, and reachability by construction, since every emitted node was reached by the DFS.

Implementation

NormalizedTreeInput<TKey, TItem> normalizeHierarchy<TKey, TItem>({
  required Iterable<TItem> roots,
  required TKey Function(TItem item) keyOf,
  required Iterable<TItem> Function(TItem item) childrenOf,
}) {
  final rootNodes = <TreeNode<TKey, TItem>>[];
  final childrenByParent = <TKey, List<TreeNode<TKey, TItem>>>{};
  final nodeByKey = <TKey, TreeNode<TKey, TItem>>{};
  final visiting = <TKey>{};

  // Iterative DFS so deep hierarchies do not stack-overflow Dart's
  // recursion limit. Three parallel stacks: `items` holds the work
  // queue; `exitMarkers` mirrors it as `null` for entry frames or as
  // the key whose `visiting` slot must be cleared on exit (post-order);
  // `exitChildKeys` carries each exit frame's child keys so the exit pop
  // can assemble `childrenByParent` from the children's already-built
  // [TreeNode]s. Exit frames push and pop in matching LIFO order, so the
  // two exit stacks stay aligned.
  final items = <TItem>[];
  final isRootStack = <bool>[];
  final exitMarkers = <TKey?>[];
  final exitChildKeys = <List<TKey>>[];

  // Push roots in REVERSE so the first root pops first. `items` is a
  // LIFO stack, so seeding it forward would reverse the whole root list
  // in the output while child order, pushed in reverse below, stayed
  // correct. Same trick, same reason, as the children loop.
  final rootList = roots is List<TItem> ? roots : roots.toList(growable: false);
  for (int i = rootList.length - 1; i >= 0; i--) {
    items.add(rootList[i]);
    isRootStack.add(true);
    exitMarkers.add(null);
  }

  while (items.isNotEmpty) {
    final item = items.removeLast();
    final isRoot = isRootStack.removeLast();
    final exitKey = exitMarkers.removeLast();

    if (exitKey != null) {
      // Post-order pop: leaving this key's subtree, whose children have
      // all been built by now.
      visiting.remove(exitKey);
      final childKeys = exitChildKeys.removeLast();
      if (childKeys.isNotEmpty) {
        childrenByParent[exitKey] = <TreeNode<TKey, TItem>>[
          for (final childKey in childKeys) nodeByKey[childKey]!,
        ];
      }
      continue;
    }

    final key = keyOf(item);
    if (!visiting.add(key)) {
      throw ArgumentError(
        "SyncedSliverTree.hierarchy detected a cycle involving key "
        "\"$key\".",
      );
    }
    if (nodeByKey.containsKey(key)) {
      throw ArgumentError(
        "SyncedSliverTree.hierarchy encountered duplicate key \"$key\".",
      );
    }

    final treeNode = TreeNode<TKey, TItem>(key: key, data: item);
    nodeByKey[key] = treeNode;
    if (isRoot) {
      rootNodes.add(treeNode);
    }

    final childKeys = <TKey>[];
    final seenChildren = <TKey>{};
    // Resolve children once so we can both record their keys and push
    // them in the correct visit order (last-pushed = first-popped).
    final childItems = <TItem>[];
    for (final child in childrenOf(item)) {
      final childKey = keyOf(child);
      if (!seenChildren.add(childKey)) {
        throw ArgumentError(
          "SyncedSliverTree.hierarchy encountered duplicate child key "
          "\"$childKey\" under parent \"$key\".",
        );
      }
      childKeys.add(childKey);
      childItems.add(child);
    }

    // Push the exit marker FIRST so it pops AFTER every child, which is
    // what defers `visiting.remove(key)` to the end of this subtree.
    items.add(item); // placeholder, ignored on exit pop
    isRootStack.add(false);
    exitMarkers.add(key);
    exitChildKeys.add(childKeys);

    // Then push children in reverse so the first child pops first,
    // preserving left-to-right visit order.
    for (int i = childItems.length - 1; i >= 0; i--) {
      items.add(childItems[i]);
      isRootStack.add(false);
      exitMarkers.add(null);
    }
  }

  return NormalizedTreeInput<TKey, TItem>(
    roots: rootNodes,
    childrenByParent: childrenByParent,
  );
}