Assignment 8 Hash Table - Can't modify Assign8.cpp / StrTab.h

Assign8.cpp

// File: Assign08.cpp
//       A simple interactive test program that looks up a state abbreviation
//       from a table containing the abbreviations of the 50 U.S. states.

#include <iostream>
#include <algorithm>
#include <string>
#include "StrTab.h"
using namespace std;

string getLine(const string& prompt = "");
// Reads a line of text from cin and returns that line as a string.
// The newline character that terminates the input is not stored as
// part of the return value. If supplied, the optional prompt string
// is printed before reading the value.

void getLine(const string& prompt, string& out);
// Overloaded version of getLine that accepts a prompt and fills a
// given output (reference) string variable with its result.

void loadStateTab(StrTab& stateTab);
// Initializes the table so that it contains the two-letter abbreviations
// for the 50 states.

int main()
{
   StrTab stateTab;
   loadStateTab(stateTab);
   while (true)
   {
      string code = getLine("Enter 2-letter state code (0-letter to quit): ");
      if (code == "") break;
      if (code.length() > 2 ) code.erase(2, string::npos);
      transform(code.begin(), code.end(), code.begin(), ::toupper);
      string name = stateTab.get(code);
      if (name == "")
         cout << code << " is not a valid abbreviation" << endl;
      else
         cout << code << " = " << stateTab.get(code) << endl;
   }
   return 0;
}

string getLine(const string& prompt)
{
    string line;
    getLine(prompt, line);
    return line;
}

void getLine(const string& prompt, string& out)
{
    string promptCopy = prompt;
    if (!promptCopy.empty() && !isspace(promptCopy[promptCopy.length() - 1]))
       promptCopy += ' ';
    cout << promptCopy;
    getline(cin, out);
}

void loadStateTab(StrTab& table)
{
   table.put("AK", "Alaska");
   table.put("AL", "Alabama");
   table.put("AR", "Arkansas");
   table.put("AZ", "Arizona");
   table.put("CA", "California");
   table.put("CO", "Colorado");
   table.put("CT", "Connecticut");
   table.put("DE", "Delaware");
   table.put("FL", "Florida");
   table.put("GA", "Georgia");
   table.put("HI", "Hawaii");
   table.put("IA", "Iowa");
   table.put("ID", "Idaho");
   table.put("IL", "Illinois");
   table.put("IN", "Indiana");
   table.put("KS", "Kansas");
   table.put("KY", "Kentucky");
   table.put("LA", "Louisiana");
   table.put("MA", "Massachusetts");
   table.put("MD", "Maryland");
   table.put("ME", "Maine");
   table.put("MI", "Michigan"); // Doesn't work. 
   table.put("MN", "Minnesota");
   table.put("MO", "Missouri");
   table.put("MS", "Mississippi");
   table.put("MT", "Montana");
   table.put("NC", "North Carolina");
   table.put("ND", "North Dakota");
   table.put("NE", "Nebraska");
   table.put("NH", "New Hampshire");
   table.put("NJ", "New Jersey");
   table.put("NM", "New Mexico");
   table.put("NV", "Nevada"); // Does't work
   table.put("NY", "New York"); // Doesn't work
   table.put("OH", "Ohio");
   table.put("OK", "Oklahoma");
   table.put("OR", "Oregon");
   table.put("PA", "Pennsylvania");
   table.put("RI", "Rhode Island"); // Doesn't work
   table.put("SC", "South Carolina"); // Doesn't work
   table.put("SD", "South Dakota"); // Doesn't work
   table.put("TN", "Tennessee"); //Doesn't work
   table.put("TX", "Texas"); // Doesn't work
   table.put("UT", "Utah"); // DW
   table.put("VA", "Virginia"); //DW
   table.put("VT", "Vermont");
   table.put("WA", "Washington"); //DW
   table.put("WI", "Wisconsin"); 
   table.put("WV", "West Virginia"); // DW
   table.put("WY", "Wyoming"); // DW
}

StrTab.cpp

// File: StrTab.cpp - implementation file for StrTab class
//       (Uses a hash table as the underlying representation.)
//       (See StrTab.h for more documentation.)

#include <string>
#include <iostream>
#include "StrTab.h"
using namespace std;

// Implementation notes: StrTab constructor
//   Allocates the array (sized INITIAL_BUCKET_COUNT) of buckets
//   and initializes each bucket to the empty list.
StrTab::StrTab()
{
	buckets = new stNode*[INITIAL_BUCKET_COUNT];
	numBuckets = INITIAL_BUCKET_COUNT;

	for(int i = 0; i < numBuckets; i++)
	{
		buckets[i] = new stNode; 
		buckets[i]->key = "";
		buckets[i]->value = "";
		buckets[i]->link = NULL; 
	}
}

// Implementation notes: StrTab destructor
//   Frees the allocated cells.
StrTab::~StrTab()
{
	for(int i = 0; i < INITIAL_BUCKET_COUNT; i++)
	{
		delete buckets[i];
	}

	delete [] buckets; 
}

// Implementation notes: get
//   Calls findNode to search the linked list for the matching key:
//     index_into_buckets_array = hasCode_return_value % numBuckets
//   If match is found, get returns the associated value (string).
//   If no match is found, get returns the empty string.
string StrTab::get(const string& key) const
{
	int index = hashCode(key) % numBuckets;
	stNode * current = findNode(index, key); 

	if(current != 0)
		return current->value;
	else
		return "";
}

// Implementation notes: put
//   Calls findNode to search the linked list for the matching key:
//     index_into_buckets_array = hasCode_return_value % numBuckets
//   If a node (with matching key) already exists, put simply resets the
//   value field. If no matching key is found, put adds a new node to
//   the beginning of the list for that chain.
void StrTab::put(const string& key, const string& value)
{ 
	int index = hashCode(key) % numBuckets; 
	cout << "put :" << key << "at buckets index" << index << endl;

	if(findNode(index, key) == 0)
	{
		stNode * current = buckets[index];
		
		while(current->link != NULL)
		{
			current = current->link;
		}

		stNode * newNode = new stNode;
		current->link = newNode;
		newNode->key = key;
		newNode->value = value;
	}
	else
	{
		findNode(index,key)->value = "";
	}	
}

// Implementation notes: private helper function findNode
//   Finds a node (in the chain for the specified bucket) that matches
//   key. If a match is found, the return value is a pointer to the
//   node containing the matching key. If no match is found, findNode
//   returns 0 (null pointer).
StrTab::stNode* StrTab::findNode(int bucket, const string& key) const
{
	stNode * cursor = buckets[bucket];

	while(cursor->link != NULL)
	{
		cout << "collision at" << key << "at buckets index: " << bucket << endl;

		if(cursor->key == key)
			return cursor;
		else
			cursor = cursor->link;
	}
   return 0; // dummy null pointer returned
}

// Implementation notes: hashCode
//   Takes a string key and uses it to derive a hash code, which is a
//   nonnegative integer related to the key by a deterministic function
//   that distributes keys well across the space of integers.
//   The specific algorithm used here is called djb2 after the initials
//   of its inventor, Daniel J. Bernstein, Professor of Mathematics at the
//   the University of Illinois at Chicago.
int hashCode(const string& str)
{
	unsigned long hash = 5381;
	unsigned int c;
	
	for(unsigned int i = 0; i < str.length(); i++)
	{
		c = str[i];
		hash += ((hash << 5) + hash) + c;
	}

	return hash; 
}

StrTab.h

// File: StrTab.h - header file for StrTab class
// CLASS PROVIDED: StrTab (A table class in which the keys and values are strings.)
//
// CONSTRUCTOR
//   StrTab()
//     Pre:  (none)
//     Post: Initializes invoking StrTab to empty table.
//
// CONSTANT MEMBER FUNCTIONS (ACCESSORS)
//   std::string get(const std::string & key) const
//     Pre:  (none)
//     Post: Returns value associated with key or empty string if key is unassociated.
//
// MODIFICATION MEMBER FUNCTIONS (MUTATORS)
//   void put(const std::string& key, const std::string& value)
//     Pre:  (none)
//     Post: Associates key with value in this StrTab.
//
// NON-MEMBER FUNCTIONS
//   int hashCode(const std::string & key)
//     Pre:  (none)
//     Post: Returns the hash code for key.
//
// ILLEGAL TO COPY
//   Copy construction/assignment may NOT be used with StrTab objects.

#ifndef STR_TAB
#define STR_TAB

#include <string>

class StrTab
{
public:
   StrTab();
   ~StrTab();
   std::string get(const std::string & key) const;
   void put(const std::string& key, const std::string& value);
private:
   // definition for nodes in a bucket's linked list (chain)
   struct stNode
   {
      std::string key;
      std::string value;
      stNode* link;
   };

   // class-level constant
   static const int INITIAL_BUCKET_COUNT = 13;
   // instance-level variables
   stNode** buckets;  // dynamic array of pointers to stNode's
   int numBuckets;    // number of buckets in the array

   // private helper function
   stNode* findNode(int bucket, const std::string & key) const;

   // disabling copy construction/assignment
   StrTab(const StrTab& src) { }
   StrTab& operator=(const StrTab& src) { return *this; }
};

int hashCode(const std::string & key);

#endif