/**
 * Class to represent a Map as a binary search tree.
 * @author cs416
 * @version 2
 * @param <K> Type
 * @param <V> Type
 */
public class CSTreeMap<K extends Comparable<K>, V> implements CSMap<K, V> {

    class Node {
        K key;
        V value;
        Node left;
        Node right;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    Node root;
    int size;

    /**
     * Removes all of the mappings from this map.
     * The map will be empty after this call returns.
     */
    public void clear() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns true if this map contains a mapping for the specified key.
     * @param key key whose presence in this map is to be tested
     * @return true if this map contains a mapping for the specified key
     */
    public boolean containsKey(K key) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns the value to which the specified key is mapped,
     * or null if this map contains no mapping for the key.
     * If this map permits null values, then a return value of null does not necessarily indicate
     * that the map contains no mapping for the key;
     * it's also possible that the map explicitly maps the key to null.
     * The Map#containsKey operation may be used to distinguish these two cases.
     * @param key the key whose associated value is to be returned
     * @return the value to which the specified key is mapped,
     * or null if this map contains no mapping for the key
     */
    public V get(K key) {
        throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Inserts the (K, V) pair into the map if it does not already exist and
     * returns true.
     * If the map already contains a mapping for the key, return false
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return true if the key, value are inserted, false otherwise.
     */
    public boolean insert(K key, V value) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns true if this map contains no key-value mappings.
     * @return true if this map contains no key-value mappings
     */
    public boolean isEmpty() {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Removes the mapping for a key from this map if it is present.
     *
     * @param key key whose mapping is to be removed from the map
     * @return true if the key was removed from the Map, false otherwise
     */
    public boolean remove(K key) {
	throw new UnsupportedOperationException("TO BE IMPLEMENTED");
    }

    /**
     * Returns the number of key-value mappings in this map.
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);

        if (sb.length() == 0) {
            return "";
        } else {
            return sb.substring(0, sb.length() - 6);
        }
    }

    private void buildString(Node n, StringBuilder sb) {
        if (n != null) {
            buildString(n.left, sb);
            sb.append("(");
            sb.append(n.key);
            sb.append("->");
            sb.append(n.value);
            sb.append(") <--> ");
            buildString(n.right, sb);
        }
    }
}