INF2220 fasit ukeoppgaver 3
===========================



OPPGAVE 1:
----------


alle kompleksitetssp?rsm?l besvares med big-O funksjonen.


a) Hva er kompleksiteten av ? finne et element i en uordnet liste?


   SVAR:

   worst case     O(n) = n
   average case   O(n) = n/2

   en m? i gjennomsnitt s?ke igjennom halve lista for
   finne et element


b) Hva er kompleksiteten av ? finne et element i BinaryHashMap dvs.

   //binHash er en BinaryHashMap
      
   Object o = binHash.get("en_n?kkel"); 


   (HINT: elementene er fordelt p? to uordnede lister)


   SVAR:

   worst case    O(n) = n
   average case  O(n) =  (n/2)/2 = n/4


   her har de to listene i gjennomsnitt n/2 elementer
   og vi m? i snitt s?ke igjennom halve listen f?r
   vi finner elementet. worst case; alle elementene
   blir liggende i en liste.



c) Hva er kompleksiteten av ? sette inn et element i BinaryHashMap dvs.

   binHash.put("some_key", some_obj_pointer);


   (HINT: n?kler er unike, vi kan ikke bare legge elementet inn i riktig liste)


   SVAR:
 

   worst case    O(n) = n
   average case  O(n) = n/4

   vi m? f?rst se om elementet finnes fra f?r, dvs. et oppslag
   m? gj?res samme som oppgave b). det ? bytte ut pekere fra gammelt
   til nytt objekt hvis det finnes fra f?r er konstant i tid,
   og legger bare til en konstant som vi kan ignorere.
    



d) La M v?re antall listepekere internt i en hash-tabell, anta at hash-funksjon
   gir oss perfekt spredning. (dvs. hvis vi fyller den med M n?kkel-objekt-par
   s? har vi ingen kollisjoner, og alle listene i arrayen inneholder 1 element).
   
   Hva er kompleksiteten av ? finne et element i en slik hash-tabell dersom
   den inneholder N elementer (den har M interne listepekere)? 
   (dvs. big-O uttrykt ved N og M)


   SVAR:

   antall elementer i interne lister dersom spredningen er s? god
   som oppgaveteksten sier:

   N/M - antall elementer i de interne listene

   oppslag dvs. ? finne et element i en liste som har lengde N/M

   worst case:    N/M
   average case:  (N/M)/2  =  N/2M





OPPGAVE 2:
----------


SVAR:



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");


        String[] keys;
        Object[] elms;

        BinaryHashMap htable = m.fillUpHashTable(names);
        //System.out.println(htable);

        keys = htable.keys();
        for(String s: keys){
            System.out.println(s);
        }
    
        elms = htable.toArray();
        for(Object o : elms){
            System.out.println(o);
        }
    
        htable.remove("Lisa");
        htable.remove("Clancy");
        System.out.println(htable);
        
    }


    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;
        //System.out.println(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;
        //System.out.println(root);
    }
}


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){
        int hVal = getHashValue(key);
        
        if(elements[hVal] == null || ! elements[hVal].hasKey(key)){
            
            System.err.println("trying to remove element not in Hash");
            return false;

        }else if(elements[hVal].getKey().equals(key)) {//delete root-node special case

            BHList old_root = elements[hVal];
            elements[hVal]  = old_root.next;
            this.size--;
            return true;    

        }else{

            BHList father = elements[hVal].findFatherNode(key);
            if(father == null){
                System.out.println("something terrible has happend");
                return false;
            }else{
                father.next = father.next.next;
                this.size--;
                return true;
            }
        }

    }

    public String[] keys(){

        String[] keys = new String[this.size];

        BHList r1 = elements[0];
        BHList r2 = elements[1];

        int i = 0;

        while(r1 != null){
            keys[i++] = r1.getKey();
            r1 = r1.next;
        }
    
        while(r2 != null){
            keys[i++] = r2.getKey();
            r2 = r2.next;
        }

        return keys;
    }

    public Object[] toArray(){
        Object[] elms = new Object[this.size];

        BHList r1 = elements[0];
        BHList r2 = elements[1];

        int i = 0;

        while(r1 != null){
            elms[i++] = r1.getElement();
            r1 = r1.next;
        }
    
        while(r2 != null){
            elms[i++] = r2.getElement();
            r2 = r2.next;
        }

        return elms;
        
    }   



    /**
    * 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;
    }
}