Assignment 1: A Dynamic String Array¶

In this assignment your task is to implement, and test, a set of functions that implement a dynamic array of strings.

Getting Started¶

For this assignment, put all the code you write into a single file named a1.cpp. that starts like this:

// a1.cpp

/////////////////////////////////////////////////////////////////////////
//
// Student Info
// ------------
//
// Name : <put your full name here!>
// St.# : <put your full SFU student number here>
// Email: <put your SFU email address here>
//
//
// Statement of Originality
// ------------------------
//
// All the code and comments below are my own original work. For any non-
// original work, I have provided citations in the comments with enough
// detail so that someone can see the exact source and extent of the
// borrowed work.
//
// In addition, I have not shared this work with anyone else, and I have
// not seen solutions from other students, tutors, websites, books,
// etc.
//
/////////////////////////////////////////////////////////////////////////

#include "a1.h"
#include "cmpt_error.h"
#include <iostream>      // no other #includes are allowed
#include <fstream>       // for this assignment
#include <string>
#include <cassert>

using namespace std;

//
// ... write your functions here ...
//

//
// ... put your test functions here (one test function for each
//     function above) ...
//

int main() {
  cout << "Assignment 1!\n";

  //
  // ... call your test functions here ...
  //
}

The header file a1.h is already written and contains this:

// a1.h

//
// Don't modify this file in any way!!
//

#include <string>

using namespace std;

struct str_array {
    string* arr;    // pointer to the underlying array
    int size;       // # of elements from user's perspective
    int capacity;   // length of underlying array
};

Don’t change a1.h in any way! When the marker tests your code, they will supply a copy of this a1.h.

Don’t add any other #include statements you need to your a1.cpp.

You can add any helper functions you think might be useful (as long as you write them yourself).

Test all your functions carefully to make sure they work correctly and efficiently.

Questions¶

Write a function that makes a brand new empty str_array of size 0 and capacity cap. It should have this header:
```
str_array make_empty(int cap = 10)
```
For example, calling make_empty(50) returns a new str_array of size 0 and capacity 50, and calling make_empty() returns a new str_array object of size 0 and capacity 10.
To avoid memory leaks, programmers must remember to always call deallocate when they are finished using a str_array:
```
void deallocate(str_array& arr)
```
deallocate(arr) calls delete[] on the underlying array, and also sets the array pointer to nullptr. Setting the array pointer to nullptr prevents memory corruption in cases when deallocate is called more than once on the same array.

Be sure to run your test code with valgrind to make sure it has no memory leaks or errors!
Implement this function:
```
// Returns the percentage of the array that is in use.
double pct_used(const str_array& arr)
```
This returns the size of the array divided by its capacity. For example, if arrs size is 5 and its capacity is 15, pct_used(arr) should return 0.333333.
Implement this function:
```
// convert arr's underlying array to a string
string to_str(const str_array& arr)
```
The string returned by to_str(arr) begins with a [ and ends with ], and all the strings in it begin and end with ". Also, the strings are separated by “, “.

For example, if arr represents an array with the strings "owl", "bug", and "cow", then to_str(arr) returns this string:
```
["owl", "bug", "cow"]
```
If arr.size is 0, then "[]" is returned. If arr.size == 1, then there’s only one string in it (and no commas).

Important: Make sure the string returned by to_str follows exactly this format.

Note that to_str only prints the first size elements of the underlying array.

After you’ve implemented to_str, use it to (easily!) implement these two functions:
```
// prints to_str(arr) to cout
void print(const str_array& arr)

// same as print, but also prints '\n' at the end
void println(const str_array& arr)
```
Implement get(arr, i), which returns the string at index location i of the underlying array:
```
string get(const str_array& arr, int i)
```
get should check the bounds of i, i.e. if i < 0 or i >= arr.size, then call cmpt::error to stop the program with a helpful error message.

Next, implement the set(arr, i, s) function, which assigns string s to location i of the underlying array:
```
void set(str_array& arr, int i, const string& s)
```
As with set, check the bounds of i, i.e. if i < 0 or i >= arr.size, then call cmpt::error to stop the program with a helpful error message.
The add_right function adds a new element to the right end of arr, re-sizing it if necessary:
```
void add_right(str_array& arr, const string& s)
```
If arr.size < arr.cap, then add_right should simply increment arr.size and put s at the first unused location at the right end of arr.

Otherwise, if arr.size >= arr.cap, then first re-size the underlying array to be twice the capacity. Then add s to the end of the array as in the previous case.
Implement the following function to test if two str_arrays are equal:
```
bool operator==(str_array a, str_array b)
```
a and b are considered equal if they have the same size, and contain the same strings in the same order.
Implement this function:
```
void clear(str_array& arr)
```
After calling clear(arr), the size of arr is 0. The underlying array doesn’t need to be changed.
Implement the add_left function:
```
void add_left(str_array& arr, const string& s)
```
It works just like add_right from above, but s is added at the left end, i.e as the first element of the array (and all the other elements are moved right one position).

For example, if arr is ["up", "down", "mouse"], then after calling add_left(arr, "cat") arr will be ["cat", up", "down", "mouse"].
Sometimes you might want to get rid of unused space in a dynamic array, and so implement this function:
```
// make the size and capacity of arr the same; if arr.size is 0,
// new capacity is set to 1; does nothing if arr.size is already
// equal to  arr.capacity
void shrink_to_fit(str_array& arr)
```
shrink_to_fit(arr) will, if possible, re-size the underlying array as described. The values in arr should be the same (and in the same order) after calling shrink_to_fit as before.
Removed! This question has been removed from the assignment since the answer was accidentally provided. The question is still given below in case you want to use make_fromFile for testing your other functions.

Implement the following make function that reads all the strings from a file:
```
str_array make_fromFile(const string& fname) {
    ifstream fin(fname);
    str_array result = make_empty();
    string s;
    while (fin >> s) add_right(result, s);
    return result;
}
```
fname is the name of a text file, and make_fromFile reads all the strings, in the same order they occur in the file, into a new str_array. To read the strings use a loop that repeatedly calls fin >> s, where fin is an fstream object and s is the string read in.

For example, suppose the text file test.txt contains this:
```
main() is the 1st "function"
C++ calls?!
```
Then, suppose you run this code:
```
str_array arr = make_fromFile("test.txt");
cout << arr.size << " words added\n";
println(arr);
```
Then make_fromFile("text.txt") returns a new str_array with these strings:
```
7 words added
["main()", "is", "the", "1st", ""function"", "C++", "calls?!"]
```
Notice the order of the words is the same as in the file.

Submit Your Work¶

Please put all your code into a single file named a1.cpp, and submit it on Canvas. Make sure to use exactly the same function headers for all the questions, otherwise the marking software will probably give you 0!

Do not submit a1.h, cmpt_error.h, or any other files. Copies of a1.h and cmpt_error.h will be in the same folder as your .cpp file.

Basic Requirements¶

Before we give your program any marks, it must meet the following basic requirements:

It must compile on Ubuntu Linux using the standard course makefile:
```
$ make a1
g++  -std=c++14 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g   a1.cpp   -o a1
```
If your program fails to compile, your mark for this assignment will be 0.

The standard course file cmpt_error.h will be in the same folder as a1.cpp when it’s compiled, so your program can use cmpt::error if necessary.
It must have no memory leaks, according to valgrind, e.g.:
```
$ valgrind ./a1

// ... lots of output ...
```
A program is considered to have no memory leaks if:
- In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.
- The ERROR SUMMARY must report 0 errors.
- It is usually okay if still reachable reports a non- zero number of bytes.
You must include the large comment section with student info and the statement of originality. If your submitted file does not have this, then we will assume your work is not original and it will not be marked.

If your program meets all these basic requirements, then it will graded using the marking scheme on Canvas.

Table Of Contents

Previous topic

Next topic

Assignment 1: A Dynamic String Array¶

Getting Started¶

Questions¶

Submit Your Work¶

Basic Requirements¶