rbtree.js 22 KB

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