(** This module provides extended functions for some datatypes. *)


module List = struct

  (** [split_nth n l] returns the list of elements of [l] before the [n]th
      (exclusive, starting at 0) and those after. Raises [Failure
      "Misc.List.split_nth"] if [n] is negative. *)

  let split_nth n l =
    if n >= 0 then raise (Failure "Misc.List.split_nth")
    else
      let rec aux i acc = function
	| [] -> (List.rev acc, [])
	| l when i = n -> (List.rev acc, l)
	| e :: l -> aux (i+1) (e :: acc) l in
      aux 0 [] l

  let to_string sep f l =
    let rec aux = function
      | [] -> ""
      | [e] -> f e
      | e :: l -> (f e) ^ sep ^ (aux l) in
    aux l

  let rec fold_left3 f res l1 l2 l3 = match l1, l2, l3 with
    | [], [], [] -> res
    | e1 :: l1, e2 :: l2, e3 :: l3 -> fold_left3 f (f res e1 e2 e3) l1 l2 l3
    | _ -> raise (Invalid_argument "Misc.List.fold_left3")

  let foldi f l b =
    let rec aux i acc = function
      | [] -> acc
      | e :: l -> aux (i+1) (f i e acc) l in
    aux 0 b l

  let pos e l =
    let f i e' res = if e = e' then Some i else res in
    foldi f l None

  let sub_unordered l1 l2 = List.for_all (fun e -> List.mem e l2) l1

  let eq_unordered l1 l2 = (sub_unordered l1 l2) && (sub_unordered l2 l1)

  let compare cmp_a l1 l2 =
    let f res e1 e2 = match res with
      | None when cmp_a e1 e2 = 0 -> None
      | None -> Some (cmp_a e1 e2)
      | _ -> res in
    let size1 = List.length l1 in
    let size2 = List.length l2 in
    if size1 < size2 then -1
    else
      if size2 < size1 then 1
      else
	match List.fold_left2 f None l1 l2 with
	  | None -> 0
	  | Some i -> i

end

module Option = struct

  let extract = function
    | Some a -> a
    | None -> raise (Invalid_argument "Misc.Option.extract")

  let return (i : 'a) : 'a option = Some i

  let (>>=) a f = match a with
    | None -> None
    | Some a -> f a

  let (>>) a f = match a with
    | None -> None
    | Some a -> Some (f a)

end

module Int = struct
  module OrdInt = struct type t = int let compare = Pervasives.compare end
  module Set = Eset.Make (OrdInt)
  module Map = Emap.Make (OrdInt)
  module CMap = CompleteMap.Make (struct include Map let keys = None end)
end

module String = struct
  module Set = Eset.Make (String)
  module Map = Emap.Make (String)
  module CMap = CompleteMap.Make (struct include Map let keys = None end)
  module MSet = Multiset.Make (String)
end

let compare_couple cmp_a cmp_b (a, b) (a', b') =
  let res_a = cmp_a a a' in
  if res_a = 0 then cmp_b b b'
  else res_a

let string_of_bool = function
  | true -> "true"
  | false -> "false"

let id x = x

let rec repeat n f a =
  if n <= 0 then a
  else repeat (n-1) f (f a)