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, \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!
