import java.util.Iterator;

public class ListAssocArray<K, V> implements AssociativeArray<K, V> {
	
	private class Node {
		public K key;
		public V value;
		public Node next;
		public Node(K key, V value, Node next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}
	}
	
	private Node first_;
	private int size_;
	private long compares_;

	public ListAssocArray() {
		this.first_ = null;
		this.size_ = 0;
		this.compares_ = 0;
	}
	
	@Override
	public void put(K key, V value) {
		Node current = search(key);
		if (current == null) {
			this.first_ = new Node(key, value, this.first_);
			this.size_ ++;
		} else {
			current.value = value;
		}
	}

	@Override
	public V get(K key) {
		Node current = search(key);
		if (current != null) {
			return current.value;
		}
		return null;
	}

	private Node search(K key) {
		for (Node current = this.first_; current != null; current = current.next) {
			this.compares_++;
			if (key.equals(current.key)) {
				return current;
			}
		}
		return null;
	}

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

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

	private class KeyIterator implements Iterator<K> {
		private Node next_;
		
		public KeyIterator() {
			this.next_ = ListAssocArray.this.first_;
		}
		
		@Override
		public boolean hasNext() {
			return this.next_ != null;
		}

		@Override
		public K next() {
			K key = this.next_.key;
			this.next_ = this.next_.next;
			return key;
		}

		@Override
		public void remove() {
			// No remove
		}
	}
	
	@Override
	public long nbComparison() {
		return this.compares_;
	}
}