Testing a Queue

In this exercise we will be testing a queue following the approache approach described in this article by Claessen and Hughes. The main idea is that we test that different operations on the class under test result in the same observable behaviour. To generate many cases for each test, we randomize the values used for each operation as well as the actions performed before and after these operations. In pseudo code, we test:

prefix = randomActions();
suffix = randomActions();

TestObject T1 = new TestObject();
TestObject T2 = new TestObject();

output1 = perform(T1, prefix) + perform(T1, command1) + perform(T1, suffix);
output2 = perform(T2, prefix) + perform(T2, command2) + perform(T2, suffix);

equals(T1, T2) && equals(output1, output2);

The output allows us to test methods that do not change the state of the class under test, such as get-methods. The testing framework handles most of this test, you mostly need to write the code that generates command1 and command2, i.e. the commands thats should be equivalent.

The Queue

• buffer -- an array containing the queue data.
• start -- the first element in the queue.
• size -- the current number of elements in the queue.

start:   2 ------\
buffer:  [ 0, 0, 4, 6, 8]
size:    3

start:   3 ---------\
buffer:  [ 0, 0, 4, 6, 8]
size:    2

start:   3 ---------\
buffer:  [ 2, 0, 4, 6, 8]
size:    3

start:   3 ---------\
buffer:  [ 2, 1, 0, 6, 8]
size:    5

• void add(int value) adds a value to the queue.
• void remove() removes the first value from the queue, if any.
• Integer front() returns the first value on the queue, null if the queue is empty.

1. Warm-up

Download the queue and testing framework here.

Implement the equals function for Queue such that two Queues are considered equal if they represent the same queue of values. For example, the following two queues should be considered equal:

== Queue 1                    == Queue 2
start:   3 ---------\         start:   2 ------\
buffer:  [ 2, 0, 4, 6, 8]     buffer:  [ 2, 5, 6, 8, 2, 5, 3, 5, 0, 0]
size:    3                    size:    3

Solution.

if (other.size != size)
  return false;

for (int i = 0; i < size; i++)
  if (other.buffer[(other.start + i) % other.buffer.length] !=
        buffer[(start + i) % buffer.length])
    return false;
return true;

2. Writing properties

If interested, you can have a look at QueueTestCase.java which implements the necessary interfaces for the testing framework. QueueAction.java specifies the actions one can perform on a queue, plus an action to force an output (i.e. to simulate the result of calling the front method).

The article by Claessen and Hughes identifies the following essential properties of a queue. That is, for each pair of command the resulting observation (both in terms of outputs as well as the queue state) should be equivalent.

Queue q = new Queue();      <==>      Queue q = new Queue();
output(q.front());                    output(null);

Queue q = new Queue();      <==>      Queue q = new Queue();
q.add(m);                             q.add(m);
output(q.front());                    output(m);

q.add(m);                   <==>      q.add(m);
q.add(n);                             output(q.frount());
output(q.front());                    q.add(n);

Queue q = new Queue();      <==>      Queue q = new Queue();
q.add(m);
q.remote();

q.add(m);                   <==>      q.add(m);
q.add(n);                             q.remove();
q.remote();                           q.add(n);

Implement these properties in the testing framework and fix what bugs you find.

Solution.

  public static final QueueTest testFrontEmpty = new QueueTest() {

    public String name() {
      return "frontEmpty";
    }

    public boolean withPrefix() {
      return false;
    }

    public void initialize(
        StatefulTestCase testCase) {
      QueueAction front = QueueAction.newFrontAction();
      QueueAction outFalse = QueueAction.newOutputAction(null);
      testCase.setCommands(new QueueAction[] { front },
          new QueueAction[] { outFalse });
    }
  };

  public static final QueueTest testFront = new QueueTest() {

    public String name() {
      return "front";
    }

    public boolean withPrefix() {
      return false;
    }

    public void initialize(
        StatefulTestCase testCase) {
      int value = rand.nextInt(10);
      QueueAction add = QueueAction.newAddAction(value);
      QueueAction front = QueueAction.newFrontAction();
      QueueAction out = QueueAction.newOutputAction(value);
      testCase.setCommands(new QueueAction[] { add, front },
          new QueueAction[] { add, out });
    }
  };

  public static final QueueTest testFrontAddTwo = new QueueTest() {

    public String name() {
      return "addTwo";
    }

    public void initialize(
        StatefulTestCase testCase) {
      int valueA = rand.nextInt(10);
      int valueB = rand.nextInt(10);
      QueueAction addA = QueueAction.newAddAction(valueA);
      QueueAction addB = QueueAction.newAddAction(valueB);
      QueueAction front = QueueAction.newFrontAction();
      testCase.setCommands(new QueueAction[] { addA, addB, front },
          new QueueAction[] { addA, front, addB });
    }
  };

  public static final QueueTest testRemove = new QueueTest() {

    public String name() {
      return "remove";
    }

    public boolean withPrefix() {
      return false;
    }

    public void initialize(
        StatefulTestCase testCase) {
      int value = rand.nextInt(10);
      QueueAction add = QueueAction.newAddAction(value);
      QueueAction remove = QueueAction.newRemoveAction();
      testCase.setCommands(new QueueAction[] { add, remove },
          new QueueAction[] {});
    }
  };

  public static final QueueTest testRemoveAddTwo = new QueueTest() {

    public String name() {
      return "removeAddTwo";
    }

    public boolean withPrefix() {
      return false;
    }

    public void initialize(
        StatefulTestCase testCase) {
      int valueA = rand.nextInt(10);
      int valueB = rand.nextInt(10);
      QueueAction addA = QueueAction.newAddAction(valueA);
      QueueAction addB = QueueAction.newAddAction(valueB);
      QueueAction remove = QueueAction.newRemoveAction();
      testCase.setCommands(new QueueAction[] { addA, addB, remove },
          new QueueAction[] { addA, remove, addB });
    }
  };

• front should return buffer[start].
• doubleArr does not copy the old elements correctly, it should be: newBuffer[i] = buffer[(start + i) % buffer.length];.
• add should increment the size after assigning the value.
• remove should update the start value as start = (start + 1) % buffer.length;.