Any class implementing the SortedSet interface must provide all methods of SortedSet, as well as Set. For this assignment, your class will support a generic type E (TreapSet<E>), and you need to implement the following methods:

~~public void add(E object)~~ public boolean add(E object) The method should return boolean, not void.
public void clear()
public boolean contains(Object object)
public boolean isEmpty()
public boolean remove(Object object)
public int size()
public Iterator<E> iterator()
public Object[] toArray()
public Comparator<? super E> comparator()
public E first()
public E last()

You must also implement the following constructors:

the default constructor (no parameters). If this is used, the generic object must implement Comparable.
a constructor that takes a Comparator<? super E> object as a parameter. If this constructor is used, all comparisons of objects should be done via the comparator, otherwise, use their natural ordering.

The Iterator<E> function must return an iterator which traverses through the set in order of the generic object's natural ordering (e.g. obj1.compareTo(obj2) or via the Comparator object).

All other Set and SortedSet methods must be defined to implement the interface, but you may define them as stubs which throw an UnsupportedOperationException.

TreapSet and Red-Black Trees

We have discussed the interface you will be implementing. Numerous data structures could be used to implement the interface. We'll focus on two--the Red-Black tree and the Treap.

The java collections libraries include an implementation of the SortedSet interface using a red-black tree. This class is called TreeSet. You will use this implementation of a red-black tree for your benchmarking experiments, rather than write your own. You will, however, be implementing the SortedSet interface using a second data structure known as a Treap. Before proceeding, read Aragon and Seidel's paper about Treaps: http://ischool.berkeley.edu/~aragon/pubs/rst96.pdf, and the Java API documentation on Set and SortedSet.

UPDATE 10/17/08: Unfortunately, we didn't get to the randomized part of the Treap data structure in lecture on Thursday. You have all the information you need in the Aragon and Seidel paper, but it may also help you to look at the last few slides from lecture on Thursday to learn about the randomization part. In particular, it should be emphasized that everything exposed through the SortedSet interface has to do with the keys only. The priorities are only for use internally in your Treap class. For example, in the add(E object) method, object is the KEY, not the priority. So your implementation of the add(E object) method should go something like this:

Call the Treap node constructor. This will make a new node with object as the key. It should also fill in the priority field with a random number obtained from the java.util.Random class method nextInt(). The left and right child of course will be null at this point. Now your node is ready to insert into the Treap. (Note that we won't worry about whether a priority might be a duplicate of another priority already in the Treap. The heap order property is: parent priority >= child priority.)
Insert the new node into the Treap, according to normal BST-style insert on the keys. (Note that we do not allow duplicate keys in BSTs. So if when doing the BST insert you find that the key to be added is already present, simply return because the insert is already done.)
Once the new node is in place, use AVL rotations to fix any problems with the heap order property and the inserted node (i.e., use AVL rotation to 'bubble-up' the new node if its priority is greater than that of its parent).

NOTE: Your Treap node does not require a parent pointer.

UPDATE 10/23/08: Please see Tuesday's lecture slides (or the webboard, or Wednesday's discussion) for explanation of how the iterator should work. It is required that the iterator operate efficiently, as described in lecture. (for example, the iterator is not allowed to pre-fetch everything into an array and then return one by one on each next() call)

Once you have implemented your TreapSet class, you will benchmark it against the native TreeSet (red-black tree) implementation.

Benchmarking

Your program usage should be as follows:

% java BenchMark <T> <insertions> <searches>

% java BenchMark

In the first case, T is a single capital letter, either "S" for String or "I" for int, and it indicates the data type of the data in the input files (note that your treap class must use generics, so it will be able to accept any Comparable data type, not just int and String). <insertions> is a name of a text file that contains a list of all the insertions to the tree, in order, one on each line. The file is a text file containing a list of the keys to search for, one on each line. Insert all the keys in the order given, the perform the searches.

In the second case, you should just select random integer values for the keys and searches.

In both cases, perform a series of experiments where the size of the tree is ever increasing. Only do the first 7 insertions, then do all the searches and output the benchmark results. Then do 15 insertions, then 31, and so on, in the pattern 2^i - 1, from i=2 to i=14 (or until you run out of input in the file, if doing the file-based option).

Benchmarking is done by counting the number of actual number of comparisons performed for an individual find operation. Do this by adding instrumentation code to the method that does the comparisons. Keep track of the min, max and average number of comparisons per search. Keep separate the statistics for successful and unsuccessful finds (i.e., key is present or not present) and report them separately (see sample below).

Do all experiments on both the TreeSet (red-black tree) and Treap.

Output your benchmark results in a a nice format with columns:

Successful finds; number of comparisons MIN/AVG/MAX: 
Statistics collected over 16384/N runs, for each N.
	        Treap           TreeSet

N=00007: 	01/03/04 	01/03/07 	
N=00015: 	01/04/06 	01/04/11 
N=00031: 	01/05/08 	01/05/14 
N=00063: 	01/06/10 	01/07/16 
N=00127: 	01/07/12 	01/08/19 
N=00255: 	01/08/14 	01/09/23 
N=00511: 	01/09/16 	01/11/23 
N=01023: 	01/10/18 	01/12/24 
N=02047: 	01/11/20 	01/14/28 
N=04095: 	01/12/22 	01/15/29 
N=08191: 	01/13/24 	01/16/34 
N=16383: 	01/14/26 	01/18/34

Unsuccessful finds; number of comparisons MIN/AVG/MAX: 
Statistics collected over 16384/N runs, for each N.

		Treap           TreeSet
N=00007: 	01/03/04 	01/03/07 	
N=00015: 	01/04/06 	01/04/11 
N=00031: 	01/05/08 	01/05/14 
N=00063: 	01/06/10 	01/07/16 
N=00127: 	01/07/12 	01/08/19 
N=00255: 	01/08/14 	01/09/23 
N=00511: 	01/09/16 	01/11/23 
N=01023: 	01/10/18 	01/12/24 
N=02047: 	01/11/20 	01/14/28 
N=04095: 	01/12/22 	01/15/29 
N=08191: 	01/13/24 	01/16/34 
N=16383: 	01/14/26 	01/18/34

In your README, include a brief discussion of your results and any patterns you see. We will provide you with pairs of input files to include in your discussion, and explain more of the details about the README on the webboard. Generally, we're looking for you to reflect on questions such as: Do your results match the big-O analysis? Graph your results and comment on the growth of the function as N increases. README can be in Open Office Document, MSWord Document, or PDF format (please add appropriate file extension, e.g., README.pdf).

UPDATE 10/21/08:

Here are the promised details about what to put in your README:

There are two sets of input files in the /home/linux/ieng6/cs100f/public/p2 directory on ieng6. Each is labeled with a file for the keys and file(s) for the searches that go along with those keys. You should run your BenchMark program once on each pair (that's 4 runs total--3 for input set 1 and 1 for input set 2). Input set 1 should be treated as integers and input set 2 should be treated as Strings.

Answer the following questions in your README:

Copy & paste all the printed information from your Benchmark results (the four tests described above), clearly label which results are which.
Make two line graphs (one for inputset 1 and one for inputset 2), with N on the x-axis and # of comparisons on the y-axis. There should be 1 line for each tree type's results (TreapSet and TreeSet) on each set of searches (so 2*3=6 lines of results for inputset1), plus the line y = ln(x) (for comparison purposes).
Answer in a few sentences each:
How does TreapSet compare with TreeSet in # of comparisons? (consider each of MIN, AVG, and MAX, and change with growing N)
Comment on whether or not there is a difference in performance between the String and Integer input sets.
Does it appear from your benchmark results that TreapSet and TreeSet are achieving the desired O(logN) performance on the find operation? Explain.

Guidelines

You must work in teams of 2 people.
Include a file named README, which contains the names of your team members, and your benchmarking results and analysis/discussion.
Your code must be thoroughly documented with javadoc.
Use good OO design and engineering practice. Use exceptions where appropriate. Design your methods and data structures BEFORE you start coding.
You should have at least two source files:

TreapSet.java: all of the code to implement your TreapSet class should go here.
BenchMark.java: your program to compute benchmarks on TreapSet and TreeSet should go here.
README

Turning in

When your program is finished, create a tar file including your source code and class files by running:

tar czvf LASTNAME1.LASTNAME2.tar.gz *.java *.class README

Then, submit your tar file by running:

turnin -c cs100f -p p2 LASTNAME1.LASTNAME2.tar.gz