SkipList.java

As with last semester there is a requirement that some of your data structure code implement a standard interface and to follow certain common practices. This will allow the TA to include your data structure in his own code. All of your dictionary classes this semester (currently a skiplist, and later a 2-3 or bplus tree) will implement java's Map interface specified at:

http://java.sun.com/j2se/1.4/docs/api/java/util/Map.html

This differs slightly from last semester when students had to partially support the sortedMap interface. Instead, you will just implement the Map interface, but you will still hold to the general contract given in the api for SortedMap. You will have to support at least the following constructors:

SkipList() //assumes elements Comparable SkipList(Comparator c) //assumes elements are Objects, uses c to compare

For this project you should not have any public methods that are not specified by the sortedMap interface(other than constructors). At the end of P2 it should be transparent to your project whether you are using TreeMaps or SkipLists (this requires that you not use the headMap(), tailMap(), subMap(), or comparator() methods provided by the treeMap class). Since the Adjacency List will not be tested in project 2, you will be required to *never* use any of java's SortedMaps or SortedSets in your own code (something easily checked with grep). Whenever you feel the need for a sorted data structure, use your skiplist ;)

The easiest way to implement the Map interface is to extend AbstractMap, which requires only that you implement the entrySet() method. The easiest way to write the entrySet is to extend AbstractSet, which requires you to implement size() and an iterator for your Map. The set that you return should have an O(1) size, that is, it is just a wrapper for your SkipList. In sun's terms, the set will eb 'backed' by the SkipList, so that changes in one are reflected in the other. However, you do not have to support any of the optional operations for sets in your entreSets, which means in particular that you don't have to deal with add or remove.

I don't have time for much more on this here, but check out both the java api and the actual TreeMap.java included with the SDK distribution(in a file src.zip in the root install folder, for win32 anyway). I'm sure much will appear about this in the newsgroup and in office hours ;)

The class must be named SkipList.java (note the case) and be located in a package called cmsc420. For a tutorial on packages see:

http://java.sun.com/docs/books/tutorial/java/interpack/

Web Accessibility