(** Extensions to the system Array module *)

(** [exists pred a]
  Analogous to List.exists *)
let exists pred a =
  let rec loop i =
    if i >= Array.length a
    then false
    else if pred a.(i)
    then true
    else loop (i+1) in
  loop 0

(** [index pred a] Analogous to My.List.index *)
let index pred a =
  let rec loop i =
    if i >= Array.length a
    then raise Not_found
    else if pred a.(i)
    then i
    else loop (i+1) in
  loop 0

(** Analogous to List.map2 *)
let map2 f a1 a2 =
  if Array.length a1 != Array.length a2
  then raise (Invalid_argument "Array.map2");
  Array.mapi (fun i _ -> f a1.(i) a2.(i)) a1

let find_all pred a =
  let result = ref [] in
  Array.iter (fun elem -> if pred elem then result := elem :: !result) a;
  List.rev !result

let filter pred a =
  Array.of_list (find_all pred a)

let count pred a = List.length (find_all pred a)

(* new *)

let combine a b =
  map2 (fun a b -> a, b) a b

let assoc key alist =
  let rec loop n =
    if n >= Array.length alist then raise Not_found;
    match alist.(n) with
      (a, b) when a = key -> b
    | _ -> loop (n + 1) in
  loop 0

let for_all pred a =
  let rec loop n =
    if n = Array.length a
    then true
    else if pred a.(n)
    then loop (n + 1)
    else false in
  loop 0

let filter pred a =
  let flags = Array.map pred a in
  let count =
    Array.fold_left
      (fun count flag -> if flag then count + 1 else count) 0 flags in
  (* FIXME: this is an n^2 algorithm. *)
  Array.init count (fun n ->
		      let rec loop i j =
			if flags.(i) && j = n
			then a.(i)
			else if flags.(i)
			then loop (i+1) (j+1)
			else loop (i+1) j in
		      loop 0 0)

let filter_out pred a =
  filter (fun x -> not (pred x)) a

let index pred a =
  let rec loop n = 
    if n = Array.length a
    then raise Not_found
    else if pred a.(n)
    then n
    else loop (n + 1) in
  loop 0      

let find pred a = a.(index pred a)

(* FIXME: this is lame. *)
let concat sep a = String.concat sep (Array.to_list a)

let mem elem a =
  let rec loop n =
    if n = Array.length a
    then false
    else if a.(n) = elem
    then true
    else loop (n+1) in
  loop 0

let memq elem a =
  let rec loop n =
    if n = Array.length a
    then false
    else if a.(n) == elem
    then true
    else loop (n+1) in
  loop 0

let exists pred a =
  let rec loop n =
    if n = Array.length a
    then false
    else if pred a.(n)
    then true
    else loop (n+1) in
  loop 0

(* Remove the array elements which correspond to 0s in a bitmap *)
let mask bits values =
  Array.map
    (function None -> failwith "internal error 6" | Some value -> value)
    (filter
       (function None -> false | _ -> true)
       (map2 (fun bit value -> if bit then Some value else None)
	  bits values))

let format ?(prefix="") format a =
  let sep = ";" ^ (if String.contains prefix '\n' then prefix ^ " " else "") ^ " " in
  prefix ^ "[|" ^ concat sep (Array.map format a) ^ "|]"

let compare compare a b =
  let rec loop n =
    if n = Array.length a
    then 0
    else
      match compare a.(n) b.(n) with
	0 -> loop (n+1)
      | n -> n in
  loop 0

let option_filter (a : 'a option array) : 'a array =
  Array.map Option.get (filter Option.pred a)

let to_1_tuple = function [|a|] -> a | _ -> raise (Invalid_argument "Array.to_1_tuple")
let to_2_tuple = function [|a;b|] -> a,b | _ -> raise (Invalid_argument "Array.to_2_tuple")
let to_3_tuple = function [|a;b;c|] -> a,b,c | _ -> raise (Invalid_argument "Array.to_3_tuple")
let to_4_tuple = function [|a;b;c;d|] -> a,b,c,d | _ -> raise (Invalid_argument "Array.to_4_tuple")
let to_5_tuple = function [|a;b;c;d;e|] -> a,b,c,d,e | _ -> raise (Invalid_argument "Array.to_5_tuple")
let to_6_tuple = function [|a;b;c;d;e;f|] -> a,b,c,d,e,f | _ -> raise (Invalid_argument "Array.to_6_tuple")
let to_7_tuple = function [|a;b;c;d;e;f;g|] -> a,b,c,d,e,f,g | _ -> raise (Invalid_argument "Array.to_7_tuple")
let to_8_tuple = function [|a;b;c;d;e;f;g;h|] -> a,b,c,d,e,f,g,h | _ -> raise (Invalid_argument "Array.to_8_tuple")
let to_9_tuple = function [|a;b;c;d;e;f;g;h;i|] -> a,b,c,d,e,f,g,h,i | _ -> raise (Invalid_argument "Array.to_9_tuple")