// BinaryTree.java (Lab 09 Version)
// Last modified 11/07/08

package lab09;

import java.awt.*;

import lab07.Queue;

/**
 * This class represents an ordered binary tree. The {@link Node}
 * objects that compose the tree elements each contain data of type
 * {@link Item}, as well as links to the left and right child
 * nodes. Each {@link Item} object contains a unique object that
 * must implement the {@link java.lang.Comparable} interface, as well
 * as an associated occurrence counter indicating the number of 
 * times that object has been inserted into the tree.
 */
public class BinaryTree {

    private Node root;
    private int itemCount;

    /**
     * Creates an empty BinaryTree object.
     */
    public BinaryTree () {
        root = null;
        itemCount = 0;
    }

    /**
     * Inserts a new data value into the binary tree.
     * @param value The data value to be added.
     */
    public void insert (String value) {
        Node curNode = root;
        Node prevNode = null;
        int result = 0;
        
        while (curNode != null) {
            Item curItem = (Item) curNode.getData();
            String curValue = curItem.getValue();
            result = value.compareTo (curValue);

            if (result == 0) {
                curItem.incOccurrences();
                return;
            }
            else if (result < 0) {
                prevNode = curNode;
                curNode = curNode.getLeftChild();
            }
            else {
                prevNode = curNode;
                curNode = curNode.getRightChild();
            }
        }

        Node newNode = new Node (new Item(value), null, null);
        if (prevNode == null) {
            root = newNode;
        }
        else if (result < 0) {
            prevNode.setLeftChild(newNode);
        }
        else {
            prevNode.setRightChild(newNode);
        }
        itemCount++;
    }

    /**
     * Searches the binary tree for a node containing an item
     * with the specified value. If found, returns the occurrence
     * count for that value. Otherwise, returns 0. 
     * @return Occurrence count for the specified value.
     */
    public int getOccurrences (String value) {
        Node curNode = root;
        
        while (curNode != null) {
            Item curItem = (Item) curNode.getData();
            String curValue = curItem.getValue();
            int result = value.compareTo (curValue);

            if (result == 0) {
                return curItem.getOccurrences();
            }
            else if (result < 0) {
                curNode = curNode.getLeftChild();
            }
            else {
                curNode = curNode.getRightChild();
            }
        }
        return 0;
    }

    /**
     * Removes all nodes from the binary, restores it to its
     * orginal empty state.
     */
    public void removeAll () {
        root = null;
        itemCount = 0;
    }

    /**
     * Indicates if binary tree is empty.
     * @return <B>true</B> if empty, <B>false</B> otherwise.
     */
    public boolean isEmpty () {
        return (itemCount == 0);
    }

    /**
     * Returns number of nodes in binary tree.
     * @return Number of nodes.
     */
    public int size () {
        return itemCount;
    }

    // --------------------------------------------------------------------
    //        START OF WORK AREA -- IMPLEMENT ALL STUBBED METHODS
    // --------------------------------------------------------------------

    public Queue listAscending () {
        Queue queue = new Queue();
        recursiveListAscending (root, queue);
        return queue;
    }
    
    private static void recursiveListAscending (Node root, Queue queue) {

        // STUB -- implement this method, using recursion
    }
    
    public Queue listDescending () {
        Queue queue = new Queue();
        recursiveListDescending (root, queue);
        return queue;
    }
    
    private static void recursiveListDescending (Node root, Queue queue) {

        // STUB -- implement this method, using recursion
    }
    
    public String getMinValue ( ) {
        if (root == null) {
            throw new IllegalStateException ("Binary tree is empty");
        }

        return null;      // STUB -- replace this line and implement
    }
    
    public String getMaxValue ( ) {
        if (root == null) {
            throw new IllegalStateException ("Binary tree is empty");
        }

        return null;      // STUB -- replace this line and implement
    }
    
    /** Returns the depth (aka height) of the binary tree. For an
     * empty tree, the depth is zero. Otherwise it is defined to
     * be the maximum level number of all the nodes in the tree,
     * where the root is at level 1.
     * @return The depth of the tree.
     */
    public int getDepth ( ) {
        return recursiveGetDepth (root);
    }

    private static int recursiveGetDepth (Node root) {
        
	return 0;         // STUB -- replace this line and implement
    }

    // --------------------------------------------------------------------
    //                          END OF WORK AREA
    // --------------------------------------------------------------------

    /**
     * Renders the binary tree in the display area.
     * @param g Graphics context used to render tree in display area.
     * @param winSize Dimensions (width, height) of the display area.
     */
    public void render (Graphics g, Dimension winSize) {
        Point startPoint = new Point (winSize.width / 2, 50);
        render (g, winSize, startPoint);
    }

    /**
     * Renders the binary tree in the display area at a specified
     * location.
     * @param g Graphics context used to render tree in display area.
     * @param winSize Dimensions (width, height) of the display area.
     * @param startPoint Location of the base of an external arrow
     * to the root node, or a null link if the tree is empty.
     */
    public void render (Graphics g, Dimension winSize, Point startPoint) {
        String rootLabel = "Root";
        Font oldFont = g.getFont();
        g.setFont (new Font ("Arial", Font.BOLD, 16));
        FontMetrics fm = g.getFontMetrics ();
        int labelWidth = fm.stringWidth (rootLabel);
        g.drawString (rootLabel,
            startPoint.x - labelWidth / 2, startPoint.y - 10);
        g.setFont (oldFont);
        
        if (root == null)
            Node.drawNullLink (g, startPoint);
        else {
            Node.drawLink (g, startPoint, 0, 0);
            Point curPoint =
                new Point (startPoint.x, startPoint.y + Node.LINK_HEIGHT);

            int level = 1;
            recursiveRender (root, level, g, curPoint);
        }
    }

    private static void recursiveRender (
        Node root, int level, Graphics g, Point startPoint) {

        if (root != null) {
            Point [] childPoints = root.render (g, startPoint, level); 
            Point lchildPoint = childPoints [0];
            Point rchildPoint = childPoints [1];

            recursiveRender (root.getLeftChild(),  level + 1, g, lchildPoint);
            recursiveRender (root.getRightChild(), level + 1, g, rchildPoint);
        }
    }
}