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 ) { if ( ! input . uri ) { return ; } let currentNode = this . root ; const fsPath = Uri . parse ( input . uri ) . fsPath ; const segments = 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 , returnEarly = false ) { let currentNode = this . root ; const segments = 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 ) { let currentNode = this . root ; let res ; const segments = 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 ) { this . _value = value ; this . _children = { } ; } public get children ( ) : INodeChildren < T > { return this . _children ; } public set children ( children ) { this . _children = children ; } public set value ( value ) { this . _value = value ; } public get value ( ) : T | undefined { return this . _value ; } } interface INodeChildren < T > { [ key ] : TrieNode < T > ; }