.config/coc/extensions/node_modules/coc-prettier/node_modules/functional-red-black-tree/rbtree.js

   1 "use strict"
   2
   3 module.exports = createRBTree
   4
   5 var RED   = 0
   6 var BLACK = 1
   7
   8 function RBNode(color, key, value, left, right, count) {
   9   this._color = color
  10   this.key = key
  11   this.value = value
  12   this.left = left
  13   this.right = right
  14   this._count = count
  15 }
  16
  17 function cloneNode(node) {
  18   return new RBNode(node._color, node.key, node.value, node.left, node.right, node._count)
  19 }
  20
  21 function repaint(color, node) {
  22   return new RBNode(color, node.key, node.value, node.left, node.right, node._count)
  23 }
  24
  25 function recount(node) {
  26   node._count = 1 + (node.left ? node.left._count : 0) + (node.right ? node.right._count : 0)
  27 }
  28
  29 function RedBlackTree(compare, root) {
  30   this._compare = compare
  31   this.root = root
  32 }
  33
  34 var proto = RedBlackTree.prototype
  35
  36 Object.defineProperty(proto, "keys", {
  37   get: function() {
  38     var result = []
  39     this.forEach(function(k,v) {
  40       result.push(k)
  41     })
  42     return result
  43   }
  44 })
  45
  46 Object.defineProperty(proto, "values", {
  47   get: function() {
  48     var result = []
  49     this.forEach(function(k,v) {
  50       result.push(v)
  51     })
  52     return result
  53   }
  54 })
  55
  56 //Returns the number of nodes in the tree
  57 Object.defineProperty(proto, "length", {
  58   get: function() {
  59     if(this.root) {
  60       return this.root._count
  61     }
  62     return 0
  63   }
  64 })
  65
  66 //Insert a new item into the tree
  67 proto.insert = function(key, value) {
  68   var cmp = this._compare
  69   //Find point to insert new node at
  70   var n = this.root
  71   var n_stack = []
  72   var d_stack = []
  73   while(n) {
  74     var d = cmp(key, n.key)
  75     n_stack.push(n)
  76     d_stack.push(d)
  77     if(d <= 0) {
  78       n = n.left
  79     } else {
  80       n = n.right
  81     }
  82   }
  83   //Rebuild path to leaf node
  84   n_stack.push(new RBNode(RED, key, value, null, null, 1))
  85   for(var s=n_stack.length-2; s>=0; --s) {
  86     var n = n_stack[s]
  87     if(d_stack[s] <= 0) {
  88       n_stack[s] = new RBNode(n._color, n.key, n.value, n_stack[s+1], n.right, n._count+1)
  89     } else {
  90       n_stack[s] = new RBNode(n._color, n.key, n.value, n.left, n_stack[s+1], n._count+1)
  91     }
  92   }
  93   //Rebalance tree using rotations
  94   //console.log("start insert", key, d_stack)
  95   for(var s=n_stack.length-1; s>1; --s) {
  96     var p = n_stack[s-1]
  97     var n = n_stack[s]
  98     if(p._color === BLACK || n._color === BLACK) {
  99       break
 100     }
 101     var pp = n_stack[s-2]
 102     if(pp.left === p) {
 103       if(p.left === n) {
 104         var y = pp.right
 105         if(y && y._color === RED) {
 106           //console.log("LLr")
 107           p._color = BLACK
 108           pp.right = repaint(BLACK, y)
 109           pp._color = RED
 110           s -= 1
 111         } else {
 112           //console.log("LLb")
 113           pp._color = RED
 114           pp.left = p.right
 115           p._color = BLACK
 116           p.right = pp
 117           n_stack[s-2] = p
 118           n_stack[s-1] = n
 119           recount(pp)
 120           recount(p)
 121           if(s >= 3) {
 122             var ppp = n_stack[s-3]
 123             if(ppp.left === pp) {
 124               ppp.left = p
 125             } else {
 126               ppp.right = p
 127             }
 128           }
 129           break
 130         }
 131       } else {
 132         var y = pp.right
 133         if(y && y._color === RED) {
 134           //console.log("LRr")
 135           p._color = BLACK
 136           pp.right = repaint(BLACK, y)
 137           pp._color = RED
 138           s -= 1
 139         } else {
 140           //console.log("LRb")
 141           p.right = n.left
 142           pp._color = RED
 143           pp.left = n.right
 144           n._color = BLACK
 145           n.left = p
 146           n.right = pp
 147           n_stack[s-2] = n
 148           n_stack[s-1] = p
 149           recount(pp)
 150           recount(p)
 151           recount(n)
 152           if(s >= 3) {
 153             var ppp = n_stack[s-3]
 154             if(ppp.left === pp) {
 155               ppp.left = n
 156             } else {
 157               ppp.right = n
 158             }
 159           }
 160           break
 161         }
 162       }
 163     } else {
 164       if(p.right === n) {
 165         var y = pp.left
 166         if(y && y._color === RED) {
 167           //console.log("RRr", y.key)
 168           p._color = BLACK
 169           pp.left = repaint(BLACK, y)
 170           pp._color = RED
 171           s -= 1
 172         } else {
 173           //console.log("RRb")
 174           pp._color = RED
 175           pp.right = p.left
 176           p._color = BLACK
 177           p.left = pp
 178           n_stack[s-2] = p
 179           n_stack[s-1] = n
 180           recount(pp)
 181           recount(p)
 182           if(s >= 3) {
 183             var ppp = n_stack[s-3]
 184             if(ppp.right === pp) {
 185               ppp.right = p
 186             } else {
 187               ppp.left = p
 188             }
 189           }
 190           break
 191         }
 192       } else {
 193         var y = pp.left
 194         if(y && y._color === RED) {
 195           //console.log("RLr")
 196           p._color = BLACK
 197           pp.left = repaint(BLACK, y)
 198           pp._color = RED
 199           s -= 1
 200         } else {
 201           //console.log("RLb")
 202           p.left = n.right
 203           pp._color = RED
 204           pp.right = n.left
 205           n._color = BLACK
 206           n.right = p
 207           n.left = pp
 208           n_stack[s-2] = n
 209           n_stack[s-1] = p
 210           recount(pp)
 211           recount(p)
 212           recount(n)
 213           if(s >= 3) {
 214             var ppp = n_stack[s-3]
 215             if(ppp.right === pp) {
 216               ppp.right = n
 217             } else {
 218               ppp.left = n
 219             }
 220           }
 221           break
 222         }
 223       }
 224     }
 225   }
 226   //Return new tree
 227   n_stack[0]._color = BLACK
 228   return new RedBlackTree(cmp, n_stack[0])
 229 }
 230
 231
 232 //Visit all nodes inorder
 233 function doVisitFull(visit, node) {
 234   if(node.left) {
 235     var v = doVisitFull(visit, node.left)
 236     if(v) { return v }
 237   }
 238   var v = visit(node.key, node.value)
 239   if(v) { return v }
 240   if(node.right) {
 241     return doVisitFull(visit, node.right)
 242   }
 243 }
 244
 245 //Visit half nodes in order
 246 function doVisitHalf(lo, compare, visit, node) {
 247   var l = compare(lo, node.key)
 248   if(l <= 0) {
 249     if(node.left) {
 250       var v = doVisitHalf(lo, compare, visit, node.left)
 251       if(v) { return v }
 252     }
 253     var v = visit(node.key, node.value)
 254     if(v) { return v }
 255   }
 256   if(node.right) {
 257     return doVisitHalf(lo, compare, visit, node.right)
 258   }
 259 }
 260
 261 //Visit all nodes within a range
 262 function doVisit(lo, hi, compare, visit, node) {
 263   var l = compare(lo, node.key)
 264   var h = compare(hi, node.key)
 265   var v
 266   if(l <= 0) {
 267     if(node.left) {
 268       v = doVisit(lo, hi, compare, visit, node.left)
 269       if(v) { return v }
 270     }
 271     if(h > 0) {
 272       v = visit(node.key, node.value)
 273       if(v) { return v }
 274     }
 275   }
 276   if(h > 0 && node.right) {
 277     return doVisit(lo, hi, compare, visit, node.right)
 278   }
 279 }
 280
 281
 282 proto.forEach = function rbTreeForEach(visit, lo, hi) {
 283   if(!this.root) {
 284     return
 285   }
 286   switch(arguments.length) {
 287     case 1:
 288       return doVisitFull(visit, this.root)
 289     break
 290
 291     case 2:
 292       return doVisitHalf(lo, this._compare, visit, this.root)
 293     break
 294
 295     case 3:
 296       if(this._compare(lo, hi) >= 0) {
 297         return
 298       }
 299       return doVisit(lo, hi, this._compare, visit, this.root)
 300     break
 301   }
 302 }
 303
 304 //First item in list
 305 Object.defineProperty(proto, "begin", {
 306   get: function() {
 307     var stack = []
 308     var n = this.root
 309     while(n) {
 310       stack.push(n)
 311       n = n.left
 312     }
 313     return new RedBlackTreeIterator(this, stack)
 314   }
 315 })
 316
 317 //Last item in list
 318 Object.defineProperty(proto, "end", {
 319   get: function() {
 320     var stack = []
 321     var n = this.root
 322     while(n) {
 323       stack.push(n)
 324       n = n.right
 325     }
 326     return new RedBlackTreeIterator(this, stack)
 327   }
 328 })
 329
 330 //Find the ith item in the tree
 331 proto.at = function(idx) {
 332   if(idx < 0) {
 333     return new RedBlackTreeIterator(this, [])
 334   }
 335   var n = this.root
 336   var stack = []
 337   while(true) {
 338     stack.push(n)
 339     if(n.left) {
 340       if(idx < n.left._count) {
 341         n = n.left
 342         continue
 343       }
 344       idx -= n.left._count
 345     }
 346     if(!idx) {
 347       return new RedBlackTreeIterator(this, stack)
 348     }
 349     idx -= 1
 350     if(n.right) {
 351       if(idx >= n.right._count) {
 352         break
 353       }
 354       n = n.right
 355     } else {
 356       break
 357     }
 358   }
 359   return new RedBlackTreeIterator(this, [])
 360 }
 361
 362 proto.ge = function(key) {
 363   var cmp = this._compare
 364   var n = this.root
 365   var stack = []
 366   var last_ptr = 0
 367   while(n) {
 368     var d = cmp(key, n.key)
 369     stack.push(n)
 370     if(d <= 0) {
 371       last_ptr = stack.length
 372     }
 373     if(d <= 0) {
 374       n = n.left
 375     } else {
 376       n = n.right
 377     }
 378   }
 379   stack.length = last_ptr
 380   return new RedBlackTreeIterator(this, stack)
 381 }
 382
 383 proto.gt = function(key) {
 384   var cmp = this._compare
 385   var n = this.root
 386   var stack = []
 387   var last_ptr = 0
 388   while(n) {
 389     var d = cmp(key, n.key)
 390     stack.push(n)
 391     if(d < 0) {
 392       last_ptr = stack.length
 393     }
 394     if(d < 0) {
 395       n = n.left
 396     } else {
 397       n = n.right
 398     }
 399   }
 400   stack.length = last_ptr
 401   return new RedBlackTreeIterator(this, stack)
 402 }
 403
 404 proto.lt = function(key) {
 405   var cmp = this._compare
 406   var n = this.root
 407   var stack = []
 408   var last_ptr = 0
 409   while(n) {
 410     var d = cmp(key, n.key)
 411     stack.push(n)
 412     if(d > 0) {
 413       last_ptr = stack.length
 414     }
 415     if(d <= 0) {
 416       n = n.left
 417     } else {
 418       n = n.right
 419     }
 420   }
 421   stack.length = last_ptr
 422   return new RedBlackTreeIterator(this, stack)
 423 }
 424
 425 proto.le = function(key) {
 426   var cmp = this._compare
 427   var n = this.root
 428   var stack = []
 429   var last_ptr = 0
 430   while(n) {
 431     var d = cmp(key, n.key)
 432     stack.push(n)
 433     if(d >= 0) {
 434       last_ptr = stack.length
 435     }
 436     if(d < 0) {
 437       n = n.left
 438     } else {
 439       n = n.right
 440     }
 441   }
 442   stack.length = last_ptr
 443   return new RedBlackTreeIterator(this, stack)
 444 }
 445
 446 //Finds the item with key if it exists
 447 proto.find = function(key) {
 448   var cmp = this._compare
 449   var n = this.root
 450   var stack = []
 451   while(n) {
 452     var d = cmp(key, n.key)
 453     stack.push(n)
 454     if(d === 0) {
 455       return new RedBlackTreeIterator(this, stack)
 456     }
 457     if(d <= 0) {
 458       n = n.left
 459     } else {
 460       n = n.right
 461     }
 462   }
 463   return new RedBlackTreeIterator(this, [])
 464 }
 465
 466 //Removes item with key from tree
 467 proto.remove = function(key) {
 468   var iter = this.find(key)
 469   if(iter) {
 470     return iter.remove()
 471   }
 472   return this
 473 }
 474
 475 //Returns the item at `key`
 476 proto.get = function(key) {
 477   var cmp = this._compare
 478   var n = this.root
 479   while(n) {
 480     var d = cmp(key, n.key)
 481     if(d === 0) {
 482       return n.value
 483     }
 484     if(d <= 0) {
 485       n = n.left
 486     } else {
 487       n = n.right
 488     }
 489   }
 490   return
 491 }
 492
 493 //Iterator for red black tree
 494 function RedBlackTreeIterator(tree, stack) {
 495   this.tree = tree
 496   this._stack = stack
 497 }
 498
 499 var iproto = RedBlackTreeIterator.prototype
 500
 501 //Test if iterator is valid
 502 Object.defineProperty(iproto, "valid", {
 503   get: function() {
 504     return this._stack.length > 0
 505   }
 506 })
 507
 508 //Node of the iterator
 509 Object.defineProperty(iproto, "node", {
 510   get: function() {
 511     if(this._stack.length > 0) {
 512       return this._stack[this._stack.length-1]
 513     }
 514     return null
 515   },
 516   enumerable: true
 517 })
 518
 519 //Makes a copy of an iterator
 520 iproto.clone = function() {
 521   return new RedBlackTreeIterator(this.tree, this._stack.slice())
 522 }
 523
 524 //Swaps two nodes
 525 function swapNode(n, v) {
 526   n.key = v.key
 527   n.value = v.value
 528   n.left = v.left
 529   n.right = v.right
 530   n._color = v._color
 531   n._count = v._count
 532 }
 533
 534 //Fix up a double black node in a tree
 535 function fixDoubleBlack(stack) {
 536   var n, p, s, z
 537   for(var i=stack.length-1; i>=0; --i) {
 538     n = stack[i]
 539     if(i === 0) {
 540       n._color = BLACK
 541       return
 542     }
 543     //console.log("visit node:", n.key, i, stack[i].key, stack[i-1].key)
 544     p = stack[i-1]
 545     if(p.left === n) {
 546       //console.log("left child")
 547       s = p.right
 548       if(s.right && s.right._color === RED) {
 549         //console.log("case 1: right sibling child red")
 550         s = p.right = cloneNode(s)
 551         z = s.right = cloneNode(s.right)
 552         p.right = s.left
 553         s.left = p
 554         s.right = z
 555         s._color = p._color
 556         n._color = BLACK
 557         p._color = BLACK
 558         z._color = BLACK
 559         recount(p)
 560         recount(s)
 561         if(i > 1) {
 562           var pp = stack[i-2]
 563           if(pp.left === p) {
 564             pp.left = s
 565           } else {
 566             pp.right = s
 567           }
 568         }
 569         stack[i-1] = s
 570         return
 571       } else if(s.left && s.left._color === RED) {
 572         //console.log("case 1: left sibling child red")
 573         s = p.right = cloneNode(s)
 574         z = s.left = cloneNode(s.left)
 575         p.right = z.left
 576         s.left = z.right
 577         z.left = p
 578         z.right = s
 579         z._color = p._color
 580         p._color = BLACK
 581         s._color = BLACK
 582         n._color = BLACK
 583         recount(p)
 584         recount(s)
 585         recount(z)
 586         if(i > 1) {
 587           var pp = stack[i-2]
 588           if(pp.left === p) {
 589             pp.left = z
 590           } else {
 591             pp.right = z
 592           }
 593         }
 594         stack[i-1] = z
 595         return
 596       }
 597       if(s._color === BLACK) {
 598         if(p._color === RED) {
 599           //console.log("case 2: black sibling, red parent", p.right.value)
 600           p._color = BLACK
 601           p.right = repaint(RED, s)
 602           return
 603         } else {
 604           //console.log("case 2: black sibling, black parent", p.right.value)
 605           p.right = repaint(RED, s)
 606           continue
 607         }
 608       } else {
 609         //console.log("case 3: red sibling")
 610         s = cloneNode(s)
 611         p.right = s.left
 612         s.left = p
 613         s._color = p._color
 614         p._color = RED
 615         recount(p)
 616         recount(s)
 617         if(i > 1) {
 618           var pp = stack[i-2]
 619           if(pp.left === p) {
 620             pp.left = s
 621           } else {
 622             pp.right = s
 623           }
 624         }
 625         stack[i-1] = s
 626         stack[i] = p
 627         if(i+1 < stack.length) {
 628           stack[i+1] = n
 629         } else {
 630           stack.push(n)
 631         }
 632         i = i+2
 633       }
 634     } else {
 635       //console.log("right child")
 636       s = p.left
 637       if(s.left && s.left._color === RED) {
 638         //console.log("case 1: left sibling child red", p.value, p._color)
 639         s = p.left = cloneNode(s)
 640         z = s.left = cloneNode(s.left)
 641         p.left = s.right
 642         s.right = p
 643         s.left = z
 644         s._color = p._color
 645         n._color = BLACK
 646         p._color = BLACK
 647         z._color = BLACK
 648         recount(p)
 649         recount(s)
 650         if(i > 1) {
 651           var pp = stack[i-2]
 652           if(pp.right === p) {
 653             pp.right = s
 654           } else {
 655             pp.left = s
 656           }
 657         }
 658         stack[i-1] = s
 659         return
 660       } else if(s.right && s.right._color === RED) {
 661         //console.log("case 1: right sibling child red")
 662         s = p.left = cloneNode(s)
 663         z = s.right = cloneNode(s.right)
 664         p.left = z.right
 665         s.right = z.left
 666         z.right = p
 667         z.left = s
 668         z._color = p._color
 669         p._color = BLACK
 670         s._color = BLACK
 671         n._color = BLACK
 672         recount(p)
 673         recount(s)
 674         recount(z)
 675         if(i > 1) {
 676           var pp = stack[i-2]
 677           if(pp.right === p) {
 678             pp.right = z
 679           } else {
 680             pp.left = z
 681           }
 682         }
 683         stack[i-1] = z
 684         return
 685       }
 686       if(s._color === BLACK) {
 687         if(p._color === RED) {
 688           //console.log("case 2: black sibling, red parent")
 689           p._color = BLACK
 690           p.left = repaint(RED, s)
 691           return
 692         } else {
 693           //console.log("case 2: black sibling, black parent")
 694           p.left = repaint(RED, s)
 695           continue
 696         }
 697       } else {
 698         //console.log("case 3: red sibling")
 699         s = cloneNode(s)
 700         p.left = s.right
 701         s.right = p
 702         s._color = p._color
 703         p._color = RED
 704         recount(p)
 705         recount(s)
 706         if(i > 1) {
 707           var pp = stack[i-2]
 708           if(pp.right === p) {
 709             pp.right = s
 710           } else {
 711             pp.left = s
 712           }
 713         }
 714         stack[i-1] = s
 715         stack[i] = p
 716         if(i+1 < stack.length) {
 717           stack[i+1] = n
 718         } else {
 719           stack.push(n)
 720         }
 721         i = i+2
 722       }
 723     }
 724   }
 725 }
 726
 727 //Removes item at iterator from tree
 728 iproto.remove = function() {
 729   var stack = this._stack
 730   if(stack.length === 0) {
 731     return this.tree
 732   }
 733   //First copy path to node
 734   var cstack = new Array(stack.length)
 735   var n = stack[stack.length-1]
 736   cstack[cstack.length-1] = new RBNode(n._color, n.key, n.value, n.left, n.right, n._count)
 737   for(var i=stack.length-2; i>=0; --i) {
 738     var n = stack[i]
 739     if(n.left === stack[i+1]) {
 740       cstack[i] = new RBNode(n._color, n.key, n.value, cstack[i+1], n.right, n._count)
 741     } else {
 742       cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count)
 743     }
 744   }
 745
 746   //Get node
 747   n = cstack[cstack.length-1]
 748   //console.log("start remove: ", n.value)
 749
 750   //If not leaf, then swap with previous node
 751   if(n.left && n.right) {
 752     //console.log("moving to leaf")
 753
 754     //First walk to previous leaf
 755     var split = cstack.length
 756     n = n.left
 757     while(n.right) {
 758       cstack.push(n)
 759       n = n.right
 760     }
 761     //Copy path to leaf
 762     var v = cstack[split-1]
 763     cstack.push(new RBNode(n._color, v.key, v.value, n.left, n.right, n._count))
 764     cstack[split-1].key = n.key
 765     cstack[split-1].value = n.value
 766
 767     //Fix up stack
 768     for(var i=cstack.length-2; i>=split; --i) {
 769       n = cstack[i]
 770       cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count)
 771     }
 772     cstack[split-1].left = cstack[split]
 773   }
 774   //console.log("stack=", cstack.map(function(v) { return v.value }))
 775
 776   //Remove leaf node
 777   n = cstack[cstack.length-1]
 778   if(n._color === RED) {
 779     //Easy case: removing red leaf
 780     //console.log("RED leaf")
 781     var p = cstack[cstack.length-2]
 782     if(p.left === n) {
 783       p.left = null
 784     } else if(p.right === n) {
 785       p.right = null
 786     }
 787     cstack.pop()
 788     for(var i=0; i<cstack.length; ++i) {
 789       cstack[i]._count--
 790     }
 791     return new RedBlackTree(this.tree._compare, cstack[0])
 792   } else {
 793     if(n.left || n.right) {
 794       //Second easy case:  Single child black parent
 795       //console.log("BLACK single child")
 796       if(n.left) {
 797         swapNode(n, n.left)
 798       } else if(n.right) {
 799         swapNode(n, n.right)
 800       }
 801       //Child must be red, so repaint it black to balance color
 802       n._color = BLACK
 803       for(var i=0; i<cstack.length-1; ++i) {
 804         cstack[i]._count--
 805       }
 806       return new RedBlackTree(this.tree._compare, cstack[0])
 807     } else if(cstack.length === 1) {
 808       //Third easy case: root
 809       //console.log("ROOT")
 810       return new RedBlackTree(this.tree._compare, null)
 811     } else {
 812       //Hard case: Repaint n, and then do some nasty stuff
 813       //console.log("BLACK leaf no children")
 814       for(var i=0; i<cstack.length; ++i) {
 815         cstack[i]._count--
 816       }
 817       var parent = cstack[cstack.length-2]
 818       fixDoubleBlack(cstack)
 819       //Fix up links
 820       if(parent.left === n) {
 821         parent.left = null
 822       } else {
 823         parent.right = null
 824       }
 825     }
 826   }
 827   return new RedBlackTree(this.tree._compare, cstack[0])
 828 }
 829
 830 //Returns key
 831 Object.defineProperty(iproto, "key", {
 832   get: function() {
 833     if(this._stack.length > 0) {
 834       return this._stack[this._stack.length-1].key
 835     }
 836     return
 837   },
 838   enumerable: true
 839 })
 840
 841 //Returns value
 842 Object.defineProperty(iproto, "value", {
 843   get: function() {
 844     if(this._stack.length > 0) {
 845       return this._stack[this._stack.length-1].value
 846     }
 847     return
 848   },
 849   enumerable: true
 850 })
 851
 852
 853 //Returns the position of this iterator in the sorted list
 854 Object.defineProperty(iproto, "index", {
 855   get: function() {
 856     var idx = 0
 857     var stack = this._stack
 858     if(stack.length === 0) {
 859       var r = this.tree.root
 860       if(r) {
 861         return r._count
 862       }
 863       return 0
 864     } else if(stack[stack.length-1].left) {
 865       idx = stack[stack.length-1].left._count
 866     }
 867     for(var s=stack.length-2; s>=0; --s) {
 868       if(stack[s+1] === stack[s].right) {
 869         ++idx
 870         if(stack[s].left) {
 871           idx += stack[s].left._count
 872         }
 873       }
 874     }
 875     return idx
 876   },
 877   enumerable: true
 878 })
 879
 880 //Advances iterator to next element in list
 881 iproto.next = function() {
 882   var stack = this._stack
 883   if(stack.length === 0) {
 884     return
 885   }
 886   var n = stack[stack.length-1]
 887   if(n.right) {
 888     n = n.right
 889     while(n) {
 890       stack.push(n)
 891       n = n.left
 892     }
 893   } else {
 894     stack.pop()
 895     while(stack.length > 0 && stack[stack.length-1].right === n) {
 896       n = stack[stack.length-1]
 897       stack.pop()
 898     }
 899   }
 900 }
 901
 902 //Checks if iterator is at end of tree
 903 Object.defineProperty(iproto, "hasNext", {
 904   get: function() {
 905     var stack = this._stack
 906     if(stack.length === 0) {
 907       return false
 908     }
 909     if(stack[stack.length-1].right) {
 910       return true
 911     }
 912     for(var s=stack.length-1; s>0; --s) {
 913       if(stack[s-1].left === stack[s]) {
 914         return true
 915       }
 916     }
 917     return false
 918   }
 919 })
 920
 921 //Update value
 922 iproto.update = function(value) {
 923   var stack = this._stack
 924   if(stack.length === 0) {
 925     throw new Error("Can't update empty node!")
 926   }
 927   var cstack = new Array(stack.length)
 928   var n = stack[stack.length-1]
 929   cstack[cstack.length-1] = new RBNode(n._color, n.key, value, n.left, n.right, n._count)
 930   for(var i=stack.length-2; i>=0; --i) {
 931     n = stack[i]
 932     if(n.left === stack[i+1]) {
 933       cstack[i] = new RBNode(n._color, n.key, n.value, cstack[i+1], n.right, n._count)
 934     } else {
 935       cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count)
 936     }
 937   }
 938   return new RedBlackTree(this.tree._compare, cstack[0])
 939 }
 940
 941 //Moves iterator backward one element
 942 iproto.prev = function() {
 943   var stack = this._stack
 944   if(stack.length === 0) {
 945     return
 946   }
 947   var n = stack[stack.length-1]
 948   if(n.left) {
 949     n = n.left
 950     while(n) {
 951       stack.push(n)
 952       n = n.right
 953     }
 954   } else {
 955     stack.pop()
 956     while(stack.length > 0 && stack[stack.length-1].left === n) {
 957       n = stack[stack.length-1]
 958       stack.pop()
 959     }
 960   }
 961 }
 962
 963 //Checks if iterator is at start of tree
 964 Object.defineProperty(iproto, "hasPrev", {
 965   get: function() {
 966     var stack = this._stack
 967     if(stack.length === 0) {
 968       return false
 969     }
 970     if(stack[stack.length-1].left) {
 971       return true
 972     }
 973     for(var s=stack.length-1; s>0; --s) {
 974       if(stack[s-1].right === stack[s]) {
 975         return true
 976       }
 977     }
 978     return false
 979   }
 980 })
 981
 982 //Default comparison function
 983 function defaultCompare(a, b) {
 984   if(a < b) {
 985     return -1
 986   }
 987   if(a > b) {
 988     return 1
 989   }
 990   return 0
 991 }
 992
 993 //Build a tree
 994 function createRBTree(compare) {
 995   return new RedBlackTree(compare || defaultCompare, null)
 996 }