normalizeFlat<TKey, TItem> function

NormalizedTreeInput<TKey, TItem> normalizeFlat<TKey, TItem>({ required Iterable<TItem> items, required TKey keyOf(TItem item), required TKey? parentOf(TItem item), })

Normalizes flat items plus parent keys (the .flat input mode).

Sibling order follows the iteration order of items. A parentOf result that names a key absent from items is rejected with ArgumentError, listing every offending (child, parent) pair. Returning null is the explicit way to make an item a root: a filter flow that removes a parent while keeping its children forgives exactly the orphans it created by guarding the stored parent key with a set of the live keys and returning null for filtered-out parents.

Implementation

NormalizedTreeInput<TKey, TItem> normalizeFlat<TKey, TItem>({
  required Iterable<TItem> items,
  required TKey Function(TItem item) keyOf,
  required TKey? Function(TItem item) parentOf,
}) {
  final orderedItems = List<TItem>.of(items);
  final nodeByKey = <TKey, TreeNode<TKey, TItem>>{};

  for (final item in orderedItems) {
    final key = keyOf(item);
    if (nodeByKey.containsKey(key)) {
      throw ArgumentError(
        "SyncedSliverTree.flat encountered duplicate key \"$key\".",
      );
    }
    nodeByKey[key] = TreeNode<TKey, TItem>(key: key, data: item);
  }

  final rootNodes = <TreeNode<TKey, TItem>>[];
  final childrenByParent = <TKey, List<TreeNode<TKey, TItem>>>{};
  // child key -> the missing parent key it named. Collected across the
  // whole pass and thrown as ONE error: a filtering bug typically
  // orphans many items at once, and naming only the first would hide
  // the blast radius. Same list-all shape as the reachability error.
  final missingParents = <TKey, TKey>{};
  for (final item in orderedItems) {
    final key = keyOf(item);
    final parentKey = parentOf(item);

    if (parentKey == null) {
      rootNodes.add(nodeByKey[key]!);
    } else if (nodeByKey.containsKey(parentKey)) {
      final children = childrenByParent.putIfAbsent(
        parentKey,
        () => <TreeNode<TKey, TItem>>[],
      );
      children.add(nodeByKey[key]!);
    } else {
      missingParents[key] = parentKey;
    }
  }
  if (missingParents.isNotEmpty) {
    throw ArgumentError(
      "SyncedSliverTree.flat: parentOf returned parent keys that are "
      "absent from items: $missingParents. If this is intentional (a "
      "filtered-out parent whose children should surface as roots), "
      "return null from parentOf for those items instead; guard the "
      "stored parent key with a set of the keys currently in items.",
    );
  }

  // Reachability. Unlike the DFS-based normalizers, the two-pass build
  // above cannot establish it by construction: a mutual parent cycle
  // (`a` claims `b` as parent while `b` claims `a`) yields nodes that
  // hang under each other with no path from any root, and without this
  // walk they would silently never render. Iterative for the same
  // deep-input reason as the DFS walks.
  final reached = <TKey>{};
  final stack = <TKey>[for (final root in rootNodes) root.key];
  while (stack.isNotEmpty) {
    final key = stack.removeLast();
    if (!reached.add(key)) {
      continue;
    }
    final children = childrenByParent[key];
    if (children != null) {
      for (final child in children) {
        stack.add(child.key);
      }
    }
  }
  if (reached.length != nodeByKey.length) {
    final unreachable = <TKey>[
      for (final key in nodeByKey.keys)
        if (!reached.contains(key)) key,
    ];
    throw ArgumentError(
      "SyncedSliverTree.flat contains unreachable nodes (a parent "
      "cycle): $unreachable.",
    );
  }

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