package net.datastructures;
import java.util.Comparator;
import java.util.Iterator;

/**
  * Realization of a dictionary by means of a binary search tree.
  * @author Michael Goodrich, Eric Zamore
  */ 

// Realization of a dictionary by means of a binary search tree
public class BinarySearchTree extends LinkedBinaryTree implements Dictionary {
  // Instance variables:
  protected Comparator C;	// comparator
  protected Position actionPos;	// insertion node or parent of removed node
  protected int numEntries = 0;	// number of entries
  /** Creates a BinarySearchTree with a default comparator. */
  public BinarySearchTree()  { 
    C = new DefaultComparator(); 
    addRoot(null);
  }
  /** Creates a BinarySearchTree with the given comparator. */
  public BinarySearchTree(Comparator c)  { 
    C = c; 
    addRoot(null);
  }
  /** Nested class for location-aware binary search tree entries */
  protected static class BSTEntry implements Entry {
    protected Object key;
    protected Object value;
    protected Position pos;
    BSTEntry() { /* default constructor */ }
    BSTEntry(Object k, Object v, Position p) { key = k; value = v; pos = p;}
    public Object key() { return key; }
    public Object value() { return value; }
    public Position position() { return pos; }
  }
  // Auxiliary methods:
  /** Extract the key of the entry at a given node of the tree. */
  protected Object key(Position position)  {
    return ((Entry) position.element()).key();
  }
  /** Extract the value of the entry at a given node of the tree. */  
  protected Object value(Position position)  { 
    return ((Entry) position.element()).value(); 
  }
  /** Extract the entry at a given node of the tree. */  
  protected Entry entry(Position position)  { 
    return (Entry) position.element();
  }
  /** Replace an entry with a new entry (and reset the entry's location) */
  protected void replaceEntry(Position pos, Entry ent) {
    ((BSTEntry) ent).pos = pos;
    replace(pos, ent);
  }
  /** Check whether a given key is valid. */  
  protected void checkKey(Object key) throws InvalidKeyException {
    if(key == null)  // just a simple test for now
      throw new InvalidKeyException("null key");
  }
  /** Check whether a given entry is valid. */
  protected void checkEntry(Entry ent) throws InvalidEntryException {
    if(ent == null || !(ent instanceof BSTEntry))
      throw new InvalidEntryException("invalid entry");
  }
  /** Auxiliary method for inserting an entry at an external node */
  protected Entry insertAtExternal(Position v, Entry e) {
    expandExternal(v,null,null);
    replace(v, e);
    numEntries++;
    return e;
  }
  /** Auxiliary method for removing an external node and its parent */
  protected void removeExternal(Position v) {
    removeAboveExternal(v);
    numEntries--;
  }
  /** Auxiliary method used by find, insert, and remove. */
  protected Position treeSearch(Object key, Position pos) {
    if (isExternal(pos)) return pos; // key not found; return external node
    else {
      Object curKey = key(pos);
      int comp = C.compare(key, curKey);
      if (comp < 0) 
	return treeSearch(key, left(pos));	// search left subtree
      else if (comp > 0)
	return treeSearch(key, right(pos));	// search right subtree
      return pos;		// return internal node where key is found
    }
  }
  /** Adds to L all entries in the subtree rooted at v having keys
   * equal to k. */
  // Adds to L all entries in the subtree rooted at v having keys equal to k
  protected void addAll(List L, Position v, Object k) {
    if (isExternal(v)) return;
    Position pos = treeSearch(k, v);
    if (!isExternal(pos))  {  // we found an entry with key equal to k 
      addAll(L, left(pos), k);
      L.insertLast(pos.element()); 	// add entries in inorder
      addAll(L, right(pos), k);
    } // this recursive algorithm is simple, but it's not the fastest
  }
  // methods of the dictionary ADT
  /** Returns the number of entries in the tree. */
  public int size() { return numEntries; }
  /** Returns whether the tree is empty. */
  public boolean isEmpty() { return size() == 0; }
  /** Returns an entry containing the given key.  Returns null if no
    * such entry exists. */
  public Entry find(Object key) throws InvalidKeyException {
    checkKey(key);		// may throw an InvalidKeyException
    Position curPos = treeSearch(key, root());
    actionPos = curPos;		// node where the search ended
    if (isInternal(curPos)) return entry(curPos);
    return null;
  }
  /** Returns an iterator containing all entries containing the given
   * key.  Returns an empty iterator if no such entries exist. */
  public Iterator findAll(Object key) throws InvalidKeyException {
    checkKey(key);		// may throw an InvalidKeyException
    List L = new NodeList();
    addAll(L, root(), key);
    return L.elements();
  }
  /** Inserts an entry into the tree and returns the newly created entry. */
  public Entry insert(Object k, Object x) throws InvalidKeyException {
    checkKey(k);	// may throw an InvalidKeyException
    Position insPos = treeSearch(k, root());
    while (!isExternal(insPos))  // iterative search for insertion position
      insPos = treeSearch(k, left(insPos));
    actionPos = insPos;	// node where the new entry is being inserted
    return insertAtExternal(insPos, new BSTEntry(k, x, insPos));
  }
  /** Removes and returns a given entry. */
  public Entry remove(Entry ent) throws InvalidEntryException  {
    checkEntry(ent);            // may throw an InvalidEntryException
    Position remPos = ((BSTEntry) ent).position(); 
    Entry toReturn = entry(remPos);	// entry to be returned
    if (isExternal(left(remPos))) remPos = left(remPos);  // left easy case
    else if (isExternal(right(remPos))) remPos = right(remPos); // right easy case
    else {			//  entry is at a node with internal children
      Position swapPos = remPos;	// find node for moving entry
      remPos = right(swapPos);
      do
	remPos = left(remPos);
      while (isInternal(remPos));
      replaceEntry(swapPos, (Entry) parent(remPos).element());
    }
    actionPos = sibling(remPos);	// sibling of the leaf to be removed
    removeExternal(remPos);
    return toReturn;
  }
  /** Returns an iterator containing all entries in the tree. */
  public Iterator entries() {
    Iterator positer = positions();
    Position cur;
    List entries = new NodeList();
    while (positer.hasNext()) {
      cur = (Position) positer.next();
      if (isInternal(cur))
	entries.insertLast(cur.element());
    }
    return entries.elements();
  }
  /** 
   * Performs a tri-node restructuring.  Assumes the nodes are in one
   * of following configurations:
   *
   * <pre>
   *          z=c       z=c        z=a         z=a
   *         /  \      /  \       /  \        /  \
   *       y=b  t4   y=a  t4    t1  y=c     t1  y=b
   *      /  \      /  \           /  \         /  \
   *    x=a  t3    t1 x=b        x=b  t4       t2 x=c
   *   /  \          /  \       /  \             /  \
   *  t1  t2        t2  t3     t2  t3           t3  t4
   * </pre>
   * @return the new root of the restructured subtree
   */
  protected Position restructure(Position x) { 
    BTPosition a, b, c, t1, t2, t3, t4;
    Position y = parent(x);	// assumes x has a parent
    Position z = parent(y);	// assumes y has a parent
    boolean xLeft = (x == left(y));
    boolean yLeft = (y == left(z));
    BTPosition xx = (BTPosition)x, yy = (BTPosition)y, zz = (BTPosition)z;
    if (xLeft && yLeft) { 
      a = xx; b = yy; c = zz; 
      t1 = a.getLeft(); t2 = a.getRight(); t3 = b.getRight(); t4 = c.getRight();
    }
    else if (!xLeft && yLeft) { 
      a = yy; b = xx; c = zz; 
      t1 = a.getLeft(); t2 = b.getLeft(); t3 = b.getRight(); t4 = c.getRight();
    }
    else if (xLeft && !yLeft) { 
      a = zz; b = xx; c = yy; 
      t1 = a.getLeft(); t2 = b.getLeft(); t3 = b.getRight(); t4 = c.getRight();
    }
    else { // right-right 
      a = zz; b = yy; c = xx; 
      t1 = a.getLeft(); t2 = b.getLeft(); t3 = c.getLeft(); t4 = c.getRight();
    }
    // put b at z's place 
    if (isRoot(z)) {
      root = b;
      b.setParent(null);
    }
    else {
      BTPosition zParent = (BTPosition)parent(z);
      if (z == left(zParent)) {
	b.setParent(zParent);
	zParent.setLeft(b);
      }
      else { // z was a right child
	b.setParent(zParent);
	zParent.setRight(b);
      }
    }
    // place the rest of the nodes and their children
    b.setLeft(a);
    a.setParent(b);
    b.setRight(c);
    c.setParent(b);
    a.setLeft(t1);
    t1.setParent(a);
    a.setRight(t2);
    t2.setParent(a);
    c.setLeft(t3);
    t3.setParent(c);
    c.setRight(t4);
    t4.setParent(c);
    // Reset the location-aware entries
    ((BSTEntry) a.element()).pos = a;
    ((BSTEntry) b.element()).pos = b;
    ((BSTEntry) c.element()).pos = c;
    return b; // the new root of this subtree
  }
} 	// entries() method is omitted here