open Types
open Board

(* The maximum number of packages is 10000. *)
let cluster = Array.create 10001 IntSet.empty
let weight_sum = Array.create 10001 0
   
let find_mst() =
    let map = 
	Array.init (!board_height + 2) (function _ -> Array.create (!board_width + 2) (-1))
    in
    let board = !board in
    let continuation = ref [] in
    let weight_margin = !max_weight in
    let add_edge n1 n2 =
	let n1, n2 = if n1 < n2 then n1, n2 else n2, n1 in
	if not (IntSet.mem n2 cluster.(n1)) then begin
	    let index1, index2 =
		IntSet.min_elt cluster.(n1), IntSet.min_elt cluster.(n2)
	    in
	    let weight1, weight2 = weight_sum.(index1), weight_sum.(index2) in
	    if weight1 + weight2 <= weight_margin then begin
		let new_cluster = IntSet.union cluster.(n1) cluster.(n2) in
		IntSet.iter (function n -> cluster.(n) <- new_cluster) new_cluster;
		weight_sum.(index1) <- weight1 + weight2
	    end
	end
    in
    let visit id x y =
	match board.(y).(x) with
	    Water -> ()
	  | Wall -> ()
	  | Plain | Home _ ->
	      let n = map.(y).(x) in
	      if n = -1 then begin
		  map.(y).(x) <- id;
		  continuation := ( id, x, y )::!continuation
	      end
	      else if n = id then
		  ()
	      else 
		  add_edge n id
    in
    let my_loc = my_loc() in
    let setup n = function
	Some pack_info, Yes loc ->
	  if loc = my_loc then begin
	      weight_sum.(n) <- pack_info.weight;
	      cluster.(n) <- IntSet.singleton n
	  end
	  else
	      cluster.(n) <- IntSet.empty
      |	_ -> 
	  cluster.(n) <- IntSet.empty
    in
    IntMap.iter setup (!packs);
    let setup_my_pack n =
	match IntMap.find n (!packs) with
	    Some pack_info, _ ->
	      weight_sum.(n) <- pack_info.weight;
	      cluster.(n) <- IntSet.singleton n
	  | _ -> 
	      cluster.(n) <- IntSet.empty
    in
    IntSet.iter setup_my_pack (my_pack());
    let place_my_pack n =
	match IntMap.find n (!packs) with
	    Some pack_info, _ -> let x, y = pack_info.dest in visit n x y
	  | _ -> ()
    in
    IntSet.iter place_my_pack (my_pack());
    let place_pack n = function
	Some pack_info, Yes loc ->
	  if loc = my_loc then 
	      let x, y = pack_info.dest in visit n x y
      |	_ -> ()
    in
    IntMap.iter place_pack (!packs);
    while not (!continuation = []) do
	let c = !continuation in
	continuation := [];
	List.iter (function id, x, y ->
	  visit id (x + 1) y;
	  visit id (x - 1) y;
	  visit id x (y + 1);
	  visit id x (y - 1)) c
    done;
    let result = ref [] in
    let print n = function
	Some _, _ ->
	  if not (IntSet.is_empty cluster.(n)) && n = IntSet.min_elt cluster.(n) then begin
(*	      print_string ("cluster "^(string_of_int n)^": "
			    ^(string_of_int weight_sum.(n))^"kg, "); *)
(*	      let l = intset_to_list cluster.(n) in
	      print_string ((Printer.print_int_list l)^"\n"); *)
	      result := ( weight_sum.(n), cluster.(n) )::!result
	  end;
(*	  let l = intset_to_list edge.(n) in
	  print_string ("edge: "^(Printer.print_int_list l)^"\n") *)
	  ()
      |	_ -> ()
    in
    IntMap.iter print (!packs);
    (* List.sort (fun ( n1, _ ) ( n2, _ ) -> compare n2 n1) *) (!result)