#define SPEW(alpha,beta) fprintf(stderr, "%s: %s\n", alpha, beta)

/*A node contains 3 parts: 
 *(a) a pointer to a previous node(prior) in the linked list
 *(b) a pointer to the next node(tail) in the linked list
 *(c) the string which exists as the contents of the node
 */ 
struct node{
  struct node *prior;
  struct node *tail;
  char *contents;
};


typedef struct node node;

/*File operations */

/* 
   initialize(char *, char *) takes a pointer to a string containing
   the filename to open and a pointer to a string containing a valid mode
   to open a file in.  It returns a FILE pointer to the file. NOTE: If 
   the filename given doesn't exist, the FILE pointer returned will point
   to NULL.
   
   Pre: The file exists.
   Pre: mode is ("r" || "w" || "a" || "r+" || "w+" || "a+")
   Post: The file has been opened.
*/
FILE *initialize(char *, char *);

/*
  readLine(FILE *, int) reads a single line from the place in 
  the file referenced by fp.  It will read *at maximum*
  MAXLINELENGTH characters from the line. If there are more
  characters, the next call to readLine will begin reading at 
  the MAXLINELENGTH character in the line until a '\n' or 
  MAXLINELENGTH characters have been read.Returns a pointer to a char
  array.
	 
  Pre: fp points to a valid file opened in "r" or "r+" mode.
  Post: The fp has been advanced to the next line or the EOF.
  Post: Memory has been allocated for the char array containing
  the line that was read in.
*/
char *readLine(FILE *, int);

/*
  writeLine(FILE *, char *) writes the characters in buf into
  the file referenced by fp at the place referenced by fp.
  Returns 1.

  Pre: The file was opened in any mode other than "r"
  Post: A char array has been written to the file
  Post: fp now points to a different place.
*/
int writeLine(FILE *, char *);

/*closes given file*/
int close(FILE *);

/* Node operations */

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: addNode will add a node after the node is passed.
 * Par: takes a buffer and a node which it will at a node after.  
 * Pre: a list which at the very least contains a startNode.
 * Pos: a node is added after the node passed and all the pointers
 *      are reassigned.
 * Pro: 
 */
node *addNode(node *, char *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: createNode builds a new node whose contents are copied from the buffer.
 * Par: a buffer which is a string is passed.
 * Pre: there must exist a startNode.
 * Pos: a new node is created with its contents defined.
 * Pro: there could be a stack overflow if the buffer becomes too big.
 */
node *createNode(char *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: deleteNode is passed a node which it will then remove from the list by
 *      reassigning the pointers.  It will then proceed to free both the  
 *      current node and the current node's contents.
 * Par: a node to be deleted.
 * Pre: there must exits a list which contains at least a startNode.
 * Pos: the tail and prior pointers are reassigned and the memory is freed.
 * Pro: if there is no list or if you try and delete an elment that is not in
 *      the list.
 */
node *deleteNode(node *, node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: findNode searches for a node whose contents match the buffer which is 
 *      passed to the funtion.  
 * Par: a buffer which is a pointer to a string.
 * Pre: there should exist a list that can be searched.
 * Pos: a node is found and then findNode returns that node.
 * Pro: 
 */
node *findNode(char *, node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: getLast finds the last element of the list for which the given 
 *      node is a part of.
 * Par: A node.
 * Pre: The node must exist.
 * Pos: The last node of the list is returned.
 * Pro: 
 */
node *getLast(node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: getFirst finds the first element of the list for which the given 
 *      node is a part of.
 * Par: A node.
 * Pre: The node must exist.
 * Pos: The first node of the list is returned.
 * Pro: 
 */
node *getFirst(node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: readListFromFile reads a given file creating a linked list wherein 
 *      each line of the file exists as a node. 
 * Par: the name of the file.
 * Pre: the file exists.
 * Pos: The first node of the new list is returned.  
 * Pro: 
 */
node *readListFromFile(char *);

/*
  writeListToFile(char *, node *) writes a list to the file. It
  first makes sure that it has the first node of the list
  and then progresses along the list until the end. The filename
  given will overwrite an existing file if allowed or will create
  a new file with the name pointed to by filename. Returns nothing.

  Pre: The file filename can be created or overwritten.
  Pre: listelement isn't null.
  Post: The file filename has been created or overwritten.
  
*/ 
void writeListToFile(char *, node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: exciseNode removes the given node from its list without deleting it, 
 *      then returns the node.
 * Par: A node.
 * Pre: The node must exist.
 * Pos: The nodes within the list no longer point to the specified node; the 
 *      node still exists, although it does not point to other nodes, and the 
 *      node is returned
 * Pro: Should not be used in place of delete, as the node remains in existence
 */
node *exciseNode(node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: Combines two lists
 * Par: two nodes, the first the start node of a list, the second a start node 
        of a list to be added to the first list.
 * Pre: the nodes passed exist
 * Pos: the list specified by the second parameter is now linked at the 
 *      end of the list specified by the first parameter; the starting node
 *      of this combined list is returned. 
 * Pro: 
 */
node *concat(node *, node *);

/*///////////////////////////////////////////////////////////////////////////*/
/* Pur: Prints to the screen the list, beginning with the given node and
 *      ending at the end of the list.
 * Par: A node.
 * Pre: The node exists.
 * Pos: The linked list is printed to the screen.
 * Pro: 
 */
void printLinkedList(node *);

/* sorting operations */

/*
  quicksort(node *) takes a list (represented by any node of the list)
  and sorts it lexicographically.  This function only moves pointers 
  around, it does not create a new list but rather returns the first
  node of the sorted list.
  
  Pre: You exist.
  Post: The node passed in and all of it's connected nodes connections
        may have been rearranged.
  Post: This collection of connected nodes are in lexicographical order.
*/
node  *quicksort(node *);