Assignment 4b: C ‘Generic’ Array Lists Solution

Description




You are responsible for writing an array list library in C.




You are to implement the functions according to the speci cation below. You can nd the same information in the header le included with the HW4b les.




You are NOT responsible for actually implementing a node of a linked list; the implementation you should use is available in the aforementioned header le.




Testing




The given zip le also includes a main method with a small number of test cases. To use them, you may compile your code along with the les given (be sure the header le is in the same directory):












ls
-l






... alist . c alist . h bool . h main . c





gcc
-g -o alist alist . c main . c











If your code is correct, you should recieve something similar to the following output by running the output from the commands above: main function:





















































































1




Test Cases With A Correct Implementation





./ alist



Tagged List








-----------








{
(
18
,
t =8
)






,
(
19
,
t =7
)






,
(
8 ,
t =16
)






,
(
15
,
t =1
)






,
(
3 ,
t =2
)






}
















Mapped


& Tagged List






--------------------






{
(
19
,
t =7
)






,
(
20
,
t =6
)






,
(
9 ,
t =15
)






,
(
16
,
t =0
)






,
(
4 ,
t =1
)




}












All
checks passed .






























The driver is randomized, so your output will not be exactly the same. Consult the le comments for a more detailed explanation on what the output means.




Submitting




Your code should be submitted to the departmental dropbox with the lename alist.c




Grading




Your assignment will be graded according to the following equation:

114 (1:5)n
1










(1)
99
(1:5)n





where n is the number of fully completed functions.




For a more visual comparison:




Eq 1



1 0:38




2 0:64




3 0:82




4 0:92




5 1:00










2
Interface




alalloc | Allocate a new list.




Return (alist t*) An empty list of length DEFAULT LEN and size 0.




push | Append an item to the list.




If more space is needed, resizes to (old size + 1) * 2.




Parameters




alist_t* lst | The list (acting as a stack) void* lst | A pointer to the item to append.




pop | Delete an item from the end of the list.




Halves the length of the array if size == length / 4.




Parameters




alist_t* lst | The list (acting as a stack) Return (void*) A pointer to the popped element.




find | Returns an item matching a given criterion, if one exists.




Searches lst for the rst item where applying ‘sel’ to that item yields true. Note that this mutates the original list; it does not return a copy.




Parameters




alist_t* lst | The list to search




bool (*sel)(void*) | The (pointer to the) selection function.




Return (void*) The rst item that yields true if ‘sel’ is applied to it (searching from the bottom of the stack). Otherwise, NULL.




map | Maps a function pointwise over a list.




E.g. map(square, [1, 2, 3, 4]) = [1, 4, 9, 16]




Note that this mutates the original list; it does not return a copy.




Parameters




alist_t* lst | The list to map over




void* (*func)(void*) | The (pointer to the) function to map

























3