a6p1.cc

#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(ostream& out) = 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 {
		this->printto(cout);
	}
	void printto(ostream& out) const {
		bool firstPrinted = false;
		for (int i = 0; i < this->data.size(); i++) {
			Student* node = this->data[i];
			while (node != NULL) {
				if (firstPrinted != false) {
					out << " ";
				}
				firstPrinted = true;
				out << "(" << node->id << ", " << node->name << ")";
				node = node->next;
			}
		}
		out << endl;
	}
	void debugPrint(ostream& out) {
		out << "Table thinks it looks like:" << endl;
		this->printto(out);
		out << "We know table looks like:" << endl;
		for (int i = 0; i < this->data.size(); i++) {
			out << "Bucket " << i << ": ";
			Student* node = this->data[i];
			while (node != NULL) {
				out << "(" << node->id << ", " << node->name << ") ";
				node = node->next;
			}
			out << 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 {
		this->printto(cout);
	}
	void printto(ostream& out) const {
		ClosedStudent node;
		for (int i = 0; i < this->data.size(); i++) {
			node = this->data[i];
			if (node.valid && node.id != 0) {
				out << "(" << node.id << ", " << node.name << ") ";
			}
		}
		out << endl;
	}
	void debugPrint(ostream& out) {
		out << "Table thinks it looks like: ";
		this->printto(out);
		out << "We know it looks like: ";
		out << "[";
		for(int x = 0; x < data.size() - 1; x++)  
			out << data[x].name << ", ";  
		out << data[data.size() - 1].name;
		out << "]" << endl;
	}
	virtual ~HashTableClosed() {}
	friend void test(HashTable*);
};

#include "testing.cc"