import java.util.Iterator;
public class TreeTable<K extends Comparable<K>, V> implements SimpleTable<K, V>, Iterable<K>
{
    private Node<K, V> head = null;
    public int nodecount = 0;
    public long getitcount = 0;
    
    public void put(K key, V value) {
        Node<K,V> b = new Node<K,V>(key, value);
        Node<K,V> n=head;
        if (head == null) {
            head=b;
            return;
        }
        nodecount++;
        for (;;) {
            if (key.equals(n.key)) {
                n.value = value;
                return;
            }
            if (key.compareTo(n.key)<0) {
                if (n.left == null) {
                    n.left = b;
                    return;
                }
                n = n.left;
            } else {
                if (n.right == null) {
                    n.right = b;
                    return;
                }
                n = n.right;
            }
        }
    }

    public V get(K key) {
        if (head == null)
            return null;
        else
            return head.get(key);
        // for (Node<K,V> n = head; n!=null;) {
        //     getitcount++;
        //     if (key.equals(n.key))
        //         return n.value;
        //     if (key.compareTo(n.key)<0)
        //         n = n.left;
        //     else
        //         n = n.right;
        // }
        // return null;
    }


    public String toString() {
        if (head == null)
            return "";
        else
            return head.toString();
    }
    public Iterator<K> iterator() {
        // return new TTI<K>(head.toList(null));
        // return new TTI2<K>(head);
        return new TTI3<K>(head);
    }

    private class List<K> {
        private K key;
        private List<K> next;
    }

    private class Node<K extends Comparable<K>, V> {
        private K key;
        private V value;
        private Node<K,V> left, right;

        Node(K k, V v) {
            key = k;
            value = v;
            left = null;
            right = null;
        }
        private V get(K k) {
            getitcount++;
            if (k.equals(key))
                return value;
            if (k.compareTo(key)<0) {
                if (left == null)
                    return null;
                return left.get(k);
            } else {
                if (right == null)
                    return null;
                return right.get(k);
            }
        }
        public void print() {
            if (left != null)
                left.print();
            System.out.println(key+": "+value+"\n");
            if (right != null)
                right.print();
        }
        public void gen(TTI3<K> it) {
            if (left != null)
                left.gen(it);
            synchronized (it) {
                it.worker.current = key;
                it.notify();
                try { it.wait(); } catch(InterruptedException Ex) { };
            }
            if (right != null)
                right.gen(it);
        }
        public String toString() {
            String l = (left == null) ? "" : left.toString();
            String r = (right == null) ? "" : right.toString();
            return l+key+": "+value+"\n"+r;
        }
        public List<K> toList(List<K> rest) {
            List<K> r= right!=null ? right.toList(rest) : rest;
            List<K> r1 = new List<K>();
            r1.next = r;
            r1.key = key;
            return left!=null ? left.toList(r1) : r1;
        }
    }

    private class NodeList<K extends Comparable<K>,V> {
        private Node<K,V> node;
        private NodeList<K,V> next;
        NodeList(Node<K,V> n, NodeList<K,V>l) {
            node = n;
            next = l;
        }
    }

    private class TTI2<K extends Comparable<K>> implements Iterator<K> {
        private NodeList<K,V> stack = null;
        TTI2(Node<K,V> n) {
            stack = n==null ? null : new NodeList<K,V>(n,null);
            walkleft();
        }
        private void walkleft() {
            while (stack != null && stack.node.left != null) {
                stack = new NodeList<K,V>(stack.node.left,stack);
            }
        }
        public boolean hasNext() {
            return stack != null;
        }
        public K next() {
            if (stack == null)
                return null;
            K res = stack.node.key;
            if (stack.node.right != null) {
                stack.node = stack.node.right;
                walkleft();
            } else {
                stack = stack.next;
            }
            return res;
        }           
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    private class TTI<K> implements Iterator<K> {
        private List<K> c;
        TTI(List<K> head) {
            c=head;
        }
        public boolean hasNext() {
            return c!=null;
        }
        public K next() {
            K k=c.key;
            c = c.next;
            return k;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    private class TTI3<K extends Comparable<K>> implements Iterator<K> {
        TTI3<K> it;
        Worker worker;
        class Worker implements Runnable {
            Node<K,V> head;
            boolean done;
            K current;
            Worker(Node<K,V> n, TTI3<K> i) {
                head = n;
                done = head==null;
                it = i;
            }
            public void run() {
                if (head != null)
                    head.gen(it);
                done = true;
            }
        }
        TTI3(Node<K,V> n) {
            worker=new Worker(n,this);
            new Thread(worker).start();
        }
        public boolean hasNext() {
            return !worker.done;
        }
        public synchronized K next() {
            try { wait(); } catch(InterruptedException Ex) { };
            K r = worker.current;
            notify();
            return r;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}