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

(** {1 Searching} *)

(** [index item list] returns the 0-based position of index in list.
 @raise Not_found if the item isn't in list.
*)
val index: 'a -> 'a list -> int

(** Same as [index] but using physical equality instead of structural equality to compare the elements. *)
val indexq: 'a -> 'a list -> int

(** {2 Complex equality} *)

(** The following functor provides list functions that compare items
of lists in terms of a user-defined equality function rather than the
built-in [=] or [==] operators. *)

(** Input signature of the functor {!ListExtras.Make}. *)
module type ComparableType = sig
  (** The type of the list elements *)
  type t
    
  (** Returns 0 if its arguments are equal, anything else if they're not equal.
   *)
  val compare: t -> t -> int
end

(** Output signature of the functor {!ListExtras.Make} *)
module type S = sig
  (** The type of elements in a list *)
  type t 

  (** Returns the 0-based position of an element in the list using user-defined equality test. *)
  val index: t -> t list -> int
    (** @raise Not_found if the item isn't in the list *)

  val mem: t -> t list -> bool
    (** [mem a l] is true if and only if [a] is equal to an element of [l]. *)

  val assoc: t -> (t * 'a) list -> 'a
    (** Same as [List.assoc] *)

  val mem_assoc: t -> (t * 'a) list -> bool
    (** Same as [List.mem_assoc] *)
    
  val remove_assoc: t -> (t * 'a) list -> (t * 'a) list
    (** Same as [List.remove_assoc] *)

end

module Make (Comp: ComparableType) : S with type t = Comp.t

(** {1 Sorting} *)

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

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

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

(** {1 Extracting elements} *)

(** These are lifted from scheme. *)

(** Same as [List.hd] *)
val car: 'a list -> 'a

(** Same as [List.tl] *)
val cdr: 'a list -> 'a list

val cadr: 'a list -> 'a

val cddr: 'a list -> 'a list

val caddr: 'a list -> 'a

val cdddr: 'a list -> 'a list

val cadddr: 'a list -> 'a

val cddddr: 'a list -> 'a list

(** Returns the nth cdr (Zero-based) of list *)
val tail: 'a list -> int -> 'a list