CpSc 241, Section 2
                             Assignment 4 
                             6 March 2001


Due: Thursday, March 15 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. 

Continuation of Assignment #3.  Continue to use directory A3.
All classes that are required for execution of the BTree must be
included in A3 and submitted with this assignment.


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 find ( Comparable item )
    // post:  returns true if item is in BTree;  otherwise, returns false.

    public void printSequential ( )
    // post:  prints the contents of all leaves
  
	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

********************************************************************************

Grading considerations:

	Program attempts to produce a BTree and compiles without error (10 pts.)

	Style requirements

	insert works for multiple inserts.

	find works correctly.

    printSequential works correctly.

	Code is reasonable efficient.


********************************************************************************
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.