/*****************************************************************************
******************************************************************************
**                                                                          **
**                          Generic List Library                            **
**                                                                          **
**                            by Keith Pomakis                              **
**                            pomakis@pobox.com                             **
**                                                                          **
**                              Spring, 1994                                **
**                                                                          **
******************************************************************************
*****************************************************************************/

/* $Id: generic_list.docs,v 1.1 2013/12/21 02:55:46 pomakis Exp pomakis $ */

                          ****  Documentation  ****


*****************************************************************************
PURPOSE AND HISTORY
*****************************************************************************

The basic data structures of lists, stacks and queues are fundamental to
programming at almost every level.  However, because of the nature of the C
programming language, it is difficult to program a set of generic list
functions without sacrificing simplicity.  Therefore, C programmers often
find themselves programming specialized list functions over and over again.
This is not only a large waste of effort, but can also be the source of many
errors since each individual implementation is often tested only
haphazardly.

After countless assignments and projects (both academic and personal) in
which I found myself constantly rewriting the same list manipulation
functions in slightly different contexts, I figured it was about time to
take the effort and program an efficient, flexible, and easy-to-use library
of generic list functions.  And that is exactly what I did!

It is my hope that, in distributing this library, others will be able to use
what I've put together to increase their own programming productivity.

    version 1.0 (circa 1994-04)
        - initial release

    version 1.1 (2013-12-20)
        - minor cosmetic changes


*****************************************************************************
DISCLAIMER
*****************************************************************************

I am releasing this library to the public domain.  Therefore, people can use
it, copy it, distribute it, modify it, and do whatever they want with it.

Although this library has been well thought out, tested, and used in real
applications, it is not guaranteed to be bug-free.  Therefore, I am not
responsible for anything that happens, either directly or indirectly, due to
the usage of this library.

If you modify or add to this library in any way, I'd appreciate it if you
dropped me a line (or Internet packet, whatever) telling me what you did.
I'm always interested in potential improvements to my work!

Also, if you find any bugs (gasp!) or have any questions or comments about
the library, you can contact me as well.  My e-mail address is
"pomaki@pobox.com".  I'd be interested in hearing what you think!

Oh, one other thing... I've put a lot of work into this library, so I'd
appreciate it if you kept my name attached to it when distributing or
modifying it.


*****************************************************************************
REQUIREMENTS
*****************************************************************************

The only requirements for the usage of this library are an ANSI C compiler,
a machine to run it on, and a project that is in need of generic list
functions!  This library has been tested with gcc on a Sun 4, with gcc on
Linux and with Think C on a Macintosh.  The code is ANSI-C89-compliant, and
should present no problem with any other setup.


*****************************************************************************
PHILOSOPHY
*****************************************************************************

My goal when designing this library was to make it as flexible and complete
as possible, while still keeping it efficient and easy to use.  I have seen
and have tried to use other generic list libraries (and yes, I realize they
are numerous), but often they have failed me on one or more of the above
points.  I also realize that such a library would be a trivial piece of work
in C++.  However, as much of a proponent of the object-oriented paradigm as
I am, I tend to dislike C++ because of the hideous syntactic nightmares I
get when tackling the language.  Therefore, I have decided to write the
library in C.

A set of basic generic doubly-linked list functions were designed and
programmed first (along with a suitable efficient data structure), and then
some higher-level functions were added to increase ease of use.  The
functionality of stacks, queues and sorted lists were then added.  In
actuality, these functions (with the exception of one of the sorted-list
functions) are nothing more than aliases for the appropriate generic list
operations.  This aliasing is behind the scenes, however, and the user of
this library may treat the operation of lists, stacks and queues in this
library as completely separate functionality.

In order to make the library completely generic, it was designed to
manipulate pointers of type void *.  Therefore, it is assumed that the
programmer is statically or dynamically creating the objects of interest,
and using the generic list functions to manipulate them.  It is up to the
programmer to handle the allocation and deallocation of the memory for the
objects themselves.

A pointer to the same object may be stored in a list multiple times.  The
only restriction imposed is that a NULL pointer may not be stored.


*****************************************************************************
USAGE
*****************************************************************************

The use of this library is simple and straight-forward.  In every source
file that requires the use of generic list functions, the line:

#include "generic_list.h"

must be included at the top of the file.  For those who hand-craft their own
makefiles, "generic_list.h" should become a prerequisite for each of these
files, as well as for "generic_list.c" itself.

The library defines three data types:

    Generic_list
    Generic_stack
    Generic_queue

The usage of these functions is best illustrated with an example:

foo() {
    Generic_stack stack;
    My_object *obj;

    initialize_stack(&stack);

    obj = new_object();
    push(stack, obj);
    ...
    obj = pop(stack);
    free(obj);
    ...
    destroy_stack(&stack);
}

Each list must be initialized before use and should be destroyed after it is
no longer needed.  The programmer must handle the allocation and
deallocation of the memory for the objects being stored.  Explicit memory
management for the lists is not necessary.


*****************************************************************************
LIST OF FUNCTIONS
*****************************************************************************

The following are the headers of the functions provided in the generic list
library.  They are described in more detail later.

Generic Lists
-------------

void initialize_list(Generic_list *list);
void destroy_list(Generic_list *list);
void add_to_beginning(Generic_list list, void *pointer);
void add_to_end(Generic_list list, void *pointer);
void add_to_list(Generic_list list, void *pointer);
void *remove_from_beginning(Generic_list list);
void *remove_from_end(Generic_list list);
void *remove_from_list(Generic_list list, void *pointer);
void *peek_at_beginning(Generic_list list);
void *peek_at_end(Generic_list list);

void *first_in_list(Generic_list list);
void *next_in_list(Generic_list list);
void *current_in_list(Generic_list list);
void *remove_current(Generic_list list);
void *previous_in_list(Generic_list list);
void *last_in_list(Generic_list list);
void reset_to_beginning(Generic_list list);
void reset_to_end(Generic_list list);

int num_of_objects(const Generic_list list);
int is_empty(const Generic_list list);
int is_in_list(const Generic_list list, const void *pointer);
Generic_list copy_list(Generic_list list);

void perform_on_list
     (Generic_list list, void (*fn)(void *pointer, void *args), void *args);
void *first_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);
void *next_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);
void *previous_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);
void *last_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);
Generic_list all_such_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);
void remove_all_such_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);


Generic Sorted Lists
--------------------

void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b));

...and all Generic_list functions except:

void add_to_beginning(Generic_list list, void *pointer);
void add_to_end(Generic_list list, void *pointer);
void *remove_from_beginning(Generic_list list);
void *remove_from_end(Generic_list list);


Generic Stacks
--------------

void initialize_stack(Generic_stack *stack);
void destroy_stack(Generic_stack *stack);
void push(Generic_stack stack, void *pointer);
void *pop(Generic_stack stack);
void pop_all(Generic_stack stack);
void *peek_at_top(Generic_stack stack);
Generic_stack copy_stack(Generic_stack stack);
int is_empty(const Generic_stack stack);


Generic Queues
--------------

void initialize_queue(Generic_queue *queue);
void destroy_queue(Generic_queue *queue);
void enqueue(Generic_queue queue, void *pointer);
void *dequeue(Generic_queue queue);
void dequeue_all(Generic_queue queue);
void *peek_at_head(Generic_queue queue);
void *peek_at_tail(Generic_queue queue);
Generic_queue copy_queue(Generic_queue queue);
int is_empty(const Generic_queue queue);


*****************************************************************************
DETAILED DESCRIPTION OF FUNCTIONS
*****************************************************************************

Generic Lists
-------------

void initialize_list(Generic_list *list);

    Every list must be initialized before it is used, unless it is the
    destination of a copy.  The only time it is valid to re-initialize a
    list is after it has been destroyed.

void destroy_list(Generic_list *list);

    When a list is no longer needed, it should be destroyed.  This process
    will automatically remove all remaining objects from the list.  However,
    the memory for these objects will not be reclaimed, so if the objects
    have no other references, care should be taken to purge the list and
    free all objects before destroying the list.

    It is an error to destroy a list more than once (unless it has been
    re-initialized in the meantime).

void add_to_beginning(Generic_list list, void *pointer);

    This function will add the specified object to the beginning of the
    list.  The pointer must not be NULL.

void add_to_end(Generic_list list, void *pointer);

    This function will add the specified object to the end of the
    list.  The pointer must not be NULL.

void add_to_list(Generic_list list, void *pointer);

    This function will add the specified object to the list.  The pointer
    must not be NULL.

void *remove_from_beginning(Generic_list list);

    This function will remove the first object from the beginning of the
    list and return it.  If the list is empty, NULL is returned.

void *remove_from_end(Generic_list list);

    This function will remove the last object from the end of the list and
    return it.  If the list is empty, NULL is returned.

void *remove_from_list(Generic_list list, void *pointer);

    This function will remove the specified object from the list and return
    it.  If the specified object does not exist in the list, NULL is
    returned.  If the specified object exists in the list more than once,
    only the last reference to it is removed.

void remove_all(Generic_list list);

    This function will remove all objects from the list.  Note that the
    memory for these objects will not be reclaimed, so if the objects have
    no other references, they should be removed one at a time, freeing them
    when necessary.

void *peek_at_beginning(Generic_list list);

    This function will return the first object in the list.  If the list is
    empty, NULL is returned.

void *peek_at_end(Generic_list list);

    This function will return the last object in the list.  If the list is
    empty, NULL is returned.

void *first_in_list(Generic_list list);

    This function will return the first object in the list and mark it as
    the current object.  If the list is empty, NULL is returned.

void *next_in_list(Generic_list list);

    This function will return the next object in the list and mark it as
    the current object.  If the end of the list is reached, or if the list
    is empty, NULL is returned.

void *current_in_list(Generic_list list);

    This function will return the object in the list that is considered
    the current object (as defined by the surrounding functions).  If the
    current object has just been removed, if current points to the
    beginning or end of the list, or if the list is empty, NULL is
    returned.

void *remove_current(Generic_list list);

    This function will remove the current object from the list and return
    it.  If the current object has already been removed, if current points
    to the beginning or end of the list, or if the list is empty, NULL is
    returned.

void *previous_in_list(Generic_list list);

    This function will return the previous object in the list and mark it
    as the current object.  If the beginning of the list is reached, or if
    the list is empty, NULL is returned.

void *last_in_list(Generic_list list);

    This function will return the last object in the list and mark it as
    the current object.  If the list is empty, NULL is returned.

void reset_to_beginning(Generic_list list);

    This function will reset the list to the beginning.  Therefore, current
    points to the beginning of the list, and the next object in the list is
    the first object.

void reset_to_end(Generic_list list);

    This function will reset the list to the end.  Therefore, current
    points to the end of the list, and the previous object in the list is
    the last object.

int num_of_objects(const Generic_list list);

    This function will return the number of objects in the list.

int is_empty(const Generic_list list);

    This function will return TRUE (1) if the list is empty, and FALSE (0)
    otherwise.

int is_in_list(const Generic_list list, const void *pointer);

    This function will return TRUE (1) if the specified object is a member
    of the list, and FALSE (0) otherwise.  Note that this only compares
    object pointers.  If an identical object is a member of the list, but
    occupies a different location in memory, this function will return
    FALSE.

Generic_list copy_list(Generic_list list);

    This function will return a copy of the list.  The objects themselves
    are not copied; only new references to them are made.  The new list
    loses its concept of the current object.  The destination of this copy
    need not be initialized.  However, care must be taken to destroy the
    copy when it is no longer needed.

void perform_on_list
     (Generic_list list, void (*fn)(void *pointer, void *args), void *args);

    This function will perform the specified function on each object in the
    list.  Any optional arguments required can be passed through args.

void *first_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

     This function will find and return the first object in the list which
     causes the specified function to return a TRUE (non-zero) value.  Any
     optional arguments required can be passed through args.  The found
     object is then marked as the current object.  If no objects in the list
     meet the criteria of the specified function, NULL is returned.

void *next_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

     This function will find and return the next object in the list which
     causes the specified function to return a TRUE (non-zero) value.  Any
     optional arguments required can be passed through args.  The found
     object is then marked as the current object.  If there are no objects
     left in the list that meet the criteria of the specified function,
     NULL is returned.

void *previous_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

     This function will find and return the previous object in the list
     which causes the specified function to return a TRUE (non-zero) value.
     Any optional arguments required can be passed through args.  The found
     object is then marked as the current object.  If there are no objects
     left in the list that meet the criteria of the specified function,
     NULL is returned.

void *last_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

     This function will find and return the last object in the list which
     causes the specified function to return a TRUE (non-zero) value.  Any
     optional arguments required can be passed through args.  The found
     object is then marked as the current object.  If no objects in the
     list meet the criteria of the specified function, NULL is returned.

Generic_list all_such_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

    This function will return a new list containing all of the objects in
    the specified list which cause the specified function to return a TRUE
    (non-zero) value.  Any optional arguments required can be passed
    through args. The objects themselves are not copied; only new
    references to them are made.  Care must be taken to destroy this new
    list when it is no longer needed.

void remove_all_such_that
     (Generic_list list, int (*fn)(const void *pointer, const void *args),
                         const void *args);

    This function will remove all objects in the list which cause the
    specified function to return a TRUE (non-zero) value.  Any optional
    arguments required can be passed through args.  Note that the memory
    for these objects will not be reclaimed, so if the objects have
    no other references, it is best to avoid this function and remove the
    objects one by one, freeing them when necessary.


Generic Sorted Lists
--------------------

void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b));

    This function initializes a sorted list.  A less-than function must be
    specified which accepts two pointers, a and b, and returns TRUE
    (non-zero) if a is less than b, FALSE otherwise.

    Once a list is initialized in this way, all of the generic list
    functions described above can be used, except for:

        void add_to_beginning(Generic_list list, void *pointer);
        void add_to_end(Generic_list list, void *pointer);
        void *remove_from_beginning(Generic_list list);
        void *remove_from_end(Generic_list list);

    In particular, the function add_to_list() should be used to add
    objects to the sorted list.  This will insure that the list will
    remain sorted by the criteria specified by the less-than function.

    The only time it is valid to re-initialize a list is after it has been
    destroyed.


Generic Stacks
--------------

void initialize_stack(Generic_stack *stack);

    Every stack must be initialized before it is used, unless it is the
    destination of a copy.  The only time it is valid to re-initialize a
    stack is after it has been destroyed.

void destroy_stack(Generic_stack *stack);

    When a stack is no longer needed, it should be destroyed.  This process
    will automatically remove all remaining objects from the stack.
    However, the memory for these objects will not be reclaimed, so if the
    objects have no other references, care should be taken to purge the
    stack and free all objects before destroying the stack.

    It is an error to destroy a stack more than once (unless it has been
    re-initialized in the meantime).

void push(Generic_stack stack, void *pointer);

    This function will push the specified object onto the stack.  The
    pointer must not be NULL.

void *pop(Generic_stack stack);

    This function will pop the first object from the top of the stack and
    return it.  If the stack is empty, NULL is returned.

void pop_all(Generic_stack stack);

    This function will pop all objects from the stack.  Note that the
    memory for these objects will not be reclaimed, so if the objects have
    no other references, they should be popped one at a time, freeing them
    when necessary.

void *peek_at_top(Generic_stack stack);

    This function will return the object on the top of the stack.  If the
    stack is empty, NULL is returned.

Generic_stack copy_stack(Generic_stack stack);

    This function will return a copy of the stack.  The objects themselves
    are not copied; only new references to them are made.  The destination
    of this copy need not be initialized.  However, care must be taken to
    destroy this copy when it is no longer needed.

int is_empty(const Generic_stack stack);

    This function will return TRUE (1) if the stack is empty, and FALSE (0)
    otherwise.


Generic Queues
--------------

void initialize_queue(Generic_queue *queue);

    Every queue must be initialized before it is used, unless it is the
    destination of a copy.  The only time it is valid to re-initialize a
    queue is after it has been destroyed.

void destroy_queue(Generic_queue *queue);

    When a queue is no longer needed, it should be destroyed.  This process
    will automatically remove all remaining objects from the queue.
    However, the memory for these objects will not be reclaimed, so if the
    objects have no other references, care should be taken to purge the
    queue and free all objects before destroying the queue.

    It is an error to destroy a queue more than once (unless it has been
    re-initialized in the meantime).

void enqueue(Generic_queue queue, void *pointer);

    This function will add the specified object to the tail of the queue.
    The pointer must not be NULL.

void *dequeue(Generic_queue queue);

    This function will remove the first object from the head of the queue
    and return it.  If the queue is empty, NULL is returned.

void dequeue_all(Generic_queue queue);

    This function will remove all objects from the queue.  Note that the
    memory for these objects will not be reclaimed, so if the objects have
    no other references, they should be dequeued one at a time, freeing
    them when necessary.

void *peek_at_head(Generic_queue queue);

    This function will return the object at the head of the queue.  If the
    queue is empty, NULL is returned.

void *peek_at_tail(Generic_queue queue);

    This function will return the object at the tail of the queue.  If the
    queue is empty, NULL is returned.

Generic_queue copy_queue(Generic_queue queue);

    This function will return a copy of the queue.  The objects themselves
    are not copied; only new references to them are made.  The destination
    of this copy need not be initialized.  However, care must be taken to
    destroy this copy when it is no longer needed.

int is_empty(const Generic_queue queue);

    This function will return TRUE (1) if the queue is empty, and FALSE (0)
    otherwise.


*****************************************************************************
HINTS AND RECOMMENDATIONS
*****************************************************************************

Technically, any of the above functions can be used with any of the three
data types.  For example, one can use perform_on_list() to perform a
specified function on every object in a queue, or is_in_list() to determine
whether or not a particular object is a member of a stack.  One can even
pop from a queue and dequeue from a stack.  However, such usage is not
recommended, as it is contrary to the logical usage of such data
structures.

A priority queue can be implemented with a sorted list.