import java.util.*;

/**
 * This is a rough template for your B+ tree class. You may modify it
 * as you see fit. Just be sure that you implement all of the required
 * functions.
 */
public class BPTree implements SortedMap
{
	/**************************************************************
	* You are responsible for implementing the following functions.
	* You may add any other private/protected/public functions that you want.
	* You are allowed to change the parameter variable names.
	***************************************************************/

	/**
	 * Defaults to order 3, assumes added elements implement Comparable
	 */
	BPTree();

	/**
	 * Defaults to order 3, uses a Comparator and NEVER tries to cast 
	 * an added object to a Comparable.
	 * @param c The Comparator to use to sort objects.
	 */
	BPTree(Comparator c);

	/**
	 * Initalizes the tree to the specified	order and assumes added elements 
	 * implement the Comparable interface
	 * @param order The order to initalize the B+ tree with
	 * @throws IllegalArgumentException thrown if order is not >= 3
	 */
	BPTree(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.
	 * @param order The order to initalize the B+ tree with
	 * @throws IllegalArgumentException thrown if order is not >= 3
	 */
	BPTree(Comparator c, int order) throws IllegalArgumentException;

	/**
	 * You are responsible for implementing the following SortedMap
	 * functions. See http://java.sun.com/j2se/1.4.1/docs/api/java/util/SortedMap.html
	 * for the specification of each function.
	 */
	public Object firstKey();
	public Object lastKey();
	public Comparator comparator();
	public int size();
	public void clear();
	public boolean isEmpty();
	public boolean containsKey(Object key);
	public boolean containsValue(Object value);	
	public void putAll(Map map);
	public Object get(Object key);
	public Object put(Object key, Object value);
	
	// make sure BPTree.entrySet().iterator works correctly
	public Set entrySet();
	// make sure BPTree.keySet().iterator works correctly
	public Set keySet();
	// make sure BPTree.values().iterator works correctly
	public Collection values();

	public Object remove(Object key)	
	{
		throw new UnsupportedOperationException("Not supported in Part 2");
	}

	/**************************************************************
	* You are not responsible for the following SortedMap functions, 
	* although you are encouraged to implement these functions if you 
	* have time. Without implementing them, the BPTree cannot truely 
	* replace another SortedMap. If you decide to implement any of 
	* these functions, do NOT throw the UnsupportedOperationException.
	***************************************************************/
	public SortedMap headMap(Object arg0)
	{
		throw new UnsupportedOperationException("Not required");
	}

	public SortedMap tailMap(Object arg0)
	{
		throw new UnsupportedOperationException("Not required");
	}

	public SortedMap subMap(Object arg0, Object arg1)
	{
		throw new UnsupportedOperationException("Not required");
	}

}