//c++ program

// the last two files are just to test the program.

// files number 2 and 3 just to help with the program

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 ahashtable. 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.

== 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.

file #1 ****** 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);

}

file # 2 ****** testfamily.cpp ******

//NOTE : you are not required to use this file, but you might fined it useful.

#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);

}

file # 3 ***** testhashtable.cpp ******

////NOTE : you are not required to use this file, but you might fined it useful.

#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);

}

file# 4 ***** familydata.txt*****

Family ID : Thornburg001

Name : Thornburg

Members : 1

Friends : Salmon003 Whyte001

-- -

Family ID : Montes001

Name : Montes

Members : 1

Friends : Coley001

-- -

Family ID : Hoff001

Name : Hoff

Members : 1

Friends : Applegate002 Hanes002 Rosenthal001

-- -

Family ID : Hoff001

Name : Hoff

Members : 1

Friends : Applegate002 Hanes002 Rosenthal001

----

Family ID : Hoff003

Name : Hoff

Members : 1

Friends : Beltran001 Barfield001 Hardin001

----

Family ID : Fair001

Name : Fair

Members : 2

Friends : Wick002

file #5 ***** expected.txt*****

table[0]:

List:

Family ID : Thornburg001

Name : Thornburg

Members : 1

Friends : Salmon003 Whyte001

--------------------

table[2] :

List :

Family ID : Montes001

Name : Montes

Members : 1

Friends : Coley001

--------------------

table[3] :

List :

--------------------

table[4] :

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