Today: Set interfaces, functional vs. mutating, some Big-O, and tree-based
set implementations

/**
 * in Java, all this is part of the base java.lang.Object class,
 * but we put it here for clarity
 */
interface SetElement {
    int hashCode();
    boolean equals(SetElement);
}

interface FunctionalSet (extends SetElement ?) {
    FunctionalSet add(SetElement);
    FunctionalSet union(FunctionalSet);
    FunctionalSet intersection(FunctionalSet);
    FunctionalSet remove(SetElement);
    FunctionalSet remove(FunctionalSet);
    
    Iterator getIterator();
    
    int cardinality();
    boolean contains(SetElement);
    boolean isSubsetOf(FunctionalSet);
}

interface MutatingSet {
    void add(SetElement);
    void union(MutatingSet);
    void intersection(MutatingSet);
    void remove(SetElement);
    void remove(MutatingSet);
    
    MutatingSet copy();
    
    Iterator getIterator();
    
    int cardinality();
    boolean contains(SetElement);
    boolean isSubsetOf(MutatingSet);
}



Tree Rotation, Applicative Trees, Building Sets from Applicative Trees

Applicative == "applying functions to values"
A "value" is immutable
An "applicative tree" is therefore immutable

Why bother?
  - iterators are "safe"
  - safe to keep multiple copies / older copies
    - and use less memory while doing it

Difficulties?
  - insertion cannot mutate the tree
  - assumes you have garbage collection
  
    class Tree {
	Object data;
	Tree left, right;
	
	Tree(Object data, Tree left, Tree right) { ... }
	
	Tree insert(Object newbie) {
	    if(data.equals(newbie)) { ... }
	    else if(data.compare(newbie) == Compare.Greater)
		// newbie goes to the left
		return new Tree(data,
				left.insert(newbie),
				right);
	    else
		// newbie goes to the right
		return new Tree(data,
				left,
				right.insert(newbie));
	}
    }
    
Insertion is still O(log N) time, but it allocates O(log N) objects as well
- but if you only keep pointer to result, the net result is creating
  O(log N) of garbage, so the net effect on space is O(1)




Tree rotation: basic operations used in all advanced tree data structures

       	    A		   rotate-right	       	      B
	    
	B      	C      	   ----------->		    D  	    A
	
      D   E   F   G   					  E    	 C
      
							       F   G
	    
	    
	    
	    
       	    A		   rotate-left	       	            C
	    
	B      	C      	   ----------->		      A       G
	
      D   E   F   G   				  B    	F    
      
						D   E
						

Java code (applicative):

    class Tree {
	Tree rotateRight() {
	    if(left == null) throw new Exception(...);
	    return new Tree(left.data,
			    left.left,
			    new Tree(this.data,
				     left.right,
				     right));
	}
    }



Recursive rotation

Many uses:
    delete member from a tree -- O(log N) work (applicative or mutating)
    iterate over subset -- O(log N) setup time to get iterator
    maintain tree balance -- O(log N) work on element insert
      (treap data structure, credit to Raimund Seidel)
      
      
    class Tree {
	Tree deleteElement(Object element) {
	    if(data.equals(element)) {
		if(left == null) return right;
		if(right == null) return left;
		
		// rotate and recursively delete from sub-tree
		return new Tree(left.data,
				left.left,
				new Tree(this.data,
					 left.right,
					 right)
				.deleteElement(element));
	    } else if(data.compare(element) == Compare.Greater)
		// the element we want to delete is on the left
		return new Tree(this.data,
				left.deleteElement(element),
				right);
	    else
		// the element we want to delete is on the right
		return new Tree(this.data,
				left,
				right.deleteElement(element));
	}
	
	Tree rotateToTop(Object element) {
	    if(data.equals(element)) return this;
	    
	    if(data.compare(element) == Compare.Greater)
		// the element we want is on the left
		return new Tree(data,
		                left.rotateToTop(element),
				right).rotateRight();
	    else
		// the element we want is on the right
		return new Tree(data,
				left,
		                right.rotateToTop(element)).rotateLeft();
	}
	
	Iterator getInterval(Object min, Object max) {
	    Tree maxTree = rotateToTop(max);
	    Tree minTree = maxTree.left.rotateToTop(min);
	    
	    // you might want to include minTree.data and maxTree.data
	    // in the iterator's output
	    return new TreeIterator(minTree.right);
	}
    }



Building a set with an applicative tree

Missing piece: dealing with hash-code collisions
    
    Possible results from a.compare(b) :
        LESS
	GREATER       (based on hashCode())
	EQUAL
	NOT_EQUAL     (a.hashCode() == b.hashCode(), !a.equals(b))

Solution (same as used in Hashtables): chaining

    class Tree {
        LinkedList data;
	Tree left, right;
	
	Object find(Object value) {
	    int myCode = data.first().hashCode();
	    int valueCode = value.hashCode();
	    if(valueCode < myCode)
		return left.find(value);
	    else if(valueCode > myCode)
		return right.find(value);
	    else
		return data.find(value);  // search the linked list
	}
    }