(* 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
*)

(** Utility functions for dealing with arrays *)

(** {1 Searching} *)

(** [find_index f arr] Returns the index of the first element in the
array that satisfies the predicate *)
val find_index: ('a -> bool) -> 'a array -> int
(** @raise Not_found if f never returns true *)

(** Same as find_index, but starts looking at the given index. *)
val find_index_from: ('a -> bool) -> 'a array -> int -> int
(** @raise Not_found if f never returns true *)

(** {2 Searching sorted arrays } 

  These modules provide efficient O(lg n) searching of sorted
  arrays. Rather than having every function take a comparison-function
  argument, functors are used.

*)

(** Modules of this type provide functions to test the ordering of elements *)
module type Comparable = sig
  (** The type of items to be compared *)
  type t 

  (** [compare a b] returns 0 if a and b are equal, a negative number
    if a is greater than b, and a positive number if a is less than
    b. *)
  val compare: t -> t -> int 
end

(** The actual functions for searching in sorted arrays *)
module Sorted: functor (Comp : Comparable) -> sig
  type elem = Comp.t (** The type of elements of the sorted array *)
      
  (** An array. Bad Stuff happens if it's not sorted! Use the sorting
    functions below or the ones in the [Array] module to fix. *)
  type t = elem array

  (** Acts just like [Array.sort] using the functorized comparision
    function. *)
  val sort: t -> unit

  (** See above. *)
  val stable_sort: t -> unit

  (** See above *)
  val fast_sort: t-> unit

  (** [exists arr elem] returns [true] of the element is in the
    sorted array. *)
  val exists: t -> elem -> bool    

  (** [index arr elem] returns the index of the element in the sorrted array. *)
  val find: t -> elem -> int
    (** @raise Not_found if [elem] isn't present. *)

    (** [range arr elem] returns a pair of the first and last indexes into the array that contain a range of elements equal to [elem]. *)
  val range: t -> elem -> int * int
    (** @raise Not_found if [elem] isn't prsent. *)
    

end
    
  (** {1 Stepping through elements} *)

(** [ensure f a] returns true if [f] is true for all elements in
  [a]. It stops after the first false result, making it more efficient
  than [Array.fold_left] for validation. *)
val ensure: ('a -> bool) -> 'a array -> bool

(** [ensure_range f a i len] applies [f] to the [len]-gth elements in [a]
  starting at index [i] and returns true if [f] is true for all the
  elements, otherwise false. *)
val ensure_range : ('a -> bool) -> 'a array -> int -> int -> bool

(** {1 Transformation} *)

(** Swap two elements of an array *)
val swap: 'a array -> int -> int -> unit

(** Reverses the elements of the array *)
val rev: 'a array -> unit

(** {1 Stacks} *)

(** Normally you'd use lists for things like this, but these functions
  are useful once in a while. *)

(** Returns the first element of the array and a new array with the
  rest of the elements of the original. *)
val pop: 'a array -> 'a * 'a array

(** Returns a new array with the element pushed onto the front of it. *)
val push: 'a -> 'a array -> 'a array

(** {1 Sorting} *)

(** Implements munging/Schwartzian transform on an array. Maps {i 'a array} to {i 'b array} and returns the original {i 'a array} ordered by a sort of {i 'b array}. *)
val munge: cmp:('b -> 'b -> int) -> f:('a -> 'b) -> 'a array -> 'a array

(** The same using a stable sort *)
val stable_munge: cmp:('b -> 'b -> int) -> f:('a -> 'b) -> 'a array -> 'a array

(** The same using the fastest array sorting *)
val fast_munge: cmp:('b -> 'b -> int) -> f:('a -> 'b) -> 'a array -> 'a array