Identify yourself in your submissions, and comment your code! If you fail to put comments in EVERY file you submit, you will lose at least 10% of the assignment credit. Every source code file, Makefile, test plan file, etc, that you create MUST have the following information.
// file: sorts.h // written by: John H Stewman // on: 9/9/2004 // for: CSE 331 - Data Structures - University of Notre Dame // Programming Assignment 2 (part 1) // // This file contains three sort functions (selection, quick and shell). // The function implementations are based on examples in the Ford & Topp // textbook. Substantial help was received from John Korecki on the // shellsort.
Create a main program capable of reading files, sorting them in ascending order, and writing the results back into text files. Also, create a library of sort functions, written as template functions, and implemented using the vector container class. The sorts should be capable of sorting strings, doubles, ints, chars, etc. All sort functions MUST be implemented in a separate header file named "sorts.h".
The main program must loop until exited, display a menu, and perform the following actions on demand.
The SlowSort may be Bubble Sort (Ford & Topp, problem 3.17), Insertion Sort or Selection Sort.
The ShellSort you have already seen in Ford & Topp, problem 4.23.
The FastSort may be QuickSort or MergeSort (both in Ford & Topp, Ch 15).
You may use any implementation of these sorts (from your text or elsewhere), but make sure you put a comment in each giving the source of the algorithm.
The summary of sort statistics report should list the following.
In the class directory you will find nine (9) test files. Three are already sorted in ascending order, three are already sorted in reverse order, and three are randomly ordered. The maximum file size will be 10,000 integers. Your program must be capable of sorting that many.
Each number file will have a simple list of integers, one per line. Your program must read the files until all data values are read, and count the number of items read in the process. In other words, there is no indication in the file of how many values it contains. Read each until you get to the end of the file.
You should test your program to make sure all three of your sorts work correctly, and then run each sort in your program on each of the nine files. Use the summary of sort stats from each sort to create two tables like the one shown below. Create one table for Comparisons and another table for Data Assignments.
Comparisons by sort and array size
----------------------------------
| random | inorder | reversed
Sort | 100 1000 10,000 | 100 1000 10,000 | 100 1000 10,000
--------+-----------------------+-----------------------+---------------------
Bubble | xxx xxxx xxxxxx | xxx xxxx xxxxxx | xxx xxxx xxxxxx
| | |
Quick | xxx xxxx xxxxxx | xxx xxxx xxxxxx | xxx xxxx xxxxxx
| | |
Heap | xxx xxxx xxxxxx | xxx xxxx xxxxxx | xxx xxxx xxxxxx
Submit these: (by MIDNIGHT Tuesday, September 21, 2004) ------------- sorts.h // sorting functions prog2_1.cpp // main program and any I/O support functions testplan2_1.txt // tell me how you know your program works sortstats.txt // the tables from your sorts of the 9 "standard" input files NOTES: 1 - name the files as indicated or you will lose credit. 2 - The two text files may be Word(.doc) or PDF(.pdf) files, if you prefer. 3 - Place all files for this assignment in your .../dropbox/<your_afsid>/prog2. DO NOT create additional folders.
complex.h -- header file for a Complex number class ctester.cpp -- test program for your Complex number class implementation Makefile -- makefile for creating all executables d_matrix.h -- defines template matrix class (from Ford & Topp)
complex.cpp -- implementation of a complex number class
pixel.h -- definition and inline implementation of the pixel class
prog2_2.cpp -- main program that uses the complex number class to
create & display Mandelbrot & Julia Images
The algorithms for most of the member functions in the Complex class should be
obvious. Those that are not are described here.
In the formulae below r, r1, r2, i, i1, i2 are used to indicate the real and imaginary parts of two complex numbers. Your class definition has different member variable names AND YOU SHOULD NOT CHANGE THEM. These are examples of the calculation, only.
Addition
(c1 + c2), where c1 = r1 + i1*j and c2 = r2 + i2*j
rsum = r1 + r2
isum = i1 + i2
(c1 + r), where c1 = r1 + i1*j and r is a real number (double)
rsum = r1 + r
isum = i1
(r + c2), where r is a real number (double) and c2 = r2 + i2*j
rsum = r + r2
isum = i2
Subtraction
(c1 - c2), where c1 = r1 + i1*j and c2 = r2 + i2*j
rdiff = r1 - r2
idiff = i1 - i2
(c1 - r), where c1 = r1 + i1*j and r is a real number (double)
rdiff = r1 - r
idiff = i1
(r - c2), where r is a real number (double) and c2 = r2 + i2*j
rdiff = r - r2
idiff = - i2
Multiplication
(c1 * c2), where c1 = r1 + i1*j and c2 = r2 + i2*j
rprod = r1*r2 - i1*i2
iprod = r1*i2 + i1*r2
(c1 * r), where c1 = r1 + i1*j and r is a real number (double)
rprod = r1*r
iprod = i1*r
(r * c2), where r is a real number (double) and c2 = r2 + i2*j
rprod = r*r2
iprod = r*i2
Division
(c1 / c2), where c1 = r1 + i1*j and c2 = r2 + i2*j
rquot = (r1*r2 + i1*i2) / (r2*r2 + i2*i2)
iquot = (i1*r2 - r1*i2) / (r2*r2 + i2*i2)
(c1 / r), where c1 = r1 + i1*j and r is a real number (double)
rquot = r1/r
iquot = i1/r
(r / c2), where r is a real number (double) and c2 = r2 + i2*j
rquot = r*r2 / (r2*r2 + i2*i2)
iquot = - r*i2 / (r2*r2 + i2*i2)
Magnitude
mag = sqrt(r1*r1 + i1*i1)
Equals (==)
(r1 == r2 && i1 == i2)
Output (<<)
should output in format like this example: 3.0 - 4.5 j
make sure to separate the parts with whitespace
Input (>>)
should input assuming format like this example: 3.0 - 4.5 j
NOTE: you can use >> (no need for get() or getline(). Just make sure
you extract the op (+ or -) and the 'j' into char variables, and then
if the op is '-' make sure that the value of the imaginary coefficient
is negative.
In your program you will use two data structures to store and retrieve the colors of the various pixels in the image.
The reason we are not using 24 bit color in the matrix itself is simple. The Mandelbrot and Julia set images we are producing are based on counts that will range between 0 and 100. Since there will only be 100 unique colors in the image, we can cut the matrix size by 2/3 by keeping the true colors in the colorMap and storing colorMap indexes (or counts) in the image matrix.
The Function is ...
Z = Z*Z + C, where
Z = 0 + 0j initially, and
C is a complex number with real coefficient between -2.0 and +0.5
and imaginary coefficient between -1.5 and + 1.5
For a particular complex number C, we initialize Z to 0+0j, and then
repeatedly calculate new values for Z using this function. If the magnitude
of Z ever equals or exceeds 2.0, then it will eventually increase infinitely
and that tells us that the number C IS NOT in the Mandelbrot Set. The numbers
in the Mandelbrot Set are in some sense ATTRACTED to the origin of the
complex plane, and will never produce a Z farther away from the origin than
2.0 units. The origin thus acts as a STRANGE ATTRACTOR for these complex
numbers, with respect to this recursive formula.
To produce an image we are most interested in the members that are NOT in the set. The count of the number of times the formula must be applied to drive Z farther away from the origin than 2.0 units, is an indication of how quickly it departs when started at C. This is also a measure of how weakly it is attracted to the origin. This count can be used to color code the NON SET members into groups based on the speed of their departure.
We will treat each complex number C as a point in a 2 dimensional complex number plane. We will use an image that is 600x600 pixels, and we will let that correspond to -2.0..+0.5 along the horizontal real number axis and -1.5.. +1.5 along the vertical imaginary number axis. PLEASE NOTE that the positive imaginary axis is in the UP DIRECTION in the images we are creating.
The main program must loop until exited, display a menu, and perform the following actions on demand.
The Mandelbrot Creation algorithm looks like this.
(0) Ask the user for three positive integer numbers (R,G,B)
(1) Set the colorMap colors based on these (R,G,B values)
Set colorMap[0] to black (r,g,b) = (0,0,0)
For each entry i from 1 to 255
use the R,G,B values entered above to set the pixel colors
with assignments something like this ...
colorMap[i].setColor((unsigned char)(1+(R*count)%255), ....)
Note: you need similar value calculations for the green and blue
color components
(2) Figure out dx and dy from the ratios of complex plane size and image size
(3) For each image pixel ...
(3.a) set Z to the value 0+0j
(3.b) determine which complex number C it represents (using dx and dy)
(3.c) count the number of times Z = Z*Z+C can be applied before
Z.magnitude() is 2.0 or greater
(3.d) set the pixel value in the image matrix to the count
(4) Save the image to a Portable PixMap (.ppm) file, using the approach
below.
(5) Issue a system command to open and display the file, using xview
or eog.
NOTES:
1 - The image must be saved to a file before it can be displayed.
2 - There are several useful calls using system() in the Linux environment.
system("ls *.ppm"); // lists names of existing image files
system("clear"); // clears the screen
system("xview " + filename + " &"); // displays image using xview
system("eog " + filename); // displays image using Eye of Gnome
A Julia set uses the same formula, but the user is required to pick a particular value for C at the beginning of the process, and the initial value of Z is based on the complex number corresponding to each image pixel.
Also, the area of the complex plane of interest is -1.5 .. +1.5 on both axes.
These are the modifications to the algorithm above, in order to create a Julia Set image. (other steps are the same)
(2.5) Get user to input a complex number C
(3) For each image pixel ...
(3.a) determine which complex number Z it represents (using dx and dy)
(3.b) skip it -- nothing required
(3.c) continue with the algorithm above
Save the images in use Portable PixMap (.ppm) images files. Use ONLY raw ppm image files. These files have the following format.
magic number (Really a string -- "P6") comment (the whole line) width and height (two nonnegative integers) maximum color value (one nonnegative integer) image data .............(CAUTION) There is an ASCII version of the PPM image file format that uses space separated integers for the pixel values (r,g,b). DO NOT code your file I/O functions to assume this version. Use only the RAW ppm file format. All pixel values are single bytes (single unsigned chars) and are not separated by any spaces. They are all on a single line. That part of the file will look like garbage if you open it in a text editor.(sequence of bytes, each an unsigned char) Here is an example ------------------ P6 # CREATOR: JHS picfix version 1.0 -- 10/2/2003 300 300 255 d0^g%8%#$...........
Save Image Algorithm -------------------- - write magic number "P6" (line 1) - write comment (line 2) - write width & height (line 3) - write maximum color value (line 4) - for every row (0 .. height-1) - for every column (0 .. width-1) - write red, green, and blue values for pixel[row][column]
Submit these: (by MIDNIGHT Tuesday, September 21, 2004) ------------- pixel.h // your pixel class complex.cpp // implementation file for your complex class prog2_2.cpp // main program NOTES: 1 - Place all files for this assignment in your .../dropbox/<your_afsid>/prog2. DO NOT create additional folders. 2 - STANDARD copies of all other files will be used. Any of the other files you place in your dropbox WILL BE IGNORED.