/* T15n02 - OK, let's deal with the use of null references in the last
 * example.
 *
 * The idea is that having to check references to see if they exist is
 * inconsistent with the idea that everything's an object.  If we don't
 * have nulls to mark the fringe of a tree, then we have to have an
 * object reference instead.  Further, we want this object to respond to
 * the messages that the preceding objects within the tree structure
 * already understand.  Of course, the fringe nodes won't perform the
 * same actions as 'regular' tree nodes in all cases.
 *
 * If you're into software design patterns, this one is called the "Active
 * Sentinel Design Pattern."  A sentinel is just a marker, or flag, that
 * indicates the end of a sequence.  For instance, in a text file of data,
 * placing a newline character after the last character of data on a line
 * creates an 'end of line' sentinel.
 * In the context of BSTs, these fringe nodes are our sentinels, as they
 * mark the bottom of the tree.
 *
 * With a little thought, it's easy to see that there's no need to replace
 * each null reference with a reference to a unique sentinel node; we can 
 * instead have just one sentinel node, and all of the formerly null 
 * references will now just reference it.
 *
 * To use this idea effectively, we have to change our method implementations.
 * In the previous example, insert() and inOrder() were methods of the
 * tree, and the BinaryNodes were blissfully unaware of them.  Now we'll
 * allow the nodes to participate in these operations; after all, each
 * node is the root of a subtree, so why not think of each node as a
 * tree (if a somewhat informal one)?  As trees, the nodes need to know about
 * the tree operations.
 *
 * Continuing with that thought:  If we are to have the sentinel node 
 * respond as if it is also a subtree, it will also have to respond to
 * the same messages, albeit in different ways.
 *
 * Now BinarySearchTree has only the "store front" methods, because the
 * actual work has been pushed off onto the nodes.  In BinaryNode, note
 * the implementation of insert() -- we are no longer checking for a null
 * reference.  We no longer have null references in BinaryNodes, and
 * insert() will just invoke the sentinel's insert() method when the
 * fringe is reached.  That's where new tree nodes are created.
 *
 * So what does this change buy us?  A cleaner design, one that eliminates 
 * all null tests, thus saving a little effort during execution.
 */

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

public class T15n02
{
    public static void main (String[] args)
    {
        BinarySearchTree<Integer> tree = null;

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

class BinarySearchTree< E extends Comparable<E> >
{
    protected BinaryNode<E> root;  

    public BinarySearchTree ()
    {
        root = new SentinelNode<E> ();
    }

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

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


    class BinaryNode< E extends Comparable<E> >
    {
        E             data;       
        BinaryNode<E> leftChild,  
                      rightChild; 

        public BinaryNode (E newData)
        {
            data = newData;
            leftChild = rightChild = null;   // ack!  a null!  Ah, but wait...
        }

        public BinaryNode<E> insert (E 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< E extends Comparable<E> > extends BinaryNode<E>
    {
        public SentinelNode ()
        {
            super(null);
        }

        public BinaryNode<E> insert (E newData)
        {
            BinaryNode<E> node = new BinaryNode<E> (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
        } 
    }

}