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:";
        r_str += root_1.toString();
        r_str += "\n\nList 1:";
        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 = "\n";
        r_str += "key: "+key+", elmt: "+element.toString()+" ) ";
        
        if(this.next != null){
            r_str +=  this.next.toString();
        }
        return r_str;
    }
}