Tree Analysis

/**
 * Find the index of the given object (number of preceding siblings)
 * Time Complexity: O(n) where n is the number of preceding siblings, O(1) amortized if tree not modified
 * @param {Object} child - Child object to find index of
 * @returns {number} The number of preceding siblings, or -1 if the object has no parent
 */
index(child: Object): number;

/**
 * Calculate the number of children
 * Time Complexity: O(n) where n is the number of children, O(1) amortized if tree not modified
 * @param {Object} parent - Parent object
 * @returns {number} Number of children
 */
childrenCount(parent: Object): number;

/**
 * Compare the position of an object relative to another object
 * Time Complexity: O(n + m + o) where n,m are ancestor counts, o is common ancestor children
 * @param {Object} left - Left object (reference/context object)
 * @param {Object} right - Right object (other object)
 * @returns {number} Bitmask indicating relationship between objects
 */
compareTreePosition(left: Object, right: Object): number;

// Access via SymbolTree.TreePosition
const TreePosition = {
  DISCONNECTED: 1,    // Objects are in different trees
  PRECEDING: 2,       // Left object precedes right object in tree order
  FOLLOWING: 4,       // Left object follows right object in tree order  
  CONTAINS: 8,        // Left object contains right object (left is ancestor of right)
  CONTAINED_BY: 16    // Left object is contained by right object (right is ancestor of left)
};

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);

// Get indices
console.log(tree.index(child1)); // 0 (first child)
console.log(tree.index(child2)); // 1 (second child)
console.log(tree.index(child3)); // 2 (third child)

// Object with no parent
const orphan = { name: "orphan" };
console.log(tree.index(orphan)); // -1

// Count children
console.log(tree.childrenCount(parent)); // 3
console.log(tree.childrenCount(child1)); // 0 (no children)

// Build a more complex tree:
//     root
//    /    \
//   A      D
//  / \      \
// B   C      E
const root = { name: "root" };
const nodeA = { name: "A" };
const nodeB = { name: "B" };
const nodeC = { name: "C" };
const nodeD = { name: "D" };
const nodeE = { name: "E" };

tree.appendChild(root, nodeA);
tree.appendChild(root, nodeD);
tree.appendChild(nodeA, nodeB);
tree.appendChild(nodeA, nodeC);
tree.appendChild(nodeD, nodeE);

// Compare positions
const { TreePosition } = SymbolTree;

// A contains B (A is ancestor of B)
const aToBRelation = tree.compareTreePosition(nodeA, nodeB);
console.log(aToBRelation === TreePosition.CONTAINS); // true

// B is contained by A (B is descendant of A)
const bToARelation = tree.compareTreePosition(nodeB, nodeA);
console.log(bToARelation === TreePosition.CONTAINED_BY); // true

// B precedes C (B comes before C in tree order)
const bToCRelation = tree.compareTreePosition(nodeB, nodeC);
console.log(bToCRelation === TreePosition.PRECEDING); // true

// C follows B (C comes after B in tree order)
const cToBRelation = tree.compareTreePosition(nodeC, nodeB);
console.log(cToBRelation === TreePosition.FOLLOWING); // true

// A precedes D (A comes before D in tree order)
const aToDRelation = tree.compareTreePosition(nodeA, nodeD);
console.log(aToDRelation === TreePosition.PRECEDING); // true

// Verify tree order using position comparison
function isInTreeOrder(node1, node2) {
  const relation = tree.compareTreePosition(node1, node2);
  return (relation & TreePosition.PRECEDING) !== 0;
}

console.log(isInTreeOrder(root, nodeA)); // true
console.log(isInTreeOrder(nodeA, nodeB)); // true
console.log(isInTreeOrder(nodeB, nodeC)); // true
console.log(isInTreeOrder(nodeC, nodeD)); // true
console.log(isInTreeOrder(nodeD, nodeE)); // true

// Reverse should be false
console.log(isInTreeOrder(nodeE, nodeD)); // false

// Create separate tree
const otherRoot = { name: "otherRoot" };
const otherChild = { name: "otherChild" };
tree.appendChild(otherRoot, otherChild);

// Compare objects from different trees
const disconnectedRelation = tree.compareTreePosition(nodeA, otherChild);
console.log(disconnectedRelation === TreePosition.DISCONNECTED); // true

// Note: DISCONNECTED never occurs with other bits
console.log(disconnectedRelation & TreePosition.PRECEDING); // 0
console.log(disconnectedRelation & TreePosition.FOLLOWING); // 0

// Find position of child among siblings
function getChildPosition(parent, targetChild) {
  const index = tree.index(targetChild);
  const total = tree.childrenCount(parent);
  
  return {
    index: index,
    total: total,
    isFirst: index === 0,
    isLast: index === total - 1,
    isEmpty: total === 0
  };
}

const position = getChildPosition(parent, child2);
console.log(position);
// { index: 1, total: 3, isFirst: false, isLast: false, isEmpty: false }

// Analyze tree structure
function analyzeNode(node) {
  const parent = tree.parent(node);
  const childCount = tree.childrenCount(node);
  const index = parent ? tree.index(node) : -1;
  
  return {
    hasParent: parent !== null,
    hasChildren: childCount > 0,
    childCount: childCount,
    siblingIndex: index,
    isRoot: parent === null,
    isLeaf: childCount === 0
  };
}

console.log(analyzeNode(root));
// { hasParent: false, hasChildren: true, childCount: 2, siblingIndex: -1, isRoot: true, isLeaf: false }

console.log(analyzeNode(nodeB));
// { hasParent: true, hasChildren: false, childCount: 0, siblingIndex: 0, isRoot: false, isLeaf: true }

// Sort nodes by tree order
function sortByTreeOrder(nodes) {
  return nodes.slice().sort((a, b) => {
    const relation = tree.compareTreePosition(a, b);
    
    if (relation & TreePosition.PRECEDING) return -1;
    if (relation & TreePosition.FOLLOWING) return 1;
    if (relation & TreePosition.CONTAINS) return -1;
    if (relation & TreePosition.CONTAINED_BY) return 1;
    if (relation & TreePosition.DISCONNECTED) {
      // For disconnected nodes, fall back to name comparison
      return a.name.localeCompare(b.name);
    }
    return 0; // Same node
  });
}

const shuffledNodes = [nodeE, nodeB, root, nodeD, nodeA, nodeC];
const sortedNodes = sortByTreeOrder(shuffledNodes);
console.log(sortedNodes.map(n => n.name));
// ["root", "A", "B", "C", "D", "E"] (tree order)

// Find common ancestor
function findCommonAncestor(node1, node2) {
  const ancestors1 = [...tree.ancestorsIterator(node1)];
  const ancestors2 = [...tree.ancestorsIterator(node2)];
  
  // Find first common ancestor
  for (const ancestor1 of ancestors1) {
    for (const ancestor2 of ancestors2) {
      if (ancestor1 === ancestor2) {
        return ancestor1;
      }
    }
  }
  
  return null; // No common ancestor (disconnected)
}

console.log(findCommonAncestor(nodeB, nodeC).name); // "A"
console.log(findCommonAncestor(nodeB, nodeE).name); // "root"

// Monitor index calculation performance
function measureIndexPerformance(parent, iterations = 1000) {
  const children = tree.childrenToArray(parent);
  if (children.length === 0) return;
  
  const startTime = performance.now();
  
  for (let i = 0; i < iterations; i++) {
    // Access index of random child
    const randomChild = children[Math.floor(Math.random() * children.length)];
    tree.index(randomChild);
  }
  
  const endTime = performance.now();
  const avgTime = (endTime - startTime) / iterations;
  
  console.log(`Average index lookup time: ${avgTime.toFixed(3)}ms`);
  return avgTime;
}

// Create large tree for testing
const largeParent = { name: "largeParent" };
for (let i = 0; i < 1000; i++) {
  tree.appendChild(largeParent, { name: `child${i}` });
}

measureIndexPerformance(largeParent);

// Simulate DOM position methods
function contains(container, contained) {
  if (container === contained) return true;
  
  const relation = tree.compareTreePosition(container, contained);
  return (relation & TreePosition.CONTAINS) !== 0;
}

function isBefore(node1, node2) {
  const relation = tree.compareTreePosition(node1, node2);
  return (relation & TreePosition.PRECEDING) !== 0;
}

function isAfter(node1, node2) {
  const relation = tree.compareTreePosition(node1, node2);
  return (relation & TreePosition.FOLLOWING) !== 0;
}

// Usage
console.log(contains(nodeA, nodeB)); // true (A contains B)
console.log(contains(nodeB, nodeA)); // false (B doesn't contain A)
console.log(isBefore(nodeA, nodeD)); // true (A comes before D)
console.log(isAfter(nodeD, nodeA)); // true (D comes after A)

// Find insertion point for ordered insertion
function findInsertionPoint(parent, newNode, compareFn) {
  const children = tree.childrenToArray(parent);
  
  for (let i = 0; i < children.length; i++) {
    if (compareFn(newNode, children[i]) < 0) {
      return children[i]; // Insert before this child
    }
  }
  
  return null; // Insert at end
}

// Usage: insert in alphabetical order
const newChild = { name: "BB" };
const insertBefore = findInsertionPoint(nodeA, newChild, 
  (a, b) => a.name.localeCompare(b.name)
);

if (insertBefore) {
  tree.insertBefore(insertBefore, newChild);
} else {
  tree.appendChild(nodeA, newChild);
}

// Verify order
console.log(tree.childrenToArray(nodeA).map(c => c.name));
// ["B", "BB", "C"] (alphabetical order maintained)