diff options
Diffstat (limited to 'tests/lexers/hx/example.txt')
| -rw-r--r-- | tests/lexers/hx/example.txt | 4363 |
1 files changed, 4363 insertions, 0 deletions
diff --git a/tests/lexers/hx/example.txt b/tests/lexers/hx/example.txt new file mode 100644 index 00000000..1a103725 --- /dev/null +++ b/tests/lexers/hx/example.txt @@ -0,0 +1,4363 @@ +---input--- +package util; + +import util.Map; +import util.Collection; +import util.Set; +import util.Option; +import util.Debug; +import util.Throwable; + +using util.StringFormat; + +/** + * An ordered map of (key,value) pairs. The key ordering is defined by + * a comparison function specified at construction. Duplicate keys + * are not allowed. + * + * Worst Case Time and Space Complexities: + * [operation] [time] [space] + * insert O(lg(n)) O(lg(n)) + * find O(lg(n)) O(1) + * delete O(lg(n)) O(lg(n)) + * range-query O(lg(n))* O(lg(n)) + * iteration O(n)** O(lg(n)) + * *range-query returns an iterator over elements in the range + * **total cost of iterating over the entire map + * + * The map is backed by a Left-Leaning Red-Black 2-3 Tree + * adapted from Robert Sedgewick (2008) (http://www.cs.princeton.edu/~rs/) + * + * Implementation choices (let size of tree be n) + * - Parent Pointers + * - This implementation omits parent pointers. + * - Omitting parent pointers saves n words of persistent memory + * at the expense of lg(n) stack space per operation. + * - Without parent pointers, most operations in the tree must + * either use recursion, or simulate recursion by saving a history + * of nodes via a stack. For example, each iterator will require + * lg(n) extra space to track progress through the tree. Insertions + * and deletions into the tree will also invalidate any existing + * iterators. + * - Node Size Information + * - This implementation omits the size of each node. + * - Omitting size information saves n words of long-term memory at + * the expense of not providing a find-kth operation. + * - This seems like a reasonable trade-off as range queries are + * generally more common than find-kth operations. The implementation + * used below could easily be modified to provide a version with + * size information should find-kth be of specific interest. + * - Recursive vs. Iterative + * - This implementation uses recursive algorithms. + * - The recursive implementations allow the code to remain compact and + * understandable. Since the height of LLRB 2-3 Trees is gaurenteed + * to be at most 2lg(n), stack overflow is typically not a concern. + * Unlike the standard single-rotation red-black algorithm, LLRB + * operations are not tail-recursive, so even an iterative + * version will require lg(n) extra memory. + */ +class OrderedMap<K,V> +{ + private var root :Null<Node<K,V>>; + private var nodeCount :Int; + private var comp :K -> K -> Int; + + public function new( keyComp :K -> K -> Int ) + { + root = null; + comp = keyComp; + nodeCount = 0; + assertInvariants(); + } + + /** + * @returns Some(v) if (\key,v) is in the map, None otherwise. + */ + public function get(key :K) :Option<V> + { + //normal BST search + var n = root; + while( n != null ) + { + var cmp = comp(key,n.key); + if( cmp < 0 ) + { + n = n.left; + } + else if ( cmp > 0 ) + { + n = n.right; + } + else + { + return Some(n.val); + } + } + return None; + } + + /** + * Puts (\key,\val) into the map or replaces the current value of \key + * with \val. + * + * @return None if \key currently is not in the map, or Some(v) if (\key,v) + * was in the map before the put operation. + */ + public function set(key :K, val :V) :Option<V> + { + var ret = new Ref<V>(null); + root = insertNode(root,key,val,ret); + root.color = black; + + assertInvariants(); + + if( ret.r == null ) + { + return None; + } + return Some(ret.r); + } + + private function insertNode(n :Node<K,V>, key :K, val :V, ret :Ref<V>) + { + //do the insertion at the leaf level + if( n == null ) + { + ++nodeCount; + return new Node<K,V>(key,val); + } + + //normal BST search + var cmp = comp(key,n.key); + if( cmp < 0 ) + { + n.left = insertNode(n.left,key,val,ret); + } + else if( cmp > 0 ) + { + n.right = insertNode(n.right,key,val,ret); + } + else + { + //the key is already in the map, update the value + ret.r = n.val; + n.val = val; + } + + return fixInvariants(n); + } + + /** + * Removes (\key,v) from the map if it exists. + * + * @return None if (\key,v) wasn't in the map, Some(v) otherwise. + */ + public function remove(key :K) :Option<V> + { + var ret = new Ref<V>(null); + if( root != null ) + { + root = deleteNode(root,key,ret); + if( root != null ) + { + root.color = black; + } + } + + assertInvariants(); + + if( ret.r == null ) + { + return None; + } + return Some(ret.r); + } + + private function deleteNode( n :Node<K,V>, key :K, ret :Ref<V> ) + { + if( comp(key,n.key) < 0 ) + { + if( isBlack(n.left) && isBlack(n.left.left) ) + { + //ensure we move into a 3-node + n = moveRedLeft(n); + } + n.left = deleteNode(n.left,key,ret); + } + else + { + if( isRed(n.left) ) + { + //ensure we move into a 3-node + n = rotateRight(n); + } + if( comp(key,n.key) == 0 && n.right == null ) + { + //delete the node + ret.r = n.val; + --nodeCount; + return null; + } + if( isBlack(n.right) && isBlack(n.right.left) ) + { + //ensure we move into a 3-node + n = moveRedRight(n); + } + if( comp(key,n.key) == 0 ) + { + Debug.assert(n.right != null); + + ret.r = n.val; + + //ensure we are deleting a node with at most one child + var min = minNode(n.right); + n.val = min.val; + n.key = min.key; + n.right = deleteMinNode(n.right); + } + else + { + n.right = deleteNode(n.right,key,ret); + } + } + + return fixInvariants(n); + } + + /** returns a view of the set of keys in this TreeMap **/ + public function keys() :SetView<K> + { + var _this = this; + + return { + size: function() return _this.size(), + iterator: function() return IterTools.mapIter(new NodeIterator(_this.root),function(x) return x.key), + exists: function(x) { + return switch(_this.get(x)) + { + case None: false; + case Some(_): true; + }; + }, + }; + } + + /** returns a view of the collection of values in this TreeMap **/ + public function values() :CollectionView<V> + { + var _this = this; + + return { + size: function() return _this.size(), + iterator: function() return IterTools.mapIter(new NodeIterator(_this.root),function(x) return x.val), + }; + } + + /** returns a view of the (key,value) pairs in this TreeMap **/ + public function entries() :CollectionView<Entry<K,V>> + { + var _this = this; + + return { + size: function() { + return _this.size(); + }, + iterator: function() { + return cast new NodeIterator(_this.root); + }, + }; + } + + /** returns the number of (key,value) pairs in the map **/ + public function size() :Int + { + return nodeCount; + } + + public function toString() :String + { + var sb = new StringBuf(); + + sb.add("{"); + for( entry in this.entries() ) + { + sb.add("%y => %y, ".sprintf([entry.key,entry.val])); + } + sb.add("}"); + + return sb.toString(); + } + + private static function isRed<K,V>( n :Node<K,V> ) + { + if( n == null ) return false; + return switch(n.color) + { + case red: true; + case black: false; + }; + } + + private static inline function isBlack<K,V>( n :Node<K,V> ) + { + return !isRed(n); + } + + private static function colorFlip<K,V>( n :Node<K,V> ) + { + n.color = oppositeColor(n.color); + n.left.color = oppositeColor(n.left.color); + n.right.color = oppositeColor(n.right.color); + } + + private static inline function oppositeColor( c :Color ) + { + return switch(c) + { + case red: black; + case black: red; + }; + } + + private static function rotateLeft<K,V>( n :Node<K,V> ) + { + Debug.assert(n != null); + Debug.assert(n.right != null); + /* + n x + / \ / \ + a x => n c + / \ / \ + b c a b + */ + var x = n.right; + n.right = x.left; + x.left = n; + x.color = n.color; + n.color = red; + return x; + } + + private static function rotateRight<K,V>( n :Node<K,V> ) + { + Debug.assert( n != null ); + Debug.assert( n.left != null ); + /* + n x + / \ / \ + x c => a n + / \ / \ + a b b c + */ + var x = n.left; + n.left = x.right; + x.right = n; + x.color = n.color; + n.color = red; + return x; + } + + private static function moveRedLeft<K,V>( n :Node<K,V> ) + { + //borrow extra node from right child (which is a 3-node) + colorFlip(n); + if( isRed(n.right.left) ) + { + n.right = rotateRight(n.right); + n = rotateLeft(n); + colorFlip(n); + } + return n; + } + + private static function moveRedRight<K,V>( n :Node<K,V> ) + { + //borrow extra node from left child (which is a 3-node) + colorFlip(n); + if( isRed(n.left.left) ) + { + n = rotateRight(n); + colorFlip(n); + } + return n; + } + + private static function fixInvariants<K,V>( n :Node<K,V> ) + { + if( isRed(n.right) && isBlack(n.left) ) + { + //ensure left-leaning property + n = rotateLeft(n); + } + if( isRed(n.left) && isRed(n.left.left) ) + { + //balance 4-node + n = rotateRight(n); + } + if( isRed(n.left) && isRed(n.right) ) + { + //split 4-node + colorFlip(n); + } + return n; + } + + private function deleteMinNode<K,V>( n :Node<K,V> ) + { + if( n.left == null ) + { + //delete + --nodeCount; + return null; + } + + if( isBlack(n.left) && isBlack(n.left.left) ) + { + n = moveRedLeft(n); + } + + n.left = deleteMinNode(n.left); + + return fixInvariants(n); + } + + private static function minNode<K,V>( n :Node<K,V> ) + { + Debug.assert(n != null); + + while( n.left != null ) + { + n = n.left; + } + return n; + } + + private static function maxNode<K,V>( n :Node<K,V> ) + { + Debug.assert(n != null); + + while( n.right != null ) + { + n = n.right; + } + return n; + } + + /** Used to verify that the invariants of the tree hold **/ + private inline function assertInvariants() + { + #if DEBUG + Debug.assert( isBlack(root), "root is black: " + root ); + + assertIsTree(root,new List<Node<K,V>>()); + assertBlackNodeCount(root); + assertBSTOrdering(root,comp); + #end + } + + private static function assertIsTree<K,V>( n: Node<K,V>, visited :List<Node<K,V>> ) + { + if( n == null ) + { + return; + } + + for( r in visited ) + { + Debug.assert( n != r ); + } + visited.push(n); + assertIsTree(n.left,visited); + assertIsTree(n.right,visited); + } + + private static function assertBlackNodeCount<K,V>( n: Node<K,V> ) :Int + { + if( n == null ) + { + return 1; + } + + var leftCount = assertBlackNodeCount(n.left); + var rightCount = assertBlackNodeCount(n.right); + + Debug.assert( + leftCount == rightCount, + "num of black nodes in all paths for left and right child not equal" + n + ); + + return leftCount + switch(n.color) { + case red: 0; + case black: 1; + } + } + + private static function assertBSTOrdering<K,V>( n: Node<K,V>, compK :K -> K -> Int ) :Void + { + if( n == null ) + { + return; + } + + if( n.left != null && n.left.val != null ) + { + Debug.assert( compK(n.left.key,n.key) < 0, "left child not less than its parent" + n ); + assertBSTOrdering(n.left,compK); + } + + if( n.right != null && n.right.val != null ) + { + Debug.assert( compK(n.key,n.right.key) < 0, "parent not less than its right child" + n ); + assertBSTOrdering(n.right,compK); + } + } +} + +private enum Color +{ + red; + black; +} + +private class Node<K,V> /*implements Entry<K,V>*/ +{ + public var left :Null<Node<K,V>>; + public var right :Null<Node<K,V>>; + public var color :Color; + + public var key :K; + public var val :V; + + public function new(k :K, v :V) + { + key = k; + val = v; + color = red; + } +} + +private class NodeIterator<K,V> +{ + private var curr :Node<K,V>; + private var fringe :Array<Node<K,V>>; + + public function new( root :Node<K,V> ) + { + fringe = new Array<Node<K,V>>(); + traverseToMin(root); + curr = fringe.pop(); + } + + public inline function hasNext() :Bool + { + return curr != null; + } + + public function next() :Node<K,V> + { + if( !hasNext() ) + { + throw new NoSuchElement(); + } + var ret = curr; + + if( fringe.length > 0 ) + { + curr = fringe.pop(); + traverseToMin(curr.right); + } + else + { + curr = null; + } + + return ret; + } + + private function traverseToMin( n :Node<K,V> ) + { + while( n != null ) + { + fringe.push(n); + n = n.left; + } + } +} + +---tokens--- +'package' Keyword.Namespace +' ' Text +'util' Name.Namespace +';' Punctuation +'\n\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Map' Name.Namespace +';' Punctuation +'\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Collection' Name.Namespace +';' Punctuation +'\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Set' Name.Namespace +';' Punctuation +'\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Option' Name.Namespace +';' Punctuation +'\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Debug' Name.Namespace +';' Punctuation +'\n' Text + +'import' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'Throwable' Name.Namespace +';' Punctuation +'\n\n' Text + +'using' Keyword.Namespace +' ' Text +'util' Name.Namespace +'.' Punctuation +'StringFormat' Name.Namespace +';' Punctuation +'\n\n' Text + +'/**\n * An ordered map of (key,value) pairs. The key ordering is defined by\n * a comparison function specified at construction. Duplicate keys\n * are not allowed.\n *\n * Worst Case Time and Space Complexities:\n * [operation] [time] [space]\n * insert O(lg(n)) O(lg(n))\n * find O(lg(n)) O(1)\n * delete O(lg(n)) O(lg(n))\n * range-query O(lg(n))* O(lg(n))\n * iteration O(n)** O(lg(n))\n * *range-query returns an iterator over elements in the range\n * **total cost of iterating over the entire map\n *\n * The map is backed by a Left-Leaning Red-Black 2-3 Tree\n * adapted from Robert Sedgewick (2008) (http://www.cs.princeton.edu/~rs/)\n *\n * Implementation choices (let size of tree be n)\n * - Parent Pointers\n * - This implementation omits parent pointers.\n * - Omitting parent pointers saves n words of persistent memory\n * at the expense of lg(n) stack space per operation.\n * - Without parent pointers, most operations in the tree must\n * either use recursion, or simulate recursion by saving a history\n * of nodes via a stack. For example, each iterator will require\n * lg(n) extra space to track progress through the tree. Insertions\n * and deletions into the tree will also invalidate any existing\n * iterators.\n * - Node Size Information\n * - This implementation omits the size of each node.\n * - Omitting size information saves n words of long-term memory at\n * the expense of not providing a find-kth operation.\n * - This seems like a reasonable trade-off as range queries are\n * generally more common than find-kth operations. The implementation\n * used below could easily be modified to provide a version with\n * size information should find-kth be of specific interest.\n * - Recursive vs. Iterative\n * - This implementation uses recursive algorithms.\n * - The recursive implementations allow the code to remain compact and\n * understandable. Since the height of LLRB 2-3 Trees is gaurenteed\n * to be at most 2lg(n), stack overflow is typically not a concern.\n * Unlike the standard single-rotation red-black algorithm, LLRB\n * operations are not tail-recursive, so even an iterative\n * version will require lg(n) extra memory.\n */' Comment.Multiline +'\n' Text + +'class' Keyword.Declaration +' ' Text +'OrderedMap' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'\n' Text + +'{' Punctuation +'\n ' Text +'private' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'root' Text +' ' Text +':' Punctuation +'Null' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +';' Punctuation +'\n ' Text +'private' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'nodeCount' Text +' ' Text +':' Punctuation +'Int' Name +';' Punctuation +'\n ' Text +'private' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'comp' Text +' ' Text +':' Punctuation +'K' Name +' ' Text +'->' Punctuation +' ' Text +'K' Name +' ' Text +'->' Punctuation +' ' Text +'Int' Name +';' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'new' Name.Function +'(' Punctuation +' ' Text +'keyComp' Name +' ' Text +':' Punctuation +'K' Name +' ' Text +'->' Punctuation +' ' Text +'K' Name +' ' Text +'->' Punctuation +' ' Text +'Int' Name +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'root' Name +' ' Text +'=' Operator +' ' Text +'null' Keyword.Constant +';' Punctuation +'\n ' Text +'comp' Name +' ' Text +'=' Operator +' ' Text +'keyComp' Name +';' Punctuation +'\n ' Text +'nodeCount' Name +' ' Text +'=' Operator +' ' Text +'0' Literal.Number.Integer +';' Punctuation +'\n ' Text +'assertInvariants' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/**\n * @returns Some(v) if (\\key,v) is in the map, None otherwise.\n */' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'get' Name.Function +'(' Punctuation +'key' Name +' ' Text +':' Punctuation +'K' Name +')' Punctuation +' ' Text +':' Punctuation +'Option' Name +'<' Punctuation +'V' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//normal BST search' Comment.Single +'\n ' Text +'var' Keyword.Declaration +' ' Text +'n' Text +' ' Text +'=' Operator +' ' Text +'root' Name +';' Punctuation +'\n ' Text +'while' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'cmp' Text +' ' Text +'=' Operator +' ' Text +'comp' Name +'(' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'cmp' Name +' ' Text +'<' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'left' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +' ' Text +'if' Keyword +' ' Text +'(' Punctuation +' ' Text +'cmp' Name +' ' Text +'>' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'right' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'Some' Name +'(' Punctuation +'n' Name +'.' Punctuation +'val' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'None' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/**\n * Puts (\\key,\\val) into the map or replaces the current value of \\key\n * with \\val.\n *\n * @return None if \\key currently is not in the map, or Some(v) if (\\key,v)\n * was in the map before the put operation.\n */' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'set' Name.Function +'(' Punctuation +'key' Name +' ' Text +':' Punctuation +'K' Name +',' Punctuation +' ' Text +'val' Name +' ' Text +':' Punctuation +'V' Name +')' Punctuation +' ' Text +':' Punctuation +'Option' Name +'<' Punctuation +'V' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'ret' Text +' ' Text +'=' Operator +' ' Text +'new' Keyword +' ' Text +'Ref' Name +'<' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n ' Text +'root' Name +' ' Text +'=' Operator +' ' Text +'insertNode' Name +'(' Punctuation +'root' Name +',' Punctuation +'key' Name +',' Punctuation +'val' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'root' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'black' Name +';' Punctuation +'\n\n ' Text +'assertInvariants' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'ret' Name +'.' Punctuation +'r' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'None' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'Some' Name +'(' Punctuation +'ret' Name +'.' Punctuation +'r' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'insertNode' Name.Function +'(' Punctuation +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +',' Punctuation +' ' Text +'key' Name +' ' Text +':' Punctuation +'K' Name +',' Punctuation +' ' Text +'val' Name +' ' Text +':' Punctuation +'V' Name +',' Punctuation +' ' Text +'ret' Name +' ' Text +':' Punctuation +'Ref' Name +'<' Punctuation +'V' Name +'>' Punctuation +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//do the insertion at the leaf level' Comment.Single +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'++' Operator +'nodeCount' Name +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'new' Keyword +' ' Text +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +'key' Name +',' Punctuation +'val' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'//normal BST search' Comment.Single +'\n ' Text +'var' Keyword.Declaration +' ' Text +'cmp' Text +' ' Text +'=' Operator +' ' Text +'comp' Name +'(' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'cmp' Name +' ' Text +'<' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'=' Operator +' ' Text +'insertNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +',' Punctuation +'key' Name +',' Punctuation +'val' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +' ' Text +'if' Keyword +'(' Punctuation +' ' Text +'cmp' Name +' ' Text +'>' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'insertNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +',' Punctuation +'key' Name +',' Punctuation +'val' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +'\n ' Text +'{' Punctuation +'\n ' Text +'//the key is already in the map, update the value' Comment.Single +'\n ' Text +'ret' Name +'.' Punctuation +'r' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'val' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'val' Name +' ' Text +'=' Operator +' ' Text +'val' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'fixInvariants' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +"/**\n * Removes (\\key,v) from the map if it exists.\n *\n * @return None if (\\key,v) wasn't in the map, Some(v) otherwise.\n */" Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'remove' Name.Function +'(' Punctuation +'key' Name +' ' Text +':' Punctuation +'K' Name +')' Punctuation +' ' Text +':' Punctuation +'Option' Name +'<' Punctuation +'V' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'ret' Text +' ' Text +'=' Operator +' ' Text +'new' Keyword +' ' Text +'Ref' Name +'<' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'root' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'root' Name +' ' Text +'=' Operator +' ' Text +'deleteNode' Name +'(' Punctuation +'root' Name +',' Punctuation +'key' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'root' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'root' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'black' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'assertInvariants' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'ret' Name +'.' Punctuation +'r' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'None' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'Some' Name +'(' Punctuation +'ret' Name +'.' Punctuation +'r' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'deleteNode' Name.Function +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +',' Punctuation +' ' Text +'key' Name +' ' Text +':' Punctuation +'K' Name +',' Punctuation +' ' Text +'ret' Name +' ' Text +':' Punctuation +'Ref' Name +'<' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'comp' Name +'(' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +' ' Text +'<' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//ensure we move into a 3-node' Comment.Single +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'moveRedLeft' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'=' Operator +' ' Text +'deleteNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +',' Punctuation +'key' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//ensure we move into a 3-node' Comment.Single +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'rotateRight' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'comp' Name +'(' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +' ' Text +'==' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +'&&' Operator +' ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//delete the node' Comment.Single +'\n ' Text +'ret' Name +'.' Punctuation +'r' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'val' Name +';' Punctuation +'\n ' Text +'--' Operator +'nodeCount' Name +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'null' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//ensure we move into a 3-node' Comment.Single +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'moveRedRight' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'comp' Name +'(' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +' ' Text +'==' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n\n ' Text +'ret' Name +'.' Punctuation +'r' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'val' Name +';' Punctuation +'\n\n ' Text +'//ensure we are deleting a node with at most one child' Comment.Single +'\n ' Text +'var' Keyword.Declaration +' ' Text +'min' Text +' ' Text +'=' Operator +' ' Text +'minNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'val' Name +' ' Text +'=' Operator +' ' Text +'min' Name +'.' Punctuation +'val' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'key' Name +' ' Text +'=' Operator +' ' Text +'min' Name +'.' Punctuation +'key' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'deleteMinNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'deleteNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +',' Punctuation +'key' Name +',' Punctuation +'ret' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'fixInvariants' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/** returns a view of the set of keys in this TreeMap **/' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'keys' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'SetView' Name +'<' Punctuation +'K' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'_this' Text +' ' Text +'=' Operator +' ' Text +'this' Keyword +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'{' Punctuation +'\n ' Text +'size' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'_this' Name +'.' Punctuation +'size' Name +'(' Punctuation +')' Punctuation +',' Punctuation +'\n ' Text +'iterator' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'IterTools' Name +'.' Punctuation +'mapIter' Name +'(' Punctuation +'new' Keyword +' ' Text +'NodeIterator' Name +'(' Punctuation +'_this' Name +'.' Punctuation +'root' Name +')' Punctuation +',' Punctuation +'function' Keyword.Declaration +'(' Punctuation +'x' Name +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'x' Name +'.' Punctuation +'key' Name +')' Punctuation +',' Punctuation +'\n ' Text +'exists' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +'x' Name +')' Punctuation +' ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'switch' Keyword +'(' Punctuation +'_this' Name +'.' Punctuation +'get' Name +'(' Punctuation +'x' Name +')' Punctuation +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'None' Name +':' Punctuation +' ' Text +'' Keyword +'false' Keyword.Constant +';' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'Some' Name +'(' Punctuation +'_' Name +')' Punctuation +':' Punctuation +' ' Text +'' Keyword +'true' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +',' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/** returns a view of the collection of values in this TreeMap **/' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'values' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'CollectionView' Name +'<' Punctuation +'V' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'_this' Text +' ' Text +'=' Operator +' ' Text +'this' Keyword +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'{' Punctuation +'\n ' Text +'size' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'_this' Name +'.' Punctuation +'size' Name +'(' Punctuation +')' Punctuation +',' Punctuation +'\n ' Text +'iterator' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'IterTools' Name +'.' Punctuation +'mapIter' Name +'(' Punctuation +'new' Keyword +' ' Text +'NodeIterator' Name +'(' Punctuation +'_this' Name +'.' Punctuation +'root' Name +')' Punctuation +',' Punctuation +'function' Keyword.Declaration +'(' Punctuation +'x' Name +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'x' Name +'.' Punctuation +'val' Name +')' Punctuation +',' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/** returns a view of the (key,value) pairs in this TreeMap **/' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'entries' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'CollectionView' Name +'<' Punctuation +'Entry' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'_this' Text +' ' Text +'=' Operator +' ' Text +'this' Keyword +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'{' Punctuation +'\n ' Text +'size' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'_this' Name +'.' Punctuation +'size' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +',' Punctuation +'\n ' Text +'iterator' Name +':' Punctuation +' ' Text +'function' Keyword.Declaration +'(' Punctuation +')' Punctuation +' ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'cast' Keyword +' ' Text +'new' Keyword +' ' Text +'NodeIterator' Name +'(' Punctuation +'_this' Name +'.' Punctuation +'root' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +',' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/** returns the number of (key,value) pairs in the map **/' Comment.Multiline +'\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'size' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'Int' Name +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'nodeCount' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'toString' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'String' Name +'\n ' Text +'{' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'sb' Text +' ' Text +'=' Operator +' ' Text +'new' Keyword +' ' Text +'StringBuf' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n\n ' Text +'sb' Name +'.' Punctuation +'add' Name +'(' Punctuation +'"' Literal.String.Double +'{' Literal.String.Double +'"' Literal.String.Double +')' Punctuation +';' Punctuation +'\n ' Text +'for' Keyword +'(' Punctuation +' ' Text +'entry' Name +' ' Text +'in' Keyword +' ' Text +'this' Keyword +'.' Punctuation +'entries' Name +'(' Punctuation +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'sb' Name +'.' Punctuation +'add' Name +'(' Punctuation +'"' Literal.String.Double +'%' Literal.String.Double +'y' Literal.String.Double +' ' Literal.String.Double +'=' Literal.String.Double +'>' Literal.String.Double +' ' Literal.String.Double +'%' Literal.String.Double +'y' Literal.String.Double +',' Literal.String.Double +' ' Literal.String.Double +'"' Literal.String.Double +'.' Punctuation +'sprintf' Name +'(' Punctuation +'[' Punctuation +'entry' Name +'.' Punctuation +'key' Name +',' Punctuation +'entry' Name +'.' Punctuation +'val' Name +']' Punctuation +')' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'sb' Name +'.' Punctuation +'add' Name +'(' Punctuation +'"' Literal.String.Double +'}' Literal.String.Double +'"' Literal.String.Double +')' Punctuation +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'sb' Name +'.' Punctuation +'toString' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'isRed' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +' ' Text +'return' Keyword +' ' Text +'false' Keyword.Constant +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'switch' Keyword +'(' Punctuation +'n' Name +'.' Punctuation +'color' Name +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'red' Name +':' Punctuation +' ' Text +'' Keyword +'true' Keyword.Constant +';' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'black' Name +':' Punctuation +' ' Text +'' Keyword +'false' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'inline' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'isBlack' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'!' Operator +'isRed' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'colorFlip' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'oppositeColor' Name +'(' Punctuation +'n' Name +'.' Punctuation +'color' Name +')' Punctuation +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'oppositeColor' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'color' Name +')' Punctuation +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'oppositeColor' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'color' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'inline' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'oppositeColor' Name.Function +'(' Punctuation +' ' Text +'c' Name +' ' Text +':' Punctuation +'Color' Name +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'switch' Keyword +'(' Punctuation +'c' Name +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'red' Name +':' Punctuation +' ' Text +'' Keyword +'black' Name +';' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'black' Name +':' Punctuation +' ' Text +'' Keyword +'red' Name +';' Punctuation +'\n ' Text +'}' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'rotateLeft' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n ' Text +'/*\n n x\n / \\ / \\\n a x => n c\n / \\ / \\\n b c a b\n */' Comment.Multiline +'\n ' Text +'var' Keyword.Declaration +' ' Text +'x' Text +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'right' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'x' Name +'.' Punctuation +'left' Name +';' Punctuation +'\n ' Text +'x' Name +'.' Punctuation +'left' Name +' ' Text +'=' Operator +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'x' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'color' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'red' Name +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'x' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'rotateRight' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +';' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +';' Punctuation +'\n ' Text +'/*\n n x\n / \\ / \\\n x c => a n\n / \\ / \\\n a b b c\n */' Comment.Multiline +'\n ' Text +'var' Keyword.Declaration +' ' Text +'x' Text +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'left' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'=' Operator +' ' Text +'x' Name +'.' Punctuation +'right' Name +';' Punctuation +'\n ' Text +'x' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'x' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'color' Name +';' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'color' Name +' ' Text +'=' Operator +' ' Text +'red' Name +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'x' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'moveRedLeft' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//borrow extra node from right child (which is a 3-node)' Comment.Single +'\n ' Text +'colorFlip' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'=' Operator +' ' Text +'rotateRight' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +';' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'rotateLeft' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'colorFlip' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'moveRedRight' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//borrow extra node from left child (which is a 3-node)' Comment.Single +'\n ' Text +'colorFlip' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'rotateRight' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'colorFlip' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'fixInvariants' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//ensure left-leaning property' Comment.Single +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'rotateLeft' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//balance 4-node' Comment.Single +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'rotateRight' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isRed' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//split 4-node' Comment.Single +'\n ' Text +'colorFlip' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'deleteMinNode' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'//delete' Comment.Single +'\n ' Text +'--' Operator +'nodeCount' Name +';' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'null' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +'&&' Operator +' ' Text +'isBlack' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'left' Name +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'moveRedLeft' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'=' Operator +' ' Text +'deleteMinNode' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'fixInvariants' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'minNode' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n\n ' Text +'while' Keyword +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'left' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'maxNode' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +')' Punctuation +';' Punctuation +'\n\n ' Text +'while' Keyword +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'right' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'n' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'/** Used to verify that the invariants of the tree hold **/' Comment.Multiline +'\n ' Text +'private' Keyword.Declaration +' ' Text +'inline' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'assertInvariants' Name.Function +'(' Punctuation +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'#if' Comment.Preproc +' ' Comment.Preproc +'DEBUG' Comment.Preproc +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'isBlack' Name +'(' Punctuation +'root' Name +')' Punctuation +',' Punctuation +' ' Text +'"' Literal.String.Double +'r' Literal.String.Double +'o' Literal.String.Double +'o' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'i' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'b' Literal.String.Double +'l' Literal.String.Double +'a' Literal.String.Double +'c' Literal.String.Double +'k' Literal.String.Double +':' Literal.String.Double +' ' Literal.String.Double +'"' Literal.String.Double +' ' Text +'+' Operator +' ' Text +'root' Name +' ' Text +')' Punctuation +';' Punctuation +'\n\n ' Text +'assertIsTree' Name +'(' Punctuation +'root' Name +',' Punctuation +'new' Keyword +' ' Text +'List' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +'(' Punctuation +')' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'assertBlackNodeCount' Name +'(' Punctuation +'root' Name +')' Punctuation +';' Punctuation +'\n ' Text +'assertBSTOrdering' Name +'(' Punctuation +'root' Name +',' Punctuation +'comp' Name +')' Punctuation +';' Punctuation +'\n ' Text +'#end' Comment.Preproc +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'assertIsTree' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +':' Punctuation +' ' Text +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +',' Punctuation +' ' Text +'visited' Name +' ' Text +':' Punctuation +'List' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'for' Keyword +'(' Punctuation +' ' Text +'r' Name +' ' Text +'in' Keyword +' ' Text +'visited' Name +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'n' Name +' ' Text +'!=' Operator +' ' Text +'r' Name +' ' Text +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'visited' Name +'.' Punctuation +'push' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'assertIsTree' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +',' Punctuation +'visited' Name +')' Punctuation +';' Punctuation +'\n ' Text +'assertIsTree' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +',' Punctuation +'visited' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'assertBlackNodeCount' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +':' Punctuation +' ' Text +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +' ' Text +':' Punctuation +'Int' Name +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'1' Literal.Number.Integer +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'var' Keyword.Declaration +' ' Text +'leftCount' Text +' ' Text +'=' Operator +' ' Text +'assertBlackNodeCount' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +')' Punctuation +';' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'rightCount' Text +' ' Text +'=' Operator +' ' Text +'assertBlackNodeCount' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +')' Punctuation +';' Punctuation +'\n\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +'\n ' Text +'leftCount' Name +' ' Text +'==' Operator +' ' Text +'rightCount' Name +',' Punctuation +'\n ' Text +'"' Literal.String.Double +'n' Literal.String.Double +'u' Literal.String.Double +'m' Literal.String.Double +' ' Literal.String.Double +'o' Literal.String.Double +'f' Literal.String.Double +' ' Literal.String.Double +'b' Literal.String.Double +'l' Literal.String.Double +'a' Literal.String.Double +'c' Literal.String.Double +'k' Literal.String.Double +' ' Literal.String.Double +'n' Literal.String.Double +'o' Literal.String.Double +'d' Literal.String.Double +'e' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'i' Literal.String.Double +'n' Literal.String.Double +' ' Literal.String.Double +'a' Literal.String.Double +'l' Literal.String.Double +'l' Literal.String.Double +' ' Literal.String.Double +'p' Literal.String.Double +'a' Literal.String.Double +'t' Literal.String.Double +'h' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'f' Literal.String.Double +'o' Literal.String.Double +'r' Literal.String.Double +' ' Literal.String.Double +'l' Literal.String.Double +'e' Literal.String.Double +'f' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'a' Literal.String.Double +'n' Literal.String.Double +'d' Literal.String.Double +' ' Literal.String.Double +'r' Literal.String.Double +'i' Literal.String.Double +'g' Literal.String.Double +'h' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'c' Literal.String.Double +'h' Literal.String.Double +'i' Literal.String.Double +'l' Literal.String.Double +'d' Literal.String.Double +' ' Literal.String.Double +'n' Literal.String.Double +'o' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'e' Literal.String.Double +'q' Literal.String.Double +'u' Literal.String.Double +'a' Literal.String.Double +'l' Literal.String.Double +'"' Literal.String.Double +' ' Text +'+' Operator +' ' Text +'n' Name +'\n ' Text +')' Punctuation +';' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'leftCount' Name +' ' Text +'+' Operator +' ' Text +'switch' Keyword +'(' Punctuation +'n' Name +'.' Punctuation +'color' Name +')' Punctuation +' ' Text +'{' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'red' Name +':' Punctuation +' ' Text +'' Keyword +'0' Literal.Number.Integer +';' Punctuation +'\n ' Text +'case' Keyword +' ' Text +'black' Name +':' Punctuation +' ' Text +'' Keyword +'1' Literal.Number.Integer +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'static' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'assertBSTOrdering' Name.Function +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'(' Punctuation +' ' Text +'n' Name +':' Punctuation +' ' Text +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +',' Punctuation +' ' Text +'compK' Name +' ' Text +':' Punctuation +'K' Name +' ' Text +'->' Punctuation +' ' Text +'K' Name +' ' Text +'->' Punctuation +' ' Text +'Int' Name +' ' Text +')' Punctuation +' ' Text +':' Punctuation +'Void' Name +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'==' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'left' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +'&&' Operator +' ' Text +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'val' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'compK' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +'.' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'key' Name +')' Punctuation +' ' Text +'<' Operator +' ' Text +'0' Literal.Number.Integer +',' Punctuation +' ' Text +'"' Literal.String.Double +'l' Literal.String.Double +'e' Literal.String.Double +'f' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'c' Literal.String.Double +'h' Literal.String.Double +'i' Literal.String.Double +'l' Literal.String.Double +'d' Literal.String.Double +' ' Literal.String.Double +'n' Literal.String.Double +'o' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'l' Literal.String.Double +'e' Literal.String.Double +'s' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'t' Literal.String.Double +'h' Literal.String.Double +'a' Literal.String.Double +'n' Literal.String.Double +' ' Literal.String.Double +'i' Literal.String.Double +'t' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'p' Literal.String.Double +'a' Literal.String.Double +'r' Literal.String.Double +'e' Literal.String.Double +'n' Literal.String.Double +'t' Literal.String.Double +'"' Literal.String.Double +' ' Text +'+' Operator +' ' Text +'n' Name +' ' Text +')' Punctuation +';' Punctuation +'\n ' Text +'assertBSTOrdering' Name +'(' Punctuation +'n' Name +'.' Punctuation +'left' Name +',' Punctuation +'compK' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'n' Name +'.' Punctuation +'right' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +'&&' Operator +' ' Text +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'val' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'Debug' Name +'.' Punctuation +'assert' Name +'(' Punctuation +' ' Text +'compK' Name +'(' Punctuation +'n' Name +'.' Punctuation +'key' Name +',' Punctuation +'n' Name +'.' Punctuation +'right' Name +'.' Punctuation +'key' Name +')' Punctuation +' ' Text +'<' Operator +' ' Text +'0' Literal.Number.Integer +',' Punctuation +' ' Text +'"' Literal.String.Double +'p' Literal.String.Double +'a' Literal.String.Double +'r' Literal.String.Double +'e' Literal.String.Double +'n' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'n' Literal.String.Double +'o' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'l' Literal.String.Double +'e' Literal.String.Double +'s' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'t' Literal.String.Double +'h' Literal.String.Double +'a' Literal.String.Double +'n' Literal.String.Double +' ' Literal.String.Double +'i' Literal.String.Double +'t' Literal.String.Double +'s' Literal.String.Double +' ' Literal.String.Double +'r' Literal.String.Double +'i' Literal.String.Double +'g' Literal.String.Double +'h' Literal.String.Double +'t' Literal.String.Double +' ' Literal.String.Double +'c' Literal.String.Double +'h' Literal.String.Double +'i' Literal.String.Double +'l' Literal.String.Double +'d' Literal.String.Double +'"' Literal.String.Double +' ' Text +'+' Operator +' ' Text +'n' Name +' ' Text +')' Punctuation +';' Punctuation +'\n ' Text +'assertBSTOrdering' Name +'(' Punctuation +'n' Name +'.' Punctuation +'right' Name +',' Punctuation +'compK' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n' Text + +'}' Punctuation +'\n\n' Text + +'private' Keyword.Declaration +' ' Text +'enum' Keyword.Declaration +' ' Text +'Color' Name +'\n' Text + +'{' Punctuation +'\n ' Text +'red' Name +';' Punctuation +'\n ' Text +'black' Name +';' Punctuation +'\n' Text + +'}' Punctuation +'\n\n' Text + +'private' Keyword.Declaration +' ' Text +'class' Keyword.Declaration +' ' Text +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +'/*implements Entry<K,V>*/' Comment.Multiline +'\n' Text + +'{' Punctuation +'\n ' Text +'public' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'left' Text +' ' Text +':' Punctuation +'Null' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +';' Punctuation +'\n ' Text +'public' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'right' Text +' ' Text +':' Punctuation +'Null' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +';' Punctuation +'\n ' Text +'public' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'color' Text +' ' Text +':' Punctuation +'Color' Name +';' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'key' Text +' ' Text +':' Punctuation +'K' Name +';' Punctuation +'\n ' Text +'public' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'val' Text +' ' Text +':' Punctuation +'V' Name +';' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'new' Name.Function +'(' Punctuation +'k' Name +' ' Text +':' Punctuation +'K' Name +',' Punctuation +' ' Text +'v' Name +' ' Text +':' Punctuation +'V' Name +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'key' Name +' ' Text +'=' Operator +' ' Text +'k' Name +';' Punctuation +'\n ' Text +'val' Name +' ' Text +'=' Operator +' ' Text +'v' Name +';' Punctuation +'\n ' Text +'color' Name +' ' Text +'=' Operator +' ' Text +'red' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n' Text + +'}' Punctuation +'\n\n' Text + +'private' Keyword.Declaration +' ' Text +'class' Keyword.Declaration +' ' Text +'NodeIterator' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'\n' Text + +'{' Punctuation +'\n ' Text +'private' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'curr' Text +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +';' Punctuation +'\n ' Text +'private' Keyword.Declaration +' ' Text +'var' Keyword.Declaration +' ' Text +'fringe' Text +' ' Text +':' Punctuation +'Array' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +';' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'new' Name.Function +'(' Punctuation +' ' Text +'root' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'fringe' Name +' ' Text +'=' Operator +' ' Text +'new' Keyword +' ' Text +'Array' Name +'<' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'>' Punctuation +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'traverseToMin' Name +'(' Punctuation +'root' Name +')' Punctuation +';' Punctuation +'\n ' Text +'curr' Name +' ' Text +'=' Operator +' ' Text +'fringe' Name +'.' Punctuation +'pop' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'inline' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'hasNext' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'Bool' Name +'\n ' Text +'{' Punctuation +'\n ' Text +'return' Keyword +' ' Text +'curr' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'public' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'next' Name.Function +'(' Punctuation +')' Punctuation +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'!' Operator +'hasNext' Name +'(' Punctuation +')' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'throw' Keyword +' ' Text +'new' Keyword +' ' Text +'NoSuchElement' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'var' Keyword.Declaration +' ' Text +'ret' Text +' ' Text +'=' Operator +' ' Text +'curr' Name +';' Punctuation +'\n\n ' Text +'if' Keyword +'(' Punctuation +' ' Text +'fringe' Name +'.' Punctuation +'length' Name +' ' Text +'>' Operator +' ' Text +'0' Literal.Number.Integer +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'curr' Name +' ' Text +'=' Operator +' ' Text +'fringe' Name +'.' Punctuation +'pop' Name +'(' Punctuation +')' Punctuation +';' Punctuation +'\n ' Text +'traverseToMin' Name +'(' Punctuation +'curr' Name +'.' Punctuation +'right' Name +')' Punctuation +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'else' Keyword +'\n ' Text +'{' Punctuation +'\n ' Text +'curr' Name +' ' Text +'=' Operator +' ' Text +'null' Keyword.Constant +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'return' Keyword +' ' Text +'ret' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n\n ' Text +'private' Keyword.Declaration +' ' Text +'function' Keyword.Declaration +' ' Text +'traverseToMin' Name.Function +'(' Punctuation +' ' Text +'n' Name +' ' Text +':' Punctuation +'Node' Name +'<' Punctuation +'K' Name +',' Punctuation +'V' Name +'>' Punctuation +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'while' Keyword +'(' Punctuation +' ' Text +'n' Name +' ' Text +'!=' Operator +' ' Text +'null' Keyword.Constant +' ' Text +')' Punctuation +'\n ' Text +'{' Punctuation +'\n ' Text +'fringe' Name +'.' Punctuation +'push' Name +'(' Punctuation +'n' Name +')' Punctuation +';' Punctuation +'\n ' Text +'n' Name +' ' Text +'=' Operator +' ' Text +'n' Name +'.' Punctuation +'left' Name +';' Punctuation +'\n ' Text +'}' Punctuation +'\n ' Text +'}' Punctuation +'\n' Text + +'}' Punctuation +'\n' Text |