COS 371: Programming Languages

Spring 2020

hw8: Vector

Due: Friday, 03/13 at 22:00

This is a pair programming assignment. If you are on a team, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. Make sure your sound volume is audible, but not so loud to disturb the people around you.

1. Goals

To implement an array-backed list that grows as necessary.

2. Introduction

Lists are amazing. We can build our entire Scheme interpreter using a linked list as our only data structure. (This may or may not be the best idea.) Here, we will get a little C practice by working on a different data structure, the vector. A vector is like an array, but can grow larger as needed. (This functionality exists in many languages, such as Python's list and Java's ArrayList.) C has no such built-in vector capability, though it does have fixed-size arrays. Under the hood, our vector is implemented as an array with some room for slack (unused slots). When we use up the slack and try to insert again, the vector will double the size of its internal array and copy over the old values.

3. Instructions

Read and follow the C style and grading guidelines linked from the course website.
We'll again be using Git and GitHub for this assignment. Look for a repository named username1-username2-vector, with you and your partner's usernames substituted. (If you are working individually, look for a repository named username-vector.) Clone it. Download the following files:
- vector.h
- vector.c
- tester.c
Add them to your repository (and commit, push, etc.).
Your task is to add to the file vector.c, which should contain the implementations for all of the functions prototyped in vector.h. Make sure to read the comments in vector.h carefully and follow all of the instructions.
Implement the functions prototyped in vector.h.
As you start, you need to make the tester more limited. (And my tester doesn't even test set!) So start by modifying the tester code so that you can develop and test your code incrementally (as always). For example, you can set the initial size high enough to test add before implementing the array resizing feature.
To compile, run:
```
clang vector.c tester.c -o tester
```
to create an executable file called tester, which you can then run:
```
./tester
```
We will be using Clang to test your code, so you should do the same. Make sure that you do not have any compiler errors or warnings under Clang. (Warnings are often a sign that you have a bug, anyway!)
Your code should have no memory leaks or memory errors. We will (and therefore you should also) test your code using Valgrind, an open source tool that is available for Linux. (It is somewhat less reliably for Macs, so you will want to run this on Linux. Valgrind is not available on Windows. Similar tools do exist for Windows, but they tend to be quite expensive.)
To use Valgrind, first compile your code with debugging info enabled:
```
clang -g vector.c tester.c -o tester
```
Then run your executable through Valgrind as follows:
```
valgrind --leak-check=full ./tester
```
You should see reports for every leaked block of memory, including file and line information for when the allocation happened. When you submit, your code should not produce memory errors.

4. Optional Challenges

Add a function to sort a Vector using, say, merge sort.
Make the Vector auto-shrink when it becomes less than half full.

5. Submission

Follow the instructions from the previous homework set. That is:

Create a file called credits.txt declaring "We didn't get any help" or listing anyone who helped you with the assignment (including lab assistants and classmates), and any websites, books or other sources you used for reference. Also briefly describe how you were helped. Please be thorough.
Add, commit, and push regularly.
When you are done, double check to make sure you have committed the version you want graded; tag and push the tag:
```
git tag hw8
git push --tags
```
(Recall that a normal git push does not push tags. Be sure to check on GitHub to make sure that it received your final submission.)

Assignment written by Dave Musicant, with some updates and improvements by Laura Effinger-Dean, David Liben-Nowell, and Jed Yang.

Start early, have fun, and discuss questions on Moodle.