// ANNOTATED VERSION -- TIED TO BOOK: C++ PRIMER, by LIPPMAN AND LAJOIE // ALL PAGE REFERENCES ARE TO THAT BOOK EXCEPT WHERE NOTED OTHERWISE // THIS IS NOT AN HTML DOCUMENT SO ANY URLS ARE NOT ACTIVE BUT MUST BE // PASTED INTO A BROWSER TO BE USED. // COM1201, Spring 2000, Professor Futrelle // lab2 one-file implementation // (initially, some expts.) // File lab2-annotated.cpp, 4/16/2000, by RPF /* Lab 2 deals with pointer-based sorting. This approach avoids interchanging potentially large records. Instead, it keeps track of the record order through an array of keys. These keys are integers that are the positions of the records in their own array. The input file and the output are appended to this file. This code does not contain the full instructions for the lab. They will be handed out later. But briefly: - You will adapt the code here to create your own version of it. - You will make up your own record type, about something you're interested in, e.g., music, sports, movies, philosophy. - You will design better output formats for the sort results. - You will test to see if the sort is stable by using some records that have equal values in certain fields, and resorting. - You will break up your file into three, including one header file. - You will explain carefully what you've done and add comments as necessary (but not more than necessary!) The programming here uses a class-based strategy, much in the same form used in Java. Also, the comments are in javadoc stylying, appearing immediately before the item being documented and in the asymmetric form below */ /** ....stuff here... */ // (below, do not mix plain new includes with old ".h" includes) // includes: pgs. 13, 21 // for curent standard headers (no ".h"), sec. D.2 of: http://www.jbpub.com/dale/AppD.htm // strings: http://www.msoe.edu/eecs/cese/resources/stl/string.htm #include // file streams and io streams: iostreams in general, all of Chapter 20. // see also: http://www.engin.umich.edu/class/eecs280/w99/lecture/filestreams.html #include #include // The standard namespace: Sec. 8.6.4, pg. 440+ using namespace std; // don't forget this! // note that file stream parameters are passed as references // ***************************************************************** /** MedRecord is an example of the type of class you will be creating for your own project. It includes both numerical and string attributes. */ // Classes, all of Chap. 13, pg. 613+ class MedRecord { public: string name; int ageMonths; string diagnosis; // static members: Sec. 13.5, pg. 641+, initialization: bottom of pg. 642. static char* chBuffer; // (must be initialized outside class def.) // Constructors: Sec. 14.2, pg. 691+ /** Straightforward form of the constructor */ MedRecord(string aName, int anAgeMonths, string aDiagnosis) { name = aName; ageMonths = anAgeMonths; diagnosis = aDiagnosis; } /** The default constructor inserts trivial values. */ MedRecord() { name = ""; ageMonths = -99; diagnosis = ""; } /** Reads one record from a file. */ void readRecord(fstream& stream) { stream.getline(chBuffer, 1023); // getline() beginning of Sec. 6.7, pg. 273 // more starting on pg. 1087 name = chBuffer; stream.getline(chBuffer, 1023); ageMonths = atoi(chBuffer); // atoi() pg. 371, not just command line args. // and doesn't seem to need ctype.h (now cctype). stream.getline(chBuffer, 1023); diagnosis = chBuffer; } /** Prints a record to a file stream, one item per line. */ void printRecord(fstream& stream){ stream << name << '\n' << ageMonths << '\n' << diagnosis << '\n'; } /** Prints a record to cout. */ void printRecord(){ cout << name << '\n' << ageMonths << '\n' << diagnosis << '\n'; } /** Prints only one field to cout. */ void printSelectedRecord(int sw){ // switch: Sec. 5.4, pg. 202+ and pay attention to "break" switch (sw) { case 0: cout << name; break; case 1: cout << ageMonths; break; case 2: cout << diagnosis; break; } cout << " "; } }; // End of MedRecord class definition // static member initialization: bottom of pg. 642. char* MedRecord::chBuffer = new char[1024]; // init of static class member // ***************************************************************** /** This Sorting class contains all the data structures and functionality for reading, sorting and writing records. The primary point of the functionality below is that sorting can be done on a chosen field of the records. This is governed by compareSwitch, and int parameter that determines what field compare() looks at. */ class Sorting { public: MedRecord* records; int numRecords; int* keys; string metadata; int compareSwitch; static char* chBuffer; /** Sets up the record and key arrays. */ Sorting(int noRecords) { // use of new for arrays: Sec. 8.4.3, pg. 414+ records = new MedRecord[noRecords]; keys = new int[noRecords]; for(int i=0; i < noRecords; i++) keys[i] = i; numRecords = noRecords; } /** Not used in this demo. */ void getMetadataFromUser (){ cout << "Please type in one line of metadata to set value:\n"; cin.getline(chBuffer, 1023); metadata = chBuffer; } /** Echoes metadata string to cout */ void echoMetadata () { cout << "Metadata line: " << metadata << endl; } /** Prepends "Metadata line: " to first line in file. */ void writeMetadataToFile(fstream& stream) { stream << "Metadata line: " << metadata << '\n'; } /** The metadata string is stored internally with "Metadata line: " stripped. */ void readMetadataFromFile(fstream& stream) { stream.getline(chBuffer, 1023); metadata = chBuffer; metadata.erase(0,15); } /** If records are created or altered internally, can be written out. */ void writeSomeRecordsToFile(int some, fstream& stream) { for(int k=0; k < some; k++) { records[k].printRecord(stream); } } /** Prints full record to cout. */ void printSomeRecords(int some) { for(int k=0; k < some; k++) { records[k].printRecord(); } } /** Loads records from file into records[]. */ void loadSomeRecords (int some, fstream& stream) { for(int k=0; k < some; k++) { records[k].readRecord(stream); } } // Sorting tools adapted for key-based sorting. // All functions will assume MedRecord types. // They are also member functions with full access to the arrays. /** Given a key compares fields determined by compareSwitch. Returns -1, 0, or +1, for val1 LT, EQ, or GT val2. */ int compare(int key1, int key2) { switch (compareSwitch) { // comparison operators, <, ++, >, pgs. Sec. 4.3, pg. 146+ case 0:{ if(records[key1].name < records[key2].name) return -1; if(records[key1].name == records[key2].name) return 0; else return 1;} case 1:{ if(records[key1].ageMonths < records[key2].ageMonths) return -1; if(records[key1].ageMonths == records[key2].ageMonths) return 0; else return 1;} case 2:{ if(records[key1].diagnosis < records[key2].diagnosis) return -1; if(records[key1].diagnosis == records[key2].diagnosis) return 0; else return 1;} } } /** The exch function interchanges two keys in the key array. */ void exch(int index1, int index2) { int t = keys[index1]; keys[index1] = keys[index2]; keys[index2] = t; } /** Uses the same compare function that sort itself does. */ void compexch(int index1, int index2) { if (compare(keys[index1], keys[index2]) > 0) exch(index1, index2);} /** The optimized insertion sort from Sedgewick, Prog. 6.3, pg. 276, adapted for key-based sorting. Printing is included to monitor the operation of the sort. */ void insertion(int l, int r) { int i; for (i = r; i > l; i--) compexch(i-1, i); printSomeRecordsInOrder(8); for (i = l+2; i <= r; i++) { int j = i; int vkey = keys[i]; while (compare(vkey, keys[j-1]) < 0) { keys[j] = keys[j-1]; j--;} keys[j] = vkey; printSomeRecordsInOrder(8); } } /** Print out the records in key-sorted order. Only the sorted field is printed. */ void printSomeRecordsInOrder(int some){ cout << "\nrecords:"; for(int i=0; i < some; i++) records[keys[i]].printSelectedRecord(compareSwitch); } /** Prints key sequence. */ void printSomeKeys(int some) { cout << "\nSome keys: "; for(int i=0; i < some; i++) cout << keys[i] << ' '; cout << endl; } /** Prevents window from closing until requested */ void quit() { char buff[4]; cout << "\nHit return to quit."; cin.getline(buff,2); } }; // End of Sorting class definition. char* Sorting::chBuffer = new char[1024]; // another static var init // ***************************************************************** void main () { /* The following is the kind of working note I included to guide my work. Your final version should have a comment here that explains what you're trying to do in main(). Further notes in the body of main() may also be needed. Subsequent plan for development and testing: Adapt insertion sort to a compare function. Write some compare functions. Flesh out sample records file. Read in a sort some records. */ Sorting* s = new Sorting(10); s->compareSwitch = 1; // for age fstream infile("medrecordbase.dat",ios::in); s->readMetadataFromFile(infile); s->echoMetadata(); s->loadSomeRecords(9, infile); s->printSomeRecordsInOrder(8); infile.close(); s->insertion(0,7); // do the sort (finally!) cout << endl << endl; s->printSomeRecordsInOrder(8); s->printSomeKeys(8); s->quit(); } /* This is the input data file: Metadata line: 9 MedRecords. R P Futrelle COM1201, Sp2000, 4/16/00. Harvey Hamster 23 Just getting old. To be expected. Su Boo 11 Limping. Nothing broken. Should clear up in a month. Snoopsie 36 Quite an old animal. Check for terminal disease(s). Fuzzy 3 May need some vaccinations. Mr. Jump 17 Seems to think it's a rabbit. Possible neurological disorder. Lappy 14 Too quiet. Running a fever. Nappy 8 Quite docile. Had ear infection. Cleaned and antibiotic shot given. Sappy 19 Bitten on ear by Nappy. Should heal but will have slightly split ear. Rudolph 1 Normal for an infant. */ /* This is the output of a run, sorting on age: Metadata line: 9 MedRecords. R P Futrelle COM1201, Sp2000, 4/16/00. records:23 11 36 3 17 14 8 19 records:3 23 11 36 8 17 14 19 records:3 11 23 36 8 17 14 19 records:3 11 23 36 8 17 14 19 records:3 8 11 23 36 17 14 19 records:3 8 11 17 23 36 14 19 records:3 8 11 14 17 23 36 19 records:3 8 11 14 17 19 23 36 records:3 8 11 14 17 19 23 36 Some keys: 3 6 1 5 4 7 0 2 Hit return to quit. */