package javakurs.musterloesung.uebung08;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * {@link DirectedGraphTest} is a test class for {@link DirectedGraphBase}.
 *
 * @author Joerg Steffen, DFKI
 * @author Bernd Kiefer, DFKI
 * @version $Id: DirectedGraphTest.java,v 1.4 2011/01/12 13:07:41 steffen Exp $
 */
public final class DirectedGraphTest {

  /**
   * This would create a new instance of {@link DirectedGraphTest}. Not to be
   * used.
   */
  private DirectedGraphTest() {

    // private constructor to enforce noninstantiability
  }


  /**
   * Use this example to test your traversal methods.
   *
   * @return the example graph or {@code null} if an error appeared
   */
  public static DirectedGraph<String> getExampleGraph() {

    String graphString =
      "s --> r w\n"
        + "r --> s v\n"
        + "v --> r\n"
        + "w --> s t x\n"
        + "t --> w u x\n"
        + "u --> t y\n"
        + "x --> w t y\n"
        + "y --> x u\n";

    DirectedGraph<String> graph = null;
    try {
      graph = readGraph(new StringReader(graphString));
    } catch (IOException e) {
      e.printStackTrace();
    }
    return graph;
  }


  /**
   * Use this example to test your traversal methods, it's the last example on
   * the slides.
   *
   * @return the example graph or {@code null} if an error appeared
   */
  public static DirectedGraph<String> getTopoExampleGraph() {

    String graphString =
      "shirt --> tie jacket belt\n"
        + "tie --> jacket\n"
        + "belt --> jacket\n"
        + "watch --> \n"
        + "undershorts --> pants shoes\n"
        + "pants --> belt shoes\n"
        + "socks --> shoes\n";

    DirectedGraph<String> graph = null;
    try {
      graph = readGraph(new StringReader(graphString));
    } catch (IOException e) {
      e.printStackTrace();
    }
    return graph;
  }


  /**
   * Creates a graph from a readable specification.
   *
   * @param in
   *          the reader from which to read the graph
   * @return the graph
   * @throws IOException
   *           if there is an error when reading the graph
   */
  public static DirectedGraph<String> readGraph(Reader in)
      throws IOException {

    BufferedReader bin = new BufferedReader(in);

    DirectedGraph<String> result = new DirectedGraph<String>();
    EqualsPredicate<String> eqPred = new EqualsPredicate<String>();

    VertexPropertyMap<String> names = new VertexPropertyMap<String>(result);
    result.register("names", names);

    String nextLine = null;
    while ((nextLine = bin.readLine()) != null) {
      String[] fromTo = nextLine.split("\\s*-->\\s*");
      if (fromTo.length < 1) {
        continue;
      }

      List<Integer> vertices = names.findVertices(fromTo[0], eqPred);
      int from = -1;
      if (vertices.isEmpty()) {
        from = result.newVertex();
        names.put(from, fromTo[0]);
      }
      else {
        from = vertices.get(0);
      }

      if (fromTo.length == 2) {
        String[] token = fromTo[1].split("\\s+");

        for (String name : token) {
          vertices = names.findVertices(name, eqPred);
          int to = -1;
          if (vertices.isEmpty()) {
            to = result.newVertex();
            names.put(to, name);
          }
          else {
            to = vertices.get(0);
          }
          result.newEdge(fromTo[0] + name, from, to);
        }
      }
    }
    return result;
  }


  /**
   * This is the main method. It requires no arguments.
   *
   * @param args
   *          the arguments; not used here
   */
  public static void main(String[] args) {

    // create empty graph
    DirectedGraph<String> graph = new DirectedGraph<String>();

    // vertices have names
    VertexPropertyMap<String> names = new VertexPropertyMap<String>(graph);

    // add some vertices
    int vertexA = graph.newVertex();
    names.put(vertexA, "A");
    int vertexB = graph.newVertex();
    names.put(vertexB, "B");
    int vertexC = graph.newVertex();
    names.put(vertexC, "C");

    // add some edges
    Edge<String> edgeAB = graph.newEdge("ab", vertexA, vertexB);
    graph.newEdge("ac", vertexA, vertexC);
    graph.newEdge("ca", vertexC, vertexA);

    // show result graph
    System.out.println(graph.toString(names));

    // change edge
    graph.changeEndVertex(edgeAB, vertexC);
    // show result graph
    System.out.println("changed 'ab' edge to vertex 'C':");
    System.out.println(graph.toString(names));

    // remove a vertex
    graph.removeVertex(vertexB);
    // show result graph
    System.out.println("graph with vertex 'B' removed:");
    System.out.println(graph.toString(names));

    // get first example graph
    graph = getExampleGraph();
    System.out.println(graph);

    // collect discovery and finish time using DFS
    System.out.println("DFS:");
    CollectTimesVisitor<String> dfsTimesVisitor =
      new CollectTimesVisitor<String>();
    graph.dfs(dfsTimesVisitor);
    names = (VertexPropertyMap<String>)graph.getPropertyMap("names");
    Iterator<Integer> dfsTimesIt = graph.getVerticesIterator();
    while (dfsTimesIt.hasNext()) {
      int v = dfsTimesIt.next();
      System.out.println(names.get(v));
      System.out.println("discovered: "
                         + dfsTimesVisitor.getDiscoveryMap().get(v)
                         + " finished: "
                         + dfsTimesVisitor.getFinishMap().get(v));
      System.out.println();
    }

    // collect discovery and finish time using BFS
    System.out.println("BFS:");
    CollectTimesVisitor<String> bfsTimesVisitor =
      new CollectTimesVisitor<String>();
    graph.bfs(bfsTimesVisitor);
    Iterator<Integer> bfsTimesIt = graph.getVerticesIterator();
    while (bfsTimesIt.hasNext()) {
      int v = bfsTimesIt.next();
      System.out.println(names.get(v));
      System.out.println("discovered: "
                         + bfsTimesVisitor.getDiscoveryMap().get(v)
                         + " finished: "
                         + bfsTimesVisitor.getFinishMap().get(v));
      System.out.println();
    }

    // get topological order
    graph = getTopoExampleGraph();
    System.out.println(graph);
    // calculate tolopogical order
    TopoOrderVisitor<String> topoVisitor = new TopoOrderVisitor<String>();
    graph.dfs(topoVisitor);
    names = (VertexPropertyMap<String>)graph.getPropertyMap("names");
    Iterator<Integer> topoIt = topoVisitor.getSortedVertices().iterator();
    while (topoIt.hasNext()) {
      int v = topoIt.next();
      System.out.println(names.get(v));
    }
  }


  /**
   * {@link EqualsPredicate}is an inner class that defines a functional object
   * used to check if two instances of the argument type are equal.
   *
   * @param <ArgumentType>
   *          the kind of arguments to compare
   */
  public static class EqualsPredicate<ArgumentType>
      implements BinaryPredicate<ArgumentType> {

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean compare(ArgumentType arg1, ArgumentType arg2) {

      return arg1.equals(arg2);
    }
  }

  /**
   * {@link ComparableComparator}is an inner class that defines a functional
   * object used to compare two instances of the argument type using their
   * internal comparison method
   *
   * @param <ArgumentType>
   *          the kind of arguments to compare
   */
  public static class ComparableComparator<ArgumentType extends Comparable>
      implements Comparator<ArgumentType> {

    /**
     * {@inheritDoc}
     */
    @Override
    public int compare(ArgumentType arg1, ArgumentType arg2) {

      return arg1.compareTo(arg2);
    }
  }
}
