package fr.uge.graph;

import static org.junit.jupiter.api.Assertions.*;

import module java.base;

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

public final class GraphTest {

  @Nested
  public final class Q1 {

    @Test
    public void testVertexCountWithZeroVertices() {
      Graph<String> graph = Graph.of(0);
      assertNotNull(graph);
      assertEquals(0, graph.vertexCount());
    }

    @Test
    public void testVertexCountWithPositiveVertices() {
      Graph<String> graph = Graph.of(5);
      assertNotNull(graph);
      assertEquals(5, graph.vertexCount());
    }

    @Test
    public void testVertexCountWithMediumGraph() {
      Graph<String> graph = Graph.of(1_000);
      assertEquals(1_000, graph.vertexCount());
    }

    @Test
    public void testVertexCountWithDifferentGenericTypes() {
      Graph<String> stringGraph = Graph.of(2);
      Graph<Integer> integerGraph = Graph.of(3);
      Graph<Double> doubleGraph = Graph.of(4);
      assertEquals(2, stringGraph.vertexCount());
      assertEquals(3, integerGraph.vertexCount());
      assertEquals(4, doubleGraph.vertexCount());
    }

    @Test
    public void testOfThrowsOnNegativeVertexCount() {
      var exception = assertThrows(IllegalArgumentException.class, () -> Graph.of(-1));
      assertNotNull(exception.getMessage());
    }

    @Test
    public void testOfThrowsOnLargeNegativeVertexCount() {
      var exception = assertThrows(IllegalArgumentException.class, () -> Graph.of(-1_000));
      assertNotNull(exception.getMessage());
    }

    @Test
    public void testOfThrowsOnLargePositiveOfVertexCount() {
      var exception = assertThrows(IllegalArgumentException.class, () -> Graph.of(1_000_000));
      assertNotNull(exception.getMessage());
    }

    @Test
    public void testOfReturnsAMatrixGraph() {
      assertInstanceOf(Graph.MatrixGraph.class, Graph.of(3));
    }

    @Test
    public void testGraphIsAnInterface() {
      assertTrue(Graph.class.isInterface());
    }

    @Test
    public void testGraphHasNoSupplementaryPublicMethods() {
      var authorizedNames = Set.of("of", "vertexCount", "edgeCount", "getEdge", "addEdge",
          "removeEdge", "edges", "neighbors");
      for (var method : Graph.class.getMethods()) {
        assertTrue(authorizedNames.contains(method.getName()),
            "Method " + method.getName() + " is not authorized in Graph");
      }
    }

    @Test
    public void testOfReturnsDoesNotLeakImplementationClassName() {
      for (var method : Graph.class.getDeclaredMethods()) {
        if (method.getName().equals("of")) {
          assertEquals(Graph.class, method.getReturnType());
        }
      }
    }

    @Test
    public void testMatrixGraphIsANestedFinalClassOfGraph() {
      var matrixGraph = Graph.MatrixGraph.class;
      assertTrue(matrixGraph.isMemberClass());
      assertEquals(Graph.class, matrixGraph.getEnclosingClass());
      assertTrue(matrixGraph.accessFlags().contains(AccessFlag.FINAL));
      assertTrue(Arrays.asList(Graph.class.getDeclaredClasses()).contains(matrixGraph));
    }

    @Test
    public void testMatrixGraphHasNoPublicConstructor() {
      assertEquals(0, Graph.MatrixGraph.class.getConstructors().length);
    }

    @Test
    public void testMatrixGraphFieldsArePrivate() {
      for (var field : Graph.MatrixGraph.class.getDeclaredFields()) {
        assertTrue(field.accessFlags().contains(AccessFlag.PRIVATE),
            "field " + field.getName() + " must be private");
      }
    }

    @Test
    public void testMatrixGraphStoresVertexCountInAFinalField() throws NoSuchFieldException {
      var field = Arrays.stream(Graph.MatrixGraph.class.getDeclaredFields())
          .filter(f -> f.getType() == int.class)
          .findFirst()
          .orElseThrow();
      assertTrue(field.accessFlags().contains(AccessFlag.FINAL));
    }

    @Test
    public void testMatrixIsAFinalOneDimensionalArray() throws NoSuchFieldException {
      var field = Arrays.stream(Graph.MatrixGraph.class.getDeclaredFields())
          .filter(f -> f.getType() == Object[].class)
          .findFirst()
          .orElseThrow();
      assertTrue(field.accessFlags().contains(AccessFlag.FINAL));
      assertFalse(field.getType().getComponentType().isArray());
    }

    @Test
    public void testMatrixGraphHasNoSupplementaryPublicMethods() {
      var authorizedNames = Set.of("vertexCount", "edgeCount", "getEdge", "addEdge",
          "removeEdge", "edges", "neighbors");
      for (var method : Graph.MatrixGraph.class.getDeclaredMethods()) {
        if (method.accessFlags().contains(AccessFlag.PUBLIC)) {
          assertTrue(authorizedNames.contains(method.getName()),
              "Method " + method.getName() + " is not authorized in MatrixGraph");
        }
      }
    }

    @Test
    public void testMatrixGraphConstructorsCallSuperAsLastInstruction() throws IOException {
      var className = "/" + Graph.MatrixGraph.class.getName().replace('.', '/') + ".class";
      byte[] data;
      try (var input = Graph.MatrixGraph.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 final class Q2 {

    @Test
    public void testAddEdgeReturnsNullWhenThereWasNoEdge() {
      Graph<String> graph = Graph.of(3);
      assertNull(graph.addEdge(0, 1, "a"));
    }

    @Test
    public void testGetEdgeOnEmptyGraphReturnsEmptyOptional() {
      Graph<String> graph = Graph.of(3);
      assertEquals(Optional.empty(), graph.getEdge(0, 0));
      assertEquals(Optional.empty(), graph.getEdge(0, 2));
      assertEquals(Optional.empty(), graph.getEdge(2, 1));
    }

    @Test
    public void testAddEdgeReturnsThePreviousValue() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      assertEquals("a", graph.addEdge(0, 1, "b"));
      assertEquals("b", graph.addEdge(0, 1, "c"));
    }

    @Test
    public void testGetEdgeReturnsTheValue() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      assertEquals(Optional.of("a"), graph.getEdge(0, 1));
    }

    @Test
    public void testAddEdgeReplacesTheValue() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 2, "first");
      graph.addEdge(1, 2, "second");
      assertEquals(Optional.of("second"), graph.getEdge(1, 2));
    }

    @Test
    public void testAddEdgeDoesNotAffectOtherCells() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      assertEquals(Optional.of("a"), graph.getEdge(0, 1));
      assertEquals(Optional.empty(), graph.getEdge(0, 0));
      assertEquals(Optional.empty(), graph.getEdge(0, 2));
      assertEquals(Optional.empty(), graph.getEdge(2, 2));
    }

    @Test
    public void testGraphIsDirected() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      assertEquals(Optional.empty(), graph.getEdge(1, 0));
    }

    @Test
    public void testSelfLoop() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 1, "loop");
      assertEquals(Optional.of("loop"), graph.getEdge(1, 1));
      assertEquals(Optional.empty(), graph.getEdge(0, 0));
      assertEquals(Optional.empty(), graph.getEdge(2, 2));
    }

    @Test
    public void testSingleVertexGraph() {
      Graph<String> graph = Graph.of(1);
      assertEquals(Optional.empty(), graph.getEdge(0, 0));
      assertNull(graph.addEdge(0, 0, "self"));
      assertEquals(Optional.of("self"), graph.getEdge(0, 0));
    }

    @Test
    public void testEveryCellIsIndependent() {
      Graph<String> graph = Graph.of(4);
      for (var from = 0; from < 4; from++) {
        for (var to = 0; to < 4; to++) {
          assertNull(graph.addEdge(from, to, from + "-" + to));
        }
      }
      for (var from = 0; from < 4; from++) {
        for (var to = 0; to < 4; to++) {
          assertEquals(Optional.of(from + "-" + to), graph.getEdge(from, to));
        }
      }
    }

    @Test
    public void testMatrixIsStoredRowByRow() throws ReflectiveOperationException {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 2, "x");
      graph.addEdge(2, 1, "y");
      graph.addEdge(0, 0, "z");

      var field = Arrays.stream(Graph.MatrixGraph.class.getDeclaredFields())
          .filter(f -> f.getType() == Object[].class)
          .findFirst()
          .orElseThrow();
      field.setAccessible(true);
      var matrix = (Object[]) field.get(graph);

      assertEquals("x", matrix[1 * 3 + 2]);
      assertEquals("y", matrix[2 * 3 + 1]);
      assertEquals("z", matrix[0]);
    }

    @Test
    public void testBoundaryVertices() {
      Graph<String> graph = Graph.of(5);
      graph.addEdge(0, 4, "a");
      graph.addEdge(4, 0, "b");
      graph.addEdge(4, 4, "c");
      assertEquals(Optional.of("a"), graph.getEdge(0, 4));
      assertEquals(Optional.of("b"), graph.getEdge(4, 0));
      assertEquals(Optional.of("c"), graph.getEdge(4, 4));
    }

    @Test
    public void testDifferentGenericTypes() {
      Graph<Integer> integerGraph = Graph.of(2);
      Graph<Double> doubleGraph = Graph.of(2);
      integerGraph.addEdge(0, 1, 42);
      doubleGraph.addEdge(1, 0, 3.14);
      assertEquals(Optional.of(42), integerGraph.getEdge(0, 1));
      assertEquals(Optional.of(3.14), doubleGraph.getEdge(1, 0));
    }

    @Test
    public void testGetEdgeThrowsOnInvalidFrom() {
      Graph<String> graph = Graph.of(3);
      var exception1 = assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(-1, 0));
      assertNotNull(exception1.getMessage());
      var exception2 = assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(3, 0));
      assertNotNull(exception2.getMessage());
    }

    @Test
    public void testGetEdgeThrowsOnInvalidTo() {
      Graph<String> graph = Graph.of(3);
      var exception1 = assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(0, -1));
      assertNotNull(exception1.getMessage());
      var exception2 = assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(0, 3));
      assertNotNull(exception2.getMessage());
    }

    @Test
    public void testAddEdgeThrowsOnInvalidFrom() {
      Graph<String> graph = Graph.of(3);
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(-1, 0, "a"));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(3, 0, "a"));
    }

    @Test
    public void testAddEdgeThrowsOnInvalidTo() {
      Graph<String> graph = Graph.of(3);
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(0, -1, "a"));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(0, 3, "a"));
    }

    @Test
    public void testGetEdgeDoesNotWrapAroundToTheNextRow() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 0, "a");

      assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(0, 3));
    }

    @Test
    public void testGetEdgeDoesNotWrapAroundToThePreviousRow() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 2, "a");

      assertThrows(IndexOutOfBoundsException.class, () -> graph.getEdge(1, -1));
    }

    @Test
    public void testAddEdgeThrowsOnNullValue() {
      Graph<String> graph = Graph.of(3);
      assertThrows(NullPointerException.class, () -> graph.addEdge(0, 1, null));
    }

    @Test
    public void testAddEdgeWithNullDoesNotModifyTheGraph() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");

      assertThrows(NullPointerException.class, () -> graph.addEdge(0, 1, null));
      assertEquals(Optional.of("a"), graph.getEdge(0, 1));
    }

    @Test
    public void testAddEdgeWithBadIndexDoesNotModifyTheGraph() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 0, "a");

      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(0, 3, "neo"));
      assertEquals(Optional.of("a"), graph.getEdge(1, 0));
    }

    @Test
    public void testAddLargeNumberOfEdges() {
      Graph<String> graph = Graph.of(1_000);
      assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
        for(var i = 0; i < 1_000; i++) {
          for(var j = 0; j < 1_000; j++) {
            graph.addEdge(i, j, "a" + i + "-" + j);
          }
        }
      });

      assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
        for(var i = 0; i < 1_000; i++) {
          for(var j = 0; j < 1_000; j++) {
            assertEquals(Optional.of("a" + i + "-" + j), graph.getEdge(i, j));
          }
        }
      });
    }
  }


  @Nested
  public final class Q3 {

    @Test
    public void testEdgeCountOfNewGraphIsZero() {
      Graph<String> graph = Graph.of(4);
      assertEquals(0, graph.edgeCount());
    }

    @Test
    public void testEdgeCountOfGraphWithoutVertices() {
      Graph<String> graph = Graph.of(0);
      assertEquals(0, graph.edgeCount());
    }

    @Test
    public void testEdgeCountAfterAdds() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      assertEquals(1, graph.edgeCount());
      graph.addEdge(0, 3, "b");
      assertEquals(2, graph.edgeCount());
      graph.addEdge(3, 0, "c");
      assertEquals(3, graph.edgeCount());
    }

    @Test
    public void testEdgeCountDoesNotChangeWhenAnEdgeIsReplaced() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 3, "b");
      graph.addEdge(0, 1, "c");
      assertEquals(2, graph.edgeCount());
    }

    @Test
    public void testEdgeCountCountsSelfLoops() {
      Graph<String> graph = Graph.of(2);
      graph.addEdge(0, 0, "a");
      graph.addEdge(1, 1, "b");
      assertEquals(2, graph.edgeCount());
    }

    @Test
    public void testEdgeCountOfAFullGraph() {
      Graph<Integer> graph = Graph.of(5);
      for (var from = 0; from < 5; from++) {
        for (var to = 0; to < 5; to++) {
          graph.addEdge(from, to, from * 5 + to);
        }
      }
      assertEquals(25, graph.edgeCount());
    }

    @Test
    public void testEdgeCountIsNotModifiedByAFailingAdd() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(0, 3, "b"));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.addEdge(-1, 0, "b"));
      assertThrows(NullPointerException.class, () -> graph.addEdge(1, 1, null));
      assertEquals(1, graph.edgeCount());
    }

    @Test
    public void testEdgeCountIsConstantTime() {
      assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
        Graph<String> graph = Graph.of(10_000);
        for(var i = 0; i < 10_000; i++) {
          graph.addEdge(i, i, "a");
        }
        var total = 0L;
        for (var i = 0; i < 10_000; i++) {
          total += graph.edgeCount();
        }
        assertEquals(100_000_000L, total);
      });
    }
  }


  @Nested
  public final class Q4 {

    @Test
    public void testNeighborsReturnsAnIntStream() {
      Graph<String> graph = Graph.of(3);
      IntStream stream = graph.neighbors(0);
      assertNotNull(stream);
    }

    @Test
    public void testNeighborsOfAVertexWithoutEdges() {
      Graph<String> graph = Graph.of(3);
      assertEquals(0L, graph.neighbors(0).count());
    }

    @Test
    public void testNeighborsAreInIncreasingOrder() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 3, "b");
      graph.addEdge(0, 1, "a");
      assertEquals(List.of(1, 3), graph.neighbors(0).boxed().toList());
    }

    @Test
    public void testNeighborsWithSelfLoop() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 1, "loop");
      assertEquals(List.of(1), graph.neighbors(1).boxed().toList());
    }

    @Test
    public void testNeighborsOnlyContainsOutgoingEdges() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(2, 0, "b");
      assertEquals(List.of(1), graph.neighbors(0).boxed().toList());
      assertEquals(List.of(), graph.neighbors(1).boxed().toList());
      assertEquals(List.of(0), graph.neighbors(2).boxed().toList());
    }

    @Test
    public void testNeighborsThrowsOnInvalidVertex() {
      Graph<String> graph = Graph.of(3);
      var exception1 = assertThrows(IndexOutOfBoundsException.class, () -> graph.neighbors(-1));
      assertNotNull(exception1.getMessage());
      var exception2 = assertThrows(IndexOutOfBoundsException.class, () -> graph.neighbors(3));
      assertNotNull(exception2.getMessage());
    }

    @Test
    public void testNeighborsStreamOperations() {
      Graph<String> graph = Graph.of(10);
      graph.addEdge(0, 2, "a");
      graph.addEdge(0, 4, "b");
      graph.addEdge(0, 7, "c");
      assertEquals(3L, graph.neighbors(0).count());
      assertEquals(13, graph.neighbors(0).sum());
      assertEquals(7, graph.neighbors(0).max().orElseThrow());
      assertEquals(2, graph.neighbors(0).findFirst().orElseThrow());
      assertEquals(List.of(4, 7), graph.neighbors(0).filter(n -> n > 2).boxed().toList());
    }

    @Test
    public void testNeighborsCanBeCalledSeveralTimes() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      assertEquals(List.of(1, 2), graph.neighbors(0).boxed().toList());
      assertEquals(List.of(1, 2), graph.neighbors(0).boxed().toList());
    }

    @Test
    public void testNeighborsWithALargeRow() {
      Graph<String> graph = Graph.of(1_000);
      for (var to = 0; to < 1_000; to++) {
        graph.addEdge(0, to, "e" + to);
      }
      assertEquals(1_000L, graph.neighbors(0).count());
      assertEquals(999 * 1_000 / 2, graph.neighbors(0).sum());
    }

    @Test
    public void testNeighborsInParallel() {
      Graph<String> graph = Graph.of(10_000);
      for (var to = 0; to < 10_000; to++) {
        graph.addEdge(5, to, "e" + to);
      }
      assertEquals(9_999 * 10_000 / 2, graph.neighbors(5).parallel().sum());
    }
  }


  @Nested
  public final class Q5 {

    @Test
    public void testTryAdvanceReturnsEachNeighborThenFalse() {
      Graph<String> graph = Graph.of(5);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 3, "b");
      var spliterator = graph.neighbors(0).spliterator();
      var values = new ArrayList<Integer>();

      assertTrue(spliterator.tryAdvance((int n) -> values.add(n)));
      assertTrue(spliterator.tryAdvance((int n) -> values.add(n)));
      assertFalse(spliterator.tryAdvance((int n) -> fail()));
      assertFalse(spliterator.tryAdvance((int n) -> fail()));
      assertEquals(List.of(1, 3), values);
    }

    @Test
    public void testTryAdvanceWithASingleNeighbor() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 0, "loop");
      var spliterator = graph.neighbors(0).spliterator();
      var values = new ArrayList<Integer>();
      assertTrue(spliterator.tryAdvance((int n) -> values.add(n)));
      assertEquals(List.of(0), values);
      spliterator.forEachRemaining((int n) -> fail());
    }

    @Test
    public void testTryAdvanceWithoutNeighbors() {
      Graph<String> graph = Graph.of(5);
      var spliterator = graph.neighbors(0).spliterator();
      assertFalse(spliterator.tryAdvance((int n) -> fail()));
      spliterator.forEachRemaining((int n) -> fail());
    }

    @Test
    public void testTryAdvanceThrowsOnNullConsumer() {
      Graph<String> graph = Graph.of(5);
      graph.addEdge(0, 1, "a");
      var spliterator = graph.neighbors(0).spliterator();
      assertThrows(NullPointerException.class,
          () -> spliterator.tryAdvance((java.util.function.IntConsumer) null));
    }

    @Test
    public void testForEachRemainingAfterATryAdvance() {
      Graph<String> graph = Graph.of(6);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(0, 5, "c");
      var spliterator = graph.neighbors(0).spliterator();
      var values = new ArrayList<Integer>();
      spliterator.tryAdvance((int n) -> values.add(n));
      spliterator.forEachRemaining((int n) -> values.add(n));
      assertEquals(List.of(1, 2, 5), values);
    }

    @Test
    public void testTrySplitReturnsNull() {
      Graph<String> graph = Graph.of(6);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(0, 3, "c");
      var spliterator = graph.neighbors(0).spliterator();
      assertNull(spliterator.trySplit());
    }

    @Test
    public void testTrySplitReturnsNullWithoutNeighbors() {
      Graph<String> graph = Graph.of(6);
      var spliterator = graph.neighbors(0).spliterator();
      assertNull(spliterator.trySplit());
    }

    @Test
    public void testEstimateSizeIsBetweenZeroAndVertexCount() {
      Graph<String> graph = Graph.of(10);
      var spliterator = graph.neighbors(3).spliterator();
      assertTrue(spliterator.estimateSize() >= 0);
      assertTrue(spliterator.estimateSize() <= 10);
    }

    @Test
    public void testEstimateSizeIsZeroOnceExhausted() {
      Graph<String> graph = Graph.of(10);
      var spliterator = graph.neighbors(3).spliterator();
      spliterator.tryAdvance((int _) -> fail());
      assertEquals(0, spliterator.estimateSize());
    }

    @Test
    public void testEstimateSizeDecreasesWhenConsuming() {
      Graph<String> graph = Graph.of(10);
      graph.addEdge(0, 2, "a");
      graph.addEdge(0, 5, "b");
      var spliterator = graph.neighbors(0).spliterator();
      var initial = spliterator.estimateSize();
      spliterator.tryAdvance((int _) -> { });
      assertTrue(spliterator.estimateSize() < initial);
      spliterator.forEachRemaining((int _) -> { });
      assertEquals(0, spliterator.estimateSize());
    }

    @Test
    public void testCharacteristics() {
      Graph<String> graph = Graph.of(10);
      var spliterator = graph.neighbors(3).spliterator();
      assertAll(
          () -> assertTrue(spliterator.hasCharacteristics(Spliterator.ORDERED)),
          () -> assertTrue(spliterator.hasCharacteristics(Spliterator.ORDERED)),
          () -> assertTrue(spliterator.hasCharacteristics(Spliterator.SORTED)),
          () -> assertTrue(spliterator.hasCharacteristics(Spliterator.NONNULL)),
          () -> assertFalse(spliterator.hasCharacteristics(Spliterator.SIZED))
      );
    }

    @Test
    public void testTwoStreamsAreIndependent() {
      Graph<String> graph = Graph.of(5);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 4, "b");
      var spliterator1 = graph.neighbors(0).spliterator();
      var spliterator2 = graph.neighbors(0).spliterator();
      spliterator1.forEachRemaining((int _) -> { });
      var values = new ArrayList<Integer>();
      spliterator2.forEachRemaining((int n) -> values.add(n));
      assertEquals(List.of(1, 4), values);
    }

    @Test
    public void testStreamWithLimitStopsEarly() {
      Graph<String> graph = Graph.of(1_000);
      for (var to = 0; to < 1_000; to++) {
        graph.addEdge(0, to, "e");
      }
      assertEquals(List.of(0, 1, 2), graph.neighbors(0).limit(3).boxed().toList());
    }
  }


  @Nested
  public final class Q6 {

    @Test
    public void testEdgeIsAPublicStaticFinal() {
      var edgeClass = Graph.Edge.class;
      assertTrue(edgeClass.accessFlags().contains(AccessFlag.PUBLIC));
      assertTrue(edgeClass.accessFlags().contains(AccessFlag.STATIC));
      assertTrue(edgeClass.accessFlags().contains(AccessFlag.FINAL));
    }

    @Test
    public void testGraphHasOnlyTwoNestedClasses() {
      var expected = Set.<Class<?>>of(Graph.Edge.class, Graph.MatrixGraph.class);
      var actual = Set.<Class<?>>of(Graph.class.getDeclaredClasses());
      assertEquals(expected, actual);
    }

    @Test
    public void testEdgeAccessors() {
      var edge = new Graph.Edge<>(0, 5, "test");
      assertEquals(0, edge.from());
      assertEquals(5, edge.to());
      assertEquals("test", edge.value());
    }

    @Test
    public void testEdgeEqualsAndHashCode() {
      var edge1 = new Graph.Edge<>(1, 2, "weight");
      var edge2 = new Graph.Edge<>(1, 2, "weight");
      var edge3 = new Graph.Edge<>(2, 1, "weight");
      assertEquals(edge1, edge2);
      assertEquals(edge2, edge1);
      assertEquals(edge1.hashCode(), edge2.hashCode());
      assertNotEquals(edge1, edge3);
    }

    @Test
    public void testEdgeToString() {
      var string = new Graph.Edge<>(2, 5, "abc").toString();
      assertTrue(string.contains("2"));
      assertTrue(string.contains("5"));
      assertTrue(string.contains("abc"));
    }

    @Test
    public void testEdgeThrowsOnNegativeFrom() {
      var exception = assertThrows(IllegalArgumentException.class,
          () -> new Graph.Edge<>(-1, 5, "test"));
      assertNotNull(exception.getMessage());
    }

    @Test
    public void testEdgeThrowsOnNegativeTo() {
      var exception = assertThrows(IllegalArgumentException.class,
          () -> new Graph.Edge<>(0, -1, "test"));
      assertNotNull(exception.getMessage());
    }

    @Test
    public void testEdgeThrowsOnNullValue() {
      assertThrows(NullPointerException.class, () -> new Graph.Edge<>(0, 1, null));
    }

    @Test
    public void testEdgesOfAVertexWithoutEdges() {
      Graph<String> graph = Graph.of(3);
      for (var edge : graph.edges(0)) {
        fail("Unexpected edge: " + edge);
      }
    }

    @Test
    public void testEdgesReturnsASingleEdge() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(List.of(new Graph.Edge<>(0, 1, "a")), edges);
    }

    @Test
    public void testEdgesReturnsEdgesInIncreasingOrderOfTo() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 3, "b");
      graph.addEdge(0, 1, "a");

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(
          List.of(new Graph.Edge<>(0, 1, "a"), new Graph.Edge<>(0, 3, "b")),
          edges);
    }

    @Test
    public void testEdgesSkipsMissingEdges() {
      Graph<Integer> graph = Graph.of(5);
      graph.addEdge(1, 0, 10);
      graph.addEdge(1, 2, 20);
      graph.addEdge(1, 4, 40);

      var edges = new ArrayList<Graph.Edge<Integer>>();
      graph.edges(1).forEach(edges::add);

      assertEquals(List.of(
              new Graph.Edge<>(1, 0, 10),
              new Graph.Edge<>(1, 2, 20),
              new Graph.Edge<>(1, 4, 40)),
          edges);
    }

    @Test
    public void testEdgesWithSelfLoop() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 1, "loop");

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(1).forEach(edges::add);

      assertEquals(List.of(new Graph.Edge<>(1, 1, "loop")), edges);
    }

    @Test
    public void testEdgesWithAFullRow() {
      Graph<Integer> graph = Graph.of(3);
      graph.addEdge(0, 0, 1);
      graph.addEdge(0, 1, 2);
      graph.addEdge(0, 2, 3);

      var edges = new ArrayList<Graph.Edge<Integer>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(List.of(
              new Graph.Edge<>(0, 0, 1),
              new Graph.Edge<>(0, 1, 2),
              new Graph.Edge<>(0, 2, 3)),
          edges);
    }

    @Test
    public void testEdgesOnlyReturnsOutgoingEdges() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "01");
      graph.addEdge(1, 2, "12");
      graph.addEdge(2, 0, "20");

      var edges0 = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges0::add);
      var edges1 = new ArrayList<Graph.Edge<String>>();
      graph.edges(1).forEach(edges1::add);
      var edges2 = new ArrayList<Graph.Edge<String>>();
      graph.edges(2).forEach(edges2::add);

      assertEquals(List.of(new Graph.Edge<>(0, 1, "01")), edges0);
      assertEquals(List.of(new Graph.Edge<>(1, 2, "12")), edges1);
      assertEquals(List.of(new Graph.Edge<>(2, 0, "20")), edges2);
    }

    @Test
    public void testEdgesThrowsOnInvalidVertex() {
      Graph<String> graph = Graph.of(3);
      var exception1 = assertThrows(IndexOutOfBoundsException.class, () -> graph.edges(-1));
      assertNotNull(exception1.getMessage());
      var exception2 = assertThrows(IndexOutOfBoundsException.class, () -> graph.edges(3));
      assertNotNull(exception2.getMessage());
    }

    @Test
    public void testEdgesIterableCanBeUsedSeveralTimes() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var edges = graph.edges(0);

      var first = new ArrayList<Graph.Edge<String>>();
      edges.forEach(first::add);
      var second = new ArrayList<Graph.Edge<String>>();
      edges.forEach(second::add);

      assertEquals(2, first.size());
      assertEquals(first, second);
    }

    @Test
    public void testEdgesWithDifferentValueTypes() {
      Graph<Integer> intGraph = Graph.of(3);
      intGraph.addEdge(0, 1, 42);
      var intEdges = new ArrayList<Graph.Edge<Integer>>();
      intGraph.edges(0).forEach(intEdges::add);
      assertEquals(List.of(new Graph.Edge<>(0, 1, 42)), intEdges);

      Graph<Boolean> boolGraph = Graph.of(2);
      boolGraph.addEdge(0, 1, true);
      var boolEdges = new ArrayList<Graph.Edge<Boolean>>();
      boolGraph.edges(0).forEach(boolEdges::add);
      assertEquals(List.of(new Graph.Edge<>(0, 1, true)), boolEdges);
    }
  }


  @Nested
  public final class Q7 {

    @Test
    public void testIteratorOnAnEmptyRow() {
      Graph<String> graph = Graph.of(3);
      var iterator = graph.edges(1).iterator();
      assertFalse(iterator.hasNext());
      assertThrows(NoSuchElementException.class, iterator::next);
    }

    @Test
    public void testHasNextIsIdempotent() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      var iterator = graph.edges(0).iterator();
      assertTrue(iterator.hasNext());
      assertTrue(iterator.hasNext());
      assertTrue(iterator.hasNext());
      assertEquals(new Graph.Edge<>(0, 1, "a"), iterator.next());
      assertFalse(iterator.hasNext());
      assertFalse(iterator.hasNext());
    }

    @Test
    public void testNextWorksWithoutCallingHasNext() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 3, "b");
      var iterator = graph.edges(0).iterator();
      assertEquals(new Graph.Edge<>(0, 1, "a"), iterator.next());
      assertEquals(new Graph.Edge<>(0, 3, "b"), iterator.next());
    }

    @Test
    public void testNextThrowsNoSuchElementExceptionAtTheEnd() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      assertThrows(NoSuchElementException.class, iterator::next);
      assertThrows(NoSuchElementException.class, iterator::next);
    }

    @Test
    public void testHasNextDoesNotMutateTheIterator() throws IllegalAccessException {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();

      var fields = iterator.getClass().getDeclaredFields();
      var before = new Object[fields.length];
      for (var i = 0; i < fields.length; i++) {
        fields[i].setAccessible(true);
        before[i] = fields[i].get(iterator);
      }

      assertTrue(iterator.hasNext());

      for (var i = 0; i < fields.length; i++) {
        assertEquals(before[i], fields[i].get(iterator),
            "hasNext() modified the field " + fields[i].getName());
      }
    }

    @Test
    public void testEachCallToIteratorStartsFromTheBeginning() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var edges = graph.edges(0);
      var iterator1 = edges.iterator();
      iterator1.next();
      var iterator2 = edges.iterator();
      assertEquals(new Graph.Edge<>(0, 1, "a"), iterator2.next());
      assertEquals(new Graph.Edge<>(0, 2, "b"), iterator1.next());
    }

    @Test
    public void testEdgesIsLazy() {
      Graph<String> graph = Graph.of(3);
      var edges = graph.edges(0);
      graph.addEdge(0, 2, "late");

      var list = new ArrayList<Graph.Edge<String>>();
      edges.forEach(list::add);

      assertEquals(List.of(new Graph.Edge<>(0, 2, "late")), list);
    }

    @Test
    public void testEdgesWithEdgesOnTheFirstAndLastColumns() {
      Graph<String> graph = Graph.of(5);
      graph.addEdge(2, 0, "first");
      graph.addEdge(2, 4, "last");

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(2).forEach(edges::add);

      assertEquals(List.of(
              new Graph.Edge<>(2, 0, "first"),
              new Graph.Edge<>(2, 4, "last")),
          edges);
    }

    @Test
    public void testEdgesWithALargeRow() {
      Graph<Integer> graph = Graph.of(10_000);
      for (var to = 0; to < 10_000; to++) {
        graph.addEdge(0, to, to);
      }
      var count = 0;
      for (var edge : graph.edges(0)) {
        assertEquals(count, edge.to());
        assertEquals(count, edge.value());
        count++;
      }
      assertEquals(10_000, count);
    }

    @Test
    public void testEdgesWithASparseLargeRow() {
      Graph<Integer> graph = Graph.of(1_000);
      graph.addEdge(999, 500, 1);

      var edges = new ArrayList<Graph.Edge<Integer>>();
      graph.edges(999).forEach(edges::add);

      assertEquals(List.of(new Graph.Edge<>(999, 500, 1)), edges);
    }

    @Test
    public void testEdgesThrowsOnInvalidVertexEvenIfNotIterated() {
      Graph<String> graph = Graph.of(3);
      assertThrows(IndexOutOfBoundsException.class, () -> graph.edges(3));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.edges(-1));
    }
  }


  @Nested
  public final class Q8 {

    @Test
    public void testRemoveEdgeReturnsTheValue() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      assertEquals("a", graph.removeEdge(0, 1));
    }

    @Test
    public void testRemoveEdgeReturnsNullWhenThereIsNoEdge() {
      Graph<String> graph = Graph.of(4);
      assertNull(graph.removeEdge(0, 1));
    }

    @Test
    public void testRemoveEdgeTwice() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      assertEquals("a", graph.removeEdge(0, 1));
      assertNull(graph.removeEdge(0, 1));
    }

    @Test
    public void testGetEdgeAfterRemove() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.removeEdge(0, 1);
      assertEquals(Optional.empty(), graph.getEdge(0, 1));
    }

    @Test
    public void testRemoveEdgeUpdatesEdgeCount() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.removeEdge(0, 1);
      assertEquals(1, graph.edgeCount());
      graph.removeEdge(0, 2);
      assertEquals(0, graph.edgeCount());
    }

    @Test
    public void testRemoveMissingEdgeDoesNotChangeEdgeCount() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.removeEdge(0, 2);
      graph.removeEdge(0, 2);
      graph.removeEdge(3, 3);
      assertEquals(1, graph.edgeCount());
    }

    @Test
    public void testRemoveEdgeKeepsTheOtherEdges() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(1, 1, "c");
      graph.removeEdge(0, 1);
      assertEquals(Optional.of("b"), graph.getEdge(0, 2));
      assertEquals(Optional.of("c"), graph.getEdge(1, 1));
    }

    @Test
    public void testRemoveEdgeIsDirected() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(1, 0, "b");
      assertEquals("a", graph.removeEdge(0, 1));
      assertEquals(Optional.of("b"), graph.getEdge(1, 0));
    }

    @Test
    public void testRemoveSelfLoop() {
      Graph<String> graph = Graph.of(2);
      graph.addEdge(1, 1, "loop");
      assertEquals("loop", graph.removeEdge(1, 1));
      assertEquals(0, graph.edgeCount());
    }

    @Test
    public void testAddEdgeAfterRemove() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.removeEdge(0, 1);
      assertNull(graph.addEdge(0, 1, "b"));
      assertEquals(Optional.of("b"), graph.getEdge(0, 1));
      assertEquals(1, graph.edgeCount());
    }

    @Test
    public void testEdgesAndNeighborsAfterRemove() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(0, 3, "c");
      graph.removeEdge(0, 2);

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(List.of(
          new Graph.Edge<>(0, 1, "a"),
              new Graph.Edge<>(0, 3, "c")),
          edges);
      assertEquals(List.of(1, 3), graph.neighbors(0).boxed().toList());
    }

    @Test
    public void testRemoveEdgeThrowsOnInvalidVertices() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(1, 0, "a");
      assertThrows(IndexOutOfBoundsException.class, () -> graph.removeEdge(-1, 0));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.removeEdge(3, 0));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.removeEdge(0, -1));
      assertThrows(IndexOutOfBoundsException.class, () -> graph.removeEdge(0, 3));

      assertEquals(Optional.of("a"), graph.getEdge(1, 0));
      assertEquals(1, graph.edgeCount());
    }

    @Test
    public void testRemoveAllEdges() {
      Graph<Integer> graph = Graph.of(1_000);
      for (var from = 0; from < 1_000; from++) {
        for (var to = 0; to < 1_000; to++) {
          graph.addEdge(from, to, from * 1_000 + to);
        }
      }
      for (var from = 0; from < 1_000; from++) {
        for (var to = 0; to < 1_000; to++) {
          assertEquals(from * 1_000 + to, graph.removeEdge(from, to));
        }
      }
      assertEquals(0, graph.edgeCount());
    }
  }


  @Nested
  public final class Q9 {

    @Test
    public void testRemoveAfterNextRemovesTheEdgeFromTheGraph() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();
      assertEquals(Optional.empty(), graph.getEdge(0, 1));
    }

    @Test
    public void testRemoveKeepsTheOtherEdges() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(List.of(new Graph.Edge<>(0, 2, "b")), edges);
    }

    @Test
    public void testRemoveUpdatesEdgeCount() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(1, 1, "c");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();
      assertEquals(2, graph.edgeCount());
    }

    @Test
    public void testRemoveDoesNotTouchOtherRows() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(1, 1, "b");
      graph.addEdge(2, 1, "c");
      var iterator = graph.edges(1).iterator();
      iterator.next();
      iterator.remove();
      assertEquals(Optional.of("a"), graph.getEdge(0, 1));
      assertEquals(Optional.empty(), graph.getEdge(1, 1));
      assertEquals(Optional.of("c"), graph.getEdge(2, 1));
    }

    @Test
    public void testIterationContinuesAfterRemove() {
      Graph<Integer> graph = Graph.of(4);
      graph.addEdge(2, 1, 10);
      graph.addEdge(2, 3, 20);
      var iterator = graph.edges(2).iterator();
      iterator.next();
      iterator.remove();
      assertTrue(iterator.hasNext());
      assertEquals(new Graph.Edge<>(2, 3, 20), iterator.next());
      assertFalse(iterator.hasNext());
    }

    @Test
    public void testRemoveAfterHasNextRemovesTheLastReturnedEdge() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      assertTrue(iterator.hasNext());   // may have moved on to (0, 2)
      iterator.remove();
      assertEquals(Optional.empty(), graph.getEdge(0, 1));
      assertEquals(Optional.of("b"), graph.getEdge(0, 2));
    }

    @Test
    public void testRemoveTheLastEdgeOfARow() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 2, "a");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      assertFalse(iterator.hasNext());
      iterator.remove();
      assertEquals(Optional.empty(), graph.getEdge(0, 2));
      assertEquals(0, graph.edgeCount());
      assertFalse(iterator.hasNext());
    }

    @Test
    public void testRemoveEveryEdgeOneByOne() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 0, "self");
      graph.addEdge(0, 2, "other");
      var iterator = graph.edges(0).iterator();
      assertEquals(0, iterator.next().to());
      iterator.remove();
      assertEquals(2, iterator.next().to());
      iterator.remove();
      assertFalse(iterator.hasNext());
      assertEquals(0, graph.edgeCount());
      assertFalse(graph.edges(0).iterator().hasNext());
    }

    @Test
    public void testRemoveSomeEdgesWhileIterating() {
      Graph<Integer> graph = Graph.of(8);
      for (var to = 0; to < 8; to++) {
        graph.addEdge(0, to, to);
      }
      var iterator = graph.edges(0).iterator();
      while (iterator.hasNext()) {
        if (iterator.next().value() % 2 == 0) {
          iterator.remove();
        }
      }
      assertEquals(List.of(1, 3, 5, 7), graph.neighbors(0).boxed().toList());
      assertEquals(4, graph.edgeCount());
    }

    @Test
    public void testRemoveAllWithALargeNumberOfEdges() {
      Graph<String> graph = Graph.of(10_000);
      for (var to = 0; to < 10_000; to++) {
        graph.addEdge(0, to, "edge" + to);
      }
      var iterator = graph.edges(0).iterator();
      var count = 0;
      while (iterator.hasNext()) {
        assertEquals("edge" + count, iterator.next().value());
        iterator.remove();
        count++;
      }
      assertEquals(10_000, count);
      assertEquals(0, graph.edgeCount());
    }

    @Test
    public void testRemoveThrowsIllegalStateExceptionBeforeNext() {
      Graph<String> graph = Graph.of(2);
      graph.addEdge(0, 1, "a");
      var iterator = graph.edges(0).iterator();
      assertThrows(IllegalStateException.class, iterator::remove);
      assertEquals(Optional.of("a"), graph.getEdge(0, 1));
    }

    @Test
    public void testRemoveThrowsIllegalStateExceptionOnAnEmptyRow() {
      Graph<String> graph = Graph.of(2);
      var iterator = graph.edges(0).iterator();
      assertThrows(IllegalStateException.class, iterator::remove);
    }

    @Test
    public void testRemoveThrowsIllegalStateExceptionWhenCalledTwice() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();
      assertThrows(IllegalStateException.class, iterator::remove);
      // the second edge must not have been removed by the failing call
      assertEquals(Optional.of("b"), graph.getEdge(0, 2));
    }

    @Test
    public void testRemoveThrowsIllegalStateExceptionWhenHasNextIsCalledBetween() {
      Graph<String> graph = Graph.of(3);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();
      assertTrue(iterator.hasNext());
      assertThrows(IllegalStateException.class, iterator::remove);
      assertEquals(Optional.of("b"), graph.getEdge(0, 2));
    }

    @Test
    public void testRemoveIsPossibleAgainAfterANewNext() {
      Graph<String> graph = Graph.of(4);
      graph.addEdge(0, 1, "a");
      graph.addEdge(0, 2, "b");
      graph.addEdge(0, 3, "c");
      var iterator = graph.edges(0).iterator();
      iterator.next();
      iterator.remove();
      iterator.next();
      iterator.remove();

      var edges = new ArrayList<Graph.Edge<String>>();
      graph.edges(0).forEach(edges::add);

      assertEquals(List.of(new Graph.Edge<>(0, 3, "c")), edges);
    }
  }
}