0
# Tree Analysis
1

2
Index calculation, counting, and position comparison operations for tree structure analysis.
3

4
## Capabilities
5

6
### Index Calculation
7

8
Find the index position of an object among its siblings.
9

10
```javascript { .api }
11
/**
12
 * Find the index of the given object (number of preceding siblings)
13
 * Time Complexity: O(n) where n is the number of preceding siblings, O(1) amortized if tree not modified
14
 * @param {Object} child - Child object to find index of
15
 * @returns {number} The number of preceding siblings, or -1 if the object has no parent
16
 */
17
index(child: Object): number;
18
```
19

20
### Children Count
21

22
Calculate the number of children an object has.
23

24
```javascript { .api }
25
/**
26
 * Calculate the number of children
27
 * Time Complexity: O(n) where n is the number of children, O(1) amortized if tree not modified
28
 * @param {Object} parent - Parent object
29
 * @returns {number} Number of children
30
 */
31
childrenCount(parent: Object): number;
32
```
33

34
### Position Comparison
35

36
Compare the relative positions of two objects in the tree.
37

38
```javascript { .api }
39
/**
40
 * Compare the position of an object relative to another object
41
 * Time Complexity: O(n + m + o) where n,m are ancestor counts, o is common ancestor children
42
 * @param {Object} left - Left object (reference/context object)
43
 * @param {Object} right - Right object (other object)
44
 * @returns {number} Bitmask indicating relationship between objects
45
 */
46
compareTreePosition(left: Object, right: Object): number;
47
```
48

49
## Position Comparison Constants
50

51
The `compareTreePosition` method returns a bitmask with these possible values:
52

53
```javascript { .api }
54
// Access via SymbolTree.TreePosition
55
const TreePosition = {
56
  DISCONNECTED: 1,    // Objects are in different trees
57
  PRECEDING: 2,       // Left object precedes right object in tree order
58
  FOLLOWING: 4,       // Left object follows right object in tree order  
59
  CONTAINS: 8,        // Left object contains right object (left is ancestor of right)
60
  CONTAINED_BY: 16    // Left object is contained by right object (right is ancestor of left)
61
};
62
```
63

64
## Usage Examples
65

66
### Basic Index Operations
67

68
```javascript
69
const SymbolTree = require("symbol-tree");
70
const tree = new SymbolTree();
71

72
// Build a tree structure
73
const parent = { name: "parent" };
74
const child1 = { name: "child1" };
75
const child2 = { name: "child2" };
76
const child3 = { name: "child3" };
77

78
tree.appendChild(parent, child1);
79
tree.appendChild(parent, child2);
80
tree.appendChild(parent, child3);
81

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

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

91
// Count children
92
console.log(tree.childrenCount(parent)); // 3
93
console.log(tree.childrenCount(child1)); // 0 (no children)
94
```
95

96
### Position Comparison Examples
97

98
```javascript
99
// Build a more complex tree:
100
//     root
101
//    /    \
102
//   A      D
103
//  / \      \
104
// B   C      E
105
const root = { name: "root" };
106
const nodeA = { name: "A" };
107
const nodeB = { name: "B" };
108
const nodeC = { name: "C" };
109
const nodeD = { name: "D" };
110
const nodeE = { name: "E" };
111

112
tree.appendChild(root, nodeA);
113
tree.appendChild(root, nodeD);
114
tree.appendChild(nodeA, nodeB);
115
tree.appendChild(nodeA, nodeC);
116
tree.appendChild(nodeD, nodeE);
117

118
// Compare positions
119
const { TreePosition } = SymbolTree;
120

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

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

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

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

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

142
### Understanding Tree Order
143

144
Tree order is depth-first: root, A, B, C, D, E
145

146
```javascript
147
// Verify tree order using position comparison
148
function isInTreeOrder(node1, node2) {
149
  const relation = tree.compareTreePosition(node1, node2);
150
  return (relation & TreePosition.PRECEDING) !== 0;
151
}
152

153
console.log(isInTreeOrder(root, nodeA)); // true
154
console.log(isInTreeOrder(nodeA, nodeB)); // true
155
console.log(isInTreeOrder(nodeB, nodeC)); // true
156
console.log(isInTreeOrder(nodeC, nodeD)); // true
157
console.log(isInTreeOrder(nodeD, nodeE)); // true
158

159
// Reverse should be false
160
console.log(isInTreeOrder(nodeE, nodeD)); // false
161
```
162

163
### Disconnected Objects
164

165
```javascript
166
// Create separate tree
167
const otherRoot = { name: "otherRoot" };
168
const otherChild = { name: "otherChild" };
169
tree.appendChild(otherRoot, otherChild);
170

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

175
// Note: DISCONNECTED never occurs with other bits
176
console.log(disconnectedRelation & TreePosition.PRECEDING); // 0
177
console.log(disconnectedRelation & TreePosition.FOLLOWING); // 0
178
```
179

180
### Practical Analysis Functions
181

182
```javascript
183
// Find position of child among siblings
184
function getChildPosition(parent, targetChild) {
185
  const index = tree.index(targetChild);
186
  const total = tree.childrenCount(parent);
187
  
188
  return {
189
    index: index,
190
    total: total,
191
    isFirst: index === 0,
192
    isLast: index === total - 1,
193
    isEmpty: total === 0
194
  };
195
}
196

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

201
// Analyze tree structure
202
function analyzeNode(node) {
203
  const parent = tree.parent(node);
204
  const childCount = tree.childrenCount(node);
205
  const index = parent ? tree.index(node) : -1;
206
  
207
  return {
208
    hasParent: parent !== null,
209
    hasChildren: childCount > 0,
210
    childCount: childCount,
211
    siblingIndex: index,
212
    isRoot: parent === null,
213
    isLeaf: childCount === 0
214
  };
215
}
216

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

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

224
### Sorting and Ordering
225

226
```javascript
227
// Sort nodes by tree order
228
function sortByTreeOrder(nodes) {
229
  return nodes.slice().sort((a, b) => {
230
    const relation = tree.compareTreePosition(a, b);
231
    
232
    if (relation & TreePosition.PRECEDING) return -1;
233
    if (relation & TreePosition.FOLLOWING) return 1;
234
    if (relation & TreePosition.CONTAINS) return -1;
235
    if (relation & TreePosition.CONTAINED_BY) return 1;
236
    if (relation & TreePosition.DISCONNECTED) {
237
      // For disconnected nodes, fall back to name comparison
238
      return a.name.localeCompare(b.name);
239
    }
240
    return 0; // Same node
241
  });
242
}
243

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

249
// Find common ancestor
250
function findCommonAncestor(node1, node2) {
251
  const ancestors1 = [...tree.ancestorsIterator(node1)];
252
  const ancestors2 = [...tree.ancestorsIterator(node2)];
253
  
254
  // Find first common ancestor
255
  for (const ancestor1 of ancestors1) {
256
    for (const ancestor2 of ancestors2) {
257
      if (ancestor1 === ancestor2) {
258
        return ancestor1;
259
      }
260
    }
261
  }
262
  
263
  return null; // No common ancestor (disconnected)
264
}
265

266
console.log(findCommonAncestor(nodeB, nodeC).name); // "A"
267
console.log(findCommonAncestor(nodeB, nodeE).name); // "root"
268
```
269

270
### Performance Monitoring
271

272
```javascript
273
// Monitor index calculation performance
274
function measureIndexPerformance(parent, iterations = 1000) {
275
  const children = tree.childrenToArray(parent);
276
  if (children.length === 0) return;
277
  
278
  const startTime = performance.now();
279
  
280
  for (let i = 0; i < iterations; i++) {
281
    // Access index of random child
282
    const randomChild = children[Math.floor(Math.random() * children.length)];
283
    tree.index(randomChild);
284
  }
285
  
286
  const endTime = performance.now();
287
  const avgTime = (endTime - startTime) / iterations;
288
  
289
  console.log(`Average index lookup time: ${avgTime.toFixed(3)}ms`);
290
  return avgTime;
291
}
292

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

299
measureIndexPerformance(largeParent);
300
```
301

302
### DOM-Style Position Analysis
303

304
```javascript
305
// Simulate DOM position methods
306
function contains(container, contained) {
307
  if (container === contained) return true;
308
  
309
  const relation = tree.compareTreePosition(container, contained);
310
  return (relation & TreePosition.CONTAINS) !== 0;
311
}
312

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

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

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

329
// Find insertion point for ordered insertion
330
function findInsertionPoint(parent, newNode, compareFn) {
331
  const children = tree.childrenToArray(parent);
332
  
333
  for (let i = 0; i < children.length; i++) {
334
    if (compareFn(newNode, children[i]) < 0) {
335
      return children[i]; // Insert before this child
336
    }
337
  }
338
  
339
  return null; // Insert at end
340
}
341

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

348
if (insertBefore) {
349
  tree.insertBefore(insertBefore, newChild);
350
} else {
351
  tree.appendChild(nodeA, newChild);
352
}
353

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