7/16/2020 CS 136 Assignment 8
https://www.student.cs.uwaterloo.ca/~cs136/current/assignments/a8/ 1/2
a. [q3a-shopping-item] In this question, we will implement an ADT for storing a
single item on our shopping list.
item_create(name, amount, price, priority) creates a single shopping
item in heap memory and returns a pointer to it. Please see shopping.h for
detailed specifications. Be aware that the string name must be copied into the
shopping item structure; the price is given in cents per amount.
item_clone(item) creates a copy of another item in heap memory and
returns a pointer to it. Please see shopping.h for detailed specifications.
item_read(item) creates a single shopping item with data from input. The
function returns the number of correctly read shopping items, i.e., 0 or 1.
[You may assume that the name of the shopping item does not exceed 42
characters.] [Jun 13] Please see shopping.h for detailed specifications and
the correct input format. Be aware that the parameter item is given as
a struct shpg_item ** (pointer-pointer): consider what this means in term
of the C memory model and check the correct call format in main.c.
item_destroy(item) releases all resources from item.
item_combine(dest, source) combines two shopping items into a single
one by combining the information of source into dest. Two shopping items
can only be combined if they have the same name (although case does not
matter!). When combining two items, the amounts are added together; the
price is averaged, with respect to both amounts; and the new priority is the
higher of the two priorities.
item_print(item) prints out item. You may use the following format string
in your printf-call: "%s: %dx, $%d.%02d, <%d>\n".
comp_by_name(i1, i2) compares two shopping items in terms of their
name. The function returns -1 if i1 is sorted before i2, 1 if i1 is sorted
after i2, and 0 if i1 and i2 have the same name. Be aware that this function
does not consider case: "Apple", "APPLE", and "aPpLe", for example, would
all be considered equal.
comp_by_priority(i1, i2) compares two shopping items in terms of their
priority. The function returns -1 if i1 is sorted before i2, 1 if i1 is sorted
after i2, and 0 if i1 and i2 have the same priority.
For every data that we store in heap memory, we have to interact with it through a
pointer-type variable. For example, when creating a struct shpg_item, we interact with
it through a struct shpg_item *. We can store multiple of these structures together in
an shopping item array, which would be of type struct shpg_item **. Be aware that
these arrays with two levels of indirection are stored differently in memory than you
might expect: with one level, for example, int arr[] = { 1, 2, 3 };, the integer
values are tightly packed in adjacent memory cells. With two levels, for example, struct
foo **arr, the pointers to the struct foo are tightly packed, but the structures
themselves can be anywhere in heap memory The following animation illustrates this
7/16/2020 CS 136 Assignment 8
https://www.student.cs.uwaterloo.ca/~cs136/current/assignments/a8/ 2/2
behaviour. An interesting side effect of these arrays is that you can sort them, for
example, without moving the structures, the actual data around. Instead, you can simply
change the order of pointers in the array to achieve a different order of data.
7/16/2020 CS 136 Assignment 8
https://www.student.cs.uwaterloo.ca/~cs136/current/assignments/a8/ 1/1
b. [q3b-shopping-list] In this questions, we will implement a shopping list, which
should act as a container (or compound data type) for multiple shopping item.
Generally, there are three methods of implementing such a container: (1) we could
use a built-in compound data type, which in C means an array; (2) we could create
our own container data type, for example, a struct shpg_list; or (3) we could
use and adapt an existing ADT, such as, a stack or queue. In this questions, we will
use approach (1) and solely rely on an array of type struct shpg_list **. This
has the advantage that we will dive deeper and learn more about pointers and the
memory model in C, and that we will gain an appreciation for ADTs.
list_read(list, capacity) reads up to capacity shopping items from
input and stores them in list. The function returns the number of
successfully read shopping items. Be aware that the parameter list is given
as a struct shpg_item *** (pointer-pointer-pointer): consider what this
means in term of the C memory model and check the correct call format
in main.c.
list_destroy(list, list_len) releases all recourses from list.
item_print(list, list_len) prints out the list by printing each of its
items. For readability, please print a newline character ('\n') at the
beginning, i.e., before printing out the actual items.
list_sort(list, list_len, comp) sorts list using comp as comparator
function for the sort. While you may implement any sorting algorithm, we
recommend using quick sort. We have provided you with a pointer-based
quick-sort implementation that sorts integers in ascending order. You may
use this code as a staring point for your implementation.
comp_by_priority_name(i1, i2) compares two shopping items in terms of
their priority first and then their name. The function returns -1 if the priority
of i1 is higher than the one of i2 and 1 if the priority of i1 is lower than the
one of i2. If the priorities are equal, the function returns -1 if the name
of i1 comes before the one of i2; 1 if the name of i1 comes after the one
of i2; and 0 if the names are the same (ignoring case).
Hints:
For simplicity sake, you can assume that the name of shopping items will only
contains letters, i.e., the characters [A-Z] and [a-z].
7/16/2020 CS 136 Assignment 8
https://www.student.cs.uwaterloo.ca/~cs136/current/assignments/a8/ 1/1
c. [q3c-shopping-set] For this bonus question, implement the shopping set library. To
solve this question, you have to combine your knowledge and solutions from q2,
q3a, and q3b. In general, the solution is surprisingly straight forward, but there are
a lot of tiny, annoying devils in the details. Happy debugging!