A First Draft of the CoordVector Class

We're not quite ready to dive into solving mazes just yet. When we do tackle that problem, we'll find that we need a way to represent a list of coordinates. (For example, the solution to a maze is a list of coordinates that you would follow to get from the start to the end.)

In practical code, you might just use std::vector<Coord> to represent such a list, as it is an array-like class that can grow and shrink as needed. But in CS 70, we don't just want to use data structures, we want to build them ourselves. So in this part of the assignment, you'll build your own version of a vector class that can hold Coord objects.

Starting Point: The CoordVector Interface

We're providing you with a complete header file (coordvector.hpp) to get started.

/**
 * \file coordvector.hpp
 * \author CS 70 Provided Code
 * \brief Declares the CoordVector class for managing an array of 2D coordinates
 *
 */

#ifndef COORDVECTOR_HPP_INCLUDED
#define COORDVECTOR_HPP_INCLUDED

#include "coord.hpp"
#include <utility>  // technicall unnecessary, but makes CPPLINT happy, :-P

/**
 * \class CoordVector
 * \brief A simple vector-like class for storing Coord objects
 * \details The CoordVector class provides a simple array-like structure for
 *          storing Coord objects. It supports basic operations such as adding
 *          and removing elements, accessing elements by index, and checking
 *          the size of the vector.
 * \note    This implementation uses a fixed-size array with a maximum capacity.
 *          It does not support dynamic resizing. (Yet!)
 */
class CoordVector {
 public:
    /**
     * \brief               Default constructor creates an empty vector
     */
    CoordVector();

    /**
     * \brief               Constructs a coord vector with an optional
     *                      initial number of default-constructed elements
     * \param initialSize   Number of elements to initially create.
     * \post                The vector is created with the specified number of
     *                      default-constructed Coord elements
     */
    explicit CoordVector(size_t initialSize);

    // Disable copy and assignment for simplicity
    CoordVector(const CoordVector&) = delete;
    CoordVector& operator=(const CoordVector&) = delete;

    /**
     * \brief               Returns the number of elements in the vector
     * \returns             Number of elements in the vector
     */
    size_t size() const;

    /**
     * \brief               Checks if the vector is empty
     * \returns             True if the vector is empty, false otherwise
     */
    bool isEmpty() const;

    /**
     * \brief               Adds a new element to the end of the vector
     * \param coord         The coordinate to add
     * \throws              An exception if the vector is full (for now!)
     */
    void pushBack(const Coord& coord);

    /**
     * \brief               Removes the last element from the vector
     * \throws              An exception if the vector is empty
     */
    void popBack();

    /**
     * \brief               Returns a const reference to the last element in the
     *                      vector
     * \returns             A const reference to the last element in the vector
     * \throws              An exception if the vector is empty
     */
    const Coord& back() const;

    /**
     * \brief               Returns a (mutable) reference to the element at the
     *                      specified index
     * \param index         The index of the element to access
     * \returns             A reference to the element at the specified index
     *                      that allows the element to be modified
     * \note                Allows Python-style negative indexing. This version
     *                      requires the target object to be non-const.
     * \throws              std::out_of_range if index is out of bounds
     */
    Coord& operator[](ptrdiff_t index);

    /**
     * \brief               Returns a (const) reference to the element at the
     *                      specified index
     * \param index         The index of the element to access
     * \returns             A constant reference to the element at the
     *                      specified index
     * \note                Allows Python-style negative indexing. This version
     *                      is for const objects.
     * \throws              std::out_of_range if index is out of bounds
     */
    const Coord& operator[](ptrdiff_t index) const;

    /**
     * \brief               Removes all elements from the vector
     */
    void clear();

 private:
    static constexpr size_t MAX_SIZE = 256;  // Arbitrary fixed maximum size
    Coord data_[MAX_SIZE];                   // The underlying array
    size_t size_;                            // Current number of elements

    // Helper to map user-provided index to physical array index
    size_t logicalToPhysical(ptrdiff_t index) const;
};

#endif  // COORDVECTOR_HPP_INCLUDED

Understanding the Interface

Before implementing anything, let's understand what this class provides:

• Storage: A fixed-size array of Coord objects (up to 256 elements).
• Size tracking: Keeps track of how many elements are actually in use.
• Stack-like operations: pushBack(), popBack(), and back().
• Array-like access: operator[] for accessing elements by index.
• Python-style indexing: Negative indices count from the end (-1 is the last element).

Notice that the copy constructor and assignment operator are disabled to keep things simpler for now—we don't need to worry about deep copying.

Your Task: Create the CoordVector Class

Step 1: Create the Header File

Create a new file called coordvector.hpp in your maze directory and paste the code given above into it. (You can just click the code snippet to copy it to your clipboard.)

Step 2: Create the Implementation File

Create a new file called coordvector.cpp and add the necessary includes:

#include "coordvector.hpp"
#include "coord.hpp"

#include <stdexcept>  // for std::out_of_range
#include <cstddef>    // for ptrdiff_t

Step 3: Implement the Constructors

The class has two constructors:

1. A constructor that takes an initial size.
2. A default constructor that creates an empty vector (equivalent to calling the first constructor with an initial size of 0).

The first constructor should

• Set size_ to the provided initial size.
• Throw an exception if the initial size exceeds MAX_SIZE.
  • Hint: The syntax for throwing an appropriate exception is throw std::length_error("Oh noes!"); — you can (and should) choose your own (better) error message.

Note that the array data_ will be default-initialized automatically with default-initialized Coord objects. (We don't care that some of them are unused; they just sit there doing nothing. The default constructor initializes them to (-1, -1), which will help detect if you somehow access a location you didn't store a value into.)

Also, remember that any initialization you do in C++ constructors should use a member-initialization list if you possibly can.

We could write the second constructor from scratch, but there is a better way! C++ supports constructor delegation, where one constructor can call another constructor in the same class. This technique is a great way to avoid duplicating code.

Here, we want the default constructor to just delegate to the first constructor with an initial size of 0. The syntax for delegation is that instead of listing member initializers after the colon, you write a single call to another constructor in the same class. Because this usage might be a bit unfamiliar, we'll just give you the code for the default constructor:

CoordVector::CoordVector() : CoordVector(0) {
    // Nothing else to do; we've delegated all the work to the other
    // constructor.
}

Step 4: Implement the Helper Function, logicalToPhysical()

Here's the key insight: many of our functions need to validate and convert indices. Rather than duplicate this logic everywhere, we use a helper function that takes a signed logical index (which can be negative just like in Python, with -1 meaning the last element) and converts it to an unsigned physical index (which is always non-negative).

Here's what this function needs to do:

• If the index is negative, add size_ to it to convert it to a positive index.
• Now that the index is non-negative, it's convenient to transfer the index value to a size_t variable for further checks (which avoids annoying compiler warnings about comparing signed and unsigned values).
• If the resulting value is out-of-bounds, throw an exception (i.e., throw std::out_of_range("Index out of range")). Remember that size_ is the number of valid elements, so valid indices are 0 through size_-1.
• Return the valid physical index.

Step 5: Implement the Remaining Functions

Now implement the rest of the member functions.

Here are some hints for each function:

size() and isEmpty()

These should be one-liners.

pushBack()

Check for overflow, increment size_, then add the element.

popBack()

Check for underflow, then decrement size_.

back()

Return the last element (hint: use logicalToPhysical(-1)).

operator[]

Use logicalToPhysical() to get the actual array index.

operator[] may seem like a very strange name for a function, but implementing it allows you to use the familiar square-bracket syntax (e.g., vec[0]).

There are two basically identical implementations here: one for const objects and one for non-const objects. Because we use logicalToPhysical(), the code should be a simple one-liner, so the code duplication isn't too bad.

clear()

Reset the size to 0.

Step 6: Update the Makefile

One of the existing files, solver.cpp is going to need to use your new CoordVector class. It has a #include "coordvector.hpp" line already, but it's commented out. Uncomment that line.

Add rules to compile coordvector.o and build coordvector-test:

coordvector.o: coordvector.cpp coordvector.hpp coord.hpp
        $(CXX) -c $(CXXFLAGS) coordvector.cpp

coordvector-test.o: coordvector-test.cpp coordvector.hpp coord.hpp
        $(CXX) -c $(CXXFLAGS) coordvector-test.cpp

coordvector-test: coordvector-test.o coordvector.o coord.o
        $(CXX) -o $@ $^ -ltestinglogger

Also, because you uncommented the #include "coordvector.hpp" line in solver.cpp, its dependencies have changed. You can work out what they are by hand or just run clang++ -MM solver.cpp to see what it says. Update the Makefile accordingly.

Finally, don't forget to add coordvector-test to your TARGETS variable!

Step 7: Test Your Implementation

Once everything compiles, run the tests:

make coordvector-test
./coordvector-test

The test file exercises all the member functions, including edge cases such as empty vectors and negative indexing. It should produce output similar to

CoordVector basics passed!
CoordVector pushBack loop passed!

All tests passed! Summary of affirmations:
----
Fails   / Total Issue
0       / 24    [CoordVector basics]
0       / 602   [CoordVector pushBack loop]

(Note that some tests are currently commented out; we'll enable them later.)

Step 8: Fix any Issues

If any tests fail, debug your implementation. Using print statements (i.e., std::cerr << ...) is probably the simplest way to figure out what's going wrong, but remember that valgrind can also help you find memory errors.

(When logged in, completion status appears here.)