import java.util.Iterator;


public class BTreeAssocArray<K extends Comparable<K>, V> extends BinaryTree<K> 
                               implements AssociativeArray<K, V> {
	private class Node implements TreeCursor<K> {
		public K key;
		public V value;
		public Node lesser;
		public Node greater;
		
		public Node(K key, V value, Node lesser, Node greater) {
			this.key = key;
			this.value = value;
			this.lesser = lesser;
			this.greater = greater;
		}
		
		public Node(K key, V value) {
			this(key, value, null, null);
		}
	}
	
	private Node root_;
	private int size_;
	private long compares_ = 0;
	
	public BTreeAssocArray() {
		this.root_ = null;
		this.size_ = 0;
		this.compares_ = 0;
	}
	
	@Override
	public void put(K key, V value) {
		Node current = this.root_;
		Node previous = null;
		int lastCompare = 0;
		while ( (current != null) ) {
			lastCompare = key.compareTo(current.key);
			this.compares_ ++;
			if (lastCompare == 0) {
				current.value = value;
				return;
			}
			previous = current;
			if (lastCompare < 0) {
				current = current.lesser;
			} else {
				current = current.greater;
			}
		}
		this.size_ ++;
		if (previous == null) {
			this.root_ = new Node(key, value);
		} else if (lastCompare < 0) {
			previous.lesser = new Node(key, value);
		} else {
			previous.greater = new Node(key, value);
		}
	}

	@Override
	public V get(K key) {
		Node current = this.root_;
		while ( (current != null) ) {
			int res = key.compareTo(current.key);
			this.compares_ ++;
			if (res == 0) {
				return current.value;
			}
			if (res < 0) {
				current = current.lesser;
			} else {
				current = current.greater;
			}
		}
		return null;
	}

	@Override
	public Iterator<K> keys() {
		return iterator();
	}

	@Override
	public int size() {
		return this.size_;
	}

	@Override
	public TreeCursor<K> root() {
		return this.root_;
	}

	@Override
	public TreeCursor<K> toLeft(TreeCursor<K> c) {
		return ((Node)c).lesser;
	}

	@Override
	public TreeCursor<K> toRight(TreeCursor<K> c) {
		return ((Node)c).greater;
	}

	@Override
	public K getElement(TreeCursor<K> c) {
		return ((Node)c).key;
	}

	@Override
	public long nbComparison() {
		return this.compares_;
	}
}