/********************************************************************************
 * Copyright (C) 2020 TypeFox and others.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License v. 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the Eclipse
 * Public License v. 2.0 are satisfied: GNU General Public License, version 2
 * with the GNU Classpath Exception which is available at
 * https://www.gnu.org/software/classpath/license.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
 ********************************************************************************/ import URI from './uri' ; import { CharCode } from './char-code' ; import { compareSubstringIgnoreCase , compare , compareSubstring } from './strings' ; export interface IKeyIterator < K > { reset ( key ) : this ; next ( ) : this ; hasNext ( ) : boolean ; cmp ( a ) : number ; value ( ) : string ; } export class PathIterator implements IKeyIterator < string > { private _value ! : string ; private _from ! : number ; private _to ! : number ; constructor ( private readonly _splitOnBackslash = true , private readonly _caseSensitive = true ) { } reset ( key ) { this . _value = key . replace ( /\\$|\/$/ , '' ) ; this . _from = 0 ; this . _to = 0 ; return this . next ( ) ; } hasNext ( ) { return this . _to < this . _value . length ; } next ( ) { this . _from = this . _to ; let justSeps = true ; for ( ; this . _to < this . _value . length ; this . _to ++ ) { const ch = this . _value . charCodeAt ( this . _to ) ; if ( ch === CharCode . Slash || this . _splitOnBackslash && ch === CharCode . Backslash ) { if ( justSeps ) { this . _from ++ ; } else { break ; } } else { justSeps = false ; } } return this ; } cmp ( a ) { return this . _caseSensitive ? compareSubstring ( a , this . _value , 0 , a . length , this . _from , this . _to ) : compareSubstringIgnoreCase ( a , this . _value , 0 , a . length , this . _from , this . _to ) ; } value ( ) { return this . _value . substring ( this . _from , this . _to ) ; } } const enum UriIteratorState { Scheme = 1 , Authority = 2 , Path = 3 , Query = 4 , Fragment = 5 } export class UriIterator implements IKeyIterator < URI > { private _pathIterator ! : PathIterator ; private _value ! : URI ; private _states : UriIteratorState [ ] = [ ] ; private _stateIdx : number = 0 ; constructor ( protected readonly caseSensitive ) { } reset ( key ) { this . _value = key ; this . _states = [ ] ; if ( this . _value . scheme ) { this . _states . push ( UriIteratorState . Scheme ) ; } if ( this . _value . authority ) { this . _states . push ( UriIteratorState . Authority ) ; } if ( this . _value . path ) { this . _pathIterator = new PathIterator ( false , this . caseSensitive ) ; this . _pathIterator . reset ( key . path . toString ( ) ) ; if ( this . _pathIterator . value ( ) ) { this . _states . push ( UriIteratorState . Path ) ; } } if ( this . _value . query ) { this . _states . push ( UriIteratorState . Query ) ; } if ( this . _value . fragment ) { this . _states . push ( UriIteratorState . Fragment ) ; } this . _stateIdx = 0 ; return this ; } next ( ) { if ( this . _states [ this . _stateIdx ] === UriIteratorState . Path && this . _pathIterator . hasNext ( ) ) { this . _pathIterator . next ( ) ; } else { this . _stateIdx += 1 ; } return this ; } hasNext ( ) { return ( this . _states [ this . _stateIdx ] === UriIteratorState . Path && this . _pathIterator . hasNext ( ) ) || this . _stateIdx < this . _states . length - 1 ; } cmp ( a ) { if ( this . _states [ this . _stateIdx ] === UriIteratorState . Scheme ) { return compareSubstringIgnoreCase ( a , this . _value . scheme ) ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Authority ) { return compareSubstringIgnoreCase ( a , this . _value . authority ) ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Path ) { return this . _pathIterator . cmp ( a ) ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Query ) { return compare ( a , this . _value . query ) ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Fragment ) { return compare ( a , this . _value . fragment ) ; } throw new Error ( ) ; } value ( ) { if ( this . _states [ this . _stateIdx ] === UriIteratorState . Scheme ) { return this . _value . scheme ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Authority ) { return this . _value . authority ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Path ) { return this . _pathIterator . value ( ) ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Query ) { return this . _value . query ; } else if ( this . _states [ this . _stateIdx ] === UriIteratorState . Fragment ) { return this . _value . fragment ; } throw new Error ( ) ; } } class TernarySearchTreeNode < K , V > { segment ! : string ; value : V | undefined ; key ! : K ; left : TernarySearchTreeNode < K , V > | undefined ; mid : TernarySearchTreeNode < K , V > | undefined ; right : TernarySearchTreeNode < K , V > | undefined ; isEmpty ( ) { return ! this . left && ! this . mid && ! this . right && ! this . value ; } } export class TernarySearchTree < K , V > { static forUris < E > ( caseSensitive ) { return new TernarySearchTree < URI , E > ( new UriIterator ( caseSensitive ) ) ; } static forPaths < E > ( ) { return new TernarySearchTree < string , E > ( new PathIterator ( ) ) ; } private _iter : IKeyIterator < K > ; private _root : TernarySearchTreeNode < K , V > | undefined ; constructor ( segments ) { this . _iter = segments ; } clear ( ) { this . _root = undefined ; } set ( key , element ) { const iter = this . _iter . reset ( key ) ; let node ; if ( ! this . _root ) { this . _root = new TernarySearchTreeNode < K , V > ( ) ; this . _root . segment = iter . value ( ) ; } node = this . _root ; while ( true ) { const val = iter . cmp ( node . segment ) ; if ( val > 0 ) { if ( ! node . left ) { node . left = new TernarySearchTreeNode < K , V > ( ) ; node . left . segment = iter . value ( ) ; } node = node . left ; } else if ( val < 0 ) { if ( ! node . right ) { node . right = new TernarySearchTreeNode < K , V > ( ) ; node . right . segment = iter . value ( ) ; } node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; if ( ! node . mid ) { node . mid = new TernarySearchTreeNode < K , V > ( ) ; node . mid . segment = iter . value ( ) ; } node = node . mid ; } else { break ; } } const oldElement = node . value ; node . value = element ; node . key = key ; return oldElement ; } get ( key ) { const iter = this . _iter . reset ( key ) ; let node = this . _root ; while ( node ) { const val = iter . cmp ( node . segment ) ; if ( val > 0 ) { node = node . left ; } else if ( val < 0 ) { node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; node = node . mid ; } else { break ; } } return node ? node . value : undefined ; } delete ( key ) { const iter = this . _iter . reset ( key ) ; const stack = [ ] ; let node = this . _root ; while ( node ) { const val = iter . cmp ( node . segment ) ; if ( val > 0 ) { stack . push ( [ 1 , node ] ) ; node = node . left ; } else if ( val < 0 ) { stack . push ( [ - 1 , node ] ) ; node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; stack . push ( [ 0 , node ] ) ; node = node . mid ; } else { node . value = undefined ; while ( stack . length > 0 && node . isEmpty ( ) ) { const [ dir , parent ] = stack . pop ( ) ! ; switch ( dir ) { case 1 : parent . left = undefined ; break ; case 0 : parent . mid = undefined ; break ; case - 1 : parent . right = undefined ; break ; } node = parent ; } break ; } } } findSubstr ( key ) { const iter = this . _iter . reset ( key ) ; let node = this . _root ; let candidate = undefined ; while ( node ) { const val = iter . cmp ( node . segment ) ; if ( val > 0 ) { node = node . left ; } else if ( val < 0 ) { node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; candidate = node . value || candidate ; node = node . mid ; } else { break ; } } return node && node . value || candidate ; } findSuperstr ( key ) { const iter = this . _iter . reset ( key ) ; let node = this . _root ; while ( node ) { const val = iter . cmp ( node . segment ) ; if ( val > 0 ) { node = node . left ; } else if ( val < 0 ) { node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; node = node . mid ; } else { if ( ! node . mid ) { return undefined ; } else { return this . _nodeIterator ( node . mid ) ; } } } return undefined ; } private _nodeIterator ( node ) { let res ; let idx ; let data ; const next = ( ) : IteratorResult < V > => { if ( ! data ) { data = [ ] ; idx = 0 ; this . _forEach ( node , value => data . push ( value ) ) ; } if ( idx >= data . length ) { return { done : true , value : undefined } ; } if ( ! res ) { res = { done : false , value : data [ idx ++ ] } ; } else { res . value = data [ idx ++ ] ; } return res ; } ; return { next } ; } forEach ( callback ) { this . _forEach ( this . _root , callback ) ; } private _forEach ( node , callback ) { if ( node ) { this . _forEach ( node . left , callback ) ; if ( node . value ) { callback ( node . value , node . key ) ; } this . _forEach ( node . mid , callback ) ; this . _forEach ( node . right , callback ) ; } } }