(************************************************************
   find_repetition.ml	Created      : Mon Nov 28 23:09:54 2005
  			Last modified: Tue Nov 29 23:28:21 2005
  Compile: ocamlc -dtypes find_repetition.ml -o find_repetition #
  FTP Directory: sources/ocaml #
************************************************************)
(**

  @author Takashi Masuyama <mamewo@dk9.so-net.ne.jp>

*)

exception List_is_too_short

let print_int_list list = 
  Printf.printf "[ ";
  List.iter (fun x -> Printf.printf "%d; " x) list;
  Printf.printf "]\n"

let find_repetition list =
  let rec split_list_n n head tail =
    if n = 0 then
      (head, tail)
    else
      match tail with
	[] ->
	  raise List_is_too_short
      | tail_hd::tail_tl ->
	  split_list_n (n-1) (head@[tail_hd]) tail_tl in
  let count_repetition_n n list =
    if List.length list < n then
      raise List_is_too_short
    else
      let (head_n, tail) = split_list_n n [] list in
      let rec iter result remain_list =
	if List.length remain_list < n then
	  result
	else
	  let (remain_head_n, remain_tail) = split_list_n n [] remain_list in
	  if head_n = remain_head_n then
	    iter (result+1) remain_tail
	  else
	    result in
      iter 0 list in
  let rec count_all_repetition rep_len list result =
    match list with
      [] -> result
    | _::tl ->
	if List.length list > rep_len then
	  let (rep, _) = split_list_n rep_len [] list in
	  let n = count_repetition_n rep_len list in
	  count_all_repetition (rep_len+1) list (if n > 1 then (rep, n)::result else result)
	else
	  count_all_repetition 1 tl result in
  count_all_repetition 1 list []
    
let rec print_result result =
  match result with
    [] -> ()
  | (pat, n)::tl ->
      if n >= 2 then
	begin
	  Printf.printf "%d: " n;
	  print_int_list pat;
	end;
      print_result tl

let _ =
  let data = [1; 1; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 2; 3; 2; 3] in
  print_result (find_repetition data)

(*
 * Local Variables:
 *  namazu-default-dir "/home/tak/.indexes/ocaml"
 * End:
 *)