CSCI 362 — Lab 4

Stack and Queue: A Unit Testing Exercise

Due: June 12, 2019 @ 11:59PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab4-stack-and-queue.tar

Overview

std::stack and std::queue are useful container adapters in the C++ Standard Library. You are tasked with implementing the majority of these classes!

Additionally, I want you to gain exposure with writing tests in C++ using a nice unit testing library called Catch.

There are four deliverables:

  1. Implementation of Queue (Queue.hpp)
  2. Implementation of Stack (Stack.hpp)
  3. Unit tests for Queue (TestQueue.hpp)
  4. Unit tests for Stack (TestStack.hpp)

The first two deliverables are the only ones "autograded", but I am not giving you the autograder! Why? I want you to write you own tests! If you see my tests you might get some crazy ideas.

Required functions

template <typename T>
class Stack {
    reference       top();
    const_reference top() const;

    bool      empty() const;
    size_type size()  const;

    void push (value_type const&);
    void push (value_type&&);

    void pop();
};

template <typename T>
class Queue {
    reference       front();
    const_reference front() const;

    reference       back();
    const_reference back() const;

    bool      empty() const;
    size_type size()  const;

    void push (value_type const&);
    void push (value_type&&);

    void pop();
};

NOTE: only 16 points of the 75 will be autograded

Writing Unit Tests

Catch provides a pretty nice interface for writing tests. I give you a little bit of an example for starters. You are welcome to reference other autograders I've written as well. For this assignment, we will be adopting principles of behavior-driven development (BDD for short). When writing tests in a BDD-way, we always following the same pattern:

  1. Provide a [Scenario]
  2. Give/initialize a state [Given]
    • assert any necessary preconditions in this section
  3. Apply the operation to update the state [When]
    • do not do anything else!
  4. [Then] assert any postconditions/evolution in state
SCENARIO("This is what I'm testing", "[stack]") // or queue if testing queue
{
  GIVEN("A state")
  {
    Stack<int> s;
    // set the state of s to what you want

    REQUIRE (precondition1);
    REQUIRE (precondition2);
    ...
    REQUIRE (preconditionN);

    // Note: you may want to preserve information here

    WHEN("I apply an operation")
    {
      s.someCoolOperation();
      THEN("Everything should still work")
      {
        REQUIRE (postcondition1);
        REQUIRE (postcondition2);
        ...
        REQUIRE (postconditionN);
      }
    }
  }
}

YOU SHOULD UNIT TEST EVERY FUNCTION YOU WRITE

Additionally, you should make sure you handle different states (when the stack/queue is empty vs. when it's not).

Style

Use good programming style:

Submission

You can generate a tarfile that contains your four modified files (Stack.hpp, Queue.hpp, TestStack.hpp, and TestQueue.hpp) by stating:

make handin

or alternatively,

tar cvf handin.tar Stack.hpp Queue.hpp TestStack.hpp TestQueue.hpp

Please submit handin.tar to autolab

Grading

This lab is graded out of 75 points.