Abstract In this programming assignment, you will implement smart arrays (arrays that expand automatically whenever they get too full). This is an immensely powerful and awesome data structure, and it will ameliorate several problems we often encounter with arrays in C (see pg. 3 of this PDF). By completing this assignment, you will gain advanced experience working with dynamic memory management and structs in C. You will also gain additional experience managing programs that use multiple source files. In the end, you will have an awesome and useful data structure that you can reuse in the future.

1. Overview A smart array is an array that grows to accommodate new elements whenever it gets too full. As with normal arrays in C, we have direct access to any index of the smart array at any given time. There are four main advantages to using smart arrays, though: 1. We do not need to specify the length of a smart array when it is created. Instead, it will automatically expand when it gets full. This is great when we dont know ahead of time just how much data were going to end up holding in the array. 2. We will use get() and put() functions to access individual elements of the array, and these functions will check to make sure we arent accessing array positions 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 whacky trouble!) 3. If our arrays end up having wasted space (i.e., they arent full), we can trim them down to size. 4. 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 smart arrays, the length will get passed automatically with the array, as theyll both be packaged together in a struct. While some languages offer built-in support for smart arrays (such as Javas ArrayList class), C does not. Thats where you come in. You will implement basic smart array functionality in C, including: 1. automatically expanding the smart arrays capacity when it gets full; 2. adding new elements into arbitrary positions in the smart array, or at the end of the smart array; 3. providing safe access to elements at specific positions in the smart array; 4. gracefully signaling to the user (i.e., the programmer (re-)using your code) when he or she attempts to access an index in the smart array that is out of bounds (instead of just segfaulting); In this assignment, your smart array will be designed to hold arrays of strings. 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 SmartArray.c, that contains all required function definitions, as well as any auxiliary functions you deem necessary. In SmartArray.c, you should #include any header files necessary for your functions to work, including SmartArray.h (see Section 2, SmartArray.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.

2. SmartArray.h This header file contains the struct definition and functional prototypes for the smart array functions you will be implementing. You should #include this file from your SmartArray.c file, like so:

#include "SmartArray.h"

The basic struct you will use to implement the smart arrays (defined in SmartArray.h) is as follows: typedef struct SmartArray

{

char **array; // pointer to array of strings

int size; // number of elements in array

int capacity; // length of array (maximum capacity)

} SmartArray;

3. Function Requirements

In the source file you submit, SmartArray.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, as you see fit.

SmartArray *createSmartArray(int length); Description: Dynamically allocate space for a new SmartArray. Initialize its internal array to be of length length or DEFAULT_INIT_LEN, whichever is greater. (DEFAULT_INIT_LEN is defined in SmartArray.h.) Properly initialize pointers in the array to NULL, and set the size and capacity members of the struct to the appropriate values. Output: -> Created new SmartArray of size . (Output should not include the quotes. Terminate the line with a newline character, . should of course be the length of the new array, without the angled brackets.) Returns: A pointer to the new SmartArray, or NULL if any calls to malloc() failed.

SmartArray *destroySmartArray(SmartArray *smarty); Description: Free any dynamically allocated memory associated with the SmartArray struct and return NULL. Returns: NULL pointer.

SmartArray *expandSmartArray(SmartArray *smarty, int length); Description: Dynamically allocate a new array of length length. Copy the contents of smartys old array into the new array. Free any memory associated with the old smartyarray that is no longer in use, then set smartyarray to point to the newly created array. Be sure all pointers are properly initialized. Update the size and capacity of the SmartArray (if applicable). Note: If length is less than or equal to smartys current array capacity, or if the smarty pointer is NULL, you should NOT modify the SmartArray at all. In that case, just return from the function right away without producing any output. Output: -> Expanded SmartArray to size . (Output should not include the quotes. Terminate the line with a newline character, . should be the new length of the array, without the angled brackets. Do NOT produce any output if you the array is not expanded.) Returns: A pointer to the SmartArray, or NULL if any calls to malloc() failed.

SmartArray *trimSmartArray(SmartArray *smarty); Description: If smartys capacity is greater than its current size, trim the length of the array to the current size. You will probably want to malloc() a new array to achieve this. If so, avoid memory leaks as you get rid of the old array. Update any members of smarty that need to be updated as a result of this action. Output: -> Trimmed SmartArray to size . (Output should not include the quotes. Terminate the line with a newline character, . should be the new length of the array, without the angled brackets. Do NOT produce any output if the length of the array is not reduced by this function.) Returns: A pointer to the SmartArray, or NULL if malloc() failed or if smarty was NULL.

char *put(SmartArray *smarty, char *str); Description: Insert a copy of str into the next unused cell of the array. If the array is already full, call expandSmartArray() to grow the array to length (capacity * 2 + 1) before inserting the new element. When copying str into the array, only allocate the minimum amount of space necessary to store the string. Returns: A pointer to the copy of the new string that was inserted into the array, or NULL if the string could not be added to the array (e.g., malloc() failed, or smarty or str was NULL).

char *get(SmartArray *smarty, int index); Description: Attempts to return the element at the specified index. This is where you protect the user from going out-of-bounds with the array. Returns: A pointer to the string at position index of the array, or NULL if index was out of bounds or the smarty pointer was NULL.

char *set(SmartArray *smarty, int index, char *str); Description: If the array already has a valid string at position index, replace it with a copy of str. Otherwise, the operation fails and we simply return NULL. Ensure that no more space is used to store the new copy of str than is absolutely necessary (so, you might have to use malloc() and free() here). Returns: A pointer to the copy of the string placed in the SmartArray, or NULL if the operation failed for any reason (e.g., invalid index, or smarty or str was NULL).

char *insertElement(SmartArray *smarty, int index, char *str); Description: Insert a copy of str at the specified index in the array. Any elements to the right of index are shifted one space to the right. If the specified index is greater than the arrays size, the element being inserted should be placed in the first empty position in the array. As with the put() function, if the SmartArray is already full, call expandSmartArray() to grow the array to length (capacity * 2 + 1) before inserting the new element. When copying str into the array, only allocate the minimum amount of space necessary to store the string. Returns: A pointer to the copy of the string inserted into the array, or NULL if insertion fails for any reason (e.g., malloc() failed, or smarty or str was NULL).

int removeElement(SmartArray *smarty, int index); Description: Remove the string at the specified index in the array. Strings to the right of index are shifted one space to the left, so as not to leave a gap in the array. The SmartArrays size member should be updated accordingly. If index exceeds the SmartArrays size, nothing is removed from the array. Returns: 1 if an element was successfully removed from the array, 0 otherwise (including the case where the smarty pointer is NULL).

int getSize(SmartArray *smarty); Description: This function returns the number of elements currently in the array. We provide this function to discourage the programmer from accessing smartysize directly. That way, if we decide to change the name or meaning of the size variable in our SmartArray struct, the programmers who download the latest version of our code can get it working right out of the box; they dont have to go through their own code and change all instances of smartysize to something else, as long as we provide them with a getSize() function that works. Returns: Number of elements currently in the array, or -1 if the smarty pointer is NULL.

void printSmartArray(SmartArray *smarty); Description: Print all strings currently in the array. Output: Print all strings currently in the array. Print a newline character, , after each string. If the SmartArray pointer is NULL, or if the array is empty, simply print (empty array) (without quotes), followed by a newline character, .

===================================================================================

SmartArray.h

================

#ifndef __SMART_ARRAY_H

#define __SMART_ARRAY_H

// Default capacity for new SmartArrays

#define DEFAULT_INIT_LEN 10

typedef struct SmartArray

{

// We will store an array of strings (i.e., an array of char arrays)

char **array;

// Size of array (i.e., number of elements that have been added to the array)

int size;

// Length of the array (i.e., the array's current maximum capacity)

int capacity;

} SmartArray;

// Functional Prototypes

SmartArray *createSmartArray(int length);

SmartArray *destroySmartArray(SmartArray *smarty);

SmartArray *expandSmartArray(SmartArray *smarty, int length);

SmartArray *trimSmartArray(SmartArray *smarty);

char *put(SmartArray *smarty, char *str);

char *get(SmartArray *smarty, int index);

char *set(SmartArray *smarty, int index, char *str);

char *insertElement(SmartArray *smarty, int index, char *str);

int removeElement(SmartArray *smarty, int index);

int getSize(SmartArray *smarty);

void printSmartArray(SmartArray *smarty);

double difficultyRating(void);

double hoursSpent(void);

#endif

=====================================================================================

testcase01.c

==========================

// Sean Szumlanski

// COP 3502, Fall 2017

// ========================

// SmartArray: testcase01.c

// ========================

#include

#include

#include "SmartArray.h"

int main(void)

{

int i; char buffer[32];

SmartArray *smarty1 = createSmartArray(-1);

SmartArray *smarty2 = createSmartArray(-1);

FILE *ifp = fopen("names.txt", "rb");

// Read all names from the file and add them to smarty1.

while (fscanf(ifp, "%s", buffer) != EOF)

put(smarty1, buffer);

// Add the names to smarty2 in reverse order.

for (i = getSize(smarty1) - 1; i >= 0; i--)

put(smarty2, get(smarty1, i));

// Print the contents of smarty1.

printf(" -- SMART ARRAY 1: -- ");

printSmartArray(smarty1);

// Print the contents of smarty2.

printf(" -- SMART ARRAY 2 (First Names): -- ");

printSmartArray(smarty2);

// Swap last names with first names in smarty2.

for (i = 0; i < getSize(smarty2); i++)

{

if (strcmp(get(smarty2, i), "Daniel") == 0)

set(smarty2, i, "Mandragona");

else if (strcmp(get(smarty2, i), "Kristjan") == 0)

set(smarty2, i, "Arumae");

else if (strcmp(get(smarty2, i), "Karan") == 0)

set(smarty2, i, "Daei-Mojdehi");

else if (strcmp(get(smarty2, i), "Shahidul") == 0)

set(smarty2, i, "Islam");

else if (strcmp(get(smarty2, i), "Fereshteh") == 0)

set(smarty2, i, "Jafariakinabad");

else if (strcmp(get(smarty2, i), "Pierre") == 0)

set(smarty2, i, "LaBorde");

else if (strcmp(get(smarty2, i), "Rachael") == 0)

set(smarty2, i, "Sera");

else if (strcmp(get(smarty2, i), "Richie") == 0)

set(smarty2, i, "Wales");

}

// Print the contents of smarty2.

printf(" -- SMART ARRAY 2 (Last Names): -- ");

printSmartArray(smarty2);

// Print smarty1 (in reverse order) and smarty2, to match up first and last

// names.

printf(" -- COMBINED ARRAYS (First and Last Names): -- ");

for (i = 0; i < getSize(smarty2); i++)

printf("%s %s ", get(smarty1, getSize(smarty1) - 1 - i), get(smarty2, i));

// Add elements from smarty1 to the end of smarty1 (in reverse order).

printf(" ");

for (i = getSize(smarty1) - 1; i >= 0; i--)

printf("Adding %s to smarty1 ... ", put(smarty1, get(smarty1, i)));

// Print the contents of smarty1.

printf(" -- SMART ARRAY 1: -- ");

printSmartArray(smarty1);

// Insert a string at the beginning of array smarty1.

insertElement(smarty1, 0, "List of Names:");

// Print the contents of smarty1.

printf(" -- SMART ARRAY 1: -- ");

printSmartArray(smarty1);

// Remove all elements from smarty1.

while (getSize(smarty1))

removeElement(smarty1, 0);

// Print smarty1, which is now an empty array.

printf(" -- SMART ARRAY 1: -- ");

printSmartArray(smarty1);

// Destroy our smart arrays.

smarty1 = destroySmartArray(smarty1);

smarty2 = destroySmartArray(smarty2);

// Make sure smarty1 is good and destroyed (and that destroySmartArray

// doesn't segfault when passed a NULL pointer).

smarty1 = destroySmartArray(smarty1);

// Print the empty arrays one last time.

printf(" -- SMART ARRAY 1: -- ");

printSmartArray(smarty1);

printf(" -- SMART ARRAY 2: -- ");

printSmartArray(smarty2);

return 0;

}

=================================================================================

names.txt

===================

Karan Kristjan Shahidul Rachael Daniel Fereshteh Richie Pierre

====================================================================================

testcase01.c OUTPUT

===========================

-> Created new SmartArray of size 10. -> Created new SmartArray of size 10.

-- SMART ARRAY 1: -- Karan Kristjan Shahidul Rachael Daniel Fereshteh Richie Pierre

-- SMART ARRAY 2 (First Names): -- Pierre Richie Fereshteh Daniel Rachael Shahidul Kristjan Karan

-- SMART ARRAY 2 (Last Names): -- LaBorde Wales Jafariakinabad Mandragona Sera Islam Arumae Daei-Mojdehi

-- COMBINED ARRAYS (First and Last Names): -- Pierre LaBorde Richie Wales Fereshteh Jafariakinabad Daniel Mandragona Rachael Sera Shahidul Islam Kristjan Arumae Karan Daei-Mojdehi

Adding Pierre to smarty1 ... Adding Richie to smarty1 ... -> Expanded SmartArray to size 21. Adding Fereshteh to smarty1 ... Adding Daniel to smarty1 ... Adding Rachael to smarty1 ... Adding Shahidul to smarty1 ... Adding Kristjan to smarty1 ... Adding Karan to smarty1 ...

-- SMART ARRAY 1: -- Karan Kristjan Shahidul Rachael Daniel Fereshteh Richie Pierre Pierre Richie Fereshteh Daniel Rachael Shahidul Kristjan Karan

-- SMART ARRAY 1: -- List of Names: Karan Kristjan Shahidul Rachael Daniel Fereshteh Richie Pierre Pierre Richie Fereshteh Daniel Rachael Shahidul Kristjan Karan

-- SMART ARRAY 1: -- (empty array)

-- SMART ARRAY 1: -- (empty array)

-- SMART ARRAY 2: -- (empty array)

=====================================================================================

testcase02.c

=============================

// Sean Szumlanski

// COP 3502, Fall 2017

// ========================

// SmartArray: testcase02.c

// ========================

#include

#include "SmartArray.h"

int main(void)

{

SmartArray *smarty = createSmartArray(-1);

// Trim smart array. This should reduce its capacity to 0.

trimSmartArray(smarty);

// Trim again. This should produce no output since capacity is already 0.

trimSmartArray(smarty);

// Print the empty array.

printSmartArray(smarty);

printf("Size of array: %d ", getSize(smarty));

// Destroy smart array. Hopefully this won't segfault.

smarty = destroySmartArray(smarty);

// Print the empty array.

printSmartArray(smarty);

printf("Size of array: %d ", getSize(smarty));

// Since smarty has been destroyed and is now NULL, the put() function should

// return NULL

if (put(smarty, "Hello, world! ") == NULL)

printf("Awesome! ");

else

printf("Not so awesome! ");

// Create new array and add strings to the end. Print out the strings we're

// adding (to ensure put() is returning pointers to those strings).

printf("%s ", put(smarty = createSmartArray(-1), "Hello,"));

printf("%s ", put(smarty, "world!"));

// Print smarty again.

printf("SmartArray contents: ");

printSmartArray(smarty);

smarty = destroySmartArray(smarty);

return 0;

}

=================================================================================

testcase02.c OUTPUT

===============================

-> Created new SmartArray of size 10. -> Trimmed SmartArray to size 0. (empty array) Size of array: 0 (empty array) Size of array: -1 Awesome! -> Created new SmartArray of size 10. Hello, world! SmartArray contents: Hello, world!

==================================================================================