import * as assert from 'assert' ; import { Buffer } from 'buffer' ; import { resize } from './array' ; type ForeachCallback = ( buffer : Buffer ) => void ; export default class Trie { referenceCount : number ; minCharacter : number ; count : number ; liveNodes : number ; next : Array < Trie | null > ; constructor ( ) { this . referenceCount = 0 ; this . minCharacter = 0 ; this . count = 0 ; this . liveNodes = 0 ; this . next = [ ] ; } get isRedundant ( ) : boolean { return this . referenceCount === 0 && this . liveNodes === 0 ; } add ( prefix , start , size ) { if ( size === 0 ) { this . referenceCount ++ ; return this . referenceCount === 1 ; } const currentCharacter = prefix . readUInt8 ( start ) ; if ( currentCharacter < this . minCharacter || currentCharacter >= this . minCharacter + this . count ) { if ( this . count === 0 ) { this . minCharacter = currentCharacter ; this . count = 1 ; this . next = Array ( 1 ) . fill ( null ) ; } else if ( this . count === 1 ) { const oldc = this . minCharacter ; const oldp = this . next [ 0 ] ; this . count = ( this . minCharacter < currentCharacter ? currentCharacter - this . minCharacter : this . minCharacter - currentCharacter ) + 1 ; this . next = Array ( this . count ) . fill ( null ) ; this . minCharacter = Math . min ( this . minCharacter , currentCharacter ) ; this . next [ oldc - this . minCharacter ] = oldp ; } else if ( this . minCharacter < currentCharacter ) { this . count = currentCharacter - this . minCharacter + 1 ; this . next = resize ( this . next , this . count , true ) ; } else { this . count = ( this . minCharacter + this . count ) - currentCharacter ; this . next = resize ( this . next , this . count , false ) ; this . minCharacter = currentCharacter ; } } if ( this . next [ currentCharacter - this . minCharacter ] === null ) { this . next [ currentCharacter - this . minCharacter ] = new Trie ( ) ; this . liveNodes ++ ; } return this . next [ currentCharacter - this . minCharacter ] . add ( prefix , start + 1 , size - 1 ) ; } remove ( prefix , start , size ) { if ( size === 0 ) { if ( this . referenceCount === 0 ) return false ; this . referenceCount -- ; return this . referenceCount === 0 ; } const currentCharacter = prefix . readUInt8 ( start ) ; if ( this . count == 0 || currentCharacter < this . minCharacter || currentCharacter >= this . minCharacter + this . count ) return false ; const nextNode = this . count == 1 ? this . next [ 0 ] : this . next [ currentCharacter - this . minCharacter ] ; if ( nextNode === null ) return false ; const wasRemoved = nextNode . remove ( prefix , start + 1 , size - 1 ) ; if ( nextNode . isRedundant ) { if ( this . count === 1 ) { this . next = [ ] ; this . count = 0 ; this . liveNodes -- ; assert ( this . liveNodes == 0 ) ; } else { this . next [ currentCharacter - this . minCharacter ] = null ; assert ( this . liveNodes > 1 ) ; this . liveNodes -- ; if ( currentCharacter == this . minCharacter ) { let newMin = this . minCharacter ; for ( let i = 1 ; i < this . count ; ++ i ) { if ( this . next [ i ] !== null ) { newMin = i + this . minCharacter ; break ; } } assert ( newMin != this . minCharacter ) ; assert ( newMin > this . minCharacter ) ; assert ( this . count > newMin - this . minCharacter ) ; this . count = this . count - ( newMin - this . minCharacter ) ; this . next = resize ( this . next , this . count , false ) ; this . minCharacter = newMin ; } else if ( currentCharacter == this . minCharacter + this . count - 1 ) { let newCount = this . count ; for ( let i = 1 ; i < this . count ; i ++ ) { if ( this . next [ this . count - 1 - i ] != null ) { newCount = this . count - i ; break ; } } assert ( newCount != this . count ) ; this . count = newCount ; this . next = resize ( this . next , this . count , true ) ; } } } return wasRemoved ; } public check ( data , offset , size ) { let current = this ; let start = offset ; while ( true ) { if ( current . referenceCount > 0 ) return true ; if ( size === 0 ) return false ; const character = data . readUInt8 ( start ) ; if ( character < current . minCharacter || character >= current . minCharacter + current . count ) return false ; if ( current . count === 1 ) { current = current . next [ 0 ] ; } else { current = current . next [ character - current . minCharacter ] ; if ( current === null ) return false ; } start ++ ; size -- ; } } forEach ( func ) { this . forEachHelper ( Buffer . alloc ( 0 ) , 0 , 0 , func ) ; } forEachHelper ( buffer , bufferSize , maxBufferSize , func ) { if ( this . referenceCount > 0 ) func ( buffer . slice ( 0 , bufferSize ) ) ; if ( bufferSize >= maxBufferSize ) { maxBufferSize = bufferSize + 256 ; const newBuffer = Buffer . alloc ( maxBufferSize , 0 ) ; buffer . copy ( newBuffer ) ; buffer = newBuffer ; } if ( this . count === 0 ) return ; if ( this . count === 1 ) { buffer [ bufferSize ] = this . minCharacter ; bufferSize ++ ; this . next [ 0 ] . forEachHelper ( buffer , bufferSize , maxBufferSize , func ) ; return ; } for ( let c = 0 ; c != this . count ; c ++ ) { buffer . writeUInt8 ( this . minCharacter + c , bufferSize ) ; if ( this . next [ c ] != null ) { this . next [ c ] . forEachHelper ( buffer , bufferSize + 1 , maxBufferSize , func ) ; } } } }