class Main {

	public static void main (String[] args){

		int how_many_reps = 100000;

		long t_0, t_1, t_2;

		String[] names = {"Lisa", "Bart", "Homer", "Marge", 
						"Ned", "Maude", "Maggie", "Rod", "Todd",
						"Lisa", "Bart", "Kirk", "Milhouse",
						"Ned", "Maude", "Maggie", "Marge",
						"Sanjay", "Apu", "Clancy", "Ralph"};
	
		// Java is fast these days but multiple executions
		// will provide some useful statistics

		Main m = new Main();

		t_0 = System.currentTimeMillis();

		for(int i = 0; i < how_many_reps; i++){
			m.fillUpHashTable(names);
		}

		t_1 = System.currentTimeMillis();

		for(int i = 0; i < how_many_reps; i++){
			m.fillUpList(names);
		}

		t_2 = System.currentTimeMillis();


		System.out.println("time used by BinaryHashMap:   "+(t_1 - t_0)+" ms");
		System.out.println("time used by List         :   "+(t_2 - t_1)+" ms");


		
	}


	public BinaryHashMap fillUpHashTable(String[] names){

		BinaryHashMap hashTable = new BinaryHashMap();
		Person p;

		for(int i = 0; i < names.length; i++){
			p = new Person(names[i], i);
			hashTable.put(names[i], p);
		}
	
		return hashTable;

	}

	public BHList fillUpList(String[] names){

		Person p;
		BHList root = new BHList("Dummy", new Person("Dummy", -11));
		BHList last = root;

		for(int i = 0; i < names.length; i++){
		
			p = new Person(names[i], i);
			
			if(root.hasKey(names[i])){
				root.replace(names[i], p);
			}else{
				last.next = new BHList(names[i], p);
				last = last.next;
			}

		}
		
		return root.next;
	}
}


class Person{
	String name;
	int ident;
	
	Person(String n, int id){
		this.name = n;
		this.ident = id;
	}

	public String toString(){
		return "Person( name: "+name+", id: "+ident+ " ) ";
	}
}


class BinaryHashMap {

	private BHList[] elements;
	private int size;

	BinaryHashMap(){
		elements = new BHList[2];
		size = 0;
	}

	public void put(String key, Object element){

		int hashValue = getHashValue(key);
		
		if(elements[hashValue] == null){

			elements[hashValue] = new BHList();
			elements[hashValue].addKey(key);
			elements[hashValue].addElement(element);

		
		}else if(elements[hashValue].hasKey(key)){

			 elements[hashValue].replace(key, element);		
			 return; //avoid increasing size when its unchanged

		}else{
			// insert at start of list to speed things up
			
			BHList old_root = elements[hashValue];
			BHList fresh_root = new BHList(key, element);

			fresh_root.next = old_root;
			elements[hashValue] = fresh_root;
		}

		this.size++;
	}

	public int size(){
		return this.size;
	}

	public boolean isEmpty(){
		return (this.size == 0);
	}

	public boolean remove(String key){
	
		// TODO
		
		return false;

	}

	public String[] keys(){
		
		// TODO

		return null;
	}

	public Object[] toArray(){

		// TODO

		return null;

	}

	/**
	* all elements hash to 0 or 1
	*/
	private int getHashValue(String str){
		return str.length() % 2;
	}

	public boolean contains(String key){
		int hVal = getHashValue(key);
		
		if(elements[hVal] == null){
			 return false;
		}else{
			return elements[hVal].hasKey(key);
		}
	}

	public Object get(String key){
		int hVal = getHashValue(key);
		return elements[hVal].get(key);
	}


	public String toString(){
		
		BHList root_1 = elements[0];
		BHList root_2 = elements[1];
		
		String r_str = "\nBinaryHashMap:\n";

		r_str += "\nList 0:\n\n";
		r_str += root_1.toString();
		r_str += "\n\nList 1:\n\n";
		r_str += root_2.toString();

		return r_str;
	}
}




class BHList {

	String key;
	Object element;


	BHList next;

	public BHList(){
		;
	}

	public BHList(String key, Object elm){
		this.key = key;
		this.element = elm;
	}

	public void addKey(String _key){
		this.key = _key;
	}

	public String getKey(){
		return this.key;
	}

	public void addElement(Object o){
		this.element = o;
	}

	public Object getElement(){
		return this.element;
	}

	public BHList getNext(){
		return this.next;
	}


	public boolean hasKey(String str){

		if(this.key.equals(str)){
			return true;
		}else if(this.next != null){
			return this.next.hasKey(str);
		}
		
		return false;
	}

	public void replace(String key, Object o){

		if(this.key.equals(key)){
			this.addElement(o);
			return;
		}else if(this.next != null){
			this.next.replace(key, o);
		}

	}

	public Object get(String key){
		if(this.key.equals(key)){
			return this.getElement();
		}else if(this.next != null){
			return this.next.get(key);
		}

		return null;
	}

	public BHList findFatherNode(String str){
		if(this.next != null && this.next.getKey().equals(str)){
			return this;
		}else if(this.next != null && ! this.next.getKey().equals(str)){
			return this.next.findFatherNode(str);
		}else{
			return null;
		}
	}

	public String toString(){
		String r_str = "BHList(";
		r_str += "key: "+key+", elmt: "+element.toString()+" ) ";
		
		if(this.next != null){
			r_str += "\n-->\n" + this.next.toString();
		}
		return r_str;
	}
}