Adding Queue Operations to CoordVector

We've seen that depth-first search (DFS) doesn't guarantee that we'll find the shortest path through a maze. To find the shortest possible path, we'll need to use BFS (breadth-first search), which explores all paths at the same rate. But BFS needs some different operations than DFS—in particular, it needs a queue instead of a stack.

Queue vs Stack Operations

A stack is LIFO (Last In, First Out):

• Add to the back with pushBack()
• Remove from the back with popBack()

A queue is FIFO (First In, First Out):

• Add to the back with pushBack()
• Remove from the front with popFront()

The Naive Approach (Don't Do This!)

The obvious way to implement popFront() would be to remove the first element and shift everything else down:

// DON'T DO THIS!
void CoordVector::popFront() {
    for (size_t i = 0; i < size_ - 1; ++i) {
        data_[i] = data_[i + 1];
    }
    --size_;
}

The Clever Solution: Circular Buffers

Instead of physically moving elements, we'll track where the logical “start” of our vector is. Imagine our array as a circle where we can wrap around:

When we popFront(), we just move the offset forward. When we pushFront(), we move it backward. No copying needed!

Your Task: Implement Queue Operations

Step 1: Update the Header

Add a new private member to coordvector.hpp:

size_t offset_ = 0;  // Where the logical start is in the physical array

Also add these public member-function declarations:

• pushFront(coord) — exactly like pushBack(), but at the front
• popFront() — exactly like popBack(), but at the front
• front() — exactly like back(), but at the front

The signatures of these functions are exactly like the back versions. In fact, it's probably easiest to just copy and paste the signatures and comment blocks for pushBack(), popBack(), and back() and modify them accordingly.

Step 2: Update Existing Functions

First, update the CoordVector(size_t initialSize) constructor to initialize offset_ to 0 in the member-initialization list.

Next, update swap() to include the new member by adding this line:

std::swap(offset_, other.offset_);

Step 3: Update logicalToPhysical()

This is the heart of the circular buffer. After your existing bounds checking, add code to apply the offset and wrap around. Specifically, you need to

1. Add offset_ to your computed physical index.
2. If the result is greater than or equal to capacity_, subtract capacity_ to wrap around.

Step 4: Implement the New Functions

Again, these functions are very similar to the back versions. The main difference is how we handle the offset_. The back versions don't change offset_ at all, whereas the front versions do.

pushFront():

• Check if we need to grow (should be the same code as pushBack())
• Decrement offset_ (but wrap to capacity_ - 1 if it's 0)
• Increment size_
• Store the element at logicalToPhysical(0)

popFront():

• Check for underflow and throw a std::out_of_range("your-message-here") exception if necessary
• Increment offset_ (wrap to 0 if it reaches capacity_)
• Decrement size_

front():

• Check if empty and throw an exception if necessary
• Return the element at logicalToPhysical(0)

Step 5: Check the Copy Constructor

Depending on how you wrote your copy constructor, you may not need to do anything at all. If it uses logicalToPhysical() directly or indirectly by calling your operator[] function, you should be good to go.

Step 6: Update and Run Tests

Add a Capacity Check to the Swap Test

As we mentioned earlier, an alarmingly common mistake when adding a new member variable is forgetting to update swap(). When we have this kind of bug, it causes a lot of head scratching and confusion until it's tracked down. So let's add a test for that issue in coordvector-test.cpp by updating test_swap().

You'll need to do something like

• Make two vectors of different sizes so that they have different capacities. Check that they have the capacities you expect.
• Call swap() on them.
• Check that their capacities have swapped.

The testing-library functions are documented in the help pages, but you can probably just figure it out by looking at the existing tests.

Enable the pushFront Test

Uncomment test_pushFrontLoop() and its call in main().

Rebuild and Run All Tests

Run all tests:

make coordvector-test
./coordvector-test

You should see output that looks like

CoordVector basics passed!
CoordVector swap passed!
CoordVector pushBack loop passed!
CoordVector reallocation passed!
CoordVector pushFront loop passed!

All tests passed! Summary of affirmations:
----
Fails   / Total Issue
0       / 24    [CoordVector basics]
0       / 5     [CoordVector swap]
0       / 602   [CoordVector pushBack loop]
0       / 801   [CoordVector reallocation]
0       / 5657  [CoordVector pushFront loop]

void debugPrint() const {
    size_t p_first = logicalToPhysical(0);
    size_t p_last = logicalToPhysical(size_ - 1);
    std::cerr << "offset=" << offset_ << ", size=" << size_
              << ", capacity=" << capacity_ << ", logical [0] at physical ["
              << p_first << "], logical [" << size_ - 1 << "] at physical ["
              << p_last << "]\n";
    for (size_t i = 0; i < capacity_; ++i) {
        if (i == p_first) {
            std::cerr << ">>";
        std::cerr << data_[i] << " ";
        if (i == p_last) {
            std::cerr << "<<";
        }
        std::cerr << " ";
    }
    std::cerr << "\n";
}

offset_ = (offset_ == 0) ? capacity_ - 1 : offset_ - 1;

(When logged in, completion status appears here.)