package fr.uge.unorderedvec;

import static java.util.stream.Collectors.toSet;
import static org.junit.jupiter.api.Assertions.*;
import static org.junit.jupiter.api.Assumptions.assumeTrue;

import module java.base;

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

public final class UnorderedVecTest {
  @Nested
  public class Q1 {
    @Test
    public void addingIntoAVecOfString() {
      var vec = new UnorderedVec<String>();
      vec.add("foo");
      vec.add("bar");
      vec.add("foo");

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

    @Test
    public void addingIntoAVecOfInteger() {
      var vec = new UnorderedVec<Integer>();
      vec.add(10);
      vec.add(20);

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

    @Test
    public void addingIntoAVecOfPerson() {
      record Person(String name) {}

      var vec = new UnorderedVec<Person>();
      vec.add(new Person("Jane"));

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

    @Test
    public void emptyVec() {
      var vec = new UnorderedVec<>();
      assertEquals(0, vec.size());
    }

    @Test
    public void addNullThrowsNPE() {
      var vec = new UnorderedVec<String>();

      assertThrows(NullPointerException.class, () -> vec.add(null));
    }

    @Test
    public void addNullThrowsAndLeavesTheVecUnchanged() {
      var vec = new UnorderedVec<String>();
      vec.add("A");

      assertThrows(NullPointerException.class, () -> vec.add(null));

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

    @Test
    public void vecClassCanNotBeInherited() {
      assertTrue(UnorderedVec.class.accessFlags().contains(AccessFlag.FINAL));
    }

    @Test
    public void vecClassIsVisible() {
      assertTrue(UnorderedVec.class.accessFlags().contains(AccessFlag.PUBLIC));
    }

    @Test
    public void vecClassHasOneConstructor() {
      assertEquals(1, UnorderedVec.class.getDeclaredConstructors().length);
    }

    @Test
    public void vecClassImplementationDoNotUseAnyCollection() {
      assertTrue(Arrays.stream(UnorderedVec.class.getDeclaredFields())
          .noneMatch(f -> f.getType().getPackageName().startsWith("java.util")));
    }

    @Test
    public void vecClassConstructorCallSuperAsLastInstruction() throws IOException {
      var className = "/" + UnorderedVec.class.getName().replace('.', '/') + ".class";
      byte[] data;
      try (var input = UnorderedVec.class.getResourceAsStream(className)) {
        if (input == null) {
          throw new AssertionError("Could not read class file");
        }
        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); // 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 vecOfInteger() {
      var vec = new UnorderedVec<Integer>();
      vec.add(12);
      vec.add(12);
      vec.add(12);

      var count = 0;
      for (var value : vec) {
        assertEquals(12, value);
        count++;
      }
      assertEquals(3, count);
    }

    @Test
    public void vecOfElementSameOrder() {
      var vec = new UnorderedVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);

      var list = new ArrayList<Integer>();
      for (var value : vec) {
        list.add(value);
      }

      assertEquals(List.of(1, 2, 3), list);
    }

    @Test
    public void vecOfOneElement() {
      var vec = new UnorderedVec<String>();
      vec.add("one");

      for (var value : vec) {
        assertEquals("one", value);
      }
    }

    @Test
    public void emptyVecHasNoElement() {
      var vec = new UnorderedVec<String>();
      for (var value : vec) {
        fail("unexpected " + value);
      }
    }

    @Test
    public void iterationIsRepeatableAndOrdered() {
      var vec = new UnorderedVec<String>();
      for (var i = 0; i < 16; i++) {
        vec.add("Element" + i);
      }

      var list1 = new ArrayList<String>();
      for(var v1 : vec) {
        list1.add(v1);
      }
      var list2 = new ArrayList<String>();
      for(var v2 : vec) {
        list2.add(v2);
      }

      assertEquals(16, list1.size());
      assertEquals(16, list2.size());
      assertEquals(list1, list2);
    }

    @Test
    public void sumOfSeveralSizes() {
      var vec = new UnorderedVec<Integer>();
      for (var i = 1; i <= 16; i++) {
        vec.add(i);

        var sum = 0;
        for (var value : vec) {
          sum += value;
        }

        assertEquals(i * (i + 1) / 2, sum);
      }
    }


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

    @Test
    public void iteratorsAreIndependent() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      var it1 = vec.iterator();
      var it2 = vec.iterator();
      assertEquals("A", it1.next());
      assertEquals("B", it1.next());
      assertEquals("A", it2.next());
    }

    @Test
    public void hasNextIsIdempotent() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      var it = vec.iterator();
      assertTrue(it.hasNext());
      assertTrue(it.hasNext());
      assertEquals("A", it.next());
      assertEquals("B", it.next());
      assertFalse(it.hasNext());
      assertFalse(it.hasNext());
    }

    @Test
    public void nextOnExhaustedIteratorThrows() {
      var vec = new UnorderedVec<String>();
      vec.add("A");

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

    @Test
    public void sumOfSeveralSizesWithoutHasNext() {
      var vec = new UnorderedVec<Integer>();
      for (var i = 1; i <= 16; i++) {
        vec.add(i);
        var iterator = vec.iterator();
        var sum = 0;
        for (; ; ) {
          try {
            sum += iterator.next();
          } catch (NoSuchElementException e) {
            break;
          }
        }
        assertEquals(i * (i + 1) / 2, sum);
      }
    }

    @Test
    public void initialCapacityIs16() throws IllegalAccessException {
      var field = Arrays.stream(UnorderedVec.class.getDeclaredFields())
          .filter(f -> f.getType().isArray())
          .findFirst().orElseThrow();
      field.setAccessible(true);
      assertEquals(16, Array.getLength(field.get(new UnorderedVec<>())));
    }
  }


  @Nested
  public class Q3 {
    @Test
    public void oneMillionInsertionsAreFast() {
      var vec = new UnorderedVec<Integer>();
      assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
        IntStream.range(0, 1_000_000).forEach(vec::add);
      });
      assertEquals(1_000_000, vec.size());

      var sum = 0L;
      for(var value : vec) {
        sum += value;
      }

      assertEquals(499_999_500_000L, sum);
    }

    @Test
    public void sizeAndOrderSurviveResizing() {
      for(var count : new int[]{0, 1, 15, 16, 17, 31, 32, 33, 100, 1_000, 10_000}) {
        var vec = new UnorderedVec<Integer>();
        assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
          IntStream.range(0, count).forEach(vec::add);
        });

        assertEquals(count, vec.size());

        var list = new ArrayList<Integer>();
        for(var value : vec) {
          list.add(value);
        }

        assertEquals(IntStream.range(0, count).boxed().toList(), list);
      }
    }

    @Test
    public void vecVeryBiiiiiig() {
      assumeTrue(Runtime.getRuntime().maxMemory() >= 15L * 1024 * 1024 * 1024, "use -Xmx16G");

      var vec = new UnorderedVec<Integer>();
      IntStream.range(0, Integer.MAX_VALUE - 16).forEach(i -> vec.add(i % 128));

      var sum = 0L;
      for (var value : vec) {
        sum += value;
      }
      assertEquals(136_365_209_625L, sum);
    }
  }


  @Nested
  public class Q4 {
    @Test
    public void removeExistingKeepsTheOthers() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      assertTrue(vec.remove("B"));
      assertEquals(2, vec.size());

      var set = new HashSet<String>();
      for(var element : vec) {
        set.add(element);
      }
      assertEquals(Set.of("A", "C"), set);
    }

    @Test
    public void removeNonExistingChangesNothing() {
      var vec = new UnorderedVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);

      assertFalse(vec.remove(4));
      assertEquals(3, vec.size());

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

    @Test
    public void removeAnInstanceOfAnotherClassChangesNothing() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      assertFalse(vec.remove(333));
      assertEquals(2, vec.size());

      var set = new HashSet<String>();
      for(var element : vec) {
        set.add(element);
      }
      assertEquals(Set.of("A", "B"), set);
    }

    @Test
    public void removeUsesEqualsNotIdentity() {
      record Person(String name) {}

      var vec = new UnorderedVec<Person>();
      vec.add(new Person("Jane"));

      assertTrue(vec.remove(new Person("Jane")));
      assertEquals(0, vec.size());
    }

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

      assertTrue(vec.remove("a"));
      assertEquals(2, vec.size());

      var set = new HashSet<String>();
      for(var element : vec) {
        set.add(element);
      }
      assertEquals(Set.of("a", "b"), set);
    }

    @Test
    public void removeFromAFullInternalArray() {
      for(var value : new int[] {0, 7, 15}) {
        var vec = new UnorderedVec<Integer>();
        IntStream.range(0, 16).forEach(vec::add);
        assertTrue(vec.remove(value));

        var elements = new HashSet<Integer>();
        for(var element : vec) {
          elements.add(element);
        }

        assertEquals(15, vec.size());
        var expected = IntStream.range(0, 16).boxed()
            .filter(i -> i != value)
            .collect(Collectors.toSet());
        assertEquals(expected, elements);
      }
    }

    @Test
    public void removeFromEmpty() {
      var vec = new UnorderedVec<String>();
      assertFalse(vec.remove("A"));
      assertEquals(0, vec.size());
    }

    @Test
    public void removeElementCanBeGarbageCollected() {
      record Person(String name) {}
      var john = new Person("John");
      var ref = new WeakReference<>(john);
      var vec = new UnorderedVec<Person>();
      vec.add(john);

      assertTrue(vec.remove(john));

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

    @Test
    public void removeSeveralElementsCanBeGarbageCollected() {
      record Person(String name) {}
      var john = new Person("John");
      var helena = new Person("Helena");
      var refJohn = new WeakReference<>(john);
      var refHelena = new WeakReference<>(helena);
      var vec = new UnorderedVec<Person>();
      vec.add(new Person("Jane"));
      vec.add(new Person("Anita"));
      vec.add(john);
      vec.add(helena);

      assertTrue(vec.remove(john));
      assertTrue(vec.remove(helena));

      john = null;
      helena = null;
      System.gc();
      assertTrue(refJohn.refersTo(null));
      assertTrue(refHelena.refersTo(null));
    }

    @Test
    public void removeLastString() {
      var vec = new UnorderedVec<String>();
      vec.add("A");

      assertTrue(vec.remove("A"));
      assertEquals(0, vec.size());
    }

    @Test
    public void removeAllString() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      assertTrue(vec.remove("A"));
      assertTrue(vec.remove("B"));
      assertTrue(vec.remove("C"));
      assertEquals(0, vec.size());
    }

    @Test
    public void removeThenAddAgain() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      vec.remove("A");
      vec.add("C");

      var set = new HashSet<String>();
      for(var element : vec) {
        set.add(element);
      }
      assertEquals(Set.of("B", "C"), set);
    }

    @Test
    public void removeAllInReverseOrderIsFast() {
      var vec = new UnorderedVec<Integer>();
      IntStream.range(0, 1_000_000).forEach(vec::add);

      assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
        assertTrue(vec.remove(0));
        for (var i = 1_000_000; --i > 0; ) {
          assertTrue(vec.remove(i));
        }
      });
      assertEquals(0, vec.size());
    }

    @Test
    public void removePrecondition() {
      var vec = new UnorderedVec<String>();
      assertThrows(NullPointerException.class, () -> vec.remove(null));
    }

    @Test
    public void removeFailButContentIsNotChanged() {
      var vec = new UnorderedVec<String>();
      vec.add("A");

      assertThrows(NullPointerException.class, () -> vec.remove(null));

      assertEquals(1, vec.size());
      for(var element : vec) {
        assertEquals("A", element);
      }
    }
  }


  @Nested
  public class Q5 {
    @Test
    public void displayEmpty() {
      var vec = new UnorderedVec<>();
      assertEquals("<>", "" + vec);
    }

    @Test
    public void displaySingleElement() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");

      assertEquals("<Hello>", "" + vec);
    }

    @Test
    public void displayMultipleElements() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");
      vec.add("!");

      assertEquals("<Hello, World, !>", "" + vec);
    }

    @Test
    public void displayWithIntegers() {
      var vec = new UnorderedVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(3);

      assertEquals("<1, 2, 3>", "" + vec);
    }

    @Test
    public void displayWithMixedTypes() {
      var vec = new UnorderedVec<>();
      vec.add(1);
      vec.add("Two");
      vec.add(3.0);
      vec.add(false);

      assertEquals("<1, Two, 3.0, false>", "" + vec);
    }

    @Test
    public void displayAfterRemove() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");
      vec.add("!");

      vec.remove("Hello");

      assertEquals("<!, World>", "" + vec);
    }
  }


  @Nested
  public class Q6 {
    @Test
    public void equalsIgnoresOrderOfString() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("foo");
      vec1.add("bar");

      var vec2 = new UnorderedVec<String>();
      vec2.add("bar");
      vec2.add("foo");

      assertTrue(vec1.equals(vec2));
      assertTrue(vec2.equals(vec1));
    }

    @Test
    public void equalsIgnoresOrderOfInteger() {
      var vec1 = new UnorderedVec<Integer>();
      vec1.add(1000);
      vec1.add(2000);
      vec1.add(3000);

      var vec2 = new UnorderedVec<Integer>();
      vec2.add(3000);
      vec2.add(1000);
      vec2.add(2000);

      assertTrue(vec1.equals(vec2));
      assertTrue(vec2.equals(vec1));
    }

    @Test
    public void notEqualWithDifferentElements() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("foo");
      vec1.add("bar");

      var vec2 = new UnorderedVec<String>();
      vec2.add("foo");
      vec2.add("baz");

      assertFalse(vec1.equals(vec2));
      assertFalse(vec2.equals(vec1));
    }

    @Test
    public void notEqualWithDifferentSizes() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("foo");
      vec1.add("bar");

      var vec2 = new UnorderedVec<String>();
      vec2.add("foo");

      assertFalse(vec1.equals(vec2));
      assertFalse(vec2.equals(vec1));
    }

    @Test
    public void equalsWithEmptyVecs() {
      var vec1 = new UnorderedVec<String>();
      var vec2 = new UnorderedVec<String>();

      assertTrue(vec1.equals(vec2));
      assertTrue(vec2.equals(vec1));
    }

    @Test
    public void equalsSameSizeDifferentMutiplicities() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("a");
      vec1.add("a");
      vec1.add("b");

      var vec2 = new UnorderedVec<String>();
      vec2.add("a");
      vec2.add("b");
      vec2.add("b");

      assertFalse(vec1.equals(vec2));
      assertFalse(vec2.equals(vec1));
    }

    @Test
    public void equalsWithItself() {
      var vec = new UnorderedVec<String>();
      vec.add("foo");
      vec.add("bar");

      assertTrue(vec.equals(vec));
    }

    @Test
    public void testEqualsWithNullDoesNotThrow() {
      var vec = new UnorderedVec<String>();
      vec.add("foo");

      assertFalse(vec.equals(null));
    }

    @Test
    public void equalsIgnoresInternalOrderAfterRemoval() {
      var vec1 = new UnorderedVec<Integer>();
      vec1.add(1);
      vec1.add(2);

      var vec2 = new UnorderedVec<Integer>();
      vec2.add(1);
      vec2.add(3);
      vec2.add(2);
      vec2.remove(3);

      assertTrue(vec1.equals(vec2));
      assertTrue(vec2.equals(vec1));
    }

    @Test
    public void notEqualsWithrOtherTypes() {
      var vec = new UnorderedVec<String>();
      vec.add("foo");

      assertFalse(vec.equals("not a vector"));
      assertFalse(vec.equals(42));
      assertFalse(vec.equals(List.of("foo")));
      assertFalse(vec.equals(Set.of("foo")));
    }

    @Test
    public void equalsWithALargeNumberOfIntegersIsFast() {
      var vec1 = new UnorderedVec<Integer>();
      for (var i = 0; i < 1_000_000; i++) {
        vec1.add(i % 17_473);
      }
      var vec2 = new UnorderedVec<Integer>();
      for (var i = 1_000_000; --i >= 0; ) {
        vec2.add(i % 17_473);
      }

      assertTimeoutPreemptively(Duration.ofSeconds(5), () -> {
        assertTrue(vec1.equals(vec2));
        assertTrue(vec2.equals(vec1));
      });
    }
  }


  @Nested
  public class Q7 {
    @Test
    public void canBeUsedAsAMapKey() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("a");
      vec1.add("b");

      var vec2 = new UnorderedVec<String>();
      vec2.add("a");
      vec2.add("b");

      var map = new HashMap<UnorderedVec<String>, String>();
      map.put(vec1, "value");
      assertEquals("value", map.get(vec2));
    }

    @Test
    public void canBeUsedInAHashSet() {
      var vec1 = new UnorderedVec<String>();
      vec1.add("Hello");
      var vec2 = new UnorderedVec<String>();
      vec2.add("Hello");
      var vec3 = new UnorderedVec<Integer>();
      vec3.add(42);
      var vec4 = new UnorderedVec<Integer>();
      vec4.add(8008);

      assertEquals(
          new HashSet<>(List.of(vec1, vec3, vec4)),
          new HashSet<>(List.of(vec3, vec2, vec4)));
    }

    @Test
    public void canBeUsedWhenResized() {
      var vec = new UnorderedVec<Integer>();
      for (var i = 0; i < 17; i++) {
        vec.add(i);
      }
      vec.remove(16);

      var vec2 = new UnorderedVec<Integer>();
      for (var i = 0; i < 16; i++) {
        vec2.add(i);
      }

      var set = new HashSet<>();
      set.add(vec);
      set.add(vec2);
      assertEquals(1, set.size());
    }

    @Test
    public void canBeUsedInAnyOrder() {
      var set = new HashSet<UnorderedVec<Integer>>();
      for(var i = 0; i < 100_000; i++) {
        var vec = new UnorderedVec<Integer>();
        for(var j = 0; j < 10; j++) {
          vec.add((i + j) % 10);
        }
        set.add(vec);
      }
      assertEquals(1, set.size());
    }
  }


  @Nested
  public class Q8 {
    @Test
    public void sizeEmpty() {
      Collection<String> vec = new UnorderedVec<String>();
      assertEquals(0, vec.size());
    }

    @Test
    public void sizeAfterAdd() {
      Collection<Integer> vec = new UnorderedVec<Integer>();
      vec.add(333);
      assertEquals(1, vec.size());
    }

    @Test
    public void sizeAfterRemove() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      vec.remove("Hello");
      assertEquals(0, vec.size());
    }

    @Test
    public void isEmptyTrueThenFalse() {
      Collection<String> vec = new UnorderedVec<>();
      assertTrue(vec.isEmpty());
      vec.add("Hello");
      assertFalse(vec.isEmpty());
    }

    @Test
    public void contains() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      assertTrue(vec.contains("Hello"));
      assertTrue(vec.contains(new String("Hello")));
      assertFalse(vec.contains("World"));
      assertFalse(vec.contains(42));
    }

    @Test
    public void containsAll() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      vec.add("World");

      assertTrue(vec.containsAll(List.of("Hello", "World")));
      assertTrue(vec.containsAll(List.of()));
      assertFalse(vec.containsAll(List.of("Hello", "Universe")));
    }


    @Test
    public void iteratorEmpty() {
      Collection<String> vec = new UnorderedVec<>();

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

    @Test
    public void iteratorNext() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");

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

    @Test
    public void iteratorNoSuchElementException() {
      Collection<String> vec = new UnorderedVec<>();

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

    @Test
    public void toArrayEmpty() {
      Collection<String> vec = new UnorderedVec<>();

      var array = vec.toArray();
      assertEquals(0, array.length);
    }

    @Test
    public void toArrayCorrectClass() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");

      var array = vec.toArray();
      assertEquals(Object[].class, array.getClass());
    }

    @Test
    public void toArrayNonEmpty() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      vec.add("World");

      var array = vec.toArray();
      assertEquals(2, array.length);
      assertArrayEquals(new Object[]{ "Hello", "World" }, array);
    }

    @Test
    public void toArrayWithGenerator() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("foo");
      vec.add("bar");

      var array = vec.toArray(String[]::new);
      assertEquals(String[].class, array.getClass());
      assertArrayEquals(new String[]{"foo", "bar"}, array);
    }

    @Test
    public void toArrayWithGeneratorOfASubtype() {
      Collection<Object> vec = new UnorderedVec<>();
      vec.add("foo");
      vec.add("bar");

      var array = vec.toArray(String[]::new);
      assertArrayEquals(new String[]{"foo", "bar"}, array);
    }

    @Test
    public void toArrayWithEmptyArrayHasTheRightClass() {
      Collection<Object> vec = new UnorderedVec<>();
      vec.add("a");
      vec.add("b");

      var array = vec.toArray(new String[0]);
      assertEquals(String[].class, array.getClass());
      assertArrayEquals(new String[]{"a", "b"}, array);
    }

    @Test
    public void toArrayWithASubtypeArray() {
      Collection<Object> vec = new UnorderedVec<>();
      vec.add("foo");
      vec.add("bar");

      var array = vec.toArray(new String[0]);
      assertArrayEquals(new String[]{"foo", "bar"}, array);
    }

    @Test
    public void toArrayWithALargerArrayNullTerminates() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      vec.add("World");

      var array = vec.toArray(new String[] { "foo", "bar", "baz" });
      assertArrayEquals(new String[]{ "Hello", "World" , null}, array);
    }

      @Test
      public void toArrayWithAnArrayOfTheRightSizeReusesIt() {
        Collection<String> vec = new UnorderedVec<>();
        vec.add("Hello");
        vec.add("World");

        var input = new String[2];
        assertSame(input, vec.toArray(input));
      }

    @Test
    public void addReturnsTrue() {
      Collection<String> vec = new UnorderedVec<>();

      assertTrue(vec.add("Hello"));
      assertEquals(1, vec.size());
    }

      @Test
      public void addAll() {
        Collection<String> vec = new UnorderedVec<>();
        assertTrue(vec.addAll(List.of("Hello", "World")));
        assertEquals(2, vec.size());
      }

      @Test
      public void addAllOfNothingReturnsFalse() {
        Collection<String> vec = new UnorderedVec<>();

        assertFalse(vec.addAll(List.of()));
        assertEquals(0, vec.size());
      }

      @Test
      public void addAllWithANullElementThrows() {
        Collection<String> vec = new UnorderedVec<>();
        var input = new ArrayList<String>();
        input.add("A");
        input.add(null);

        assertThrows(NullPointerException.class, () -> vec.addAll(input));
      }

      @Test
      public void addAllReturnTrue() {
        Collection<String> vec = new UnorderedVec<>();

        assertTrue(vec.addAll(List.of("Hello", "World")));
        assertEquals(2, vec.size());
      }

    @Test
    public void removeExistingElement() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");

      assertTrue(vec.remove("Hello"));
      assertEquals(0, vec.size());
    }

    @Test
    public void removeNonExistingElement() {
      Collection<String> vec = new UnorderedVec<>();
      vec.add("Hello");

      assertFalse(vec.remove("World"));
    }

    @Test
    public void removeNonExistingAnInstanceOfAnotherClass() {
      UnorderedVec<String> vec = new UnorderedVec<>();
      vec.add("Hello");

      assertFalse(vec.remove(42));
    }

    @Test
    public void removeNull() {
      Collection<String> vec = new UnorderedVec<>();

      assertThrows(NullPointerException.class, () -> vec.remove(null));
    }

    @Test
    public void vecClassIsNeitherOrderedNorASet() {
      var vec = (Object) new UnorderedVec<>();

      assertAll(
          () -> assertFalse(vec instanceof List<?>),
          () -> assertFalse(vec instanceof Set<?>),
          () -> assertFalse(vec instanceof SequencedCollection<?>),
          () -> assertFalse(vec instanceof Queue<?>));
    }
  }


  @Nested
  public class Q9 {
    @Test
    public void iteratorRemoveOnlyElement() {
      UnorderedVec<String> vec = new UnorderedVec<>();
      vec.add("Hello");
      var iterator = vec.iterator();
      iterator.next();
      iterator.remove();

      assertEquals(0, vec.size());
      assertFalse(iterator.hasNext());
    }

    @Test
    public void iteratorRemoveSelectedElement() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      var iterator = vec.iterator();
      while (iterator.hasNext()) {
        var element = iterator.next();
        if (element.equals("B")) {
          iterator.remove();
        }
      }

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);

      assertEquals(Set.of("A", "C"), set);
    }

    @Test
    public void iteratorRemoveSeveralSelectedElements() {
      var vec = new UnorderedVec<Integer>();
      vec.add(1);
      vec.add(3);
      vec.add(7);
      vec.add(2);

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

      assertEquals(1, vec.size());
      assertEquals(2, vec.iterator().next());
    }

    @Test
    public void iteratorRemoveDuplicates() {
      var vec = new UnorderedVec<Integer>();
      vec.add(1);
      vec.add(2);
      vec.add(1);
      vec.add(3);
      vec.add(1);

      for (var iterator = vec.iterator(); iterator.hasNext(); ) {
        if (iterator.next() == 1) {
          iterator.remove();
        }
      }

      assertEquals(2, vec.size());

      var set = new HashSet<Integer>();
      vec.iterator().forEachRemaining(set::add);
      assertEquals(Set.of(2, 3), set);
    }

    @Test
    public void iteratorRemoveTheLastElement() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      var it = vec.iterator();
      it.next();
      it.next();
      it.next();
      it.remove();
      assertFalse(it.hasNext());

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);
      assertEquals(Set.of("A", "B"), set);
    }

    @Test
    public void remainingElementsAreStillVisitedAfterARemoval() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      var it = vec.iterator();
      assertEquals("A", it.next());
      it.remove();

      var remaining = new ArrayList<String>();
      it.forEachRemaining(remaining::add);

      assertEquals(Set.of("B", "C"), new HashSet<>(remaining));
      assertEquals(2, remaining.size());
    }

    @Test
    public void iteratorRemoveWithoutNextThrows() {
      var vec = new UnorderedVec<String>();
      vec.add("A");

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

    @Test
    public void iteratorRemoveTwiceThrows() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      var it = vec.iterator();
      it.next();
      it.remove();
      assertThrows(IllegalStateException.class, it::remove);
      assertEquals(1, vec.size());
    }

    @Test
    public void iteratorRemoveCanBeReArmedByNext() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      var it = vec.iterator();
      it.next();
      it.remove();
      it.next();
      it.remove();

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

    @Test
    public void removingEverythingThroughTheIteratorSeesEachElementOnce() {
      for(var count : new int[] {1, 2, 3, 5, 11, 16, 17, 40}) {

        var vec = new UnorderedVec<Integer>();
        IntStream.range(0, count).forEach(vec::add);

        var seen = new ArrayList<Integer>();
        var iterator = vec.iterator();
        while (iterator.hasNext()) {
          seen.add(iterator.next());
          iterator.remove();
        }

        assertEquals(0, vec.size());
        assertEquals(count, seen.size());
        assertEquals(IntStream.range(0, count).boxed().collect(toSet()), new HashSet<>(seen));
      }
    }

    @Test
    public void elementRemovedByTheIteratorCanBeGarbageCollected() {
      record Person(String name) {}
      var person = new Person("John");
      var vec = new UnorderedVec<Person>();
      vec.add(person);

      var weakRef = new WeakReference<>(person);
      person = null;

      var iterator = vec.iterator();
      iterator.next();
      iterator.remove();

      System.gc();

      assertTrue(weakRef.refersTo(null));
    }

    @Test
    public void elementsMovedThenRemovedByTheIteratorCanBeGarbageCollected() {
      record Person(String name) {}
      var john = new Person("John");
      var helena = new Person("Helena");
      var vec = new UnorderedVec<Person>();
      vec.add(john);
      vec.add(helena);

      var weakJohn = new WeakReference<>(john);
      john = null;
      var weakHelena = new WeakReference<>(helena);
      helena = null;

      var iterator = vec.iterator();
      iterator.next();
      iterator.remove();
      iterator.next();
      iterator.remove();

      System.gc();

      assertTrue(weakJohn.refersTo(null));
      assertTrue(weakHelena.refersTo(null));
    }

    @Test
    public void clear() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.clear();

      assertEquals(0, vec.size());
      assertFalse(vec.iterator().hasNext());
    }

    @Test
    public void clearOnAnEmptyVec() {
      var vec = new UnorderedVec<String>();
      vec.clear();
      assertEquals(0, vec.size());
    }

    @Test
    public void vecIsUsableAndOrderedAfterClear() {
      var vec = new UnorderedVec<Integer>();
      IntStream.range(0, 40).forEach(vec::add);
      vec.clear();
      vec.add(100);
      vec.add(2);
      vec.add(7);

      var list = new ArrayList<Integer>();
      vec.iterator().forEachRemaining(list::add);

      assertEquals(List.of(100, 2, 7), list);
    }

    @Test
    public void clearedElementsCanBeGarbageCollected() {
      var object = new Object();
      var vec = new UnorderedVec<>();
      vec.add(object);

      var weakRef = new WeakReference<>(object);
      object = null;

      vec.clear();

      System.gc();

      assertTrue(weakRef.refersTo(null));
    }

    @Test
    public void retainAll() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");
      vec.add("!");

      assertTrue(vec.retainAll(List.of("Hello", "!")));

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);

      assertEquals(Set.of("Hello", "!"), set);
    }

    @Test
    public void retainAllWithoutChangeReturnsFalse() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");

      assertFalse(vec.retainAll(List.of("Hello", "World", "!")));
    }

    @Test
    public void retainAllOfNothingEmptiesTheVec() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");

      assertTrue(vec.retainAll(List.of()));
      assertEquals(0, vec.size());
    }

    @Test
    public void removeAll() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");
      vec.add("!");

      assertTrue(vec.removeAll(List.of("Hello")));

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);
      assertEquals(Set.of("World", "!"), set);
    }

    @Test
    public void removeAllWithoutChangeReturnsFalse() {
      var vec = new UnorderedVec<String>();
      vec.add("Hello");
      vec.add("World");

      assertFalse(vec.removeAll(List.of("!")));

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);
      assertEquals(Set.of("Hello", "World"), set);
    }

    @Test
    public void removeIf() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");
      vec.add("C");

      assertTrue(vec.removeIf("B"::equals));

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);

      assertEquals(Set.of("A", "C"), set);
    }

    @Test
    public void removeIfWithoutMatchReturnsFalse() {
      var vec = new UnorderedVec<String>();
      vec.add("A");
      vec.add("B");

      assertFalse(vec.removeIf("Z"::equals));

      var set = new HashSet<String>();
      vec.iterator().forEachRemaining(set::add);
      assertEquals(Set.of("A", "B"), set);
    }

    @Test
    public void removeIfOnEverything() {
      var vec = new UnorderedVec<Integer>();
      IntStream.range(0, 40).forEach(vec::add);

      assertTrue(vec.removeIf(_ -> true));
      assertEquals(0, vec.size());
    }
  }
}