package bstorderedmap;
import java.util.*;


public class BSTOrderedMap<K,V> {

    protected Comparator<K> comp;
    protected BTNode<MyEntry<K,V>> root;
    protected int size;

    protected static class MyEntry<K,V> implements Entry<K,V> {
        protected K key;
        protected V value;
        public MyEntry(K k, V v) {key = k; value = v;}
        public K getKey() {return key;}
        public V getValue() {return value;}
        public String toString() {return "(" + key + "," + value + ")";}
    }

    protected static class BTNode<E> {
        protected E element;
        protected BTNode<E> left, right, parent;
        public BTNode(E e, BTNode<E> p, BTNode<E> l, BTNode<E> r) {
            element = e;
            parent = p;
            left = l;
            right = r;
	}

        public E element() {return element;}
        public void setElement(E e) {element = e;}
        public BTNode<E> getLeft() {return left;}
        public void setLeft(BTNode<E> l) {left = l;}
        public BTNode<E> getRight() {return right;}
        public void setRight(BTNode<E> r) {right = r;}
        public BTNode<E> getParent() {return parent;}
        public void setParent(BTNode<E> p) {parent = p;}
    }

    public BSTOrderedMap() {
        this(new DefaultComparator<K>());
    }

    public BSTOrderedMap(Comparator<K> c) {
	root = new BTNode<MyEntry<K,V>>(null, null, null, null);
	size = 0;
	comp = c;
    }

    protected boolean isRoot(BTNode<MyEntry<K,V>> u) {
        return (u.getParent() == null);
    }

    protected boolean isExternal(BTNode<MyEntry<K,V>> u) {
        return ((u.getLeft() == null) && (u.getRight() == null));
    }

    protected boolean isInternal(BTNode<MyEntry<K,V>> u) {
        return (! isExternal(u));
    }

    protected boolean hasLeftChild(BTNode<MyEntry<K,V>> u) {
        return (! (u.getLeft().element() == null) );
    }

    protected boolean hasRightChild(BTNode<MyEntry<K,V>> u) {
        return (! (u.getRight().element() == null) );
    }





    protected BTNode<MyEntry<K,V>> treeSearch(K k, BTNode<MyEntry<K,V>> u) {
        //find a node conatining key k. If none exists,
        //return an external node where an element with this
        //key can be inserted.
        BTNode<MyEntry<K,V>> w;
        if (isExternal(u)) return u;
        K curKey = u.element().getKey();
        int compResult = comp.compare(k, curKey);
        if (compResult > 0)
            return treeSearch(k, u.getRight());
        w = treeSearch(k, u.getLeft());
        if (isInternal(w)) return w;
        if (compResult == 0) return u;
        return w;
    }

    /* Methods of the OrderedMap ADT follow */
 
    public int size() {return size;}
    public boolean isEmpty() {return size() == 0;}

    public V get(K k) {
        // get of Map ADT

        BTNode<MyEntry<K,V>> u = treeSearch(k, root);
        if (isInternal(u))
            return u.element().getValue();
        return null;
    }

    public V put(K k, V v) {
        // put of Map ADT

        BTNode<MyEntry<K,V>> u = treeSearch(k, root);
        if (isInternal(u)) {
            V returnValue = u.element().value;
            u.element().value = v;
            return returnValue;
        }
        u.setLeft(new BTNode<MyEntry<K,V>>(null,u,null,null));
        u.setRight(new BTNode<MyEntry<K,V>>(null,u,null,null));
        u.setElement(new MyEntry<K,V>(k,v) );
        size++;
        return null;
    }

    public V remove(K k) {
        // remove of Map ADT. Removes the entry with key equal
        // to k, and returns the corresponding value. If no
        // such entry, returns null
    }

    public Entry<K,V> firstEntry() {
	// returns entry with smallest key; if the map is
        // empty, it returns null

    }

    public Entry<K,V> lastEntry() {
	// returns entry with largest key; if the map is
        // empty, it returns null
    }

    
    public ceilingEntry(K k) {
        // returns the entry with the least key greater than or
        // equal to k; if there is no such entry, returns null
    }

    public higherEntry(K k) {
        // returns the entry with the least key strictly greater
        // than k; if there is no such entry, returns null
    }

    public String toString() {
        // returns a string with the entries stored in the map. It
        // does this via  an inorder traversal of the tree
        return "[" + elementsIn(root) + "]";
    }

    private String elementsIn(BTNode<MyEntry<K,V>> u) {
        if (isExternal(u))
                return "";
        return elementsIn(u.getLeft()) + u.element() + elementsIn(u.getRight());
    }

    /*
    public void printTree() {
        printTree(root);
    }

    public void printTree(BTNode<MyEntry<K,V>> u) {
        if (isExternal(u)) return;
        printTree(u.getLeft());
        System.out.println(u.element());
        printTree(u.getRight());
    }
    */
}