SHARE
TWEET

Untitled

a guest Nov 4th, 2015 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Fix up a double black node in a tree
  2. function fixDoubleBlack(stack) {
  3.   var n, p, s, z
  4.   for(var i=stack.length-1; i>=0; --i) {
  5.     n = stack[i]
  6.     if(i === 0) {
  7.       n._color = BLACK
  8.       return
  9.     }
  10.     //console.log("visit node:", n.key, i, stack[i].key, stack[i-1].key)
  11.     p = stack[i-1]
  12.     if(p.left === n) {
  13.       //console.log("left child")
  14.       s = p.right
  15.       if(s.right && s.right._color === RED) {
  16.         //console.log("case 1: right sibling child red")
  17.         s = p.right = cloneNode(s)
  18.         z = s.right = cloneNode(s.right)
  19.         p.right = s.left
  20.         s.left = p
  21.         s.right = z
  22.         s._color = p._color
  23.         n._color = BLACK
  24.         p._color = BLACK
  25.         z._color = BLACK
  26.         recount(p)
  27.         recount(s)
  28.         if(i > 1) {
  29.           var pp = stack[i-2]
  30.           if(pp.left === p) {
  31.             pp.left = s
  32.           } else {
  33.             pp.right = s
  34.           }
  35.         }
  36.         stack[i-1] = s
  37.         return
  38.       } else if(s.left && s.left._color === RED) {
  39.         //console.log("case 1: left sibling child red")
  40.         s = p.right = cloneNode(s)
  41.         z = s.left = cloneNode(s.left)
  42.         p.right = z.left
  43.         s.left = z.right
  44.         z.left = p
  45.         z.right = s
  46.         z._color = p._color
  47.         p._color = BLACK
  48.         s._color = BLACK
  49.         n._color = BLACK
  50.         recount(p)
  51.         recount(s)
  52.         recount(z)
  53.         if(i > 1) {
  54.           var pp = stack[i-2]
  55.           if(pp.left === p) {
  56.             pp.left = z
  57.           } else {
  58.             pp.right = z
  59.           }
  60.         }
  61.         stack[i-1] = z
  62.         return
  63.       }
  64.       if(s._color === BLACK) {
  65.         if(p._color === RED) {
  66.           //console.log("case 2: black sibling, red parent", p.right.value)
  67.           p._color = BLACK
  68.           p.right = repaint(RED, s)
  69.           return
  70.         } else {
  71.           //console.log("case 2: black sibling, black parent", p.right.value)
  72.           p.right = repaint(RED, s)
  73.           continue  
  74.         }
  75.       } else {
  76.         //console.log("case 3: red sibling")
  77.         s = cloneNode(s)
  78.         p.right = s.left
  79.         s.left = p
  80.         s._color = p._color
  81.         p._color = RED
  82.         recount(p)
  83.         recount(s)
  84.         if(i > 1) {
  85.           var pp = stack[i-2]
  86.           if(pp.left === p) {
  87.             pp.left = s
  88.           } else {
  89.             pp.right = s
  90.           }
  91.         }
  92.         stack[i-1] = s
  93.         stack[i] = p
  94.         if(i+1 < stack.length) {
  95.           stack[i+1] = n
  96.         } else {
  97.           stack.push(n)
  98.         }
  99.         i = i+2
  100.       }
  101.     } else {
  102.       //console.log("right child")
  103.       s = p.left
  104.       if(s.left && s.left._color === RED) {
  105.         //console.log("case 1: left sibling child red", p.value, p._color)
  106.         s = p.left = cloneNode(s)
  107.         z = s.left = cloneNode(s.left)
  108.         p.left = s.right
  109.         s.right = p
  110.         s.left = z
  111.         s._color = p._color
  112.         n._color = BLACK
  113.         p._color = BLACK
  114.         z._color = BLACK
  115.         recount(p)
  116.         recount(s)
  117.         if(i > 1) {
  118.           var pp = stack[i-2]
  119.           if(pp.right === p) {
  120.             pp.right = s
  121.           } else {
  122.             pp.left = s
  123.           }
  124.         }
  125.         stack[i-1] = s
  126.         return
  127.       } else if(s.right && s.right._color === RED) {
  128.         //console.log("case 1: right sibling child red")
  129.         s = p.left = cloneNode(s)
  130.         z = s.right = cloneNode(s.right)
  131.         p.left = z.right
  132.         s.right = z.left
  133.         z.right = p
  134.         z.left = s
  135.         z._color = p._color
  136.         p._color = BLACK
  137.         s._color = BLACK
  138.         n._color = BLACK
  139.         recount(p)
  140.         recount(s)
  141.         recount(z)
  142.         if(i > 1) {
  143.           var pp = stack[i-2]
  144.           if(pp.right === p) {
  145.             pp.right = z
  146.           } else {
  147.             pp.left = z
  148.           }
  149.         }
  150.         stack[i-1] = z
  151.         return
  152.       }
  153.       if(s._color === BLACK) {
  154.         if(p._color === RED) {
  155.           //console.log("case 2: black sibling, red parent")
  156.           p._color = BLACK
  157.           p.left = repaint(RED, s)
  158.           return
  159.         } else {
  160.           //console.log("case 2: black sibling, black parent")
  161.           p.left = repaint(RED, s)
  162.           continue  
  163.         }
  164.       } else {
  165.         //console.log("case 3: red sibling")
  166.         s = cloneNode(s)
  167.         p.left = s.right
  168.         s.right = p
  169.         s._color = p._color
  170.         p._color = RED
  171.         recount(p)
  172.         recount(s)
  173.         if(i > 1) {
  174.           var pp = stack[i-2]
  175.           if(pp.right === p) {
  176.             pp.right = s
  177.           } else {
  178.             pp.left = s
  179.           }
  180.         }
  181.         stack[i-1] = s
  182.         stack[i] = p
  183.         if(i+1 < stack.length) {
  184.           stack[i+1] = n
  185.         } else {
  186.           stack.push(n)
  187.         }
  188.         i = i+2
  189.       }
  190.     }
  191.   }
  192. }
  193.  
  194. //Removes item at iterator from tree
  195. iproto.remove = function() {
  196.   var stack = this._stack
  197.   if(stack.length === 0) {
  198.     return this.tree
  199.   }
  200.   //First copy path to node
  201.   var cstack = new Array(stack.length)
  202.   var n = stack[stack.length-1]
  203.   cstack[cstack.length-1] = new RBNode(n._color, n.key, n.value, n.left, n.right, n._count)
  204.   for(var i=stack.length-2; i>=0; --i) {
  205.     var n = stack[i]
  206.     if(n.left === stack[i+1]) {
  207.       cstack[i] = new RBNode(n._color, n.key, n.value, cstack[i+1], n.right, n._count)
  208.     } else {
  209.       cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count)
  210.     }
  211.   }
  212.  
  213.   //Get node
  214.   n = cstack[cstack.length-1]
  215.   //console.log("start remove: ", n.value)
  216.  
  217.   //If not leaf, then swap with previous node
  218.   if(n.left && n.right) {
  219.     //console.log("moving to leaf")
  220.  
  221.     //First walk to previous leaf
  222.     var split = cstack.length
  223.     n = n.left
  224.     while(n.right) {
  225.       cstack.push(n)
  226.       n = n.right
  227.     }
  228.     //Copy path to leaf
  229.     var v = cstack[split-1]
  230.     cstack.push(new RBNode(n._color, v.key, v.value, n.left, n.right, n._count))
  231.     cstack[split-1].key = n.key
  232.     cstack[split-1].value = n.value
  233.  
  234.     //Fix up stack
  235.     for(var i=cstack.length-2; i>=split; --i) {
  236.       n = cstack[i]
  237.       cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count)
  238.     }
  239.     cstack[split-1].left = cstack[split]
  240.   }
  241.   //console.log("stack=", cstack.map(function(v) { return v.value }))
  242.  
  243.   //Remove leaf node
  244.   n = cstack[cstack.length-1]
  245.   if(n._color === RED) {
  246.     //Easy case: removing red leaf
  247.     //console.log("RED leaf")
  248.     var p = cstack[cstack.length-2]
  249.     if(p.left === n) {
  250.       p.left = null
  251.     } else if(p.right === n) {
  252.       p.right = null
  253.     }
  254.     cstack.pop()
  255.     for(var i=0; i<cstack.length; ++i) {
  256.       cstack[i]._count--
  257.     }
  258.     return new RedBlackTree(this.tree._compare, cstack[0])
  259.   } else {
  260.     if(n.left || n.right) {
  261.       //Second easy case:  Single child black parent
  262.       //console.log("BLACK single child")
  263.       if(n.left) {
  264.         swapNode(n, n.left)
  265.       } else if(n.right) {
  266.         swapNode(n, n.right)
  267.       }
  268.       //Child must be red, so repaint it black to balance color
  269.       n._color = BLACK
  270.       for(var i=0; i<cstack.length-1; ++i) {
  271.         cstack[i]._count--
  272.       }
  273.       return new RedBlackTree(this.tree._compare, cstack[0])
  274.     } else if(cstack.length === 1) {
  275.       //Third easy case: root
  276.       //console.log("ROOT")
  277.       return new RedBlackTree(this.tree._compare, null)
  278.     } else {
  279.       //Hard case: Repaint n, and then do some nasty stuff
  280.       //console.log("BLACK leaf no children")
  281.       for(var i=0; i<cstack.length; ++i) {
  282.         cstack[i]._count--
  283.       }
  284.       var parent = cstack[cstack.length-2]
  285.       fixDoubleBlack(cstack)
  286.       //Fix up links
  287.       if(parent.left === n) {
  288.         parent.left = null
  289.       } else {
  290.         parent.right = null
  291.       }
  292.     }
  293.   }
  294.   return new RedBlackTree(this.tree._compare, cstack[0])
  295. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top