LinkedDequeTests.java

package edu.caltech.cs2.datastructures;

import edu.caltech.cs2.helpers.Inspection;
import edu.caltech.cs2.helpers.NodeChecker;
import edu.caltech.cs2.helpers.Reflection;
import edu.caltech.cs2.helpers.RuntimeInstrumentation;
import edu.caltech.cs2.interfaces.*;
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.ArrayDeque;
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.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNull;

@Tag("C")
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class LinkedDequeTests implements IDequeTests, IStackTests, IQueueTests {
  private static String LINKED_DEQUE_SOURCE = "src/edu/caltech/cs2/datastructures/LinkedDeque.java";

  private Constructor linkedDequeConstructor = Reflection.getConstructor(LinkedDeque.class);

  public ICollection<Object> newCollection() {
    return Reflection.newInstance(linkedDequeConstructor);
  }

  public IDeque<Object> newDeque() {
    return Reflection.newInstance(linkedDequeConstructor);
  }

  public IStack<Object> newStack() {
    return Reflection.newInstance(linkedDequeConstructor);
  }

  public IQueue<Object> newQueue() {
    return Reflection.newInstance(linkedDequeConstructor);
  }

  public IQueue<Object> newQueue(int size) {
    return newQueue();
  }

  // LINKEDDEQUE-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(LINKED_DEQUE_SOURCE, regexps);
    Inspection.assertNoUsageOf(LINKED_DEQUE_SOURCE, regexps);
  }

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

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

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

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

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

  @Order(classSpecificTestLevel)
  @DisplayName("The public interface is correct")
  @Test
  public void testPublicInterface() {
    Reflection.assertPublicInterface(LinkedDeque.class, List.of("addFront", "addBack", "removeFront", "removeBack",
        "enqueue", "dequeue", "push", "pop", "peek", "peekFront", "peekBack", "iterator", "size", "toString"));
  }

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

  @Order(classSpecificTestLevel)
  @DisplayName("Check that LinkedDeque uses a node class")
  @Test
  public void testLinkedNode() {
    Class[] classes = LinkedDeque.class.getDeclaredClasses();
    for (Class clazz : classes) {
      if (Iterator.class.isAssignableFrom(clazz)) {
        continue;
      }
      NodeChecker.isNode(clazz, true);
    }
  }

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

  @Order(toStringTestLevel)
  @DisplayName("toString is correctly overridden")
  @Test
  public void testToStringOverride() {
    Reflection.assertMethodCorrectlyOverridden(LinkedDeque.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>();
    LinkedDeque<String> me = new LinkedDeque<>();
    for (String value : inputs.trim().split(", ")) {
      assertEquals(reference.toString(), me.toString(), "toString outputs should be the same");
      reference.addLast(value);
      me.addBack(value);
    }
  }

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

  @Order(complexityTestLevel)
  @DisplayName("addFront() and removeFront() take constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testFrontDequeOperationComplexity() {
    Function<Integer, IDeque<Integer>> provide = (Integer numElements) -> {
      IDeque<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.addFront(i);
      }
      return q;
    };
    Consumer<IDeque<Integer>> addFront = (IDeque<Integer> q) -> q.addFront(0);
    Consumer<IDeque<Integer>> removeFront = (IDeque<Integer> q) -> q.removeFront();

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

  @Order(complexityTestLevel)
  @DisplayName("addBack() and removeBack() take constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testBackDequeOperationComplexity() {
    Function<Integer, IDeque<Integer>> provide = (Integer numElements) -> {
      IDeque<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.addBack(i);
      }
      return q;
    };
    Consumer<IDeque<Integer>> addBack = (IDeque<Integer> q) -> q.addBack(0);
    Consumer<IDeque<Integer>> removeBack = (IDeque<Integer> q) -> q.removeBack();

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

  @Order(complexityTestLevel)
  @DisplayName("enqueue() and dequeue() take constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testQueueOperationComplexity() {
    Function<Integer, IQueue<Integer>> provide = (Integer numElements) -> {
      IQueue<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.enqueue(i);
      }
      return q;
    };
    Consumer<IQueue<Integer>> enqueue = (IQueue<Integer> q) -> q.enqueue(0);
    Consumer<IQueue<Integer>> dequeue = (IQueue<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("push() and pop() take constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testStackOperationComplexity() {
    Function<Integer, IStack<Integer>> provide = (Integer numElements) -> {
      IStack<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.push(i);
      }
      return q;
    };
    Consumer<IStack<Integer>> push = (IStack<Integer> q) -> q.push(0);
    Consumer<IStack<Integer>> pop = (IStack<Integer> q) -> q.pop();

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

  @Order(complexityTestLevel)
  @DisplayName("peek() takes constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testPeekComplexity() {
    Function<Integer, IStack<Integer>> provide = (Integer numElements) -> {
      IStack<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.push(i);
      }
      return q;
    };
    Consumer<IStack<Integer>> peek = (IStack<Integer> q) -> q.peek();

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

  @Order(complexityTestLevel)
  @DisplayName("peekFront() takes constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testPeekFrontComplexity() {
    Function<Integer, IDeque<Integer>> provide = (Integer numElements) -> {
      IDeque<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.addFront(i);
      }
      return q;
    };
    Consumer<IDeque<Integer>> peekFront = (IDeque<Integer> q) -> q.peekFront();

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

  @Order(complexityTestLevel)
  @DisplayName("peekBack() takes constant time")
  @Timeout(value = 10, unit = SECONDS)
  @Test
  public void testPeekBackComplexity() {
    Function<Integer, IDeque<Integer>> provide = (Integer numElements) -> {
      IDeque<Integer> q = new LinkedDeque<>();
      for (int i = 0; i < numElements; i++) {
        q.addBack(i);
      }
      return q;
    };
    Consumer<IDeque<Integer>> peekBack = (IDeque<Integer> q) -> q.peekBack();

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

  // "LINKED-NESS" TESTS ------------------------------------------------

  @Order(dequeTestLevel)
  @DisplayName("Cycle detection for addFront(...), addBack(...), removeFront(...), and removeBack(...)")
  @ParameterizedTest(name = "Test cycles - {1} random numbers with seed = {0}")
  @CsvSource({ "69, 2000", "20, 3000" })
  public void checkForCycles(int seed, int size) {
    Random r = new Random(seed);
    Deque<Object> reference = new ArrayDeque<>();
    IDeque<Object> impl = new LinkedDeque<>();
    // Test that first peek is null
    assertNull(impl.peekFront(), "empty peek should return null");
    // Randomly add / remove elements to the front / back
    for (int i = 0; i < size; i++) {
      int num = r.nextInt();
      if (num % 2 == 0) {
        reference.addLast(num);
        impl.addBack(num);
      } else {
        reference.addFirst(num);
        impl.addFront(num);
      }
      if (reference.size() > 1 && impl.size() > 1) {
        if (num % 5 == 0) {
          reference.removeFirst();
          impl.removeFront();
        } else if (num % 7 == 0) {
          reference.removeLast();
          impl.removeBack();
        }
      }
      // After each operation, check whether cycles have formed
      NodeChecker.cycleDetection(impl, true);
      // Sanity checks, though these aren't super necessary
      assertEquals(reference.size(), impl.size(), "size()s are not equal");
      assertEquals(reference.toString(), impl.toString(), "toStrings()s are not equal");
    }
  }

  @Order(dequeTestLevel)
  @DisplayName("Check reverses for addFront(...), addBack(...), removeFront(...), and removeBack(...)")
  @ParameterizedTest(name = "Test reverse - {1} random numbers with seed = {0}")
  @CsvSource({ "31, 2000", "64, 3000" })
  public void checkReverses(int seed, int size) {
    Random r = new Random(seed);
    Deque<Object> reference = new ArrayDeque<>();
    IDeque<Object> impl = new LinkedDeque<>();
    // Test that first peek is null
    assertNull(impl.peekFront(), "empty peek should return null");
    // Randomly add / remove elements to the front / back
    for (int i = 0; i < size; i++) {
      int num = r.nextInt();
      if (num % 2 == 0) {
        reference.addLast(num);
        impl.addBack(num);
      } else {
        reference.addFirst(num);
        impl.addFront(num);
      }
      if (reference.size() > 1 && impl.size() > 1) {
        if (num % 5 == 0) {
          reference.removeFirst();
          impl.removeFront();
        } else if (num % 7 == 0) {
          reference.removeLast();
          impl.removeBack();
        }
      }
      // Check that forwards and backwards iteration are sane
      NodeChecker.checkReverse(impl);
      assertEquals(reference.size(), impl.size(), "size()s are not equal");
      assertEquals(reference.toString(), impl.toString(), "toStrings()s are not equal");
    }
  }

}