Tree Iterators

/**
 * Iterate over all children of the given parent object
 * Time Complexity: O(1) for a single iteration
 * @param {Object} parent - Parent object
 * @param {Object} [options] - Iterator options
 * @param {boolean} [options.reverse=false] - Iterate in reverse order
 * @returns {Iterator<Object>} ES6 iterator over children
 */
childrenIterator(parent: Object, options?: { reverse?: boolean }): Iterator<Object>;

/**
 * Iterate over all previous siblings of the given object
 * Time Complexity: O(1) for a single iteration
 * @param {Object} object - Reference object
 * @returns {Iterator<Object>} ES6 iterator over previous siblings
 */
previousSiblingsIterator(object: Object): Iterator<Object>;

/**
 * Iterate over all next siblings of the given object
 * Time Complexity: O(1) for a single iteration
 * @param {Object} object - Reference object
 * @returns {Iterator<Object>} ES6 iterator over next siblings
 */
nextSiblingsIterator(object: Object): Iterator<Object>;

/**
 * Iterate over all inclusive ancestors of the given object
 * Time Complexity: O(1) for a single iteration
 * @param {Object} object - Starting object
 * @returns {Iterator<Object>} ES6 iterator over ancestors (including the object itself)
 */
ancestorsIterator(object: Object): Iterator<Object>;

/**
 * Iterate over all descendants of the given object in tree order
 * Time Complexity: O(n) worst case for single iteration, O(n) amortized when completing
 * @param {Object} root - Root object of tree/subtree
 * @param {Object} [options] - Iterator options
 * @param {boolean} [options.reverse=false] - Iterate in reverse tree order
 * @returns {Iterator<Object>} ES6 iterator over tree descendants
 */
treeIterator(root: Object, options?: { reverse?: boolean }): Iterator<Object>;

// Iterator interface
interface Iterator<T> {
  next(): IteratorResult<T>;
  [Symbol.iterator](): Iterator<T>;
}

interface IteratorResult<T> {
  done: boolean;
  value: T;
}

const SymbolTree = require("symbol-tree");
const tree = new SymbolTree();

// Build a tree structure
const parent = { name: "parent" };
const child1 = { name: "child1" };
const child2 = { name: "child2" };
const child3 = { name: "child3" };

tree.appendChild(parent, child1);
tree.appendChild(parent, child2);
tree.appendChild(parent, child3);

// Iterate over children using for...of
for (const child of tree.childrenIterator(parent)) {
  console.log(child.name);
}
// Output: child1, child2, child3

// Iterate in reverse
for (const child of tree.childrenIterator(parent, { reverse: true })) {
  console.log(child.name);
}
// Output: child3, child2, child1

// Manual iterator control
const childIterator = tree.childrenIterator(parent);

let result = childIterator.next();
while (!result.done) {
  console.log("Child:", result.value.name);
  result = childIterator.next();
}

// Or using the iterator protocol
const children = [...tree.childrenIterator(parent)];
console.log(children.map(c => c.name)); // ["child1", "child2", "child3"]

// Iterate over next siblings
for (const sibling of tree.nextSiblingsIterator(child1)) {
  console.log("Next sibling:", sibling.name);
}
// Output: Next sibling: child2, Next sibling: child3

// Iterate over previous siblings
for (const sibling of tree.previousSiblingsIterator(child3)) {
  console.log("Previous sibling:", sibling.name);
}
// Output: Previous sibling: child2, Previous sibling: child1

// Build larger tree
const grandchild1 = { name: "grandchild1" };
const grandchild2 = { name: "grandchild2" };
tree.appendChild(child1, grandchild1);
tree.appendChild(child2, grandchild2);

// Iterate over entire tree
console.log("Forward tree iteration:");
for (const node of tree.treeIterator(parent, { reverse: false })) {
  console.log(node.name);
}
// Output: parent, child1, grandchild1, child2, grandchild2, child3

console.log("Reverse tree iteration:");
for (const node of tree.treeIterator(parent, { reverse: true })) {
  console.log(node.name);
}
// Output: child3, grandchild2, child2, grandchild1, child1, parent

// Iterate up the ancestor chain
console.log("Ancestors of grandchild1:");
for (const ancestor of tree.ancestorsIterator(grandchild1)) {
  console.log(ancestor.name);
}
// Output: grandchild1, child1, parent

// Find first child matching condition
function findChild(parent, predicate) {
  for (const child of tree.childrenIterator(parent)) {
    if (predicate(child)) {
      return child;
    }
  }
  return null;
}

const firstChildWithName = findChild(parent, child => 
  child.name.includes("2")
);
console.log(firstChildWithName?.name); // "child2"

// Collect nodes at specific depth
function getNodesAtDepth(root, targetDepth) {
  const nodes = [];
  
  for (const node of tree.treeIterator(root)) {
    const ancestors = [...tree.ancestorsIterator(node)];
    const depth = ancestors.length - 1;
    
    if (depth === targetDepth) {
      nodes.push(node);
    }
  }
  
  return nodes;
}

const depthOneNodes = getNodesAtDepth(parent, 1);
console.log(depthOneNodes.map(n => n.name)); // ["child1", "child2", "child3"]

// Convert iterators to arrays for functional operations
const childNames = [...tree.childrenIterator(parent)]
  .map(child => child.name)
  .filter(name => name.includes("child"))
  .sort();

console.log(childNames); // ["child1", "child2", "child3"]

// Reduce over tree
const treeStats = [...tree.treeIterator(parent)]
  .reduce((stats, node) => {
    stats.total++;
    if (tree.hasChildren(node)) {
      stats.containers++;
    } else {
      stats.leaves++;
    }
    return stats;
  }, { total: 0, containers: 0, leaves: 0 });

console.log(treeStats); // { total: 6, containers: 3, leaves: 3 }

// Early termination (more efficient than converting to array first)
function findFirstLeafNode(root) {
  for (const node of tree.treeIterator(root)) {
    if (!tree.hasChildren(node)) {
      return node; // Stop immediately when found
    }
  }
  return null;
}

// Process in chunks to avoid memory pressure
function processTreeInChunks(root, chunkSize = 100) {
  let chunk = [];
  
  for (const node of tree.treeIterator(root)) {
    chunk.push(node);
    
    if (chunk.length >= chunkSize) {
      processChunk(chunk);
      chunk = []; // Clear for next chunk
    }
  }
  
  // Process remaining items
  if (chunk.length > 0) {
    processChunk(chunk);
  }
}

function processChunk(nodes) {
  // Do something with the chunk of nodes
  console.log(`Processing chunk of ${nodes.length} nodes`);
}

// Combine multiple iterators
function* getAllSiblings(node) {
  // Yield previous siblings in reverse order
  const prevSiblings = [...tree.previousSiblingsIterator(node)].reverse();
  for (const sibling of prevSiblings) {
    yield sibling;
  }
  
  // Yield the node itself
  yield node;
  
  // Yield next siblings
  for (const sibling of tree.nextSiblingsIterator(node)) {
    yield sibling;
  }
}

// Usage
console.log("All siblings of child2:");
for (const sibling of getAllSiblings(child2)) {
  console.log(sibling.name);
}
// Output: child1, child2, child3

// Create custom tree walker
function* walkTreeWithCallback(root, callback) {
  for (const node of tree.treeIterator(root)) {
    const result = callback(node);
    if (result) {
      yield { node, result };
    }
  }
}

// Usage
const results = [...walkTreeWithCallback(parent, node => {
  if (node.name.includes("child")) {
    return `Found child: ${node.name}`;
  }
})];

console.log(results);

// Simulate DOM traversal patterns
function* getElementsOfType(root, tagName) {
  for (const node of tree.treeIterator(root)) {
    if (node.tagName === tagName) {
      yield node;
    }
  }
}

function getParentElements(node) {
  const parents = [];
  
  for (const ancestor of tree.ancestorsIterator(node)) {
    if (ancestor !== node && ancestor.nodeType === "element") {
      parents.push(ancestor);
    }
  }
  
  return parents;
}

// Find next element sibling
function getNextElementSibling(node) {
  for (const sibling of tree.nextSiblingsIterator(node)) {
    if (sibling.nodeType === "element") {
      return sibling;
    }
  }
  return null;
}