(*
 * bfs_test.sml - test out breadth-first search
 *   Ronald Garcia
 *   $Id: bfs_test.sml,v 1.2 2003/05/02 20:03:37 jewillco Exp $
 *)

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


use "adj_list.sml";
use "bfs.sml";
use "queue.sml";


(* RG : For now, I wrap a preexisting Queue to meet concept needs.
 * Later I may want to modify the original queue interface.
 *)

structure BFSQueue  = 
struct
    type data_t = ALGraph.vertex_t Queue.Queue
    type value_t = ALGraph.vertex_t 

    fun push queue x = (Queue.insert queue x; ())

    fun pop queue =
	let
	    val result = Queue.front(queue)
	in
	    (Queue.delete(queue); result)
	end
    fun empty queue = Queue.empty(queue)
    
    fun create () = (Queue.create(): data_t)
end;

structure printV (*: BFSVisitor*) =
struct
    type data_t = unit
    type graph_t = ALGraph.graph_t
    type vertex_t = ALGraph.vertex_t
    type edge_t = ALGraph.edge_t

    type vertex_fn = data_t -> vertex_t -> graph_t -> unit;
    type edge_fn = data_t -> edge_t -> graph_t -> unit;

    fun create() = ()

    fun edge (src,tgt) =
        "(" ^ Int.toString(src) ^ "," ^ Int.toString(tgt) ^ ")"

    fun initialize_vertex () v g =
        print ("initialize vertex " ^ Int.toString(v) ^ "\n")

    fun discover_vertex () v g =
        print("discover vertex " ^ Int.toString(v) ^ "\n")

    fun examine_vertex () v g = 
        print("examine vertex " ^ Int.toString(v) ^ "\n")

    fun examine_edge () e g = 
        print("examine edge " ^ edge(e) ^ "\n")

    fun tree_edge () e g = 
        print("tree edge " ^ edge(e) ^ "\n")

    fun non_tree_edge () e g =
        print("non-tree edge " ^ edge(e) ^ "\n")

    fun gray_target () (src,v) g =
        print("gray target " ^ Int.toString(v) ^ "\n")

    fun black_target () (src,v) g =
        print("black target " ^ Int.toString(v) ^ "\n")

    fun finish_vertex () v g =
        print("finish vertex " ^ Int.toString(v) ^ "\n")

end;


structure BFS = 
MakeBFS(struct 
             structure IncidenceGraph = ALGraph
             structure VertexListGraph = ALGraph
             structure ColorMap = ALGColorMap
             structure Queue = BFSQueue
             structure Visitor = printV
           end)

val x = ALGraph.create(4);

ALGraph.add_edge(x,0,1);
ALGraph.add_edge(x,1,2);
ALGraph.add_edge(x,0,3);
ALGraph.add_edge(x,3,1);
ALGraph.add_edge(x,2,0);

BFS.breadth_first_search x (hd (ALGraph.vertices(x))) (BFSQueue.create()) 
	                 (printV.create()) (ALGColorMap.create(x));