Rollin my own hash map. College c++ style :)

gistfile1.cpp

//
//  main.cpp
//  HashMap
//
//  Created by Jacob Wilson on 2/28/12.
//  Copyright (c) 2012 Weber State. All rights reserved.
//


#include <iostream>
#include <string>
#include <sstream>
#include <time.h>
#include <stdlib.h>

using namespace std;

//The struct nodeType
template <class T>
struct nodeType{
	T info;
	nodeType* link;
    string key; 
};

//The linked list base class.
template <class Type>
class linkedListType {
protected:
	int count;
	nodeType<Type> *first;
	nodeType<Type> *last;
public:	
	linkedListType(); 
	~linkedListType();
	void destroyList(); 
	bool isEmptyList() const; 
	int getCount() const;
};

template <class Type>
linkedListType<Type>::linkedListType(){
	first = NULL;
	last = NULL;
	count = 0;
}

template <class Type>
linkedListType<Type>::~linkedListType(){	
	this->destroyList();
}

//Destroy the list, and reclaim all memory.
template <class Type>
void linkedListType<Type>::destroyList() {
	nodeType<Type> *temp;
    
	while (first != NULL) {
		temp = first;
		first = first->link;
		delete temp;
	}
	last = NULL;
	count = 0;
}

//Check true if list is empty.  False otherwise.
template <class Type>
bool linkedListType<Type>::isEmptyList() const {
	return (first == NULL);
}

//Return the number of nodes
template <class Type>
int linkedListType<Type>::getCount() const {
	return count;
}

//The unordered linked list class, which inherits off the linked list base class
template <class Type>
class unorderedLinkedList : public linkedListType<Type> {
public:
	void addLast(const string& key, const Type& info); 
    bool exists(const string& key) const;
    Type& item(const string& key) const;
    void remove(const string& key);
    
    
};

template <class Type>
void unorderedLinkedList<Type>::addLast(const string& key, const Type& info) {
    nodeType<Type> *newNode;
    newNode = new nodeType<Type>;
    newNode->info = info;
    newNode->key = key; 
    newNode->link = NULL;
    
    if (this->first == NULL) {
        //Empty list
        this->first = newNode;
    } else {
        this->last->link = newNode;
    }
    this->last = newNode;
    this->count++;

}
template <class Type>
Type& unorderedLinkedList<Type>::item(const string& key)const {
     
     nodeType<Type> *current;
     nodeType<Type> *trailCurrent;
     bool found;
     
    if (this->first == NULL) {
        cerr << "Whoa, this doesn't exist, so we're returning something just to make the compiler happy"; 
        return this->first->info; 
    }    
         else {
         if (this->first->key == key) {
             current = this->first;
           
             return current->info;
             
         } else {
             found = false;
             trailCurrent = this->first;
             current = this->first->link;
             while (current != NULL && !found) {
                 if (current->key != key) {
                     trailCurrent = current;
                     current = current->link;
                 } else {
                     found = true;
                 }
             }
             if (found) {
                 return current->info; 
             } else {
                 return this->first->info; 
             }
         }
     }
}
template <class Type>
bool unorderedLinkedList<Type>::exists(const string& key)const {
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    bool found;
    
    if (this->first == NULL)
        return false; 
    else {
        if (this->first->key == key) {
            return true; 
            
        } else {
            found = false;
            trailCurrent = this->first;
            current = this->first->link;
            while (current != NULL && !found) {
                if (current->key != key) {
                    trailCurrent = current;
                    current = current->link;
                } else {
                    found = true;
                }
            }
            if (found) {
                return true;     
            } else {
                return false; 
            }
        }
    }
    
    
}

template <class Type>
void unorderedLinkedList<Type>::remove(const string& key) {
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    bool found;
    
    if (this->first == NULL)
        cout << "Can't delete from an empty list" << endl;
    else {
        if (this->first->key == key) {
            current = this->first;
            this->first = this->first->link;
            this->count--;
            if (this->first == NULL)
                this->last = NULL;
            delete current;
            
        } else {
            found = false;
            trailCurrent = this->first;
            current = this->first->link;
            while (current != NULL && !found) {
                if (current->key != key) {
                    trailCurrent = current;
                    current = current->link;
                } else {
                    found = true;
                }
            }
            if (found) {
                trailCurrent->link = current->link;
                this->count--;
                if (this->last == current) {
                    this->last = trailCurrent;
                }
                delete current;
            } else {
                cout << "The item wasn't found" << endl;
            }
        }
    }
}

//Implement a hashTable class here
template <class Type>
class hashTable{
public:
	hashTable();
	~hashTable();
	void displayHashTableStatus() const;
	void add(const string& key, const Type& value);
	bool exists(const string& key) const;
	Type& item(const string& key) const;
	void remove(const string& key);
	Type& operator[](const string& key);

protected:
	unorderedLinkedList<Type> *linkedListArray; //The array of linked lists
    int hash(const string& key) const;
};
template <class Type>
int hashTable<Type>::hash(const string& key)const {
    
    int sum = 0; 
    for(int i = 3; i < key.length(); i++){
        sum += key[i] * key[i];  
    }
     
    sum += key[3] * key[7]; 
    
    return sum % 1000; 
    
}
template <class Type>
hashTable<Type>::hashTable() {
    
	//Initialize an array of linked lists
	linkedListArray = new unorderedLinkedList<Type>[1000];
}
template <class Type>
void hashTable<Type>::add(const string& key, const Type& value) {
    this->linkedListArray[hash(key)].addLast(key, value);   
    
    
}
template <class Type>
bool hashTable<Type>::exists(const string& key) const{
    if(this->linkedListArray[hash(key)].exists(key))
        return true; 
    else 
        return false; 
}
template <class Type>
Type& hashTable<Type>::item(const string& key) const{
    return this->linkedListArray[hash(key)].item(key); 
    
}
template <class Type>
Type& hashTable<Type>::operator[](const string& key){
    return this->linkedListArray[hash(key)].item(key); 
}
template <class Type>
void hashTable<Type>::remove(const string& key){
    
    this->linkedListArray[hash(key)].remove(key); 
    
}
template <class Type>
hashTable<Type>::~hashTable() {
	delete[] linkedListArray;
}

template <class Type>
void hashTable<Type>::displayHashTableStatus() const{
	int count;
	int sum = 0;
	int highest = 0;
	for (int i = 0; i < 1000; i++) {
		count = linkedListArray[i].getCount();
		sum += count;
		if (count > highest) {
			highest = count;
		}
	}
	cout << "The hashtable contains 1000 linked lists." << endl;
	cout << "The average amount of nodes per linked list is " << (float)sum / 1000 << endl;
	cout << "The largest linked list had this many nodes: " << highest << endl;
    
}


//A quick and dirty class that simulates a student record for one student.
class studentRecord {
public:
	void setAge(int age);
	void setGPA(float GPA);
	void setWNumber(const string& wNumber);
	friend ostream& operator<<(ostream&, const studentRecord&);
private:
	string wNumber;
	int age;
	float GPA;
};
void studentRecord::setAge(int age) {
	this->age = age;
}
void studentRecord::setGPA(float GPA) {
	this->GPA = GPA;
}
void studentRecord::setWNumber(const string& wNumber) {
	this->wNumber = wNumber;
}

//An overloaded << operator to help us display a student record
ostream& operator<<(ostream& out, const studentRecord& studentRecord) {
	out << "W#: " << studentRecord.wNumber << ", Age: " << studentRecord.age << ", GPA:" << studentRecord.GPA << endl;
	return out;
}

int main(){
	
	//Create a hashTable. 
	hashTable<studentRecord> h;
	
    


	//This next section loads the hashtable with a thousand objects.  
	//Generate 1000 key/value pairs.
	studentRecord *studentRecordObject;
	string key;
	stringstream out;
	srand(time(0));
	for(int value = 0, i = 0; i < 1000; value = value + 107, i++){
		studentRecordObject = new studentRecord();
		key = "W0000";
		out.str("");
		if (value < 1000)
			key = key + "0";
		if (value < 100)
			key = key + "0";
		if (value < 10)
			key = key + "0";
		out << value;
		key = key + out.str();
        
		//Give the object some random values.  
		studentRecordObject->setWNumber(key);
		studentRecordObject->setAge(rand() % 50 + 20);
		studentRecordObject->setGPA(rand() % 4000 / 1000.0);
		//Testing the "add" method
		h.add(key, *studentRecordObject);
	}
	//End of the section of loading the hashtable with a thousand objects.
    h.displayHashTableStatus();
	//Testing the "item" method
	cout << "The data for key W00000214 is " << h.item("W00000214");
	cout << "The data for key W00001070 is " << h.item("W00001070");
	cout << "Now deleting item for key W00000214" << endl;
	//Testing the "remove" method
	h.remove("W00000214");
	//Testing the "exists" method.
	if (h.exists("W00000214"))
		cout << "The node with key W00000214 was found" << endl;
	else
		cout << "The node with key W00000214 was not found" << endl;
    
	h["W00000107"].setAge(20);
    
	cout << "The data for key W00000107 is " << h["W00000107"];
	
    

	return 0;
}