|
//-----------------------------------------------------------------------
// File: prob.cc
// Description: Build hobbit family tree
// Author: Chau-Wen Tseng (tseng@cs.umd.edu)
//-----------------------------------------------------------------------
#include
#include
#include
// Uncomment the following lines if using APCS classes
// #include "apvector.h"
// #include "apmatrix.h"
// #include "apstack.h"
// #include "apqueue.h"
// #include "apstring.cpp"
#include "apstring.cpp"
const int MAXLEN = 50; // maximum number of hobbit families
int families; // number of actual hobbit families
apstring names[MAXLEN]; // hobbit family names in alphabetical order
//-----------------------------------------------------------------------
// printDistance
//-----------------------------------------------------------------------
// variables used by printDistance() & printTree()
double height[MAXLEN]; // height of tree branches
int merge[MAXLEN][2]; // sequence of joins / merges
void
printDistance(double ht, int name1, int name2)
{
static int treeSize;
height[name2] = ht;
merge[treeSize][0] = name1;
merge[treeSize][1] = name2;
treeSize++;
if (treeSize == (families - 1))
height[name1] = ht;
cout << ht << " " << names[name1] << " " << names[name2] << endl;
}
//-----------------------------------------------------------------------
// printTree()
//-----------------------------------------------------------------------
void
printTree()
{
apstring n1, n2;
int i,j;
bool active[MAXLEN];
//----------------------------------------------------
// Draw family tree
//----------------------------------------------------
const int MAXTREE = 60;
double position[MAXLEN];
double scale;
int tmp, name1, name2;
for (i = 0; i < families; i++) {
position[i] = 0.0;
}
// decide order of names
for (i = 0; i < families; i++) {
active[i] = true;
}
// place names next to neighbors in tree
// use decreasing scale so there's always space to insert
scale = 1000.0;
name1 = merge[families-2][0];
name2 = merge[families-2][1];
position[name1] = 1000.0;
position[name2] = position[name1] + 2*scale;
active[name1] = false;
active[name2] = false;
for (i = families-3; i >=0; i--) {
name1 = merge[i][0];
name2 = merge[i][1];
if (active[name1] && active[name2]) {
cout << "CROSSING BRANCH ERROR!" << endl;
position[name1] = i * scale;
position[name2] = position[name1] + scale;
}
else if (active[name1]) {
position[name1] = position[name2] + scale;
}
else if (active[name2]) {
position[name2] = position[name1] + scale;
}
else {
cout << "MERGING ERROR!" << endl;
}
active[name1] = false;
active[name2] = false;
scale = 0.5 * scale;
}
// find actual order of names
int order[MAXLEN];
int lineNum[MAXLEN];
for (i = 0; i < families; i++) {
order[i] = i;
}
for (i = 0; i < families-1; i++) {
for (j = i+1; j < families; j++) {
if (position[order[j]] < position[order[i]]) {
tmp = order[i];
order[i] = order[j];
order[j] = tmp;
}
}
}
// put names on every other line
for (i = 0; i < families; i++) {
lineNum[order[i]] = 2*i;
}
// find tallest branch
double maxHeight = 0.0;
for (i = 0; i < families; i++) {
if (height[i] > maxHeight)
maxHeight = height[i];
}
// keep tree in character array
char trees[MAXLEN*2][MAXTREE];
for (i = 0; i < 2*MAXLEN; i++) {
for (j = 0; j < MAXTREE; j++) {
trees[i][j] = ' ';
}
}
// draw branches
int branchLen;
for (i = 0; i < families; i++) {
branchLen = (int) (height[i] * (double) MAXTREE / maxHeight);
if (branchLen > 0) {
for (j = 1; j < branchLen; j++)
trees[lineNum[i]][MAXTREE-j] = '-';
}
}
// connect branches
for (i = 0; i < families-1; i++) {
branchLen = (int) (height[merge[i][1]] * (double) MAXTREE / maxHeight);
for (j = lineNum[merge[i][0]]+1; j < lineNum[merge[i][1]]; j++) {
trees[j][MAXTREE-branchLen] = '|';
}
}
// actually output family tree
cout << endl;
cout << " Maximum Tree Height = " << maxHeight << endl;
cout << " 100% 75% 50% 25% 0% " << endl;
cout << " 987654321098765432109876543210987654321098765432109876543210 " << endl << endl;
for (i = 0; i < (2*families)-1; i++) {
if (i == families-1) {
cout << "-----";
}
else {
cout << " ";
}
for (j = 0; j < MAXTREE; j++) {
cout << trees[i][j];
}
if ((i % 2) == 0) {
cout << " " << names[order[i/2]] << endl;
}
else {
cout << endl;
}
}
}
//-----------------------------------------------------------------------
// main
//-----------------------------------------------------------------------
int main()
{
apstring n1, n2;
double dist[MAXLEN][MAXLEN];
int i, j, current, name1, name2;
bool active[MAXLEN];
double minDist;
//----------------------------------------------------
// Read in distances
//----------------------------------------------------
cin >> families;
// read in names & distances between 1st name and others
for (i = 1; i < families; i++) {
cin >> dist[0][i];
if (i == 1) {
cin >> names[0];
}
else {
cin >> n1;
if (n1 != names[0]) {
cout << "ERROR: conflicting names at position # 0: ";
cout << names[0] << " " << n1 << endl;
}
}
cin >> names[i];
}
// read in distances between other names
for (i = 1 ;i < families; i++) {
for (j = i+1; j < families; j++) {
cin >> dist[i][j];
cin >> n1;
cin >> n2;
if (n1 != names[i]) {
cout << "ERROR: conflicting names at position # " << i << ": ";
cout << names[i] << " " << n1 << endl;
}
if (n2 != names[j]) {
cout << "ERROR: conflicting names at position # " << j << ": ";
cout << names[j] << " " << n2 << endl;
}
}
}
//----------------------------------------------------
// Find minimum distances
//----------------------------------------------------
double height[MAXLEN];
int merge[MAXLEN][2];
for (i = 0; i < families; i++) {
active[i] = true;
}
for (current = 0; current < families-1; current++) {
// find smallest remaining distance
minDist = 9999999.0;
for (i = 0 ;i < families; i++) {
for (j = i+1; j < families; j++) {
if (active[i] && active[j]) {
if (dist[i][j] < minDist) {
minDist = dist[i][j];
merge[current][0] = i;
merge[current][1] = j;
}
}
}
}
// merge 2nd name into 1st
name1 = merge[current][0];
name2 = merge[current][1];
// store distance between 1st & 2nd names, deactivate 2nd name
height[name2] = 0.5 * minDist;
active[name2] = false;
}
cout.setf(ios::showpoint);
for (i = 0; i < families-1; i++) {
printDistance(height[merge[i][1]], merge[i][0], merge[i][1]);
}
// printTree() is optional, requires correct values for
// int families = total # of hobbit families
// apstring names[] = names in alphabetical order
printTree();
return 0;
|  |
|
