import { URI } from './uri' ; import { CharCode } from './charCode' ; import { Iterator , IteratorResult , FIN } from './iterator' ; export function values < V = any > ( set ) ; export function values < K = any , V = any > ( map ) ; export function values < V > ( forEachable ) { const result = [ ] ; forEachable . forEach ( ( value ) => result . push ( value ) ) ; return result ; } export function keys < K , V > ( map ) { const result = [ ] ; map . forEach ( ( value , key ) => result . push ( key ) ) ; return result ; } export function getOrSet < K , V > ( map , key , value ) { let result = map . get ( key ) ; if ( result === undefined ) { result = value ; map . set ( key , result ) ; } return result ; } export function mapToString < K , V > ( map ) { const entries = [ ] ; map . forEach ( ( value , key ) => { entries . push ( `${ key } => ${ value }` ) ; } ) ; return `Map(${ map . size }) {${ entries . join ( ', ' ) }}` ; } export function setToString < K > ( set ) { const entries = [ ] ; set . forEach ( ( value ) => { entries . push ( value ) ; } ) ; return `Set(${ set . size }) {${ entries . join ( ', ' ) }}` ; } export function mapToSerializable ( map ) { const serializable = [ ] ; map . forEach ( ( value , key ) => { serializable . push ( [ key , value ] ) ; } ) ; return serializable ; } export function serializableToMap ( serializable ) { const items = new Map < string , string > ( ) ; for ( const [ key , value ] of serializable ) { items . set ( key , value ) ; } return items ; } export interface IKeyIterator { reset ( key ) : this ; next ( ) : this ; hasNext ( ) : boolean ; cmp ( a ) : number ; value ( ) : string ; } export class StringIterator implements IKeyIterator { private _value : string = '' ; private _pos : number = 0 ; reset ( key ) { this . _value = key ; this . _pos = 0 ; return this ; } next ( ) { this . _pos += 1 ; return this ; } hasNext ( ) { return this . _pos < this . _value . length - 1 ; } cmp ( a ) { let aCode = a . charCodeAt ( 0 ) ; let thisCode = this . _value . charCodeAt ( this . _pos ) ; return aCode - thisCode ; } value ( ) { return this . _value [ this . _pos ] ; } } export class PathIterator implements IKeyIterator { private _value ! : string ; private _from ! : number ; private _to ! : number ; 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 || ch === CharCode . Backslash ) { if ( justSeps ) { this . _from ++ ; } else { break ; } } else { justSeps = false ; } } return this ; } cmp ( a ) { let aPos = 0 ; let aLen = a . length ; let thisPos = this . _from ; while ( aPos < aLen && thisPos < this . _to ) { let cmp = a . charCodeAt ( aPos ) - this . _value . charCodeAt ( thisPos ) ; if ( cmp !== 0 ) { return cmp ; } aPos += 1 ; thisPos += 1 ; } if ( aLen === this . _to - this . _from ) { return 0 ; } else if ( aPos < aLen ) { return - 1 ; } else { return 1 ; } } value ( ) { return this . _value . substring ( this . _from , this . _to ) ; } } class TernarySearchTreeNode < E > { segment ! : string ; value : E | undefined ; key ! : string ; left : TernarySearchTreeNode < E > | undefined ; mid : TernarySearchTreeNode < E > | undefined ; right : TernarySearchTreeNode < E > | undefined ; isEmpty ( ) { return ! this . left && ! this . mid && ! this . right && ! this . value ; } } export class TernarySearchTree < E > { static forPaths < E > ( ) { return new TernarySearchTree < E > ( new PathIterator ( ) ) ; } static forStrings < E > ( ) { return new TernarySearchTree < E > ( new StringIterator ( ) ) ; } private _iter : IKeyIterator ; private _root : TernarySearchTreeNode < E > | undefined ; constructor ( segments ) { this . _iter = segments ; } clear ( ) { this . _root = undefined ; } set ( key , element ) { let iter = this . _iter . reset ( key ) ; let node ; if ( ! this . _root ) { this . _root = new TernarySearchTreeNode < E > ( ) ; this . _root . segment = iter . value ( ) ; } node = this . _root ; while ( true ) { let val = iter . cmp ( node . segment ) ; if ( val > 0 ) { if ( ! node . left ) { node . left = new TernarySearchTreeNode < E > ( ) ; node . left . segment = iter . value ( ) ; } node = node . left ; } else if ( val < 0 ) { if ( ! node . right ) { node . right = new TernarySearchTreeNode < E > ( ) ; node . right . segment = iter . value ( ) ; } node = node . right ; } else if ( iter . hasNext ( ) ) { iter . next ( ) ; if ( ! node . mid ) { node . mid = new TernarySearchTreeNode < E > ( ) ; node . mid . segment = iter . value ( ) ; } node = node . mid ; } else { break ; } } const oldElement = node . value ; node . value = element ; node . key = key ; return oldElement ; } get ( key ) { let iter = this . _iter . reset ( key ) ; let node = this . _root ; while ( node ) { let 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 ) { let iter = this . _iter . reset ( key ) ; let stack = [ ] ; let node = this . _root ; while ( node ) { let 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 ( ) ) { let [ 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 ) { let iter = this . _iter . reset ( key ) ; let node = this . _root ; let candidate = undefined ; while ( node ) { let 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 ) { let iter = this . _iter . reset ( key ) ; let node = this . _root ; while ( node ) { let 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 ; let next = ( ) : IteratorResult < E > => { if ( ! data ) { data = [ ] ; idx = 0 ; this . _forEach ( node , ( value ) => data . push ( value ) ) ; } if ( idx >= data . length ) { return FIN ; } 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 ) ; } } } export class ResourceMap < T > { protected readonly map : Map < string , T > ; protected readonly ignoreCase ? : boolean ; constructor ( ) { this . map = new Map < string , T > ( ) ; this . ignoreCase = false ; } set ( resource , value ) { this . map . set ( this . toKey ( resource ) , value ) ; } get ( resource ) { return this . map . get ( this . toKey ( resource ) ) ; } has ( resource ) { return this . map . has ( this . toKey ( resource ) ) ; } get size ( ) : number { return this . map . size ; } clear ( ) { this . map . clear ( ) ; } delete ( resource ) { return this . map . delete ( this . toKey ( resource ) ) ; } forEach ( clb ) { this . map . forEach ( clb ) ; } values ( ) { return values ( this . map ) ; } private toKey ( resource ) { let key = resource . toString ( ) ; if ( this . ignoreCase ) { key = key . toLowerCase ( ) ; } return key ; } keys ( ) { return keys ( this . map ) . map ( ( k ) => URI . parse ( k ) ) ; } clone ( ) { const resourceMap = new ResourceMap < T > ( ) ; this . map . forEach ( ( value , key ) => resourceMap . map . set ( key , value ) ) ; return resourceMap ; } } interface Item < K , V > { previous : Item < K , V > | undefined ; next : Item < K , V > | undefined ; key : K ; value : V ; } export const enum Touch { None = 0 , AsOld = 1 , AsNew = 2 } export class LinkedMap < K , V > { private _map : Map < K , Item < K , V > > ; private _head : Item < K , V > | undefined ; private _tail : Item < K , V > | undefined ; private _size : number ; constructor ( ) { this . _map = new Map < K , Item < K , V > > ( ) ; this . _head = undefined ; this . _tail = undefined ; this . _size = 0 ; } clear ( ) { this . _map . clear ( ) ; this . _head = undefined ; this . _tail = undefined ; this . _size = 0 ; } isEmpty ( ) { return ! this . _head && ! this . _tail ; } get size ( ) : number { return this . _size ; } has ( key ) { return this . _map . has ( key ) ; } get ( key , touch = Touch . None ) { const item = this . _map . get ( key ) ; if ( ! item ) { return undefined ; } if ( touch !== Touch . None ) { this . touch ( item , touch ) ; } return item . value ; } set ( key , value , touch = Touch . None ) { let item = this . _map . get ( key ) ; if ( item ) { item . value = value ; if ( touch !== Touch . None ) { this . touch ( item , touch ) ; } } else { item = { key , value , next : undefined , previous : undefined } ; switch ( touch ) { case Touch . None : this . addItemLast ( item ) ; break ; case Touch . AsOld : this . addItemFirst ( item ) ; break ; case Touch . AsNew : this . addItemLast ( item ) ; break ; default : this . addItemLast ( item ) ; break ; } this . _map . set ( key , item ) ; this . _size ++ ; } } delete ( key ) { return ! ! this . remove ( key ) ; } remove ( key ) { const item = this . _map . get ( key ) ; if ( ! item ) { return undefined ; } this . _map . delete ( key ) ; this . removeItem ( item ) ; this . _size -- ; return item . value ; } shift ( ) { if ( ! this . _head && ! this . _tail ) { return undefined ; } if ( ! this . _head || ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } const item = this . _head ; this . _map . delete ( item . key ) ; this . removeItem ( item ) ; this . _size -- ; return item . value ; } forEach ( callbackfn , thisArg ? ) { let current = this . _head ; while ( current ) { if ( thisArg ) { callbackfn . bind ( thisArg ) ( current . value , current . key , this ) ; } else { callbackfn ( current . value , current . key , this ) ; } current = current . next ; } } values ( ) { let result = [ ] ; let current = this . _head ; while ( current ) { result . push ( current . value ) ; current = current . next ; } return result ; } keys ( ) { let result = [ ] ; let current = this . _head ; while ( current ) { result . push ( current . key ) ; current = current . next ; } return result ; } protected trimOld ( newSize ) { if ( newSize >= this . size ) { return ; } if ( newSize === 0 ) { this . clear ( ) ; return ; } let current = this . _head ; let currentSize = this . size ; while ( current && currentSize > newSize ) { this . _map . delete ( current . key ) ; current = current . next ; currentSize -- ; } this . _head = current ; this . _size = currentSize ; if ( current ) { current . previous = undefined ; } } private addItemFirst ( item ) { if ( ! this . _head && ! this . _tail ) { this . _tail = item ; } else if ( ! this . _head ) { throw new Error ( 'Invalid list' ) ; } else { item . next = this . _head ; this . _head . previous = item ; } this . _head = item ; } private addItemLast ( item ) { if ( ! this . _head && ! this . _tail ) { this . _head = item ; } else if ( ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } else { item . previous = this . _tail ; this . _tail . next = item ; } this . _tail = item ; } private removeItem ( item ) { if ( item === this . _head && item === this . _tail ) { this . _head = undefined ; this . _tail = undefined ; } else if ( item === this . _head ) { if ( ! item . next ) { throw new Error ( 'Invalid list' ) ; } item . next . previous = undefined ; this . _head = item . next ; } else if ( item === this . _tail ) { if ( ! item . previous ) { throw new Error ( 'Invalid list' ) ; } item . previous . next = undefined ; this . _tail = item . previous ; } else { const next = item . next ; const previous = item . previous ; if ( ! next || ! previous ) { throw new Error ( 'Invalid list' ) ; } next . previous = previous ; previous . next = next ; } item . next = undefined ; item . previous = undefined ; } private touch ( item , touch ) { if ( ! this . _head || ! this . _tail ) { throw new Error ( 'Invalid list' ) ; } if ( touch !== Touch . AsOld && touch !== Touch . AsNew ) { return ; } if ( touch === Touch . AsOld ) { if ( item === this . _head ) { return ; } const next = item . next ; const previous = item . previous ; if ( item === this . _tail ) { previous ! . next = undefined ; this . _tail = previous ; } else { next ! . previous = previous ; previous ! . next = next ; } item . previous = undefined ; item . next = this . _head ; this . _head . previous = item ; this . _head = item ; } else if ( touch === Touch . AsNew ) { if ( item === this . _tail ) { return ; } const next = item . next ; const previous = item . previous ; if ( item === this . _head ) { next ! . previous = undefined ; this . _head = next ; } else { next ! . previous = previous ; previous ! . next = next ; } item . next = undefined ; item . previous = this . _tail ; this . _tail . next = item ; this . _tail = item ; } } toJSON ( ) { const data = [ ] ; this . forEach ( ( value , key ) => { data . push ( [ key , value ] ) ; } ) ; return data ; } fromJSON ( data ) { this . clear ( ) ; for ( const [ key , value ] of data ) { this . set ( key , value ) ; } } } export class LRUCache < K , V > extends LinkedMap < K , V > { private _limit : number ; private _ratio : number ; constructor ( limit , ratio = 1 ) { super ( ) ; this . _limit = limit ; this . _ratio = Math . min ( Math . max ( 0 , ratio ) , 1 ) ; } get limit ( ) : number { return this . _limit ; } set limit ( limit ) { this . _limit = limit ; this . checkTrim ( ) ; } get ratio ( ) : number { return this . _ratio ; } set ratio ( ratio ) { this . _ratio = Math . min ( Math . max ( 0 , ratio ) , 1 ) ; this . checkTrim ( ) ; } get ( key ) { return super . get ( key , Touch . AsNew ) ; } peek ( key ) { return super . get ( key , Touch . None ) ; } set ( key , value ) { super . set ( key , value , Touch . AsNew ) ; this . checkTrim ( ) ; } private checkTrim ( ) { if ( this . size > this . _limit ) { this . trimOld ( Math . round ( this . _limit * this . _ratio ) ) ; } } }