(*

 * ExtList - additional and modified functions for lists.

 * Copyright (C) 2003 Brian Hurt

 * Copyright (C) 2003 Nicolas Cannasse

 *

 * 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,

 * with the special exception on linking described in file LICENSE.

 *

 * 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

 *)

(** Additional and modified functions for lists.

  The OCaml standard library provides a module for list functions.

  This ExtList module can be used to override the List module or

  as a standalone module. It provides new functions and modify

  the behavior of some other ones (in particular all functions

  are now {b tail-recursive}).

*)

module List :

    sig

  (** {6 New functions} *)

  val init : int -> (int -> 'a) -> 'a list

  (** Similar to [Array.init], [init n f] returns the list containing

   the results of (f 0),(f 1).... (f (n-1)).

   Raise [Invalid_arg "ExtList.init"] if n < 0.

   Uses stdlib implementation in OCaml 4.06.0 and newer.

  *)

  val make : int -> 'a -> 'a list

    (** Similar to [String.make], [make n x] returns a

      * list containing [n] elements [x].

          *)

  val first : 'a list -> 'a

  (** Returns the first element of the list, or raise [Empty_list] if

   the list is empty (similar to [hd]). *)

  val last : 'a list -> 'a

  (** Returns the last element of the list, or raise [Empty_list] if

   the list is empty. This function takes linear time. *)

  val iteri : (int -> 'a -> unit) -> 'a list -> unit

  (** [iteri f l] will call [(f 0 a0);(f 1 a1) ... (f n an)] where

   [a0..an] are the elements of the list [l]. *)

  val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list

  (** [mapi f l] will build the list containing

   [(f 0 a0);(f 1 a1) ... (f n an)] where [a0..an] are the elements of

   the list [l]. *)

  val rfind : ('a -> bool) -> 'a list -> 'a

  (** [rfind p l] returns the last element [x] of [l] such as [p x] returns

   [true] or raises [Not_found] if such element as not been found. *)

  val find_exc : ('a -> bool) -> exn -> 'a list -> 'a

  (** [find_exc p e l] returns the first element of [l] such as [p x]

   returns [true] or raises [e] if such element as not been found. *)

  val findi : (int -> 'a -> bool) -> 'a list -> (int * 'a)

  (** [findi p e l] returns the first element [ai] of [l] along with its

   index [i] such that [p i ai] is true, or raises [Not_found] if no

   such element has been found. *)

  val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list

  (** [unique cmp l] returns the list [l] without any duplicate element.

   Default comparator ( = ) is used if no comparison function specified. *)

  val filter_map : ('a -> 'b option) -> 'a list -> 'b list

  (** [filter_map f l] call [(f a0) (f a1).... (f an)] where [a0..an] are

   the elements of [l]. It returns the list of elements [bi] such as

   [f ai = Some bi] (when [f] returns [None], the corresponding element of

   [l] is discarded). *)

  val find_map : ('a -> 'b option) -> 'a list -> 'b

  (** [find_map pred list] finds the first element of [list] for which

      [pred element] returns [Some r].  It returns [r] immediately

      once found or raises [Not_found] if no element matches the

      predicate.  See also {!filter_map}. *)

  val split_nth : int -> 'a list -> 'a list * 'a list

  (** [split_nth n l] returns two lists [l1] and [l2], [l1] containing the

   first [n] elements of [l] and [l2] the others. Raise [Invalid_index] if

   [n] is outside of [l] size bounds. *)

  val remove : 'a list -> 'a -> 'a list

  (** [remove l x] returns the list [l] without the first element [x] found

   or returns  [l] if no element is equal to [x]. Elements are compared

   using ( = ). *)

  val remove_if : ('a -> bool) -> 'a list -> 'a list

  (** [remove_if cmp l] is similar to [remove], but with [cmp] used

   instead of ( = ). *)

  val remove_all : 'a list -> 'a -> 'a list

  (** [remove_all l x] is similar to [remove] but removes all elements that

   are equal to [x] and not only the first one. *)

  val take : int -> 'a list -> 'a list

  (** [take n l] returns up to the [n] first elements from list [l], if

   available. *)

  val drop : int -> 'a list -> 'a list

  (** [drop n l] returns [l] without the first [n] elements, or the empty

   list if [l] have less than [n] elements. *)

  val takewhile : ('a -> bool) -> 'a list -> 'a list

    (** [takewhile f xs] returns the first elements of list [xs]

        which satisfy the predicate [f]. *)

  val dropwhile : ('a -> bool) -> 'a list -> 'a list

    (** [dropwhile f xs] returns the list [xs] with the first

        elements satisfying the predicate [f] dropped. *)

  (** {6 Enum functions} *)

  (** Enumerations are important in ExtLib, they are a good way to work with

   abstract enumeration of elements, regardless if they are located in a list,

   an array, or a file. *)

  val enum : 'a list -> 'a Enum.t

  (** Returns an enumeration of the elements of a list. *)

  val of_enum : 'a Enum.t -> 'a list

  (** Build a list from an enumeration. *)

  (** {6 Compatibility functions} *)

  val cons : 'a -> 'a list -> 'a list

  val assoc_opt : 'a -> ('a * 'b) list -> 'b option

  val assq_opt : 'a -> ('a * 'b) list -> 'b option

  val find_opt : ('a -> bool) -> 'a list -> 'a option

  val nth_opt : 'a list -> int -> 'a option

  val compare_lengths : 'a list -> 'b list -> int

  val compare_length_with : 'a list -> int -> int

  (** {6 Modified functions} *)

  (** Some minor modifications have been made to the specification of some

   functions, especially concerning exceptions raised. *)

  val hd : 'a list -> 'a

  (** Returns the first element of the list or raise [Empty_list] if the

   list is empty. *)

  val tl : 'a list -> 'a list

  (** Returns the list without its first elements or raise [Empty_list] if

   the list is empty. *)

  val nth : 'a list -> int -> 'a

  (** [nth l n] returns the n-th element of the list [l] or raise

   [Invalid_index] is the index is outside of [l] bounds. *)

  val sort : ?cmp:('a -> 'a -> int) -> 'a list -> 'a list

  (** Sort the list using optional comparator (by default [compare]). *)

  (** The following functions have been improved so all of them are

   tail-recursive. They have also been modified so they no longer

   raise [Invalid_arg] but [Different_list_size] when used on two

   lists having a different number of elements. *)

  val map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

  val rev_map2 : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

  val iter2 : ('a -> 'b -> unit) -> 'a list -> 'b list -> unit

  val fold_left2 : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a

  val fold_right2 : ('a -> 'b -> 'c -> 'c) -> 'a list -> 'b list -> 'c -> 'c

  val for_all2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool

  val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool

  val combine : 'a list -> 'b list -> ('a * 'b) list

  (** {6 Improved functions} *)

  (** The following functions have the same behavior as the [List]

    module ones but are tail-recursive. That means they will not

    cause a [Stack_overflow] when used on very long list.

    The implementation might be a little more slow in bytecode,

    but compiling in native code will not affect performances. *)

  val map : ('a -> 'b) -> 'a list -> 'b list

  val append : 'a list -> 'a list -> 'a list

  val flatten : 'a list list -> 'a list

  val concat : 'a list list -> 'a list

  val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

  val remove_assoc : 'a -> ('a * 'b) list -> ('a * 'b) list

  val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list

  val split : ('a * 'b) list -> 'a list * 'b list

  (** The following functions were already tail-recursive in the [List]

    module but were using [List.rev] calls. The new implementations

    have better performances. *)

  val filter : ('a -> bool) -> 'a list -> 'a list

  val find_all : ('a -> bool) -> 'a list -> 'a list

  val partition : ('a -> bool) -> 'a list -> 'a list * 'a list

  (** {6 Older functions} *)

  (** These functions are already part of the Ocaml standard library

    and have not been modified. Please refer to the Ocaml Manual for

    documentation. *)

  val length : 'a list -> int

  val rev_append : 'a list -> 'a list -> 'a list

  val rev : 'a list -> 'a list

  val rev_map : ('a -> 'b) -> 'a list -> 'b list

  val iter : ('a -> unit) -> 'a list -> unit

  val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b

  val for_all : ('a -> bool) -> 'a list -> bool

  val exists : ('a -> bool) -> 'a list -> bool

  val find : ('a -> bool) -> 'a list -> 'a

  val mem : 'a -> 'a list -> bool

  val memq : 'a -> 'a list -> bool

  val assoc : 'a -> ('a * 'b) list -> 'b

  val assq : 'a -> ('a * 'b) list -> 'b

  val mem_assoc : 'a -> ('a * 'b) list -> bool

  val mem_assq : 'a -> ('a * 'b) list -> bool

  val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list

  val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list

  val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list

#if OCAML >= 402

  val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list

  (** Same as {!List.sort}, but also remove duplicates.

      @since 4.02.0 *)

#endif

#if OCAML >= 407

  (** [*_seq] functions were introduced in OCaml 4.07.0, and are _not_ implemented in extlib for older OCaml versions *)

  val to_seq : 'a list -> 'a Seq.t

  val of_seq : 'a Seq.t -> 'a list

#endif

  (** {6 Exceptions} *)

  exception Empty_list

  (** [Empty_list] is raised when an operation applied on an empty list

    is invalid : [hd] for example. *)

  exception Invalid_index of int

  (** [Invalid_index] is raised when an indexed access on a list is

    out of list bounds. *)

  exception Different_list_size of string

  (** [Different_list_size] is raised when applying functions such as

    [iter2] on two lists having different size. *)

end

val ( @ ) : 'a list -> 'a list -> 'a list

(** the new implementation for ( @ ) operator, see [List.append]. *)