Create a C program that implements lonely party arrays.(arrays that are broken into fragments that get allocated and deallocated on an as-needed basis, rather than being allocated all at once as one big array, in order to eliminate unnecessary memory bloat).

1. Overview For a lot of programming tasks that use arrays, its not uncommon to allocate an array that is large enough to handle any worst-case scenario you might throw at your program, but which has a lot of unused, wasted memory in most cases. For example, suppose were writing a program that needs to store the frequency distribution of scores on some exam. If we know the minimum possible exam score is zero and the maximum possible exam score is 109 (because there are a few bonus questions), and all possible scores are integers, then we might create an array of length 110 (with indices 0 through 109) to meet our needs. Suppose, then, that were storing data for 25 students who took that exam. If 3 of them earned 109%, 6 students earned 98%, 8 students earned 95%, 5 students earned 92%, 2 students earned 83%, and 1 student earned a 34%, the frequency array for storing their scores would look like this: 0 . . . 1 . . . 2 . . . 5 0 0 8 0 0 6 . . . 3 0 1..33 34 35..82 83 84..91 92 93 94 95 96 97 98 99..108 109 wasted space wasted space wasted space wasted space wasted space wasted space Notice that with only 6 distinct scores in the class, we only use 6 cells to record the frequencies of scores earned for all 25 students. The other 104 cells in the array are just wasted space. 1.1 Lonely Party Arrays to the Rescue! In this assignment, you will implement a new array-like data structure, called a lonely party array (or LPA),1 that will solve the problem described above. In this data structure, instead of allocating one large array, we will allocate smaller array fragments an as-needed basis.

1.2 Advantages of Lonely Party Arrays As with normal arrays in C, we will have fast, direct access to any index of a lonely party array at any given time. This data structure has three main advantages over Cs traditional arrays: 1. As we saw above, normal arrays often have wasted space. We will only allocate fragments of our lonely party arrays on an as-needed basis, and deallocate them when theyre no longer in use, which will reduce the amount of unused memory being wasted. 2. We will use get(), set(), and delete() functions to access and modify individual elements of the lonely party array, and these functions will help us avoid segfaults by first checking that we arent accessing array indices that are out of bounds. (Recall that C doesnt check whether an array index is out of bounds before accessing it during program execution. That can lead to all kinds of wacky trouble!) 3. In C, if we have to pass an array to a function, we also typically find ourselves passing its length to that function as a second parameter. With lonely party arrays, all the information you need about the data structure will get passed automatically with the array fragments themselves, as everything will be packaged together in a struct.

The lonely party arrays you implement for this assignment will be designed to hold integers. The precise number of fragments and the lengths of those fragments will be allowed to vary from one LPA to the next. A complete list of the functions you must implement, including their functional prototypes, is given below in Section 3, Function Requirements.

You will submit a single source file, named LonelyPartyArray.c, that contains all required function definitions, as well as any auxiliary functions you deem necessary. In LonelyPartyArray.c, you should #include any header files necessary for your functions to work, including LonelyPartyArray.h (see Section 2, LonelyPartyArray.h). Note that you will not write a main() function in the source file you submit! Rather, we will compile your source file with our own main() function(s) in order to test your code. We have attached example source files that have main() functions, which you can use to test your code. You should also write your own main() functions for testing purposes, but your code must not have a main() function when you submit it. We realize this is still fairly new territory for most of you, so dont panic. Weve included instructions on compiling multiple source files into a single executable (e.g., mixing your LonelyPartyArray.c with our LonelyPartyArray.h and testcase01.c files) in Section 5 (pg. 16). Although we have included sample main() functions to get you started with testing the functionality of your code, we encourage you to develop your own test cases, as well. Ours are by no means comprehensive. We will use much more elaborate test cases when grading your submission. Start early. Work hard. Good luck! 2. LonelyPartyArray.h This header file contains the struct definition and functional prototypes for the lonely party array functions you will be implementing. You must #include this file from LonelyPartyArray.c, as follows. Recall that the quotes (as opposed to ) indicate to the compiler that this header file is found in the same directory as your source, not a system directory: #include "LonelyPartyArray.h" Please do not modify LonelyPartyArray.h in any way, and do not send LonelyPartyArray.h when you submit your assignment. We will use our own copy of LonelyPartyArray.h when compiling your program. If you write auxiliary functions (helper functions) in LonelyPartyArray.c (which is strongly encouraged!), you should not add those functional prototypes to LonelyPartyArray.h. Our test case programs will not call your helper functions directly, so they do not need any awareness of the fact that your helper functions even exist. (We only list functional prototypes in a header file if we want multiple source files to be able to call those functions.) So, just put the functional prototypes for any helper functions you write at the top of your LonelyPartyArray.c file. Think of LonelyPartyArray.h as a bridge between source files. It contains struct definitions and functional prototypes for functions that might be defined in one source file (such as your LonelyPartyArray.c file) and called from a different source file (such as testcase01.c). The basic struct you will use for this data structure (defined in the header file) is as follows: typedef struct LonelyPartyArray { int size; // number of occupied cells across all fragments int num_fragments; // number of fragments (arrays) in this struct int fragment_length; // number of cells per fragment int num_active_fragments; // number of allocated (non-NULL) fragments int **fragments; // array of pointers to individual fragments int *fragment_sizes; // stores number of used cells in each fragment } LonelyPartyArray; The LonelyPartyArray struct contains an int** pointer that can be used to set up a 2D int array (which is just an array of int arrays). That fragments array will have to be allocated dynamically whenever you create a new LPA struct. The size member of this struct tells us how many elements currently reside in the lonely party array (i.e., how many int cells are actually being used across all the fragments and are not just wasted space). The fragment_length member tells us how many integer cells there should be in each individual fragment that we allocate. (All the non-NULL fragments within a given LPA struct will always be the same length.) num_active_fragments tells us how many non-NULL fragments this lonely party array is using. The fragment_sizes array is used to keep track of how many cells are actually being used in each fragment. This count allows us to determine very quickly whether we can deallocate a fragment any time we delete one of the elements it contains. This header file also contains definitions for UNUSED, LPA_SUCCESS and LPA_FAILURE, which you will use in some of the required functions described below. 3. Function Requirements In the source file you submit, LonelyPartyArray.c, you must implement the following functions. You may implement any auxiliary functions you need to make these work, as well. Please be sure the spelling, capitalization, and return types of your functions match these prototypes exactly. In this section, I often refer to malloc(), but youre welcome to use calloc() or realloc() instead, if youre familiar with those functions. LonelyPartyArray *createLonelyPartyArray(int num_fragments, int fragment_length); Description: This function will create a LonelyPartyArray (LPA) that can accommodate up to num_fragments different array fragments, each of length fragment_length. So, the maximum number of integers this LPA can hold is num_fragments x fragment_length. Start by dynamically allocating space for a new LonelyPartyArray struct. Initialize the structs num_fragments and fragment_length members using the arguments passed to this function. Initialize num_active_fragments and size to the appropriate values. Dynamically allocate the fragments array to be an array of num_fragments integer pointers, and initialize all those pointers to NULL. (Eventually, that array will store pointers to any individual array fragments you allocate when adding elements to this data structure.) Dynamically allocate the fragment_sizes array, and initialize all values to zero (since none of the fragments currently hold any elements). If one or both of the parameters passed to this function are less than or equal to zero (i.e., if they are not both positive integers), you should immediately return NULL. If any of your calls to malloc() fail, you should free any memory you have dynamically allocated in this function call up until that point (to avoid memory leaks), and then return NULL. Output: If the function successfully creates a new LPA, print the following: -> A new LonelyPartyArray has emerged from the void. (capacity: , fragments: ) Do not print the quotes, and do not print around the variables. Terminate the line with a newline character, . is the maximum number of integers this LPA can contain (num_fragments x fragment_length). is simply num_fragments. Note that in testing, we will never create a lonely party array whose capacity would be too large to store in a 32-bit int. Returns: A pointer to the new LonelyPartyArray, or NULL if any calls to malloc() failed. LonelyPartyArray *destroyLonelyPartyArray(LonelyPartyArray *party); Description: Free all dynamically allocated memory associated with this LonelyPartyArray struct, and return NULL. Be careful to avoid segfaulting in the event that party is NULL. Output: -> The LonelyPartyArray has returned to the void. (Output should not include the quotes. Terminate the line with a newline character, .) If party is NULL, this function should not print anything to the screen. Returns: This function should always return NULL. int set(LonelyPartyArray *party, int index, int key); Description: Insert key into the appropriate index of the lonely party array. Based on the index parameter passed to this function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought. For example, if index is 14 and the LPA has num_fragments = 3 and fragment_length = 12, then key would go into the second array fragment (fragments[1]) at index 2 (fragments[1][2]), since the first fragment (fragments[0]) would be used for indices 0 through 11, the second fragment would be used for indices 12 through 23, and the third fragment would be used for indices 24 through 35, for a total of 36 cells across the 3 fragments. For additional indexing examples, please refer to the test cases included with this assignment. If the fragment where we need to insert key is NULL, then you should dynamically allocate space for that fragment (an array of fragment_length integers), initialize each cell in that new fragment to UNUSED (which is #defined in LonelyPartyArray.h), update the structs num_active_fragments member, and store key at the appropriate index in the new allocated array. If the index being modified was previously empty (i.e., UNUSED), and/or if the fragment was not yet allocated, then after inserting key into the lonely party array, be sure to increment the structs size member so that it always has an accurate count of the number of cells in the LPA that are currently occupied, and be sure to increment the appropriate value in the structs fragment_size array so that it always has an accurate count of the number of cells currently being used in each particular fragment. If index is invalid (see note below), or if a NULL party pointer is passed to this function, simply return LPA_FAILURE without attempting to modify the data structure in any way and without causing any segmentation faults. Note on invalid index values: In our set(), get(), and delete() functions, index is considered valid if it falls in the range 0 through (num_fragments x fragment_length - 1), even if index refers to a cell marked as UNUSED or a fragment that has not been allocated yet. An invalid index is one that falls outside that specified range. Output: There are three cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .) If calling this function results in the allocation of a new fragment in memory, print: -> Spawned fragment

. (capacity: , indices: ..)

is the index where the newly allocated fragments address is stored in the structs fragments array, and is the length of the new array (i.e., the number of integers it can hold), and and correspond to the lowest and highest index values that would map to this particular fragment. If party is non-NULL and index is invalid (see definition of invalid index above), print: -> Bloop! Invalid access in set(). (index: , fragment: , offset: ) is value of index passed to this function; is the invalid fragments array index that index would have mapped to, had that fragment been within bounds for this lonely party array; and is the precise index within that fragment that index would have mapped to. For example, if num_fragments = 2, fragment_length = 10, and index = 21, then the valid indices for this LPA would be 0 through 19, and index, being invalid, would produce this error message with = 2 and = 1. See testcase16.c and output16.txt for examples of how to handle output for negative index values. For additional examples, please refer to the test cases included with this assignment. If party is NULL, print: -> Bloop! NULL pointer detected in set(). Output should not contain any quotes or angled brackets. Terminate the line with a newline character, . Returns: If this operation is successful, return LPA_SUCCESS. If the operation is unsuccessful (either because index is invalid or the function receives a NULL party pointer, or because any calls to malloc() fail), return LPA_FAILURE. LPA_SUCCESS and LPA_FAILURE are #defined in LonelyPartyArray.h. int get(LonelyPartyArray *party, int index); Description: Retrieve the value stored at the corresponding index of the lonely party array. As with the set() function, based on the index parameter passed to this function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought. Keep in mind that index could try taking you to a fragment that has not yet been allocated. Its up to you to avoid going out of bounds in an array and/or causing any segmentation faults. Output: There are two cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .) If index is invalid (see definition of invalid index in the set() function description) and party is non-NULL, print: -> Bloop! Invalid access in get(). (index: , fragment: , offset: ) For explanations of , , and , see the set() function description above. Note that if a cell is marked as UNUSED, but index is within range, you should not generate this error message. If party is NULL, print: -> Bloop! NULL pointer detected in get(). Returns: If index is valid (see definition of invalid index in the set() function description), return the value stored at the appropriate index in the lonely party array (even if it is marked as UNUSED). If index is technically valid (according to the definition in the set() function description) but refers to a cell in an unallocated fragment, return UNUSED. If the operation is unsuccessful (either because index is invalid or because the function receives a NULL party pointer), return LPA_FAILURE. Continued on the following page... int delete(LonelyPartyArray *party, int index); Description: Set the value stored at the corresponding index of the lonely party array to UNUSED. As with the set() and get() functions, based on the index parameter passed to this function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought. If the cell being sought is not already set to UNUSED, then after writing UNUSED to that cell, decrement the structs size member so that it always has an accurate count of the total number of cells that are currently being used, and decrement the appropriate value in the structs fragment_size array so that it always has an accurate count of the number of cells currently being used in each fragment. If deleting the value at this index causes the fragment containing that value to become empty (i.e., all of its cells are now UNUSED), deallocate that array, set the appropriate pointer in the structs fragments array to NULL, and update the structs num_active_fragments member. You should never loop through a fragment to see if all of its cells are unused. Instead, you should rely on the fragment_sizes array to keep track of whether or not a fragment is ready for deallocation. Keep in mind that index could try taking you to a fragment that has not yet been allocated. Its up to you to avoid going out of bounds in an array and/or causing any segmentation faults. Output: There are three cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .) If calling this function results in the deallocation of a fragment in memory, print: -> Deallocated fragment

. (capacity: , indices: ..) For explanations of

, , , and , see the set() function description above. If index is invalid (see definition of invalid index in the set() function description) and party is non-NULL, print: -> Bloop! Invalid access in delete(). (index: , fragment: , offset: ) For explanations of , , and , see the set() function description above. Note that if a cell is marked as UNUSED, but index is within range, you should not generate this error message. If party is NULL, print: -> Bloop! NULL pointer detected in delete(). Returns: Return LPA_FAILURE if this operation refers to an invalid index (as defined in the set() function description), if this function receives a NULL party pointer, if this operation refers to a cell that lies within an unallocated fragment, or if this operation refers to a cell whose value was already set to UNUSED when the function was called. Otherwise, return LPA_SUCCESS. int containsKey(LonelyPartyArray *party, int key); Description: Perform a linear search through the entire lonely party array to determine whether it contains key (i.e., whether key is stored in any of the cells in the LPA). Be careful to avoid segmentation faults. Output: This function should not print anything to the screen. Returns: Return 1 if the LPA contains key. Otherwise, return 0. If party is NULL, return 0. int isSet(LonelyPartyArray *party, int index); Description: Determine whether there is a value (other than UNUSED) being stored at the corresponding index of the lonely party array. Be careful to avoid segmentation faults. Output: This function should not print anything to the screen. Returns: If index is invalid (according to the definition of invalid index given in the set() function description), or if it refers to a cell marked as UNUSED or a fragment that has not been allocated yet, or if party is NULL, return 0. Otherwise, return 1. int printIfValid(LonelyPartyArray *party, int index); Description: Print the value stored at the corresponding index of the lonely party array. As with the set(), get(), and delete() functions, based on the index parameter passed to this function, as well as the number of fragments in the LPA and the length of each fragment, you will have to determine which fragment index maps to, and precisely which cell in that array fragment is being sought. Output: Simply print the appropriate integer to the screen, followed by a newline character, . This function should not print anything if index is invalid (as defined in the set() function description), if index refers to a cell whose value is set to UNUSED, or if party is NULL. Returns: Return LPA_SUCCESS if this function prints a value to the screen. Otherwise, return LPA_FAILURE. LonelyPartyArray *resetLonelyPartyArray(LonelyPartyArray *party); Description: Reset the lonely party array to the state it was in just after it was created with createLonelyPartyArray(). Be sure to avoid any memory leaks or segmentation faults. You will need to deallocate any array fragments that are currently active within party. You will also need to reset all the values in the structs fragments and fragment_sizes arrays. However, you should not re-allocate the fragments or fragment_sizes arrays; simply reset the values contained in those already-existing arrays. You will also need to reset the structs size and num_active_fragments members. You should not, however, change the values of num_fragments or fragment_length. Output: There are two cases that should generate output for this function. (Do not print the quotes, and do not print around the variables. Terminate any output with .) If party is non-NULL, print: -> The LonelyPartyArray has returned to its nascent state. (capacity: , fragments: ) Here, is the maximum number of integers the lonely party array can hold, and is the value of the structs num_fragments member. If party is NULL, be sure to avoid segmentation faults, and simply return from the function after printing the following: -> Bloop! NULL pointer detected in resetLonelyPartyArray(). Returns: This function should always return party. int getSize(LonelyPartyArray *party); Description: This function simply returns the number of elements currently in the LPA (not including any elements marked as UNUSED). This should be a near-instantaneous function call; it should not loop through the cells in the LPA at all. We provide this function to discourage other programmers from ever accessing partysize directly if they try to compile code that uses our fancy LPA data structure. That way, if we release this data structure to the public but then end up updating it a few months later to rename the size member of the LonelyPartyArray struct to something else, the programmers who have been using our code and end up downloading the latest version can get it working right out of the box; they dont have to go through their own code and change all instances of partysize to something else, as long as we still provide them with a getSize() function that works as intended.3 Output: This function should not print anything to the screen. Returns: Return the number of elements currently in the LPA, or -1 if party is NULL. int getCapacity(LonelyPartyArray *party); Description: This function should simply return the maximum number of elements that party can hold, based on the values of its num_fragments and fragment_length members. For example, for the lonely party array shown on pg. 4 of this PDF, getCapacity() would return 110, because when all of its array fragments are allocated, it will be able to hold up to 110 integer elements. Note that in testing, we will never create a lonely party array whose capacity would be too large to store in a 32-bit int, so you dont need to worry about type casting when calculating this return value. 3 Note, by the way, that it is common to use the term size to refer to the number of elements that have been inserted into a data structure, while length often refers to the number of cells in an array, whether those cells have been used or not. (I.e., length refers to the maximum capacity of an array, in terms of the number of elements it can hold.) Output: This function should not print anything to the screen. Returns: Return the capacity of the LPA (as just described), or -1 if party is NULL. int getAllocatedCellCount(LonelyPartyArray *party); Description: This function should return the maximum number of elements that party can hold without allocating any new array fragments. For example, for the lonely party array shown on pg. 4 of this PDF, getAllocatedCellCount() would return 40, because the non-NULL fragments are able to hold up to 40 integer elements in total. Output: This function should not print anything to the screen. Returns: Return the number of allocated integer cells (as just described), or -1 if the party pointer is NULL. long long unsigned int getArraySizeInBytes(LonelyPartyArray *party); Description: This function should return the number of bytes that would be used if we were using a standard array rather than a LonelyPartyArray struct. For example, for the LPA struct shown on pg. 4 of this PDF, a traditional array representation would have 110 integer cells, which would occupy 110 x sizeof(int) = 440 bytes, and so this function should return 440 for that struct. For additional examples, please refer to the test cases included with this assignment. Note: This number could get quite large, and so as you perform the arithmetic here, you should cast to long long unsigned int. (For details, see Appendix B on pg. 23.) Note: You should use sizeof() in this function (rather than hard-coding the size of an integer as 4 bytes), and cast the sizeof() values to long long unsigned int as appropriate. Note: If your system does not use 32-bit integers for some reason, using sizeof() in this function could cause output mismatches on some test cases. For this function to work, you will need to ensure that youre testing on a system that uses 32-bit integers (which you almost certainly are). To check that, you can compile and run SanityCheck.c (included with this assignment), or simply run the test-all.sh script. Output: This function should not print anything to the screen. Returns: The number of bytes (as just described), or 0 if the party pointer is NULL. long long unsigned int getCurrentSizeInBytes(LonelyPartyArray *party); Description: This function should return the number of bytes currently taken up in memory by the LPA. You will need to account for all of the following: The number of bytes taken up by the LPA pointer itself: sizeof(LPA*) The number of bytes taken up by the LPA struct (which is just the number of bytes taken up by the four integers and two pointers within the struct): sizeof(LPA) The number of bytes taken up by the fragments array (i.e., the number of bytes taken up by the pointers in that array). The number of bytes taken up by the fragment_sizes array (i.e., the number of bytes taken up by the integers in that array). The number of bytes taken up by the active fragments (i.e., the number of bytes taken up by all the integer cells in the individual array fragments). The getArraySizeInBytes() and getCurrentSizeInBytes() functions will let you see, concretely, the amount of memory saved by using a lonely party array instead of a traditional C-style array.4 Note: This number could get quite large, and so as you perform the arithmetic here, you should cast to long long unsigned int. (For details, see Appendix B on pg. 23.) Note: You should use sizeof() in this function (rather than hard-coding the sizes of any data types), and cast the sizeof() values to long long unsigned int as appropriate. Output: This function should not print anything to the screen. Returns: The number of bytes (as just described), or 0 if the party pointer is NULL. double difficultyRating(void); Note: You do not need to call this function anywhere in your code. I will call this function myself to gather data on how difficult students found this assignment. Output: This function should not print anything to the screen. Returns: A double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult). double hoursSpent(void); Note: You do not need to call this function anywhere in your code. I will call this function myself to gather data on how much time students estimate spending on this assignment. Output: This function should not print anything to the screen. Returns: A reasonable estimate (greater than zero) of the number of hours you spent on this assignment. 4 Note that lonely party arrays are best used to replace large, sparsely populated arrays. Because of all the pointers in the LPA struct, a densely populated lonely party array could actually take up more space than a traditional C-style array. 3.1 Bonus Functions This function is optional. Any credit awarded for this function will be given as bonus points. LonelyPartyArray *cloneLonelyPartyArray(LonelyPartyArray *party); Description: Dynamically allocate a new LonelyPartyArray struct and set it up to be a clone of party. The clone should have entirely new, separate copies of all the data contained within party. (For example, the clone should not simply refer to partys fragments. Instead, it should have entirely new copies of those fragments.) If any calls to malloc() fail, free any memory that this function dynamically allocated up until that point, and then return NULL. Output: If party is non-NULL, print the following: -> Successfully cloned the LonelyPartyArray. (capacity: , fragments: ) This output should not include the quotes or angled brackets. Terminate the line with a newline character, . is the maximum number of integers this LPA can contain (num_fragments x fragment_length). is simply num_fragments. Note that in testing, we will never create a lonely party array whose capacity would be too large to store in a 32-bit int. If party is NULL, or if any calls to malloc() fail, this function should not print anything to the screen. Returns: If party is NULL, or if any calls to malloc() fail, simply return NULL. Otherwise, return a pointer to the newly allocated lonely party array.