//
// Basic Summary:
//
// Implementation file for table definition
//
// Copyright:
//
// Copyright 1993 Ron Burback
// Copyright 1993 Objects Plus
// All rights reserved
//
// Description: basic open hash table
//
// Include files:
//
#include <oops.h>
#include "pair.h"
#include "table.h"

// 
// define the version of this structure
//

char * table::version = "Objects Plus Table Version 1.0" ;


//
// there is one pool for this class
//

pool table::ThePool (sizeof(table)) ;

//
// function: 	table
// parameters: 	none 
// goal:		basic constructor
// returns:		new element 
//		
table::table(){
	water_mark = 0 ;
	hash_base = HASH_BASE ;
	storage = new dynamic_array() ; 
	for(natural i = 0 ; i < HASH_BASE ; i++ ) {
		storage->set(i,new dynamic_array()) ;
	}
}

//
// function: 	~table
// parameters: 	none 
// goal:		basic destructor
// returns:		element to the heap
//		
table::~table(){
	natural len ;
	pair * p ;
	natural j ;
	dynamic_array * d ;
	natural limit ;
	
	limit = storage->length() ;
	
	for(natural i=0;i<limit;i++) { 
		d = (dynamic_array *)storage->get(0) ;
		len = d->length() ;
		for(j=0;j<len;j++) {
			p = (pair *)d->get(0) ;
			delete p ;
		}
		delete d ; 
	};
	delete storage ;
}

//
// function: 	hash
// parameters: 	the key 
// goal:		given the key, calculate the hash
// returns:		hash location 
// note:		this is a simple prototype, hash on address of key
//				needs to return a full range integer
//		
natural table::hash(void * key) { return (natural)key ; }

//
// function: 	compare
// parameters: 	two keys, key1 and key2 
// goal:		are the two keys equal, 
// returns:		true/false 
// note:		the default is a simple addres check
//		
Boolean table::compare(void * key1, void * key2) { 
	return key1 == key2 ;
}

//
// function: 	location
// parameters: 	the key 
// goal:		given the key, calculate the hash table location
// returns:		hash table location 
// note:		there are two hash location, low and high
//				if high is valid, use that, else use low
//				this is a dynamic re sizing hash table
//				high is from 0 ... base - 1
//				low is from 0 ... 2*base -1
//				water_mark + base - 1 is the last valid location in the hast table
//				we use the high hash value if it will work
//				else we use the low hash value
//		
natural table::location(void * key) {
	natural TheHash = hash(key) ;
	natural low = TheHash % hash_base ;
	natural high =  TheHash % (hash_base*2) ;
	natural location = (high < water_mark + hash_base) ? high : low ;
	return location ;
}

//
// function: 	expand
// parameters: 	none 
// goal:		grow the hash table size by one
// returns:		bigger hash table
// note:		water mark is the locatin that needs to be re-hashed
//				it will be rehashed into two locations
//				water mark and water mark + hash base 
//		
void table::expand() {
	dynamic_array * d ;

	// add one more location to the hash table
	natural limit = storage->length() ;
	d = new dynamic_array() ;
	storage->set(limit,(void *)d) ;
	
	// grab the old list at this location location and replace with new
	d = (dynamic_array *)storage->peak(water_mark) ;
	natural length = d->length() ;
	storage->replace(water_mark, new dynamic_array() );
	
	// update the water marks
	water_mark++ ;
	if (water_mark == hash_base ) {
		water_mark = 0 ;
		hash_base *= 2 ;
	}

	// now put the values back into the table
	pair * p ;	
	for(natural i = 0; i < length ; i++ ) {
		p = (pair *)d->get(0) ;
		set(p->key,p->data) ;
		delete p ;
	}
	delete d ;
}



//
// function: 	peak
// parameters: 	a pointer to the key
// goal:		find the data, given the key
// returns:		the data 
//		
void * table::peak(void * key){

	// find the location and check to see if we should grow
	natural l = location(key);
	dynamic_array * d = (dynamic_array *)storage->peak(l) ;	
	natural length = d->length();
	if (length > RE_HASH_THRESHOLD) {
		expand() ;
		l = location(key);
		d = (dynamic_array *)storage->peak(l) ;	
		length = d->length();
	}
	
	// walk this list looking for the key
	pair * p;
	for (natural i = 0 ; i < length ; i++ ){
		p = (pair *)d->peak(i);
		if (compare(p->key,key)) return p->data;
	}
	
	return nil;
}

//
// function: 	get
// parameters: 	the key 
// goal:		find the data given the key and remove from table
// returns:		the data  
//		
void * table::get(void * key){

	// find the location and check to see if we should grow
	natural l = location(key);
	dynamic_array * d = (dynamic_array *)storage->peak(l) ;	
	natural length = d->length();
	if (length > RE_HASH_THRESHOLD) {
		expand() ;
		l = location(key);
		d = (dynamic_array *)storage->peak(l) ;	
		length = d->length();
	}
	
	// walk this list looking for the key
	pair * p;
	void * data ;
	for (natural i = 0 ; i < length ; i++ ){
		p = (pair *)d->peak(i);
		if (compare(p->key,key)) {
			p = (pair *)d->get(i);
			data = p->data ;
			delete p ;
			return data;
		}			
	}
	return nil;
}

//
// function: 	set
// parameters: 	key,data  
// goal:		add the (key,data) pair to the table
// returns:		modified table 
// note:		this algorithm does not check for an already present element
//		
void table::set(void * key, void * data){

	natural l = location(key);
	dynamic_array * d = (dynamic_array *)storage->peak(l) ;
	natural length = d->length();
	if (length > RE_HASH_THRESHOLD) {
		expand() ;
		l = location(key);
		d = (dynamic_array *)storage->peak(l) ;	
		length = d->length();
	}

	pair * p = new pair();
	p->key = key ;
	p->data = data ;
	d->set(0,p);
	
}


//
// function: 	test
// parameters: 	none 
// goal:		the QA test, self check, memory conservation
// returns:		true/false 
//		
Boolean table::test(){
	Boolean results;
	table * t ;
	void * key ;
	void * data ;
	
	results = true ;
	
	// add data and verify with peak
	t = new table();
	for(natural i=0;i<100*CHUNK_SIZE;i++){
		key = (void *)i ;
		data = (void *)(i+100*CHUNK_SIZE) ;
		t->set(key,data);
		data = t->peak(key);
		results &= (data == (void *)(i+100*CHUNK_SIZE));
	};
	delete t;
	
	// add data and verify with get
	t = new table();
	for(i=0;i<100*CHUNK_SIZE;i++){
		key = (void *)i ;
		data = (void *)(i+100*CHUNK_SIZE) ;
		t->set(key,data);
		data = t->get(key);
		results &= (data == (void *)(i+100*CHUNK_SIZE));
	};
	delete t;
	
	// add lots of data and verify with peak
	t = new table();
	for(i=0;i<100*CHUNK_SIZE;i++){
		key = (void *)i ;
		data = (void *)(i+100*CHUNK_SIZE) ;
		t->set(key,data);
	}
	
	for(i=0;i<100*CHUNK_SIZE;i++){
		key = (void *)i ;
		
		data = t->peak(key);
		results &= (data == (void *)(i+100*CHUNK_SIZE));
	};
	delete t;

	// done
	return results;

}