package edu.princeton.cs.algs4.growingtree.framework;
/*
 * @(#)TreeHead.java
 *
 * Last Modified: 9/15/01
 */

import java.awt.*;
import java.util.*;


/**
 * The TreeHead interface extends the Tree interface. The TreeHead is used as the top <b>null</b> node
 * of any given Tree. This implementation makes many necessary methods easier to perform with a null
 * head node. The head node must implement all pertinent methods defined in the interface. <p>
 *
 * Generally, the TreeHead extends from the Tree in most cases and simply includes more defined methods.
 * The constructor generally constructs the Tree super construction first and then proceeds to the Head
 * defined methods. Consequently, the TreeHead is simply an extended <code>Tree</code> with null information.
 *
 * @author Corey Sanders
 * @version 1.2 9/15/01
 */
public interface TreeHead<P extends NodeProperties> extends Tree<P>{


	/**
	 * String representing the waiting action of <code>rotateUp</code>. Requires an accompanying node.
	 */
	public static final String ROTATE_UP = "Rotate Up";

	/**
	 * String representing the waiting action of <code>rotateToTop</code>. Requires an accompanying node.
	 */
	public static final String ROTATE_TO_TOP_NODE = "Rotate To Top";
	/**
	 * String representing the waiting action of <code>rotateUpDouble</code>. Requires an accompanying node.
	 */
	public static final String ROTATE_UP_DOUBLE = "Rotate Up Double";
	/**
	 * String representing the waiting action of <code>splay</code>. Requires an accompanying node.
	 */
	public static final String SPLAY_NODE = "Splay";
    /**
     * String representing the waiting action of <code>remove</code>. Requires an accompanying node.
     */
    public static final String REMOVE_NODE = "Remove Node";
    /**
     * String representing the waiting action of <code>insert</code>. Requires an accompanying node.
     */
    public static final String INSERT_NODE = "Insert Node";

    /**
     * String representing the waiting action of <code>search</code>. Requires an accompanying node.
     */
    public static final String SEARCH = "Search";

    /**
     * String representing the waiting action of <code>select</code>. Requires an accompanying node.
     */
    public static final String SELECT = "Select";
    
    /**
     * String representing the waiting action of swap. Requires an accompanying node.
     */
    public static final String SWAP = "Swap";

    /**
     * String representing the waiting action of freeze
     */
    public static final String FREEZE = "Freeze";
    
    /**
     * String representing the waiting action of <code>partition</code>. Requires an accompanying <code>NodeAndKey</code> object (Inner class of BSTTreeHead).
     */
    public static final String PARTITION_NODE = "Partition Node";

    /**
     * String representing the waiting action of <code>balance</code>. Requires an accompanying <code>NodeAndKey</code> object (Inner class of BSTTreeHead).
     */
    public static final String BALANCE_NODE = "Balance Node";

    /**
     * String representing the waiting action of <code>traverse</code>. Requires an accompanying <code>Integer</code> object.
     */
    public static final String TRAVERSE = "Traverse Tree";


    /**
     * String representing the waiting action of <code>changeDisplay</code>.
     */
    public static final String CHANGE_DISPLAY = "Change Display";


	/**
	 * Traverse type preorder.
	 */
	public static final int PREORDER_TRAVERSAL = 1;
	/**
	 * Traverse type inorder.
	 */
	public static final int INORDER_TRAVERSAL = 2;
	/**
	 * Traverse type postorder.
	 */
	public static final int POSTORDER_TRAVERSAL = 3;
	/**
	 * Traverse type levelorder.
	 */
	public static final int LEVELORDER_TRAVERSAL = 4;


	/**
	 * Returns true if the <codeTreeHead</code> is empty, indicating no Child node, and a level of 0.
	 *
	 * @return true if the <code>TreeHead</code> is empty.
	 */
	public boolean isTreeEmpty();

	/**
	 * Resets the lowest level of the <code>Tree</code>.
	 */
	 public void resetTreeLevel();

	/**
	 * Gets the lowest level of the Tree. A level of 0 indicates an empty tree.
	 *
	 * @return integer level set for the <code>Tree</code>.
	 */
	 public int getTreeLevel();

	/**
	 * Fixes the lowest level of the <code>Tree</code>.
	 */
	public void fixLevel();

	/**
	 * Sets the child of the TreeHead. The child is the beginning of the Tree nodes.
	 *
	 * @param child <code>Tree</code>, beginning the <code>Tree</code> nodes.
	 */
	public void setChild(Tree<P> child);

	/**
	 * Gets the child of the TreeHead. The child is the beginning of the Tree nodes.
	 *
	 * @param child <code>Tree</code>, beginning the <code>Tree</code> nodes.
	 */
	public Tree<P> getChild();



	/**
	 * Adds an TreeMessageListener from the tree, according to
	 * the TreeMessageListener interface and the <code>TreeMessageEvent</code>.
	 *
	 * @param l the listener added recieves the TreeMessageEvents occuring.
	 */
	public void addTreeMessageListener(TreeMessageListener l);

	/**
	 * Removes an TreeMessageListener from the tree, according to
	 * the TreeMessageListener interface and the <code>TreeMessageEvent</code>.
	 *
	 * @param l the listener removed from recieving the TreeMessageEvents occuring.
	 */
	public void removeTreeMessageListener(TreeMessageListener l);



	/**
	 * Adds the comaparable object keyInsert to the tree using its <i> natural ordering </i>.
	 * The value, valueInsert is added with the key to the node.
	 *
	 * @param keyInsert	comparable object which is added to the tree.
	 * @param valueInsert Object that accompanies keyInsert in the node.
	 *
	 * @return boolean true if this collection changed as a result of the call.
	 *
	 * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the map.
	 * @throws NullPointerException key is <tt>null</tt>.
	 */
	public boolean insert(KeyType keyInsert, Object valueInsert) throws ClassCastException, NullPointerException;


	/**
	 * Removes the given node from the tree. The accompanying value is also
	 * removed from the tree and the node is deleted.
	 *
	 * @param node the <code>Tree</code> node to be removed from the tree.
	 *
	 * @throws NullPointerException node is <code>null</code>
	 */
	public void remove(Tree<P> node) throws NullPointerException;

	/**
	* Removes the comaparable object keyRemove from the <code>BSTTree</code> using its <i> natural ordering </i>.
	* If the method is successful in removing the element, true is returned.
	*
	* @param keyRemove	comparable object which is removed from the tree.
	*
	* @return boolean true if this collection changed as a result of the call.
	*
	* @throws ClassCastException key cannot be compared with the keys
 	*		  currently in the map.
	* @throws NullPointerException key is <tt>null</tt>.
	*/
	public boolean remove(KeyType keyRemove) throws ClassCastException, NullPointerException;


   /**
	* Searches for the comaparable object in the <code>Tree</code> using its <i> natural ordering </i>.
	* If the method is successful in finding the element, the item is returned. Otherwise, null is
	* returned.
	*
	* @param keySearch	comparable object which is search for within the tree.
	*
	* @return Tree element which matches the keySearch or null of the key is not present within the
	* tree.
	*
	* @throws ClassCastException key cannot be compared with the keys
 	*		  currently in the map.
	* @throws NullPointerException key is <tt>null</tt>.
	*/
	public Tree<P> search(KeyType keySearch) throws ClassCastException, NullPointerException;


	/**
	 * Partitions from the given node the keySelect value. Replacing the reference in the
	 * Tree to the given node, to the keySelectth item.
	 *
	 * @param node Tree which the partition occurs at.
	 * @param keySelect integer key selecting the count item.
	 *
	 * @return Tree that is the reference to the newly partitioned tree.
	 */
	public Tree<P> partition(Tree<P> node, int keySelect);

	/**
	* Selects the kth smallest item in the <code>Tree</code> using its <i> natural ordering </i> from the given node.
	* If the method is successful in finding the element, the item is returned. Otherwise, null is
	* returned if the integer is greater than the size.
	*
	* @param node Tree which the partition occurs at.
	* @param keySelect integer key selecting the count item.
	*
	* @return Tree element which matches the kth element or null if k > size.
	*/
	public Tree<P> select(Tree<P> node, int keySelect);

	/**
	 * Balances the entire tree.
	 *
	 */
	 public void balanceTree();

	/**
	 * Balances the tree, from the node downward.
	 *
	 * @param node the Tree node from which the balance occurs
	 */
	 public void balance(Tree<P> node);

	/**
	 * Returns the number of objects in the entire tree.
	 *
	 * @return the number of objects in the entire tree.
	 */
	public int size();

	/**
     * Clears the tree completely, removing all references to all nodes and all
     * values return to the default.
     */
	public void clear();


	/**
	 * Acts according to the String action passed. The method generally accompanies
	 * a <code>WaitingActionList</code> which keeps the list of actions, and calls the method when
	 * instructed to call the next action.
	 *
	 * @param action String action representing the next action for the TreeHead.
	 * @param elements elemetns to which the action could be occuring, depending on the type of action.
	 */
	public void waitingAction(String action, ActionElementType<P> element);

}