var DncTree = (() => {
  var __defProp = Object.defineProperty;
  var __getOwnPropDesc = Object.getOwnPropertyDescriptor;
  var __getOwnPropNames = Object.getOwnPropertyNames;
  var __hasOwnProp = Object.prototype.hasOwnProperty;
  var __export = (target, all) => {
    for (var name in all)
      __defProp(target, name, { get: all[name], enumerable: true });
  };
  var __copyProps = (to, from, except, desc) => {
    if (from && typeof from === "object" || typeof from === "function") {
      for (let key of __getOwnPropNames(from))
        if (!__hasOwnProp.call(to, key) && key !== except)
          __defProp(to, key, { get: () => from[key], enumerable: !(desc = __getOwnPropDesc(from, key)) || desc.enumerable });
    }
    return to;
  };
  var __toCommonJS = (mod) => __copyProps(__defProp({}, "__esModule", { value: true }), mod);

  // ../todoapp/apps/api/src/dnc/domain/dnc-tree.ts
  var dnc_tree_exports = {};
  __export(dnc_tree_exports, {
    buildTree: () => buildTree,
    collectSubtreeIds: () => collectSubtreeIds,
    flattenTree: () => flattenTree,
    insertIntoTree: () => insertIntoTree,
    planMove: () => planMove,
    removeFromTree: () => removeFromTree
  });
  function planMove(allNodes, intent) {
    const sorted = [...allNodes].sort(
      (a, b) => a.depth - b.depth || a.sortOrder - b.sortOrder
    );
    const oldTree = buildTree(sorted);
    if (intent.newParentId != null) {
      const descendantIds = collectSubtreeIds(oldTree, intent.nodeId);
      if (descendantIds.includes(intent.newParentId)) {
        throw "Cannot move a node under its own descendant";
      }
    }
    const { tree: treeWithout, removed } = removeFromTree(oldTree, intent.nodeId);
    if (!removed) {
      throw `Node ${intent.nodeId} not found in tree`;
    }
    const newTree = insertIntoTree(
      treeWithout,
      removed,
      intent.newParentId,
      intent.sortOrder
    );
    const newFlat = flattenTree(newTree);
    const oldMap = /* @__PURE__ */ new Map();
    for (const n of sorted) {
      oldMap.set(n.id, n);
    }
    const updates = [];
    for (const n of newFlat) {
      const old = oldMap.get(n.id);
      if (!old || old.parentId !== n.parentId || old.sortOrder !== n.sortOrder || old.depth !== n.depth || old.rootNodeId !== n.rootNodeId) {
        updates.push({
          id: n.id,
          data: {
            parentId: n.parentId,
            sortOrder: n.sortOrder,
            depth: n.depth,
            rootNodeId: n.rootNodeId
          }
        });
      }
    }
    return updates;
  }
  function buildTree(nodes) {
    const map = /* @__PURE__ */ new Map();
    const roots = [];
    for (const node of nodes) {
      map.set(node.id, { ...node, children: [] });
    }
    for (const node of nodes) {
      const current = map.get(node.id);
      if (node.parentId === null || !map.has(node.parentId)) {
        roots.push(current);
      } else {
        map.get(node.parentId).children.push(current);
      }
    }
    return roots;
  }
  function collectSubtreeIds(tree, id) {
    const ids = [];
    function walk(nodes) {
      for (const node of nodes) {
        if (node.id === id) {
          collect(node);
          return true;
        }
        if (walk(node.children)) return true;
      }
      return false;
    }
    function collect(node) {
      ids.push(node.id);
      for (const child of node.children) {
        collect(child);
      }
    }
    walk(tree);
    return ids;
  }
  function removeFromTree(tree, id) {
    let removed = null;
    function walk(nodes) {
      return nodes.reduce((acc, node) => {
        if (node.id === id) {
          removed = node;
          return acc;
        }
        acc.push({ ...node, children: walk(node.children) });
        return acc;
      }, []);
    }
    return { tree: walk(tree), removed };
  }
  function insertIntoTree(tree, node, parentId, sortOrder) {
    if (parentId === null) {
      const result = [...tree];
      const index = Math.min(sortOrder, result.length);
      result.splice(index, 0, node);
      return result;
    }
    return tree.map((root) => {
      if (root.id === parentId) {
        const children = [...root.children];
        const index = Math.min(sortOrder, children.length);
        children.splice(index, 0, node);
        return { ...root, children };
      }
      return {
        ...root,
        children: insertIntoTree(root.children, node, parentId, sortOrder)
      };
    });
  }
  function flattenTree(tree) {
    const result = [];
    function walk(nodes, parentId, depth, rootNodeId) {
      for (let i = 0; i < nodes.length; i++) {
        const node = nodes[i];
        let nodeRootId;
        if (parentId === null) {
          nodeRootId = null;
        } else {
          nodeRootId = rootNodeId ?? parentId;
        }
        result.push({
          id: node.id,
          parentId,
          sortOrder: i,
          depth,
          rootNodeId: nodeRootId
        });
        const childRootId = nodeRootId ?? node.id;
        walk(node.children, node.id, depth + 1, childRootId);
      }
    }
    walk(tree, null, 0, null);
    return result;
  }
  return __toCommonJS(dnc_tree_exports);
})();
