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