// Copyright 2003, Trustees of Indiana University
// Please see the license in the file ../LICENSE

// dijkstra_shortest_paths algorithm from BFS

using GCollections;

public class negative_edge: System.Exception {}

public class indirect_cmp<
  Vertex,
  Distance,
  DistanceMap,
  DistanceCompare>
  : StrictWeakOrdering<Vertex>
  where DistanceMap: ReadablePropertyMap<Vertex, Distance>,
	DistanceCompare: StrictWeakOrdering<Distance> {
  private DistanceMap m_distance;
  private DistanceCompare m_compare;

  public indirect_cmp(DistanceMap distance, DistanceCompare compare) {
    m_distance = distance;
    m_compare = compare;
  }

  public bool less(Vertex a, Vertex b) {
    return m_compare.less(((ReadablePropertyMap<Vertex,Distance>)m_distance)[a], ((ReadablePropertyMap<Vertex,Distance>)m_distance)[b]);
  }
}

public class dijkstra_visitor<
	      Graph,
	      QueueType,
	      WeightMap,
	      PredecessorMap,
	      DistanceMap,
	      DistanceCombine,
	      DistanceCompare,
	      Vertex,
	      Edge,
	      Distance>
       : Visitor<Graph, Vertex, Edge>
    where QueueType: MutableQueue<Vertex>,
	  WeightMap: ReadablePropertyMap<Edge,Distance>,
	  PredecessorMap: ReadWritePropertyMap<Vertex,Vertex>,
	  DistanceMap: ReadWritePropertyMap<Vertex,Distance>,
	  DistanceCombine: BinaryFunction<Distance>,
	  DistanceCompare: StrictWeakOrdering<Distance>,
	  Edge: GraphEdge<Vertex> {
  private WeightMap m_weight;
  private DistanceCompare m_compare;
  private DistanceCombine m_combine;
  private Distance m_zero;
  private DistanceMap m_distance;
  private PredecessorMap m_predecessor;
  private QueueType m_Q;

  public dijkstra_visitor(QueueType Q, WeightMap weight, PredecessorMap predecessor, DistanceMap distance, DistanceCombine combine, DistanceCompare compare, Distance zero) {
    m_Q = Q;
    m_weight = weight;
    m_predecessor = predecessor;
    m_distance = distance;
    m_combine = combine;
    m_compare = compare;
    m_zero = zero;
  }

  public void initialize_vertex(Vertex u, Graph g) {}
  public void discover_vertex(Vertex u, Graph g) {}
  public void examine_edge(Edge e, Graph g) {
    if (m_compare.less(((ReadablePropertyMap<Edge,Distance>)m_weight)[e], m_zero))
      throw new negative_edge();
  }
  public void tree_edge(Edge e, Graph g) {
    relax.go<Vertex,Edge,WeightMap,Distance,DistanceMap,PredecessorMap,DistanceCombine,DistanceCompare>(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
  }
  public void non_tree_edge(Edge e, Graph g) {}
  public void gray_target(Edge e, Graph g) {
    bool relaxed = relax.go<Vertex,Edge,WeightMap,Distance,DistanceMap,PredecessorMap,DistanceCombine,DistanceCompare>(e, m_weight, m_distance, m_predecessor, m_combine, m_compare);
    if (relaxed)
      m_Q.update(e.target);
  }
  public void black_target(Edge e, Graph g) {}
  public void finish_vertex(Vertex u, Graph g) {}
}

public class dijkstra_shortest_paths {
  public static void go<
    GraphT,
    Vertex,
    Edge,
    VertexIterator,
    OutEdgeIterator,
    WeightMap,
    DistanceMap,
    Distance,
    PredecessorMap,
    DistanceCombine,
    DistanceCompare>
  (GraphT g, Vertex s, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, DistanceCompare compare, DistanceCombine combine, Distance inf, Distance zero)
    where GraphT: VertexListAndIncidenceGraph<Vertex,Edge,VertexIterator,OutEdgeIterator>,
	  Edge: GraphEdge<Vertex>,
	  VertexIterator: IEnumerable<Vertex>,
	  OutEdgeIterator: IEnumerable<Edge>,
	  WeightMap: ReadablePropertyMap<Edge,Distance>,
	  DistanceMap: ReadWritePropertyMap<Vertex,Distance>,
	  PredecessorMap: ReadWritePropertyMap<Vertex,Vertex>,
	  DistanceCombine: BinaryFunction<Distance>,
	  DistanceCompare: StrictWeakOrdering<Distance> {
    for (IEnumerator<Vertex> ui = g.vertices().GetEnumerator(); ui.MoveNext();) {
      Vertex u = ui.Current;
      ((ReadWritePropertyMap<Vertex,Distance>)distance)[u] = inf;
      ((ReadWritePropertyMap<Vertex,Vertex>)predecessor)[u] = u;
    }
    ((ReadWritePropertyMap<Vertex,Distance>)distance)[s] = zero;

    indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> icmp 
      = new indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>(distance, compare);

    mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> > Q 
      = new mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> >(icmp);

    dijkstra_visitor<GraphT, mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> >, WeightMap, PredecessorMap, DistanceMap, DistanceCombine, DistanceCompare, Vertex, Edge, Distance> vis 
      = new dijkstra_visitor<GraphT, mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> >, WeightMap, PredecessorMap, DistanceMap, DistanceCombine, DistanceCompare, Vertex, Edge, Distance>(Q, weight, predecessor, distance, combine, compare, zero);

    hash_property_map<Vertex, ColorValue> color
      = new hash_property_map<Vertex, ColorValue>();

    // Initialize color map
    for (IEnumerator<Vertex> ui = g.vertices().GetEnumerator(); ui.MoveNext();) {
      Vertex v = ui.Current;
      color[v] = ColorValue.white;
    }

    graph_search.go<
      GraphT,
      Vertex,
      Edge,
      VertexIterator,
      OutEdgeIterator,
      dijkstra_visitor<
	GraphT,
	mutable_queue<
	  Vertex, 
	  indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> >,
	WeightMap, 
	PredecessorMap, 
	DistanceMap, 
	DistanceCombine, 
	DistanceCompare, 
	Vertex, 
	Edge, 
	Distance>,
      hash_property_map<Vertex,ColorValue>,
      mutable_queue<Vertex,indirect_cmp<Vertex,Distance,DistanceMap,DistanceCompare> > >
      (g, s, vis, color, Q);
  }
}