P R E L I M I N A R Y   S P E C I F I C A T I O N

					     Due 2:00 am, Friday, 27 March 2009

CPSC 223b  Homework #4    QuickSorting Deques

(40) Write a sort program

	Quick09 [filename]*

that reads lines from the files specified, sorts them using quickSort, and
writes the sorted lines to the standard output.  The order is that defined by
strcmp().  When more than one file is specified, all of the lines in all of the
files are sorted into one output stream.  If a specified file does not exist,
Quick09 writes an error message to the standard error and calls exit().

To make the assignment more challenging, you may not use any arrays other than
argv[] and the strings returned by the function getLine() described in Note 2.
Instead, you may use up to three deques(*) of string pointers; i.e., no more
than three deques may exist at any point during the execution of Quick09.  The
penalty for using four (respectively, five or more) deques at the same time is
only 2 (respectively, 5) points.

  (*) A deque (or double-ended queue) is a data structure that combines the
  attributes of a queue and a stack: items can be added at the tail but can
  be removed from either the head or the tail.

These deques should be implemented (in a separate file) as the abstract data
type Deque defined in the header file Hwk4/Deque.h.  The file Hwk4/example.c,
contains an example of how the functions declared in Deque.h are used to
create, destroy, add elements to, and remove elements from a Deque.  The file
Hwk4/protoDeque.c contains my implementation (except that I deleted all of the
important lines of code).  Copies of Deque.h and example.c are appended.

To verify that your implementations of Quick09.c and Deque.c satisfy the
interface requirements, the test script will have three phases:

1) Link your Quick09.o with your Deque.o and test whether the combination
   Quick09 satisfies the overall specification.

2) Link your Deque.o with the driver Hwk4/testDeque.o and test whether your
   implementation of the abstract data type Deque satisfies the interface
   specification.

3) Link your Quick09.o with Hwk4/Deque.o (another implementation of the Deque
   ADT) and test whether the combination Quick09H (H for hybrid) satisfies the
   overall specification.

   WARNING:  Hwk4/Deque.o will always implement the Deque ADT, but the
   particular implementation may change without notice.

Hwk4/Makefile will create Quick09, testDeque, and Quick09H and can be used
as (the basis for) your makefile.

Use the submit command to turn in the source files for Quick09, the Deque ADT,
a Makefile, and your log file (see Homework #1).

YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION
WHERE YOU SPEND AT LEAST ONE HOUR WRITING OR DEBUGGING CODE, AND AT LEAST ONCE
EVERY FIVE HOURS DURING LONGER SESSIONS.  (ALL SUBMISSIONS ARE RETAINED.)


Notes:

1. To ensure that your program can handle input lines of arbitrary length,
   you should use the function getLine(), which is defined in Hwk4/getLine.h
   and is implemented in Hwk4/getLine.c.  YOUR SOURCE FILE(S) SHOULD #INCLUDE
   Hwk4/getLine.h AND YOUR MAKEFILE SHOULD SPECIFY Hwk4/getLine.o RATHER THAN
   THE NAMES OF LOCAL COPIES.  Warning: This version of getLine() strips the
   trailing newline (if any), unlike that used in Homework #3.

2. The Deque data type should be implemented using a doubly-linked, circular
   list.  Since the Deque data type is void*, it can be cast to a value of the
   appropriate type and then cast back again without losing information.

3. The values stored in a Deque are the string pointers returned by getLine().
   That is, the strings themselves should not be duplicated within the Deque
   and must be freed before the Deque is destroyed (or that storage will be
   lost forever).

4. Your implementation of quickSort may use any pivot, but must run in
   O(n*log(n)) time under the usual randomness assumptions.  Thus you may NOT
   use the Deque just to simulate a random-access array (e.g., to read the i-th
   element, transfer i-1 elements from the head of the Deque to the tail;
   transfer 1 element from head to tail, making a copy to return to quickSort;
   and then transfer n-i elements from head to tail, restoring the status quo).
    
5. The prohibition against arrays means that you may not use malloc(),
   realloc(), or free() outside the module that implements the Deque ADT
   (except to free storage returned by getLine()).

6. Your program may NOT contain any global variables.
								 CS-223-02/23/09

// Deque.h                                     Stan Eisenstat (2009/02/23)
//
// Define the abstract data type for a Deque of string pointers.  The
// strings themselves are NOT stored.

// Define true and false

#include <stdbool.h>


// A Deque is a pointer to some object that is used to implement the deque
// operations declared below.  By defining its data type as void *, that
// pointer can be stored within the calling program without knowing what the
// exact type of the object is.

typedef void *Deque;


// The following functions are the only means to access the Deque data
// structure.  They all require a pointer to a Deque variable since they may
// need to modify that variable in the course of accessing the data structure.
// Each returns the status of the operation, either true or false (e.g.,
// invalid arguments, an inconsistent Deque object, or a NULL return from
// malloc() / realloc()).

#include <stdbool.h>


// Set *D to a new object of type Deque.
// Returns true if successful, false otherwise.
int createD (Deque *d);


// Return true if the Deque *D is empty, false otherwise.  The value of *D
//   may change as a result.
int isEmptyD (Deque *d);


// Add the string pointer S to the tail of the Deque *D; the string itself
//   is not copied.  The value of *D may change as a result.
// Return true if successful,  false otherwise.
int addD (Deque *d, char *s);


// Remove the string pointer at the head of the Deque *D and store that
//   value in *S.  The value of *D may change as a result.
// Return true if successful, false otherwise (e.g., if *D is empty).
int headD (Deque *d, char **s);


// Remove the string pointer at the tail of the Deque *D and store that
//   value in *S.  The value of *D may change as a result.
// Return true if successful, false otherwise (e.g., if *D is empty).
int tailD (Deque *d, char **s);


// Destroy the Deque *D by freeing any storage that it uses (but not the
//   the blocks of storage to which the string pointers point) and set the
//   value of *D to NULL.
// Return true if successful, false otherwise.
int destroyD (Deque *d);
// example.c                                    Stan Eisenstat (2009/02/23)
//
// Demonstrate the use of the Deque ADT

#include <stdio.h>
#include <stdlib.h>
#include "/c/cs223/Hwk4/getLine.h"
#include "/c/cs223/Hwk4/Deque.h"

// Print message to stderr and exit.
#define die(msg)    exit (fprintf (stderr, "%s\n", msg))


int main (int argc, char *argv[])
{
    FILE *fp = stdin;           // Read from standard input
    Deque D;
    char *line;
    int parity;

    if (!createD (&D))                          // Create Deque for stdin
	die ("createD() failed");

    while ((line = getLine(fp))) {              // Append lines read to D
	if (!addD (&D, line))
	    die ("addD() failed");
    }

    for (parity = 1; !isEmptyD (&D);            // Output lines in from
		     parity = 1 - parity) {     //  head and tail of D
	if (parity == 1) {
	    if (!headD (&D, &line))
		die ("headD() failed");
	} else {
	    if (!tailD (&D, &line))
		die ("tailD() failed");
	}
	fputs (line, stdout);
	free (line);                            // Free storage
    }

    if (! destroyD (&D))                        // Destroy Deque
	die ("destroyD() failed");

    return EXIT_SUCCESS;
}