8000 [lookup-by-path] Add deleteSubtree (#5227) · lwsinclair/rushstack@0233664 · GitHub 8000
[go: up one dir, main page]
Skip to content

Commit 0233664

Browse files
dmichon-msftdmichon-msft
authored
[lookup-by-path] Add deleteSubtree (microsoft#5227)
Co-authored-by: David Michon <dmichon-msft@users.noreply.github.com>
1 parent fba6858 commit 0233664

File tree

4 files changed

+118
-0
lines changed

4 files changed

+118
-0
lines changed

‎common/changes/@rushstack/lookup-by-path/lookup-delete-subtree_2025-05-13-00-49.json

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
{
2+
"changes": [
3+
{
4+
"packageName": "@rushstack/lookup-by-path",
5+
"comment": "Add `deleteSubtree` method.",
6+
"type": "minor"
7+
}
8+
],
9+
"packageName": "@rushstack/lookup-by-path"
10+
}

‎common/reviews/api/lookup-by-path.api.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@ export class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TIt
5050
constructor(entries?: Iterable<[string, TItem]>, delimiter?: string);
5151
clear(): this;
5252
deleteItem(query: string, delimeter?: string): boolean;
53+
deleteSubtree(query: string, delimeter?: string): boolean;
5354
readonly delimiter: string;
5455
entries(query?: string, delimiter?: string): IterableIterator<[string, TItem]>;
5556
findChildPath(childPath: string, delimiter?: string): TItem | undefined;

‎libraries/lookup-by-path/src/LookupByPath.ts

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -342,6 +342,38 @@ export class LookupByPath<TItem extends {}> implements IReadonlyLookupByPath<TIt
342342
return false;
343343
}
344344

345+
/**
346+
* Deletes an item and all its children.
347+
* @param query - The path to the item to delete
348+
* @param delimeter - Optional override delimeter for parsing the query
349+
* @returns `true` if any nodes were deleted, `false` otherwise
350+
*/
351+
public deleteSubtree(query: string, delimeter: string = this.delimiter): boolean {
352+
const queryNode: IPathTrieNode<TItem> | undefined = this._findNodeAtPrefix(query, delimeter);
353+
if (!queryNode) {
354+
return false;
355+
}
356+
357+
const queue: IPathTrieNode<TItem>[] = [queryNode];
358+
let removed: number = 0;
359+
while (queue.length > 0) {
360+
const node: IPathTrieNode<TItem> = queue.pop()!;
361+
if (node.value !== undefined) {
362+
node.value = undefined;
363+
removed++;
364+
}
365+
if (node.children) {
366+
for (const child of node.children.values()) {
367+
queue.push(child);
368+
}
369+
node.children.clear();
370+
}
371+
}
372+
373+
this._size -= removed;
374+
return removed > 0;
375+
}
376+
345377
/**
346378
* Associates the value with the specified path.
347379
* If a value is already associated, will overwrite.

‎libraries/lookup-by-path/src/test/LookupByPath.test.ts

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -359,6 +359,81 @@ describe(LookupByPath.prototype.deleteItem.name, () => {
359359
});
360360
});
361361

362+
describe(LookupByPath.prototype.deleteSubtree.name, () => {
363+
it('returns false for an empty tree', () => {
364+
expect(new LookupByPath().deleteSubtree('foo')).toEqual(false);
365+
});
366+
367+
it('deletes the matching node in a trivial tree', () => {
368+
const tree = new LookupByPath([['foo', 1]]);
369+
expect(tree.deleteSubtree('foo')).toEqual(true);
370+
expect(tree.size).toEqual(0);
371+
expect(tree.get('foo')).toEqual(undefined);
372+
});
373+
374+
it('returns false for non-matching paths in a single-layer tree', () => {
375+
const tree: LookupByPath<number> = new LookupByPath([
376+
['foo', 1],
377+
['bar', 2],
378+
['baz', 3]
379+
]);
380+
381+
expect(tree.deleteSubtree('buzz')).toEqual(false);
382+
expect(tree.size).toEqual(3);
383+
});
384< 9E81 code class="diff-text syntax-highlighted-line addition">+
385+
it('deletes the matching node in a single-layer tree', () => {
386+
const tree: LookupByPath<number> = new LookupByPath([
387+
['foo', 1],
388+
['bar', 2],
389+
['baz', 3]
390+
]);
391+
392+
expect(tree.deleteSubtree('bar')).toEqual(true);
393+
expect(tree.size).toEqual(2);
394+
expect(tree.get('bar')).toEqual(undefined);
395+
});
396+
397+
it('deletes the matching subtree in a multi-layer tree', () => {
398+
const tree: LookupByPath<number> = new LookupByPath([
399+
['foo', 1],
400+
['foo/bar', 2],
401+
['foo/bar/baz', 3]
402+
]);
403+
404+
expect(tree.deleteSubtree('foo/bar')).toEqual(true);
405+
expect(tree.size).toEqual(1);
406+
expect(tree.get('foo/bar')).toEqual(undefined);
407+
expect(tree.get('foo/bar/baz')).toEqual(undefined); // child nodes are deleted
408+
});
409+
410+
it('returns false for non-matching paths in a multi-layer tree', () => {
411+
const tree: LookupByPath<number> = new LookupByPath([
412+
['foo', 1],
413+
['foo/bar', 2],
414+
['foo/bar/baz', 3]
415+
]);
416+
417+
expect(tree.deleteSubtree('foo/baz')).toEqual(false);
418+
expect(tree.size).toEqual(3);
419+
});
420+
421+
it('handles custom delimiters', () => {
422+
const tree: LookupByPath<number> = new LookupByPath(
423+
[
424+
['foo,bar', 1],
425+
['foo,bar,baz', 2]
426+
],
427+
','
428+
);
429+
430+
expect(tree.deleteSubtree('foo\0bar', '\0')).toEqual(true);
431+
expect(tree.size).toEqual(0);
432+
expect(tree.get('foo\0bar', '\0')).toEqual(undefined);
433+
expect(tree.get('foo\0bar\0baz', '\0')).toEqual(undefined); // child nodes are deleted
434+
});
435+
});
436+
362437
describe(LookupByPath.prototype.findChildPath.name, () => {
363438
it('returns empty for an empty tree', () => {
364439
expect(new LookupByPath().findChildPath('foo')).toEqual(undefined);

0 commit comments

Comments
 (0)
0