package com.hubspot.blazar.data.util;

import static org.assertj.core.api.Assertions.assertThat;

import java.util.Arrays;

import org.junit.Test;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSetMultimap;
import com.google.common.collect.SetMultimap;

public class GraphUtilsTest {
  private static final SetMultimap<Integer, Integer> EDGES = ImmutableSetMultimap.<Integer, Integer>builder()
      .put(1, 2)
      .put(1, 3)
      .put(3, 4)
      .put(3, 5)
      .put(4, 5)
      .put(5, 2)
      .build();

  private static final SetMultimap<Integer, Integer> REDUCED = ImmutableSetMultimap.<Integer, Integer>builder()
      //.put(1, 2) Not in transitive reduction, handled by 1 -> 3 -> 4 -> 5 -> 2
      .put(1, 3)
      .put(3, 4)
      //.put(3, 5) Not in transitive reduction, handled by 3 -> 4 -> 5
      .put(4, 5)
      .put(5, 2)
      .build();

  private static final SetMultimap<Integer, Integer> RETAINED = ImmutableSetMultimap.<Integer, Integer>builder()
      .put(1, 5)
      .build();

  private static final SetMultimap<Integer, Integer> BLAZAR = ImmutableSetMultimap.<Integer, Integer>builder()
      .put(278, 280)
      .put(280, 277)
      .put(280, 281)
      .put(280, 279)
      .put(279, 276)
      .build();

  @Test
  public void testTransitiveReduction() {
    assertThat(GraphUtils.INSTANCE.transitiveReduction(EDGES).asMap()).isEqualTo(REDUCED.asMap());
  }

  @Test
  public void testTopologicalSort() {
    assertThat(GraphUtils.INSTANCE.topologicalSort(REDUCED)).isEqualTo(Arrays.asList(1, 3, 4, 5, 2));
  }

  @Test
  public void testBlazarTopologicalSort() {
    assertThat(GraphUtils.INSTANCE.topologicalSort(BLAZAR)).isEqualTo(Arrays.asList(278, 280, 277, 279, 281, 276));
  }

  @Test
  public void testRetain() {
    assertThat(GraphUtils.INSTANCE.retain(EDGES, ImmutableSet.of(1, 5)).asMap()).isEqualTo(RETAINED.asMap());
  }
}

@@ -120,32 +120,239 @@
 ys;%0A
-%0Aimport org.junit.Test;%0A
+import java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.Set;%0A%0Aimport org.junit.Test;%0A%0Aimport com.google.common.base.Optional;%0Aimport com.google.common.collect.ImmutableList;
 %0Aimp
@@ -495,16 +495,103 @@
 ultimap;
+%0Aimport com.hubspot.blazar.base.DependencyGraph;%0Aimport com.hubspot.blazar.base.Module;
 %0A%0Apublic
@@ -1718,32 +1718,1116 @@
 .asMap());%0A  %7D%0A%0A
+  @Test%0A  public void itSortsModulesAccordingToTopologicalSort() %7B%0A    SetMultimap%3CInteger, Integer%3E transitiveReduction = GraphUtils.INSTANCE.transitiveReduction(EDGES);%0A    List%3CInteger%3E topologicalSort = GraphUtils.INSTANCE.topologicalSort(transitiveReduction);%0A    Map%3CInteger, Set%3CInteger%3E%3E tree = new HashMap%3C%3E();%0A    EDGES.entries().stream().forEach(entry -%3E tree.put(entry.getKey(), new HashSet%3C%3E(entry.getValue())));%0A    DependencyGraph graph = new DependencyGraph(tree, topologicalSort);%0A%0A    Set%3CModule%3E modules = ImmutableSet.%3CModule%3Ebuilder()%0A        .add(makeModuleWithId(1))%0A        .add(makeModuleWithId(2))%0A        .add(makeModuleWithId(3))%0A        .add(makeModuleWithId(4))%0A        .add(makeModuleWithId(5))%0A        .build();%0A%0A    List%3CModule%3E expectedOrder = ImmutableList.%3CModule%3Ebuilder()%0A        .add(makeModuleWithId(1))%0A        .add(makeModuleWithId(3))%0A        .add(makeModuleWithId(4))%0A        .add(makeModuleWithId(5))%0A        .add(makeModuleWithId(2))%0A        .build();%0A%0A    assertThat(graph.orderByTopologicalSort(modules)).isEqualTo(expectedOrder);%0A  %7D%0A%0A
   @Test%0A  public
@@ -3286,11 +3286,224 @@
 ());%0A  %7D
+%0A%0A  private static Module makeModuleWithId(int id) %7B%0A    return new Module(Optional.of(id), %22test-module%22, %22config%22, %22/%22, %22/*%22, true, System.currentTimeMillis(), System.currentTimeMillis(), Optional.absent());%0A  %7D
 %0A%7D%0A

Test that the sort works