Debian Codegraph @

closure-library/closure/goog/structs/treenode.js

raw
1 // Copyright 2010 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Generic tree node data structure with arbitrary number of child
17 * nodes.
18 *
19 */
20
21 goog.provide('goog.structs.TreeNode');
22
23 goog.require('goog.array');
24 goog.require('goog.asserts');
25 goog.require('goog.structs.Node');
26
27
28
29 /**
30 * Generic tree node data structure with arbitrary number of child nodes.
31 * It is possible to create a dynamic tree structure by overriding
32 * {@link #getParent} and {@link #getChildren} in a subclass. All other getters
33 * will automatically work.
34 *
35 * @param {KEY} key Key.
36 * @param {VALUE} value Value.
37 * @constructor
38 * @extends {goog.structs.Node<KEY, VALUE>}
39 * @template KEY, VALUE
40 */
41 goog.structs.TreeNode = function(key, value) {
42 goog.structs.Node.call(this, key, value);
43
44 /**
45 * Reference to the parent node or null if it has no parent.
46 * @private {goog.structs.TreeNode<KEY, VALUE>}
47 */
48 this.parent_ = null;
49
50 /**
51 * Child nodes or null in case of leaf node.
52 * @private {Array<!goog.structs.TreeNode<KEY, VALUE>>}
53 */
54 this.children_ = null;
55 };
56 goog.inherits(goog.structs.TreeNode, goog.structs.Node);
57
58
59 /**
60 * Constant for empty array to avoid unnecessary allocations.
61 * @private
62 */
63 goog.structs.TreeNode.EMPTY_ARRAY_ = [];
64
65
66 /**
67 * @return {!goog.structs.TreeNode} Clone of the tree node without its parent
68 * and child nodes. The key and the value are copied by reference.
69 * @override
70 */
71 goog.structs.TreeNode.prototype.clone = function() {
72 return new goog.structs.TreeNode(this.getKey(), this.getValue());
73 };
74
75
76 /**
77 * @return {!goog.structs.TreeNode} Clone of the subtree with this node as root.
78 */
79 goog.structs.TreeNode.prototype.deepClone = function() {
80 var clone = this.clone();
81 this.forEachChild(function(child) { clone.addChild(child.deepClone()); });
82 return clone;
83 };
84
85
86 /**
87 * @return {goog.structs.TreeNode<KEY, VALUE>} Parent node or null if it has no
88 * parent.
89 */
90 goog.structs.TreeNode.prototype.getParent = function() {
91 return this.parent_;
92 };
93
94
95 /**
96 * @return {boolean} Whether the node is a leaf node.
97 */
98 goog.structs.TreeNode.prototype.isLeaf = function() {
99 return !this.getChildCount();
100 };
101
102
103 /**
104 * Tells if the node is the last child of its parent. This method helps how to
105 * connect the tree nodes with lines: L shapes should be used before the last
106 * children and |- shapes before the rest. Schematic tree visualization:
107 *
108 * <pre>
109 * Node1
110 * |-Node2
111 * | L-Node3
112 * | |-Node4
113 * | L-Node5
114 * L-Node6
115 * </pre>
116 *
117 * @return {boolean} Whether the node has parent and is the last child of it.
118 */
119 goog.structs.TreeNode.prototype.isLastChild = function() {
120 var parent = this.getParent();
121 return Boolean(parent && this == goog.array.peek(parent.getChildren()));
122 };
123
124
125 /**
126 * @return {!Array<!goog.structs.TreeNode<KEY, VALUE>>} Immutable child nodes.
127 */
128 goog.structs.TreeNode.prototype.getChildren = function() {
129 return this.children_ || goog.structs.TreeNode.EMPTY_ARRAY_;
130 };
131
132
133 /**
134 * Gets the child node of this node at the given index.
135 * @param {number} index Child index.
136 * @return {goog.structs.TreeNode<KEY, VALUE>} The node at the given index or
137 * null if not found.
138 */
139 goog.structs.TreeNode.prototype.getChildAt = function(index) {
140 return this.getChildren()[index] || null;
141 };
142
143
144 /**
145 * @return {number} The number of children.
146 */
147 goog.structs.TreeNode.prototype.getChildCount = function() {
148 return this.getChildren().length;
149 };
150
151
152 /**
153 * @return {number} The number of ancestors of the node.
154 */
155 goog.structs.TreeNode.prototype.getDepth = function() {
156 var depth = 0;
157 var node = this;
158 while (node.getParent()) {
159 depth++;
160 node = node.getParent();
161 }
162 return depth;
163 };
164
165
166 /**
167 * @return {!Array<!goog.structs.TreeNode<KEY, VALUE>>} All ancestor nodes in
168 * bottom-up order.
169 */
170 goog.structs.TreeNode.prototype.getAncestors = function() {
171 var ancestors = [];
172 var node = this.getParent();
173 while (node) {
174 ancestors.push(node);
175 node = node.getParent();
176 }
177 return ancestors;
178 };
179
180
181 /**
182 * @return {!goog.structs.TreeNode<KEY, VALUE>} The root of the tree structure,
183 * i.e. the farthest ancestor of the node or the node itself if it has no
184 * parents.
185 */
186 goog.structs.TreeNode.prototype.getRoot = function() {
187 var root = this;
188 while (root.getParent()) {
189 root = root.getParent();
190 }
191 return root;
192 };
193
194
195 /**
196 * Builds a nested array structure from the node keys in this node's subtree to
197 * facilitate testing tree operations that change the hierarchy.
198 * @return {!Array<KEY>} The structure of this node's descendants as nested
199 * array of node keys. The number of unclosed opening brackets up to a
200 * particular node is proportional to the indentation of that node in the
201 * graphical representation of the tree. Example:
202 * <pre>
203 * this
204 * |- child1
205 * | L- grandchild
206 * L- child2
207 * </pre>
208 * is represented as ['child1', ['grandchild'], 'child2'].
209 */
210 goog.structs.TreeNode.prototype.getSubtreeKeys = function() {
211 var ret = [];
212 this.forEachChild(function(child) {
213 ret.push(child.getKey());
214 if (!child.isLeaf()) {
215 ret.push(child.getSubtreeKeys());
216 }
217 });
218 return ret;
219 };
220
221
222 /**
223 * Tells whether this node is the ancestor of the given node.
224 * @param {!goog.structs.TreeNode<KEY, VALUE>} node A node.
225 * @return {boolean} Whether this node is the ancestor of {@code node}.
226 */
227 goog.structs.TreeNode.prototype.contains = function(node) {
228 var current = node;
229 do {
230 current = current.getParent();
231 } while (current && current != this);
232 return Boolean(current);
233 };
234
235
236 /**
237 * Finds the deepest common ancestor of the given nodes. The concept of
238 * ancestor is not strict in this case, it includes the node itself.
239 * @param {...!goog.structs.TreeNode<KEY, VALUE>} var_args The nodes.
240 * @return {goog.structs.TreeNode<KEY, VALUE>} The common ancestor of the nodes
241 * or null if they are from different trees.
242 * @template KEY, VALUE
243 */
244 goog.structs.TreeNode.findCommonAncestor = function(var_args) {
245 /** @type {goog.structs.TreeNode} */
246 var ret = arguments[0];
247 if (!ret) {
248 return null;
249 }
250
251 var retDepth = ret.getDepth();
252 for (var i = 1; i < arguments.length; i++) {
253 /** @type {goog.structs.TreeNode} */
254 var node = arguments[i];
255 var depth = node.getDepth();
256 while (node != ret) {
257 if (depth <= retDepth) {
258 ret = ret.getParent();
259 retDepth--;
260 }
261 if (depth > retDepth) {
262 node = node.getParent();
263 depth--;
264 }
265 }
266 }
267
268 return ret;
269 };
270
271
272 /**
273 * Returns a node whose key matches the given one in the hierarchy rooted at
274 * this node. The hierarchy is searched using an in-order traversal.
275 * @param {KEY} key The key to search for.
276 * @return {goog.structs.TreeNode<KEY, VALUE>} The node with the given key, or
277 * null if no node with the given key exists in the hierarchy.
278 */
279 goog.structs.TreeNode.prototype.getNodeByKey = function(key) {
280 if (this.getKey() == key) {
281 return this;
282 }
283 var children = this.getChildren();
284 for (var i = 0; i < children.length; i++) {
285 var descendant = children[i].getNodeByKey(key);
286 if (descendant) {
287 return descendant;
288 }
289 }
290 return null;
291 };
292
293
294 /**
295 * Traverses all child nodes.
296 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>, number,
297 * !Array<!goog.structs.TreeNode<KEY, VALUE>>)} f Callback function. It
298 * takes the node, its index and the array of all child nodes as arguments.
299 * @param {THIS=} opt_this The object to be used as the value of {@code this}
300 * within {@code f}.
301 * @template THIS
302 */
303 goog.structs.TreeNode.prototype.forEachChild = function(f, opt_this) {
304 goog.array.forEach(this.getChildren(), f, opt_this);
305 };
306
307
308 /**
309 * Traverses all child nodes recursively in preorder.
310 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>)} f Callback
311 * function. It takes the node as argument.
312 * @param {THIS=} opt_this The object to be used as the value of {@code this}
313 * within {@code f}.
314 * @template THIS
315 */
316 goog.structs.TreeNode.prototype.forEachDescendant = function(f, opt_this) {
317 var children = this.getChildren();
318 for (var i = 0; i < children.length; i++) {
319 f.call(opt_this, children[i]);
320 children[i].forEachDescendant(f, opt_this);
321 }
322 };
323
324
325 /**
326 * Traverses the subtree with the possibility to skip branches. Starts with
327 * this node, and visits the descendant nodes depth-first, in preorder.
328 * @param {function(this:THIS, !goog.structs.TreeNode<KEY, VALUE>):
329 * (boolean|undefined)} f Callback function. It takes the node as argument.
330 * The children of this node will be visited if the callback returns true or
331 * undefined, and will be skipped if the callback returns false.
332 * @param {THIS=} opt_this The object to be used as the value of {@code this}
333 * within {@code f}.
334 * @template THIS
335 */
336 goog.structs.TreeNode.prototype.traverse = function(f, opt_this) {
337 if (f.call(opt_this, this) !== false) {
338 var children = this.getChildren();
339 for (var i = 0; i < children.length; i++) {
340 children[i].traverse(f, opt_this);
341 }
342 }
343 };
344
345
346 /**
347 * Sets the parent node of this node. The callers must ensure that the parent
348 * node and only that has this node among its children.
349 * @param {goog.structs.TreeNode<KEY, VALUE>} parent The parent to set. If
350 * null, the node will be detached from the tree.
351 * @protected
352 */
353 goog.structs.TreeNode.prototype.setParent = function(parent) {
354 this.parent_ = parent;
355 };
356
357
358 /**
359 * Appends a child node to this node.
360 * @param {!goog.structs.TreeNode<KEY, VALUE>} child Orphan child node.
361 */
362 goog.structs.TreeNode.prototype.addChild = function(child) {
363 this.addChildAt(child, this.children_ ? this.children_.length : 0);
364 };
365
366
367 /**
368 * Inserts a child node at the given index.
369 * @param {!goog.structs.TreeNode<KEY, VALUE>} child Orphan child node.
370 * @param {number} index The position to insert at.
371 */
372 goog.structs.TreeNode.prototype.addChildAt = function(child, index) {
373 goog.asserts.assert(!child.getParent());
374 child.setParent(this);
375 this.children_ = this.children_ || [];
376 goog.asserts.assert(index >= 0 && index <= this.children_.length);
377 goog.array.insertAt(this.children_, child, index);
378 };
379
380
381 /**
382 * Replaces a child node at the given index.
383 * @param {!goog.structs.TreeNode<KEY, VALUE>} newChild Child node to set. It
384 * must not have parent node.
385 * @param {number} index Valid index of the old child to replace.
386 * @return {!goog.structs.TreeNode<KEY, VALUE>} The original child node,
387 * detached from its parent.
388 */
389 goog.structs.TreeNode.prototype.replaceChildAt = function(newChild, index) {
390 goog.asserts.assert(
391 !newChild.getParent(), 'newChild must not have parent node');
392 var children = this.getChildren();
393 var oldChild = children[index];
394 goog.asserts.assert(oldChild, 'Invalid child or child index is given.');
395 oldChild.setParent(null);
396 children[index] = newChild;
397 newChild.setParent(this);
398 return oldChild;
399 };
400
401
402 /**
403 * Replaces the given child node.
404 * @param {!goog.structs.TreeNode<KEY, VALUE>} newChild New node to replace
405 * {@code oldChild}. It must not have parent node.
406 * @param {!goog.structs.TreeNode<KEY, VALUE>} oldChild Existing child node to
407 * be replaced.
408 * @return {!goog.structs.TreeNode<KEY, VALUE>} The replaced child node
409 * detached from its parent.
410 */
411 goog.structs.TreeNode.prototype.replaceChild = function(newChild, oldChild) {
412 return this.replaceChildAt(
413 newChild, goog.array.indexOf(this.getChildren(), oldChild));
414 };
415
416
417 /**
418 * Removes the child node at the given index.
419 * @param {number} index The position to remove from.
420 * @return {goog.structs.TreeNode<KEY, VALUE>} The removed node if any.
421 */
422 goog.structs.TreeNode.prototype.removeChildAt = function(index) {
423 var child = this.children_ && this.children_[index];
424 if (child) {
425 child.setParent(null);
426 goog.array.removeAt(this.children_, index);
427 if (this.children_.length == 0) {
428 this.children_ = null;
429 }
430 return child;
431 }
432 return null;
433 };
434
435
436 /**
437 * Removes the given child node of this node.
438 * @param {goog.structs.TreeNode<KEY, VALUE>} child The node to remove.
439 * @return {goog.structs.TreeNode<KEY, VALUE>} The removed node if any.
440 */
441 goog.structs.TreeNode.prototype.removeChild = function(child) {
442 return child &&
443 this.removeChildAt(goog.array.indexOf(this.getChildren(), child));
444 };
445
446
447 /**
448 * Removes all child nodes of this node.
449 */
450 goog.structs.TreeNode.prototype.removeChildren = function() {
451 if (this.children_) {
452 for (var i = 0; i < this.children_.length; i++) {
453 this.children_[i].setParent(null);
454 }
455 this.children_ = null;
456 }
457 };