/**
 * node.h 
 *   Nodes in linked lists.
 */

#ifndef __NODE_H__
#define __NODE_H__

// +-------+----------------------------------------------------------
// | Types |
// +-------+

struct node 
  {
    char *data;
    struct node *next;
  };


// +-------------------+----------------------------------------------
// | Primary Functions |
// +-------------------+

/**
 * Procedure:
 *   is_null
 * Parameters:
 *   lst, a pointer to a node.
 * Purpose:
 *   Determine if val is null.
 * Produces:
 *   empty, an integer.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   empty = (val == NULL)
 */
int is_null (struct node *lst);

/**
 * Procedure:
 *   cons
 * Parameters:
 *   str, a string
 *   lst, a pointer to a node
 * Purpose:
 *   Add str to the front of the list.
 * Produces:
 *   newlst, a list
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   car (newlst) = str
 *   cdr (newlst) = lst
 * Problems:
 *   If no space is available, returns NULL.  We hope that this situation
 *   never happens.
 */
struct node *cons (char *str, struct node *lst);

/**
 * Procedure:
 *   car
 * Parameters:
 *   lst, a non-null pointer to a node.
 * Purpose:
 *   Get the first element of lst.
 * Produces:
 *   first, a string.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   car (cons (x, y)) = x
 */
char *car (struct node *lst);

/**
 * Procedure:
 *   cdr
 * Parameters:
 *   lst, a non-null pointer to a node.
 * Purpose:
 *   Get all but the first element of lst.
 * Produces:
 *   rest, a pointer to a node.
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   cdr (cons (x, y)) = y
 */
struct node *cdr (struct node *lst);

/**
 * Procedure:
 *   set_car
 * Parameters:
 *   lst, a non-null pointer to a node.
 *   str, a string
 * Purpose:
 *   Change the first element of lst.
 * Produces:
 *   lst, the modified list
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   car (set_car (lst, x)) = x
 *   cdr (set_car (lst, x)) = cdr (lst)
 */
struct node *set_car (struct node *lst, char *str);

/**
 * Procedure:
 *   set_cdr
 * Parameters:
 *   lst, a non-null pointer to a node.
 *   rest, a non-null pointer to a node.
 * Purpose:
 *   Change the remainder of lst.
 * Produces:
 *   lst, the modified list
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   car (set_cdr (lst, x)) = car (lst)
 *   cdr (set_cdr (lst, x)) = x
 */
struct node *set_cdr (struct node *lst, struct node*rest);


// +----------------------+-------------------------------------------
// | Additional Functions |
// +----------------------+

/**
 * Procedure:
 *   np_last
 * Parameters:
 *   lst, a pointer to a non-NULL node
 * Purpose:
 *   Find the last element in lst
 * Produces:
 *   last, a string
 * Preconditions:
 *   [No additional.]
 * Postconditions:
 *   last is the last element in lst.
 */
char *np_last (struct node *lst);

/**
 * Procedure:
 *   np_length
 * Parameters:
 *   lst, a pointer to a node
 * Purpose:
 *   Find the length of the list given by lst.
 * Produces:
 *   length, an integer
 * Preconditions:
 *   [No additional]
 * Postconditions:
 *   length is the number of nodes in lst.
 */
int np_length (struct node *lst);

/**
 * Procedure:
 *   np_print
 * Parameters:
 *   lst, a pointer to a node
 *   fp, a file pointer
 * Purpose:
 *   Prints lst (in Scheme 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 np_print (struct node *lst, FILE *fp);

/** 
 * Procedure:
 *   np_append
 * Parameters:
 *   lst, a pointer to a node
 *   str, a string
 * Purpose:
 *   Adds str to the end of lst
 * Produces:
 *   newlst, the extended list.
 * Preconditions:
 *   [No additional.]
 * Postconditions:
 *   If lst != NULL, then np_last (lst) is str.
 *   np_last (newlst) = NULL
 */
struct node *np_append (struct node *lst, char *str);

/**
 * Procedure:
 *   np_delete
 * Parameters:
 *   lst, a pointer to a node
 *   str, a string
 * Purpose:
 *   Delete the first element in lstwhose car is str.
 * Produces:
 *   newlst, an updated list.
 */
struct node *np_delete (struct node *lst, char *str);

#endif // __NODE_H__

