Skip to content

Commit 4a77765

Browse files
jriekenjrieken
committed
debt - better way to track keys in tst
1 parent 17e78c4 commit 4a77765

4 files changed

Lines changed: 83 additions & 62 deletions

File tree

‎src/vs/base/common/iterator.ts‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,13 @@
55

66
'use strict';
77

8+
export interface IIteratorResult<T> {
9+
readonly done: boolean;
10+
readonly value: T;
11+
}
12+
813
export interface IIterator<E> {
9-
next(): { readonly done: boolean, readonly value: E };
14+
next(): IIteratorResult<E>;
1015
}
1116

1217
export interface INextIterator<T> {

‎src/vs/base/common/map.ts‎

Lines changed: 46 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,8 @@
66
'use strict';
77

88
import URI from 'vs/base/common/uri';
9+
import { CharCode } from 'vs/base/common/charCode';
10+
import { IIterator } from './iterator';
911

1012
export function values<V = any>(set: Set<V>): V[];
1113
export function values<K = any, V = any>(map: Map<K, V>): V[];
@@ -35,7 +37,6 @@ export function getOrSet<K, V>(map: Map<K, V>, key: K, value: V): V {
3537
export interface IKeyIterator {
3638
reset(key: string): this;
3739
next(): this;
38-
join(parts: string[]): string;
3940

4041
hasNext(): boolean;
4142
cmp(a: string): number;
@@ -58,10 +59,6 @@ export class StringIterator implements IKeyIterator {
5859
return this;
5960
}
6061

61-
join(parts: string[]): string {
62-
return parts.join('');
63-
}
64-
6562
hasNext(): boolean {
6663
return this._pos < this._value.length - 1;
6764
}
@@ -79,9 +76,6 @@ export class StringIterator implements IKeyIterator {
7976

8077
export class PathIterator implements IKeyIterator {
8178

82-
private static readonly _fwd = '/'.charCodeAt(0);
83-
private static readonly _bwd = '\\'.charCodeAt(0);
84-
8579
private _value: string;
8680
private _from: number;
8781
private _to: number;
@@ -97,17 +91,13 @@ export class PathIterator implements IKeyIterator {
9791
return this._to < this._value.length;
9892
}
9993

100-
join(parts: string[]): string {
101-
return parts.join('/');
102-
}
103-
10494
next(): this {
10595
// this._data = key.split(/[\\/]/).filter(s => !!s);
10696
this._from = this._to;
10797
let justSeps = true;
10898
for (; this._to < this._value.length; this._to++) {
10999
const ch = this._value.charCodeAt(this._to);
110-
if (ch === PathIterator._fwd || ch === PathIterator._bwd) {
100+
if (ch === CharCode.Slash || ch === CharCode.Backslash) {
111101
if (justSeps) {
112102
this._from++;
113103
} else {
@@ -150,14 +140,15 @@ export class PathIterator implements IKeyIterator {
150140
}
151141

152142
class TernarySearchTreeNode<E> {
153-
str: string;
154-
element: E;
143+
segment: string;
144+
value: E;
145+
key: string;
155146
left: TernarySearchTreeNode<E>;
156147
mid: TernarySearchTreeNode<E>;
157148
right: TernarySearchTreeNode<E>;
158149

159150
isEmpty(): boolean {
160-
return !this.left && !this.mid && !this.right && !this.element;
151+
return !this.left && !this.mid && !this.right && !this.value;
161152
}
162153
}
163154

@@ -188,25 +179,25 @@ export class TernarySearchTree<E> {
188179

189180
if (!this._root) {
190181
this._root = new TernarySearchTreeNode<E>();
191-
this._root.str = iter.value();
182+
this._root.segment = iter.value();
192183
}
193184

194185
node = this._root;
195186
while (true) {
196-
let val = iter.cmp(node.str);
187+
let val = iter.cmp(node.segment);
197188
if (val > 0) {
198189
// left
199190
if (!node.left) {
200191
node.left = new TernarySearchTreeNode<E>();
201-
node.left.str = iter.value();
192+
node.left.segment = iter.value();
202193
}
203194
node = node.left;
204195

205196
} else if (val < 0) {
206197
// right
207198
if (!node.right) {
208199
node.right = new TernarySearchTreeNode<E>();
209-
node.right.str = iter.value();
200+
node.right.segment = iter.value();
210201
}
211202
node = node.right;
212203

@@ -215,23 +206,24 @@ export class TernarySearchTree<E> {
215206
iter.next();
216207
if (!node.mid) {
217208
node.mid = new TernarySearchTreeNode<E>();
218-
node.mid.str = iter.value();
209+
node.mid.segment = iter.value();
219210
}
220211
node = node.mid;
221212
} else {
222213
break;
223214
}
224215
}
225-
const oldElement = node.element;
226-
node.element = element;
216+
const oldElement = node.value;
217+
node.value = element;
218+
node.key = key;
227219
return oldElement;
228220
}
229221

230222
get(key: string): E {
231223
let iter = this._iter.reset(key);
232224
let node = this._root;
233225
while (node) {
234-
let val = iter.cmp(node.str);
226+
let val = iter.cmp(node.segment);
235227
if (val > 0) {
236228
// left
237229
node = node.left;
@@ -246,7 +238,7 @@ export class TernarySearchTree<E> {
246238
break;
247239
}
248240
}
249-
return node ? node.element : undefined;
241+
return node ? node.value : undefined;
250242
}
251243

252244
delete(key: string): void {
@@ -257,7 +249,7 @@ export class TernarySearchTree<E> {
257249

258250
// find and unset node
259251
while (node) {
260-
let val = iter.cmp(node.str);
252+
let val = iter.cmp(node.segment);
261253
if (val > 0) {
262254
// left
263255
stack.push([1, node]);
@@ -273,7 +265,7 @@ export class TernarySearchTree<E> {
273265
node = node.mid;
274266
} else {
275267
// remove element
276-
node.element = undefined;
268+
node.value = undefined;
277269

278270
// clean up empty nodes
279271
while (stack.length > 0 && node.isEmpty()) {
@@ -295,7 +287,7 @@ export class TernarySearchTree<E> {
295287
let node = this._root;
296288
let candidate: E;
297289
while (node) {
298-
let val = iter.cmp(node.str);
290+
let val = iter.cmp(node.segment);
299291
if (val > 0) {
300292
// left
301293
node = node.left;
@@ -305,20 +297,20 @@ export class TernarySearchTree<E> {
305297
} else if (iter.hasNext()) {
306298
// mid
307299
iter.next();
308-
candidate = node.element || candidate;
300+
candidate = node.value || candidate;
309301
node = node.mid;
310302
} else {
311303
break;
312304
}
313305
}
314-
return node && node.element || candidate;
306+
return node && node.value || candidate;
315307
}
316308

317-
findSuperstr(key: string): TernarySearchTree<E> {
309+
findSuperstr(key: string): IIterator<E> {
318310
let iter = this._iter.reset(key);
319311
let node = this._root;
320312
while (node) {
321-
let val = iter.cmp(node.str);
313+
let val = iter.cmp(node.segment);
322314
if (val > 0) {
323315
// left
324316
node = node.left;
@@ -333,37 +325,47 @@ export class TernarySearchTree<E> {
333325
// collect
334326
if (!node.mid) {
335327
return undefined;
328+
} else {
329+
return this._nodeIterator(node.mid);
336330
}
337-
let ret = new TernarySearchTree<E>(this._iter);
338-
ret._root = node.mid;
339-
return ret;
340331
}
341332
}
342333
return undefined;
343334
}
344335

345336
forEach(callback: (value: E, index: string) => any) {
346-
this._forEach(this._root, [], callback);
337+
this._forEach(this._root, callback);
347338
}
348339

349-
private _forEach(node: TernarySearchTreeNode<E>, parts: string[], callback: (value: E, index: string) => any) {
340+
private _forEach(node: TernarySearchTreeNode<E>, callback: (value: E, index: string) => any) {
350341
if (node) {
351342
// left
352-
this._forEach(node.left, parts, callback);
343+
this._forEach(node.left, callback);
353344

354345
// node
355-
parts.push(node.str);
356-
if (node.element) {
357-
callback(node.element, this._iter.join(parts));
346+
if (node.value) {
347+
// callback(node.value, this._iter.join(parts));
348+
callback(node.value, node.key);
358349
}
359350
// mid
360-
this._forEach(node.mid, parts, callback);
361-
parts.pop();
351+
this._forEach(node.mid, callback);
362352

363353
// right
364-
this._forEach(node.right, parts, callback);
354+
this._forEach(node.right, callback);
365355
}
366356
}
357+
358+
private *_nodeIterator(node: TernarySearchTreeNode<E>): any & IIterator<E> {
359+
if (node) {
360+
yield* this._nodeIterator(node.left);
361+
if (node.value) {
362+
yield node.value;
363+
}
364+
yield* this._nodeIterator(node.mid);
365+
yield* this._nodeIterator(node.right);
366+
}
367+
}
368+
367369
}
368370

369371
export class ResourceMap<T> {

‎src/vs/base/test/common/map.test.ts‎

Lines changed: 25 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
import { ResourceMap, TernarySearchTree, PathIterator, StringIterator, LinkedMap, Touch, LRUCache } from 'vs/base/common/map';
99
import * as assert from 'assert';
1010
import URI from 'vs/base/common/uri';
11+
import { IIteratorResult } from 'vs/base/common/iterator';
1112

1213
suite('Map', () => {
1314

@@ -418,17 +419,30 @@ suite('Map', () => {
418419
map.set('/user/foo/flip/flop', 3);
419420
map.set('/usr/foo', 4);
420421

421-
const elements = map.findSuperstr('/user');
422-
423-
assertTernarySearchTree(elements, ['foo/bar', 1], ['foo', 2], ['foo/flip/flop', 3]);
424-
// assert.equal(elements.length, 3);
425-
assert.equal(elements.get('foo/bar'), 1);
426-
assert.equal(elements.get('foo'), 2);
427-
assert.equal(elements.get('foo/flip/flop'), 3);
428-
429-
assertTernarySearchTree(map.findSuperstr('/usr'), ['foo', 4]);
430-
assert.equal(map.findSuperstr('/usr/foo'), undefined);
431-
assert.equal(map.get('/usr/foo'), 4);
422+
let item: IIteratorResult<number>;
423+
let iter = map.findSuperstr('/user');
424+
425+
item = iter.next();
426+
assert.equal(item.value, 2);
427+
assert.equal(item.done, false);
428+
item = iter.next();
429+
assert.equal(item.value, 1);
430+
assert.equal(item.done, false);
431+
item = iter.next();
432+
assert.equal(item.value, 3);
433+
assert.equal(item.done, false);
434+
item = iter.next();
435+
assert.equal(item.value, undefined);
436+
assert.equal(item.done, true);
437+
438+
iter = map.findSuperstr('/usr');
439+
item = iter.next();
440+
assert.equal(item.value, 4);
441+
assert.equal(item.done, false);
442+
443+
item = iter.next();
444+
assert.equal(item.value, undefined);
445+
assert.equal(item.done, true);
432446

433447
assert.equal(map.findSuperstr('/not'), undefined);
434448
assert.equal(map.findSuperstr('/us'), undefined);

‎src/vs/workbench/services/decorations/browser/decorationsService.ts‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -287,13 +287,13 @@ class DecorationProviderWrapper {
287287

288288
if (includeChildren) {
289289
// (resolved) children
290-
const childTree = this.data.findSuperstr(key);
291-
if (childTree) {
292-
childTree.forEach(value => {
293-
if (value && !isThenable<void>(value)) {
294-
callback(value, true);
290+
const iter = this.data.findSuperstr(key);
291+
if (iter) {
292+
for (let item = iter.next(); !item.done; item = iter.next()) {
293+
if (item.value && !isThenable<void>(item.value)) {
294+
callback(item.value, true);
295295
}
296-
});
296+
}
297297
}
298298
}
299299
}

0 commit comments

Comments
 (0)