gistfile1.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <map>

using namespace std;

class HashTable {
public:
	HashTable() {}
	virtual ~HashTable() {}
	virtual int insert(int uw_id, string const& info) = 0;
	virtual int remove(int uw_id) = 0;
	virtual string& operator[](int uw_id) = 0;
	virtual void print() const = 0;
	virtual void debugPrint() = 0;
protected:
	static const int defaultSize = 100;
	int hash(int key, int buckets) const { return key % buckets; }
};

class HashTableOpen: public HashTable {
private:
	struct Student {
		Student(int id, string const& name)
		: id(id), name(name), next(NULL) {}
		int id;
		string name;
		Student* next;
	};
	vector<Student*> data;
public:
	HashTableOpen() {
		HashTableOpen(defaultSize);
	}
	HashTableOpen(int size) {
		if (size < 1) size = defaultSize;
		
		this->data.resize(size);
		for (int i = 0; i < this->data.size(); i++) {
			assert(this->data[i] == NULL);
		}
	}
	virtual ~HashTableOpen() {
		cout << "delete";
		for (int i = 0; i < this->data.size(); i++) {
			Student* node = this->data[i];
			Student* next = NULL;
			while (node != NULL) {
				cout << " " << node->id;
				next = node->next;
				delete node;
				node = next;
			}
		}
		cout << endl;
	}
	Student* findParent(int id) {
		int hsh = hash(id, this->data.size());
		Student* node = this->data[hsh];
		Student* prev = node;
		while (node != NULL) {
			if (node->id == id) return prev;
			prev = node;
			node = node->next;
		}
		return NULL;
	}
	Student* find(int id) {
		int hsh = hash(id, this->data.size());
		Student* node = this->data[hsh];
		while (node != NULL) {
			if (node->id == id) return node;
			node = node->next;
		}
		return NULL;
	}
	int insert(int id, string const& name) {
		Student* node = this->find(id);
		if (node != NULL) {
// 			node->name = name;
			return 0;
		}
		
		int hsh = hash(id, this->data.size());
		Student* next = this->data[hsh];
		this->data[hsh] = new Student(id, name);
		this->data[hsh]->next = next;
		return 1;
	}
	int remove(int id) {
		// Node does not exist
		Student* node = this->find(id);
		if (node == NULL) {
			return 0;
		}
		
		// Node has no parent; it is the only node currently in the table which hashes to this value.
		int hsh = hash(id, this->data.size());
		if (node == this->data[hsh]) {
			Student* next = node->next;
			delete node;
			this->data[hsh] = next;
			return 1;
		}
		
		// Node has a parent. Remove the node and set it's parent's reference to NULL.
		Student* parent = this->findParent(id);
		assert(parent->id != node->id);
		cout << "parent: " << parent->id << " node: " << node->id << endl;
		parent->next = node->next;
		delete node;
		return 1;
	}
	string& operator[](int id) {
		Student* node = this->find(id);
		if (node == NULL) {
			this->insert(id, "");
			node = this->find(id);
			if (node == NULL) throw "Fatal internal error!";
		}
		string& name = node->name;
		return name;
	}
	void print() const {
		bool firstPrinted = false;
		for (int i = 0; i < this->data.size(); i++) {
			Student* node = this->data[i];
			while (node != NULL) {
				if (firstPrinted != false) {
					cout << " ";
				}
				firstPrinted = true;
				cout << "(" << node->id << ", " << node->name << ")";
				node = node->next;
			}
		}
		cout << endl;
	}
	void debugPrint() {
		cout << "debugPrint() not implemented!" << endl;
	}
};

class HashTableClosed: public HashTable {
private:
	struct ClosedStudent {
		ClosedStudent() : id(0), valid(false) {}
		int id;
		string name;
		bool valid;
	};
	vector<ClosedStudent> data;
	bool tablefull;
public:
	HashTableClosed() {
		HashTableClosed(defaultSize);
	}
	HashTableClosed(int defaultSize) {
		this->data.resize(defaultSize);
		this->tablefull = false;
	}
	ClosedStudent* find(int id) {
		int size = this->data.size();
		int hsh = this->hash(id, size);
		int i = hsh;
		ClosedStudent* node = &this->data[hsh];
		while (node->valid == true) {
			i += 1;
			if (node->id == id) return node;
			node = &this->data[i % size];
			if (i % size == hsh) {
				this->tablefull = true;
				return NULL;
			}
		}
		return node;
	}
	int insert(int id, const string& name) {
		ClosedStudent* node = this->find(id);
		if (node == NULL) {
			return 0;
		}
		if (node->valid != false) {
			return 0;
		}
		node->id = id;
		node->name = name;
		node->valid = true;
		return 1;
	}
	int remove(int id) {
		ClosedStudent* node = this->find(id);
		if (node == NULL) return 0;
		if (node->id != id) return 0;
		if (node->valid == false) return 0;
		
		node->valid = false;
		return 1;
	}
	string& operator[](int id) {
		ClosedStudent* node = this->find(id);
		if (node == NULL) {
			throw string("table full");
		}
		if (node->id != id) {
			this->insert(id, "");
		}
		if (node->valid == false) {
			node->name = "";
		}
		return this->find(id)->name;
	}
	void print() const {
		ClosedStudent node;
		for (int i = 0; i < this->data.size(); i++) {
			node = this->data[i];
			if (node.valid && node.id != 0) {
				cout << "(" << node.id << ", " << node.name << ") ";
			}
		}
		cout << endl;
	}
	void debugPrint() {
		cout << "Table thinks it looks like: ";
		this->print();
		cout << "We know it looks like: ";
		cout << "[";
		for(int x = 0; x < data.size() - 1; x++)  
			cout << data[x].name << ", ";  
		cout << data[data.size() - 1].name;
		cout << "]" << endl;
	}
	virtual ~HashTableClosed() {}
	friend void test(HashTable*);
};

string intToString(int number) {
	char * buffer = new char[10];
	sprintf(buffer, "%d", number);
	return *(new string(buffer));
}

void test(HashTable* table) {
	int size = 5;
	
	printf("%s", ((*table)[5]).c_str());
	
	bool errorThrown = false;
	map<int, string> expected;
	int exp;
	int res;
	
	for (int i = 0; i < 50; i++) {
		int var = rand() % 10 + 1;
		int action = rand() % 3;
		try {
		switch (action) {
		case 0:
			exp = expected.erase(var);
			res = table->remove(var);
			if(exp != res) {
				cout << "When removing " << var << "(" << var % size << "), got unexpected value " << res << " (expected " << exp << ")" << endl;
				table->debugPrint();
			}
			break;
		case 1:
			exp = expected.insert(pair<int, string>(var, intToString(var))).second;
			res = table->insert(var, intToString(var));  
			if(exp != res) {
				cout << "When adding " << var << " (" << var % size << ")" << "), got unexpected value " << res << " (expected " << exp << ")" << endl;
				cout << " (not added)";
				table->debugPrint();
			}
			break;
		case 2:
			break;
			cout << "accessing index " << var << "(" << var % size << ") and setting it to " << (var + 5);
			(*table)[var] = intToString(var + 5);
		}
		} catch(string error) {
			cout << " (error thrown from " << var << ")";
			errorThrown = true;
		}
	}
}

int main (int argc, char* argv[]) {
	test(new HashTableClosed(5));
	return 0;
	HashTable* table = new HashTableClosed(4);
	delete table;
	for(int i=0; i<2; i++) {
		switch(i) {
			case 0: table = new HashTableClosed(4); break;
			case 1: table = new HashTableOpen(4); break;
		}
		cout << "------------------------------" << endl;
		cout << " Running test " << (i == 0 ? "HashTableClosed" : "HashTableOpen") << endl;
		cout << "------------------------------" << endl;

		cout << "5660:" << table->insert(5660, "Ali") << " ";
		cout << "1223:" << table->insert(1223, "Gia") << " ";
		cout << "9020:" << table->insert(9020, "Jon") << " ";
		cout << "9020b:" << table->insert(9020, "Jon") << " ";
		cout << "3447:" << table->insert(3447, "Mei") << endl;
		
		table->print();
		cout << table->remove(9020) << " ";
// 			 << (*table)[9020] << " "
		cout << table->remove(3405) << " ";
		cout << table->remove(9020) << " ";
		cout << (*table)[9020] << " ";
		cout << table->remove(5660) << " ";
		cout << table->remove(5660) << " ";
		cout << table->insert(5660, "TROLL") << " ";
		cout << table->insert(1223, "TROLL") << endl;
		(*table)[4444] = "Rin";
		cout << "uw_ids[" << 4444 << "] = " << (*table)[4444] << endl;
		try {
			(*table)[1111] = "Uri";
		} catch (string e) {
			cout << e << endl;
		}
		table->print();
		cout << endl;

		delete table;
	}
}