(* Array utility routines for ocaml
   Copyright (C) 2003,2004 Shawn Wagner <shawnw@speakeasy.org>

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.
	 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.
	 
   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*)

let find_index_from pred arr pos =
  let len = Array.length arr 
  and n = ref pos in
  while !n < len && not (pred arr.(!n)) do
    incr n
  done;
    if !n >= len then
      raise Not_found
    else 
      !n

let find_index pred arr = find_index_from pred arr 0

let pop arr = 
  let len = Array.length arr in
  if len = 0 then
    raise (Invalid_argument "ArrayExtras.pop")
  else if len = 1 then
    (arr.(0), [||])
  else
    (arr.(0), Array.sub arr 1 (len - 1))

let push item arr =
  let newarr = Array.make (Array.length arr + 1) item in
    Array.blit arr 0 newarr 1 (Array.length arr);
    newarr

let genmunge sort cmp f arr =
  let pairs = Array.init (Array.length arr) (function i -> f arr.(i), arr.(i)) in
    sort (fun x y -> cmp (fst x) (fst y)) pairs;
    Array.init (Array.length arr) (function i -> snd pairs.(i))

let munge ~cmp ~f arr = genmunge Array.sort cmp f arr
let stable_munge ~cmp ~f arr = genmunge Array.stable_sort cmp f arr
let fast_munge ~cmp ~f arr = genmunge Array.fast_sort cmp f arr

let swap arr a  b =
  let tmp = arr.(a) in
    arr.(a) <- arr.(b);
    arr.(b) <- tmp

let rev arr =
  match Array.length arr with
    | 0 | 1 -> ()
    | 2 -> swap arr 0 1
    | 3 -> swap arr 0 2
    | len -> 
	let z = ref (len - 1) in
	  for x = 0 to len / 2 - 1 do
	    swap arr x !z;
	    decr z
	  done

let ensure_range f a start len =
  let stop = start + len in
  let rec ensure2 i  =
    if i >= stop then
      true
    else if f a.(i) then
      ensure2 (i + 1)
    else
      false in
    ensure2 start
      
let ensure f a =
  ensure_range f a 0 (Array.length a)

module type Comparable = sig
  type t 
  val compare: t -> t -> int 
end

(** The actual functions for searching in sorted arrays *)
module Sorted (Comp : Comparable) = struct
  type elem = Comp.t
  type t = Comp.t array
      
  let sort = Array.sort Comp.compare 
  let stable_sort = Array.stable_sort Comp.compare
  let fast_sort = Array.fast_sort Comp.compare

  (* This could be done better *)
  let insert sarr elem =
    let newsarr = Array.append sarr [| elem |] in
      fast_sort newsarr;                       
      newsarr

  let rec find_helper sarr elem starti endi =
    let i = (starti + endi) / 2 in
      if starti > endi then raise Not_found;
      match Comp.compare elem sarr.(i) with
	| 0 -> i
	| x when x < 0 -> 
	    if starti = endi then
	      raise Not_found
	    else 
	      find_helper sarr elem starti (i - 1)
	| x ->
	    if starti = endi then
	      raise Not_found
	    else
	      find_helper sarr elem (i + 1) endi

  let find sarr elem = 
    let starti = 0
    and endi = (Array.length sarr) - 1 in
      find_helper sarr elem starti endi

  let exists sarr elem =
    try
      ignore (find sarr elem);
      true
    with
      | Not_found -> false


  let rec step way sarr elem i =
    let n = way i in
      if n < 0 or n >= Array.length sarr then 
	i
      else if Comp.compare elem sarr.(n) <> 0 then
	i
      else
	step way sarr elem n

  let range sarr elem =
    let i = find sarr elem in
      (step pred sarr elem i), (step succ sarr elem i)

end