| 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
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398 |
13x
13x
13x
13x
13x
887x
13x
887x
13x
13x
13x
22x
22x
53x
22x
4490x
9867x
13x
2661x
13x
7367x
743x
6624x
286x
6338x
6338x
6338x
1856x
1856x
996x
996x
860x
4482x
13x
5511x
13x
3855x
769x
3086x
3086x
3086x
1080x
2006x
13x
1703x
982x
721x
721x
721x
721x
721x
13x
303x
122x
114x
8x
181x
181x
181x
181x
181x
181x
147x
34x
181x
64x
117x
13x
5560x
3683x
1877x
1877x
1877x
1629x
248x
13x
2806x
1031x
1775x
1775x
1775x
1775x
1775x
545x
1230x
1775x
13x
157x
13x
178x
178x
21x
178x
13x
470x
13x
1035x
1035x
154x
881x
208x
673x
673x
673x
565x
108x
13x
410x
13x
665x
162x
503x
18x
503x
503x
503x
255x
248x
13x
42x
13x
79x
37x
79x
63x
13x
380x
12x
9x
13x
| /**
* 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 { SortedMap } from './SortedMap';
import { Path } from './Path';
import { stringCompare } from './util';
import { forEach } from '@firebase/util';
let emptyChildrenSingleton: SortedMap<string, ImmutableTree<null>>;
/**
* Singleton empty children collection.
*
* @const
* @type {!SortedMap.<string, !ImmutableTree.<?>>}
*/
const EmptyChildren = (): SortedMap<string, ImmutableTree<null>> => {
if (!emptyChildrenSingleton) {
emptyChildrenSingleton = new SortedMap<string, ImmutableTree<null>>(
stringCompare
);
}
return emptyChildrenSingleton;
};
/**
* A tree with immutable elements.
*/
export class ImmutableTree<T> {
static Empty = new ImmutableTree<any>(null);
/**
* @template T
* @param {!Object.<string, !T>} obj
* @return {!ImmutableTree.<!T>}
*/
static fromObject<T>(obj: { [k: string]: T }): ImmutableTree<T> {
let tree: ImmutableTree<T> = ImmutableTree.Empty;
forEach(obj, (childPath: string, childSnap: T) => {
tree = tree.set(new Path(childPath), childSnap);
});
return tree;
}
/**
* @template T
* @param {?T} value
* @param {SortedMap.<string, !ImmutableTree.<T>>=} children
*/
constructor(
public readonly value: T | null,
public readonly children: SortedMap<
string,
ImmutableTree<T>
> = EmptyChildren()
) {}
/**
* True if the value is empty and there are no children
* @return {boolean}
*/
isEmpty(): boolean {
return this.value === null && this.children.isEmpty();
}
/**
* Given a path and predicate, return the first node and the path to that node
* where the predicate returns true.
*
* TODO Do a perf test -- If we're creating a bunch of {path: value:} objects
* on the way back out, it may be better to pass down a pathSoFar obj.
*
* @param {!Path} relativePath The remainder of the path
* @param {function(T):boolean} predicate The predicate to satisfy to return a
* node
* @return {?{path:!Path, value:!T}}
*/
findRootMostMatchingPathAndValue(
relativePath: Path,
predicate: (a: T) => boolean
): { path: Path; value: T } | null {
if (this.value != null && predicate(this.value)) {
return { path: Path.Empty, value: this.value };
} else {
if (relativePath.isEmpty()) {
return null;
} else {
const front = relativePath.getFront();
const child = this.children.get(front);
if (child !== null) {
const childExistingPathAndValue = child.findRootMostMatchingPathAndValue(
relativePath.popFront(),
predicate
);
if (childExistingPathAndValue != null) {
const fullPath = new Path(front).child(
childExistingPathAndValue.path
);
return { path: fullPath, value: childExistingPathAndValue.value };
} else {
return null;
}
} else {
return null;
}
}
}
}
/**
* Find, if it exists, the shortest subpath of the given path that points a defined
* value in the tree
* @param {!Path} relativePath
* @return {?{path: !Path, value: !T}}
*/
findRootMostValueAndPath(
relativePath: Path
): { path: Path; value: T } | null {
return this.findRootMostMatchingPathAndValue(relativePath, () => true);
}
/**
* @param {!Path} relativePath
* @return {!ImmutableTree.<T>} The subtree at the given path
*/
subtree(relativePath: Path): ImmutableTree<T> {
if (relativePath.isEmpty()) {
return this;
} else {
const front = relativePath.getFront();
const childTree = this.children.get(front);
if (childTree !== null) {
return childTree.subtree(relativePath.popFront());
} else {
return ImmutableTree.Empty;
}
}
}
/**
* Sets a value at the specified path.
*
* @param {!Path} relativePath Path to set value at.
* @param {?T} toSet Value to set.
* @return {!ImmutableTree.<T>} Resulting tree.
*/
set(relativePath: Path, toSet: T | null): ImmutableTree<T> {
if (relativePath.isEmpty()) {
return new ImmutableTree(toSet, this.children);
} else {
const front = relativePath.getFront();
const child = this.children.get(front) || ImmutableTree.Empty;
const newChild = child.set(relativePath.popFront(), toSet);
const newChildren = this.children.insert(front, newChild);
return new ImmutableTree(this.value, newChildren);
}
}
/**
* Removes the value at the specified path.
*
* @param {!Path} relativePath Path to value to remove.
* @return {!ImmutableTree.<T>} Resulting tree.
*/
remove(relativePath: Path): ImmutableTree<T> {
if (relativePath.isEmpty()) {
if (this.children.isEmpty()) {
return ImmutableTree.Empty;
} else {
return new ImmutableTree(null, this.children);
}
} else {
const front = relativePath.getFront();
const child = this.children.get(front);
Eif (child) {
const newChild = child.remove(relativePath.popFront());
let newChildren;
if (newChild.isEmpty()) {
newChildren = this.children.remove(front);
} else {
newChildren = this.children.insert(front, newChild);
}
if (this.value === null && newChildren.isEmpty()) {
return ImmutableTree.Empty;
} else {
return new ImmutableTree(this.value, newChildren);
}
} else {
return this;
}
}
}
/**
* Gets a value from the tree.
*
* @param {!Path} relativePath Path to get value for.
* @return {?T} Value at path, or null.
*/
get(relativePath: Path): T | null {
if (relativePath.isEmpty()) {
return this.value;
} else {
const front = relativePath.getFront();
const child = this.children.get(front);
if (child) {
return child.get(relativePath.popFront());
} else {
return null;
}
}
}
/**
* Replace the subtree at the specified path with the given new tree.
*
* @param {!Path} relativePath Path to replace subtree for.
* @param {!ImmutableTree} newTree New tree.
* @return {!ImmutableTree} Resulting tree.
*/
setTree(relativePath: Path, newTree: ImmutableTree<T>): ImmutableTree<T> {
if (relativePath.isEmpty()) {
return newTree;
} else {
const front = relativePath.getFront();
const child = this.children.get(front) || ImmutableTree.Empty;
const newChild = child.setTree(relativePath.popFront(), newTree);
let newChildren;
if (newChild.isEmpty()) {
newChildren = this.children.remove(front);
} else {
newChildren = this.children.insert(front, newChild);
}
return new ImmutableTree(this.value, newChildren);
}
}
/**
* Performs a depth first fold on this tree. Transforms a tree into a single
* value, given a function that operates on the path to a node, an optional
* current value, and a map of child names to folded subtrees
* @template V
* @param {function(Path, ?T, Object.<string, V>):V} fn
* @return {V}
*/
fold<V>(fn: (path: Path, value: T, children: { [k: string]: V }) => V): V {
return this.fold_(Path.Empty, fn);
}
/**
* Recursive helper for public-facing fold() method
* @template V
* @param {!Path} pathSoFar
* @param {function(Path, ?T, Object.<string, V>):V} fn
* @return {V}
* @private
*/
private fold_<V>(
pathSoFar: Path,
fn: (path: Path, value: T | null, children: { [k: string]: V }) => V
): V {
const accum: { [k: string]: V } = {};
this.children.inorderTraversal(function(
childKey: string,
childTree: ImmutableTree<T>
) {
accum[childKey] = childTree.fold_(pathSoFar.child(childKey), fn);
});
return fn(pathSoFar, this.value, accum);
}
/**
* Find the first matching value on the given path. Return the result of applying f to it.
* @template V
* @param {!Path} path
* @param {!function(!Path, !T):?V} f
* @return {?V}
*/
findOnPath<V>(path: Path, f: (path: Path, value: T) => V | null): V | null {
return this.findOnPath_(path, Path.Empty, f);
}
private findOnPath_<V>(
pathToFollow: Path,
pathSoFar: Path,
f: (path: Path, value: T) => V | null
): V | null {
const result = this.value ? f(pathSoFar, this.value) : false;
if (result) {
return result;
} else {
if (pathToFollow.isEmpty()) {
return null;
} else {
const front = pathToFollow.getFront()!;
const nextChild = this.children.get(front);
if (nextChild) {
return nextChild.findOnPath_(
pathToFollow.popFront(),
pathSoFar.child(front),
f
);
} else {
return null;
}
}
}
}
/**
*
* @param {!Path} path
* @param {!function(!Path, !T)} f
* @returns {!ImmutableTree.<T>}
*/
foreachOnPath(
path: Path,
f: (path: Path, value: T) => void
): ImmutableTree<T> {
return this.foreachOnPath_(path, Path.Empty, f);
}
private foreachOnPath_(
pathToFollow: Path,
currentRelativePath: Path,
f: (path: Path, value: T) => void
): ImmutableTree<T> {
if (pathToFollow.isEmpty()) {
return this;
} else {
if (this.value) {
f(currentRelativePath, this.value);
}
const front = pathToFollow.getFront();
const nextChild = this.children.get(front);
if (nextChild) {
return nextChild.foreachOnPath_(
pathToFollow.popFront(),
currentRelativePath.child(front),
f
);
} else {
return ImmutableTree.Empty;
}
}
}
/**
* Calls the given function for each node in the tree that has a value.
*
* @param {function(!Path, !T)} f A function to be called with
* the path from the root of the tree to a node, and the value at that node.
* Called in depth-first order.
*/
foreach(f: (path: Path, value: T) => void) {
this.foreach_(Path.Empty, f);
}
private foreach_(
currentRelativePath: Path,
f: (path: Path, value: T) => void
) {
this.children.inorderTraversal(function(childName, childTree) {
childTree.foreach_(currentRelativePath.child(childName), f);
});
if (this.value) {
f(currentRelativePath, this.value);
}
}
/**
*
* @param {function(string, !T)} f
*/
foreachChild(f: (name: string, value: T) => void) {
this.children.inorderTraversal(
(childName: string, childTree: ImmutableTree<T>) => {
if (childTree.value) {
f(childName, childTree.value);
}
}
);
}
}
|