| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239 |
12x
12x
12x
12x
2531x
2531x
2531x
12x
12x
7273x
7273x
7273x
12x
2395x
2395x
2395x
2825x
2825x
2825x
2395x
12x
5535x
12x
280x
280x
280x
12x
12x
519x
12x
344x
2132x
2132x
747x
12x
427x
427x
427x
12x
427x
427x
766x
766x
427x
12x
12x
3239x
12x
12x
1193x
12x
446x
12x
344x
344x
344x
83x
83x
83x
261x
83x
83x
83x
12x
| /**
* Copyright 2017 Google Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import { assert } from '@firebase/util';
import { Path } from './Path';
import { forEach, contains, safeGet } from '@firebase/util';
/**
* Node in a Tree.
*/
export class TreeNode<T> {
// TODO: Consider making accessors that create children and value lazily or
// separate Internal / Leaf 'types'.
children: { [name: string]: TreeNode<T> } = {};
childCount = 0;
value: T | null = null;
}
/**
* A light-weight tree, traversable by path. Nodes can have both values and children.
* Nodes are not enumerated (by forEachChild) unless they have a value or non-empty
* children.
*/
export class Tree<T> {
/**
* @template T
* @param {string=} name_ Optional name of the node.
* @param {Tree=} parent_ Optional parent node.
* @param {TreeNode=} node_ Optional node to wrap.
*/
constructor(
private name_: string = '',
private parent_: Tree<T> | null = null,
private node_: TreeNode<T> = new TreeNode<T>()
) {}
/**
* Returns a sub-Tree for the given path.
*
* @param {!(string|Path)} pathObj Path to look up.
* @return {!Tree.<T>} Tree for path.
*/
subTree(pathObj: string | Path): Tree<T> {
// TODO: Require pathObj to be Path?
let path = pathObj instanceof Path ? pathObj : new Path(pathObj);
let child = this as any,
next;
while ((next = path.getFront()) !== null) {
const childNode = safeGet(child.node_.children, next) || new TreeNode();
child = new Tree(next, child, childNode);
path = path.popFront();
}
return child;
}
/**
* Returns the data associated with this tree node.
*
* @return {?T} The data or null if no data exists.
*/
getValue(): T | null {
return this.node_.value;
}
/**
* Sets data to this tree node.
*
* @param {!T} value Value to set.
*/
setValue(value: T) {
assert(typeof value !== 'undefined', 'Cannot set value to undefined');
this.node_.value = value;
this.updateParents_();
}
/**
* Clears the contents of the tree node (its value and all children).
*/
clear() {
this.node_.value = null;
this.node_.children = {};
this.node_.childCount = 0;
this.updateParents_();
}
/**
* @return {boolean} Whether the tree has any children.
*/
hasChildren(): boolean {
return this.node_.childCount > 0;
}
/**
* @return {boolean} Whether the tree is empty (no value or children).
*/
isEmpty(): boolean {
return this.getValue() === null && !this.hasChildren();
}
/**
* Calls action for each child of this tree node.
*
* @param {function(!Tree.<T>)} action Action to be called for each child.
*/
forEachChild(action: (tree: Tree<T>) => void) {
forEach(this.node_.children, (child: string, childTree: TreeNode<T>) => {
action(new Tree<T>(child, this, childTree));
});
}
/**
* Does a depth-first traversal of this node's descendants, calling action for each one.
*
* @param {function(!Tree.<T>)} action Action to be called for each child.
* @param {boolean=} includeSelf Whether to call action on this node as well. Defaults to
* false.
* @param {boolean=} childrenFirst Whether to call action on children before calling it on
* parent.
*/
forEachDescendant(
action: (tree: Tree<T>) => void,
includeSelf?: boolean,
childrenFirst?: boolean
) {
Iif (includeSelf && !childrenFirst) action(this);
this.forEachChild(function(child) {
child.forEachDescendant(action, /*includeSelf=*/ true, childrenFirst);
});
Iif (includeSelf && childrenFirst) action(this);
}
/**
* Calls action on each ancestor node.
*
* @param {function(!Tree.<T>)} action Action to be called on each parent; return
* true to abort.
* @param {boolean=} includeSelf Whether to call action on this node as well.
* @return {boolean} true if the action callback returned true.
*/
forEachAncestor(
action: (tree: Tree<T>) => void,
includeSelf?: boolean
): boolean {
let node = includeSelf ? this : this.parent();
while (node !== null) {
Iif (action(node)) {
return true;
}
node = node.parent();
}
return false;
}
/**
* Does a depth-first traversal of this node's descendants. When a descendant with a value
* is found, action is called on it and traversal does not continue inside the node.
* Action is *not* called on this node.
*
* @param {function(!Tree.<T>)} action Action to be called for each child.
*/
forEachImmediateDescendantWithValue(action: (tree: Tree<T>) => void) {
this.forEachChild(function(child) {
if (child.getValue() !== null) action(child);
else child.forEachImmediateDescendantWithValue(action);
});
}
/**
* @return {!Path} The path of this tree node, as a Path.
*/
path(): Path {
return new Path(
this.parent_ === null
? this.name_
: this.parent_.path() + '/' + this.name_
);
}
/**
* @return {string} The name of the tree node.
*/
name(): string {
return this.name_;
}
/**
* @return {?Tree} The parent tree node, or null if this is the root of the tree.
*/
parent(): Tree<T> | null {
return this.parent_;
}
/**
* Adds or removes this child from its parent based on whether it's empty or not.
*
* @private
*/
private updateParents_() {
if (this.parent_ !== null) this.parent_.updateChild_(this.name_, this);
}
/**
* Adds or removes the passed child to this tree node, depending on whether it's empty.
*
* @param {string} childName The name of the child to update.
* @param {!Tree.<T>} child The child to update.
* @private
*/
private updateChild_(childName: string, child: Tree<T>) {
const childEmpty = child.isEmpty();
const childExists = contains(this.node_.children, childName);
if (childEmpty && childExists) {
delete this.node_.children[childName];
this.node_.childCount--;
this.updateParents_();
} else if (!childEmpty && !childExists) {
this.node_.children[childName] = child.node_;
this.node_.childCount++;
this.updateParents_();
}
}
}
|