Source

ocaml-workspace / clusters.ml

module IntSet = Set.Make( 
  struct
    let compare = Pervasives.compare
    type t = int
  end )
;;

exception InFormatError of string ;;

let read_bits s = 
  match (Str.split (Str.regexp "[ \t]+") s) with
    |x::y::_ -> int_of_string y
    |_ -> raise (InFormatError "could not read header" )
;;

let fold_lines f chan acc =
  let lines = ref acc in
  try
    while true; do
      lines := f (input_line chan) !lines
    done; acc
  with End_of_file ->
    close_in chan;
    !lines
;;

let timer f x =
  let t0 = Sys.time() in
  let res = f x in
  let t1 = Sys.time() in
  Printf.printf "time take %f sec \n" (t1 -. t0);
  res
    



let  n_choose_k n k = 
  let rec choose lo = 
    function
      |[] -> [[]]
      |x::xs as cs -> if lo = 1 then List.map (fun a -> [a]) cs
	              else 
	                List.map (fun cs -> x::cs) (choose (lo-1) xs)
			  
  in
  choose k n

	

let bits_to_int nbits s  = 
  let rec acc_bits hi lo shift acc = 
    if hi = lo then acc
    else
      match s.[lo] with
	|'1' | '0' as c -> 
	  let b = (Char.code c)-48 in
	  acc_bits hi (lo+1) (shift-1) (acc+(b lsl shift))
	|_ -> acc_bits hi (lo+1) shift acc
  in
  acc_bits (String.length s) 0 (nbits-1) 0
;;


let read_input fname = 
  let chan = open_in fname in
  try
    let nbits = read_bits (input_line chan) in
    let f line s = IntSet.add (bits_to_int nbits line) s in
    (nbits, (fold_lines f chan IntSet.empty))
  with End_of_file ->
    close_in chan;
    (0,IntSet.empty) 
;;
      
      
let fname =  Sys.argv.(1);;

 ignore (timer read_input fname)
;;