CS201: Data Structures and Algorithms

Assignment 1

Version 6

Printable Version

Introduction

For your second programming assignment, you are to implement a sorting algorithm only using a stack and two queues, and a set of allowed operations. Your program will check both real and decimal numbers as well as strings.

I/O

Your executable must be named sqsort. The executable reads in a series of only string, decimal, or real numbers, either from a file or from stdin, and will produce, on stdout, the list of numbers as they are processed Here is an example invocation:
    $ echo 2 4 5 3 1 > items
    $ sqsort -d items
    [2,4,5,3,1]
    [5,4,3,2,1]
    $
where $ is the system prompt. The file to be processed (items in the example) is a free-format text file. That is, the potential values within are separated by arbitrary amounts of whitespace (i.e. spaces, tabs, and newlines) and every line ends with a newline. If a file name is not given, input is to be read from the keyboard:
    $ sqsort -s
    "goodbye"                       "c is the best"
            "hello"

        "please compile"

                                    "0"
    ["goodbye","c is the best","hello","please compile","0"]
    ["goodbye","please compile","hello","c is the best","0"]
    ["please compile","hello","goodbye","c is the best","0"]
    $
Input is ended by entering a ^D character.

The executable must handle the following options:
option example action
-v sqsort -v give author's name and exit
[-d,-r,-s] sqsort -d FILENAME print the steps of each pass of the algorithm
found in FILENAME
sqsort [-d,-r,-s] print the steps of each pass of the algorithm
read in from stdin

Here are some example invocations using options:
    $ sqsort -v
    Jeffrey A. Robinson
    $ sqsort -r
    2.6 1.5 3.8 1.9
    [2.600000,1.500000,3.800000,1.900000]
    [2.600000,3.800000,1.900000,1.500000]
    [3.800000,2.600000,1.900000,1.500000]
    $

Reading the input

You must use the Art and Science of Programming - C Edition scanner for this task:
    wget troll.cs.ua.edu/ACP-C/scanner.c
    wget troll.cs.ua.edu/ACP-C/scanner.h
The scanner can read in integers, reals, or double-quoted strings from a file or from stdin. Note that a token is not a string. Using scanf, fscanf, gets, or other equivalent functions is forbidden and will be considered a test failure.

You should write three input functions for reading in files of the three types of values. You should then use a function pointer to point to the appropriate input function when processing the command line options.

Error checking

The only error checking you must perform is detecting the valid use of flags.
    $ sqsort -q  
    unknown flag 'q', valid flags are -d, -r, -s, and -v
    $
After printing the error message, you should exit the program. Other than this one exception, your program will only be tested with valid input.

Implementation details

You must follow the C programming style guide for this project: http://beastie.cs.ua.edu/cs201/cstyle.html.

Your implementation should have two queues, input and output, and a stack. During the execution of your program you move items from input and eventually place them on output in some, possibly different, order. During this process where you move elements from the input queue to the output queue, you can perform three operations:
If more than one operation is possible, transferring a value from the stack takes precedence over the other operation(s). Note that these descriptions assume a comparator that implements “less than”. A comparator that implements “greater than” would use the opposite comparisons.



If there are elements on the stack after the input queue is exhausted, these elements are moved to the output queue. Once all elements have been placed on output, swap the input and output queues (this must happen in constant time). If the elements are sorted you are done, otherwise you do another pass.

The first line you present reflects the original input and the final line should reflect the sorted values. Each intermediate line should contain the result of a pass. You must use the stack and queue classes from Assignment 0, keeping the same public interface. You must use the displayQueue function you implemented from assignment 0 to output each line. An output has a minimum of two lines.

For this assignment, you will use a comparator function to compare items and a display function to display them. In order to remove extraneous code you are required to use function pointers for the comparator and print. To make things easier you can use the following type definitions.
	typedef int (*Comparator)(void*,void*)
	typedef void (*Printer)(FILE*,void*)
these can be used in your program as such:
	Comparator comp;
	Printer print;

	switch(argv[1][1]) {
		...
		case 'd':	// decimal
			comp = intComparator;
			print = displayInteger;
			break;
		...
	}
where intComparator and displayInteger have been previously defined. You must also define the functions realComparator and stringComparator with similar semantics appropriate for the types they are comparing. Your string comparator function must be based on the strcmp function. All your comparator functions should be placed in a module named comparator.c. The function signatures of these functions and the above typedefs should be placed in comparator.h. It is important that only the comparator functions are placed in comparator.c.

Compilation details

You must implement your sorting algorithm in C99. You must provide a makefile which responds properly to the commands:
    make 
    make test
    make clean
The make command compiles your program, which should compile cleanly with no warnings or errors at the highest level of error checking (the -Wall and -Wextra options). The make test command should test your program and the make clean command should remove object files and the executable. Here are examples (your files may differ in number and name):
    $ make clean
    rm -f scanner.o integer.o real.o string.o queue.o sll.o stack.o dll.o comparator.o sqsort.o sqsort
    $ make
    gcc -Wall -std=c99 -c -g scanner.c
    gcc -Wall -std=c99 -c -g integer.c
    gcc -Wall -std=c99 -c -g real.c
    gcc -Wall -std=c99 -c -g string.c
    gcc -Wall -std=c99 -c -g queue.c
    gcc -Wall -std=c99 -c -g sll.c
    gcc -Wall -std=c99 -c -g stack.c
    gcc -Wall -std=c99 -c -g dll.c
    gcc -Wall -std=c99 -c -g comparator.c
    gcc -Wall -std=c99 -c -g sqsort.c
    gcc -Wall -std=c99 scanner.o integer.o real.o string.o queue.o dll.o stack.o dll.o comparator.o sqsort.o -o sqsort
    $ make
    make: `sqsort' is up to date.
    $ make test
    sqsort -d mytestfile
    [1, 2, 3, 4, 5, 6]
    [6, 5, 4, 3, 2, 1]
    $
The compilation command must name the executable sqsort (not sqsort.exe for you Cygwin users). The You may develop on any system you wish but your program will be compiled and tested on a Linux system. Only the most foolish students would not thoroughly test their implementations on a Linux system before submission. Note: depending on where you develop your code, uninitialized variables may have a tendency to start with a value of zero. Thus, a program with uninitialized variables may work on your system but fail when I run it.

The correctness and efficiency of your makefile will be tested. You must have the correct dependencies and your makefile should not perform any unnecessary compilations.

Documentation

All code you hand in must be attributed to its authors. Comment sparingly but well. Do explain the purpose of your program. Do not explain obvious code. If code is not obvious, consider rewriting the code rather than explaining what is going on through comments.

Grading

Grading will proceed in the same fashion as the previous assignment.

Submission

To submit assignments, you need to install the submit system.
You will hand in (electronically) your code for the preliminary assessment and for final testing with the command:
    submit cs201 lusth assign1
Make sure you are in the same directory as your makefile when submitting. The submit program will bundle up all the files in your current directory and ship them to me, so run a make clean command before submitting. It is very important that only the source code and any testing files be in your directory. Submitting .o files may cause you to fail some of the makefile tests. You should clean up your subdirectories as well, since all the files in your subdirectories will also be shipped to me. You may submit as many times as you want before the deadline; new submissions replace old submissions. Old submissions are stored and can be used for backup.