OLD | NEW |
| (Empty) |
1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 cr.define('bmm', function() { | |
6 /** | |
7 * An inorder (document order) iterator for iterating over a bookmark tree. | |
8 * | |
9 * <pre> | |
10 * var it = new TreeIterator(node); | |
11 * while (it.moveNext()) { | |
12 * print(it.current.title); | |
13 * } | |
14 * </pre> | |
15 * | |
16 * @param {!BookmarkTreeNode} node The node to start at. | |
17 * @constructor | |
18 */ | |
19 function TreeIterator(node) { | |
20 this.current_ = node; | |
21 this.parentStack_ = []; | |
22 this.indexStack_ = []; | |
23 } | |
24 | |
25 /** | |
26 * Helper function for {@code TreeIterator.prototype.next}. This returns the | |
27 * next node in document order. | |
28 * @param {BookmarkTreeNode} node The current node. | |
29 * @param {!Array.<!BookmarkTreeNode>} parents A stack of parents. | |
30 * @param {!Array.<number>} index A stack of indexes. | |
31 * @return {BookmarkTreeNode} The next node or null if no more nodes can be | |
32 * found. | |
33 */ | |
34 function getNext(node, parents, index) { | |
35 var i, p; | |
36 | |
37 if (!node) | |
38 return null; | |
39 | |
40 // If the node has children return first child. | |
41 if (node.children && node.children.length) { | |
42 parents.push(node); | |
43 index.push(0); | |
44 return node.children[0]; | |
45 } | |
46 | |
47 if (!parents.length) | |
48 return null; | |
49 | |
50 // Walk up the parent stack until we find a node that has a next sibling. | |
51 while (node) { | |
52 p = parents[parents.length - 1]; | |
53 if (!p) | |
54 return null; | |
55 i = index[index.length - 1]; | |
56 if (i + 1 < p.children.length) | |
57 break; | |
58 node = parents.pop(); | |
59 index.pop(); | |
60 } | |
61 | |
62 // Walked out of subtree. | |
63 if (!parents.length || !node) | |
64 return null; | |
65 | |
66 // Return next child. | |
67 i = ++index[index.length - 1]; | |
68 p = parents[parents.length - 1]; | |
69 return p.children[i]; | |
70 } | |
71 | |
72 TreeIterator.prototype = { | |
73 /** | |
74 * Whether the next move will be the first move. | |
75 * @type {boolean} | |
76 * @private | |
77 */ | |
78 first_: true, | |
79 | |
80 /** | |
81 * Moves the iterator to the next item. | |
82 * @return {boolean} Whether we succeeded moving to the next item. This | |
83 * returns false when we have moved off the end of the iterator. | |
84 */ | |
85 moveNext: function() { | |
86 // The first call to this should move us to the first node. | |
87 if (this.first_) { | |
88 this.first_ = false; | |
89 return true; | |
90 } | |
91 this.current_ = getNext(this.current_, this.parentStack_, | |
92 this.indexStack_); | |
93 | |
94 return !!this.current_; | |
95 }, | |
96 | |
97 /** | |
98 * The current item. This throws an exception if trying to access after | |
99 * {@code moveNext} has returned false or before {@code moveNext} has been | |
100 * called. | |
101 * @type {!BookmarkTreeNode} | |
102 */ | |
103 get current() { | |
104 if (!this.current_ || this.first_) | |
105 throw Error('No such element'); | |
106 return this.current_; | |
107 } | |
108 }; | |
109 | |
110 return { | |
111 TreeIterator: TreeIterator | |
112 }; | |
113 }); | |
OLD | NEW |