(* GRAPH *)

class virtual graf = object(self)
  method virtual is_vertex: int -> bool
  method virtual add_vertex: int -> unit
  val mutable size = 0
  method size = size
  method virtual is_wedge: int -> int -> bool
  method virtual add_wedge: int -> int -> unit
  method virtual reset: int -> unit
  method virtual is_neighbor: int -> bool
  method virtual neighbor: int -> int
  method virtual getnext: int -> unit
  method for_neighbors (x:int) (f: int -> unit) =
     self#reset x;
     while (self#is_neighbor x) do
       f (self#neighbor x);
       self#getnext x
     done
  method is_path l = match l with
     a::b::t -> (self#is_wedge a b)&&(self#is_path (b::t)) |
     _ -> true
end;;

(* GRAPH with WEIGTHS *)
let rec all_ints s = get_ints s 0
 and
  get_ints s i = let j1 = digpos s i in
   if (j1 < i) then [] else
   let j2 = nondigpos s j1 in (int_of_string (String.sub s j1 (j2-j1)))::(get_ints s j2)
 and
  digpos s i = if (i >= String.length s) then -1 else match s.[i] with '0'..'9' -> i | _ -> digpos s (i+1)
 and
  nondigpos s i = if (i >= String.length s) then i else match s.[i] with '0'..'9' -> nondigpos s (i+1) | _ -> i;;

exception Wrong_input;;
class virtual wgraf = object(self)
  inherit graf
  method virtual weight: int -> int -> int
  method virtual add_weight: int -> int -> int -> unit
  method path_weight l = match l with
     a::b::t -> (self#weight a b)+(self#path_weight (b::t)) |
     _ -> 0
  method read s = let ic = open_in s in
     let l = ref [] in
     while try l:=all_ints(input_line ic); true with _ -> false do
       match !l with a::b::c::t -> self#add_weight a b c | _ -> raise Wrong_input
     done
end;;

(* GRAPH WITH WEIGHTS and DIJKSTRA ALGORITHM *)
class virtual dwgraf = object(self)
  inherit wgraf
  val mutable source = 0
  val mutable dist = Array.create 1 10000
  val mutable chosen = Array.create 1 false
  method virtual getmin: unit -> int
  method virtual init_getmin: unit -> unit
  method virtual remake: int -> unit
  method init_dist x =
    source <- x;
    dist <- Array.create (self#size) 10000;
    chosen <- Array.create (self#size) false;
    dist.(x) <- 0;
    chosen.(x) <- true;
    self#for_neighbors x (fun y -> dist.(y) <- self#weight x y);
    self#init_getmin()
  method dijkstra x =
    self#init_dist x;
    let m = ref 0 in
      while try m:=self#getmin(); true with _ -> false do
        chosen.(!m) <- true;
        self#for_neighbors (!m)
          (fun y ->
            if not (chosen.(y)) then
	      begin
		let d = dist.(!m)+self#weight (!m) y in
		  if d < dist.(y) then
		    begin
                      dist.(y) <- d;
                      self#remake (!m)
		    end
              end
          )
       done
end;;

(* Heap *)

class virtual ['a] heap (cmp: 'a -> 'a -> bool) (prn: 'a -> unit) = object(self)
  val mutable arr: 'a array = [||]
  val mutable size = 0
  method size = size
  method resize(a:'a) = let b = Array.create (10+Array.length arr) a in
     for i=0 to self#size-1 do
       b.(i) <- arr.(i)
     done;
     arr <- b
  method add (a:'a) = if (self#size == Array.length arr) then self#resize(a) else arr.(self#size) <- a; size<-self#size+1
  method first() = arr.(0)
  val mcmp = ref cmp
  method change_cmp c = mcmp:=c
  method pass i =
(*    print_string "passing "; print_int i; print_string "\n"; *)
    let j = if ((2*i+1 >= size)or(!mcmp arr.(i) arr.(2*i+1))) then i else 2*i+1 in
    let k = if ((2*i+2 >= size)or(!mcmp arr.(j) arr.(2*i+2))) then j else 2*i+2 in
    if (i != k) then begin
      (let x = arr.(i) in arr.(i) <- arr.(k); arr.(k) <- x);
      self#pass k
    end
  method make_heap() =
    for i=size/2-1 downto 0 do
      self#pass i
    done
  method getmin() =
    let x = arr.(0) in
      arr.(0) <- arr.(size-1);
      size <- size-1;
      self#pass 0;
      x
  method passup i =
(*    print_string "passing UP "; print_int i; print_string "\n"; *)
    if i > 0 then
    let j = (i-1)/2 in if not (!mcmp arr.(j) arr.(i)) then begin
      (let x = arr.(i) in arr.(i) <- arr.(j); arr.(j) <- x);
      self#pass j
    end
  method print() =
    for i=0 to size-1 do
      prn (arr.(i));
      if (i < size-1) then print_string ", "
    done;
    print_string "\n"
end;;

let rec foreach l f = match l with [] -> () | a::t -> f a; foreach t f;;

exception No_elems;;

class ['a] stack = object(self)
  val mutable elems : 'a list = []
  method empty() = (elems = [])
  method on_top() = (match elems with a::l -> a | _ -> raise No_elems)
  method push(a:'a) = elems <- a::elems
  method pop() = (match elems with a::l -> elems <- l; a | _ -> raise No_elems)
  method transfer(s:'a stack) = while(not(self#empty())) do s#push (self#on_top()); self#pop() done
  method foreach (f:'a -> unit) =  foreach elems f
end;;

class ['a] queue = object
  val mutable stack_in : 'a stack = new stack
  val mutable stack_out : 'a stack = new stack
  method empty() = (stack_in#empty() && stack_out#empty())
  method first() = (if (stack_out#empty()) then stack_in#transfer(stack_out);stack_out#on_top())
  method inject(a:'a) = stack_in#push a
  method pop() = (if (stack_out#empty()) then stack_in#transfer(stack_out);stack_out#pop())
end;;

exception End_of_stack;;
class ['a] reviewable_stack = object(self)
  inherit ['a] stack
  val mutable aux : 'a list = []
  method reset() = aux <- elems
  method getnext() = match aux with [] -> () | a::t -> aux <- t
  method eos() = aux = []
  method current() = match aux with [] -> raise No_elems | a::t -> a
  method exists (f:'a->bool) = (List.exists:('a -> bool) -> 'a list -> bool) f (elems: 'a list)
  method find (f:'a->bool) = List.find f elems
end;;

class swgraf = object(self)
  inherit wgraf
  val mutable wedges(* : int*float reviewable_stack array *) = [||]
  method resize a = let b = Array.create a (new reviewable_stack) in
     for i=0 to size-1 do
       b.(i) <- wedges.(i)
     done;
     for i=size to a-1 do
       b.(i) <- new reviewable_stack
     done;
     size <- a;
     wedges <- b
  method reset a = wedges.(a)#reset()
  method is_neighbor a = not (wedges.(a)#eos())
  method neighbor a = fst (wedges.(a)#current())
  method getnext a = wedges.(a)#getnext()
  method add_weight a b w = wedges.(a)#push (b,w)
  method weight a b =
    if fst (wedges.(a)#current()) = b then snd (wedges.(a)#current())
    else 0
  method is_vertex a = a < size
  method add_vertex a = if (a >= size) then self#resize (a+1)
  method is_wedge a b =
    false
  method add_wedge a b = self#add_weight a b 1
end;;

class virtual ddwgraf = object
  inherit dwgraf
  method dist a = dist.(a)
end;;

class ['a] myheap (cmp: 'a -> 'a -> bool) (prn: 'a -> unit) = object inherit ['a] heap cmp prn end;;

class lastgraf n = object(self)
  inherit ddwgraf
  inherit swgraf
  val dheap = new myheap (fun a b -> (a <= b)) (fun a -> print_int a)
  initializer (self#add_vertex (n-1))
  method init_getmin() =
    dheap#change_cmp (fun a b -> (dist.(a)) <= (dist.(b)));
    for i=0 to size-1 do dheap#add i done;
    dheap#make_heap()
  method getmin() = dheap#getmin()
  method remake m =
    dheap#change_cmp (fun a b -> (dist.(a)) <= (dist.(b)));
    dheap#passup m
  method print() =
    for a=0 to size-1 do
      print_int a;
      print_string ": ";
      self#for_neighbors a (fun b -> print_int b; print_string " - "; print_int (self#weight a b); print_string ", ");
      print_string "\n"
    done
  method print_dist() =
    for a=0 to size-1 do
      print_int a;
      print_string ": ";
      print_int dist.(a);
      print_string "\n"
    done
end;;

let g = new lastgraf 6;;
g#read "g.txt";;
g#print();;
g#dijkstra 0;;
g#print_dist();;