Programming Project

COP$3503$ Computer Science II $-$ Summer $2023$

Assignment

Implement a skip list as a genericized SkipListSet collection in Java. Your class must implement SortedSet $($and hence Set, Collection and Iterable$).$

A program that has your class available will be able to instantiate a SkiplistSet for any Comparable class, and treat it like any other sorted collection $($as long as it uses classes with a natural order$).$

Structure

You'll create three things: a set class, an iterator class, and an item$-$wrapper $($node$)$ class. You'll almost certainly want to make the iterator and item$-$wrapper classes internal private classes of the set class. I'll call the iterator and itemwrapper classes SkipListSetIterator and SkipListSetItem, but you can call them anything you like.

SortedSet is a Java interface. That means it specifies a set of methods that you must implement to make it work. Your SkiplistSet will implement it$.$

What this means is you're not calling methods from SortedSet yourself $-$ you're writing them, so that a program that wants to use your SkipListSet can work with it the same way it would any other SortedSet, like TreeSet.

Likewise, Iterator is another Java interface. Your SkipListSetIterator will implement the methods that it requires.