As the IT lead for this project, you are programming the software that will be used access employee data for a particular company.  The company wants to use this info for various things like company-wide email, Human Resources applications, submission to government authorities, etc.

After a series of discussions, you have come up with the following class design:

 Employee Node class

This class will hold info for an employee.

Employee’s id (a string)

Employee’s name

Access level (an int)

Terminated

Requirements

1) Implement a hash function (as a function, not a method.) The function must accept a string as a key and an int as the array size, and will return an int as the index hashed to. The return value MUST be in the range of 0 through (the second argument - 1).

2) Write the routine to populate the hash map (does not have to be a function). The hash map for the employees is backed by an array of some arbitrary size. To obtain the correct index to populate, you must use the hash function created in step 1, passing the employee id and the array size to the function. The array of employee pointers will be the ‘database’ from which the hash map will be populated.  You must use the getDirectory() code below to get a list of employees.  Note the getDirectory() function must not be changed (except to change the name of the Employee class, or perhaps the order of the data.)  Allowed changes will be discussed in class.

3) Implement a function (not a method) called getEmployee() that will accept an employee id string to look up in the hashmap. The function will access the appropriate index in the hashmap and if the employee is found the function returns a pointer to that employee, otherwise, NULL is returned. Hint: The solution is NOT to walk the hashmap array looking for a match to the employee id! That would be O(N) performance. The whole point of using hashmaps is to get very close to O(1).

The hash map can be made global for simplicity.

Notes

If you grasp the concept of hashing, pointers, and processing collections as we have done since day one, you realize this is an easy assignment. Do NOT make it harder than it is.

To keep this exercise easy, all class members may be made public.

Note, again for simplicity, when inserting employees into the hash map, more than one employee may hash to the same index, even though they contain different key values. For this exercise, if this occurs, the latter value should replace the previous one (do NOT delete the employee from memory for this exercise). Include comments in the function in requirement 3 to note this short coming and also include what should occur if this were a real life hash map.  Note that this explanation IS REQUIRED.

As always, we will be discussing the requirements and code, but you should know enough already to complete this exercise.

Walking the vector returned from getDirectory() may seem difficult at first, but review what you know about pointers and the problem is easily solved.  Another way (BIG hint), look up the at() method on vectors.

Note that if we found that the array size in our hashmap is not adequate, we could easily increase (or reduce) the size of the map by changing the MAPSIZE variable.

-----------------------------
 Starter code and database
/* A function that will obtain all employees in the company.
No 2 employees will ever share the same employee ID.
*/
vector<Employee*>* getDirectory()
{
 vector<Employee *> *employeeDatabase = new vector<Employee*>;
  
 employeeDatabase->push_back(new Employee("00729N", "William", 6, false));
 employeeDatabase->push_back(new Employee("10360F", "Karen", 3, false));
 employeeDatabase->push_back(new Employee("19789B", "Chang", 2, false));
 employeeDatabase->push_back(new Employee("11111G", "Vijay", 3, true));
 employeeDatabase->push_back(new Employee("21002F", "Carlos", 4, false));
 employeeDatabase->push_back(new Employee("00021X", "Mickey", 5, false));
 employeeDatabase->push_back(new Employee("19089B", "Woody", 3, true));
 employeeDatabase->push_back(new Employee("19783C", "Fredrick", 1, false));
 employeeDatabase->push_back(new Employee("00010A", "Henrietta", 6, false));
 employeeDatabase->push_back(new Employee("09980C", "Murtle", 4, true));
 employeeDatabase->push_back(new Employee("10360G", "Pat", 6, false));
 employeeDatabase->push_back(new Employee("00361G", "Irving", 9, false));
 employeeDatabase->push_back(new Employee("92323G", "Niles", 6, false));
 employeeDatabase->push_back(new Employee("92323R", "Lee", 5, false));
 employeeDatabase->push_back(new Employee("92324R", "Bernie", 7, false));
 employeeDatabase->push_back(new Employee("92325R", "Melvin", 4, true));
 employeeDatabase->push_back(new Employee("92326G", "Ruby-Joe", 1, false));
 employeeDatabase->push_back(new Employee("92327Y", "Petey", 1, false));
 employeeDatabase->push_back(new Employee("01320B", "Billie-Jean", 3, true));
 employeeDatabase->push_back(new Employee("51120A", "Ellen", 7, true));
 employeeDatabase->push_back(new Employee("77072D", "Dalton", 3, false));
 employeeDatabase->push_back(new Employee("44766D", "D'Jean", 6, false));
 employeeDatabase->push_back(new Employee("66498X", "Arnold", 2, false));
 employeeDatabase->push_back(new Employee("34565D", "Eddy", 1, false));
 employeeDatabase->push_back(new Employee("67762D", "Gerard", 9, false));
 employeeDatabase->push_back(new Employee("45542J", "Todd", 1, true));
 employeeDatabase->push_back(new Employee("00904A", "Olive", 2, false));
 employeeDatabase->push_back(new Employee("22981S", "Gloria", 3, false));
 employeeDatabase->push_back(new Employee("08159E", "Joan", 3, false));
 employeeDatabase->push_back(new Employee("20376S", "Alice", 3, false));
 employeeDatabase->push_back(new Employee("88159E", "Joan", 3, false));
 employeeDatabase->push_back(new Employee("08159E", "Yolanda", 3, false));
 employeeDatabase->push_back(new Employee("58159E", "Xiang-Lu", 3, false));
 employeeDatabase->push_back(new Employee("55156F", "Vera-Lee", 4, false));
 employeeDatabase->push_back(new Employee("89812G", "Shaune", 4, true));
 employeeDatabase->push_back(new Employee("05016F", "Marilyn", 5, false));
 employeeDatabase->push_back(new Employee("55157G", "Armand", 2, false));
 employeeDatabase->push_back(new Employee("55188B", "Don", 4, false));
 employeeDatabase->push_back(new Employee("55999Z", "Gertrude", 4, false));
 employeeDatabase->push_back(new Employee("78787F", "Samuel", 4, false));
 return employeeDatabase;
}
 //Declare the global hash map
 Employee** hashMap = NULL;
/*************
Put the functions here.
****************/

void main()
{
int MAP_SIZE = 29;  //The size of the hashmap
 
 //instantiate and initialize the hash map
 hashMap = new Employee*[MAP_SIZE];
 for(int a=0;a<MAP_SIZE;a++)
  hashMap[a] = NULL;
 //Get the Employee database.
 //The return is a pointer to a vector of Employee pointers
//This is NOT the hash map!
//You must walk this array to populate the hash map.
 vector<Employee*>* employeeDatabase= getDirectory();
//Populate the hashmap

//test the lookup with several sample id's

/*
Self study.  What code would you include here (after a lookup) to report whether the employee exists and whether he or she has been terminated? 
*/
}