CpSc 241, Section 2
                             Assignment 3 
                            9 February 2001


Due: Thursday, February 22 at 11:59 p.m.

	Not accepted late.

Total point value of assignment:  100 points

This assignment is to be done INDIVIDUALLY.  Some parts of this design
will be changed at different stages of the assignment.  For now, we are
designing a framework that will be used internally in a computer.  If
we change the design to write to disk, modifications will need to be
made.  Also, at any stage in the design we may, as a class, decide 
that some choices should be changed in order to improve the basic design. 

Your test program should insert at least L+1 items in a LeafNode.
When the (L+1)st item is inserted, the LeafNode splits into two
LeafNodes, each containing (L+1)/2 keys.  At the same time, a TreeNode
is created and LeafNode references in the TreeNode set to reference
the LeafNodes.  The keys in the leafList will always be sorted in
ascending order.

Create a directory, A3, which will contain all parts of this assignment.
Construct the following classes for inclusion in A3

	LeafNode
	TreeNode
	BTree

Your BTree class will have the following instance variables

	int M // the maximum number of children a TreeNode can have
	int L // the maximum number of keys in a LeafNode
	Object root // null if the tree is empty
	LeafNode leafList // references the first LeafNode in the BTree
	int keyCount // the number of keys stored in the BTree

at least the following constructors 

	public BTree ( )
	// constructs an empty BTree with M set to 5 and L set to 7

	public BTree ( int M, int L )
	// constructs an empty BTree with M and L as parameters

and the following methods

	public Object insert ( Comparable item )
	// pre:  the BTree exists
	// post:  item is inserted in the BTree

	public boolean isEmpty ( )
	// post:  returns true if BTree is empty; otherwise, returns false

	public int size ( )
	// post:  returns count of the number of keys stored in BTree

	public String toString ( )
	// post:  returns a printable representation of the BTree

	public static void main ( String [ ] args )
	// test driver 

Your LeafNode class will have at least the following instance variables

	int keyCount;  // the number of keys stored in the LeafNode
	Comparable [ ] key;  // the keys
	LeafNode next;  // reference to next LeafNode

and the following methods

	public LeafNode ( int L )  // constructor
	// pre:  L > 0
	// post:  Creates an empty LeafNode with space for L keys

	public void insert ( Comparable item )
	// pre:  LeafNode is not full
	// post:  item is inserted in ascending order
	//        if item is a duplicate key, item is not inserted

	public boolean isFull ( )
	// post:  returns false if a key can be inserted in LeafNode;
	//        otherwise, returns true.

	public String toString ( )
	// post:  returns a String representation of a LeafNode

********************************************************************************
You may find the following helpful:

     ( op1 instanceof op2 ) returns true when op1 and op2 are assignment compatible
     For example, "if ( root instanceof LeafNode ) ..." 
        returns true if root references a LeafNode and false otherwise.