Calculating "The Sum of Its Parts"
Background
"The whole is greater than the sum of its parts" is a central theme
of Gestalt psychology, and for humans it may be a true observation.
Computers are much more literal-minded.
Description
In this assessment, you will construct a representation of a complex
structure, a hospital that is composed of many parts. There are too
many parts for a human to keep track of, which is why we want the
computer to do it for us. The description of the hospital is contained
in the file definitions.txt.
Layout of a floor in the hospital
The building has ten floors. Each floor has four wings emanating from a central core.
Each wing contains two long corridors joined at the end by a short connecting corridor.
Each long corridor contains twenty-one patient rooms. Each connecting corridor contains five supply rooms.
The hospital is described by a labeled tree, whose nodes are of type Part.
A node contains children nodes corresponding to its subparts, as shown
in the figure below. Each edge is labeled by the number of subparts the
node contains. For example, the label 10 on the edge from hospital to floor
indicates that the hospital has ten floors. You can assume there are no
duplicate edges, that is, there is at most one edge between any two
nodes.
Tree representation of the hospital
The driver program main.cpp first loads the file definitions.txt, which contains the subpart relationships that define the hospital. It then processes queries from the file queries.txt, which contains two kinds of queries about the hospital. The whatis query requests the description of a Part. The howmany query is the heart of the exercise. It asks how many instances of a Part are contained in another Part.
You are provided with main.cpp and a skeleton version of parts.h as a starting point. Your job is to complete the parts.h file (and write parts.cpp,
if you deem necessary). The steps below point the way toward a
solution, but they do not cover every detail, so if you find you need
to create additional functions or member items, feel free to do so.
#ifndef _PARTS_H_
#define _PARTS_H_
#include <vector>
#include <map>
#include <string>
using namespace std;
//**************** Part ****************
class Part {
public:
string name;
map<Part*, int> subparts;
Part(string const &n) : name(n) {};
void describe(void);
int count_howmany(Part const *p);
};
//**************** NameContainer ****************
class NameContainer {
private:
map<string,Part*> name_map;
public:
NameContainer(void) {};
Part* lookup(string const &name) {
for( map<string, Part*>::iterator it = name_map.begin();
it != name_map.end(); it++ )
{
if( it->first == name )
return it->second;
}
Part *new_part = new Part( name );
name_map[name] = new_part;
return name_map[name];
}
};
NameContainer partContainer;
//**************** Part Member Functions ****************
void Part::describe(void) {
cout << "Part " << name << "subparts are" << endl;
if( subparts.empty())
{
cout << " There no subparts" << endl;
return;
}
for( map<Part*, int>::iterator it = subparts.begin();
it != subparts.end(); it++ )
{
cout << " " << it->second << " " << it->first->name << endl;
}
cout << endl;
}
int Part::count_howmany(Part const *p) {
if( this->name == p->name ) return 1;
if( this->subparts.empty() )return 0;
int sum = 0;
for( map<Part*, int>::iterator it = subparts.begin();
it != subparts.end(); it++ )
{
sum += ( ( it->second ) * ( it->first->count_howmany( p )) );
}
return sum;
}
//**************** Miscellaneous Functions ****************
void add_part(string const &x, int q, string const &y) {
// TODO: Finish implementation
Part *parent = partContainer.lookup(x);
Part *child = partContainer.lookup(y);
parent->subparts.insert( make_pair( child, q ) );
}
#endif