/* listfunc.h 
 * Header file for doubly-linked list function declarations
 * Authors: Amit Nangalia   
 * Last modified: 17th February, 2000
 */

#define DUMMY_TRAILER '\177' /* the constant stored in the dummy trailer node */
#define BUFSIZE 20    /* the size of the string stored in the nodes */
#define HEADER '\0'          /* the constant stored in the dummy header node */

/* Purpose: definition of the structure of the nodes in the doubly-linked-list.
 * Part of the declaration is taken from 
 *  - "Advanced C Programming - by example", Perry, John W. - Chapter 3, p.56
 */

typedef struct node {
  char str[BUFSIZE];
  struct node *forward, *backward;
} NODE;

/* Purpose: creates the doubly linked list by creating two dummy nodes:
 *  one at the front and one at the back.  This eliminates the need to 
 *  test for special cases for inserting an deleting at the ends of the list.
 * Pre-conditions: The structure of the nodes must have been defined.
 * Post-conditions: memory has been allocated for the two dummy headers.
 * Produces: a pointer to the beginning of the doubly-linked-list.
 * Part of the function declaration is taken from 
 *  - "Advanced C Programming - by example", Perry, John W. - Chapter 3, p.56
 */
NODE *create(void);


/* Purpose: deletes a node from the doubly linked list:
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created.
 *                 The node to delete should be identified by the string it stores.
 * Post-conditions: Memory has been freed for the deleted node.
 * Parameters: Pointer to the head of the doubly-linked-list.
 *             The string to be deleted in the list.
 * Produces: Nothing new, but deletes the node containing the string provided.
 *           If no string of that type is matched, then the procedure does nothing. 
 * Part of the function declaration is taken from 
 *  - "Advanced C Programming - by example", Perry, John W. - Chapter 3, p.64
 */
void delete(NODE *list, char *str);


/* Purpose: Inserts a node into the doubly linked list:
 *          The new node is inserted before the dummy trailer node (at the end of list).
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created .
 *                 Data for the new node should be provided .
 * Post-conditions: Memory has been allocated for the new node.
 * Parameters: pointer to the head of the doubly-linked-list.
 *             the string to be stored in the node.
 * Produces: Nothing new, but extends the doubly-linked-list to include 
 *           new node.
 * Part of the function declaration is taken from 
 *  - "Advanced C Programming - by example", Perry, John W. - Chapter 3, p.64
 */
void insert(NODE *list, char *str);


/* Purpose: Prints the strings in the doubly linked list to a file:
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created.
 *                 The file to write to must be opened for writing.
 * Post-conditions: The output file contains the strings in the order of the list.
 * Parameters: Pointer to the head of the doubly-linked-list.
 *             Pointer to the file to write to.
 * Produces: A file with each string of each node printed on one line. 
 */
void toFile(NODE *list, FILE *fp);


/* Purpose: Prints the doubly linked list in order:
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created.
 * Parameters: Pointer to the head of the doubly-linked-list. 
 * Part of the function declaration is taken from 
 *  - "Advanced C Programming - by example", Perry, John W. - Chapter 3, p.60
 */
void traverse(NODE *list);


/* Purpose: Counts the number of nodes in a list excluding the dummy nodes.
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created.
 * Parameters: pointer to the head of the doubly-linked-list.
 * Problems: The file to which this function writes to, cannot be read by
 *           the function insert if called immediately.
 * Produces: returns the number of nodes containing strings read from a file or 
 * inserted (exlcuding the dummy nodes).
 */
int num_elements(NODE *list);


/* Purpose: Concatenates three lists in alphabetical order (smaller, equal, larger).
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The three lists must have been created.
 * Post-conditions: Create a new list which is in alphabetical order
 *                  in the contains the strings in the order of the list.
 * Parameters: Pointers to the head of the three doubly-linked-lists.
 * Produces: A pointer pointing to the head of the newly created list. 
 */
NODE *join(NODE *smaller, NODE *equal, NODE *larger);


/* Purpose: Recursively sorts a list in alphabetical order by spliting the linked list
 *          into three smaller lists using a pivot point - smaller, equal and larger 
 *          elements lists.
 * Pre-conditions: The structure of the nodes must have been defined; 
 *                 The list must have been created.
 * Post-conditions: Create a smaller sized list to sort recursively and then eventually
 *                  a new list which is either in alphabetical order.
 * Parameters: Pointers to the head of the doubly-linked-list to sort.
 * Produces: A pointer pointing to the head of either the smaller, larger or the
 *           entire sorted list. 
 */
NODE *sort(NODE *list);