From CS113

Implement the follwing Linked-List specification:

File: llist.h

#ifndef __LLIST_H
#define __LLIST_H

typedef void *llist;
typedef void *(llist_foldfn)(void *base, void *elem);
typedef void *(llist_mapfn)(void *base, void *elem);
typedef void (llist_appfn)(void *base, void *elem);
typedef int (llist_unzipfn)(void *base, void *elem);
typedef int (llist_zipfn)(void *base, void *zelem, void *nzelem);

/* Creates a new linked list. */
llist llist_new();

/* Returns 0 if the list has elements, non-zero otherwise */
int llist_isempty(llist list);

/* Adds an element to the front of the list and returns the 
   new linked list. */
llist llist_push(void *elem, llist list);

/* Removes an element from the front of the list (stored in the
   output argument, and returns the remaining elements. */
llist llist_pop(void **elem, llist list);

/* Frees a list. */
void llist_free(llist list);

/* Given a function f, and an initial value b, computes
   f(f(f(f(f(f(b, l1), l2), l3) ... ), lN)
   where l1 is the first element at the begining of the list, 
   l2 is the next list-element, l3 after that, and so on until
   the last element lN */
void *llist_foldl(llist_foldfn f, void *b, llist list);

/* Given a function f, and an initial value b, computes
   f(f(f(f(f(f(b, lN), ...), l3), l2) l1)
   where l1 is the first element at the begining of the list, 
   l2 is the next list-element, l3 after that, and so on until
   the last element lN */
void *llist_foldr(llist_foldfn f, void *b, llist list);

/* Given a function f and base b, and a list [l1, l2, l3, ..., lN]
   constructs a list [f(b,l1), f(b,l2), f(b,l3), ..., f(b,lN)] */
llist llist_map(llist_mapfn f, void *b, llist list);

/* Applies a function f(b, elem) to each element in the list */
void llist_app(llist_appfn f, void *b, llist list);

//-----------------------------------------------------------------
// THE FOLLOWING FUNCTIONS ARE OPTIONAL. REPLACE WITH BLANK STUBS
// IF YOU DO NOT PLAN TO IMPLEMENT THE FOLLOWING FUNCTIONS
//-----------------------------------------------------------------

/* Splits a list into two lists based on the result of f.
   If f returns a 0 for an element, it is put in zlist other
   wise in nzlist. The original list is destroyed in the process. 
   [l1, l2, l3, ... lN] goes to [l2, l3, ..], [l1, ..., LN]
   assuming f(b,l2) is 0, f(b,l3) is 0, f(b,l1) is NOT 0, l(b,lN) is NOT 0 */
void llist_unzip(llist *zlist, llist *nzlist, llist_unzipfn f, void *b, llist list);

/* Merges two lists based on the result of f applied to the head of the two
   lists. If zlist is [l2, l3, l5 ...] and nzlist is [l1, l4, ..., lN] and
   f(b, l2, l1) is NOT 0 then the first element in the resulting list is l1.
   Subsequently, if f(b, l2, l4) is 0 then the next element in the resulting
   list is l2. Next, if f(b, l3, l4) is 0 then the next element is l3. Then
   if f(b, l5, l4) is NOT 0 then the next element is l4 and so on. The two original
   lists are destroyed in the process. */
llist llist_zip(llist zlist, llist nzlist, llist_zipfn f, void *b);

#endif

Submitting Your Code

Create the files llist.c and llist.h

Testing Your Code

Test programs will be posted here shortly. The test program must compile cleanly with your library. Each test in the test program should pass when run.

Download the source for the test harness by running:

[netid@submit cs113]$ wget http://submit.cs.cornell.edu/~cs113/2006fa/llist_test.c

Compile the test harness:

[netid@submit cs113]$ gcc -o llist_test llist_test.c llist.c

Run the test using:

[netid@submit cs113]$ ./llist_test
... help information ...
[netid@submit cs113]$ ./llist_test new
... test output ...
[netid@submit cs113]$ ./llist_test push
...
[netid@submit cs113]$ ./llist_test pop
[netid@submit cs113]$ ./llist_test isempty
[netid@submit cs113]$ ./llist_test free
[netid@submit cs113]$ ./llist_test foldl
[netid@submit cs113]$ ./llist_test foldr
[netid@submit cs113]$ ./llist_test map
[netid@submit cs113]$ ./llist_test app
[netid@submit cs113]$ ./llist_test unzip
[netid@submit cs113]$ ./llist_test zip