package deferredvec;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

import java.io.IOException;
import java.lang.classfile.ClassFile;
import java.lang.classfile.Instruction;
import java.lang.classfile.Opcode;
import java.lang.classfile.instruction.InvokeInstruction;
import java.lang.ref.WeakReference;
import java.lang.reflect.AccessFlag;
import java.lang.reflect.Field;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;
import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.fail;

public final class DeferredVecTest {
  
  @Nested
  public class Q1 {
    
    @Test
    public void addSingleElement() {
      DeferredVec<String> vec = new DeferredVec<String>();
      vec.add("hello");

      assertEquals(1, vec.size());
      String element = vec.get(0);
      assertEquals("hello", element);
    }

    @Test
    public void addDifferentTypes() {
      DeferredVec<Integer> vec = new DeferredVec<Integer>();
      vec.add(42);
      vec.add(100);

      assertEquals(2, vec.size());
      assertEquals(42, vec.get(0));
      assertEquals(100, vec.get(1));
    }
    
    @Test
    public void addMultipleElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");

      assertEquals(3, vec.size());
      assertEquals("first", vec.get(0));
      assertEquals("second", vec.get(1));
      assertEquals("third", vec.get(2));
    }

    @Test
    public void addNoElement() {
      var vec = new DeferredVec<String>();
      assertEquals(0, vec.size());
    }
    
    @Test
    public void addUpToInitialCapacity() {
      var vec = new DeferredVec<String>();
      for (var i = 0; i < 8; i++) {
        vec.add("element" + i);
      }

      assertEquals(8, vec.size());
      for (var i = 0; i < 8; i++) {
        assertEquals("element" + i, vec.get(i));
      }
    }
    
    @Test
    public void sizeIncreasesAfterEachAdd() {
      var vec = new DeferredVec<String>();
      assertEquals(0, vec.size());
      vec.add("a");
      assertEquals(1, vec.size());
      vec.add("b");
      assertEquals(2, vec.size());
      vec.add("c");
      assertEquals(3, vec.size());
    }

    @Test
    public void addNullElementThrowsNPE() {
      var vec = new DeferredVec<String>();
      assertThrows(NullPointerException.class, () -> vec.add(null));
    }

    @Test
    public void getEmptyOutOfRangeThrowsIndexOutOfBoundsException() {
      var vec = new DeferredVec<>();
      assertAll(
          () -> assertThrows(IndexOutOfBoundsException.class, () -> vec.get(0)),
          () -> assertThrows(IndexOutOfBoundsException.class, () -> vec.get(-1))
      );
    }

    @Test
    public void getMultipleElementsOutOfRangeThrowsIndexOutOfBoundsException() {
      var vec = new DeferredVec<>();
      vec.add("a");
      vec.add(77);

      assertAll(
          () -> assertThrows(IndexOutOfBoundsException.class, () -> vec.get(2)),
          () -> assertThrows(IndexOutOfBoundsException.class, () -> vec.get(-1))
      );
    }

    @Test
    public void classIsPublicAndFinal() {
      var flags = DeferredVec.class.accessFlags();
      assertAll(
          () -> assertTrue(flags.contains(AccessFlag.PUBLIC)),
          () -> assertTrue(flags.contains(AccessFlag.FINAL))
      );
    }

    @Test
    public void classOnlyOnePublicConstructor() {
      var constructors = DeferredVec.class.getConstructors();
      assertEquals(1, constructors.length);
    }

    @Test
    public void classFieldsArePrivate() {
      var fields = DeferredVec.class.getDeclaredFields();
      for(var field : fields) {
        assertTrue(field.accessFlags().contains(AccessFlag.PRIVATE));
      }
    }

    @Test
    public void classNoFieldStoreACollection() {
      var fields = DeferredVec.class.getDeclaredFields();
      for(var field : fields) {
        assertFalse(Collection.class.isAssignableFrom(field.getType()));
      }
    }

    @Test
    public void classConstructorsCallSuperAsLastInstruction() throws IOException {
      var className = "/" + DeferredVec.class.getName().replace('.', '/') + ".class";
      byte[] data;
      try (var input = DeferredVec.class.getResourceAsStream(className)) {
        data = input.readAllBytes();
      }
      var classModel = ClassFile.of().parse(data);
      var constructors =
          classModel.methods().stream().filter(m -> m.methodName().equalsString("<init>")).toList();
      for (var constructor : constructors) {
        var code =
            constructor.code().orElseThrow(() -> new AssertionError("Constructor has no code"));
        var instructions =
            code.elementStream()
                .flatMap(e -> e instanceof Instruction instruction ? Stream.of(instruction) : null)
                .toList();
        var lastInstruction =
            instructions.get(instructions.size() - 2); // -2 because last is RETURN
        if (!(lastInstruction instanceof InvokeInstruction invokeInstruction)) {
          throw new AssertionError(
              "lastInstruction is neither super() nor this() " + lastInstruction);
        }
        assertAll(
            () -> assertEquals(Opcode.INVOKESPECIAL, invokeInstruction.opcode()),
            () -> assertEquals("<init>", invokeInstruction.name().stringValue())
        );
      }
    }
  }


  @Nested
  public class Q2 {

    @Test
    public void addExactlyAtCapacityBoundary() {
      var vec = new DeferredVec<String>();
      for (var i = 0; i < 8; i++) {
        vec.add("element" + i);
      }

      assertEquals(8, vec.size());
      vec.add("ninth");
      assertEquals(9, vec.size());
      assertEquals("ninth", vec.get(8));
    }

    @Test
    public void addBeyondInitialCapacityResizesArray() {
      var vec = new DeferredVec<String>();
      for (var i = 0; i < 10; i++) {
        vec.add("element" + i);
      }

      assertEquals(10, vec.size());
      for (var i = 0; i < 10; i++) {
        assertEquals("element" + i, vec.get(i));
      }
    }

    @Test
    public void addManyElementsTriggersMultipleResizes() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }

      assertEquals(1_000_000, vec.size());
      for (var i = 0; i < 1_000_000; i++) {
        assertEquals(i, vec.get(i));
      }
    }

    @Test
    public void resizingPreservesAllExistingElements() {
      var vec = new DeferredVec<String>();
      for (var i = 0; i < 8; i++) {
        vec.add("old" + i);
      }
      vec.add("new0");
      vec.add("new1");
      vec.add("new2");

      assertEquals(11, vec.size());
      for (var i = 0; i < 8; i++) {
        assertEquals("old" + i, vec.get(i));
      }
      assertEquals("new0", vec.get(8));
      assertEquals("new1", vec.get(9));
      assertEquals("new2", vec.get(10));
    }
  }


  @Nested
  public class Q3 {

    @Test
    public void removeValidElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      var removed = vec.remove(1);

      assertEquals("second", removed);
      assertEquals(3, vec.size());
    }

    @Test
    public void getAfterRemoveThrowsIllegalStateException() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.remove(1);

      assertThrows(IllegalStateException.class, () -> vec.get(1));
    }

    @Test
    public void removeAlreadyRemovedElementThrowsIllegalStateException() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.remove(1);

      assertThrows(IllegalStateException.class, () -> vec.remove(1));
    }

    @Test
    public void getNonRemovedElementsStillWorks() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(1);

      assertEquals("first", vec.get(0));
      assertEquals("third", vec.get(2));
    }

    @Test
    public void removeMultipleElements() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(0);
      vec.remove(2);

      assertEquals(4, vec.size());
      assertThrows(IllegalStateException.class, () -> vec.get(0));
      assertEquals("b", vec.get(1));
      assertThrows(IllegalStateException.class, () -> vec.get(2));
      assertEquals("d", vec.get(3));
    }

    @Test
    public void removeFirstElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      var removed = vec.remove(0);

      assertEquals("first", removed);
      assertThrows(IllegalStateException.class, () -> vec.get(0));
      assertEquals("second", vec.get(1));
    }

    @Test
    public void removeLastElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      var removed = vec.remove(1);

      assertEquals("second", removed);
      assertEquals("first", vec.get(0));
      assertThrows(IllegalStateException.class, () -> vec.get(1));
    }

    @Test
    public void sizeDoesNotChangeAfterRemove() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      assertEquals(3, vec.size());
      vec.remove(1);
      assertEquals(3, vec.size());
      vec.remove(0);
      assertEquals(3, vec.size());
    }

    @Test
    public void testUndoWithNoRemoves() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.undo();

      assertEquals("first", vec.get(0));
      assertEquals("second", vec.get(1));
    }

    @Test
    public void testUndoOnEmptyVec() {
      var vec = new DeferredVec<String>();
      vec.undo();

      assertEquals(0, vec.size());
    }

    @Test
    public void testUndoAfterSingleRemove() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(1);

      assertThrows(IllegalStateException.class, () -> vec.get(1));

      vec.undo();

      assertEquals("second", vec.get(1));
    }

    @Test
    public void testUndoAfterMultipleRemoves() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.add("fourth");
      vec.remove(0);
      vec.remove(2);
      vec.remove(3);

      assertThrows(IllegalStateException.class, () -> vec.get(0));
      assertThrows(IllegalStateException.class, () -> vec.get(2));
      assertThrows(IllegalStateException.class, () -> vec.get(3));

      vec.undo();

      assertEquals("first", vec.get(0));
      assertEquals("second", vec.get(1));
      assertEquals("third", vec.get(2));
      assertEquals("fourth", vec.get(3));
    }

    @Test
    public void testUndoALargeDataset() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec.add(i);
        vec.remove(i);
      }

      assertTimeoutPreemptively(Duration.ofSeconds(1), vec::undo);

      for (var i = 0; i < 1_000_000; i++) {
        assertEquals(i, vec.get(i));
      }
    }

    @Test
    public void testUndoThenRemoveAgain() {
      var vec = new DeferredVec<Integer>();
      vec.add(10);
      vec.add(20);
      vec.add(30);
      vec.remove(1);
      vec.undo();

      assertEquals(20, vec.get(1));

      vec.remove(1);

      assertThrows(IllegalStateException.class, () -> vec.get(1));
    }

    @Test
    public void testMultipleUndoCalls() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.remove(0);
      vec.undo();
      vec.undo();

      assertEquals("first", vec.get(0));
    }

    @Test
    public void removeInvalidIndexThrowsIndexOutOfBoundsException() {
      var vec = new DeferredVec<>();
      assertThrows(IndexOutOfBoundsException.class, () -> vec.remove(1));
    }

    @Test
    public void removeNegativeIndexThrowsIndexOutOfBoundsException() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      assertThrows(IndexOutOfBoundsException.class, () -> vec.remove(-1));
    }
  }


  @Nested
  public class Q4 {

    @Test
    public void compactWithOneRemovedElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(1);
      vec.compact();

      assertEquals(2, vec.size());
      assertEquals("first", vec.get(0));
      assertEquals("third", vec.get(1));
    }

    @Test
    public void compactWithMultipleRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.remove(1);
      vec.remove(3);
      vec.compact();

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
      assertEquals("e", vec.get(2));
    }

    @Test
    public void compactRemovesFirstElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(0);
      vec.compact();

      assertEquals(2, vec.size());
      assertEquals("second", vec.get(0));
      assertEquals("third", vec.get(1));
    }

    @Test
    public void compactRemovesLastElement() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(2);
      vec.compact();

      assertEquals(2, vec.size());
      assertEquals("first", vec.get(0));
      assertEquals("second", vec.get(1));
    }

    @Test
    public void compactWithNoRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.compact();

      assertEquals(3, vec.size());
      assertEquals("first", vec.get(0));
      assertEquals("second", vec.get(1));
      assertEquals("third", vec.get(2));
    }

    @Test
    public void compactAllowsAccessToPreviouslyRemovedIndices() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(1);
      vec.compact();
      vec.add("d");

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
      assertEquals("d", vec.get(2));
    }

    @Test
    public void compactWithAllElementsRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(0);
      vec.remove(1);
      vec.remove(2);
      vec.compact();

      assertEquals(0, vec.size());
    }

    @Test
    public void compactOnEmptyVec() {
      var vec = new DeferredVec<String>();
      vec.compact();
      assertEquals(0, vec.size());
    }

    @Test
    public void compactMultipleTimes() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(1);
      vec.compact();

      assertEquals(2, vec.size());
      vec.compact();

      assertEquals(2, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
    }

    @Test
    public void compactThenRemoveAndCompactAgain() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(1);
      vec.compact();

      assertEquals(3, vec.size());
      vec.remove(1);
      vec.compact();

      assertEquals(2, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("d", vec.get(1));
    }

    @Test
    public void compactPreservesOrder() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 10; i++) {
        vec.add(i);
      }
      vec.remove(2);
      vec.remove(5);
      vec.remove(8);
      vec.compact();

      assertEquals(7, vec.size());
      assertEquals(0, vec.get(0));
      assertEquals(1, vec.get(1));
      assertEquals(3, vec.get(2));
      assertEquals(4, vec.get(3));
      assertEquals(6, vec.get(4));
      assertEquals(7, vec.get(5));
      assertEquals(9, vec.get(6));
    }

    @Test
    public void compactWithALargeDataset() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }
      for (var i = 0; i < 1_000_000; i += 2) {
        vec.remove(i);
      }

      assertTimeoutPreemptively(Duration.ofSeconds(1), () -> vec.compact());

      assertEquals(500_000, vec.size());
      for (var i = 0; i < 500_000; i ++) {
        assertEquals(i * 2 + 1, vec.get(i));
      }
    }

    @Test
    public void compactWithALargeDatasetRemoveAll() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }
      for (var i = 0; i < 1_000_000; i ++) {
        vec.remove(i);
      }

      assertTimeoutPreemptively(Duration.ofSeconds(1), () -> vec.compact());

      assertEquals(0, vec.size());
    }

    @Test
    public void compactHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(bob);
      vec.remove(0);
      vec.compact();
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }

    @Test
    public void compactRemoveLastHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(new Person("Ana", 42));
      vec.add(new Person("Jim", 22));
      vec.add(bob);
      vec.remove(2);
      vec.compact();
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }

    @Test
    public void compactRemoveFirstHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(bob);
      vec.add(new Person("Ana", 42));
      vec.add(new Person("Jim", 22));
      vec.remove(0);
      vec.compact();
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }
  }


  @Nested
  public class Q5 {

    @Test
    public void eachStateWithAllNonRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");

      var elements = new ArrayList<String>();
      var removedStates = new ArrayList<Boolean>();
      vec.eachState((element, removed) -> {
        elements.add(element);
        removedStates.add(removed);
      });
      assertEquals(List.of("first", "second", "third"), elements);
      assertEquals(List.of(false, false, false), removedStates);
    }

    @Test
    public void eachStateWithSomeRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.add("fourth");
      vec.remove(1);
      vec.remove(3);

      var elements = new ArrayList<String>();
      var removedStates = new ArrayList<Boolean>();
      vec.eachState((element, removed) -> {
        elements.add(element);
        removedStates.add(removed);
      });
      assertEquals(List.of("first", "second", "third", "fourth"), elements);
      assertEquals(List.of(false, true, false, true), removedStates);
    }

    @Test
    public void eachStateWithAllRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.remove(0);
      vec.remove(1);

      var box = new Object() { int removedCount; };
      vec.eachState((element, removed) -> {
        if (removed) box.removedCount++;
      });
      assertEquals(2, box.removedCount);
    }

    @Test
    public void eachStateAfterUndo() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");

      vec.remove(1);
      vec.undo();

      var elements = new ArrayList<String>();
      var removedStates = new ArrayList<Boolean>();
      vec.eachState((element, removed) -> {
        elements.add(element);
        removedStates.add(removed);
      });
      assertEquals(List.of("first", "second", "third"), elements);
      assertEquals(List.of(false, false, false), removedStates);
    }

    @Test
    public void eachStateWithNoElements() {
      var vec = new DeferredVec<String>();
      vec.eachState((_, _) -> fail());
    }

    @Test
    public void eachStateVisitsElementsInOrder() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 5; i++) {
        vec.add(i);
      }

      var visited = new ArrayList<Integer>();
      vec.eachState((element, removed) -> {
        visited.add(element);
        if (removed) {
          fail("removed");
        }
      });
      assertEquals(List.of(0, 1, 2, 3, 4), visited);
    }

    @Test
    public void eachStateAfterCompact() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(1);
      vec.compact();

      var elements = new ArrayList<String>();
      var removedStates = new ArrayList<Boolean>();
      vec.eachState((element, removed) -> {
        elements.add(element);
        removedStates.add(removed);
      });
      assertEquals(List.of("a", "c"), elements);
      assertEquals(List.of(false, false), removedStates);
    }

    @Test
    public void eachStateCanCountElements() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(1);

      var totalBox = new Object() { int totalCount; };
      var removedBox = new Object() { int removedCount; };
      var activeBox = new Object() { int activeCount; };
      vec.eachState((_, removed) -> {
        totalBox.totalCount++;
        if (removed) {
          removedBox.removedCount++;
        } else {
          activeBox.activeCount++;
        }
      });
      assertEquals(3, totalBox.totalCount);
      assertEquals(1, removedBox.removedCount);
      assertEquals(2, activeBox.activeCount);
    }

    @Test
    public void eachStateWithMixedRemovals() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.remove(0);
      vec.remove(2);
      vec.remove(4);

      var result = new StringBuilder();
      vec.eachState((element, removed) -> {
        result.append(element).append(removed ? "R" : "-").append(",");
      });
      assertEquals("aR,b-,cR,d-,eR,", result.toString());
    }

    @Test
    public void eachStateCanBuildNewCollection() {
      var vec = new DeferredVec<Integer>();
      vec.add(10);
      vec.add(20);
      vec.add(30);
      vec.remove(1);

      var activeElements = new ArrayList<Integer>();
      vec.eachState((element, removed) -> {
        if (!removed) {
          activeElements.add(element);
        }
      });
      assertEquals(List.of(10, 30), activeElements);
    }

    @Test
    public void eachStateCountNoRemoveFastEnough() {
      var vec = new DeferredVec<Integer>();
      for(var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }

      var box = new Object() { int counter; };
      assertTimeoutPreemptively(Duration.ofSeconds(1), () -> {
        vec.eachState((_, removed) -> {
          if (!removed) {
            box.counter++;
          }
        });
      });
      assertEquals(1_000_000, box.counter);
    }

    @Test
    public void eachStateCountAllRemovedFastEnough() {
      var vec = new DeferredVec<Integer>();
      for(var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }
      for(var i = 0; i < 1_000_000; i++) {
        vec.remove(i);
      }

      var box = new Object() { int counter; };
      assertTimeoutPreemptively(Duration.ofSeconds(1), () -> {
        vec.eachState((_, removed) -> {
          if (!removed) {
            box.counter++;
          }
        });
      });
      assertEquals(0, box.counter);
    }

    @Test
    public void eachStateCountRemoveHalfFastEnough() {
      var vec = new DeferredVec<Integer>();
      for(var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }
      for(var i = 0; i < 1_000_000; i++) {
        if (i % 2 == 0) {
          vec.remove(i);
        }
      }

      var box = new Object() { int counter; };
      assertTimeoutPreemptively(Duration.ofSeconds(1), () -> {
        vec.eachState((_, removed) -> {
          if (!removed) {
            box.counter++;
          }
        });
      });
      assertEquals(500_000, box.counter);
    }

    @Test
    public void eachStateNullActionThrowsNPE() {
      var vec = new DeferredVec<String>();
      vec.add("test");
      assertThrows(NullPointerException.class, () -> vec.eachState(null));
    }
  }


  @Nested
  public class Q6 {

    @Test
    public void loopOverAllElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");

      var result = new ArrayList<String>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of("first", "second", "third"), result);
    }
    
    @Test
    public void loopSkipsRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.add("fourth");
      vec.remove(1);
      vec.remove(2);

      var result = new ArrayList<String>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of("first", "fourth"), result);
    }

    @Test
    public void loopSkipsConsecutiveRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.remove(1);
      vec.remove(2);
      vec.remove(3);

      var result = new ArrayList<String>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of("a", "e"), result);
    }

    @Test
    public void loopAfterCompact() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(1);
      vec.compact();

      var result = new ArrayList<String>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of("first", "third"), result);
    }

    @Test
    public void loopAfterUndo() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(1);
      vec.undo();

      var result = new ArrayList<String>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of("first", "second", "third"), result);
    }
    
    @Test
    public void iteratorHasNextWithAllElementsRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.remove(0);
      vec.remove(1);

      var iterator = vec.iterator();
      assertFalse(iterator.hasNext());
      assertFalse(iterator.hasNext());
      assertFalse(iterator.hasNext());
    }

    @Test
    public void iteratorOnEmptyVec() {
      var vec = new DeferredVec<String>();
      var iterator = vec.iterator();
      assertFalse(iterator.hasNext());
    }

    @Test
    public void iteratorRemoveAfterNext() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");

      var iterator = vec.iterator();
      assertEquals("first", iterator.next());
      var element = iterator.next();
      assertEquals("second", element);
      iterator.remove();
      assertThrows(IllegalStateException.class, () -> vec.get(1));
    }

    @Test
    public void iteratorRemoveWithoutNextThrowsIllegalStateException() {
      var vec = new DeferredVec<String>();
      vec.add("first");

      var iterator = vec.iterator();
      assertThrows(IllegalStateException.class, iterator::remove);
    }

    @Test
    public void iteratorRemoveTwiceThrowsIllegalStateException() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");

      var iterator = vec.iterator();
      assertEquals("first", iterator.next());
      iterator.remove();
      assertThrows(IllegalStateException.class, iterator::remove);
    }

    @Test
    public void iteratorRemoveAndContinue() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");

      var iterator = vec.iterator();
      assertEquals("a", iterator.next());
      assertEquals("b", iterator.next());
      iterator.remove();

      var result = new ArrayList<String>();
      iterator.forEachRemaining(result::add);
      assertEquals(List.of("c", "d"), result);
    }

    @Test
    public void iteratorSkipsInitialRemovedElements() {
      var vec = new DeferredVec<String>();
      vec.add("first");
      vec.add("second");
      vec.add("third");
      vec.remove(0);

      var iterator = vec.iterator();
      assertTrue(iterator.hasNext());
      assertTrue(iterator.hasNext());
      assertTrue(iterator.hasNext());
      assertEquals("second", iterator.next());
    }

    @Test
    public void multipleIteratorsIndependent() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");

      var iter1 = vec.iterator();
      var iter2 = vec.iterator();
      assertEquals("a", iter1.next());
      assertEquals("a", iter2.next());
      assertEquals("b", iter1.next());
      assertEquals("b", iter2.next());
    }

    @Test
    public void iteratorRemoveMultipleElements() {
      var vec = new DeferredVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);
      vec.add(4);
      vec.add(5);

      var iterator = vec.iterator();
      while (iterator.hasNext()) {
        var value = iterator.next();
        if (value % 2 == 0) {
          iterator.remove();
        }
      }

      var result = new ArrayList<>();
      for (var element : vec) {
        result.add(element);
      }
      assertEquals(List.of(1, 3, 5), result);
    }

    @Test
    public void iteratorHasNextShouldNotDoSideEffect() {
      class FieldDumper {
        static Map<String, Object> stateMap(Object object) {
          return Arrays.stream(object.getClass().getDeclaredFields())
              .collect(Collectors.toMap(Field::getName, field -> {
                field.setAccessible(true);
                try {
                  return field.get(object);
                } catch (IllegalAccessException e) {
                  throw new IllegalStateException(e);
                }
              }));
        }
      }

      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.remove(0);

      var  iterator = vec.iterator();
      var stateMap1 = FieldDumper.stateMap(iterator);
      iterator.hasNext();
      var stateMap2 = FieldDumper.stateMap(iterator);

      assertEquals(stateMap1, stateMap2);
    }

    @Test
    public void iteratorNextOnEmptyThrowsNoSuchElementException() {
      var vec = new DeferredVec<String>();
      var iterator = vec.iterator();
      assertThrows(NoSuchElementException.class, iterator::next);
    }

    @Test
    public void iteratorNextBeyondEndThrowsNoSuchElementException() {
      var vec = new DeferredVec<String>();
      vec.add("only");

      var iterator = vec.iterator();
      assertEquals("only", iterator.next());
      assertThrows(NoSuchElementException.class, iterator::next);
    }

    @Test
    public void iteratorNextAllElementRemovedThrowsNoSuchElementException() {
      var vec = new DeferredVec<String>();
      vec.add("only");
      vec.remove(0);

      var iterator = vec.iterator();
      assertThrows(NoSuchElementException.class, iterator::next);
    }
  }


  @Nested
  public class Q7 {
    @Test
    public void compactRangeEmpty() {
      var vec = new DeferredVec<String>();
      vec.compact(0, 0);

      assertEquals(0, vec.size());
    }

    @Test
    public void compactRangeNoRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.compact(0, 2);

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("b", vec.get(1));
      assertEquals("c", vec.get(2));
    }

    @Test
    public void compactRangeWithRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(1);
      vec.compact(0, 3);

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
      assertEquals("d", vec.get(2));
    }

    @Test
    public void compactRangeMiddle() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.remove(2);
      vec.compact(1, 4);

      assertEquals(4, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("b", vec.get(1));
      assertEquals("d", vec.get(2));
      assertEquals("e", vec.get(3));
    }

    @Test
    public void compactRangeAllRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(1);
      vec.remove(2);
      vec.compact(1, 3);

      assertEquals(2, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("d", vec.get(1));
    }

    @Test

    public void compactRangeRemovedElementAtTheRightOfTheRange() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.add("f");

      vec.remove(1);
      vec.remove(4);
      vec.compact(0, 3);


      assertEquals(5, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
      assertEquals("d", vec.get(2));
      assertThrows(IllegalStateException.class, () -> vec.get(3));
      assertEquals("f", vec.get(4));
    }

    @Test
    public void compactRangeFromEqualsTo() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.compact(1, 1);

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("b", vec.get(1));
      assertEquals("c", vec.get(2));
    }

    @Test
    public void compactRangeEntireList() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(1);
      vec.compact(0, 3);

      assertEquals(2, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("c", vec.get(1));
    }

    @Test
    public void compactRangeAtEnd() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(2);
      vec.compact(2, 4);

      assertEquals(3, vec.size());
      assertEquals("a", vec.get(0));
      assertEquals("b", vec.get(1));
      assertEquals("d", vec.get(2));
    }

    @Test
    public void compactRangeHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(bob);
      vec.remove(0);
      vec.compact(0, 1);
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }

    @Test
    public void compactRangeRemoveLastHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(new Person("Ana", 42));
      vec.add(new Person("Jim", 22));
      vec.add(bob);
      vec.remove(2);
      vec.compact(2, 3);
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }

    @Test
    public void compactRangeRemoveFirstHasNoMemoryLeaks() {
      record Person(String name, int age) {}

      var bob = new Person("Bob", 30);
      var ref = new WeakReference<>(bob);

      var vec = new DeferredVec<Person>();
      vec.add(bob);
      vec.add(new Person("Ana", 42));
      vec.add(new Person("Jim", 22));
      vec.remove(0);
      vec.compact(0, 2);
      bob = null;

      System.gc();
      assertTrue(ref.refersTo(null));
    }

    @Test
    public void compactRangeInvalidFromNegative() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      assertThrows(IndexOutOfBoundsException.class, () -> vec.compact(-1, 1));
    }

    @Test
    public void compactRangeInvalidToGreaterThanSize() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      assertThrows(IndexOutOfBoundsException.class, () -> vec.compact(0, 2));
    }

    @Test
    public void compactRangeInvalidFromGreaterThanTo() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      assertThrows(IndexOutOfBoundsException.class, () -> vec.compact(2, 1));
    }
  }


  @Nested
  public class Q8 {
    @Test
    public void streamEmpty() {
      var vec = new DeferredVec<String>();
      var list = vec.stream().toList();
      assertTrue(list.isEmpty());
    }

    @Test
    public void streamNoRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");

      var list = vec.stream().toList();
      assertEquals(List.of("a", "b", "c"), list);
    }

    @Test
    public void streamNoRemovedCountIsKnown() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);

      var count = vec.stream().map(_ -> fail()).count();
      assertEquals(3L, count);
    }

    @Test
    public void streamWithRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(1);
      vec.remove(2);

      var list = vec.stream().toList();
      assertEquals(List.of("a", "d"), list);
    }

    @Test
    public void streamWithRemovedCount() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);
      vec.remove(1);

      var count = vec.stream().count();
      assertEquals(2L, count);
    }

    @Test
    public void streamAfterCompact() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);
      vec.remove(1);
      vec.compact();

      var list = vec.stream().toList();
      assertEquals(List.of(12, 51), list);
    }

    @Test
    public void streamAfterUndo() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);
      vec.remove(1);
      vec.undo();

      var list = vec.stream().toList();
      assertEquals(List.of(12, 25, 51), list);
    }

    @Test
    public void streamAllRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.remove(0);
      vec.remove(1);

      var list = vec.stream().toList();
      assertEquals(0, list.size());
    }

    @Test
    public void streamOperations() {
      var vec = new DeferredVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);
      vec.add(4);
      vec.remove(1);

      var sum = vec.stream().mapToInt(x -> x).sum();
      assertEquals(8, sum);
    }

    @Test
    public void streamFilter() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("ab");
      vec.add("abc");
      vec.add("abcd");
      vec.remove(0);

      var list = vec.stream().filter(s -> s.length() > 2).toList();
      assertEquals(List.of("abc", "abcd"), list);
    }

    @Test
    public void streamFindFirst() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(0);

      var first = vec.stream().findFirst().orElseThrow();
      assertEquals("b", first);
    }

    @Test
    public void streamSpliteratorCharacteristicsIsNonNull() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.remove(1);

      assertTrue(vec.stream().spliterator().hasCharacteristics(Spliterator.NONNULL));
    }
  }


  @Nested
  public class Q9 {
    @Test
    public void parallelStreamEmpty() {
      var vec = new DeferredVec<String>();
      var list = vec.stream().parallel().toList();
      assertTrue(list.isEmpty());
    }

    @Test
    public void parallelStreamNoRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");

      var set = vec.stream().parallel().toList();
      assertEquals(List.of("a", "b", "c", "d"), set);
    }

    @Test
    public void parallelStreamWithRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.add("e");
      vec.remove(1);
      vec.remove(3);

      var set = vec.stream().parallel().toList();
      assertEquals(List.of("a", "c", "e"), set);
    }

    @Test
    public void parallelStreamAllRemoved() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.remove(0);
      vec.remove(1);
      vec.remove(2);

      var list = vec.stream().parallel().toList();
      assertTrue(list.isEmpty());
    }

    @Test
    public void parallelStreamAfterCompact() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);
      vec.remove(1);
      vec.compact();

      var list = vec.stream().parallel().toList();
      assertEquals(List.of(12, 51), list);
    }

    @Test
    public void parallelStreamAfterUndo() {
      var vec = new DeferredVec<Integer>();
      vec.add(12);
      vec.add(25);
      vec.add(51);
      vec.remove(1);
      vec.undo();

      var list = vec.stream().parallel().toList();
      assertEquals(List.of(12, 25, 51), list);
    }

    @Test
    public void parallelStreamOperations() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 100; i++) {
        vec.add(i);
      }
      for (var i = 10; i < 20; i++) {
        vec.remove(i);
      }

      var sum = vec.stream().parallel().mapToInt(x -> x).sum();
      var expected = IntStream.range(0, 10).sum() + IntStream.range(20, 100).sum();
      assertEquals(expected, sum);
    }

    @Test
    public void parallelStreamReduce() {
      var vec = new DeferredVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);
      vec.add(4);
      vec.add(5);
      vec.remove(2);

      var result = vec.stream().parallel().reduce(0, Integer::sum);
      assertEquals(12, result);
    }

    @Test
    public void parallelStreamLargeDataset() {
      var vec = new DeferredVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec.add(i);
      }
      for (var i = 0; i < 1_000_000; i += 2) {
        vec.remove(i);
      }

      var count = vec.stream().parallel().count();
      assertEquals(500_000, count);
    }

    @Test
    public void parallelStreamCollectToList() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.add("c");
      vec.add("d");
      vec.remove(1);

      var list = vec.stream().parallel().sorted().toList();
      assertEquals(List.of("a", "c", "d"), list);
    }

    @Test
    public void parallelStreamSpliteratorCharacteristicsIsNonNull() {
      var vec = new DeferredVec<String>();
      vec.add("a");
      vec.add("b");
      vec.remove(1);

      assertTrue(vec.stream().parallel().spliterator().hasCharacteristics(Spliterator.NONNULL));
    }
  }
}