forked from microsoft/vscode-java-dependency
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTrie.ts
More file actions
117 lines (94 loc) · 2.91 KB
/
Copy pathTrie.ts
File metadata and controls
117 lines (94 loc) · 2.91 KB
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
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT license.
import * as path from "path";
import { Uri } from "vscode";
export class Trie<T extends IUriData> {
private _root: TrieNode<T | undefined>;
constructor() {
this._root = new TrieNode(undefined);
}
public insert(input: T): void {
if (!input.uri) {
return;
}
let currentNode: TrieNode<T | undefined> = this.root;
const fsPath: string = Uri.parse(input.uri).fsPath;
const segments: string[] = fsPath.split(path.sep);
for (const segment of segments) {
if (!segment) {
continue;
}
if (!currentNode.children[segment]) {
currentNode.children[segment] = new TrieNode(undefined);
}
currentNode = currentNode.children[segment];
}
currentNode.value = input;
}
public find(fsPath: string, returnEarly: boolean = false): TrieNode<T | undefined> | undefined {
let currentNode = this.root;
const segments: string[] = fsPath.split(path.sep);
for (const segment of segments) {
if (!segment) {
continue;
}
if (returnEarly && currentNode.value) {
return currentNode;
}
if (currentNode.children[segment]) {
currentNode = currentNode.children[segment];
} else {
return undefined;
}
}
return currentNode;
}
public findFirstAncestorNodeWithData(fsPath: string): TrieNode<T | undefined> | undefined {
let currentNode: TrieNode<T | undefined> = this.root;
let res: TrieNode<T | undefined> | undefined;
const segments: string[] = fsPath.split(path.sep);
for (const segment of segments) {
if (!segment) {
continue;
}
if (currentNode.children[segment]) {
currentNode = currentNode.children[segment];
} else {
break;
}
if (currentNode.value) {
res = currentNode;
}
}
return res;
}
public get root(): TrieNode<T | undefined> {
return this._root;
}
}
export interface IUriData {
uri?: string;
}
export class TrieNode<T> {
private _value?: T;
private _children: INodeChildren<T>;
constructor(value: T) {
this._value = value;
this._children = {};
}
public get children(): INodeChildren<T> {
return this._children;
}
public set children(children: INodeChildren<T>) {
this._children = children;
}
public set value(value: T | undefined) {
this._value = value;
}
public get value(): T | undefined {
return this._value;
}
}
interface INodeChildren<T> {
[key: string]: TrieNode<T>;
}