module Webglimpse { export class BinaryTree < V > { private _root : TreeNode < V > ; private _comp : Comparator < V > ; private _size : number ; constructor ( comparator ) { this . _root = null ; this . _comp = comparator ; this . _size = 0 ; } insert ( value ) { this . _root = this . insert0 ( value , this . _root ) ; } remove ( value ) { this . _root = this . remove0 ( value , this . _root ) ; } removeAll ( ) { this . _root = null ; this . _size = 0 ; } contains ( value ) { return this . contains0 ( value , this . _root ) !== null ; } getValue ( value ) { return this . contains0 ( value , this . _root ) ; } get size ( ) : number { return this . _size ; } get isEmpty ( ) : boolean { return ( this . _size === 0 ) ; } ceiling ( value ) { return this . higher0 ( value , this . _root , true ) ; } floor ( value ) { return this . lower0 ( value , this . _root , true ) ; } lower ( value ) { return this . lower0 ( value , this . _root , false ) ; } higher ( value ) { return this . higher0 ( value , this . _root , false ) ; } headSet ( value , inclusive = true ) { var results = new Array < V > ( ) ; this . head0 ( value , inclusive , this . _root , results ) ; return results ; } tailSet ( value , inclusive = false ) { var results = new Array < V > ( ) ; this . tail0 ( value , inclusive , this . _root , results ) ; return results ; } subSet ( low , high , lowInclusive = true , highInclusive = false ) { var results = new Array < V > ( ) ; this . sub0 ( low , high , lowInclusive , highInclusive , this . _root , results ) ; return results ; } toArray ( ) { var results = new Array < V > ( ) ; this . addAll0 ( this . _root , results ) ; return results ; } iterator ( ) { var node = this . _root ; var down ; var stack = new Array < TreeNode < V > > ( ) ; while ( node != null && node . left != null ) { stack . push ( node ) ; node = node . left ; } down = node . right != null ; return { next : function ( ) : V { var value = node . value ; if ( down && node != null && node . right != null ) { node = node . right ; while ( node != null && node . left != null ) { stack . push ( node ) ; node = node . left ; } down = node . right != null ; } else { node = stack . pop ( ) ; down = true ; } return value ; } , hasNext : function ( ) : boolean { return node != null ; } } ; } compare ( node1 , node2 ) { return this . _comp . compare ( node1 , node2 ) ; } private contains0 ( value , node ) { if ( node == null ) { return null ; } var comp = this . compare ( value , node . value ) ; if ( comp > 0 ) { return this . contains0 ( value , node . right ) ; } else if ( comp < 0 ) { return this . contains0 ( value , node . left ) ; } else { return node . value ; } } private lower0 ( value , node , inclusive ) { if ( node == null ) { return null ; } var comp = this . compare ( value , node . value ) ; var candidate ; if ( comp > 0 ) { candidate = this . lower0 ( value , node . right , inclusive ) ; return candidate != null ? candidate : node . value ; } else if ( comp < 0 || ( ! inclusive && comp == 0 ) ) { candidate = this . lower0 ( value , node . left , inclusive ) ; if ( candidate == null ) candidate = node . value ; comp = this . compare ( value , candidate ) ; return comp > 0 || ( inclusive && comp == 0 ) ? candidate : null ; } else { return node . value ; } } private higher0 ( value , node , inclusive ) { if ( node == null ) { return null ; } var comp = this . compare ( value , node . value ) ; var candidate ; if ( comp < 0 ) { candidate = this . higher0 ( value , node . left , inclusive ) ; return candidate != null ? candidate : node . value ; } else if ( comp > 0 || ( ! inclusive && comp == 0 ) ) { candidate = this . higher0 ( value , node . right , inclusive ) ; if ( candidate == null ) candidate = node . value ; comp = this . compare ( value , candidate ) ; return comp < 0 || ( inclusive && comp == 0 ) ? candidate : null ; } else { return node . value ; } } private sub0 ( low , high , lowInclusive , highInclusive , node , results ) { if ( node == null ) { return ; } var compLow = this . compare ( low , node . value ) ; if ( compLow > 0 || ( compLow == 0 && ! lowInclusive ) ) { return this . sub0 ( low , high , lowInclusive , highInclusive , node . right , results ) ; } var compHigh = this . compare ( high , node . value ) ; if ( compHigh < 0 || ( compHigh == 0 && ! highInclusive ) ) { return this . sub0 ( low , high , lowInclusive , highInclusive , node . left , results ) ; } this . sub0 ( low , high , lowInclusive , highInclusive , node . left , results ) ; results . push ( node . value ) ; this . sub0 ( low , high , lowInclusive , highInclusive , node . right , results ) ; } private head0 ( value , inclusive , node , results ) { if ( node == null ) { return ; } var comp = this . compare ( value , node . value ) ; if ( comp < 0 || ( comp == 0 && inclusive ) ) { this . head0 ( value , inclusive , node . left , results ) ; results . push ( node . value ) ; this . addAll0 ( node . right , results ) ; } else if ( comp > 0 ) { this . head0 ( value , inclusive , node . right , results ) ; } } private tail0 ( value , inclusive , node , results ) { if ( node == null ) { return ; } var comp = this . compare ( value , node . value ) ; if ( comp > 0 || ( comp == 0 && inclusive ) ) { this . addAll0 ( node . left , results ) ; results . push ( node . value ) ; this . tail0 ( value , inclusive , node . right , results ) ; } else if ( comp < 0 ) { this . tail0 ( value , inclusive , node . left , results ) ; } } private addAll0 ( node , results ) { if ( node == null ) { return ; } this . addAll0 ( node . left , results ) ; results . push ( node . value ) ; this . addAll0 ( node . right , results ) ; } private remove0 ( value , node ) { if ( node == null ) { return node ; } var comp = this . compare ( value , node . value ) ; if ( comp < 0 ) { node . left = this . remove0 ( value , node . left ) ; } else if ( comp > 0 ) { node . right = this . remove0 ( value , node . right ) ; } else { if ( node . isLeaf ( ) ) { return null ; } else if ( node . left == null ) { var lower = node . getSuccessor ( ) ; node . right = this . remove0 ( lower . value , node . right ) ; node . value = lower . value ; } else { var lower = node . getPredecessor ( ) ; node . left = this . remove0 ( lower . value , node . left ) ; node . value = lower . value ; } this . _size -= 1 ; } node = this . decreaseLevel0 ( node ) ; node = this . skew0 ( node ) ; node . right = this . skew0 ( node . right ) ; if ( node . right != null ) { node . right . right = this . skew0 ( node . right . right ) ; } node = this . split0 ( node ) ; node . right = this . split0 ( node . right ) ; return node ; } private level0 ( node ) { if ( node == null ) { return 0 ; } else { return node . level ; } } private decreaseLevel0 ( node ) { var correctLevel = Math . min ( this . level0 ( node . left ) , this . level0 ( node . right ) ) + 1 ; if ( correctLevel < node . level ) { node . level = correctLevel ; if ( node . right != null && correctLevel < node . right . level ) { node . right . level = correctLevel ; } } return node ; } private insert0 ( value , node ) { if ( node == null ) { this . _size += 1 ; return this . newTreeNode0 ( value ) ; } var comp = this . compare ( value , node . value ) ; if ( comp < 0 ) { node . left = this . insert0 ( value , node . left ) ; } else if ( comp > 0 ) { node . right = this . insert0 ( value , node . right ) ; } node = this . skew0 ( node ) ; node = this . split0 ( node ) ; return node ; } newTreeNode0 ( value ) { return new TreeNode ( value ) ; } private skew0 ( node ) { if ( node == null ) { return null ; } else if ( node . left == null ) { return node ; } else if ( node . left . level == node . level ) { var left = node . left ; node . left = left . right ; left . right = node ; return left ; } else { return node ; } } private split0 ( node ) { if ( node == null ) { return null ; } else if ( node . right == null || node . right . right == null ) { return node ; } else if ( node . level == node . right . right . level ) { var right = node . right ; node . right = right . left ; right . left = node ; right . level = right . level + 1 ; return right ; } else { return node ; } } } export class TreeNode < V > { private _level : number ; private _right : TreeNode < V > ; private _left : TreeNode < V > ; private _value : V ; constructor ( value , level = 1 , left = null , right = null ) { this . _level = level ; this . _right = right ; this . _left = left ; this . _value = value ; } get level ( ) : number { return this . _level ; } get right ( ) : TreeNode < V > { return this . _right ; } get left ( ) : TreeNode < V > { return this . _left ; } get value ( ) : V { return this . _value ; } set right ( node ) { this . _right = node ; } set left ( node ) { this . _left = node ; } set level ( level ) { this . _level = level ; } set value ( value ) { this . _value = value ; } isLeaf ( ) { return this . right == null && this . left == null ; } getSuccessor ( ) { var node = this . right ; while ( node != null && node . left != null ) { node = node . left ; } return node ; } getPredecessor ( ) { var node = this . left ; while ( node != null && node . right != null ) { node = node . right ; } return node ; } toString ( ) { return this . value . toString ( ) + ':' + this . level . toString ( ) ; } } export interface Iterator < V > { hasNext ( ) : boolean ; next ( ) : V ; } export interface Comparator < V > { compare ( node1 , node2 ) : number ; } export class StringComparator implements Comparator < string > { compare ( value1 , value2 ) { return value1 . toLocaleLowerCase ( ) . localeCompare ( value2 . toLocaleLowerCase ( ) ) ; } } export class NumberComparator implements Comparator < number > { compare ( value1 , value2 ) { return value1 - value2 ; } } export function createStringTree ( ) { return new BinaryTree ( new StringComparator ( ) ) ; } export function createNumberTree ( ) { return new BinaryTree ( new NumberComparator ( ) ) ; } }