CircularArrayFixedSizeQueueTests.java

package edu.caltech.cs2.datastructures;

import edu.caltech.cs2.helpers.Inspection;
import edu.caltech.cs2.helpers.Reflection;
import edu.caltech.cs2.helpers.RuntimeInstrumentation;
import edu.caltech.cs2.interfaces.IFixedSizeQueueTests;
import edu.caltech.cs2.interfaces.IFixedSizeQueue;
import edu.caltech.cs2.interfaces.IQueue;
import org.junit.jupiter.api.*;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;
import org.junit.jupiter.params.provider.ValueSource;

import java.lang.reflect.Constructor;
import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;

import static edu.caltech.cs2.project03.Project03TestOrdering.*;
import static java.util.concurrent.TimeUnit.SECONDS;
import static org.junit.jupiter.api.Assertions.*;

@Tag("B")
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class CircularArrayFixedSizeQueueTests implements IFixedSizeQueueTests {
  private static String FIXED_QUEUE_SOURCE = "src/edu/caltech/cs2/datastructures/CircularArrayFixedSizeQueue.java";

  private Constructor circFixedSizeQueueConstructor = Reflection.getConstructor(CircularArrayFixedSizeQueue.class,
      int.class);
  private int DEFAULT_CAPACITY = 10;

  public IQueue<Object> newQueue() {
    return Reflection.newInstance(circFixedSizeQueueConstructor, DEFAULT_CAPACITY);
  }

  public IQueue<Object> newQueue(int capacity) {
    return Reflection.newInstance(circFixedSizeQueueConstructor, capacity);
  }

  public IFixedSizeQueue<Object> newFixedSizeQueue(int capacity) {
    return Reflection.newInstance(circFixedSizeQueueConstructor, capacity);
  }

  // FIXED QUEUE-SPECIFIC TESTS ----------------------------------------

  @Order(classSpecificTestLevel)
  @DisplayName("Does not use or import disallowed classes")
  @Test
  public void testForInvalidClasses() {
    List<String> regexps = List.of("java\\.util\\.(?!Iterator)", "java\\.lang\\.reflect", "java\\.io");
    Inspection.assertNoImportsOf(FIXED_QUEUE_SOURCE, regexps);
    Inspection.assertNoUsageOf(FIXED_QUEUE_SOURCE, regexps);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("There are no static fields")
  @Test
  public void testConstantFields() {
    Reflection.assertFieldsEqualTo(CircularArrayFixedSizeQueue.class, "static", 0);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("The overall number of fields is small")
  @Test
  public void testSmallNumberOfFields() {
    Reflection.assertFieldsLessThan(CircularArrayFixedSizeQueue.class, "private", 4);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("There are no public fields")
  @Test
  public void testNoPublicFields() {
    Reflection.assertNoPublicFields(CircularArrayFixedSizeQueue.class);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("There are no protected fields")
  @Test
  public void testNoProtectedFields() {
    Reflection.assertNoProtectedFields(CircularArrayFixedSizeQueue.class);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("All fields in CircularArrayFixedSizeQueue have modifiers")
  @Test
  public void testFieldModifiers() {
    Reflection.assertFieldModifiers(CircularArrayFixedSizeQueue.class);
  }

  @Order(classSpecificTestLevel)
  @DisplayName("The public interface is correct")
  @Test
  public void testPublicInterface() {
    Reflection.assertPublicInterface(CircularArrayFixedSizeQueue.class,
        List.of("enqueue", "dequeue", "peek", "iterator", "size", "isFull", "capacity", "toString"));
  }

  @Order(classSpecificTestLevel)
  @DisplayName("Uses this(...) notation in all but one constructor")
  @Test
  public void testForThisConstructors() {
    Inspection.assertConstructorHygiene(FIXED_QUEUE_SOURCE);
  }

  // TOSTRING TESTS ---------------------------------------------------

  @Order(toStringTestLevel)
  @DisplayName("toString is correctly overridden")
  @Test
  public void testToStringOverride() {
    Reflection.assertMethodCorrectlyOverridden(ArrayDeque.class, "toString");
  }

  @Order(toStringTestLevel)
  @DisplayName("toString() matches java.util.ArrayDeque")
  @ParameterizedTest(name = "Test toString() on [{arguments}]")
  @ValueSource(strings = { "0, 1, 2, 3", "5, 4, 3, 2, 1", "8, 3, 5, 7, 4, 3, 12, 12, 1" })
  public void testToString(String inputs) {
    java.util.ArrayDeque<String> reference = new java.util.ArrayDeque<String>();
    Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
    IFixedSizeQueue<String> me = Reflection.newInstance(c, inputs.length());
    for (String value : inputs.trim().split(", ")) {
      assertEquals(reference.toString(), me.toString(), "toString outputs should be the same");
      reference.addLast(value);
      me.enqueue(value);
    }
  }

  // TIME COMPLEXITY TESTS ------------------------------------------------

  @Order(complexityTestLevel)
  @DisplayName("enqueue() and dequeue() take constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test()
  public void testQueueOperationComplexity() {
    Function<Integer, IFixedSizeQueue<Integer>> provide = (Integer numElements) -> {
      Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
      IFixedSizeQueue<Integer> q = Reflection.newInstance(c, numElements * 2);
      for (int i = 0; i < numElements; i++) {
        q.enqueue(i);
      }
      return q;
    };
    Consumer<IFixedSizeQueue<Integer>> enqueue = (IFixedSizeQueue<Integer> q) -> q.enqueue(0);
    Consumer<IFixedSizeQueue<Integer>> dequeue = (IFixedSizeQueue<Integer> q) -> q.dequeue();

    RuntimeInstrumentation.assertAtMost("enqueue", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, enqueue, 8);
    RuntimeInstrumentation.assertAtMost("dequeue", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, dequeue, 8);
  }

  @Order(complexityTestLevel)
  @DisplayName("peek() takes constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test()
  public void testPeekComplexity() {
    Function<Integer, IFixedSizeQueue<Integer>> provide = (Integer numElements) -> {
      Constructor c = Reflection.getConstructor(CircularArrayFixedSizeQueue.class, int.class);
      IFixedSizeQueue<Integer> q = Reflection.newInstance(c, numElements * 2);
      for (int i = 0; i < numElements; i++) {
        q.enqueue(i);
      }
      return q;
    };
    Consumer<IFixedSizeQueue<Integer>> peek = (IFixedSizeQueue<Integer> q) -> q.peek();

    RuntimeInstrumentation.assertAtMost("peek", RuntimeInstrumentation.ComplexityType.CONSTANT, provide, peek, 8);
  }

  @Order(fixedSizeQueueLevel)
  @DisplayName("Test iterator matches reference for wraparound values")
  @ParameterizedTest(name = "Test iterator and wraparound behavior with {1} random values with seed = {0} and fixed array size = {2}")
  @CsvSource({ "69, 200, 20", "21, 300, 200" })
  public void testWrapAround(int seed, int numVals, int queueSize) {
    Random r = new Random(seed);
    IFixedSizeQueue<Object> me = newFixedSizeQueue(queueSize);
    Queue<Object> reference = new java.util.ArrayDeque<>();
    assertEquals(queueSize, me.capacity(), "capacity does not match expected value");
    for (int i = 0; i < queueSize; i++) {
      int num = r.nextInt();
      assertFalse(me.isFull(), "queue should not be full");
      assertTrue(me.enqueue(num), "enqueue should be successful");
      reference.add(num);

    }
    for (int i = 0; i < numVals; i++) {
      me.enqueue(me.dequeue());
      reference.add(reference.remove());
      assertEquals(reference.peek(), me.peek(), "return values of peek()s are not equal");
      assertEquals(reference.size(), me.size(), "size()s are not equal");
      assertEquals(queueSize, me.capacity(), "capacity of a fixed size queue should not change");
      assertIterableEquals(reference, me, "Reference and implemented queues are not equal");
    }
  }

}