Dictionaries in c++

Source/Assg13/assg-13.cpp

Source/Assg13/assg-13.cpp

/**

 *

 *

 * @description Assignment 13 Dictionaries and Hash table

 * implementations.

 */

#include < cassert >

#include < iostream >

#include "KeyValuePair.hpp"

#include "Employee.hpp"

#include "HashDictionary.hpp"

using namespace std ;

/** main

 * The main entry point for this program. Execution of this program

 * will begin with this main function.

 *

 * @param argc The command line argument count which is the number of

 * command line arguments provided by user when they started

 * the program.

 * @param argv The command line arguments, an array of character

 * arrays.

 *

 * @returns An int value indicating program exit status. Usually 0

 * is returned to indicate normal exit and a non-zero value

 * is returned to indicate an error condition.

 */

int main ( int argc , char ** argv )

{

   // -----------------------------------------------------------------------

  cout << "----- testing Employee record and KeyValuePair class -----------" << endl ;

   KeyValuePair < int , string > pair ( 42 , "blue" );

  cout << "test key: " << pair . key () << endl ;

  assert ( pair . key () == 42 );

  cout << "test value: " << pair . value () << endl ;

  assert ( pair . value () == "blue" );

   int id = 3 ;

   Employee e ( id , "Derek Harter" , "1234 Main Street, Commerce TX" , 12345.67 );

  cout << e << endl ;

  assert ( e . getId () == 3 );

  assert ( e . getName () == "Derek Harter" );

  cout << endl ;

   // -----------------------------------------------------------------------

  cout << "-------------- testing quadratic probing -----------------------" << endl ;

   const int TABLE_SIZE = 7 ;

   HashDictionary < int , Employee > dict ( TABLE_SIZE , EMPTY_EMPLOYEE_ID );

  cout << "Newly created hash dictionary should be empty, size: " << dict . size () << endl ;

  assert ( dict . size () == 0 );

   int probeIndex = 0 ;

   //cout << "probe index: " << probeIndex

   // << " returned probe value: " << dict.probe(id, probeIndex)

   // << endl;

   //assert(dict.probe(id, probeIndex) == 2);

  probeIndex = 1 ;

   //cout << "probe index: " << probeIndex

   // << " returned probe value: " << dict.probe(id, probeIndex)

   // << endl;

   //assert(dict.probe(id, probeIndex) == 5);

  probeIndex = 5 ;

   //cout << "probe index: " << probeIndex

   // << " returned probe value: " << dict.probe(id, probeIndex)

   // << endl;

   //assert(dict.probe(id, probeIndex) == 37);

  cout << endl ;

   // -----------------------------------------------------------------------

  cout << "-------------- testing mid-square hashing ----------------------" << endl ;

   // the following asserts will only work for 32 bit ints, leave asserts

   // commented out if you have 64 bit asserts

  cout << "Assuming 32 bit (4 byte) ints for these tests: " << sizeof ( int ) << endl ;

  assert ( sizeof ( int ) == 4 );

   //id = 3918;

   //cout << "hash key: " << id

   // << " returned hash value: " << dict.hash(id)

   // << endl;

   //assert(dict.hash(id) == 1);

   //id = 48517;

   //cout << "hash key: " << id

   // << " returned hash value: " << dict.hash(id)

   // << endl;

   //assert(dict.hash(id) == 6);

   //id = 913478;

   //cout << "hash key: " << id

   // << " returned hash value: " << dict.hash(id)

   // << endl;

   //assert(dict.hash(id) == 5);

   //id = 8372915;

   //cout << "hash key: " << id

   // << " returned hash value: " << dict.hash(id)

   // << endl;

   //assert(dict.hash(id) == 4);

   // test that the distribution of the hash values

   // over the possible slots/buckets looks relatively

   // evenly distributed

   int counts [ TABLE_SIZE ] = { 0 };

   //for (id = 0; id < 1000000; id++)

   //{

   // int hash = dict.hash(id);

   // counts[hash]++;

   //}

   // display results

   int sum = 0 ;

   for ( int slot = 0 ; slot < TABLE_SIZE ; slot ++ )

   {

    cout << "counts for slot[" << slot << "] = "

      << counts [ slot ] << endl ;

    sum = sum + counts [ slot ];

   }

   // spot check results

   //assert(sum == 1000000);

   //assert(counts[0] == 143055);

   //assert(counts[6] == 142520);

  cout << endl ;

   // -----------------------------------------------------------------------

  cout << "-------------- testing dictionary insertion --------------------" << endl ;

  id = 438901234 ;

   //dict.insert(id, Employee(id, "Derek Harter", "123 Main St. Commerce TX", 58.23));

  id = 192834192 ;

   //dict.insert(id, Employee(id, "Alice White", "384 Bois'darc. Campbell TX", 45.45));

  id = 998439281 ;

   //dict.insert(id, Employee(id, "Bob Green", "92 Washington Apt. 5 Greenville TX", 16.00));

  id = 362817371 ;

   //dict.insert(id, Employee(id, "Carol Black", "8913 FM 24 Cooper TX", 28.50));

  cout << "After inserting " << dict . size () << " employees:" << endl ;

  cout << dict << endl ;

   // spot check that hash table entries were correctly performed

   //assert(dict.size() == 4);

   //assert(dict[3].key() == 192834192);

   //assert(dict[3].value().getName() == "Alice White");

   //assert(dict[1].key() == 438901234);

   //assert(dict[1].value().getName() == "Derek Harter");

  cout << endl ;

   // -----------------------------------------------------------------------

  cout << "-------------- testing dictionary search -----------------------" << endl ;

  id = 438901234 ;

   //e = dict.find(id);

   //cout << "Search for id: " << id << endl;

   //cout << " Found employee: " << e << endl;

   //assert(e.getId() == id);

   //assert(e.getName() == "Derek Harter");

  id = 362817371 ;

   //e = dict.find(id);

   //cout << "Search for id: " << id << endl;

   //cout << " Found employee: " << e << endl;

   //assert(e.getId() == id);

   //assert(e.getName() == "Carol Black");

  id = 239481432 ;

   //e = dict.find(id);

   //cout << "Unsuccessful Search for id: " << id << endl;

   //cout << " Found employee: " << e << endl;

   //assert(e.getId() == EMPTY_EMPLOYEE_ID);

   //assert(e.getName() == "");

  cout << endl ;

   // return 0 to indicate successful completion

   return 0 ;

}

Source/Assg13/assg13.pdf

Assg 13: Dictionaries and Hashing

COSC 2336 Spring 2019

April 18, 2019

Dates:

Due: Sunday May 05, by Midnight

Objectives

• More practice with using class templates

• Learn about implementing and using key/value pair Dictionary ab- straction

• Implement and learn about some basic hashing techniques, like mid- square hasing and quadratic probing for closed hashing schemes.

Description

In this assignment you will be implementing some basic mechanisms of a hash table to implement a Dictionary that uses hashing to store and search for items in its collection. You have been given many files for this assign- ment. I have provided an Employee class in "Employee.[hpp|cpp]" and a KeyValuePair class in "KeyValuePair.[hpp|cpp]". You will not need to make any changes to these files or classes, they should work as given for this as- signment.

You will be adding and implementing some member functions to the HashDictionary class. The initial "HashDictionary.[hpp|cpp]" file contains a constructor and destructor for a HashDictionary as well as some other accessors and operators already implemented that are used for testing.

You will be implementing a closed hash table mechanism using quadratic probing of the slots. You will also implement a version of the mid-square

1

hashing function described in our textbook (Shaffer section 9.4.3 on closed hashing mechinsms).

For this assignment you need to perform the following tasks.

1. Your first task is to implement methods to define the probe sequence for closed hasing. Add a member function named probe() to the HashDictionary class. Be aware that the HashDictionary class is a templatized on <Key, Value> templates, thus when you implement the class methods you need to templatize the class methods correctly. You can look at the example implementations of size() and the con- structors to remind yourself how to do this correctly.

In any case, probe() is a member function that takes two parameters, a Key and an integer index value. We are not using secondary hashing (as described in our textbook) so the Key value will actually not be used in your function. However, keep it as a parameter as the gen- eral abstraction/API for the probe function should include it for cases where secondary hashing is used. probe() should be a const class member function, as calling it does not change the dictionary. Finally probe() will return an ineger as its result.

Your probe() funciton should implement a quadratic probing scheme as described in our Shaffer textbook section 9.4.3 on pg. 338. Use c1 = 1, c2 =2, c3 = 2 as the parameters for your quadratic probe (the tests of probe() assume your probe sequence is using these pa- rameter values for the quadratic function).

2. You second tasks is to implement a hash function for integer like keys using the described mid-square hasing function (Shaffer 9.4.1 Example 9.6 pg. 327). We will create a slight variation of this algorithm for our hashing dictionary. First of all the hash() member functions should take a Key as its only input parameter, and it will then return a regular int as its result. Since this is a hash function, the integer value should be in the range 0 - tableSize-1, so don’t forget to mod by the tableSize before returning your hash result.

hash() should work like this. First of all, you should square the key value that is passed in. Then, assuming we are working with a 32 bit int, we want to only keep the middle 16 bits of the square of the key to use for our hash. There are many ways to work with and get the bits you need, but most likely you will want to use C bitwise operators to do this. For example, a simple method to get the middle 16 bits is

2

to first mask out the upper 8 bits using the bitwise & operator (e.g. key & 0x00FFFFFF) will mask out the high order 8 bits to 0). Then once you have removed the upper most significant 8 bits, you can left shift the key by 8 bits, thus dropping out the lower least significant 8 bits (e.g. key >> 8). Performing a mask of the upper 8 bits and shifting out the lower 8 bits will result in you only retaining the middle 16 bits.

If your system is using 64 bit integers rather than 32 bit integers, perform the mid-square method but retain the middle 32 bits of the result. You can use the sizeof(int) method to determine how many bytes are in an int on your system. I will give a bonus point if you write your hash() function to correctly work for both 32 and 64 bit values by testing sizeof(int) and doing the appopriate work to get the middle bits. Again after you square the key and get the middle bits, make sure you modulo the result to get an actual has index in the correct range.

3. The third task is to add the insert()method to your HashDictionary so that you can insert new key/value pairs into the dictionary. insert() should take a constant Key reference and a constant Value reference as its input parameters (note that both of these parameters should be declared as const, and they should both be reference pa- rameters, so use the & to indicate they are passed by reference). Your insert() function does not return a result, so it will be a void func- tion.

The algorithm for insert is described in Shaffer 9.4.3 on pg. 334. You need to call and use the probe() and hash() funciton you created in the first 2 steps to correctly define/implement your closed hashing probe sequence. The basica algorithm is that you use hash() to de- termine the initial home slot, and probe() gives an offset you should add. Basically you have to search the hashTable using the probe se- quence until you find an empty slot. Once you find an empty slot, you should create a new instance of a KeyValuePair<Key, Value> object, that contains the key and value that were provided as input param- eters to your insert() function. This KeyValuePair instance should then be inserted into the table at the location where you find the first empty slot on the probe sequence. Also don’t forget to update the valueCount paramemter of the HashDictionary class that keeps track of the number of items currently in the dictionary.

3

4. Finally you will also implement the find() method to search for a particular key in your dictionary. The find() member function taks a single Key parameter as input (it should be a const Key& reference parameter). The find() functin will return a Value as a result, which will be the Value of the record associated with the given Key if it was found in the dictionary, or an empty Value() object if it was not found.

The find() method uses the same probe sequence as insert() imple- mented by your probe() and hash() methods. So you should again search along the probe sequence, until you either find the key you were given to search for, or else find an empty slot. Then at the end, if you found the key in the hashTable you should return the value that corresponds to the key that was searched for. If the search failed and you found an empty slot on your probe sequence, you should instead return an empty Value() object, which is used as an indicator for a failed search.

In this assignment you will be given a lot of starting code. As usual, there is an "assg-13.cpp" file which contains commented out tests of the code/functions you are to write. You have been given and "Em- ployee.[hpp|cpp]" file containing a simple definition of a (non-templated) class/record that holds a few pieces of information about a theoretical Employee. We use this class to create a hash dictionary for testing with the employee id as the key, and the Employee record as the associated value in our Dictionary. You have also been given a template class in the file "KeyValuePair.[hpp|cpp]". This contains a templatized container to holding a key/value pair of items. You will not need to add any code or make any changes in the Employee or KeyValuePair class files.

You have also been given a "HashDictionary.[hpp|cpp]" file containing beginning defintions of a HashDictionary class. The member functions you need to add for this assignment should be added to these files.

Here is an example of the output you should get if your code is passing all of the tests and is able to run the simulation. You may not get the exact same statistics for the runSimulation() output, as the simulation is generating random numbers, but you should see similar values.

----- testing Employee record and KeyValuePair class ----------- test key: 42 test value: blue ( id: 3, Derek Harter, 1234 Main Street, Commerce TX, 12345.67 )

4

-------------- testing quadratic probing ----------------------- Newly created hash dictionary should be empty, size: 0 probe index: 0 returned probe value: 2 probe index: 1 returned probe value: 5 probe index: 5 returned probe value: 37

-------------- testing mid-square hashing ---------------------- Assuming 32 bit (4 byte) ints for these tests: 4 hash key: 3918 returned hash value: 1 hash key: 48517 returned hash value: 6 hash key: 913478 returned hash value: 5 hash key: 8372915 returned hash value: 4 counts for slot[0] = 143055 counts for slot[1] = 143040 counts for slot[2] = 143362 counts for slot[3] = 142399 counts for slot[4] = 142966 counts for slot[5] = 142658 counts for slot[6] = 142520

-------------- testing dictionary insertion -------------------- After inserting 4 employees: Slot: 0

Key : 362817371 Value: ( id: 362817371, Carol Black, 8913 FM 24 Cooper TX, 28.50 )

Slot: 1 Key : 438901234 Value: ( id: 438901234, Derek Harter, 123 Main St. Commerce TX, 58.23 )

Slot: 2 Key : 0 Value: ( id: 0, , , 0.00 )

Slot: 3 Key : 192834192 Value: ( id: 192834192, Alice White, 384 Bois'darc. Campbell TX, 45.45 )

Slot: 4

5

Key : 998439281 Value: ( id: 998439281, Bob Green, 92 Washington Apt. 5 Greenville TX, 16.00 )

Slot: 5 Key : 0 Value: ( id: 0, , , 0.00 )

Slot: 6 Key : 0 Value: ( id: 0, , , 0.00 )

-------------- testing dictionary search ----------------------- Search for id: 438901234

Found employee: ( id: 438901234, Derek Harter, 123 Main St. Commerce TX, 58.23 )

Search for id: 362817371 Found employee: ( id: 362817371, Carol Black, 8913 FM 24 Cooper TX, 28.50 )

Unsuccessful Search for id: 239481432 Found employee: ( id: 0, , , 0.00 )

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed "HashDictionary.[hpp|cpp]" source files to the submission folder to complete this assignment. You do not need to submit your "assg-13.cpp" file with the tests, nor the Employee or KeyVal- uePair files, since you should not have made changes to any of these (except to uncomment out the tests in assg-13.cpp). Please only submit the asked for source code files, I do not need your build projects, executables, project files, etc.

6

Requirements and Grading Rubrics

Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.

2. (20 pts.) probe() member function implemented. Function is using quadratic probing as asked for, with correct values for c1, c2 and c3 parameters. Probe sequence appears correct and passes tests.

3. (20 pts.) hash() member function implemented correctly. Function implements the mid-square method as described. Function correctly uses only the 16 middle bits if system uses 32 bit integers.

4. (30 pts.) insert() member function implemented and working. Func- tion appears to be correctly generating probe sequence using the probe() and hash() functions. Items are correctly inserted into ex- pected location in the hash table.

5. (30 pts.) find()member function implemented and working. Function appears to be also correctly using the probe sequence in the same was as insert(). Function passes the expected tests.

Program Style

Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.

2. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

7

3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.

8

Source/Assg13/Employee.cpp

Source/Assg13/Employee.cpp

/**

 * @description Simple example of an Employee record/class

 * we can use to demonstrate HashDictionary key/value pair

 * management.

 */

#include < string >

#include < iostream >

#include < iomanip >

#include < sstream >

#include "Employee.hpp"

using namespace std ;

/** constructor

 * Default constructor for our Employee record/class. Construct an

 * empty employee record

 */

Employee :: Employee ()

{

   this -> id = EMPTY_EMPLOYEE_ID ;

   this -> name = "" ;

   this -> address = "" ;

   this -> salary = 0.0 ;

}

/** constructor

 * Basic constructor for our Employee record/class.

 */

Employee :: Employee ( int id , string name , string address , float salary )

{

   this -> id = id ;

   this -> name = name ;

   this -> address = address ;

   this -> salary = salary ;

}

/** id accessor

 * Accessor method to get the employee id.

 *

 * @returns int Returns the integer employee id value.

 */

int Employee :: getId () const

{

   return id ;

}

/** name accessor

 * Accessor method to get the employee name.

 *

 * @returns string Returns the string containing the full

 * employee name for this record.

 */

string Employee :: getName () const

{

   return name ;

}

/** overload operator<<

 * Friend function to ouput representation of Employee to an

 * output stream.

 *

 * @param out A reference to an output stream to which we should

 * send the representation of an employee record for display.

 * @param employee The reference to the employee record to be displayed.

 *

 * @returns ostream& Returns a reference to the original output

 * stream, but now the employee information should have been

 * inserted into the stream for display.

 */

ostream & operator << ( ostream & out , Employee & employee )

{

   //out << "Employee id: " << employee.id << endl

   // << " name : " << employee.name << endl

   // << " address: " << employee.address << endl

   // << " salary : " << fixed << setprecision(2) << employee.salary << endl;

  out << "( id: " << employee . id << ", "

       << employee . name << ", "

       << employee . address << ", "

       << fixed << setprecision ( 2 ) << employee . salary << " )" << endl ;

   return out ;

}

Source/Assg13/Employee.hpp

/** * @description Simple example of an Employee record/class * we can use to demonstrate HashDictionary key/value pair * management. */ #include <string> #include <iostream> using namespace std; #ifndef EMPLOYEE_HPP #define EMPLOYEE_HPP // This should really be a class constant, however this // global constant represents a flag that is used to // indicate empty slots and/or failed search. const int EMPTY_EMPLOYEE_ID = 0; /** Employee * A simple Employee class/record to demonstrate/test * our hashing dictionary assignment. * NOTE: we are using 0 as a flag to represent an unused * slot or an invalid/empty employee. This is used/assumed * by our dictionary class to determine if a slot is empty * and/or to give a failure result for a failed search. */ class Employee { private: int id; string name; string address; float salary; public: Employee(); Employee(int id, string name, string address, float salary); int getId() const; string getName() const; friend ostream& operator<<(ostream& out, Employee& employee); }; #endif // EMPLOYEE_HPP

Source/Assg13/HashDictionary.cpp

Source/Assg13/HashDictionary.cpp

/**

 * @description Template class for definining a dictionary

 * that uses a hash table of KeyValuePair items.

 * Based on Shaffer hashdict implementation pg. 340

 */

/** constructor

 * Standard constructor for the HashDictionary

 *

 * @param tableSize The size of the hash table that should be

 * generated for internal use by this dictionary for hasing.

 * @param emptyKey A special flag/value that can be used to detect

 * invalid/unused keys. We need this so we can indicate which

 * slots/buckets in our hash table are currently empty, and also

 * this value is used as a return result when an unsuccessful

 * search is performed on the dictionary.

 */

template < class Key , class Value >

HashDictionary < Key , Value >:: HashDictionary ( int tableSize , Key emptyKey )

{

   this -> tableSize = tableSize ;

   this -> EMPTYKEY = emptyKey ;

  valueCount = 0 ;

   // allocate an array/table of the indicated initial size

  hashTable = new KeyValuePair < Key , Value > [ tableSize ];

   // initialize the hash table so all slots are initially empty

   for ( int index = 0 ; index < tableSize ; index ++ )

   {

    hashTable [ index ]. setKey ( EMPTYKEY );

   }

}

/** destructor

 * Standard destructor for the HashDictionary. Be good memory managers and

 * free up the dynamically allocated array of memory pointed to by hashTable.

 */

template < class Key , class Value >

HashDictionary < Key , Value >::~ HashDictionary ()

{

   delete [] hashTable ;

}

/** size

 * Accessor method to get the current size of this dictionary,

 * e.g. the count of the number of key/value pairs currently being

 * managed in our hash table.

 *

 * @returns in Returns the current number of items being managed by

 * this dictionary and currently in our hashTable.

 */

template < class Key , class Value >

int HashDictionary < Key , Value >:: size () const

{

   return valueCount ;

}

// Place your implementations of the class methods probe(), hash(),

// insert() and find() here

/** overload indexing operator[]

 * Overload indexing operator[] to provide direct access

 * to hash table. This is not normally part of the Dictionary

 * API/abstraction, but included here for testing.

 *

 * @param index An integer index. The index should be in the range 0 - tablesize-1.

 *

 * @returns KeyValuePair<> Returns a KeyValuePair object if the index into the

 * internal hash table is a valid index. This method throws an exception if

 * the index is not a valid slot of the hash table.

 */

template < class Key , class Value >

KeyValuePair < Key , Value >& HashDictionary < Key , Value >:: operator []( int index )

{

   if ( index < 0 || index >= tableSize )

   {

    cout << "Error: <HashDictionary::operator[] invalid index: "

      << index << " table size is currently: "

      << tableSize << endl ;

    assert ( false );

   }

   return hashTable [ index ];

}

/** HashDictionary output stream operator

 * Friend function for HashDictionary. We normally wouldn't have

 * something like this for a Dictionary or HashTable, but for testing

 * and learning purposes, we want to be able to display the contents of

 * each slot in the hash table of a HashDictionary container.

 *

 * @param out An output stream reference into which we should insert

 * a representation of the given HashDictionary.

 * @param aDict A HashDictionary object that we want to display/represent

 * on an output stream.

 *

 * @returns ostream& Returns a reference to the original given output stream,

 * but now the values representing the dictionary we were given should

 * have been sent into the output stream.

 */

template < typename K , typename V >

ostream & operator << ( ostream & out , const HashDictionary < K , V >& aDict )

{

   for ( int slot = 0 ; slot < aDict . tableSize ; slot ++ )

   {

    out << "Slot: " << slot << endl ;

    out << " Key : " << aDict . hashTable [ slot ]. key () << endl ;

    out << " Value: " << aDict . hashTable [ slot ]. value () << endl ;

   }

  out << endl ;

   return out ;

}

Source/Assg13/HashDictionary.hpp

/** * @description Template class for definining a dictionary * that uses a hash table of KeyValuePair items. * Based on Shaffer hashdict implementation pg. 340 */ #include <cassert> #include <iostream> #include "KeyValuePair.hpp" using namespace std; #ifndef HASHDICTIONARY_HPP #define HASHDICTIONARY_HPP /** HashDictionary * An implementation of a dictionary that uses a hash table to insert, search * and delete a set of KeyValuePair items. In the assignment, we will be * implementing a closed hashing table with quadratic probing. The hash function * will implement a version of the mid-square hasing function described in * our Shaffer textbook. * * @value hashTable An array of KeyValuePair items, the hash table this class/container * is managing. * @value tableSize The actual size of the hashTable array * @value valueCount The number of KeyValuePair items that are currently being * managed and are contained in the hashTable * @value EMPTYKEY A special user-supplied key that can be used to indicate empty * slots. Since how we determine what is a valid/invalid key will depend on the * key type, the user must supply this special flag/value when setting up the * hash dictionary. */ template <class Key, class Value> class HashDictionary { protected: KeyValuePair<Key, Value>* hashTable; // the hash table int tableSize; // the size of the hash table, e.g. symbol M from textbook int valueCount; // the count of the number of value items currently in table Key EMPTYKEY; // a special user-supplied key that can be used to indicate empty slots public: // constructors and destructors HashDictionary(int tableSize, Key emptyKey); ~HashDictionary(); // accessor methods int size() const; // searching and insertion // all 4 of the methods you were required to create for this // assignment should have appropriate class method signatures // defined here. // overload operators (mostly for testing) KeyValuePair<Key, Value>& operator[](int index); template <typename K, typename V> friend ostream& operator<<(ostream& out, const HashDictionary<K, V>& aDict); }; #include "HashDictionary.cpp" #endif // HASHDICTIONARY_HPP

Source/Assg13/KeyValuePair.cpp

Source/Assg13/KeyValuePair.cpp

/**

 * @description Template class for definining Key/Value pairs,

 * suitable for dictionary and hash table implementations.

 * Based on Shaffer KVPair ADT definition, pg. 139 Fig 4.31.

 */

/** constructor

 * Default constructor for a KeyValuePair.

 */

template < class Key , class Value >

KeyValuePair < Key , Value >:: KeyValuePair ()

{

}

/** constructor

 * Standard constructor for a KeyValuePair.

 *

 * @param key The key portion that is to be stored in this pair.

 * @param value The value portion that is to be stored in this pair.

 */

template < class Key , class Value >

KeyValuePair < Key , Value >:: KeyValuePair ( Key key , Value value )

{

   this -> myKey = key ;

   this -> myValue = value ;

}

/** key accessor

 * Accessor method to get and return the key for this key/value pair

 *

 * @returns Key Returns an object of template type Key, which is the

 * key portion of the pair in this container.

 */

template < class Key , class Value >

Key KeyValuePair < Key , Value >:: key ()

{

   return myKey ;

}

/** key setter

 * Accessor method to set the key for this key/value pair

 *

 * @param key The new value to update the key to for this pair.

 */

template < class Key , class Value >

void KeyValuePair < Key , Value >:: setKey ( Key key )

{

   this -> myKey = key ;

}

/** value accessor

 * Accessor method to get and return the value for this key/value pair.

 *

 * @returns Value& Returns a reference to the value object in this

 * key value pair container.

 */

template < class Key , class Value >

Value & KeyValuePair < Key , Value >:: value ()

{

   return myValue ;

}

Source/Assg13/KeyValuePair.hpp

/** * @description Template class for definining Key/Value pairs, * suitable for dictionary and hash table implementations. * Based on Shaffer KVPair ADT definition, pg. 139 Fig 4.31. */ #ifndef KEYVALUEPAIR_HPP #define KEYVALUEPAIR_HPP /** KeyValue Pair * Definition of basic key/value pair container. This container of course * associates a value (usually a record like a class or struct), with * a key (can be anything). * * We do not use the comparator Strategy pattern as discussed in * Shaffer pg. 144 here. We assume that the Key type has suitably * overloaded operators for <, >, ==, <=, >= operations as needed * in order to compare and order keys if needed by dictionaries and * hash tables using a KeyValuePair. * * @value key The key for a key/value pair item/association. * @value value The value for a key/value pair, usually something like * a record (a class or struct of data we are hashing or keeping in * a dictionary). */ template <class Key, class Value> class KeyValuePair { private: Key myKey; Value myValue; public: // constructors KeyValuePair(); KeyValuePair(Key key, Value value); // accessors, getters and setters Key key(); void setKey(Key key); Value& value(); }; #include "KeyValuePair.cpp" #endif // KEYVALUEPAIR_HPP

Applied Sciences

Architecture and Design

Biology

Business & Finance

Chemistry

Computer Science

Geography

Geology

Education

Engineering

English

Environmental science

Spanish

Government

History

Human Resource Management

Information Systems

Law

Literature

Mathematics

Nursing

Physics

Political Science

Psychology

Reading

Science

Social Science

Home

Blog

Archive

Contact

google+twitterfacebook

Copyright © 2019 HomeworkMarket.com