import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.List;

public class Graph<T extends Comparable<T>> {
  private List<Vertex<T>> verticies = new CopyOnWriteArrayList<Vertex<T>>();
  private List<Edge<T>> edges = new CopyOnWriteArrayList<Edge<T>>();

  public enum TYPE {
      DIRECTED, UNDIRECTED
  };

  private TYPE type = TYPE.UNDIRECTED;

  public Graph(){

  }
  public Graph(Graph<T> g) {
      // Deep copies

      // Copy the vertices (which copies the edges)
      for (Vertex<T> v : g.getVerticies()) {
          this.verticies.add(new Vertex<T>(v));
      }

      // Update the object references
      for (Vertex<T> v : this.verticies) {
          for (Edge<T> e : v.getEdges()) {
              Vertex<T> fromVertex = e.getFromVertex();
              Vertex<T> toVertex = e.getToVertex();
              int indexOfFrom = this.verticies.indexOf(fromVertex);
              e.from = this.verticies.get(indexOfFrom);
              int indexOfTo = this.verticies.indexOf(toVertex);
              e.to = this.verticies.get(indexOfTo);
              this.edges.add(e);
          }
      }

      type = g.getType();
  }
  public Graph(TYPE type) {
      this();
      this.type = type;
  }

  public Graph(List<Vertex<T>> verticies, List<Edge<T>> edges) {
      this(TYPE.UNDIRECTED, verticies, edges);
  }
  public Graph(TYPE type, List<Vertex<T>> verticies, List<Edge<T>> edges) {
      this(type);
      this.verticies.addAll(verticies);
      this.edges.addAll(edges);

      for (Edge<T> e : edges) {
          Vertex<T> from = e.from;
          Vertex<T> to = e.to;

          if (!this.verticies.contains(from) || !this.verticies.contains(to))
              continue;

          int index = this.verticies.indexOf(from);
          Vertex<T> fromVertex = this.verticies.get(index);
          index = this.verticies.indexOf(to);
          Vertex<T> toVertex = this.verticies.get(index);
          fromVertex.addEdge(e);
          if (this.type == TYPE.UNDIRECTED) {
              Edge<T> reciprical = new Edge<T>(e.cost, toVertex, fromVertex);
              toVertex.addEdge(reciprical);
              this.edges.add(reciprical);
          }
      }
  }
  public TYPE getType() {
      return type;
  }

  public List<Vertex<T>> getVerticies() {
      return verticies;
  }

  public List<Edge<T>> getEdges() {
      return edges;
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public String toString() {
      StringBuilder builder = new StringBuilder();
      for (Vertex<T> v : verticies) {
          builder.append(v.toString());
      }
      return builder.toString();
  }

  // 정점
  public static class Vertex<T extends Comparable<T>> implements Comparable<Vertex<T>>{
    private T value = null;
    private int weight = 0;
    private List<Edge<T>> edges = new ArrayList<Edge<T>>();

    public Vertex(T value){
      this.value = value;
    }
    public Vertex(T value, int weight) {
        this(value);
        this.weight = weight;
    }

    public Vertex(Vertex<T> vertex) {
        this(vertex.value, vertex.weight);
        this.edges = new ArrayList<Edge<T>>();
        for (Edge<T> e : vertex.edges) {
            this.edges.add(new Edge<T>(e));
        }
    }
    public T getValue(){
      return value;
    }

    public int getWeight(){
      return weight;
    }

    public void setWeight(int weight){
      this.weight = weight;
    }

    public void addEdge(Edge<T> e){
      edges.add(e);
    }

    public List<Edge<T>> getEdges(){
      return edges;
    }
    public boolean pathTo(Vertex<T> v) {
        for (Edge<T> e : edges) {
            if (e.to.equals(v))
                return true;
        }
        return false;
    }
    @Override
    public int compareTo(Vertex<T> v) {
      if (this.value == null || v.value == null)
          return -1;
      return this.value.compareTo(v.value);
    }
    @SuppressWarnings("unchecked")
    @Override
    public boolean equals(Object v1) {
        if (!(v1 instanceof Vertex))
            return false;

        Vertex<T> v = (Vertex<T>) v1;

        boolean values = this.value.equals(v.value);
        if (!values)
            return false;

        boolean weight = this.weight == v.weight;
        if (!weight)
            return false;

        return true;
    }
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("vertex:").append(" value=").append(value).append(" weight=").append(weight).append("\n");
        for (Edge<T> e : edges) {
            builder.append("\t").append(e.toString());
        }
        return builder.toString();
    }
  }

  // 간선
  public static class Edge<T extends Comparable<T>> implements Comparable<Edge<T>> {

      private Vertex<T> from = null;
      private Vertex<T> to = null;
      private int cost = 0;

      public Edge(int cost, Vertex<T> from, Vertex<T> to) {
          if (from == null || to == null)
              throw (new NullPointerException("Both 'to' and 'from' Verticies need to be non-NULL."));
          this.cost = cost;
          this.from = from;
          this.to = to;
      }

      public Edge(Edge<T> e) {
          this(e.cost, e.from, e.to);
      }

      public int getCost() {
          return cost;
      }

      public void setCost(int cost) {
          this.cost = cost;
          ;
      }

      public Vertex<T> getFromVertex() {
          return from;
      }

      public Vertex<T> getToVertex() {
          return to;
      }

      @Override
      public int compareTo(Edge<T> e) {
          if (this.cost < e.cost)
              return -1;
          if (this.cost > e.cost)
              return 1;
          return 0;
      }

      @Override
      public int hashCode() {
          return this.cost * (this.getFromVertex().value.hashCode() * this.getToVertex().value.hashCode());
      }

      @SuppressWarnings("unchecked")
      @Override
      public boolean equals(Object e1) {
          if (!(e1 instanceof Edge))
              return false;

          Edge<T> e = (Edge<T>) e1;

          boolean costs = this.cost == e.cost;
          if (!costs)
              return false;

          boolean froms = this.from.equals(e.from);
          if (!froms)
              return false;

          boolean tos = this.to.equals(e.to);
          if (!tos)
              return false;

          return true;
      }

      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          builder.append("edge:").append(" [").append(from.value).append("]").append(" -> ").append("[")
                  .append(to.value).append("]").append(" = ").append(cost).append("\n");
          return builder.toString();
      }
  }

  // 경로 테이블 만들때 Vertex 와 Cost 쌍
  public static class CostVertexPair<T extends Comparable<T>> implements Comparable<CostVertexPair<T>> {

      private int cost = Integer.MAX_VALUE;
      private Vertex<T> vertex = null;

      public CostVertexPair(int cost, Vertex<T> vertex) {
          if (vertex == null)
              throw (new NullPointerException("vertex cannot be NULL."));

          this.cost = cost;
          this.vertex = vertex;
      }

      public int getCost() {
          return cost;
      }

      public void setCost(int cost) {
          this.cost = cost;
      }

      public Vertex<T> getVertex() {
          return vertex;
      }

      @Override
      public int compareTo(CostVertexPair<T> p) {
          if (p == null)
              throw new NullPointerException("CostVertexPair 'p' must be non-NULL.");
          if (this.cost < p.cost)
              return -1;
          if (this.cost > p.cost)
              return 1;
          return 0;
      }

      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          builder.append("Vertex=").append(vertex.getValue()).append(" cost=").append(cost).append("\n");
          return builder.toString();
      }
  }

  // 경로 path pair
  public static class CostPathPair<T extends Comparable<T>> {

      private int cost = 0;
      private Set<Edge<T>> path = null;

      public CostPathPair(int cost, Set<Edge<T>> path) {
          if (path == null)
              throw (new NullPointerException("path cannot be NULL."));

          this.cost = cost;
          this.path = path;
      }

      public int getCost() {
          return cost;
      }

      public void setCost(int cost) {
          this.cost = cost;
      }

      public Set<Edge<T>> getPath() {
          return path;
      }

      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          builder.append("Cost = ").append(cost).append("\n");
          for (Edge<T> e : path) {
              builder.append("\t").append(e);
          }
          return builder.toString();
      }
  }
}