/* T06n04 - A detour to introduce another idea:  Abstract classes.
 * 
 * When you have several similar classes, rather than picking one and
 * having the rest inherit the common ideas from it, we can instead
 * create a super class and place the common details in it.  This
 * parent class is often not intended to be instantiated.  A nice way
 * to ensure that it can't be instantiated is to make it an abstract
 * class.  In Java, abstract classes can still have methods for subclasses
 * to inherit, but they can also have abstract (non-implemented; without
 * bodies) methods.  Why?  For one thing, a class with an abstract method
 * may not be instantiated.  But more practically, by providing such a
 * method, we are indicating that any subclass of the abstract class that
 * is meant to be instantiable must implement its own version of the
 * abstract method.
 *
 * In this version of our running example, we have added an 
 * AbstractBinaryNode class, which specifies that any subclass must
 * include an instance variable (data), an insert() method, and an 
 * inOrder() method.  Just to demonstrate an implemented method in an 
 * abstract class, we've also added a getter method.  With this new
 * parent class in place, we can have SentinelNode inherit from it 
 * instead of from BinaryNode.
 *
 * You might be surprised to see that an AbstractBinaryNode doesn't have
 * subtree references.  We don't need any there; when BinaryNode is
 * implemented, we include leftChild and rightChild, because they are
 * needed.  SentinelNode objects have no need for them.  We include the
 * data variable in AbstractBinaryNode because the implementation of
 * the getter requires it; without the getter, we could move it to
 * BinaryNode, too, as Sentinel has no need of it.  (Of course, if
 * we wanted to have a more generally useful abstract node class, we'd
 * probably include the subtree references.)
 * 
 * To further clean things up a bit, we've removed the constructor from
 * the SentinelNode class, because the default constructor is all that we
 * need.
 */

import java.io.*;
import java.util.*;

public class T06n04
{
    public static void main (String[] args)
    {
        BinarySearchTree tree = null;

        tree = new BinarySearchTree();
        tree.insert(new Integer (50));
        tree.insert(new Integer (40));
        tree.insert(new Integer (60));
        tree.insert(new Integer (45));
        tree.insert(new Integer (42));
        tree.inOrder();
        System.out.println("");
    }
}

class BinarySearchTree
{
    protected AbstractBinaryNode root; 

    public BinarySearchTree ()
    {
        root = new SentinelNode ();
    }

    public void insert (Comparable newData)
    {
        root = root.insert(newData);
    }

    public void inOrder ()
    {
        root.inOrder();
    }


    abstract class AbstractBinaryNode
    {
        Comparable data;              

        public Comparable getData ()      // implemented for use by subclasses
        {
            return data;
        }

        abstract public BinaryNode insert  (Comparable newData);
        abstract public       void inOrder ();

    }


    class BinaryNode extends AbstractBinaryNode
    {
        AbstractBinaryNode leftChild,  
                           rightChild; 

        public BinaryNode (Comparable newData)
        {
            data = newData;
            leftChild = rightChild = null;
        }

        public BinaryNode insert (Comparable newData)
        {
            if (newData.compareTo(data) < 0) {               // insert on left
                leftChild = leftChild.insert(newData); 
            } else {                                         // insert on right
                rightChild = rightChild.insert(newData);
            }
            return this;
        } 

        public void inOrder ()
        {
            leftChild.inOrder();
            System.out.print(data.toString() + " ");
            rightChild.inOrder();
        }

    }

    class SentinelNode extends AbstractBinaryNode
    {
        public BinaryNode insert (Comparable newData)
        {
            BinaryNode node = new BinaryNode (newData);
            node.leftChild = node.rightChild = this;    // nulls are replaced!
            return node;
        } 

        public void inOrder ()
        {
            // nothing to do, but the message still has to be received
        } 
    }

}