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:

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.

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!)

If our arrays end up having wasted space (i.e., they arent full), we can trim them down to size.

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:

automatically expanding the smart arrays capacity when it gets full;

adding new elements into arbitrary positions in the smart array, or at the end of the smart array;

providing safe access to elements at specific positions in the smart array;

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);

... and more!

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. We realize this is completely 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 SmartArray.c with our SmartArray.h and testcase01.c) in Sections 4 and 5 (Compilation and Testing).

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. 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" 

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.

You should not modify SmartArray.h in any way, and you should not send SmartArray.h when you submit your assignment. We will use our own unmodified copy of SmartArray.h when compiling your program.

If you write auxiliary functions in SmartArray.c (which is strongly encouraged!), you should not add those functional prototypes to SmartArray.h. Just put those functional prototypes at the top of your SmartArray.c.

Think of SmartArray.h as a public interface to the SmartArray data structure. It contains only the functions that the end user (i.e., the programmer (re-)using your code) should call in order to create and use a SmartArray. You do not want the end user to call your auxiliary functions directly, so you do not put those functional prototypes in SmartArray.h. That way, the end user doesnt need to worry about all your auxiliary functions in order to use an SmartArray; everything just works. (And you dont have to worry about the end user mucking everything up by accidentally calling auxiliary functions that he or she shouldnt be messing around with!)

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

{

} SmartArray; 

char **array; int size; int capacity;

// pointer to array of strings // number of elements in array // length of array (maximum capacity) 

The SmartArray struct contains a double char pointer that can be used to set up a 2D char array (which is just an array of char arrays, otherwise known as an array of strings). array will have to be allocated dynamically at runtime. It will probably be the bane of your existence for the next week or so.

The struct also has size and capacity variables, which store the number of elements in the array (initially zero) and the current length (i.e., maximum capacity) of the array, respectively.

3. FunctionRequirements

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.

(Continued from previous page...) 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, .

double difficultyRating(void); 

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); 

Returns: An estimate (greater than zero) of the number of hours you spent on this assignment.