Make your own free website on Tripod.com

TTS

Home

About Me | THF | Favorite Links | Contact Me
THF

Enter subhead content here

//----------------------------------------------------------------------- // 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;

Enter content here

Enter supporting content here