package larkworthy.tom; import java.util.*; /** * An unmutable ordered set that forks modified versions (insert, delete) in log(n) space and time *

* Red-black tree set keeps member elements in order according to the supplied comparator, or the hashcode. *

* * The implementation does not conform to java API Collections contract, because this does not support persistence. The * class overrides AbstractSet so that this set is compatible with other collection helpers *

* * Insert, delete, membership queries and lookups are all log(n) operations in time and space, but with persistence. This * implementation is optimized for speed. Persistence was added as per the paper, Making Data Structures Persistent, * by James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan *

* * A persistent red-black tree forks a new version of itself for every operation. * The returned value from the operation method (insert(*), delete(*)) is newly modified version, while the original * reference stays structurally the same *

* * * e.g.
* PersistentRedBlackTreeSet a = new PersistentRedBlackTreeSet();
* PersistentRedBlackTreeSet a2 = a1.insert(new Object());
* assert(a.isEmpty()); assert(!a2.isEmpty);
*
* *

* This is very useful for search if the state of variables change little between transitions. The entire state does * not need to be copied into a new state data structure for modification (which would normally cost O(n)). *

Hashing combined with persistent red-black trees, R. Battiti, M. Brunato, and F. Mascia *

Red-black trees, wikipedia * *

* I have since found this collection to be very useful as a building block for other complex persistent data structures like * persistent graphs. This was used in my PhD thesis and has had about 3 years of bashing sums on it. I think most bugs have * been squished. * *

* Copyright 2009 Tom Larkworthy * This program is distributed under the terms of the GNU General Public License as per http://www.gnu.org/licenses/gpl.txt Version 3, 29th June 2007 * Other licensing options are available (email tom.larkworthy att spectral-robotics.com) * @author Tom.Larkworthy@spectral-robotics.com */ public class PersistentRedBlackTreeSet extends AbstractSet implements Iterable{ private static final boolean RED = false; private static final boolean BLACK = true; private static final Comparator HASH_MAP_COMPARATOR = new Comparator(){ public int compare(Object o1, Object o2) { return o1.hashCode() - o2.hashCode(); } }; Comparator comparator; RedBlackNode root = new RedBlackNode((RedBlackNode)null); RedBlackNode newRoot = null; int size = 0; private long longHashcode=0; //addition hashcode calculated in a different way to try and avoid clashes int hashcode; //simple hascode private ArrayList elements = null; public PersistentRedBlackTreeSet() { this.comparator = HASH_MAP_COMPARATOR; } public PersistentRedBlackTreeSet(Comparator comparator) { this.comparator = comparator; } private PersistentRedBlackTreeSet(Comparator comparator, RedBlackNode root, int size, int hashcode, long longHashcode) { this.size =size; this.comparator = comparator; this.root = root; this.hashcode = hashcode; this.longHashcode = longHashcode; } private RedBlackNode rotate_right(LinkedList> parents, RedBlackNode n) { RedBlackNode left = n.left ;//= n.left.clone(); RedBlackNode right = n.right;// = n.right.clone(); RedBlackNode left_right = n.left.right;// = n.left.right.clone(); RedBlackNode left_left = n.left.left;// = n.left.left.clone(); //make left the new top node if(n.parent(parents)!= null){ if(n.parent(parents).left == n) n.parent(parents).left = left; else n.parent(parents).right = left; }else{ newRoot = left; } //make n the new right child of the top node left.right = n; //swap parent of left_right n.left = left_right; n.right = right; return left; } private RedBlackNode rotate_left(LinkedList> parents, RedBlackNode n) { RedBlackNode right = n.right;// = n.right.clone(); RedBlackNode left = n.left;// = n.left.clone(); RedBlackNode right_left = n.right.left;//= n.right.left.clone(); RedBlackNode right_right = n.right.right;// = n.right.right.clone(); //make right the new top node if(n.parent(parents)!= null){ if(n.parent(parents).left == n) n.parent(parents).left = right; else n.parent(parents).right = right; }else{ newRoot = right; } //make n the new left child of the top node right.left = n; //swap parent of left_right n.right = right_left; n.left = left; return right; } private void replace_node(RedBlackNode node,RedBlackNode nodeParent, RedBlackNode replacement) { if(nodeParent != null){ if(nodeParent.left == node) nodeParent.left = replacement; else { nodeParent.right = replacement; } }else{ newRoot = replacement; } } /** * inserts an element persistently. "this" remains the same list. The returned list is the modified version * @param element the new data element * @return the "this" with "element" removed */ public PersistentRedBlackTreeSet insert(D element) { RedBlackNode newNode = new RedBlackNode(element); return insertNode(newNode); } /** * note the subtree is not merged, only inserted into a specific position within the tree, all subelements of the * subtree remain in the same order. Use with caution. * @param subtree * @return */ public PersistentRedBlackTreeSet insertSubTree(PersistentRedBlackTreeSet subtree) { if(subtree.size() == 0) return this; return insertNode(subtree.root); } private PersistentRedBlackTreeSet insertNode(RedBlackNode newNode) { newRoot = root.clone(); RedBlackNode current = newRoot; LinkedList> parents = new LinkedList>(); parents.add(null);//null indicates the root parent, just like it does in RedBlackTree //find the node where the element should go at the bottom of the tree while (current.element != null) { parents.add(current); int dir = comparator.compare(newNode.element, current.element); if(dir == 0) { newRoot = null; //allready in tree return this; } else if (dir < 0) { current = current.left = current.left.clone(); } else { current = current.right = current.right.clone(); } } if(parents.getLast() != null){ if (parents.getLast().left == current) { parents.getLast().left = newNode; } else { assert parents.getLast().right == current; parents.getLast().right = newNode; } } insertCase_1(parents, newNode); PersistentRedBlackTreeSet result = new PersistentRedBlackTreeSet(comparator, newRoot, size+1, hashcode ^ newNode.element.hashCode(), longHashcode + newNode.element.hashCode()); newRoot = null;//clear reference to the newly generated root return result; } private void insertCase_1(LinkedList> parents, RedBlackNode n) { if (parents.getLast() == null){ newRoot = n; n.black = BLACK; } else insertCase_2(parents, n); } private void insertCase_2(LinkedList> parents, RedBlackNode n) { //easy case 2 if (parents.getLast().black){ }else{ insertCase_3(parents, n); } } private void insertCase_3(LinkedList> parents, RedBlackNode n) { if (!n.uncle(parents).black) { parents.getLast().black = BLACK; n.cloneUncle(parents); n.uncle(parents).black = BLACK; n.grandparent(parents).black = RED; //we recurse on the granparent now, up two levels //so we need to pop a 2 elements from the parents list RedBlackNode grandparent = n.grandparent(parents); parents.removeLast(); parents.removeLast(); insertCase_1(parents, grandparent); } else insertCase_4(parents, n); } private void insertCase_4(LinkedList> parents, RedBlackNode n) { if (n == n.parent(parents).right && n.parent(parents) == n.grandparent(parents).left) { //we rotate on n's parent //so we need to pop n's parent off the parent list RedBlackNode nParent = n.parent(parents); parents.removeLast(); RedBlackNode replacement = rotate_left(parents, nParent); //then we go to case 5 using n's left. So n is the new parent of the algorithm's n parents.addLast(replacement); n = replacement.left = replacement.left.clone(); } else if (n == n.parent(parents).left && n.parent(parents) == n.grandparent(parents).right) { RedBlackNode nParent = n.parent(parents); parents.removeLast(); RedBlackNode replacement = rotate_right(parents, nParent); parents.addLast(replacement); n = replacement.right = replacement.right.clone(); } insert_case5(parents, n); } private void insert_case5(LinkedList> parents, RedBlackNode n) { n.parent(parents).black = BLACK; n.grandparent(parents).black = RED; if (n == n.parent(parents).left && n.parent(parents) == n.grandparent(parents).left) { RedBlackNode gp = n.grandparent(parents); parents.removeLast(); parents.removeLast(); rotate_right(parents, gp); } else { assert n == n.parent(parents).right && n.parent(parents) == n.grandparent(parents).right; RedBlackNode gp = n.grandparent(parents); parents.removeLast(); parents.removeLast(); rotate_left(parents, gp); } } /** * returns a new list, that is "this" minus the deleted item. * @param element the element to delete * @return the modified version */ public PersistentRedBlackTreeSet delete(D element){ RedBlackNode current = newRoot = root.clone(); //RedBlackNode current = newRoot = root.deepClone(); LinkedList> parents = new LinkedList>(); parents.add(null);//root represented by null //find the node where the element should go at the bottom of the tree while (current.element != null) { parents.add(current); int dir = comparator.compare(element, current.element); if (dir < 0) { current = current.left = current.left.clone(); } else if(dir > 0){ current = current.right= current.right.clone(); }else{ parents.removeLast(); delete(parents, current); PersistentRedBlackTreeSet tree = new PersistentRedBlackTreeSet(comparator, newRoot, size-1, hashcode ^ element.hashCode(), longHashcode - element.hashCode()); newRoot = null; return tree; } } newRoot = null; //no change return this; } private void delete(LinkedList> parents, RedBlackNode n) { assert n.parent(parents) == null || n.parent(parents).left == n || n.parent(parents).right == n; //if the node has two children, we swap it with the next leaf if(n.left.element != null && n.right.element != null){ parents.addLast(n); n.left = n.left.clone(); RedBlackNode current = n.right = n.right.clone(); while(current.element != null){ parents.addLast(current); current = current.left = current.left.clone(); } n.element = current.parent(parents).element; RedBlackNode currentParent = current.parent(parents); parents.removeLast(); delete_one_child(parents, currentParent); }else{ delete_one_child(parents, n); } } private void delete_one_child(LinkedList> parents, RedBlackNode n) { /* Precondition: n has at most one non-null child */ RedBlackNode child; if(n.right.element == null){ child = n.left = n.left.clone(); }else{ assert n.left.element == null; child = n.right = n.right.clone(); } replace_node(n, n.parent(parents), child); if (n.black) { if (!child.black) child.black = BLACK; else delete_case1(parents, child); } } private void delete_case1(LinkedList> parents, RedBlackNode n) { if (n.parent(parents) == null) { newRoot = n; }else{ delete_case2(parents, n); } } private void delete_case2(LinkedList> parents, RedBlackNode n) { if (!n.sibling(parents).black) { n.cloneSibling(parents); n.parent(parents).black = RED; n.sibling(parents).black = BLACK; if (n == n.parent(parents).left) { //rotate on the parent, back up one level RedBlackNode parent = n.parent(parents); parents.removeLast(); RedBlackNode replacement = rotate_left(parents, parent); //n acually ends up deeper now than to begin with //so we need to regenerate the parents list to its prior level parents.add(replacement); parents.add(replacement.left); n = replacement.left.left = replacement.left.left.clone(); } else { RedBlackNode parent = n.parent(parents); parents.removeLast(); RedBlackNode replacement =rotate_right(parents, parent); parents.add(replacement); parents.add(replacement.right); n = replacement.right.right = replacement.right.right.clone(); } } delete_case3(parents, n); } private void delete_case3(LinkedList> parents, RedBlackNode n) { if (n.parent(parents).black && n.sibling(parents).black && n.sibling(parents).left.black && n.sibling(parents).right.black) { n.cloneSibling(parents); n.sibling(parents).black = RED; RedBlackNode parent = parents.removeLast(); delete_case1(parents, parent); } else delete_case4(parents, n); } private void delete_case4(LinkedList> parents, RedBlackNode n) { if (!n.parent(parents).black && n.sibling(parents).black && n.sibling(parents).left.black && n.sibling(parents).right.black) { n.cloneSibling(parents); n.sibling(parents).black = RED; n.parent(parents).black = BLACK; } else delete_case5(parents, n); } private void delete_case5(LinkedList> parents, RedBlackNode n) { if (n == n.parent(parents).left && n.sibling(parents).black && !n.sibling(parents).left.black && n.sibling(parents).right.black) { n.cloneSibling(parents); n.sibling(parents).black = RED; n.sibling(parents).left = n.sibling(parents).left.clone(); n.sibling(parents).left.black = BLACK; rotate_right(parents, n.sibling(parents)); } else if (n == n.parent(parents).right && n.sibling(parents).black && !n.sibling(parents).right.black && n.sibling(parents).left.black) { n.cloneSibling(parents); n.sibling(parents).black = RED; n.sibling(parents).right = n.sibling(parents).right.clone(); n.sibling(parents).right.black = BLACK; rotate_left(parents, n.sibling(parents)); } delete_case6(parents, n); } private void delete_case6(LinkedList> parents, RedBlackNode n) { n.cloneSibling(parents); n.sibling(parents).black = n.parent(parents).black; n.parent(parents).black = BLACK; if (n == n.parent(parents).left) { n.sibling(parents).right = n.sibling(parents).right.clone(); n.sibling(parents).right.black = BLACK; RedBlackNode parent = parents.removeLast(); rotate_left(parents, parent); } else { n.sibling(parents).left = n.sibling(parents).left.clone(); n.sibling(parents).left.black = BLACK; RedBlackNode parent = parents.removeLast(); rotate_right(parents, parent); } } private ArrayList fillArray(ArrayList array, RedBlackNode current){ if(current.element == null) return array;//null element fillArray(array, current.left); array.add(current.element); fillArray(array, current.right); return array; } /** * returns the contents of the PRBTree in a list, the result is cached and returned on subsequent call. * DO NOT MODIFY THE RETURNED LIST, copy it modification is needed. */ public List getElements(){ if(elements == null){ elements = new ArrayList(size); fillArray(elements, root); } return elements; } /** * iterates the elements of the list. O(1) cost of initialisation and next(). You can abandon * iteratation midway without time or space penalties. * @return */ public Iterator iterator() { return new NullIteratorAdapter(new InOrderTraverser()); } public int size() { return size; } /** * gets a random leaf element out the list in log(n) time. Note some elements are not stored in leaf nodes, so * not all the contents can be sampled. However, samples are approximately drawn uniformly over the full range of the list * @return */ public D getRandomLeaf(){ RedBlackNode current = root; while (true) { int dir = Math.random()>.5f?1:-1; if(dir < 0) { if(current.left.element == null) return current.element; current = current.left; } else { if(current.right.element == null) return current.element; current = current.right; } } //return root.element; } /** * log(n) implementation of contains * @param e * @return */ public boolean contains(Object e) { D element = (D) e; RedBlackNode current = root; while (current.element != null) { int dir = comparator.compare(element, current.element); if (dir == 0 ){ return true; }else if(dir < 0) { current = current.left; } else { current = current.right; } } return false; } public D get(D element) { RedBlackNode current = root; while (current.element != null) { int dir = comparator.compare(element, current.element); if (dir == 0 ){ return current.element; }else if(dir < 0) { current = current.left; } else { current = current.right; } } return null; } public int hashCode() { return hashcode; } private D getRoot() { if(size == 0) return null; return root.element; } private class InOrderTraverser implements Iterator{ Stack stack = new Stack(); public InOrderTraverser() { if(root.element!=null){ stack.push(new TraversalVariable(TraversalSymbol.RIGHT, root)); stack.push(new TraversalVariable(TraversalSymbol.VISIT, root)); stack.push(new TraversalVariable(TraversalSymbol.LEFT, root)); } } public boolean hasNext() { return true; } public D next(){ if(stack.isEmpty()) return null; TraversalVariable curr = stack.pop(); while(curr.s != TraversalSymbol.VISIT){ RedBlackNode child; if(curr.s == TraversalSymbol.LEFT){ child = curr.node.left; }else{ assert curr.s == TraversalSymbol.RIGHT; child = curr.node.right; } if(child.element != null){ stack.push(new TraversalVariable(TraversalSymbol.RIGHT, child)); stack.push(new TraversalVariable(TraversalSymbol.VISIT, child)); stack.push(new TraversalVariable(TraversalSymbol.LEFT, child)); } if(stack.isEmpty()) return null; curr = stack.pop(); } return curr.node.element; } public void remove() { throw new UnsupportedOperationException(); } } private class TraversalVariable{ TraversalSymbol s; public TraversalVariable(TraversalSymbol s, RedBlackNode node) { this.s = s; this.node = node; } RedBlackNode node; } private static enum TraversalSymbol{LEFT, RIGHT, VISIT} /** * currently only supports comparisons with other PersistentRB sets * @param obj * @return */ public boolean equals(Object obj) { PersistentRedBlackTreeSet other = (PersistentRedBlackTreeSet) obj; if(other.hashcode != hashcode) return false; if(other.longHashcode != longHashcode)return false; List l1 = other.getElements(); List l2 = getElements(); return l1.equals(l2); } /** * main storage node for class * @param */ private class RedBlackNode { RedBlackNode left; RedBlackNode right; boolean black; D element; public RedBlackNode() { } /** * creates a new RED leaf node (black empty children are also created automatically) * * @param element elemnt */ public RedBlackNode(D element) { this.element = element; black = RED; this.left = new RedBlackNode(this); //create BLACK null nodes this.right = new RedBlackNode(this);//create BLACK null nodes } public RedBlackNode(RedBlackNode parent) { this.black = BLACK; } RedBlackNode grandparent(LinkedList> parents) { return parents.get(parents.size() - 2); } RedBlackNode parent(LinkedList> parents) { return parents.getLast(); } RedBlackNode uncle(LinkedList> parents) { if (grandparent(parents).left == parents.getLast()){ return grandparent(parents).right; } else{ assert grandparent(parents).right == parents.getLast(); return grandparent(parents).left; } } public void cloneUncle(LinkedList> parents){ if (grandparent(parents).left == parents.getLast()){ grandparent(parents).right = grandparent(parents).right.clone(); } else{ assert grandparent(parents).right == parents.getLast(); grandparent(parents).left = grandparent(parents).left.clone(); } } public RedBlackNode sibling(LinkedList> parents) { if (parent(parents).left == this){ return parent(parents).right; } else{ return parent(parents).left; } } public void cloneSibling(LinkedList> parents) { if (parent(parents).left == this){ parent(parents).right = parent(parents).right.clone(); } else{ assert parent(parents).right == this; parent(parents).left = parent(parents).left.clone(); } } public RedBlackNode clone(){ RedBlackNode node = new RedBlackNode(); node.element = element; node.left = left; node.right = right; node.black = black; return node; } public RedBlackNode deepClone(){ RedBlackNode node = new RedBlackNode(); node.element = element; node.black = black; if(element == null) return node; node.left = left.deepClone(); node.right = right.deepClone(); return node; } } /** * This iterator wraps another iterator so the implementor of the other iterator can be lazy. * They do not need to implement the hasNext function. The emptyness of the iterator can be signalled by returning * a null from the next() method. */ private class NullIteratorAdapter implements Iterator { T next; Iterator wrapper; public NullIteratorAdapter(Iterator nullTerminatedIterator) { this.wrapper = nullTerminatedIterator; next = wrapper.next(); } public boolean hasNext() { return next != null; } public T next() { T ret = next; next = wrapper.next(); return ret; } public void remove() { throw new UnsupportedOperationException(); } } } %% %%(language-ref) package larkworthy.tom; import junit.framework.TestCase; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Iterator; /** * Tests for the RedBlackTree by throwing lots of random data at it * * Copyright 2009 Tom Larkworthy * This program is distributed under the terms of the GNU General Public License as per http://www.gnu.org/licenses/gpl.txt Version 3, 29th June 2007 * Other licensing options are availible. * @author Tom.Larkworthy@spectral-robotics.com */ public class TestRBTree extends TestCase { public static final Comparator INTEGER_COMP = new Comparator() { public int compare(Integer o1, Integer o2) { return o1 - o2; } }; /** * tests that a thousand integers randomly added to the tree are remembered and stored in order */ public void testPersistantInsert() { PersistentRedBlackTreeSet tree = new PersistentRedBlackTreeSet(INTEGER_COMP); ArrayList shuffledIntegers = getShuffledIntegers(1000); //add shuffled integers to the tree for (Integer integer : shuffledIntegers) { tree = tree.insert(integer); } assertTrue(tree.size() == 1000); int count = 0; //check they are iterated in the correct order for (Integer integer : tree) { assertEquals(integer.intValue(), count++); } } /** * tests that a thousand integers randomly added to the tree can be removed in a random order * successfully */ public void testPersistantDelete() { PersistentRedBlackTreeSet tree = new PersistentRedBlackTreeSet(INTEGER_COMP); ArrayList shuffledIntegers = getShuffledIntegers(1000); //insert all for (Integer integer : shuffledIntegers) { tree = tree.insert(integer); } //reshuffle them Collections.shuffle(shuffledIntegers); int size = 1000; assertTrue(tree.size() == size); for (Integer integer : shuffledIntegers) { assertTrue(tree.contains(integer)); tree = tree.delete(integer); assertEquals(tree.size(), --size); assertFalse(tree.contains(integer)); //check we fail to remove elements not present tree = tree.delete(integer); assertEquals(size, tree.size()); tree = tree.delete(1001); assertEquals(size, tree.size()); tree = tree.delete(-1); assertEquals(size, tree.size()); } assertFalse(tree.iterator().hasNext()); } private static ArrayList getShuffledIntegers(int number) { ArrayList shuffledIntegers = new ArrayList(number); for (int i = 0; i < 1000; i++) { shuffledIntegers.add(i); } Collections.shuffle(shuffledIntegers); return shuffledIntegers; } /** * performs a 100K random walk of inserting and removing random integers, and choosing whether to keep the old * tree or the new tree. */ public void testPersistantDelete2() { PersistentRedBlackTreeSet tree = new PersistentRedBlackTreeSet(INTEGER_COMP); for (int i = 0; i < 100000; i++) { int el = (int) (Math.random() * 10); PersistentRedBlackTreeSet del = tree.delete(el); PersistentRedBlackTreeSet ins = tree.insert(el); assertTrue(tree.equals(ins) || tree.equals(del)); double choice = Math.random(); if(choice < .33){ //System.out.println("del"); tree = del; }else if(choice < .66){ //System.out.println("ins"); tree = ins; }//else System.out.println("keep"); } } /** * tests if certain intervals can be inserted */ public void testPersistentInsertSubtree(){ PersistentRedBlackTreeSet tree1 = new PersistentRedBlackTreeSet(INTEGER_COMP); PersistentRedBlackTreeSet tree2 = new PersistentRedBlackTreeSet(INTEGER_COMP); ArrayList tree1Contents = new ArrayList(); ArrayList tree2Contents = new ArrayList(); for(int i=0;i<=1000;i++){ tree1 = tree1.insert(i); tree1Contents.add(i); } for(int i=1001;i<=2000;i++){ tree2 = tree2.insert(i); tree2Contents.add(i); } for(int i=2001;i<=3000;i++){ tree1 = tree1.insert(i); tree1Contents.add(i); } Collections.sort(tree1Contents, INTEGER_COMP); Collections.sort(tree2Contents, INTEGER_COMP); assertEquals(tree1.getElements(), tree1Contents); assertEquals(tree2.getElements(), tree2Contents); ArrayList treeContents = new ArrayList(); treeContents.addAll(tree1Contents); treeContents.addAll(tree2Contents); Collections.sort(treeContents, INTEGER_COMP); PersistentRedBlackTreeSet combined = tree1.insertSubTree(tree2); //check new tree is the combination assertEquals(combined.getElements(), treeContents); //and check originals are intact assertEquals(tree1.getElements(), tree1Contents); assertEquals(tree2.getElements(), tree2Contents); } public void testPersistantIterator(){ PersistentRedBlackTreeSet tree1 = new PersistentRedBlackTreeSet(INTEGER_COMP); PersistentRedBlackTreeSet tree2 = new PersistentRedBlackTreeSet(INTEGER_COMP); ArrayList tree1Contents = new ArrayList(); ArrayList tree2Contents = new ArrayList(); for(int i=0;i<=1000;i++){ tree1 = tree1.insert(i); tree1Contents.add(i); } for(int i=1001;i<=2000;i++){ tree2 = tree2.insert(i); tree2Contents.add(i); } for(int i=2001;i<=3000;i++){ tree1 = tree1.insert(i); tree1Contents.add(i); } Collections.sort(tree1Contents, INTEGER_COMP); Collections.sort(tree2Contents, INTEGER_COMP); assertEquals(tree1.getElements(), tree1Contents); assertEquals(tree2.getElements(), tree2Contents); Iterator tree1Iter = tree1.iterator(); Iterator tree2Iter = tree2.iterator(); int cursur = 0; while(tree1Iter.hasNext()){ int el1 = tree1Iter.next(); assertEquals(el1, (int)tree1Contents.get(cursur)); cursur++; } cursur = 0; while(tree2Iter.hasNext()){ int el2 = tree2Iter.next(); assertEquals(el2, (int)tree2Contents.get(cursur)); cursur++; } } }