export class Node < K , V > { public left : Node < K , V > | null = null ; public right : Node < K , V > | null = null ; public height : number = 0 ; param key param value constructor ( public key , public value ) { } return public get leftHeight ( ) : number { if ( ! this . left ) { return - 1 ; } return this . left . height ; } return public get rightHeight ( ) : number { if ( ! this . right ) { return - 1 ; } return this . right . height ; } return public rotateRight ( ) { const other = < Node < K , V > > this . left ; this . left = other . right ; other . right = this ; this . height = Math . max ( this . leftHeight , this . rightHeight ) + 1 ; other . height = Math . max ( other . leftHeight , this . height ) + 1 ; return other ; } return public rotateLeft ( ) { const other = < Node < K , V > > this . right ; this . right = other . left ; other . left = this ; this . height = Math . max ( this . leftHeight , this . rightHeight ) + 1 ; other . height = Math . max ( other . rightHeight , this . height ) + 1 ; return other ; } } export type DistanceFunction < K > = ( a : K , b : K ) => number ; export type CompareFunction < K > = ( a : K , b : K ) => number ; /**
 * Represents how balanced a node's left and right children are.
 */ const enum BalanceState { /** Right child's height is 2+ greater than left child's height */ UNBALANCED_RIGHT , /** Right child's height is 1 greater than left child's height */ SLIGHTLY_UNBALANCED_RIGHT , /** Left and right children have the same height */ BALANCED , /** Left child's height is 1 greater than right child's height */ SLIGHTLY_UNBALANCED_LEFT , /** Left child's height is 2+ greater than right child's height */ UNBALANCED_LEFT } export class NearestNeighborDict < K , V > { public static NUMERIC_DISTANCE_FUNCTION = ( a , b ) => ( a > b ? a - b : b - a ) ; public static DEFAULT_COMPARE_FUNCTION = ( a , b ) => ( a > b ? 1 : a < b ? - 1 : 0 ) ; protected root : Node < K , V > | null = null ; /**
     * Creates a new AVL Tree.
     */ constructor ( start , private distance , private compare = NearestNeighborDict . DEFAULT_COMPARE_FUNCTION ) { this . insert ( start . key , start . value ) ; } public height ( ) { return this . root ? this . root . height : 0 ; } param key param value public insert ( key , value ? ) { this . root = this . _insert ( key , value , this . root ) ; } param key return public getNearest ( key ) { return this . _getNearest ( key , this . root ! , this . root ! ) ; } param key param root return private _insert ( key , value , root ) { if ( root === null ) { return new Node ( key , value ) ; } if ( this . compare ( key , root . key ) < 0 ) { root . left = this . _insert ( key , value , root . left ) ; } else if ( this . compare ( key , root . key ) > 0 ) { root . right = this . _insert ( key , value , root . right ) ; } else { return root ; } root . height = Math . max ( root . leftHeight , root . rightHeight ) + 1 ; const balanceState = this . _getBalanceState ( root ) ; if ( balanceState === BalanceState . UNBALANCED_LEFT ) { if ( this . compare ( key , root . left ! . key ) < 0 ) { root = root . rotateRight ( ) ; } else { root . left = root . left ! . rotateLeft ( ) ; return root . rotateRight ( ) ; } } if ( balanceState === BalanceState . UNBALANCED_RIGHT ) { if ( this . compare ( key , root . right ! . key ) > 0 ) { root = root . rotateLeft ( ) ; } else { root . right = root . right ! . rotateRight ( ) ; return root . rotateLeft ( ) ; } } return root ; } param key param root param closest return private _getNearest ( key , root , closest ) { const result = this . compare ( key , root . key ) ; if ( result === 0 ) { return root ; } closest = this . distance ( key , root . key ) < this . distance ( key , closest . key ) ? root : closest ; if ( result < 0 ) { return root . left ? this . _getNearest ( key , root . left , closest ) : closest ; } else { return root . right ? this . _getNearest ( key , root . right , closest ) : closest ; } } param node return private _getBalanceState ( node ) { const heightDifference = node . leftHeight - node . rightHeight ; switch ( heightDifference ) { case - 2 : return BalanceState . UNBALANCED_RIGHT ; case - 1 : return BalanceState . SLIGHTLY_UNBALANCED_RIGHT ; case 1 : return BalanceState . SLIGHTLY_UNBALANCED_LEFT ; case 2 : return BalanceState . UNBALANCED_LEFT ; case 0 : return BalanceState . BALANCED ; default : { console . error ( 'Internal error: Avl tree should never be more than two levels unbalanced' ) ; if ( heightDifference > 0 ) { return BalanceState . UNBALANCED_LEFT ; } return BalanceState . UNBALANCED_RIGHT ; } } } }