module Dijkstra(dijkstra_shortest_paths, Comparer, Combiner) where
  import Graph
  import PropertyMap
  import Queue
  import BFS
  import Relax

  type ParentMap v = FMap v v
  data State d p w = St d p w

  data DijsktraBFSVis n = DijVis (Combiner n) (Comparer n)

  instance (Graph g e v, Ord v, Ord e, Ord n, 
    ReadWritePropertyMap d v n, ReadPropertyMap w e n, 
    UpdateablePriorityQueue q n v d) => 
    BFSVisitor (DijsktraBFSVis n) q (State d (ParentMap v) w) g e v 
    where
    tree_edge (DijVis plus less) e g q (St d1 p1 w) =
      let (d2, p2, decreased) = relax e g w d1 p1 plus less
      in ((St d2 p2 w), q)

    gray_target (DijVis plus less) e g q1 (St d1 p1 w) =
      let (d2, p2, decreased) = relax e g w d1 p1 plus less
      in if (decreased) then 
	   let q2 = update d2 (tgt e g) q1
	   in ((St d2 p2 w), q2)
	 else
	   ((St d2 p2 w), q1)

  dijkstra_shortest_paths ::
    (VertexListGraph g v, IncidenceGraph g e v, Ord v, Ord e, Ord n,
     ReadWritePropertyMap d v n, ReadPropertyMap w e n) =>
    g -> v -> d -> w -> (Comparer n) -> (Combiner n) -> n
      -> (d, (ParentMap v))
  dijkstra_shortest_paths g s d1 w less plus zero =
    let d2 = put d1 s zero
        p2 = create_map [(v,v) | v <- vertices g ] s
        h = make_heap d2
        bfs_vis = DijVis plus less
        init_st = St d2 p2 w
        c = init_map (vertices g) White
    in let (St d3 p3 w2) = breadth_first_visit g s bfs_vis init_st h c
       in (d3,p3)