B+ Tree Implementation Requirements

Your B+ tree is required to implement the SortedMap interface in the java.util package. (In earlier versions of JAVA, we would have had you extend the Dictionary class but it has become deprecated and replaced by the Map and SortedMap interfaces.)

A Map, in short, is:

An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. ⁴

The SortedMap extends the Map interface to further specify:

A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys (see the Comparable interface), or by a comparator provided at sorted map creation time. ⁵

Since a B+ tree guarantees that the actual values, in this case what we've called ``search keys'' will be stored in sorted order in the external/leaf nodes, the SortedMap interface is the most appropriate choice for allowing us to design our B+ tree so that it can be used in place of any other data structure that implements the SortedMap interface.

By requiring that you implement the SortedMap interface, we can test your B+ tree separately from your code! That is, we will write our own Mediator object which does something that requires the use of a SortedMap. We will plug your B+ tree into this Mediator to test it beyond the scope of the commands for Part 2.

You must adhere to the following rules for your B+ tree:

1. Names: Your class should be called "BPTree" and be contained in a file named "BPTree.java"
2. Constructors: You must minimally implement the following four constructors:
   • BPTree() // defaults to order 3, assumes added elements implement the Comparable interface
   • BPTree(Comparator c) // defaults to order 3, uses a Comparator and never tries to cast an added object to a Comparable
   • BPTree(int order) throws IllegalArgumentException // initalizes the tree to the specified order and assumes added elements implement the Comparable interface; throws IllegalArgumentException if order is less than 3
   • BPTree(Comparator c, int order) throws IllegalArgumentException // initalizes the tree to the specified order and uses a Comparator and never tries to cast an added object to a Comparable; throws IllegalArgumentException if order is less than 3

To make your life easier, we won't be asking you to actually implement the headMap, tailMap, or subMap functions. If someone calls these functions, you may simply throw an UnsupportedOperationException and move on with life like this:

		public SortedMap headMap(Object key)
		{
			// you don't need to specify that this exception
			// is thrown in the function signature since it
			// is an unchecked exception
			throw new UnsupportedOperationException("Not required");
		}

For Part 2, you may also throw an UnsupportedOperationException for the remove method as this will not be required until Part 3.

Also be sure that your BPTree.entrySet().iterator(), BPTree.keySet().iterator, and BPTree.values().iterator() calls return correctly working Iterators.

For any function in Map/SortedMap that takes a "key" as a parameter make sure that your functions will work if an object of type "String" is passed in as the parameter. For any function in Map/SortedMap that takes a "value" as a parameter make sure that your functions will work if an object of generic type "Object" is passed in as the parameter. This means that you should never try to cast your "value" parameter to type "Site". A good way to make sure that you did not do this would be to try to save objects of type Integer to your B+ tree during testing. (HINT: A random number generator, like Math.random(), would also make generating test data very easy. You could easily generate large sets of input that you will be quickly able to analyze for correct sorted order.)

There are ways to code your B+ tree to accept a "key" parameter of type Object and using dynamic type checking determine the best method to generate a guide value. This is the recommended method for implementation. However, you are minimally required to accept objects of type String for all parameters named "key".

We also promise that when testing your SortedMap interface we will only try to insert homogenously typed objects. That is, if we have inserted numerous Integer values into a tree, we won't try to insert a Double or Site into the same tree. Having values of different types in your leaves may or may not be a problem given your design, but the behavior for comparing a Site object to an Integer, for instance, is undefined so we won't be testing it.

(Note that the Map/SortedMap "key" is the same as the guide value discussed in lectures.)

Your B+ tree is not required to support null keys or values, however you may choose to do so. If a null values are ever passed in for a "key" or "value" parameter you are permitted to throw a NullPointerException if your implementation does not support null values.

You can find the exact specifications for the SortedMap interface in the JAVA API at:

http://java.sun.com/j2se/1.4.1/docs/api/java/util/SortedMap.html

One hint if anyone really likes a class name other than BPTree: you can just add an extra BPTree.java file with the following contents and you'll be set:

//file BPTree.java

public class BPTree extends YOURNAME
{
public BPTree(){super();}
public BPTree(Comparator c){super(c);} 
public BPTree(int order){super(order);}
public BPTree(Comparator c, int order){super(c,order);}
}

Web Accessibility