import { ArrayExt , each , empty , IIterable , IIterator , IRetroable , IterableOrArrayLike } from '@lumino/algorithm' ; /**
 * A generic B+ tree.
 *
 * #### Notes
 * Most operations have `O(log32 n)` or better complexity.
 */ export class BPlusTree < T > implements IIterable < T > , IRetroable < T > { param cmp constructor ( cmp ) { this . cmp = cmp ; } /**
     * The item comparison function for the tree.
     *
     * #### Complexity
     * `O(1)`
     */ readonly cmp : ( a : T , b : T ) => number ; /**
     * Whether the tree is empty.
     *
     * #### Complexity
     * `O(1)`
     */ get isEmpty ( ) : boolean { return this . _root . size === 0 ; } /**
     * The size of the tree.
     *
     * #### Complexity
     * `O(1)`
     */ get size ( ) : number { return this . _root . size ; } /**
     * The first item in the tree.
     *
     * This is `undefined` if the tree is empty.
     *
     * #### Complexity
     * `O(log32 n)`
     */ get first ( ) : T | undefined { let node = Private . firstLeaf ( this . _root ) ; return node . size > 0 ? node . items [ 0 ] : undefined ; } /**
     * The last item in the tree.
     *
     * This is `undefined` if the tree is empty.
     *
     * #### Complexity
     * `O(log32 n)`
     */ get last ( ) : T | undefined { let node = Private . lastLeaf ( this . _root ) ; return node . size > 0 ? node . items [ node . size - 1 ] : undefined ; } returns iter ( ) { return Private . iterItems ( this . _root ) ; } returns retro ( ) { return Private . retroItems ( this . _root ) ; } param start param stop returns slice ( start ? , stop ? ) { return Private . sliceItems ( this . _root , start , stop ) ; } param start param stop returns retroSlice ( start ? , stop ? ) { return Private . retroSliceItems ( this . _root , start , stop ) ; } param index returns at ( index ) { return Private . itemAt ( this . _root , index ) ; } param key param cmp returns has < U > ( key , cmp ) { return Private . hasItem ( this . _root , key , cmp ) ; } param key param cmp returns indexOf < U > ( key , cmp ) { return Private . indexOf ( this . _root , key , cmp ) ; } param item param cmp returns get < U > ( key , cmp ) { return Private . getItem ( this . _root , key , cmp ) ; } param items assign ( items ) { this . clear ( ) ; this . update ( items ) ; } param item returns insert ( item ) { let existing = Private . insertItem ( this . _root , item , this . cmp ) ; this . _root = Private . maybeSplitRoot ( this . _root ) ; return existing ; } param items update ( items ) { each ( items , item => { this . insert ( item ) ; } ) ; } param key param cmp returns delete < U > ( key , cmp ) { let item = Private . deleteItem ( this . _root , key , cmp ) ; this . _root = Private . maybeExtractRoot ( this . _root ) ; return item ; } param index returns remove ( index ) { let item = Private . removeItem ( this . _root , index ) ; this . _root = Private . maybeExtractRoot ( this . _root ) ; return item ; } /**
     * Clear the contents of the tree.
     *
     * #### Complexity
     * `O(n)`
     */ clear ( ) { Private . clear ( this . _root ) ; this . _root = new Private . LeafNode < T > ( ) ; } private _root : Private . Node < T > = new Private . LeafNode < T > ( ) ; } /**
 * The namespace for the `BPlusTree` class statics.
 */ export namespace BPlusTree { param items param cmp returns export function from < T > ( items , cmp ) { let tree = new BPlusTree < T > ( cmp ) ; tree . assign ( items ) ; return tree ; } } /**
 * The namespace for the module implementation details.
 */ namespace Private { /**
     * A const enum of the B+ tree node types.
     */ export const enum NodeType { Branch , Leaf } /**
     * A branch node in a B+ tree.
     */ export class BranchNode < T > { /**
         * The left-most item of each child subtree.
         */ readonly items : T [ ] = [ ] ; /**
         * The cumulative sizes of each child subtree.
         */ readonly sizes : number [ ] = [ ] ; /**
         * The child nodes of this branch node.
         */ readonly children : Node < T > [ ] = [ ] ; /**
         * The discriminated type of the node.
         */ get type ( ) : NodeType . Branch { return NodeType . Branch ; } /**
         * The total number of items in the subtree.
         */ get size ( ) : number { return this . sizes [ this . sizes . length - 1 ] ; } /**
         * The tree width of the node.
         */ get width ( ) : number { return this . children . length ; } } /**
     * A leaf node in a B+ tree.
     */ export class LeafNode < T > { /**
         * The next sibling leaf node of this leaf node.
         */ next : LeafNode < T > | null = null ; /**
         * The previous sibling leaf node of this leaf node.
         */ prev : LeafNode < T > | null = null ; /**
         * The items of the leaf.
         */ readonly items : T [ ] = [ ] ; /**
         * The discriminated type of the node.
         */ get type ( ) : NodeType . Leaf { return NodeType . Leaf ; } /**
         * The total number of items in the leaf.
         */ get size ( ) : number { return this . items . length ; } /**
         * The tree width of the node.
         */ get width ( ) : number { return this . items . length ; } } /**
     * A type alias for the B+ tree nodes.
     */ export type Node < T > = BranchNode < T > | LeafNode < T > ; param node returns export function firstLeaf < T > ( node ) { while ( node . type === NodeType . Branch ) { node = node . children [ 0 ] ; } return node ; } param node returns export function lastLeaf < T > ( node ) { while ( node . type === NodeType . Branch ) { node = node . children [ node . children . length - 1 ] ; } return node ; } param node returns export function iterItems < T > ( node ) { let leaf = firstLeaf ( node ) ; return new ForwardIterator < T > ( leaf , 0 , - 1 ) ; } param node returns export function retroItems < T > ( node ) { let leaf = lastLeaf ( node ) ; return new RetroIterator < T > ( leaf , leaf . size - 1 , - 1 ) ; } param node param start param stop returns export function sliceItems < T > ( node , start ? , stop ? ) { if ( start === undefined ) { start = 0 ; } else if ( start < 0 ) { start = Math . max ( 0 , start + node . size ) ; } else { start = Math . min ( start , node . size ) ; } if ( stop === undefined ) { stop = node . size ; } else if ( stop < 0 ) { stop = Math . max ( 0 , stop + node . size ) ; } else { stop = Math . min ( stop , node . size ) ; } let count = Math . max ( 0 , stop - start ) ; if ( count === 0 ) { return empty < T > ( ) ; } while ( node . type === NodeType . Branch ) { let i = findPivotIndexByIndex ( node . sizes , start ) ; if ( i > 0 ) start -= node . sizes [ i - 1 ] ; node = node . children [ i ] ; } return new ForwardIterator < T > ( node , start , count ) ; } param node param start param stop returns export function retroSliceItems < T > ( node , start ? , stop ? ) { if ( start === undefined ) { start = node . size - 1 ; } else if ( start < 0 ) { start = Math . max ( - 1 , start + node . size ) ; } else { start = Math . min ( start , node . size - 1 ) ; } if ( stop === undefined ) { stop = - 1 ; } else if ( stop < 0 ) { stop = Math . max ( - 1 , stop + node . size ) ; } else { stop = Math . min ( stop , node . size - 1 ) ; } let count = Math . max ( 0 , start - stop ) ; if ( count === 0 ) { return empty < T > ( ) ; } while ( node . type === NodeType . Branch ) { let i = findPivotIndexByIndex ( node . sizes , start ) ; if ( i > 0 ) start -= node . sizes [ i - 1 ] ; node = node . children [ i ] ; } return new RetroIterator < T > ( node , start , count ) ; } param node param index returns export function itemAt < T > ( node , index ) { if ( index < 0 ) { index += node . size ; } if ( index < 0 || index >= node . size ) { return undefined ; } while ( node . type === NodeType . Branch ) { let i = findPivotIndexByIndex ( node . sizes , index ) ; if ( i > 0 ) index -= node . sizes [ i - 1 ] ; node = node . children [ i ] ; } return node . items [ index ] ; } param node param key param cmp returns export function hasItem < T , U > ( node , key , cmp ) { while ( node . type === NodeType . Branch ) { let i = findPivotIndexByKey ( node . items , key , cmp ) ; node = node . children [ i ] ; } let i = findKeyIndex ( node . items , key , cmp ) ; return i >= 0 ; } param node param key param cmp returns export function indexOf < T , U > ( node , key , cmp ) { let index = 0 ; while ( node . type === NodeType . Branch ) { let i = findPivotIndexByKey ( node . items , key , cmp ) ; if ( i > 0 ) index += node . sizes [ i - 1 ] ; node = node . children [ i ] ; } let i = findKeyIndex ( node . items , key , cmp ) ; return i >= 0 ? index + i : - index + i ; } param node param key param cmp returns export function getItem < T , U > ( node , key , cmp ) { while ( node . type === NodeType . Branch ) { let i = findPivotIndexByKey ( node . items , key , cmp ) ; node = node . children [ i ] ; } let i = findKeyIndex ( node . items , key , cmp ) ; return i >= 0 ? node . items [ i ] : undefined ; } param node param item param cmp returns export function insertItem < T > ( node , item , cmp ) { if ( node . type === NodeType . Leaf ) { let i = findKeyIndex ( node . items , item , cmp ) ; let existing ; if ( i >= 0 ) { existing = node . items [ i ] ; node . items [ i ] = item ; } else { existing = undefined ; ArrayExt . insert ( node . items , - i - 1 , item ) ; } return existing ; } let i = findPivotIndexByKey ( node . items , item , cmp ) ; let child = node . children [ i ] ; let prevSize = child . size ; let existing = insertItem ( child , item , cmp ) ; let currSize = child . size ; node . items [ i ] = child . items [ 0 ] ; if ( prevSize === currSize ) { return existing ; } if ( child . width > MAX_NODE_WIDTH ) { let next = splitNode ( child ) ; ArrayExt . insert ( node . children , i + 1 , next ) ; ArrayExt . insert ( node . items , i + 1 , next . items [ 0 ] ) ; } updateSizes ( node , i ) ; return existing ; } param node param key param cmp returns export function deleteItem < T , U > ( node , key , cmp ) { if ( node . type === NodeType . Leaf ) { let i = findKeyIndex ( node . items , key , cmp ) ; if ( i < 0 ) { return undefined ; } return ArrayExt . removeAt ( node . items , i ) ; } let i = findPivotIndexByKey ( node . items , key , cmp ) ; let child = node . children [ i ] ; let prevSize = child . size ; let item = deleteItem ( child , key , cmp ) ; let currSize = child . size ; if ( prevSize === currSize ) { return item ; } node . items [ i ] = child . items [ 0 ] ; if ( child . width < MIN_NODE_WIDTH ) { i = joinChild ( node , i ) ; } updateSizes ( node , i ) ; return item ; } param node param index returns export function removeItem < T > ( node , index ) { if ( index < 0 ) { index += node . size ; } if ( index < 0 || index >= node . size ) { return undefined ; } if ( node . type === NodeType . Leaf ) { return ArrayExt . removeAt ( node . items , index ) ; } let i = findPivotIndexByIndex ( node . sizes , index ) ; if ( i > 0 ) index -= node . sizes [ i ] ; let child = node . children [ i ] ; let item = removeItem ( child , index ) ; node . items [ i ] = child . items [ 0 ] ; if ( child . width < MIN_NODE_WIDTH ) { i = joinChild ( node , i ) ; } updateSizes ( node , i ) ; return item ; } param node export function clear < T > ( node ) { if ( node . type === NodeType . Branch ) { each ( node . children , clear ) ; node . children . length = 0 ; node . sizes . length = 0 ; node . items . length = 0 ; } else { node . items . length = 0 ; node . next = null ; node . prev = null ; } } param node returns export function maybeSplitRoot < T > ( node ) { if ( node . width <= MAX_NODE_WIDTH ) { return node ; } let root = new BranchNode < T > ( ) ; let next = splitNode ( node ) ; root . sizes [ 0 ] = node . size ; root . sizes [ 1 ] = node . size + next . size ; root . children [ 0 ] = node ; root . children [ 1 ] = next ; root . items [ 0 ] = node . items [ 0 ] ; root . items [ 1 ] = next . items [ 0 ] ; return root ; } param node returns export function maybeExtractRoot < T > ( node ) { if ( node . type === NodeType . Leaf ) { return node ; } if ( node . children . length > 1 ) { return node ; } let root = node . children . pop ( ) ! ; clear ( node ) ; return root ; } /**
     * The maximum width for a node in the tree.
     */ const MAX_NODE_WIDTH = 32 ; /**
     * The minimum width for a node in the tree.
     */ const MIN_NODE_WIDTH = MAX_NODE_WIDTH >> 1 ; /**
     * A forward iterator for a B+ tree.
     */ class ForwardIterator < T > implements IIterator < T > { param node param index param count constructor ( node , index , count ) { this . _node = node ; this . _index = index ; this . _count = count ; } returns iter ( ) { return this ; } returns clone ( ) { return new ForwardIterator < T > ( this . _node , this . _index , this . _count ) ; } returns next ( ) { if ( this . _node === null || this . _count === 0 ) { return undefined ; } if ( this . _index >= this . _node . size ) { this . _node = this . _node . next ; this . _index = 0 ; return this . next ( ) ; } if ( this . _count > 0 ) { this . _count -- ; } return this . _node . items [ this . _index ++ ] ; } private _index : number ; private _count : number ; private _node : LeafNode < T > | null ; } /**
     * A reverse iterator for a B+ tree.
     */ class RetroIterator < T > implements IIterator < T > { param node param index param count constructor ( node , index , count ) { this . _node = node ; this . _index = index ; this . _count = count ; } returns iter ( ) { return this ; } returns clone ( ) { return new RetroIterator < T > ( this . _node , this . _index , this . _count ) ; } returns next ( ) { if ( this . _node === null || this . _count === 0 ) { return undefined ; } if ( this . _index >= this . _node . size ) { this . _index = this . _node . size - 1 ; } if ( this . _index < 0 ) { this . _node = this . _node . prev ; this . _index = this . _node ? this . _node . size - 1 : - 1 ; return this . next ( ) ; } if ( this . _count > 0 ) { this . _count -- ; } return this . _node . items [ this . _index -- ] ; } private _index : number ; private _count : number ; private _node : LeafNode < T > | null ; } /**
     * Find the pivot index for a particular local index.
     */ function findPivotIndexByIndex ( sizes , index ) { let n = sizes . length ; for ( let i = 0 ; i < n ; ++ i ) { if ( sizes [ i ] > index ) { return i ; } } return n - 1 ; } /**
     * Find the pivot index for a particular key.
     */ function findPivotIndexByKey < T , U > ( items , key , cmp ) { let n = items . length ; for ( let i = 1 ; i < n ; ++ i ) { if ( cmp ( items [ i ] , key ) > 0 ) { return i - 1 ; } } return n - 1 ; } /**
     * Find the key index for a particular key.
     */ function findKeyIndex < T , U > ( items , key , cmp ) { let n = items . length ; for ( let i = 0 ; i < n ; ++ i ) { let c = cmp ( items [ i ] , key ) ; if ( c === 0 ) { return i ; } if ( c > 0 ) { return - i - 1 ; } } return - n - 1 ; } /**
     * Update the sizes of a branch node starting at the given index.
     */ function updateSizes < T > ( node , i ) { let { sizes , children } = node ; let last = i > 0 ? sizes [ i - 1 ] : 0 ; for ( let n = children . length ; i < n ; ++ i ) { last = sizes [ i ] = last + children [ i ] . size ; } sizes . length = children . length ; } param node returns function splitNode < T > ( node ) { if ( node . type === NodeType . Leaf ) { let next = new LeafNode < T > ( ) ; let v1 = node . items ; let v2 = next . items ; for ( let i = MIN_NODE_WIDTH , n = v1 . length ; i < n ; ++ i ) { v2 . push ( v1 [ i ] ) ; } v1 . length = MIN_NODE_WIDTH ; if ( node . next ) node . next . prev = next ; next . next = node . next ; next . prev = node ; node . next = next ; return next ; } let next = new BranchNode < T > ( ) ; let c1 = node . children ; let c2 = next . children ; for ( let i = MIN_NODE_WIDTH , n = c1 . length ; i < n ; ++ i ) { c2 . push ( c1 [ i ] ) ; } c1 . length = MIN_NODE_WIDTH ; let v1 = node . items ; let v2 = next . items ; for ( let i = MIN_NODE_WIDTH , n = v1 . length ; i < n ; ++ i ) { v2 . push ( v1 [ i ] ) ; } v1 . length = MIN_NODE_WIDTH ; updateSizes ( node , MIN_NODE_WIDTH ) ; updateSizes ( next , 0 ) ; return next ; } param node param i returns function joinChild < T > ( node , i ) { let child = node . children [ i ] ; let sibling = i === 0 ? node . children [ i + 1 ] : node . children [ i - 1 ] ; let hasNext = i === 0 ; let isLeaf = child . type === NodeType . Leaf ; let hasExtra = sibling . width > MIN_NODE_WIDTH ; if ( isLeaf && hasExtra && hasNext ) { let c = child as LeafNode < T > ; let s = sibling as LeafNode < T > ; c . items . push ( s . items . shift ( ) ! ) ; node . items [ i + 1 ] = s . items [ 0 ] ; return i ; } if ( isLeaf && hasExtra && ! hasNext ) { let c = child as LeafNode < T > ; let s = sibling as LeafNode < T > ; c . items . unshift ( s . items . pop ( ) ! ) ; node . items [ i ] = c . items [ 0 ] ; return i - 1 ; } if ( isLeaf && ! hasExtra && hasNext ) { let c = child as LeafNode < T > ; let s = sibling as LeafNode < T > ; s . items . unshift ( ... c . items ) ; ArrayExt . removeAt ( node . children , i ) ; ArrayExt . removeAt ( node . items , i + 1 ) ; if ( c . prev ) c . prev . next = s ; s . prev = c . prev ; clear ( c ) ; return i ; } if ( isLeaf && ! hasExtra && ! hasNext ) { let c = child as LeafNode < T > ; let s = sibling as LeafNode < T > ; s . items . push ( ... c . items ) ; ArrayExt . removeAt ( node . children , i ) ; ArrayExt . removeAt ( node . items , i ) ; if ( c . next ) c . next . prev = s ; s . next = c . next ; clear ( c ) ; return i - 1 ; } if ( ! isLeaf && hasExtra && hasNext ) { let c = child as BranchNode < T > ; let s = sibling as BranchNode < T > ; c . children . push ( s . children . shift ( ) ! ) ; c . items . push ( s . items . shift ( ) ! ) ; node . items [ i + 1 ] = s . items [ 0 ] ; updateSizes ( c , c . width - 1 ) ; updateSizes ( s , 0 ) ; return i ; } if ( ! isLeaf && hasExtra && ! hasNext ) { let c = child as BranchNode < T > ; let s = sibling as BranchNode < T > ; c . children . unshift ( s . children . pop ( ) ! ) ; c . items . unshift ( s . items . pop ( ) ! ) ; node . items [ i ] = c . items [ 0 ] ; updateSizes ( c , 0 ) ; updateSizes ( s , s . width - 1 ) ; return i - 1 ; } if ( ! isLeaf && ! hasExtra && hasNext ) { let c = child as BranchNode < T > ; let s = sibling as BranchNode < T > ; s . children . unshift ( ... c . children ) ; s . items . unshift ( ... c . items ) ; ArrayExt . removeAt ( node . children , i ) ; ArrayExt . removeAt ( node . items , i + 1 ) ; updateSizes ( s , 0 ) ; c . children . length = 0 ; clear ( c ) ; return i ; } if ( ! isLeaf && ! hasExtra && ! hasNext ) { let c = child as BranchNode < T > ; let s = sibling as BranchNode < T > ; s . children . push ( ... c . children ) ; s . items . push ( ... c . items ) ; ArrayExt . removeAt ( node . children , i ) ; ArrayExt . removeAt ( node . items , i ) ; updateSizes ( s , 0 ) ; c . children . length = 0 ; clear ( c ) ; return i - 1 ; } throw 'unreachable' ; } }