C++ HARD PROJECT USE GETLINE.

The Universal List

In our upcoming projects we will find a lot of use for an extremely versatile container, one that can hold anything without size limitations and easily change its size to fit the requirements of the moment. This list will be similar to the sequence class that we created for Project Two, but it will be implemented differently and the iterator access will be done as an external iterator. This list will also be implemented as a template, allowing it to hold any type of data. This will be our universal list.

Our list will be a doubly linked list. In a doubly linked list each node has a pointer pointing to the next node and another one pointing to the previous node. (The node after the last item is NULL and the node previous to the first one is NULL as well.) This will require the definition of a different node class from whats in the book (p. 324). So you should start your project by making a Dnode class for nodes appropriate for use in a double linked list. Make this class template so it can hold any kind of data. You will need functions to access next, previous, and data as well as functions to set_next, set_previous and set_data. You should provide a constructor that uses default arguments that will set the pointers to NULL.

Now using, this node class, develop a template list class. You will need pointers for head and tail, and these may initially be the only private variables that you need. Your class will have functions for front_insert, rear_insert, front_remove, and rear_remove. Remember to program incrementally. To help you with this I have written a file called main1.cc. When you first open this file you will see that everything has been commented out, except the default constructor for the Dlist class. So begin by writing just the Dnode class, and then a list class with just a default constructor. Compile and run. Then uncomment the next block of code and write the implementation for the functions that are called in that block. (Note that STL classes dont have show_all functions, but I find it very useful to have one as you develop the class.) Continue this progress, compiling and running for each block as you uncomment it. If you get a crash go back and fix it before going on. (Compile with g++ -g main1.cc)

The list is holding dynamic memory (although the node class does not). This means that the default forms of the Big 3 do not work correctly so you will need to define a Big 3 for this class. The destructor is much the same as one for a singly linked list, but the other two are different because in copying the list you must remember to maintain both pointers. Work carefully and use drawings. A minor misstep and can lead to major seg faults on down the road. There is code that does some testing of these in the main1 file as well.

The last thing that you will develop in this process is a bidirectional, external iterator. You will need to make an additional class for this, a class which will closely parallel the node_iterator class in the book. (p. 330). You will then alter the list class to include begin, end, r_begin, and r_end functions (book: p. 338)[1], and finally adding insert_before and insert_after functions that will each take an iterator and an item to be item to be added, and a remove function that takes an external iterator as its argument.

The Application Color Squares

As many of you may know colors on a computer are frequently represented as a hexadecimal number, such as cc0099. (Hexadecimal numbers are base 16 numbers and consists of the digits 0 f.) This number is actually three numbers, with the first two digits representing the intensity of red, the second two the amount of green and the third pair blue. There are 256 possible values for each color. (A total of 16,777,216 different colors can be represented in this way with 000000 being black and ffffff being white.)

I have developed a small class to store color swatches, much like something used in a paint store. Each swatch consists of a hexadecimal number representing the color, and two decimal numbers representing the dimensions of the swatch in millimeters. This class is in ~jdolan/cs2401/projects/project4. I have also provided a data file listing a whole collection of these swatches called swatches.txt. There are also a couple of executables that will convert these numbers in viewable html files, as well as the application for the program, main2.cc. (This part will compile with g++ -g swatch.cc main2.cc)

This application reads data from the aforementioned data file, and place the predominantly red colors at the start of the list, and the predominantly green colors at the back of the list, and the predominantly bluecolors at the spot immediately following the centermost spot in the list.

It then

Makes a copy of the list using either your copy constructor or your overloaded assignment operator

Removes the front, back and centermost swatch from the copy.

Outputs the original list frontwards

Outputs the copy frontwards.

Outputs the original list backwards.

Destroys the original list by alternating between removal of the first item and the last item, outputting each item as it is removed.

Outputs the copy backwards.

Notice that there is no user interaction in this application. It simply runs the test and stops, outputting the results to the screen, one swatch per line with two or more blank lines between each of the outputs. Although it is not required you can see the colors by :

Redirect the output of your program to a file: a.out > result

Run either: p1p2_mkhtml result OR: labs_mkhtml result depending on what machine youre on.

This will create a .html file which you can transfer to your local machine via winscp or something similar, if you are not in lab, and which you can then open by double-clicking

All code should be adequately documented and nicely formatted. Your submission should include all four of the files that I am giving you as well as files for your dnode.h, iterator.h, dlist.h and dlist.template.

main1.cc-----------------------------------------------------

#include #include "dlist.h" using namespace std; int main(){ // default constructor for the list dlist lis1, lis2; int tmp; // testing rear_insert and show /* for(int i = 0; i<10; ++i) lis1.rear_insert(i); lis1.show(); cout<::iterator it1; for(it1=lis1.begin(); it1 != lis1.end(); ++it1) cout<<*it1< copy(lis1); lis1 = lis2; for(it1=lis1.begin(); it1 != lis1.end(); ++it1) cout<<*it1<

main2.cc-----------------------------------------------------

#include #include #include "dlist.h" #include "swatches.h" using namespace std; int main() { dlist swatches; dlist::iterator it; ifstream fin; fin.open("swatches.txt"); if (fin.fail()) { cout << "Could not open input file." << endl; return 1; } Swatch tmp; while (fin >> tmp) { int red = tmp.get_red(); int green = tmp.get_green(); int blue = tmp.get_blue(); if ( (red>=green) && (red>=blue) ) // red is dominant { swatches.front_insert(tmp); } else if ( (green >= red) && (green >= blue) ) // green is dominant { swatches.rear_insert(tmp); } else // blue is dominant { it = swatches.begin(); for(int i = 0;i < swatches.size()/2;i++) ++it; // loop moves iterator to the middle if(swatches.size()%2 == 1){ //if(swatches.size()>2){ //it++; //} swatches.insert_before(it,tmp); } else{ swatches.insert_after(it,tmp); } } } fin.close(); dlist copy(swatches); // make a copy // remove the front, back, and centermost swatch from the copy copy.front_remove(); copy.rear_remove(); it = copy.begin(); for(int i =0; i < copy.size()/2; ++i) ++it; //if(copy.size()%2 ==1) ++it; // if list has a true middle // step up into it copy.remove(it); // output the original list frontwards for (dlist::iterator i=swatches.begin(); i != swatches.end(); ++i) { cout << *i << endl; } cout << endl << endl; // some space // output the copy frontwards for (dlist::iterator i=copy.begin(); i != copy.end(); ++i) { cout << *i << endl; } cout << endl << endl; // some space // output the original backwards for (dlist::iterator i=swatches.r_begin(); i != swatches.r_end(); --i) { cout << *i << endl; } cout << endl << endl; // some space // destroy the original list by alternating between removal of first and // last items. Print each item as it is removed int counter=0; while (swatches.size() > 0) { cout<<*swatches.begin()< 0){ cout<<*swatches.r_begin()<::iterator i=copy.r_begin(); i != copy.r_end(); --i) { cout << *i << endl; } return 0; }

swatches.h--------------------------------------------------

#include #include #include #ifndef SWATCH_H #define SWATCH_H class Swatch{ public: static const unsigned long ONE_COLOR = 256; static const unsigned long TWO_COLOR = 256*256; // CONSTRUCTORS Swatch(); Swatch(unsigned long n_color, int n_width, int n_height); // ACCESSOR FUNCTIONS unsigned long get_color(); std::string color_string(); unsigned long get_red(); unsigned long get_green(); unsigned long get_blue(); int get_width(); int get_length(); // MODIFICATION FUNCTIONS void set_color(unsigned long n_color); void set_color(std::string n_color); void set_width(int n_width); void set_length(int n_length); // FRIENDS friend std::ostream& operator <<(std::ostream& outs, const Swatch& sw); friend std::istream& operator >>(std::istream& ins, Swatch& sw); private: unsigned long color; unsigned long red, green, blue; int width; int length; }; #endif 

swatches.cc-------------------------------------------------

#include "swatches.h" #include #include #include using namespace std; // CONSTRUCTORS Swatch::Swatch(){ color=0; red=green=blue=0; width=0; length=0; } Swatch::Swatch(unsigned long n_color, int n_width, int n_length){ color=n_color; red = n_color/TWO_COLOR; blue = n_color%ONE_COLOR; green = (n_color/ONE_COLOR)%ONE_COLOR; width=n_width; length=n_length; } // ACCESSOR FUNCTIONS //This function returns the color as a number which is how it is //actually stored unsigned long Swatch::get_color(){ return color; } //This function returns a string version of the color number in standard // RGB format std::string Swatch::color_string(){ char a_c_string[10]; sprintf(a_c_string,"%x",color); std::string tmp(a_c_string); int leading = 6 - tmp.length(); if(leading <= 0) return tmp; else{ std::string padding; for(int i=0; i>(std::istream& ins, Swatch& sw){ ins>>hex>>sw.color>>dec>>sw.width>>sw.length; sw.red = sw.color/sw.TWO_COLOR; sw.blue = sw.color%sw.ONE_COLOR; sw.green = (sw.color/sw.ONE_COLOR)%sw.ONE_COLOR; return ins; } 

swatches.txt--------------------------------------

fbc454 12 35 b71bfd 23 49 835fb0 21 58 0f59c2 18 51 23b873 27 35 3ebfe7 21 44 a0ca1b 15 48 0e1fdc 14 40 509ce6 15 54 42d6fa 20 37 487ceb 24 45 1f7532 16 56 c339ea 21 58 9ca5b2 18 44 38fbf4 15 43 f0df60 24 54 004164 15 33 1cdec9 13 47 1c054e 10 42 d2f3a6 26 57 ce7731 26 56 5fdf7f 24 51 269f39 23 54 29a1ab 21 56 ad2279 18 57 7e5bee 23 56 952e99 27 48 8a7a99 12 56 e7482c 16 46 1f620a 10 45 a06362 24 48 4ca036 20 50 1e15b9 14 43 a2af11 20 37 594196 25 40 7114c4 18 31 d47692 15 35 b5ebdc 20 52 fe4297 22 53 3470dd 19 55 505300 23 36 67cbea 14 37 7a3bda 18 40 b5ed95 25 36 487e53 17 30 a9c3e8 11 49 ce1dca 12 53 7fa978 16 49 453990 11 57 cb283e 18 55 ceb3dd 12 41 5f7edf 17 44 2ae7f8 10 31 cdf64d 22 46 e572bc 10 30 cd0e94 23 58 bec9b2 17 35 acb2ec 29 29 b5f6f1 20 58 e52236 19 46 c4e16f 27 41 06f6cc 13 42 61d279 16 53 a49b72 24 51 60d634 28 35 20b1cd 17 29 cac73d 21 42 ec1f75 18 35 e47fc9 21 30 c735f9 27 50 10fc42 19 48 090d24 24 39 4edd5e 11 57 8c092b 18 39 0f5e9a 29 44 b32401 17 42 f134e9 17 46 442489 11 29 502f64 21 31 46c5dd 23 32 39925c 21 40 eb7e6f 28 34 fc0765 13 35 b4302b 17 40 696c21 15 36 c32ddd 16 44 de2806 19 35 e23d82 29 56 509a8f 21 37 406488 14 43 0a8343 23 29 f7ecd6 13 37 d067bc 17 54 301bb9 28 33 95515d 21 31 4dc9cf 11 45 317857 20 52 333675 19 31 a409cd 25 52 0d75bd 12 54 1cba01 28 46 5266ae 26 33 15a4d9 26 45 2de1c0 21 37 3f29c4 12 54 ed2883 19 51 917f3b 14 45 c0916e 15 33 f7069c 12 46 bd862f 10 33 e4b841 23 34 efd229 20 33 6c6dbe 17 55 1ba343 20 43 c56568 22 29 766175 22 35 91d280 18 52 e69ad5 11 34 800134 23 47 7edb70 15 44 73469c 24 52 1a3523 23 39 2be560 24 35 3ef13c 22 41 44aaaf 19 37 f69ae0 12 30 54ba2a 22 36 25c38a 28 36 819fa5 11 48 60e9c0 27 46 d4a1ca 13 30 0c4c91 22 57 bd5b7c 28 58 c16557 18 50 2e91dc 21 41 a8db98 10 52 d0ad0b 20 30 931c6a 10 30 27a94f 20 43