//c++ program // the last two files are just to test the program. // files numbe
ID: 3918053 • Letter: #
Question
//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 <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include "familymgr.h"
using namespace std;
int main(int argc,char** argv)
{
if (argc != 2)
{
cout << "Usage: " << argv[0] << " <datafile>" << 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: <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] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend2,friendPtr,MAX_LINE);
else
friend2[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend3,friendPtr,MAX_LINE);
else
friend3[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 <iostream>
#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 <iostream>
#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<NUMFAMILIES;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<NUMFAMILIES;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
Explanation / Answer
//HousingHelper.cpp
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include "familymgr.h"
using namespace std;
int main(int argc,char** argv)
{
if (argc != 2)
{
cout << "Usage: " << argv[0] << " <datafile>" << 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: <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] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend2,friendPtr,MAX_LINE);
else
friend2[0] = '';
friendPtr = strtok(nullptr," ");
if (friendPtr != nullptr)
strncpy(friend3,friendPtr,MAX_LINE);
else
friend3[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);
}
-------------------------------------------------------------------------------------------
//family.cpp
#include "family.h"
family::family()
{
ID = new char [4];
strcpy(ID,"N/A");
name = new char[4];
strcpy(name,"N/A");
members = 0;
nFriends = 0;
}
family::family(char * tID, char * tName, int tMemebers)
{
ID = new char [strlen(tID) + 1];
strcpy(ID,tID);
name = new char[strlen(tName) + 1];
strcpy(name,tName);
members = tMemebers;
nFriends = 0;
for (int i = 0; i < MAX_FRIENDS; i++)
friends[i] = NULL;
}
family::~family()
{
if(ID)
delete[] ID;
if(name)
delete[] name;
for(int i = 0; i < MAX_FRIENDS ; i++)
{
if(friends[i])
delete friends[i];
}
}
char * family::getId()
{
return ID;
}
char * family::getName()
{
return name;
}
int family::getMembers()
{
return members;
}
int family::getFriendCount()
{
return nFriends;
}
char * family::getFriend(int index) const
{
return friends[index];
}
void family::getFriends(ostream & buffer)
{
for(int i = 0; i < 3; i++)
{
if(friends[i])
buffer << friends[i] << " ";
}
}
bool family::addFriend(const char * tFriend)
{
if (nFriends == MAX_FRIENDS)
{
return false;
}
else
{
friends[nFriends] = new char[strlen(tFriend) + 1];
strcpy(friends[nFriends],tFriend);
nFriends++;
return true;
}
}
const family & family::operator = (const family & tempFam)
{
if(this == & tempFam)
{
return *this;
}
else
{
if(ID)
delete [] ID;
ID = new char[strlen(tempFam.ID)];
strcpy(this->ID,tempFam.ID);
if(name)
delete [] name;
name = new char[strlen(tempFam.name)];
strcpy(this->name,tempFam.name);
this->members = tempFam.members;
for(int i = 0; i < MAX_FRIENDS; i++)
{
if(friends[i])
{
delete friends[i];
}
if(tempFam.friends[i])
{
friends[i] = new char[strlen(tempFam.friends[i]) + 1];
strcpy(this->friends[i],tempFam.friends[i]);
}
}
return * this;
}
}
ostream & operator << (ostream & buffer, family & fam)
{
buffer << "Family ID: " << fam.getId() << endl;
buffer << " Name: " << fam.getName() << endl;
buffer << " Members: " << fam.getMembers() << endl;
buffer << " Friends: ";
fam.getFriends(buffer);
buffer << endl;
return buffer;
}
------------------------------------------------------------------------------------------
//family.h
#ifndef FAMILY_H
#define FAMILY_H
#include <iostream>
#include <string.h>
using namespace std;
class family
{
private:
const int MAX_FRIENDS = 3;
char * ID;
char * name;
int members;
int nFriends;
char * friends[3];
public:
// Constructors/Destructors
family();
family(char*, char*, int);
~family();
// Accessors
char * getId();
char * getName();
int getMembers();
int getFriendCount();
char * getFriend(int) const;
void getFriends(ostream & buffer);
// Mutators
bool addFriend(const char *);
// Operators
const family & operator = (const family &);
friend ostream & operator << (ostream &, family &);
};
#endif
------------------------------------------------------------------------------------------
//familymgr.cpp
#include "familymgr.h"
familymgr::familymgr()
{
families = new hashtable();
outFile.open("assigned.txt");
}
familymgr::~familymgr()
{
if(families)
delete families;
outFile.close();
}
void familymgr::printAllFamilies()
{
outFile << * families;
}
void familymgr::printGroup(family *)
{
}
void familymgr::printSmallCircle(char * thing)
{
family * fam = families->lookup(thing);
outFile << "Printing family and immediate friends " << thing << endl;
outFile << "== Family ==" << endl;
outFile << * fam << endl;
outFile << "== Friends (1 level) ==" << endl;
cout << endl<< endl<< endl<< endl<< endl<< fam->getFriendCount() << endl;
for(int i = 0; i < 3; i++)
{
if(families->lookup(fam->getFriend(i)))
outFile << * families->lookup(fam->getFriend(i));
}
}
void familymgr::addFamily(family & fam)
{
families->insert(fam.getId(),fam);
}
------------------------------------------------------------------------------------------------------------
//familymgr.h
#ifndef FAMILYMGR_H
#define FAMILYMGR_H
#include <iostream>
#include <fstream>
#include "hashtable.h"
using namespace std;
class familymgr
{
private:
hashtable * families;
ofstream outFile;
public:
// Constructors/Destructors
familymgr();
~familymgr();
// Accessors
void printAllFamilies();
void printGroup(family *);
void printSmallCircle(char *);
// Mutators
void addFamily(family &);
};
#endif
-----------------------------------------------------------------------------------------------------
//hashtable.cpp
#include "hashtable.h"
hashtable::hashtable()
{
tableCount = 0;
tableSize = MAX_CAP;
famTable = new hashEntry * [tableSize];
for (int i = 0; i < tableSize; i++)
{
famTable[i] = NULL;
}
}
hashtable::hashtable(int x)
{
tableCount = 0;
tableSize = x;
famTable = new hashEntry * [tableSize];
for (int i = 0; i < tableSize; i++)
{
famTable[i] = NULL;
}
}
hashtable::~hashtable()
{
destroyTable();
}
family * hashtable::lookup(char * id) const
{
size_t i = hash(id);
hashEntry * curr = famTable[i];
while(curr)
{
if(curr->data.getId())
{
char * tID = new char[strlen(curr->data.getId())];
strcpy(tID,curr->data.getId());
if(strcmp(id, tID) == 0)
{
delete tID;
return & curr->data;
}
else
{
delete tID;
curr = curr->next;
}
}
}
curr = NULL;
return NULL;
}
int hashtable::getSize() const
{
return tableSize;
}
void hashtable::dumpTable()
{
for(int i = 0; i < tableSize; i++)
{
for(hashEntry * curr = famTable[i]; curr; curr = curr->next)
{
cout << curr->data << endl;
}
}
}
void hashtable::insert(char * id, const family & fam)
{
size_t i = hash(id);
hashEntry * temp = new hashEntry(fam);
temp->next = famTable[i];
famTable[i] = temp;
tableCount++;
}
size_t hashtable::hash(char * id) const
{
size_t index = id[0];
size_t length = strlen(id);
for(int i = 1; i < length; i++)
{
index = (int) id[i] + (index * 32);
}
return index % tableSize;
}
void hashtable::destroyTable()
{
for(int i = 0; i < tableSize; i++)
{
hashEntry * head = famTable[i];
hashEntry * curr;
while(head)
{
curr = head->next;
head->next = NULL;
delete head;
head = curr;
}
}
delete [] famTable;
}
ostream & operator << (ostream & buffer, hashtable & entry)
{
hashtable::hashEntry * curr;
for(int i = 0; i < entry.tableSize; i++)
{
buffer << "table[" << i << "]:" << endl << "List:" << endl;
for(curr = entry.famTable[i]; curr; curr = curr->next)
{
buffer << curr->data;
}
buffer << setw(20) << right << setfill('-') << "" << endl;
}
return buffer;
}
const hashtable & hashtable::operator = (const hashtable & temp)
{
if(this == & temp)
{
return *this;
}
else
{
destroyTable();
famTable = new hashEntry * [MAX_CAP];
tableCount = temp.tableCount;
tableSize = temp.tableSize;
for(int i = 0; i < tableSize; i++)
{
if(temp.famTable[i] == NULL)
{
famTable[i] = NULL;
}
else
{
famTable[i] = new hashEntry(temp.famTable[i]->data);
hashEntry * curr = temp.famTable[i]->next;
hashEntry * tNext = famTable[i];
while(curr)
{
tNext->next = new hashEntry(tNext->data);
curr = curr->next;
tNext = curr->next;
}
tNext->next = NULL;
}
}
return * this;
}
}
-----------------------------------------------------------------------------------------------
//hashtable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <iostream>
#include <iomanip>
#include "family.h"
using namespace std;
class hashtable
{
private:
// Hash Entry Node
struct hashEntry
{
// Constructors/Destructors
hashEntry(const family & fam)
{
data = fam;
next = NULL;
}
family data;
hashEntry * next;
};
const size_t MAX_CAP = 7877;
int tableCount;
int tableSize;
hashEntry ** famTable;
public:
// Constructors/Destructors
hashtable();
hashtable(int);
~hashtable();
// Accessors
family * lookup(char *) const;
int getSize() const;
void dumpTable();
// Mutators
void insert(char *, const family &);
size_t hash(char *) const;
void destroyTable();
// Operators
friend ostream & operator << (ostream &, hashtable &);
const hashtable & operator = (const hashtable &);
};
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.