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 and provide size() and iterator() methods. The set that you return from the iterator should have an O(1) size, that is, it is just a wrapper for your SkipList. In sun's terms, the set will be '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 entrySet() methods, which means in, particular that you don't have to deal with add or remove. Please note that the the skiplist tower height should be at least 10, and, if you choose to implement it with a maximum tower height, the maximum must be at least 20. 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