CSSE 120 -- Intro. to Software Development

Homework 27

Complete the assigned reading for the next session: Kochan: Pages 363-370 (File input and output)
IntArrays (a smarter "array" for C)

This is your C capstone project, and will count towards the "projects" category of your grade.

This project is due at the 11:59 PM on Friday of 10th week, but there are also milestones that are due at the beginning of Sessions 28 and 29:

You will earn 10 points for completing milestone 1 (through part h) by the start of Session 28 (no extension).

You will earn 10 points for completing milestone 2 (through part o) by the start of Session 29 (no extension).

You must do this assignment using Eclipse and the SmarterArrays project that you checked out from your individual SVN repository in class.

You should commit after completing each part, and include the letter of the part you completed in your commit message. This helps us award credit for each function you finish.

Overview: An IntArray is "smarter" than a normal C array. It is a start toward implementing something that behaves more like a Python list. In particular, an IntArray knows its size, can dynamically change its size, can disallow attempts to do something with an "element" whose index beyond its size, allows insertion into the middle, and automatically allocates more space when needed. It is your job to implement these (and some other) behaviors. A C array is not sufficient to keep track of everything we need to know, so we created a simple struct type that you will use. It has a member called size that you will use to keep track of the list's current size.
(239 points, in addition to the 20 milestone-completion points) You are to complete the definitions of all of the functions below. Stubs have been provided for you in main.c and IntArray.c. The IntArray.h file also contains specifications of each function in comments. Read them for more hints!

We've provided lots of test code in main.c. You can uncomment calls to various test functions as you go. The tests are written expecting that you will complete them in the order listed.
1. (3 points) In the source file main.c, edit the initial comment to include your name and today's date.
2. (20 points) Implement makeIntArray(), freeIntArray(), and printArray(). We will begin these together in class. Make sure these work for a range of sizes by running the included tests.
3. (10 points) Implement makeZeroedIntArray().
4. (20 points) Implement set()and get()functions for mutating and accessing IntArrays. For each, you need to check to see that the indices are in bounds (i.e., non-negative and smaller than the array size). Your functions should print an error and return TRUEif an out-of-bounds index is passed to the function, and return FALSEotherwise. If you overwrite memory that doesn't belong to your array, you will lose half credit. (Check this carefully, since the tests don't detect this.)
5. (25 points) Implement pascalsTriangle(). See the comments for details and expected output. In order for your code to pass the memory stress tests (next part), you can't store the entire triangle in memory. Your solution should use very little memory and free memory it no longer needs as it goes. Hint: to compute a row of Pascal's Triangle, you only need to use the previous row.
6. (10 points) Uncomment the call to stressTests. This runs your pascalsTriangle() function with larger and larger values, doubling in size each time. If your program has a memory leak, this stress test will detect it.
  
  Temporarily comment out pascalsTriangle's printArray(); otherwise your program will spend lots of time printing and it will take much longer to reach large memory sizes.
  
  In our tests, when we failed to free memory correctly in pascalsTriangle(), the program "died" at a stress test size of 40960, with the error message unable to allocate enough memory for array of size 22563. Without the memory leak, our program made it to a stress test size of over 2.6 million before we stopped it. (If you let it run to ~80,000, which took us about 30 seconds, you'll be sure that most leaks are fixed, although one bug we saw didn't surface until ~320,000! After this size, though, you can be very confident in your code.)
  
  Edit the appropriate comment in main(), indicating how large a stress test size your program reached.
7. (6 points) Reflection. On the next homework, we will extend the idea of SmarterArrays to create lists that have more of the capabilities of lists in Python. Think about how you might change our IntArray struct so we could create initially empty IntArrays and append to them. Don't change your code, but add a comment near the end of main()describing what you might do.
8. (0 points) Before submitting your final version, comment out the the call to memoryStressTests, to keep it from running. Also uncomment the call to printArray() so the grader can check the functionality of your functions. Commit your final version to your SVN repository.
9. (4 points) Edit the IntArraystruct to add an additional field, capacity. For our updated IntArray, the size field represents the number of items actually in the list, and the capacity represents how many items total the list could hold before we have to make it bigger. Question: with this additional field, should you malloc space for size or capacity integers? (This is an important question to answer, because if you do the wrong thing, you could malloc 0 bytes, which is a nasty bug that can be extremely difficult to track down!)
10. (4 points) Update makeIntArray()and makeZeroedIntArray()so that they set both the size and the capacity to the given size. Make sure all your previous functions, apart from the memory stress test, still work.
11. (6 points) Write functions
```
    int getCapacity(IntArray* a)
    
    int getSize(IntArray* a)
```
  that do what their names suggest.
12. (6 points) Write a function
```
    int* getHeapLocation(IntArray* a)
```
  that returns the address of the internal array field on the heap (not the IntArray struct, which is on the stack).
13. (10 points) Add a function
```
    IntArray makeEmptyIntArray()
```
  that takes no arguments and returns an empty (size is 0) IntArray with an initial capacity of 5.
14. (20 points) Add a function
```
    void resizeIntArray(IntArray *a, int newCapacity)
```
  It should change the capacity of the IntArray, but not its size. If newCapacity is smaller than the current size (not capacity) of the IntArray, this function should do nothing.
15. (20 points) Write a function
```
    void append(IntArray* a, int newElement) 
```
  to add the given element to the end of the given array. You will need to adjust the size. If the array has reached its capacity, use your resizeIntArray() function to double the array's capacity.
  Doubling gives us room for future growth. If we just grew by one, we would have to keep growing with every additional append, which is really inefficient.
16. (30 points) Add a function
```
       boolean insert(IntArray* a, int index, int value) 
```
  that works something like Python's insert method. That is, the given value should be inserted into the given array and all subsequent values in the array should be moved to the next higher index. For full credit, your program must resize (double capacity, as above) the array to make room for the additional element when that is necessary. The return value signifies whether there was an index out-of-bounds error. For full credit, your program must check for out-of-bounds indices and return TRUE if (and only if) so, refusing to do the insertion. (If you overwrite memory that doesn't belong to your array, you will lose half credit.) Add code to main() to test your new function.
  
  We illustrate "out of bounds" with some examples. Given an IntArray of size 4,
  - attempting to insert at index 3 is OK, because it will push the old element in index 3 back one.
  - attempting to insert at index 4 is OK, since it will do the equivalent of appending.
  - attempting to insert at index 5 is out of bounds, since there would be a gap between the old array and the new element inserted.
  - Inserting at index -1 is still bad, since C doesn't allow negative indices.
17. (25 points) Create a test function in main.c that will read a bunch of integers from the console and store them in an IntArray created using makeEmptyIntArray()and extending using append().
  
  You may assume that the user will enter non-negative numbers, thus allowing you to use a negative as a sentinel.
  
  After each integer is read, you should print the memory address of the internal array on the heap, its current size, its current capacity, and the integer contents of the array (on a single line).
  
  For example, a run might look like:
```
stored at 003D3D80, with size = 1 and capacity = 5, contents = [3]
stored at 003D3D80, with size = 2 and capacity = 5, contents = [3,7]
stored at 003D3D80, with size = 3 and capacity = 5, contents = [3,7,8]
stored at 003D3D80, with size = 4 and capacity = 5, contents = [3,7,8,2]
stored at 003D3D80, with size = 5 and capacity = 5, contents = [3,7,8,2,4]
stored at 003D5DF0, with size = 6 and capacity = 10, contents = [3,7,8,2,4,0]
stored at 003D5DF0, with size = 7 and capacity = 10, contents = [3,7,8,2,4,0,12]
stored at 003D5DF0, with size = 8 and capacity = 10, contents = [3,7,8,2,4,0,12,4]
stored at 003D5DF0, with size = 9 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4]
stored at 003D5DF0, with size = 10 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4,7]
stored at 003D5E20, with size = 11 and capacity = 20, contents = [3,7,8,2,4,0,12,4,4,7,9]
```
18. (20 points) Create another very similar function that reads integers from a file instead. Test it with the file ints.txt that is in your Eclipse project.
19. BONUS (20 points): Write a function
```
    char* toString(IntArray* a)
```
  that works like printIntArray(), but instead of printing, returns what would be printed as a string. Add code that uses your function to demonstrate that it works.
  
  To get bonus credit, you must pay attention to the memory allocation issues that we have discussed and that you have worked with during this assignment. Specifically, your code must work on small or large arrays, but must return a string that's exactly big enough to hold the whole array.