SHARE
TWEET

Untitled

a guest Nov 4th, 2015 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.          * returns a new list, that is "this" minus the deleted item.
  3.          * @param element the element to delete
  4.          * @return the modified version
  5.          */
  6.         public PersistentRedBlackTreeSet<D> delete(D element){
  7.                 RedBlackNode<D> current = newRoot = root.clone();
  8.                 //RedBlackNode<D> current = newRoot = root.deepClone();
  9.                 LinkedList<RedBlackNode<D>> parents = new LinkedList<RedBlackNode<D>>();
  10.                 parents.add(null);//root represented by null
  11.  
  12.  
  13.                 //find the node where the element should go at the bottom of the tree
  14.                 while (current.element != null) {
  15.                         parents.add(current);
  16.  
  17.                         int dir = comparator.compare(element, current.element);
  18.                         if (dir < 0) {
  19.                                 current = current.left = current.left.clone();
  20.                         } else if(dir > 0){
  21.                                 current = current.right= current.right.clone();
  22.                         }else{
  23.  
  24.                                 parents.removeLast();
  25.                                 delete(parents, current);
  26.                                 PersistentRedBlackTreeSet<D> tree = new PersistentRedBlackTreeSet<D>(comparator, newRoot, size-1, hashcode ^ element.hashCode(), longHashcode - element.hashCode());
  27.                                 newRoot = null;
  28.                                 return tree;
  29.                         }
  30.                 }
  31.                 newRoot = null;
  32.                 //no change
  33.                 return this;
  34.         }
  35.  
  36.         private void delete(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  37.  
  38.                 assert n.parent(parents) == null || n.parent(parents).left == n || n.parent(parents).right == n;
  39.  
  40.                 //if the node has two children, we swap it with the next leaf
  41.                 if(n.left.element != null && n.right.element != null){
  42.                         parents.addLast(n);
  43.                         n.left = n.left.clone();
  44.                         RedBlackNode<D> current = n.right = n.right.clone();
  45.                         while(current.element != null){
  46.                                 parents.addLast(current);
  47.                                 current = current.left = current.left.clone();
  48.                         }
  49.  
  50.                         n.element = current.parent(parents).element;
  51.  
  52.                         RedBlackNode<D> currentParent = current.parent(parents);
  53.                         parents.removeLast();
  54.                         delete_one_child(parents, currentParent);
  55.                 }else{
  56.                         delete_one_child(parents, n);
  57.                 }
  58.         }
  59.  
  60.         private void delete_one_child(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  61.                 /* Precondition: n has at most one non-null child */
  62.                 RedBlackNode<D> child;
  63.                 if(n.right.element == null){
  64.                         child = n.left = n.left.clone();
  65.                 }else{
  66.                         assert n.left.element == null;
  67.                         child = n.right = n.right.clone();
  68.                 }
  69.  
  70.                 replace_node(n, n.parent(parents), child);
  71.                 if (n.black) {
  72.                         if (!child.black)
  73.                                 child.black = BLACK;
  74.                         else
  75.                                 delete_case1(parents, child);
  76.                 }
  77.         }
  78.  
  79.  
  80.         private void delete_case1(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  81.                 if (n.parent(parents) == null)
  82.                 {
  83.                         newRoot = n;
  84.                 }else{
  85.                         delete_case2(parents, n);
  86.                 }
  87.         }
  88.  
  89.         private void delete_case2(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  90.                 if (!n.sibling(parents).black) {
  91.                         n.cloneSibling(parents);
  92.                         n.parent(parents).black = RED;
  93.                         n.sibling(parents).black = BLACK;
  94.                         if (n == n.parent(parents).left)
  95.                         {
  96.                                 //rotate on the parent, back up one level
  97.                                 RedBlackNode<D> parent = n.parent(parents);
  98.                                 parents.removeLast();
  99.                                 RedBlackNode<D> replacement = rotate_left(parents, parent);
  100.  
  101.                                 //n acually ends up deeper now than to begin with
  102.                                 //so we need to regenerate the parents list to its prior level
  103.                                 parents.add(replacement);
  104.                                 parents.add(replacement.left);
  105.                                 n = replacement.left.left = replacement.left.left.clone();
  106.                         }
  107.                         else
  108.                         {
  109.                                 RedBlackNode<D> parent = n.parent(parents);
  110.                                 parents.removeLast();
  111.                                 RedBlackNode<D> replacement =rotate_right(parents, parent);
  112.                                 parents.add(replacement);
  113.                                 parents.add(replacement.right);
  114.                                 n = replacement.right.right = replacement.right.right.clone();
  115.                         }
  116.                 }
  117.                 delete_case3(parents, n);
  118.         }
  119.  
  120.         private void delete_case3(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  121.                 if (n.parent(parents).black &&
  122.                                 n.sibling(parents).black &&
  123.                                 n.sibling(parents).left.black &&
  124.                                 n.sibling(parents).right.black) {
  125.                         n.cloneSibling(parents);
  126.                         n.sibling(parents).black = RED;
  127.  
  128.                         RedBlackNode<D> parent = parents.removeLast();
  129.                         delete_case1(parents, parent);
  130.                 } else
  131.                         delete_case4(parents, n);
  132.         }
  133.  
  134.         private void delete_case4(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  135.                 if (!n.parent(parents).black &&
  136.                                 n.sibling(parents).black &&
  137.                                 n.sibling(parents).left.black &&
  138.                                 n.sibling(parents).right.black) {
  139.                         n.cloneSibling(parents);
  140.                         n.sibling(parents).black = RED;
  141.                         n.parent(parents).black = BLACK;
  142.                 } else
  143.                         delete_case5(parents, n);
  144.         }
  145.  
  146.         private void delete_case5(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  147.                 if (n == n.parent(parents).left &&
  148.                                 n.sibling(parents).black &&
  149.                                 !n.sibling(parents).left.black &&
  150.                                 n.sibling(parents).right.black) {
  151.                         n.cloneSibling(parents);
  152.                         n.sibling(parents).black = RED;
  153.                         n.sibling(parents).left = n.sibling(parents).left.clone();
  154.                         n.sibling(parents).left.black = BLACK;
  155.                         rotate_right(parents, n.sibling(parents));
  156.                 } else if (n == n.parent(parents).right &&
  157.                                 n.sibling(parents).black &&
  158.                                 !n.sibling(parents).right.black &&
  159.                                 n.sibling(parents).left.black) {
  160.                         n.cloneSibling(parents);
  161.                         n.sibling(parents).black = RED;
  162.                         n.sibling(parents).right = n.sibling(parents).right.clone();
  163.                         n.sibling(parents).right.black = BLACK;
  164.                         rotate_left(parents, n.sibling(parents));
  165.                 }
  166.                 delete_case6(parents, n);
  167.         }
  168.  
  169.         private void delete_case6(LinkedList<RedBlackNode<D>> parents, RedBlackNode<D> n) {
  170.                 n.cloneSibling(parents);
  171.                 n.sibling(parents).black = n.parent(parents).black;
  172.                 n.parent(parents).black = BLACK;
  173.                 if (n == n.parent(parents).left) {
  174.                         n.sibling(parents).right = n.sibling(parents).right.clone();
  175.                         n.sibling(parents).right.black = BLACK;
  176.                         RedBlackNode<D> parent = parents.removeLast();
  177.                         rotate_left(parents, parent);
  178.                 } else {
  179.                         n.sibling(parents).left = n.sibling(parents).left.clone();
  180.                         n.sibling(parents).left.black = BLACK;
  181.                         RedBlackNode<D> parent = parents.removeLast();
  182.                         rotate_right(parents, parent);
  183.                 }
  184.         }
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