/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.datastax.driver.core;

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

import com.datastax.driver.core.exceptions.DriverInternalError;
import java.util.Comparator;
import java.util.List;
import org.testng.annotations.Test;

public class DirectedGraphTest {

  private Comparator<String> alphaComparator =
      new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
          return o1.compareTo(o2);
        }
      };

  @Test(groups = "unit")
  public void should_sort_empty_graph() {
    DirectedGraph<String> g = new DirectedGraph<String>(alphaComparator);
    assertThat(g.topologicalSort()).isEmpty();
  }

  @Test(groups = "unit")
  public void should_sort_graph_with_one_node() {
    DirectedGraph<String> g = new DirectedGraph<String>(alphaComparator, "A");
    assertThat(g.topologicalSort()).containsExactly("A");
  }

  @Test(groups = "unit")
  public void should_sort_complex_graph() {
    //         H   G
    //        / \ /\
    //       F   |  E
    //        \ /  /
    //         D  /
    //        / \/
    //        B  C
    //        |
    //        A
    DirectedGraph<String> g =
        new DirectedGraph<String>(alphaComparator, "A", "B", "C", "D", "E", "F", "G", "H");
    g.addEdge("H", "F");
    g.addEdge("G", "E");
    g.addEdge("H", "D");
    g.addEdge("F", "D");
    g.addEdge("G", "D");
    g.addEdge("D", "C");
    g.addEdge("E", "C");
    g.addEdge("D", "B");
    g.addEdge("B", "A");

    // Topological sort order should be : GH,E,F,D,BC,A
    List<String> sorted = g.topologicalSort();
    assertThat(sorted).containsExactly("G", "H", "E", "F", "D", "B", "C", "A");
  }

  @Test(groups = "unit")
  public void should_sort_complex_custom_comparator() {
    // Version of should_sort_complex_graph using a custom comparator based on ordering largest
    // values first.
    // This is counter to how hashmaps should usually behave, so this should help ensure that the
    // comparator is
    // being used.
    Comparator<Integer> highFirst =
        new Comparator<Integer>() {
          @Override
          public int compare(Integer o1, Integer o2) {
            return o2 - o1;
          }
        };

    // sort graph and use a alphaComparator that favors larger values ordered first.
    //         7   6
    //        / \ /\
    //       5   | 10
    //        \ /  /
    //         9  /
    //        / \/
    //        1  2
    //        |
    //        0
    DirectedGraph<Integer> g = new DirectedGraph<Integer>(highFirst, 0, 1, 2, 9, 10, 5, 6, 7);
    g.addEdge(7, 5);
    g.addEdge(6, 10);
    g.addEdge(7, 9);
    g.addEdge(5, 9);
    g.addEdge(6, 9);
    g.addEdge(9, 2);
    g.addEdge(10, 2);
    g.addEdge(9, 1);
    g.addEdge(1, 0);

    // Topological sort order should be : [7,6],[5],[10],[9],[2,1],[0]
    // 5 comes before 10 even though they appear at the same depth.  This happens because 5's (7)
    // dependency
    // is evaluated before 10's (6), so it is placed first.
    List<Integer> sorted = g.topologicalSort();
    assertThat(sorted).containsExactly(7, 6, 5, 10, 9, 2, 1, 0);
  }

  @Test(groups = "unit", expectedExceptions = DriverInternalError.class)
  public void should_fail_to_sort_if_graph_has_a_cycle() {
    DirectedGraph<String> g = new DirectedGraph<String>(alphaComparator, "A", "B", "C");
    g.addEdge("A", "B");
    g.addEdge("B", "C");
    g.addEdge("C", "B");

    g.topologicalSort();
  }

  @Test(groups = "unit", expectedExceptions = DriverInternalError.class)
  public void should_fail_to_sort_if_graph_is_a_cycle() {
    DirectedGraph<String> g = new DirectedGraph<String>(alphaComparator, "A", "B", "C");
    g.addEdge("A", "B");
    g.addEdge("B", "C");
    g.addEdge("C", "A");

    g.topologicalSort();
  }
}
