/****
 *
 * Type List is a generic, weakly-typed list structure.  An object of type List*
 * points to zero or more list elements of type ListElem*.  A ListElem has the
 * following concrete structure:
 *
 *              |-------------------------------|
 *              |           void* data          |
 *              |-------------------------------|
 *              |         ListElem* next        |
 *              |-------------------------------|
 *              |         ListElem* prev        |
 *              |-------------------------------|
 *
 * Nested lists can be constructed using some form of struct for the void*
 * data.  For example,
 *
 *     typedef struct {
 *         void* data;	   // Generic atomic data, null if this is a sublist
 *         List* subList;  // Sublist pointer, null if this is an atomic elem
 *     } NestedListData;
 *
 * Strongly-typed list specializations can be defined by using a specific type
 * for the data field, and supplying appropriately typed access functions.
 * Otherwise, the void* data pointer needs to be manually cast, as values are
 * retrieved from the list.
 *
 * The top-level concrete structure of a list looks like this:
 *
 *              |-------------------------------|
 *              |         ListElem* first       |
 *              |-------------------------------|
 *              |         ListElem* last        |
 *              |-------------------------------|
 *              |            int size           |
 *              |-------------------------------|
 *              |         int ref_count         |
 *              |-------------------------------|
 *              |      ListElem* enum_elem      |
 *              |-------------------------------|
 *
 *
 * where size is the number of elements in the list, ref_count is for storage
 * management, and enum_elem points to the next element in the list to be
 * returned from the list enumerator function.
 *
 */
#ifndef listIncluded
#define listIncluded
#include "std-macros.h"

typedef void ListElemData;

typedef struct ListElemStruct {
    ListElemData* data;
    struct ListElemStruct *next;
    struct ListElemStruct *prev;
} ListElem;

typedef struct ListStruct {
    ListElem* first;
    ListElem* last;
    int size;
    int ref_count;
    ListElem* enum_elem;
} List;


/*
 * Construct a new empty list.  Initialize first, last, and enum_elem to null.
 * Initialize size and ref_count to 0.
 */
List* NewList();

/*
 * Construct a new 1-element list, with the given element.  Initialize first,
 * last, and enum_elem to the new element.  Initialize size to 1 and ref_count
 * to 0.
 */
List* NewList1(ListElemData* e);

/*
 * Return true of the given lists are elementwise equal, and have the same
 * number of elements.  If either or both of the given lists is null, or have
 * any different elements, return false.
 *
 * This is a shallow test for equality, in that the void* data pointer of each
 * element pair is compared using C ==.  To perform a deep equality comparison,
 * use the function ListEqualsWithFunction, which takes a pointer to a function
 * that performs a deep eqality comparison of the data for each element pair.
 */
bool ListEquals(List* l1, List* l2);

/*
 * Like ListEquals, but calls equals_func on each list element pair.  The
 * equals_func is called with the void* data pointers from each pair.  It is
 * the responsibility of the equals_func implementor to perform the appropriate
 * equality test. This includes, if necessary, recursive descent into nested
 * list structures.
 */
bool ListEqualsWithFunction(List* l1, List* l2,
	bool (*equals_func)(ListElemData*, ListElemData*));

/*
 * Copy the given list into a new list, and return the new list.  If the given
 * list is null, no action is performed.
 *
 * This is a shallow copy, in that the void* data pointer of each element is
 * copied via C assignment to its corresponding new element in the copy,
 * without descending into the element data.  To perform a deep copy, use the
 * function CopyListWithFunction, which takes a pointer to a function that
 * performs a deep copy for each element.
 */
List* CopyList(List* l);

/*
 * Like CopyList, but calls copy_func on each element's data, and assigns that
 * copy to the copied element's void* data field.  The copy_func is called with
 * the void* data pointer from each list element.  It is the responsibility of
 * the copy_func implementor to perform the appropriate deep copy actions. This
 * includes, if necessary, recursive descent into nested list structures.
 */ 
List* CopyListWithFunction(List* l, void* (*copy_func)(ListElemData*));

/*
 * Delete the given list, and all of its elements.  If the given list is null,
 * no action is performed.
 *
 * This is a shallow delete, that calls free on the void* data pointer for each
 * element, without descending into the data.  To perform a deep delete, use
 * the function DelListWithFunction, which takes a pointer to a function that
 * performs the delete operation on the data for each element.
 */
void DelList(List* l);

/*
 * Like DelList, but calls del_func on each element's data, instead of free.
 * The del_func is called with the void* data pointer from each list element.
 */ 
void DelListWithFunction(List* l, void (*del_func)(ListElemData*));

/*
 * Like DelList, but do not delete the void* data in the elements.  I.e., free
 * only the ListElems themselves, without freeing the void* data to which the
 * elements point.  It is assumed that the caller has other references to all
 * of the storage referred to the deleted list elements.  If not, garbage will
 * be created.
 */
void DelListNodesOnly(List* l);

/*
 * Put the given element onto the end of the given list (fifo discipline).  If
 * the given list is non-null, it is mutated and returned.  If the list is
 * null, then no action is performed and null is returned.
 */
List* PutList(List* l, ListElemData* e);

/*
 * Remove and return the last element off the end of the given list, i.e., the
 * last element added by PutList.  If the given list is non-null, it is
 * mutated.  If the given list is null, then no action is performed and null is
 * returned.
 * 
 */
ListElemData* PullList(List* l);

/*
 * Push the given element onto the front of the given list (lifo discipline).
 * If the given list is non-null, it is mutated and returned.  If the list is
 * null, then no action is performed and null is returned.
 */
List* PushList(List* l, ListElemData* e);

/*
 * Remove and return the first element from the front of the given list, i.e.,
 * the last element added by PushList.  If the given list is non-null, it is
 * mutated and returned.  If the given list is null, then no action is
 * performed and null is returned.
 */
ListElemData* PopList(List* l);

/*
 * Return the nth element of the given list, without removing it.  Elements are
 * numbered starting at 1.  If the given list is null or empty, n<1 or
 * n>LenList(l), then null is returned.
 */
ListElemData* GetListNth(List* l, int n);

/*
 * Delete the nth element from the given list.  If the given list is non-null,
 * it is mutated.  If the given list is null or empty, or n is out of range,
 * then no action is performed and null is returned.
 */
ListElemData* DelListNth(List* l, int n);

/*
 * Return a sublist of the given list from the mth to nth elements.  No copying
 * is performed, so the given list will be mutated if the returned sublist is
 * subsequently mutated.  If the given list is null or empty, m is out of
 * range, n is out of range, or m > n, then no action is performed and null is
 * returned.
 */
List* SubList(List* l, int m, int n);

/*
 * Concatenate the two given lists, without mutating either.  The concatenated
 * result is returned, as a shallow copy of the two lists.  "Shallow" in this
 * context means that the void* data pointer of each element is copied via C
 * assignment to its corresponding copied element.  If either or both of the
 * given lists is null, then no action is performed and null is returned.
 * (Either or both lists may be empty, with the expected results, i.e.,
 * concatenating onto empty is empty.)
 *
 * The non-mutating behavior of ConcatLists is in contrast to the other list
 * mutating functions, i.e., Put, Pull, Push, Pop, and DelNth.  To maintain a
 * mutation-free regime of list usage, ConcatLists is used in place of the
 * mutating functions, per the following equivalences:
 * 
 *     Mutating Functions	Non-Mutating Equivalents
 *     ==================	=======================
 *
 *     PutList(l,e); f(l)	l = ConcatLists(l, NewList1(e)));
 *				f(l)
 *
 *     x=PullList(l); f(l)	x = GetListNth(l, ListLen(l));
 *				l = (SubList(l, 1, ListLen(l)-1));
 *				f(l)
 *
 *     PushList(l,e); f(l)	l = ConcatLists(NewList1(e), l);
 *				f(l)
 *
 *     PopList(l) ...; f(l)	GetListNth(l, 1) ...;
 *				f(SubList(l, 2, ListLen(l)))
 *
 *     x=DelListNth(l,n); f(l)	x = GetListNth(l, n);
 *				l = ConcatLists(SubList(l, 1, n-1),
 *					        SubList(l, n+1, ListLen(l)));
 *				f(l)
 *
 * As in Lisp environments, the non-copy semantics of SubList is fine here, as
 * long as no mutations are subsequently performed.  To be specific, the Lisp
 * analog being referred to is the non-copy semantics of cdr, which is fine
 * when mutations are not performed with Lisp destructive functions.  "Fine"
 * means that non-mutating semantics are preserved.
 */
List* ConcatLists(List* l1, List* l2);

/*
 * Return non-zero if the given element is in the given list, 0 otherwise.  A
 * non-zero return value is the position of the given element in the list.  The
 * given element is compared to the list elements using ==.  To perform the
 * comparison with a different comparator function, use InListWithFunction.
 */
int InList(List* l, ListElemData* e);

/*
 * Like InList, but uses the given comparator function to test for equality of
 * the given element with the list elements.  The comparator function is
 * boolean-valued, returning true for equals and false for unequals.
 */
int InListWithFunction(List* l, ListElemData* e,
    bool (*compare_func)(ListElemData*, ListElemData*));

/*
 * Return the length of the given list.  Return 0 if the list is empty or null.
 */
int ListLen(List* l);

/*
 * Generate all elements of the given list, starting from the front.
 * Successive calls to EnumList will return the next successive element.  Null
 * is returned for an empty list or at the end of a non-empty list enumeration.
 */
ListElemData* EnumList(List* l);

/*
 * Reset the EnumList generator for the given list, such that the next call to
 * EnumList will return the first element.
 */
void ResetListEnum(List* l);

/*
 * Increment by one the reference count of the given list.  In a garbage
 * collection and/or copy management regime, this function is called whenever a
 * list value is bound to a storage designator.  Return the resulting, i.e.,
 * incremented ref_count value.
 */
int IncrListRefs(List* l);

/*
 * Decrement by one the reference count of the given list.  In a garbage
 * collection and/or copy management regime, this function is called whenever a
 * list-valued storage designator changes its value or ends its lifetime.
 * Return the resulting, i.e., decremented ref_count value.
 */
int DecrListRefs(List* l);

/*
 * Print the given list to stdout, using the given function to print each
 * element.  The print_func is called with the void* data pointer from each
 * list element.  The print_func is responsible for printing the value of its
 * given element to stdout.  PrintList prints an opening square bracket at the
 * beginning of the list, a closing bracket at the end, and a comma between
 * each printed element.
 */
void PrintList(List* l, void (*print_func)(ListElemData*));

#endif