import java.io.IOException;
/*
State Design Pattern for 2-3-4 trees.

This is an object-oriented implementation of the algorithm outlined in
Sedgewick's "Algorithms in C++", Addison-Wesley 1992, pp. 215-219.
Other elucidating discussions of balanced trees can be found in
Stubbs/Webre's "Data Structures", and Aho/Hopcroft/Ullman's "Data Structures
and Algorithms".

6/25/97 DXN
Copyright 1997,  Dung X. Nguyen - All Rights Reserved.
*/
public class Tree234
{
   /** @SBGen Variable (,,,64)   */
	private ANode234 _rootNode;

  public static void main (String[] args) throws IOException
  //Driver for Tree234 to test itself.
  {
	System.out.println ("Empty 2-3-4 tree:");
	Tree234 myTree = new Tree234 ();
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
	System.out.println ("Insert -10...");
	myTree.insert (new Integer (-10));
	myTree.draw ();
	System.out.println ("\n\n");
	System.out.println ("Insert -5...");
	myTree.insert (new Integer (-5));
	myTree.draw ();
	System.out.println ("\n\n");
 	System.out.println ("Insert 0...");
	myTree.insert (new Integer (0));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 5...");
	myTree.insert (new Integer (5));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 15...");
	myTree.insert (new Integer (15));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 20..");
	myTree.insert (new Integer (20));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 25...");
	myTree.insert (new Integer (25));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 30...");
	myTree.insert (new Integer (30));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 35...");
	myTree.insert (new Integer (35));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 40...");
	myTree.insert (new Integer (40));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to continue...");
   System.in.read ();
   System.in.read ();
	System.out.println ("Insert 45...");
	myTree.insert (new Integer (45));
	myTree.draw ();
   System.out.println ("\n\nPress Enter to quit...");
   System.in.read ();
   System.in.read ();
  }

  public Tree234 ()
  //Post:  the Tree234 exists and is empty.
  {
  	   _rootNode = EmptyNode.Singleton;
  }

  public Tree234 (Integer n)
  //Pre:  n != null
  //Post: the Tree234 exists and contains exactly one data element n, an empty
  //  left subtree, and an empty right subtree.
  {
  	_rootNode = new Node2 (n);
  }

  public final boolean isEmpty ()
  {
	  return _rootNode.isEmpty ();
  }

  public final void insert (Integer n)
  //Pre : n != null
  //Post: the Tree234 contains n without duplication.
  {
	  _rootNode.insert (this,n);
  }

  public final void draw ()
  {
    drawAtLevel (0);
  }

  ///////////////////////////////////////
  //Not visible outside of package

  Tree234(ANode234 root)
  {
    _rootNode = root;
  }

  Tree234(Tree234 lTree, Integer n, Tree234 rTree)
  {
    _rootNode = new Node2 (lTree, n, rTree);
  }

  final void drawAtLevel (int level)
  {
	  _rootNode.drawAtLevel (level);
  }

  final void changeRoot (ANode234 newRoot)
  {
	  _rootNode = newRoot;
  }

  final ANode234 root()
  {
	  return _rootNode;
  }

  final void insertHelper (Tree234 parent, Integer n)
  {
    _rootNode.insertHelper (parent, this, n);
  }

  final void attach (Tree234 lTree, Integer n, Tree234 rTree)
  {
    _rootNode.attach (this, lTree, n, rTree);
  }
}