/**
 * BinaryTree.java
 *
 * Last modified 10/30/08
 */

package lab08;

import java.awt.*;

/**
 * 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) {

        // STUB -- implement this method
    }

    /**
     * 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) {

        return 0;  // STUB -- remove this line and implement method
    }

    /**
     * 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;
    }

    /**
     * Renders the binary tree in the window using the specified
     * <B>Graphics</B> object, at the specified location.
     * @param g <B>Graphics</B> object used for rendering within
     *   app window.
     * @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 window using the specified
     * <B>Graphics</B> object, at the specified location.
     * @param g <B>Graphics</B> object used for rendering within
     *   app window.
     * @param winSize Dimensions (width, height) of the display area.
     * @param startPoint location specifying the "start"
     * point for rendering the binary tree. 
     * In this implementation, this point denotes 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;
            recursivePaint (root, level, g, curPoint);
        }
    }

    private static void recursivePaint (
        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];

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