== Programming Assignment == For this assignment you will write a program that reads in the family data for the Martian colonies and stores that data in an accessible database. This database allows for a user to look up a family and its immediate friends. The program should store the data in a hashtable to ensure quick access time. The objective of this assignment is to learn how to implement and use a hashtable. Since this is the objective, you cannot use a premade hashtable (e.g. the STL map class). Note: there is an advanced version of this program (for no additional credit) that also adds the feature of finding ALL friends, friends of friends, etc. until a certain group size it met. == Program Design == Your program should use good design methodologies so you should have separate classes for each of the following: - family -- This class represents a family. Each family has a family ID (guaranteed to be unique), a family name (not unique), a number of family members, and a list of 0-3 friends. The friends are identified by their associated family ID. - hashtable -- This is the data storage for family data. It is a hash table that contains families. It supports the ability to lookup a family and an ability to insert a family. (Remove is not needed for this assignment). For debugging purposes, this class also needs to have a "dumpTable()" method that will print out the contents of the hashtable. - familymgr -- This class is the interface to the main program for handing family data. The family manager has a method to add families to the database. It can also print a list of all known families. The primary value of the family manager is that, given a family id, it can look up that family and all of the friends of that family. This functionality is meant to be used by the HR group to make housing assignments. The simple functionality for this assignment takes a family and prints out only the immediate friends. The advanced version will print the full transitive closure of all friends from a given family up to a given group size limit. == Other Files == I have provided two test programs: testfamily.cpp and testhashtable.cpp. These are for your use. You are not required to use them but they will be helpful for developing and debugging your classes. Finally, for your convenience I have provided a "makefile". If you name all of your files the same as I have then you can use the following makefile to simplify your building and testing. Using the makefile is optional. You are welcome to modify it anyway you want. You do not need to turn in the makefile. == External Requirements == - The main driver (housinghelper.cpp) will add families to your family manager. When all of the families have been added the driver program will ask the family manager class to print out a list of all of the families. After that, it calls the method to print out the family and immediate friends for a few families. - The output from your program must match expected.txt exactly. == Internal Requirements == - The program must use the supplied housinghelper.cpp file, unmodified, as the main driver. - The program must store all families in a hashtable. - The hashtable must use linked list chaining to deal with hash collisions. New items should be added to the front of the linked list. - The hashtable hashing function should use the method discussed in the book and in class. That is: s[0] + s[1]*32 + s[2]*32^2 + s[3]*32^3 + ... s[n-1]*32^n-1 Hint: when calculating the hash value keep in mind each of these things: 1) Use the ASCII values of the letters (e.g. "A" = 65). 2) The hash index needs to be an unsigned integer (e.g. size_t). 3) Apply the modulus operator AFTER summing and multiplying all of the numbers. - The hashtable hash function must use Horner's rule to refactor the calculation to make it more efficient (you cannot use the pow() function or anything else like it). - The hashtable array size should be 7877 elements (that is a prime number). - You do not need to resize the table. - The should be no memory leaks. - All "string" data should be stored as char* variables. DO NOT USE std::string. some examples of family.txt (not the entire file) Family ID: Smith001 Name: Smith Members: 2 Friends: Ayala002 Goode001 --- Family ID: Smith002 Name: Smith Members: 4 Friends: Roderick003 --- Family ID: Johnson001 Name: Johnson Members: 4 Friends: Springer002 --- Family ID: Johnson002 Name: Johnson Members: 4 Friends: Harman001 Millard002 Hornsby001 --- Family ID: Johnson003 Name: Johnson Members: 2 Friends: Custer001 Aviles001 Haney001 --- Family ID: Williams001 Name: Williams Members: 2 Friends: Baylor002 Cleveland001 Kelley001 --- Family ID: Jones001 Name: Jones Members: 2 Friends: Quinonez001 Groce001 --- Family ID: Jones002 Name: Jones Members: 2 Friends: Cavazos001 --- Family ID: Jones003 Name: Jones Members: 4 Friends: Himes002 Guyton002 Macon001 --- Family ID: Brown001 Name: Brown Members: 3 Friends: Holland002 ---

== Programming Assignment ==

For this assignment you will write a program that reads in the family data for the Martian colonies and stores that data in an accessible database. This database allows for a user to look up a family and its immediate friends. The program should store the data in a hashtable to ensure quick access time.

The objective of this assignment is to learn how to implement and use a hashtable. Since this is the objective, you cannot use a premade hashtable (e.g. the STL map class).

Note: there is an advanced version of this program (for no additional credit) that also adds the feature of finding ALL friends, friends of friends, etc. until a certain group size it met.

== Program Design ==

Your program should use good design methodologies so you should have separate classes for each of the following:

- family -- This class represents a family. Each family has a family ID (guaranteed to be unique), a family name (not unique), a number of family members, and a list of 0-3 friends. The friends are identified by their associated family ID.

- hashtable -- This is the data storage for family data. It is a hash table that contains families. It supports the ability to lookup a family and an ability to insert a family. (Remove is not needed for this assignment). For debugging purposes, this class also needs to have a "dumpTable()" method that will print out the contents of the hashtable.

- familymgr -- This class is the interface to the main program for handing family data. The family manager has a method to add families to the database. It can also print a list of all known families. The primary value of the family manager is that, given a family id, it can look up that family and all of the friends of that family. This functionality is meant to be used by the HR group to make housing assignments. The simple functionality for this assignment takes a family and prints out only the immediate friends. The advanced version will print the full transitive closure of all friends from a given family up to a given group size limit.

== Other Files ==

I have provided two test programs: testfamily.cpp and testhashtable.cpp. These are for your use. You are not required to use them but they will be helpful for developing and debugging your classes.

Finally, for your convenience I have provided a "makefile". If you name all of your files the same as I have then you can use the following makefile to simplify your building and testing.

Using the makefile is optional. You are welcome to modify it anyway you want. You do not need to turn in the makefile.

== External Requirements ==

- The main driver (housinghelper.cpp) will add families to your family manager. When all of the families have been added the driver program will ask the family manager class to print out a list of all of the families. After that, it calls the method to print out the family and immediate friends for a few families. - The output from your program must match expected.txt exactly.

== Internal Requirements ==

- The program must use the supplied housinghelper.cpp file, unmodified, as the main driver. - The program must store all families in a hashtable. - The hashtable must use linked list chaining to deal with hash collisions. New items should be added to the front of the linked list. - The hashtable hashing function should use the method discussed in the book and in class. That is: s[0] + s[1]*32 + s[2]*32^2 + s[3]*32^3 + ... s[n-1]*32^n-1

Hint: when calculating the hash value keep in mind each of these things: 1) Use the ASCII values of the letters (e.g. "A" = 65). 2) The hash index needs to be an unsigned integer (e.g. size_t). 3) Apply the modulus operator AFTER summing and multiplying all of the numbers. - The hashtable hash function must use Horner's rule to refactor the calculation to make it more efficient (you cannot use the pow() function or anything else like it). - The hashtable array size should be 7877 elements (that is a prime number). - You do not need to resize the table. - The should be no memory leaks. - All "string" data should be stored as char* variables. DO NOT USE std::string.

some examples of family.txt (not the entire file)

Family ID: Smith001 Name: Smith Members: 2 Friends: Ayala002 Goode001 --- Family ID: Smith002 Name: Smith Members: 4 Friends: Roderick003 --- Family ID: Johnson001 Name: Johnson Members: 4 Friends: Springer002 --- Family ID: Johnson002 Name: Johnson Members: 4 Friends: Harman001 Millard002 Hornsby001 --- Family ID: Johnson003 Name: Johnson Members: 2 Friends: Custer001 Aviles001 Haney001 --- Family ID: Williams001 Name: Williams Members: 2 Friends: Baylor002 Cleveland001 Kelley001 --- Family ID: Jones001 Name: Jones Members: 2 Friends: Quinonez001 Groce001 --- Family ID: Jones002 Name: Jones Members: 2 Friends: Cavazos001 --- Family ID: Jones003 Name: Jones Members: 4 Friends: Himes002 Guyton002 Macon001 --- Family ID: Brown001 Name: Brown Members: 3 Friends: Holland002 ---

testfamily.cpp

#include

#include "family.h"

using namespace std;

void addFriendHelper(family& fam,const char* myfriend)

{

if (!fam.addFriend(myfriend))

{

cout << "Too many friends for " << fam.getId() << endl;

}

}

int main()

{

// Test some of the basic family functionality. Normally a test like this

// should be self-checking but for this class I am just having it print to

// screen since I think that will be more helpful for you (the students)

family fam("Test001","Test",3);

cout << fam;

addFriendHelper(fam,"Friend001");

cout << fam;

addFriendHelper(fam,"Friend002");

cout << fam;

addFriendHelper(fam,"Friend003");

cout << fam;

addFriendHelper(fam,"Friend004");

cout << fam;

return(0);

}

testhashtable.cpp

#include

#include "hashtable.h"

using namespace std;

int main()

{

const int HASHTABLESIZE = 13;

const int NUMFAMILIES = 50;

hashtable ht(HASHTABLESIZE);

cout << "======================================================================" << endl;

cout << "Testing inserts (should show full table)" << endl;

for (int i=0;i

{

char id[8];

char name[8];

char friendName[10];

family* familyPtr;

sprintf(id,"Test%d",i);

sprintf(name,"Name%d",i);

sprintf(friendName,"Friend%d",i);

familyPtr = new family(id,name,1);

familyPtr->addFriend(friendName);

ht.insert(id,*familyPtr);

delete familyPtr;

}

ht.dumpTable();

cout << "======================================================================" << endl;

cout << "Testing searches (should show no errors)" << endl;

const family* foundFam;

foundFam = ht.lookup("Test44");

if (foundFam == nullptr)

cout << "ERROR searching for Test44" << endl;

foundFam = ht.lookup("Test39");

if (foundFam == nullptr)

cout << "ERROR searching for Test39" << endl;

foundFam = ht.lookup("Test999");

if (foundFam != nullptr)

cout << "ERROR searching for Test999" << endl;

cout << "======================================================================" << endl;

cout << "Testing removes (should show empty table)" << endl;

for (int i=0;i

{

char id[8];

sprintf(id,"Test%d",i);

ht.remove(id);

}

ht.dumpTable();

return(0);

}

some examples of expected.txt (not entire file)

table[0]: List: Family ID: Thornburg001 Name: Thornburg Members: 1 Friends: Salmon003 Whyte001 -------------------- table[1]: List: -------------------- table[2]: List: Family ID: Montes001 Name: Montes Members: 1 Friends: Coley001 -------------------- table[3]: List: -------------------- table[4]: List: -------------------- table[5]: List: -------------------- table[6]: List: -------------------- table[7]: List: -------------------- table[8]: List: -------------------- table[9]: List: -------------------- table[10]: List: -------------------- table[11]: List: Family ID: Hoff001 Name: Hoff Members: 1 Friends: Applegate002 Hanes002 Rosenthal001 -------------------- table[12]: List: Family ID: Hoff002 Name: Hoff Members: 2 Friends: Marlowe003 -------------------- table[13]: List: Family ID: Hoff003 Name: Hoff Members: 1 Friends: Beltran001 Barfield001 Hardin001 -------------------- table[14]: List: Family ID: Fair001 Name: Fair Members: 2 Friends: Wick002 Family ID: Mccullough001 Name: Mccullough Members: 3 Friends: Tatum003 Lovejoy001 -------------------- table[15]: List: Family ID: Fair002 Name: Fair Members: 4 Friends: Mckeon003 Family ID: Mccullough002 Name: Mccullough Members: 1 Friends: Pepper002 Larose002 -------------------- table[16]: List: Family ID: Mccullough003 Name: Mccullough Members: 2 Friends: Thao002 Holloman001 -------------------- table[17]: List: -------------------- table[18]: List: Family ID: Martin001 Name: Martin Members: 1 Friends: Turner001 Stephenson002

housinghelper.cpp

#include  #include  #include  #include  #include "familymgr.h" using namespace std; int main(int argc,char** argv) { if (argc != 2) { cout << "Usage: " << argv[0] << " " << endl; exit(0); } // family manager object; familymgr familyMgr; // Read the data const int MAX_LINE = 64; char* datafile = argv[1]; ifstream infile(datafile); char line[MAX_LINE]; char id[MAX_LINE]; char name[MAX_LINE]; int members; char friend1[MAX_LINE]; char friend2[MAX_LINE]; char friend3[MAX_LINE]; if (infile.is_open()) { while (infile.getline(line,MAX_LINE) ) { char* s; // ID -- Family ID:  s = strchr(line,':') + 2; // Skip the space strncpy(id,s,MAX_LINE); // Name infile.getline(line,MAX_LINE); s = strchr(line,':') + 2; // Skip the space strncpy(name,s,MAX_LINE); // members infile.getline(line,MAX_LINE); s = strchr(line,':') + 2; // Skip the space members = atoi(s); // friends infile.getline(line,MAX_LINE); s = strchr(line,':') + 2; // Skip the space char* friendPtr; friendPtr = strtok(s," "); if (friendPtr != nullptr) strncpy(friend1,friendPtr,MAX_LINE); else friend1[0] = '\0'; friendPtr = strtok(nullptr," "); if (friendPtr != nullptr) strncpy(friend2,friendPtr,MAX_LINE); else friend2[0] = '\0'; friendPtr = strtok(nullptr," "); if (friendPtr != nullptr) strncpy(friend3,friendPtr,MAX_LINE); else friend3[0] = '\0'; infile.getline(line,MAX_LINE); if (strcmp(line,"---")!=0) { cout << "Error parsing the file" << endl; } // Add the family to the family manager family* famPtr = new family(id,name,members); famPtr->addFriend(friend1); famPtr->addFriend(friend2); famPtr->addFriend(friend3); familyMgr.addFamily(*famPtr); delete famPtr; } infile.close(); familyMgr.printAllFamilies(); // familyMgr.printGroup("Smith001"); familyMgr.printSmallCircle("Smith001"); familyMgr.printSmallCircle("Hall001"); familyMgr.printSmallCircle("Noel003"); } return(0); }