CS14 - At-Home Programming Assignment 2

Test files used

You may download the following test files to determine how well your project did. These are the test files used to grade your assignments.

printjobs1.txt - Sample Output printjobs1.out
printjobs2.txt - Sample Output printjobs2.out
printjobs3.txt - Sample Output printjobs3.out
printjobs4.txt - Sample Output printjobs4.out
printjobs5.txt - Sample Output printjobs5.out
printjobs6.txt - Sample Output printjobs6.out
printjobs7.txt - Sample Output printjobs7.out
printjobs8.txt - Sample Output printjobs8.out
printjobs9.txt - Sample Output printjobs9.out
printjobs10.txt - Sample Output printjobs10.out
printjobs11.txt - Sample Output printjobs11.out
printjobs12.txt - Sample Output printjobs12.out
printjobs13.txt - Sample Output printjobs13.out
printjob14.txt - Sample Output printjobs14.out

Write a program that takes care of a printer queue. Your program will simulate and evaluate the printing. The arrival pattern of print jobs will be represented in a file as the arrival times (in printing time intervals (you can think fo these as some number of seconds or a minute)) of each print job and its number of pages. The file will be specified in a command line parameter to your program. Your program will take no input other than the test file name as the command line parameter. You will simply open the file, process the print jobs, print out the results, and exit. It takes one time interval to print each page. You should process the jobs in the file and then print out the total number of jobs processed, the total number of pages printed, and the average waiting time per job. Waiting time is the number of intervals from arrival time to beginning of printing. The job at the head of the queue is currently being printed and is not dequeued until printing completion. Use a linked list to implement your queue. There are many List templates available (for example, the Standard Template Library offers a list template). However, for this assignment, when you use a linked list, it will be your own code so that you can practice your programming and learn the concepts thoroughly.

NOTE - Be aware of the precision of the average waiting time per job. You must print the average waiting time with a precision of 4 significant digits. HINT - use iomanip

A sample file is shown below (a 0 specifies the end of the processing):

1 4
3 3
8 1
8 2
12 10
19 1
20 2
26 5
26 1
0

You can download the sample file here.

An explanation of the processing of the above file is shown below:

arrival time	pages	intervals used for printing	number of waiting intervals
1	4	1 2 3 4	no wait
3	3	5 6 7	2
8	1	8	no wait
8	2	9 10	1
12	10	12 13 14 15 16 17 18 19 20 21	no wait
19	1	22	3
20	2	23 24	3
26	5	26 27 28 29 30	no wait
26	1	31	5

# of jobs	# of pages		average waiting time per job
9	29		1.556

Your output MUST match mine EXACTLY. This is my output. You need to determine if yours is exactly like mine by using the diff command. Do a man on diff for more information (type "man diff" at the command prompt). Basically, you need to run the following command in Linux: "diff --ignore-all-space --ignore-blank-lines youroutput.out myoutput.out" and if the files are the same, nothing will be printed to the screen (That is your goal). To capture your output to a file, you can use the output redirection available in the Linux shell. You can redirect your output using > . To capture your output for this project, your command would look similar to this: "printqueue inputfile.txt > youroutput.out" where printqueue might be the name of your executable, inputfile.txt might be the name of the input file you are using, and youroutput.out is what normally would have been printed to the screen.

Format of input file

Don't make any assumptions on the correctness of the input file. I gave you a sample of what the input file would look like, and if the input file is in the correct format, that is exactly what it will look like. However, you should never make any assumptions about the correctness of the input file. I will make other test files with invalid input cases and I will expect that you code will never crash. If, while reading in the file, you find something that does not match the expected input format, print out an error message and exit the program. Examples

do not expect that the jobs will be sorted in ascending ordering (if you find a job out of order, that is an error)
do not make any assumptions on the maximum number of pages or arrival time (valid numbers will be in the range of an unsigned int, however, if I enter a value outside the range of an unsigned int, that is an error)
do not expect that only integers will in be the file
The final 0 may not exist
in general, the input file can be ANYTHING that I can think of and your code should not crash. It is up to you to write a robust input routine that can handle any situation. It will be our goal to crash your input routine and that is exactly the attitute you should expect from any user of any program you ever write.

Format of output

To make sure that your output file matches mine exactly, I will list the special things you must know:

There is a single tab (\t) after "Time" on the first line
There are two tabs (\t\t) after "Status" on the first line
There are 58 underscores on the second line - HINT: use iomanip but check carefully because setting a width of 58 may not work correclty
There is a single tab after the time interval on each line
There are two tabs on each line after the printer status (printing or idle)
Everywhere else there is a space it is one single space

However, we will be ignoring blank lines and white space so it is really not that important to get it looking EXACTLY the same with respect to white space. It should just look similar.

Object Oriented Programming for the print queue

There is a lot of freedom in the design of this assignment and since writing the actual queue code is simple (I give a lot of it in class), a large portion of the points will be dedicated to your OOP skills. There are three main points to consider while designing your program:

Modular design - What modules should you create and what should each module be responsible for? When you are done with this assignment, you should be able to directly take out your queue class and your node class and use it to implement a queue for some other data structure by simply changing the pointer to the data in the node class. A queue class should know nothing about WHAT it is actually queuing, nor should a queue class contain data specific statistics.
Processing of the input file - Your input file processing should be efficient in both running time and space utilization. Your program should use O(n) for space requirements (n=number of jobs) and should process the file in O(n) time (n=number of jobs) - i.e one pass through the file. So, to stick with the space and time requirements, the easiest way to implement the program is to read the entire file in at one time, enqueue all the jobs into the queue, and then have loop to simulate the print queue. However, if you do this, then you really aren't implementing a queue. You are just doing a list. You should process the jobs one at a time with a driver loop that counts time intervals and at no time should a job be in the queue that has not arrived yet.
Main driver for the program - You will need to decide how to simulate the print queue. While designing your main driver, keep in mind that your program should actually do a simulation of a print queue. Your main loop should loop based on time and at each time interval, should simulate the actions of the print queue - jobs arrive, a job gets printed if there is a job to print, then print the information about that interval. You should shoot for your program to run in O(mn) time where n = number of jobs and m = total number of time intervals.

Notes on grading

Much of the grading of your program will be based on not just getting code to do the necessary functions correctly, but on your actual coding. Be sure to use good programming where possible (use of classes, functions, good parameter passing techniques, error checking, encapsulation, object oriented programming). Make sure your program is user friendly.

If your output does not look exactly like mine (doing a diff on my output against yours should print nothing), be prepared to lose significant points.

You must use a makefile to compile your program and you must at least use the compilation flags -W -Wall -Werror -pedantic. Programs will be graded under linux on hill.cs.ucr.edu. Significant points will be taken off if your program does not compile with a makefile or if you code under Windows.

Suggestions to follow while coding

Follow a modular programming style. Write one function for your program and completely test it before moving to the next function. This will isolate your debugging because most of the time the bug will be in the newly created module. However, if you forget a test case in an old module and do not completely test it, a new module can reveal old bugs. Watch out for this.

What to turn in

You should have turned in what you have thus far on our program at least 6 hours before the due date (by 2pm). Then continue to work on your program and turn in more current versions as you get them working. Ideally, you should have your project done well before the due date.

You must turn in all .cc and .h files and your makefile. In addition, you must follow any guidelines and include any information that is stated on the main page about at-home programming assignments.

DO NOT, I repeat, DO NOT turn in any files that are not required for the final compilation of your assignment. Do not turn in your temporary .cc files or your saved/olded revisions of your .cc files. If you turn in files that aren't required for your assignment, it hinders the grading processes. You will be docked points if you turn in extraineous files.

A reminder about collaboration on home programming assignments

Please remember, at-home programming assignments are not lab assignments and you may not team-code with your lab partner or any other individual. Limited collaboration may be acceptable, but programs must represent YOUR OWN original work. Sharing code or team-coding are strictly not allowed. Copying code from ANY source (any book, current or past students, past solutions, web, etc) is strictly not allowed even with citation. Collaboration may consist of discussing the general approach to solving the problem, but should not involve communicating in code or even pseudo-code. Students may help others find bugs. Your code MUST be unique -- the odds of randomly producing similar code is very low. Computing, like surgery or driving a car or playing golf, can only be learned by doing it yourself!