INF2220 fasit ukeoppgaver uke 3 (10/9-14/9)
===========================================



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


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 3:
----------


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