#use "topfind" ;;
#require "pcre" ;;

type tree = Node of string * tree list | Leaf of string

let () = Random.self_init ()

let ( |> ) x f = f x

let shuffle arr =
  let len = Array.length arr in
  for i = 0 to len - 2 do
    let r = i + Random.int (len - i - 1) in
    let x = Array.unsafe_get arr i in
    let y = Array.unsafe_get arr r in
    Array.unsafe_set arr i y ;
    Array.unsafe_set arr r x
  done

let words =
  let ws = ref [] in
  let ic = Pervasives.open_in "/usr/share/dict/words" in
  Pcre.foreach_line ~ic (fun w -> ws := w :: !ws) ;
  Pervasives.close_in ic ;
  let ret = Array.of_list (List.rev !ws) in
  shuffle ret ;
  ret

let random_word () =
  Array.length words
  |> Random.int
  |> Array.unsafe_get words

let rec rev_list_init n curr fn = match n with
  | 0 -> fn 0 :: curr
  | _ -> rev_list_init (n - 1) (fn n :: curr) fn

let list_init n fn =
  if n <= 0 then [] else rev_list_init (n - 1) [] fn

let randtree =
  let rec make dep = match dep with
    | 0 -> Leaf (random_word ())
    | _ ->
        Node (random_word (),
              list_init (1 + Random.int (dep + 1)) (fun _ -> make (dep - 1)))
  in
  make 4

let rec p_tree ff = function
  | Leaf lf -> Format.pp_print_string ff lf
  | Node (nd, kids) ->
      Format.fprintf ff "@[<v2>%s@,%a@]"
        nd p_trees kids

and p_trees ff = function
  | [ ] -> ()
  | [tr] ->
      p_tree ff tr
  | tr :: trs ->
      p_tree ff tr ;
      Format.pp_print_cut ff () ;
      p_trees ff trs

let () =
  Format.eprintf "Here's a random tree@.%a@." p_tree randtree