import { ISortedMap , ISortedMapF } from './interfaces' ; export { ISetSource , ISetSink , ISet , ISetF , ISortedSetSource , ISortedSet , ISortedSetF , IMapSource , IMapSink , IMap , IMapF , ISortedMapSource , ISortedMap , ISortedMapF } from './interfaces' ; export type EditRangeResult < V , R = number > = { value ? : V ; break ? : R ; delete ? : boolean ; } ; type index = number ; /**
 * Types that BTree supports by default
 */ export type DefaultComparable = number | string | Date | boolean | null | undefined | ( number | string ) [ ] | { valueOf : ( ) => number | string | Date | boolean | null | undefined | ( number | string ) [ ] ; } ; /**
 * Compares DefaultComparables to form a strict partial ordering.
 *
 * Handles +/-0 and NaN like Map: NaN is equal to NaN, and -0 is equal to +0.
 *
 * Arrays are compared using '<' and '>', which may cause unexpected equality:
 * for example [1] will be considered equal to ['1'].
 *
 * Two objects with equal valueOf compare the same, but compare unequal to
 * primitives that have the same value.
 */ export function defaultComparator ( a , b ) { if ( Number . isFinite ( a as any ) && Number . isFinite ( b as any ) ) { return a as number - ( b as number ) ; } let ta = typeof a ; let tb = typeof b ; if ( ta !== tb ) { return ta < tb ? - 1 : 1 ; } if ( ta === 'object' ) { if ( a === null ) return b === null ? 0 : - 1 ; else if ( b === null ) return 1 ; a = a ! . valueOf ( ) as DefaultComparable ; b = b ! . valueOf ( ) as DefaultComparable ; ta = typeof a ; tb = typeof b ; if ( ta !== tb ) { return ta < tb ? - 1 : 1 ; } } if ( a ! < b ! ) return - 1 ; if ( a ! > b ! ) return 1 ; if ( a === b ) return 0 ; if ( Number . isNaN ( a as any ) ) return Number . isNaN ( b as any ) ? 0 : - 1 ; else if ( Number . isNaN ( b as any ) ) return 1 ; return Array . isArray ( a ) ? 0 : Number . NaN ; } ; /**
 * Compares items using the < and > operators. This function is probably slightly
 * faster than the defaultComparator for Dates and strings, but has not been benchmarked.
 * Unlike defaultComparator, this comparator doesn't support mixed types correctly,
 * i.e. use it with `BTree<string>` or `BTree<number>` but not `BTree<string|number>`.
 *
 * NaN is not supported.
 *
 * Note: null is treated like 0 when compared with numbers or Date, but in general
 *   null is not ordered with respect to strings (neither greater nor less), and
 *   undefined is not ordered with other types.
 */ export function simpleComparator ( a , b ) ; export function simpleComparator ( a , b ) ; export function simpleComparator ( a , b ) ; export function simpleComparator ( a , b ) ; export function simpleComparator ( a , b ) { return a > b ? 1 : a < b ? - 1 : 0 ; } ; example description author David Piepgrass
  export default class BTree < K = any , V = any > implements ISortedMapF < K , V > , ISortedMap < K , V > { private _root : BNode < K , V > = EmptyLeaf as BNode < K , V > ; _size : number = 0 ; _maxNodeSize : number ; returns _compare : ( a : K , b : K ) => number ; param compare param entries param maxNodeSize public constructor ( entries ? , compare ? , maxNodeSize ? ) { this . _maxNodeSize = maxNodeSize ! >= 4 ? Math . min ( maxNodeSize ! , 256 ) : 32 ; this . _compare = compare || defaultComparator as any as ( a : K , b : K ) => number ; if ( entries ) this . setPairs ( entries ) ; } /** Gets the number of key-value pairs in the tree. */ get size ( ) { return this . _size ; } /** Gets the number of key-value pairs in the tree. */ get length ( ) { return this . _size ; } /** Returns true iff the tree contains no key-value pairs. */ get isEmpty ( ) { return this . _size === 0 ; } /** Releases the tree so that its size is 0. */ clear ( ) { this . _root = EmptyLeaf as BNode < K , V > ; this . _size = 0 ; } forEach ( callback , thisArg ? ) ; param thisArg returns forEach < R = number > ( callback , thisArg ? ) { if ( thisArg !== undefined ) callback = callback . bind ( thisArg ) ; return this . forEachPair ( ( k , v ) => callback ( v , k , this ) ) ; } param onFound param initialCounter returns forEachPair < R = number > ( callback , initialCounter ? ) { var low = this . minKey ( ) , high = this . maxKey ( ) ; return this . forRange ( low ! , high ! , true , callback , initialCounter ) ; } param defaultValue returns description get ( key , defaultValue ? ) { return this . _root . get ( key , defaultValue , this ) ; } param key param value param overwrite returns description set ( key , value , overwrite ? ) { if ( this . _root . isShared ) this . _root = this . _root . clone ( ) ; var result = this . _root . set ( key , value , overwrite , this ) ; if ( result === true || result === false ) return result ; this . _root = new BNodeInternal < K , V > ( [ this . _root , result ] ) ; return true ; } param key description has ( key ) { return this . forRange ( key , key , true , undefined ) !== 0 ; } param key returns description delete ( key ) { return this . editRange ( key , key , true , DeleteRange ) !== 0 ; } /** Returns a copy of the tree with the specified key set (the value is undefined). */ with ( key ) ; /** Returns a copy of the tree with the specified key-value pair set. */ with < V2 > ( key , value , overwrite ? ) ; with < V2 > ( key , value ? , overwrite ? ) { let nu = this . clone ( ) as BTree < K , V | V2 | undefined > ; return nu . set ( key , value , overwrite ) || overwrite ? nu : this ; } /** Returns a copy of the tree with the specified key-value pairs set. */ withPairs < V2 > ( pairs , overwrite ) { let nu = this . clone ( ) as BTree < K , V | V2 > ; return nu . setPairs ( pairs , overwrite ) !== 0 || overwrite ? nu : this ; } param keys param returnThisIfUnchanged withKeys ( keys , returnThisIfUnchanged ? ) { let nu = this . clone ( ) as BTree < K , V | undefined > , changed = false ; for ( var i = 0 ; i < keys . length ; i ++ ) changed = nu . set ( keys [ i ] , undefined , false ) || changed ; return returnThisIfUnchanged && ! changed ? this : nu ; } param returnThisIfUnchanged without ( key , returnThisIfUnchanged ? ) { return this . withoutRange ( key , key , true , returnThisIfUnchanged ) ; } param returnThisIfUnchanged withoutKeys ( keys , returnThisIfUnchanged ? ) { let nu = this . clone ( ) ; return nu . deleteKeys ( keys ) || ! returnThisIfUnchanged ? nu : this ; } /** Returns a copy of the tree with the specified range of keys removed. */ withoutRange ( low , high , includeHigh , returnThisIfUnchanged ? ) { let nu = this . clone ( ) ; if ( nu . deleteRange ( low , high , includeHigh ) === 0 && returnThisIfUnchanged ) return this ; return nu ; } /** Returns a copy of the tree with pairs removed whenever the callback
     *  function returns false. `where()` is a synonym for this method. */ filter ( callback , returnThisIfUnchanged ? ) { var nu = this . greedyClone ( ) ; var del ; nu . editAll ( ( k , v , i ) => { if ( ! callback ( k , v , i ) ) return del = Delete ; } ) ; if ( ! del && returnThisIfUnchanged ) return this ; return nu ; } /** Returns a copy of the tree with all values altered by a callback function. */ mapValues < R > ( callback ) { var tmp = { } as { value : R ; } ; var nu = this . greedyClone ( ) ; nu . editAll ( ( k , v , i ) => { return tmp . value = callback ( v , k , i ) , tmp as any ; } ) ; return nu as any as BTree < K , R > ; } /** Performs a reduce operation like the `reduce` method of `Array`.
     *  It is used to combine all pairs into a single value, or perform
     *  conversions. `reduce` is best understood by example. For example,
     *  `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys
     *  together. It means "start with P=1, and for each pair multiply
     *  it by the key in pair[0]". Another example would be converting
     *  the tree to a Map (in this example, note that M.set returns M):
     *
     *  var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map())
     *
     *  **Note**: the same array is sent to the callback on every iteration.
     */ reduce < R > ( callback , initialValue ) ; reduce < R > ( callback ) ; reduce < R > ( callback , initialValue ? ) { let i = 0 , p = initialValue ; var it = this . entries ( this . minKey ( ) , ReusedArray ) , next ; while ( ! ( next = it . next ( ) ) . done ) p = callback ( p , next . value , i ++ , this ) ; return p ; } param lowestKey param reusedArray entries ( lowestKey ? , reusedArray ? ) { var info = this . findPath ( lowestKey ) ; if ( info === undefined ) return iterator < [ K , V ] > ( ) ; var { nodequeue , nodeindex , leaf } = info ; var state = reusedArray !== undefined ? 1 : 0 ; var i = ( lowestKey === undefined ? - 1 : leaf . indexOf ( lowestKey , 0 , this . _compare ) - 1 ) ; return iterator < [ K , V ] > ( ( ) => { jump : for ( ; ; ) { switch ( state ) { case 0 : if ( ++ i < leaf . keys . length ) return { done : false , value : [ leaf . keys [ i ] , leaf . values [ i ] ] } ; state = 2 ; continue ; case 1 : if ( ++ i < leaf . keys . length ) { reusedArray ! [ 0 ] = leaf . keys [ i ] , reusedArray ! [ 1 ] = leaf . values [ i ] ; return { done : false , value : reusedArray as [ K , V ] } ; } state = 2 ; case 2 : for ( var level = - 1 ; ; ) { if ( ++ level >= nodequeue . length ) { state = 3 ; continue jump ; } if ( ++ nodeindex [ level ] < nodequeue [ level ] . length ) break ; } for ( ; level > 0 ; level -- ) { nodequeue [ level - 1 ] = ( nodequeue [ level ] [ nodeindex [ level ] ] as BNodeInternal < K , V > ) . children ; nodeindex [ level - 1 ] = 0 ; } leaf = nodequeue [ 0 ] [ nodeindex [ 0 ] ] ; i = - 1 ; state = reusedArray !== undefined ? 1 : 0 ; continue ; case 3 : return { done : true , value : undefined } ; } } } ) ; } param highestKey param reusedArray param skipHighest entriesReversed ( highestKey ? , reusedArray ? , skipHighest ? ) { if ( highestKey === undefined ) { highestKey = this . maxKey ( ) ; skipHighest = undefined ; if ( highestKey === undefined ) return iterator < [ K , V ] > ( ) ; } var { nodequeue , nodeindex , leaf } = this . findPath ( highestKey ) || this . findPath ( this . maxKey ( ) ) ! ; check ( ! nodequeue [ 0 ] || leaf === nodequeue [ 0 ] [ nodeindex [ 0 ] ] , "wat!" ) ; var i = leaf . indexOf ( highestKey , 0 , this . _compare ) ; if ( ! skipHighest && i < leaf . keys . length && this . _compare ( leaf . keys [ i ] , highestKey ) <= 0 ) i ++ ; var state = reusedArray !== undefined ? 1 : 0 ; return iterator < [ K , V ] > ( ( ) => { jump : for ( ; ; ) { switch ( state ) { case 0 : if ( -- i >= 0 ) return { done : false , value : [ leaf . keys [ i ] , leaf . values [ i ] ] } ; state = 2 ; continue ; case 1 : if ( -- i >= 0 ) { reusedArray ! [ 0 ] = leaf . keys [ i ] , reusedArray ! [ 1 ] = leaf . values [ i ] ; return { done : false , value : reusedArray as [ K , V ] } ; } state = 2 ; case 2 : for ( var level = - 1 ; ; ) { if ( ++ level >= nodequeue . length ) { state = 3 ; continue jump ; } if ( -- nodeindex [ level ] >= 0 ) break ; } for ( ; level > 0 ; level -- ) { nodequeue [ level - 1 ] = ( nodequeue [ level ] [ nodeindex [ level ] ] as BNodeInternal < K , V > ) . children ; nodeindex [ level - 1 ] = nodequeue [ level - 1 ] . length - 1 ; } leaf = nodequeue [ 0 ] [ nodeindex [ 0 ] ] ; i = leaf . keys . length ; state = reusedArray !== undefined ? 1 : 0 ; continue ; case 3 : return { done : true , value : undefined } ; } } } ) ; } private findPath ( key ? ) { var nextnode = this . _root ; var nodequeue , nodeindex ; if ( nextnode . isLeaf ) { nodequeue = EmptyArray , nodeindex = EmptyArray ; } else { nodequeue = [ ] , nodeindex = [ ] ; for ( var d = 0 ; ! nextnode . isLeaf ; d ++ ) { nodequeue [ d ] = ( nextnode as BNodeInternal < K , V > ) . children ; nodeindex [ d ] = key === undefined ? 0 : nextnode . indexOf ( key , 0 , this . _compare ) ; if ( nodeindex [ d ] >= nodequeue [ d ] . length ) return ; nextnode = nodequeue [ d ] [ nodeindex [ d ] ] ; } nodequeue . reverse ( ) ; nodeindex . reverse ( ) ; } return { nodequeue , nodeindex , leaf : nextnode } ; } param other param onlyThis param onlyOther param different diffAgainst < R > ( other , onlyThis ? , onlyOther ? , different ? ) { if ( other . _compare !== this . _compare ) { throw new Error ( "Tree comparators are not the same." ) ; } if ( this . isEmpty || other . isEmpty ) { if ( this . isEmpty && other . isEmpty ) return undefined ; if ( this . isEmpty ) return onlyOther === undefined ? undefined : BTree . stepToEnd ( BTree . makeDiffCursor ( other ) , onlyOther ) ; return onlyThis === undefined ? undefined : BTree . stepToEnd ( BTree . makeDiffCursor ( this ) , onlyThis ) ; } const { _compare } = this ; const thisCursor = BTree . makeDiffCursor ( this ) ; const otherCursor = BTree . makeDiffCursor ( other ) ; let thisSuccess = true , otherSuccess = true , prevCursorOrder = BTree . compare ( thisCursor , otherCursor , _compare ) ; while ( thisSuccess && otherSuccess ) { const cursorOrder = BTree . compare ( thisCursor , otherCursor , _compare ) ; const { leaf : thisLeaf , internalSpine : thisInternalSpine , levelIndices : thisLevelIndices } = thisCursor ; const { leaf : otherLeaf , internalSpine : otherInternalSpine , levelIndices : otherLevelIndices } = otherCursor ; if ( thisLeaf || otherLeaf ) { if ( prevCursorOrder !== 0 ) { if ( cursorOrder === 0 ) { if ( thisLeaf && otherLeaf && different ) { const valThis = thisLeaf . values [ thisLevelIndices [ thisLevelIndices . length - 1 ] ] ; const valOther = otherLeaf . values [ otherLevelIndices [ otherLevelIndices . length - 1 ] ] ; if ( ! Object . is ( valThis , valOther ) ) { const result = different ( thisCursor . currentKey , valThis , valOther ) ; if ( result && result . break ) return result . break ; } } } else if ( cursorOrder > 0 ) { if ( otherLeaf && onlyOther ) { const otherVal = otherLeaf . values [ otherLevelIndices [ otherLevelIndices . length - 1 ] ] ; const result = onlyOther ( otherCursor . currentKey , otherVal ) ; if ( result && result . break ) return result . break ; } } else if ( onlyThis ) { if ( thisLeaf && prevCursorOrder !== 0 ) { const valThis = thisLeaf . values [ thisLevelIndices [ thisLevelIndices . length - 1 ] ] ; const result = onlyThis ( thisCursor . currentKey , valThis ) ; if ( result && result . break ) return result . break ; } } } } else if ( ! thisLeaf && ! otherLeaf && cursorOrder === 0 ) { const lastThis = thisInternalSpine . length - 1 ; const lastOther = otherInternalSpine . length - 1 ; const nodeThis = thisInternalSpine [ lastThis ] [ thisLevelIndices [ lastThis ] ] ; const nodeOther = otherInternalSpine [ lastOther ] [ otherLevelIndices [ lastOther ] ] ; if ( nodeOther === nodeThis ) { prevCursorOrder = 0 ; thisSuccess = BTree . step ( thisCursor , true ) ; otherSuccess = BTree . step ( otherCursor , true ) ; continue ; } } prevCursorOrder = cursorOrder ; if ( cursorOrder < 0 ) { thisSuccess = BTree . step ( thisCursor ) ; } else { otherSuccess = BTree . step ( otherCursor ) ; } } if ( thisSuccess && onlyThis ) return BTree . finishCursorWalk ( thisCursor , otherCursor , _compare , onlyThis ) ; if ( otherSuccess && onlyOther ) return BTree . finishCursorWalk ( otherCursor , thisCursor , _compare , onlyOther ) ; } private static finishCursorWalk < K , V , R > ( cursor , cursorFinished , compareKeys , callback ) { const compared = BTree . compare ( cursor , cursorFinished , compareKeys ) ; if ( compared === 0 ) { if ( ! BTree . step ( cursor ) ) return undefined ; } else if ( compared < 0 ) { check ( false , "cursor walk terminated early" ) ; } return BTree . stepToEnd ( cursor , callback ) ; } private static stepToEnd < K , V , R > ( cursor , callback ) { let canStep = true ; while ( canStep ) { const { leaf , levelIndices , currentKey } = cursor ; if ( leaf ) { const value = leaf . values [ levelIndices [ levelIndices . length - 1 ] ] ; const result = callback ( currentKey , value ) ; if ( result && result . break ) return result . break ; } canStep = BTree . step ( cursor ) ; } return undefined ; } private static makeDiffCursor < K , V > ( tree ) { const { _root , height } = tree ; return { height : height , internalSpine : [ [ _root ] ] , levelIndices : [ 0 ] , leaf : undefined , currentKey : _root . maxKey ( ) } ; } param cursor param stepToNode returns private static step < K , V > ( cursor , stepToNode ? ) { const { internalSpine , levelIndices , leaf } = cursor ; if ( stepToNode === true || leaf ) { const levelsLength = levelIndices . length ; if ( stepToNode === true || levelIndices [ levelsLength - 1 ] === 0 ) { const spineLength = internalSpine . length ; if ( spineLength === 0 ) return false ; const nodeLevelIndex = spineLength - 1 ; let levelIndexWalkBack = nodeLevelIndex ; while ( levelIndexWalkBack >= 0 ) { if ( levelIndices [ levelIndexWalkBack ] > 0 ) { if ( levelIndexWalkBack < levelsLength - 1 ) { cursor . leaf = undefined ; levelIndices . pop ( ) ; } if ( levelIndexWalkBack < nodeLevelIndex ) cursor . internalSpine = internalSpine . slice ( 0 , levelIndexWalkBack + 1 ) ; cursor . currentKey = internalSpine [ levelIndexWalkBack ] [ -- levelIndices [ levelIndexWalkBack ] ] . maxKey ( ) ; return true ; } levelIndexWalkBack -- ; } return false ; } else { const valueIndex = -- levelIndices [ levelsLength - 1 ] ; cursor . currentKey = ( leaf as unknown as BNode < K , V > ) . keys [ valueIndex ] ; return true ; } } else { const nextLevel = internalSpine . length ; const currentLevel = nextLevel - 1 ; const node = internalSpine [ currentLevel ] [ levelIndices [ currentLevel ] ] ; if ( node . isLeaf ) { cursor . leaf = node ; const valueIndex = levelIndices [ nextLevel ] = node . values . length - 1 ; cursor . currentKey = node . keys [ valueIndex ] ; } else { const children = ( node as BNodeInternal < K , V > ) . children ; internalSpine [ nextLevel ] = children ; const childIndex = children . length - 1 ; levelIndices [ nextLevel ] = childIndex ; cursor . currentKey = children [ childIndex ] . maxKey ( ) ; } return true ; } } /**
     * Compares the two cursors. Returns a value indicating which cursor is ahead in a walk.
     * Note that cursors are advanced in reverse sorting order.
     */ private static compare < K , V > ( cursorA , cursorB , compareKeys ) { const { height : heightA , currentKey : currentKeyA , levelIndices : levelIndicesA } = cursorA ; const { height : heightB , currentKey : currentKeyB , levelIndices : levelIndicesB } = cursorB ; const keyComparison = compareKeys ( currentKeyB , currentKeyA ) ; if ( keyComparison !== 0 ) { return keyComparison ; } const heightMin = heightA < heightB ? heightA : heightB ; const depthANormalized = levelIndicesA . length - ( heightA - heightMin ) ; const depthBNormalized = levelIndicesB . length - ( heightB - heightMin ) ; return depthANormalized - depthBNormalized ; } param firstKey keys ( firstKey ? ) { var it = this . entries ( firstKey , ReusedArray ) ; return iterator < K > ( ( ) => { var n = it . next ( ) ; if ( n . value ) n . value = n . value [ 0 ] ; return n ; } ) ; } param firstKey values ( firstKey ? ) { var it = this . entries ( firstKey , ReusedArray ) ; return iterator < V > ( ( ) => { var n = it . next ( ) ; if ( n . value ) n . value = n . value [ 1 ] ; return n ; } ) ; } /** Returns the maximum number of children/values before nodes will split. */ get maxNodeSize ( ) { return this . _maxNodeSize ; } /** Gets the lowest key in the tree. Complexity: O(log size) */ minKey ( ) { return this . _root . minKey ( ) ; } /** Gets the highest key in the tree. Complexity: O(1) */ maxKey ( ) { return this . _root . maxKey ( ) ; } /** Quickly clones the tree by marking the root node as shared.
     *  Both copies remain editable. When you modify either copy, any
     *  nodes that are shared (or potentially shared) between the two
     *  copies are cloned so that the changes do not affect other copies.
     *  This is known as copy-on-write behavior, or "lazy copying". */ clone ( ) { this . _root . isShared = true ; var result = new BTree < K , V > ( undefined , this . _compare , this . _maxNodeSize ) ; result . _root = this . _root ; result . _size = this . _size ; return result ; } param force greedyClone ( force ? ) { var result = new BTree < K , V > ( undefined , this . _compare , this . _maxNodeSize ) ; result . _root = this . _root . greedyClone ( force ) ; result . _size = this . _size ; return result ; } /** Gets an array filled with the contents of the tree, sorted by key */ toArray ( maxLength = 0x7FFFFFFF ) { let min = this . minKey ( ) , max = this . maxKey ( ) ; if ( min !== undefined ) return this . getRange ( min , max ! , true , maxLength ) ; return [ ] ; } /** Gets an array of all keys, sorted */ keysArray ( ) { var results = [ ] ; this . _root . forRange ( this . minKey ( ) ! , this . maxKey ( ) ! , true , false , this , 0 , ( k , v ) => { results . push ( k ) ; } ) ; return results ; } /** Gets an array of all values, sorted by key */ valuesArray ( ) { var results = [ ] ; this . _root . forRange ( this . minKey ( ) ! , this . maxKey ( ) ! , true , false , this , 0 , ( k , v ) => { results . push ( v ) ; } ) ; return results ; } /** Gets a string representing the tree's data based on toArray(). */ toString ( ) { return this . toArray ( ) . toString ( ) ; } returns setIfNotPresent ( key , value ) { return this . set ( key , value , false ) ; } param key param reusedArray nextHigherPair ( key , reusedArray ? ) { reusedArray = reusedArray || ( [ ] as unknown as [ K , V ] ) ; if ( key === undefined ) { return this . _root . minPair ( reusedArray ) ; } return this . _root . getPairOrNextHigher ( key , this . _compare , false , reusedArray ) ; } /** Returns the next key larger than the specified key, or undefined if there is none.
     *  Also, nextHigherKey(undefined) returns the lowest key.
     */ nextHigherKey ( key ) { var p = this . nextHigherPair ( key , ReusedArray as [ K , V ] ) ; return p && p [ 0 ] ; } param key param reusedArray nextLowerPair ( key , reusedArray ? ) { reusedArray = reusedArray || ( [ ] as unknown as [ K , V ] ) ; if ( key === undefined ) { return this . _root . maxPair ( reusedArray ) ; } return this . _root . getPairOrNextLower ( key , this . _compare , false , reusedArray ) ; } /** Returns the next key smaller than the specified key, or undefined if there is none.
     *  Also, nextLowerKey(undefined) returns the highest key.
     */ nextLowerKey ( key ) { var p = this . nextLowerPair ( key , ReusedArray as [ K , V ] ) ; return p && p [ 0 ] ; } param key param reusedArray getPairOrNextLower ( key , reusedArray ? ) { return this . _root . getPairOrNextLower ( key , this . _compare , true , reusedArray || ( [ ] as unknown as [ K , V ] ) ) ; } param key param reusedArray getPairOrNextHigher ( key , reusedArray ? ) { return this . _root . getPairOrNextHigher ( key , this . _compare , true , reusedArray || ( [ ] as unknown as [ K , V ] ) ) ; } returns changeIfPresent ( key , value ) { return this . editRange ( key , key , true , ( k , v ) => ( { value } ) ) !== 0 ; } param low param high param includeHigh param maxLength description getRange ( low , high , includeHigh ? , maxLength = 0x3FFFFFF ) { var results = [ ] ; this . _root . forRange ( low , high , includeHigh , false , this , 0 , ( k , v ) => { results . push ( [ k , v ] ) ; return results . length > maxLength ? Break : undefined ; } ) ; return results ; } param pairs param overwrite returns description setPairs ( pairs , overwrite ? ) { var added = 0 ; for ( var i = 0 ; i < pairs . length ; i ++ ) if ( this . set ( pairs [ i ] [ 0 ] , pairs [ i ] [ 1 ] , overwrite ) ) added ++ ; return added ; } forRange ( low , high , includeHigh , onFound ? , initialCounter ? ) ; param low param high param includeHigh param onFound param initialCounter returns description forRange < R = number > ( low , high , includeHigh , onFound ? , initialCounter ? ) { var r = this . _root . forRange ( low , high , includeHigh , false , this , initialCounter || 0 , onFound ) ; return typeof r === "number" ? r : r . break ! ; } param low param high param includeHigh param onFound returns description editRange < R = V > ( low , high , includeHigh , onFound , initialCounter ? ) { var root = this . _root ; if ( root . isShared ) this . _root = root = root . clone ( ) ; try { var r = root . forRange ( low , high , includeHigh , true , this , initialCounter || 0 , onFound ) ; return typeof r === "number" ? r : r . break ! ; } finally { while ( root . keys . length <= 1 && ! root . isLeaf ) this . _root = root = root . keys . length === 0 ? EmptyLeaf : ( root as any as BNodeInternal < K , V > ) . children [ 0 ] ; } } /** Same as `editRange` except that the callback is called for all pairs. */ editAll < R = V > ( onFound , initialCounter ? ) { return this . editRange ( this . minKey ( ) ! , this . maxKey ( ) ! , true , onFound , initialCounter ) ; } param low param high param includeHigh returns description deleteRange ( low , high , includeHigh ) { return this . editRange ( low , high , includeHigh , DeleteRange ) ; } /** Deletes a series of keys from the collection. */ deleteKeys ( keys ) { for ( var i = 0 , r = 0 ; i < keys . length ; i ++ ) if ( this . delete ( keys [ i ] ) ) r ++ ; return r ; } /** Gets the height of the tree: the number of internal nodes between the
     *  BTree object and its leaf nodes (zero if there are no internal nodes). */ get height ( ) : number { let node = this . _root ; let height = - 1 ; while ( node ) { height ++ ; node = node . isLeaf ? undefined : ( node as unknown as BNodeInternal < K , V > ) . children [ 0 ] ; } return height ; } /** Makes the object read-only to ensure it is not accidentally modified.
     *  Freezing does not have to be permanent; unfreeze() reverses the effect.
     *  This is accomplished by replacing mutator functions with a function
     *  that throws an Error. Compared to using a property (e.g. this.isFrozen)
     *  this implementation gives better performance in non-frozen BTrees.
     */ freeze ( ) { var t = this as any ; t . clear = t . set = t . editRange = function ( ) { throw new Error ( "Attempted to modify a frozen BTree" ) ; } ; } /** Ensures mutations are allowed, reversing the effect of freeze(). */ unfreeze ( ) { delete this . clear ; delete this . set ; delete this . editRange ; } /** Returns true if the tree appears to be frozen. */ get isFrozen ( ) { return this . hasOwnProperty ( 'editRange' ) ; } /** Scans the tree for signs of serious bugs (e.g. this.size doesn't match
     *  number of elements, internal nodes not caching max element properly...)
     *  Computational complexity: O(number of nodes), i.e. O(size). This method
     *  skips the most expensive test - whether all keys are sorted - but it
     *  does check that maxKey() of the children of internal nodes are sorted. */ checkValid ( ) { var size = this . _root . checkValid ( 0 , this , 0 ) ; check ( size === this . size , "size mismatch: counted " , size , "but stored" , this . size ) ; } } declare const Symbol ; if ( Symbol && Symbol . iterator ) ( BTree as any ) . prototype [ Symbol . iterator ] = BTree . prototype . entries ; ( BTree as any ) . prototype . where = BTree . prototype . filter ; ( BTree as any ) . prototype . setRange = BTree . prototype . setPairs ; ( BTree as any ) . prototype . add = BTree . prototype . set ; function iterator < T > ( next = ( ( ) => ( { done : true , value : undefined } ) ) ) { var result = { next } ; if ( Symbol && Symbol . iterator ) result [ Symbol . iterator ] = function ( ) { return this ; } ; return result ; } /** Leaf node / base class. **************************************************/ class BNode < K , V > { keys : K [ ] ; values : V [ ] ; isShared : true | undefined ; get isLeaf ( ) { return ( this as any ) . children === undefined ; } constructor ( keys = [ ] , values ? ) { this . keys = keys ; this . values = values || undefVals as any [ ] ; this . isShared = undefined ; } maxKey ( ) { return this . keys [ this . keys . length - 1 ] ; } indexOf ( key , failXor , cmp ) { const keys = this . keys ; var lo = 0 , hi = keys . length , mid = hi >> 1 ; while ( lo < hi ) { var c = cmp ( keys [ mid ] , key ) ; if ( c < 0 ) lo = mid + 1 ; else if ( c > 0 ) hi = mid ; else if ( c === 0 ) return mid ; else { if ( key === key ) return keys . length ; else throw new Error ( "BTree: NaN was used as a key" ) ; } mid = ( lo + hi ) >> 1 ; } return mid ^ failXor ; } minKey ( ) { return this . keys [ 0 ] ; } minPair ( reusedArray ) { if ( this . keys . length === 0 ) return undefined ; reusedArray [ 0 ] = this . keys [ 0 ] ; reusedArray [ 1 ] = this . values [ 0 ] ; return reusedArray ; } maxPair ( reusedArray ) { if ( this . keys . length === 0 ) return undefined ; const lastIndex = this . keys . length - 1 ; reusedArray [ 0 ] = this . keys [ lastIndex ] ; reusedArray [ 1 ] = this . values [ lastIndex ] ; return reusedArray ; } clone ( ) { var v = this . values ; return new BNode < K , V > ( this . keys . slice ( 0 ) , v === undefVals ? v : v . slice ( 0 ) ) ; } greedyClone ( force ? ) { return this . isShared && ! force ? this : this . clone ( ) ; } get ( key , defaultValue , tree ) { var i = this . indexOf ( key , - 1 , tree . _compare ) ; return i < 0 ? defaultValue : this . values [ i ] ; } getPairOrNextLower ( key , compare , inclusive , reusedArray ) { var i = this . indexOf ( key , - 1 , compare ) ; const indexOrLower = i < 0 ? ~ i - 1 : ( inclusive ? i : i - 1 ) ; if ( indexOrLower >= 0 ) { reusedArray [ 0 ] = this . keys [ indexOrLower ] ; reusedArray [ 1 ] = this . values [ indexOrLower ] ; return reusedArray ; } return undefined ; } getPairOrNextHigher ( key , compare , inclusive , reusedArray ) { var i = this . indexOf ( key , - 1 , compare ) ; const indexOrLower = i < 0 ? ~ i : ( inclusive ? i : i + 1 ) ; const keys = this . keys ; if ( indexOrLower < keys . length ) { reusedArray [ 0 ] = keys [ indexOrLower ] ; reusedArray [ 1 ] = this . values [ indexOrLower ] ; return reusedArray ; } return undefined ; } checkValid ( depth , tree , baseIndex ) { var kL = this . keys . length , vL = this . values . length ; check ( this . values === undefVals ? kL <= vL : kL === vL , "keys/values length mismatch: depth" , depth , "with lengths" , kL , vL , "and baseIndex" , baseIndex ) ; check ( depth == 0 || kL > 0 , "empty leaf at depth" , depth , "and baseIndex" , baseIndex ) ; return kL ; } set ( key , value , overwrite , tree ) { var i = this . indexOf ( key , - 1 , tree . _compare ) ; if ( i < 0 ) { i = ~ i ; tree . _size ++ ; if ( this . keys . length < tree . _maxNodeSize ) { return this . insertInLeaf ( i , key , value , tree ) ; } else { var newRightSibling = this . splitOffRightSide ( ) , target = this ; if ( i > this . keys . length ) { i -= this . keys . length ; target = newRightSibling ; } target . insertInLeaf ( i , key , value , tree ) ; return newRightSibling ; } } else { if ( overwrite !== false ) { if ( value !== undefined ) this . reifyValues ( ) ; this . keys [ i ] = key ; this . values [ i ] = value ; } return false ; } } reifyValues ( ) { if ( this . values === undefVals ) return this . values = this . values . slice ( 0 , this . keys . length ) ; return this . values ; } insertInLeaf ( i , key , value , tree ) { this . keys . splice ( i , 0 , key ) ; if ( this . values === undefVals ) { while ( undefVals . length < tree . _maxNodeSize ) undefVals . push ( undefined ) ; if ( value === undefined ) { return true ; } else { this . values = undefVals . slice ( 0 , this . keys . length - 1 ) ; } } this . values . splice ( i , 0 , value ) ; return true ; } takeFromRight ( rhs ) { var v = this . values ; if ( rhs . values === undefVals ) { if ( v !== undefVals ) v . push ( undefined as any ) ; } else { v = this . reifyValues ( ) ; v . push ( rhs . values . shift ( ) ! ) ; } this . keys . push ( rhs . keys . shift ( ) ! ) ; } takeFromLeft ( lhs ) { var v = this . values ; if ( lhs . values === undefVals ) { if ( v !== undefVals ) v . unshift ( undefined as any ) ; } else { v = this . reifyValues ( ) ; v . unshift ( lhs . values . pop ( ) ! ) ; } this . keys . unshift ( lhs . keys . pop ( ) ! ) ; } splitOffRightSide ( ) { var half = this . keys . length >> 1 , keys = this . keys . splice ( half ) ; var values = this . values === undefVals ? undefVals : this . values . splice ( half ) ; return new BNode < K , V > ( keys , values ) ; } forRange < R > ( low , high , includeHigh , editMode , tree , count , onFound ? ) { var cmp = tree . _compare ; var iLow , iHigh ; if ( high === low ) { if ( ! includeHigh ) return count ; iHigh = ( iLow = this . indexOf ( low , - 1 , cmp ) ) + 1 ; if ( iLow < 0 ) return count ; } else { iLow = this . indexOf ( low , 0 , cmp ) ; iHigh = this . indexOf ( high , - 1 , cmp ) ; if ( iHigh < 0 ) iHigh = ~ iHigh ; else if ( includeHigh === true ) iHigh ++ ; } var keys = this . keys , values = this . values ; if ( onFound !== undefined ) { for ( var i = iLow ; i < iHigh ; i ++ ) { var key = keys [ i ] ; var result = onFound ( key , values [ i ] , count ++ ) ; if ( result !== undefined ) { if ( editMode === true ) { if ( key !== keys [ i ] || this . isShared === true ) throw new Error ( "BTree illegally changed or cloned in editRange" ) ; if ( result . delete ) { this . keys . splice ( i , 1 ) ; if ( this . values !== undefVals ) this . values . splice ( i , 1 ) ; tree . _size -- ; i -- ; iHigh -- ; } else if ( result . hasOwnProperty ( 'value' ) ) { values ! [ i ] = result . value ! ; } } if ( result . break !== undefined ) return result ; } } } else count += iHigh - iLow ; return count ; } /** Adds entire contents of right-hand sibling (rhs is left unchanged) */ mergeSibling ( rhs , _ ) { this . keys . push . apply ( this . keys , rhs . keys ) ; if ( this . values === undefVals ) { if ( rhs . values === undefVals ) return ; this . values = this . values . slice ( 0 , this . keys . length ) ; } this . values . push . apply ( this . values , rhs . reifyValues ( ) ) ; } } /** Internal node (non-leaf node) ********************************************/ class BNodeInternal < K , V > extends BNode < K , V > { children : BNode < K , V > [ ] ; constructor ( children , keys ? ) { if ( ! keys ) { keys = [ ] ; for ( var i = 0 ; i < children . length ; i ++ ) keys [ i ] = children [ i ] . maxKey ( ) ; } super ( keys ) ; this . children = children ; } clone ( ) { var children = this . children . slice ( 0 ) ; for ( var i = 0 ; i < children . length ; i ++ ) children [ i ] . isShared = true ; return new BNodeInternal < K , V > ( children , this . keys . slice ( 0 ) ) ; } greedyClone ( force ? ) { if ( this . isShared && ! force ) return this ; var nu = new BNodeInternal < K , V > ( this . children . slice ( 0 ) , this . keys . slice ( 0 ) ) ; for ( var i = 0 ; i < nu . children . length ; i ++ ) nu . children [ i ] = nu . children [ i ] . greedyClone ( ) ; return nu ; } minKey ( ) { return this . children [ 0 ] . minKey ( ) ; } minPair ( reusedArray ) { return this . children [ 0 ] . minPair ( reusedArray ) ; } maxPair ( reusedArray ) { return this . children [ this . children . length - 1 ] . maxPair ( reusedArray ) ; } get ( key , defaultValue , tree ) { var i = this . indexOf ( key , 0 , tree . _compare ) , children = this . children ; return i < children . length ? children [ i ] . get ( key , defaultValue , tree ) : undefined ; } getPairOrNextLower ( key , compare , inclusive , reusedArray ) { var i = this . indexOf ( key , 0 , compare ) , children = this . children ; if ( i >= children . length ) return this . maxPair ( reusedArray ) ; const result = children [ i ] . getPairOrNextLower ( key , compare , inclusive , reusedArray ) ; if ( result === undefined && i > 0 ) { return children [ i - 1 ] . maxPair ( reusedArray ) ; } return result ; } getPairOrNextHigher ( key , compare , inclusive , reusedArray ) { var i = this . indexOf ( key , 0 , compare ) , children = this . children , length = children . length ; if ( i >= length ) return undefined ; const result = children [ i ] . getPairOrNextHigher ( key , compare , inclusive , reusedArray ) ; if ( result === undefined && i < length - 1 ) { return children [ i + 1 ] . minPair ( reusedArray ) ; } return result ; } checkValid ( depth , tree , baseIndex ) { let kL = this . keys . length , cL = this . children . length ; check ( kL === cL , "keys/children length mismatch: depth" , depth , "lengths" , kL , cL , "baseIndex" , baseIndex ) ; check ( kL > 1 || depth > 0 , "internal node has length" , kL , "at depth" , depth , "baseIndex" , baseIndex ) ; let size = 0 , c = this . children , k = this . keys , childSize = 0 ; for ( var i = 0 ; i < cL ; i ++ ) { size += c [ i ] . checkValid ( depth + 1 , tree , baseIndex + size ) ; childSize += c [ i ] . keys . length ; check ( size >= childSize , "wtf" , baseIndex ) ; check ( i === 0 || c [ i - 1 ] . constructor === c [ i ] . constructor , "type mismatch, baseIndex:" , baseIndex ) ; if ( c [ i ] . maxKey ( ) != k [ i ] ) check ( false , "keys[" , i , "] =" , k [ i ] , "is wrong, should be " , c [ i ] . maxKey ( ) , "at depth" , depth , "baseIndex" , baseIndex ) ; if ( ! ( i === 0 || tree . _compare ( k [ i - 1 ] , k [ i ] ) < 0 ) ) check ( false , "sort violation at depth" , depth , "index" , i , "keys" , k [ i - 1 ] , k [ i ] ) ; } let toofew = childSize === 0 ; if ( toofew || childSize > tree . maxNodeSize * cL ) check ( false , toofew ? "too few" : "too many" , "children (" , childSize , size , ") at depth" , depth , "maxNodeSize:" , tree . maxNodeSize , "children.length:" , cL , "baseIndex:" , baseIndex ) ; return size ; } set ( key , value , overwrite , tree ) { var c = this . children , max = tree . _maxNodeSize , cmp = tree . _compare ; var i = Math . min ( this . indexOf ( key , 0 , cmp ) , c . length - 1 ) , child = c [ i ] ; if ( child . isShared ) c [ i ] = child = child . clone ( ) ; if ( child . keys . length >= max ) { var other ; if ( i > 0 && ( other = c [ i - 1 ] ) . keys . length < max && cmp ( child . keys [ 0 ] , key ) < 0 ) { if ( other . isShared ) c [ i - 1 ] = other = other . clone ( ) ; other . takeFromRight ( child ) ; this . keys [ i - 1 ] = other . maxKey ( ) ; } else if ( ( other = c [ i + 1 ] ) !== undefined && other . keys . length < max && cmp ( child . maxKey ( ) , key ) < 0 ) { if ( other . isShared ) c [ i + 1 ] = other = other . clone ( ) ; other . takeFromLeft ( child ) ; this . keys [ i ] = c [ i ] . maxKey ( ) ; } } var result = child . set ( key , value , overwrite , tree ) ; if ( result === false ) return false ; this . keys [ i ] = child . maxKey ( ) ; if ( result === true ) return true ; if ( this . keys . length < max ) { this . insert ( i + 1 , result ) ; return true ; } else { var newRightSibling = this . splitOffRightSide ( ) , target = this ; if ( cmp ( result . maxKey ( ) , this . maxKey ( ) ) > 0 ) { target = newRightSibling ; i -= this . keys . length ; } target . insert ( i + 1 , result ) ; return newRightSibling ; } } insert ( i , child ) { this . children . splice ( i , 0 , child ) ; this . keys . splice ( i , 0 , child . maxKey ( ) ) ; } splitOffRightSide ( ) { var half = this . children . length >> 1 ; return new BNodeInternal < K , V > ( this . children . splice ( half ) , this . keys . splice ( half ) ) ; } takeFromRight ( rhs ) { this . keys . push ( rhs . keys . shift ( ) ! ) ; this . children . push ( ( rhs as BNodeInternal < K , V > ) . children . shift ( ) ! ) ; } takeFromLeft ( lhs ) { this . keys . unshift ( lhs . keys . pop ( ) ! ) ; this . children . unshift ( ( lhs as BNodeInternal < K , V > ) . children . pop ( ) ! ) ; } forRange < R > ( low , high , includeHigh , editMode , tree , count , onFound ? ) { var cmp = tree . _compare ; var keys = this . keys , children = this . children ; var iLow = this . indexOf ( low , 0 , cmp ) , i = iLow ; var iHigh = Math . min ( high === low ? iLow : this . indexOf ( high , 0 , cmp ) , keys . length - 1 ) ; if ( ! editMode ) { for ( ; i <= iHigh ; i ++ ) { var result = children [ i ] . forRange ( low , high , includeHigh , editMode , tree , count , onFound ) ; if ( typeof result !== 'number' ) return result ; count = result ; } } else if ( i <= iHigh ) { try { for ( ; i <= iHigh ; i ++ ) { if ( children [ i ] . isShared ) children [ i ] = children [ i ] . clone ( ) ; var result = children [ i ] . forRange ( low , high , includeHigh , editMode , tree , count , onFound ) ; keys [ i ] = children [ i ] . maxKey ( ) ; if ( typeof result !== 'number' ) return result ; count = result ; } } finally { var half = tree . _maxNodeSize >> 1 ; if ( iLow > 0 ) iLow -- ; for ( i = iHigh ; i >= iLow ; i -- ) { if ( children [ i ] . keys . length <= half ) { if ( children [ i ] . keys . length !== 0 ) { this . tryMerge ( i , tree . _maxNodeSize ) ; } else { keys . splice ( i , 1 ) ; children . splice ( i , 1 ) ; } } } if ( children . length !== 0 && children [ 0 ] . keys . length === 0 ) check ( false , "emptiness bug" ) ; } } return count ; } /** Merges child i with child i+1 if their combined size is not too large */ tryMerge ( i , maxSize ) { var children = this . children ; if ( i >= 0 && i + 1 < children . length ) { if ( children [ i ] . keys . length + children [ i + 1 ] . keys . length <= maxSize ) { if ( children [ i ] . isShared ) children [ i ] = children [ i ] . clone ( ) ; children [ i ] . mergeSibling ( children [ i + 1 ] , maxSize ) ; children . splice ( i + 1 , 1 ) ; this . keys . splice ( i + 1 , 1 ) ; this . keys [ i ] = children [ i ] . maxKey ( ) ; return true ; } } return false ; } mergeSibling ( rhs , maxNodeSize ) { var oldLength = this . keys . length ; this . keys . push . apply ( this . keys , rhs . keys ) ; this . children . push . apply ( this . children , ( rhs as any as BNodeInternal < K , V > ) . children ) ; this . tryMerge ( oldLength - 1 , maxNodeSize ) ; } } /**
 * A walkable pointer into a BTree for computing efficient diffs between trees with shared data.
 * - A cursor points to either a key/value pair (KVP) or a node (which can be either a leaf or an internal node).
 *    As a consequence, a cursor cannot be created for an empty tree.
 * - A cursor can be walked forwards using `step`. A cursor can be compared to another cursor to
 *    determine which is ahead in advancement.
 * - A cursor is valid only for the tree it was created from, and only until the first edit made to
 *    that tree since the cursor's creation.
 * - A cursor contains a key for the current location, which is the maxKey when the cursor points to a node
 *    and a key corresponding to a value when pointing to a leaf.
 * - Leaf is only populated if the cursor points to a KVP. If this is the case, levelIndices.length === internalSpine.length + 1
 *    and levelIndices[levelIndices.length - 1] is the index of the value.
 */ type DiffCursor < K , V > = { height : number ; internalSpine : BNode < K , V > [ ] [ ] ; levelIndices : number [ ] ; leaf : BNode < K , V > | undefined ; currentKey : K ; } ; var undefVals = [ ] ; const Delete = { delete : true } , DeleteRange = ( ) => Delete ; const Break = { break : true } ; const EmptyLeaf = ( function ( ) { var n = new BNode < any , any > ( ) ; n . isShared = true ; return n ; } ) ( ) ; const EmptyArray = [ ] ; const ReusedArray = [ ] ; function check ( fact , ... args ) { if ( ! fact ) { args . unshift ( 'B+ tree' ) ; throw new Error ( args . join ( ' ' ) ) ; } } /** A BTree frozen in the empty state. */ export const EmptyBTree = ( ( ) => { let t = new BTree ( ) ; t . freeze ( ) ; return t ; } ) ( ) ;