normalizeSyncedNodes<TKey, TItem> function

NormalizedTreeInput<TKey, TItem> normalizeSyncedNodes<TKey, TItem>(Iterable<SyncedTreeNode<TKey, TItem>> tree)

Normalizes a nested SyncedTreeNode tree (the default constructor's input mode).

The walk rejects cycles via visiting, keys repeated anywhere in the tree via seen, and keys repeated among one node's children via seenChildren. Reachability needs no separate check: every emitted node was reached by the walk.

Implementation

NormalizedTreeInput<TKey, TItem> normalizeSyncedNodes<TKey, TItem>(
  Iterable<SyncedTreeNode<TKey, TItem>> tree,
) {
  final roots = <TreeNode<TKey, TItem>>[];
  final childrenByParent = <TKey, List<TreeNode<TKey, TItem>>>{};
  final seen = <TKey>{};
  final visiting = <TKey>{};
  // Iterative DFS so a deep input tree cannot overflow the stack. Each
  // node's built [TreeNode] is kept in `nodeByKey`, which is what lets an
  // exit frame assemble `childrenByParent[key]` from children that are
  // already built by the time it pops.
  final nodeByKey = <TKey, TreeNode<TKey, TItem>>{};

  final stack = <SyncedTreeNode<TKey, TItem>>[];
  final isRootStack = <bool>[];
  // true = post-order exit frame, false = pre-order entry frame.
  final exitMarkers = <bool>[];

  // Push roots in reverse so the first root pops first, preserving
  // input order; same trick as the children push below.
  final rootList = tree is List<SyncedTreeNode<TKey, TItem>>
      ? tree
      : tree.toList(growable: false);
  for (int i = rootList.length - 1; i >= 0; i--) {
    stack.add(rootList[i]);
    isRootStack.add(true);
    exitMarkers.add(false);
  }

  while (stack.isNotEmpty) {
    final node = stack.removeLast();
    final isRoot = isRootStack.removeLast();
    final isExit = exitMarkers.removeLast();

    if (isExit) {
      visiting.remove(node.key);
      if (node.children.isNotEmpty) {
        final childNodes = <TreeNode<TKey, TItem>>[];
        for (final child in node.children) {
          childNodes.add(nodeByKey[child.key]!);
        }
        childrenByParent[node.key] = childNodes;
      }
      continue;
    }

    final key = node.key;
    if (!visiting.add(key)) {
      throw ArgumentError(
        "SyncedSliverTree.tree detected a cycle involving key \"$key\".",
      );
    }
    if (!seen.add(key)) {
      throw ArgumentError(
        "SyncedSliverTree.tree encountered duplicate key \"$key\".",
      );
    }

    // Validate sibling-key uniqueness here, in the parent's frame,
    // rather than as each child is visited: the error can then name the
    // parent the duplicates sit under, which is what a caller needs in
    // order to find them.
    final seenChildren = <TKey>{};
    for (final child in node.children) {
      if (!seenChildren.add(child.key)) {
        throw ArgumentError(
          "SyncedSliverTree.tree encountered duplicate child key "
          "\"${child.key}\" under parent \"$key\".",
        );
      }
    }

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

    // Push the exit marker FIRST so it pops AFTER every child. That is
    // what makes the frame post-order, and both the `visiting.remove(key)`
    // and the `childrenByParent[key]` assembly require every child to
    // have been visited already.
    stack.add(node);
    isRootStack.add(false);
    exitMarkers.add(true);

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

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