(************************************************************
   multimap.ml		Created      : Mon Dec 16 01:11:22 2002
  			Last modified: Wed Dec 25 22:14:41 2002
  Compile: ocamlopt.opt -i multimap.ml -o multimap #
  FTP Directory: sources/ocaml #
************************************************************)
(**
   ないなら作る
  @author Takashi Masuyama <mamewo@dk9.so-net.ne.jp>

*)

(*module MultiMap =*)
(*  struct *)
(*    module Make = functor (Ord : Map.OrderedType)  ->*)
(*      struct*)
(*	module M = Map.Make(Ord)*)
(*	let empty = M.empty*)
(*	    (* 単に値の部分をリストにするだけ。 *)*)
(*	let add k v mm =*)
(*	  try*)
(*	    let lst = M.find k mm in*)
(*	    M.add k (v::lst) mm*)
(*	  with*)
(*	    Not_found -> M.add k [v] mm*)
(*	let find = M.find*)
(*      end*)
(*  end*)

(* extended version *)
module MultiMap =
  struct 
    module Make = functor (Ord : Map.OrderedType)  ->
      struct
	module M = Map.Make(Ord)
	type 'a t = 'a list M.t
	let empty = M.empty
	    (* 単に値の部分をリストにするだけ。 *)
	    (* Setじゃなくてもいいよね          *)
	let find = M.find	    
	let add k v mm =
	  try
	    let lst = find k mm in
	    M.add k (v::lst) mm
	  with
	    Not_found -> M.add k [v] mm
	let iter = M.iter
	    (* 名前がよいかどうかは別として *)
	let fold = M.fold
	let union m1 m2 = 
	  fold (fun k v mm ->
	    try
	      let lst = find k mm in
	      M.add k (v@lst) mm
	    with
	      Not_found -> 
		M.add k v mm) m1 m2
      end
  end

(* ちょっと雰囲気だしてみる?? (Makeとか言ってみる) *)
module StringMM = MultiMap.Make(String)

let print m =
  StringMM.iter (fun x l ->
    print_endline x; 
    List.iter (fun x -> Printf.printf "\t%s\n" x) l) m

let test_union () =
  let test_data = [("aki", "okui"); ("tak", "mamewo"); ("tak", "takashi")] in
  let mm = List.fold_right 
      (fun (k,v) mm ->  StringMM.add k v mm) test_data StringMM.empty in
  let new_mm = StringMM.union mm mm in
  let sample_key = "aki" in
  List.iter print_endline (StringMM.find sample_key new_mm);
  new_mm
      
(* ただのめんどくさがり ↑ ↓*)
let _ = 
   print (test_union ());