/**
 * dll.h 
 *   Doubly-linked lists.
 */

#ifndef __DLL_H__
#define __DLL_H__


// +---------+--------------------------------------------------------
// | Headers |
// +---------+

#include <stdio.h>	// For FILE


// +------------------+-----------------------------------------------
// | Shared Variables |
// +------------------+

/**
 * The error message generated by various operations.
 */
extern char *dll_error;


// +----------------------------+-------------------------------------
// | Constructors & Destructors |
// +----------------------------+

/**
 * Procedure:
 *   dll_new
 * Parameters:
 *   [None]
 * Purpose:
 *   Create a new, empty list.
 * Produces:
 *   lst, a list
 * Problems:
 *   If no memory is available, returns NULL.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   The list is empty and has a cursor at an undefined location.
 */
struct dll *dll_new ();

/**
 * Procedure:
 *   dll_free
 * Parameters:
 *   lst, a list
 * Purpose:
 *   Free all the memory associated with list (except for that associated
 *   with the strings).
 * Produces:
 *   [Nothing; Called for the side effect]
 * Preconditions:
 *   lst has not already been freed.
 * Postconditions:
 *   Memory has been freed.
 *   lst is no longer usable.
 */
void dll_free (struct dll *lst);

/**
 * Procedure:
 *   dll_clear
 * Parameters:
 *   lst, a list
 * Purpose:
 *   Remove all of the elements of lst.
 * Produces:
 *   [Nothing; Called for the side effect]
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   dll_length (lst) is 0
 */
void dll_clear (struct dll *lst);


// +-----------+------------------------------------------------------
// | Observers |
// +-----------+

/**
 * Procedure:
 *   dll_get
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Get the current element of lst (the one under the cursor).
 * Produces:
 *   str, a string
 * Preconditions:
 *   lst is nonempty
 * Postconditions:
 *   lst is not modified.
 *   str is the element naturally viewed as being at the cursor.
 */
char *dll_get (struct dll *lst);

/**
 * Procedure:
 *   dll_is_empty
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Determine if the list is empty
 * Produces:
 *   is_empty, an integer, representing a Boolean.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   If there are elements in the list, is_empty is false (0).  Otherwise,
 *     is_empty is true (1).
 */
int dll_is_empty (struct dll *lst);

/**
 * Procedure:
 *   dll_at_head
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Determine if the cursor for the list is at the head.
 * Produces:
 *   at_head, an integer representing a Boolean.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   If the cursor is at the head, at_head is 1.  Otherwise, at_head is 0.
 * Philosophy:
 *   Useful for checking the precondition to retreat.
 */
int dll_at_head (struct dll *lst);

/**
 * Procedure:
 *   dll_at_tail
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Determine if the cursor for the list is at the tail.
 * Produces:
 *   at_tail, an integer representing a Boolean.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   If the cursor is at the tail, at_tail is 1.  Otherwise, at_tail is 0.
 * Philosophy:
 *   Useful for checking the precondition to advance.
 */
int dll_at_tail (struct dll *lst);

/**
 * Procedure:
 *   dll_print
 * Parameters:
 *   lst, a doubly-linked list
 *   fp, a file pointer
 * Purpose:
 *   Prints lst (in modified C array form) to fp.
 * Produces:
 *   [Nothing; Called for the side effect.]
 * Preconditions:
 *   fp must be open for writing.
 * Postconditions:
 *   fp now contains a representation of lst.
 *   lst is unchanged.
 */
void dll_print (struct dll *lst, FILE *fp);


// +---------------+--------------------------------------------------
// | List Mutators |
// +---------------+

/**
 * Procedure:
 *   dll_insert_before
 * Parameters:
 *   lst, a doubly-linked list
 *   str, a string
 * Purpose:
 *   Insert str immediately before the cursor.
 * Produces:
 *   ok, an integer that represents whether or not the operation
 * Preconditions:
 *   lst is nonempty.
 *   lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k s_(k+1) ... s_(n-1))
 *   The cursor is at s_k.
 * Postconditions:
 *   If the insertion succeeded, ok is nonzero and
 *     dll has the form (s_0 s_1 s_2 ... s_(k-1) str s_k s_(k+1) ... s_(n-1))
 *     The cursor is at s_k.
 *   If the insertion failed, ok is 0 and
 *     lst is unmodified
 *     dll_error contains a message about the reason for failure.
 */
int dll_insert_before (struct dll *lst, char *str);

/**
 * Procedure:
 *   dll_insert_after
 * Parameters:
 *   lst, a doubly-linked list
 *   str, a string
 * Purpose:
 *   Insert str immediately after the cursor.
 * Produces:
 *   ok, an integer that represents whether or not the operation
 * Preconditions:
 *   lst is nonempty.
 *   lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k s_(k+1) ... s_(n-1))
 *   The cursor is at s_k.
 * Postconditions:
 *   If the insertion succeeded, ok is nonzero and
 *     lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k str s_(k+1) ... s_(n-1))
 *     The cursor is at s_k.
 *   If the insertion failed, ok is 0 and
 *     lst is unmodified
 *     dll_error contains a message about the reason for failure.
 */
int dll_insert_after (struct dll *lst, char *str);

/** 
 * Procedure:
 *   dll_append
 * Parameters:
 *   lst, a doubly-linked list
 *   str, a string
 * Purpose:
 *   Adds str to the end of lst
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   lst has the form (s_0 ... s_(n-1))
 * Postconditions:
 *   If the append succeeded, ok is nonzero and
 *     lst has the form (s_0 ... s_(n-1) str)
 *   If problems occurred, ok is 0 and
 *     The list is unmodified
 *   In either case,
 *     The cursor is unchanged
 */
int dll_append (struct dll *lst, char *str);

/** 
 * Procedure:
 *   dll_prepend
 * Parameters:
 *   lst, a doubly-linked list
 *   str, a string
 * Purpose:
 *   Adds str to the front of lst
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   lst has the form (s_0 ... s_(n-1))
 * Postconditions:
 *   If the prepend succeeded, ok is nonzero and
 *     lst has the form (str s_0 ... s_(n-1))
 *   If problems occurred, ok is 0 and
 *     The list is unmodified
 *   In either case,
 *     The cursor is unchanged
 */
int dll_prepend (struct dll *lst, char *str);

/**
 * Procedure:
 *   dll_delete
 * Parameters:
 *   lst, a doubly-linked list 
 * Purpose:
 *   Delete the current element of the list.
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   The list is nonempty.
 *   lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k s_(k+1) ... s_(n-1))
 *   The cursor is at s_k.
 * Postconditions:
 *   If the deletion succeeded, ok is nonzero and
 *     lst has the form (s_0 s_1 s_2 ... s_(k-1) s_(k+1) ... s_(n-1))
 *     The cursor is at s_(k+1)
 *   If problems occurred, ok is 0 and
 *     The list is unmodified
 *     The cursor remains at s_k
 */
int dll_delete (struct dll *lst);


// +-----------------+------------------------------------------------
// | Cursor Mutators |
// +-----------------+

/**
 * Procedure:
 *   dll_to_head
 * Parameters:
 *   dll, a doubly-linked list.
 * Purpose:
 *   Move the cursor to the head of the list.
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   The list is non-empty.
 * Postconditions:
 *   The elements of the list are unmodified.
 *   If the move succeeded, ok is 1 and
 *     dll_at_head (dll) is true.
 *   If the move did not succeed, ok is 0 and
 *     The cursor is unmodified.
 * Ponderings:
 *   I don't know of a reason this could fail, but the return value is
 *   included to be on the safe side.
 */
int dll_to_head (struct dll *lst);

/**
 * Procedure:
 *   dll_to_tail
 * Parameters:
 *   dll, a doubly-linked list.
 * Purpose:
 *   Move the cursor to the tail of the list.
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   The list is non-empty.
 * Postconditions:
 *   The elements of the list are unmodified.
 *   If the move succeeded, ok is 1 and
 *     dll_at_tail (dll) is true.
 *   If the move did not succeed, ok is 0 and
 *     The cursor is unmodified.
 * Ponderings:
 *   I don't know of a reason this could fail, but the return value is
 *   included to be on the safe side.
 */
int dll_to_tail (struct dll *lst);

/**
 * Procedure:
 *   dll_advance
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Advance the cursor to the next element.
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   The list is nonempty.
 *   lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k s_(k+1) ... s_(n-1))
 *   The cursor is at s_k.
 *   ! dll_at_tail (dll)
 * Postconditions:
 *   The list is unmodified.
 *   If the advance succeeded, ok is 1 and
 *     The cursor is at s_(k+1)
 *   If the advance failed, ok is 0 and
 *     The cursor remains at s_k.
 */
int dll_advance (struct dll *lst);

/**
 * Procedure:
 *   dll_retreat
 * Parameters:
 *   lst, a doubly-linked list
 * Purpose:
 *   Retreat the cursor to the previous element.
 * Produces:
 *   ok, an integer
 * Preconditions:
 *   The list is nonempty.
 *   lst has the form (s_0 s_1 s_2 ... s_(k-1) s_k s_(k+1) ... s_(n-1))
 *   The cursor is at s_k.
 *   ! dll_at_head (dll)
 * Postconditions:
 *   The list is unmodified.
 *   If the advance succeeded, ok is 1 and
 *     The cursor is at s_(k+1)
 *   If the advance failed, ok is 0 and
 *     The cursor remains at s_k.
 */
int dll_retreat (struct dll *lst);


// +---------------+--------------------------------------------------
// | Miscellaneous |
// +---------------+

/**
 * Procedure:
 *   dll_check
 * Parameters:
 *   dll, a doubly-linked list
 *   strings, an array
 *   size, an integer
 * Purpose:
 *   Determine if the strings in dll exactly match the strings in strings.
 * Produces:
 *   match, an integer that represents a Boolean
 * Preconditions:
 *   size is the size of strings.
 * Postconditions:
 *   If (a) dll has exactly size elements and (b) for all i, 0 <= i < size,
 *     the ith element of dll is equal to the ith element of strings, then
 *     match is 1.
 *   Otherwise, match is 0.
 *   That is, if dll has a different length, or if any two corresponding
 *     strings don't match, match is 0.
 * Philosophy:
 *   In unit testing, we may want to check the structure of the list.  
 *   This procedure helps us check that.
 */
int dll_check (struct dll *dll, char *strings[], int size);

#endif // __DLL_H__