|
rpm-build |
0f2925 |
(*
|
|
rpm-build |
0f2925 |
* Enum - enumeration over abstract collection of elements.
|
|
rpm-build |
0f2925 |
* Copyright (C) 2003 Nicolas Cannasse
|
|
rpm-build |
0f2925 |
*
|
|
rpm-build |
0f2925 |
* This library is free software; you can redistribute it and/or
|
|
rpm-build |
0f2925 |
* modify it under the terms of the GNU Lesser General Public
|
|
rpm-build |
0f2925 |
* License as published by the Free Software Foundation; either
|
|
rpm-build |
0f2925 |
* version 2.1 of the License, or (at your option) any later version,
|
|
rpm-build |
0f2925 |
* with the special exception on linking described in file LICENSE.
|
|
rpm-build |
0f2925 |
*
|
|
rpm-build |
0f2925 |
* This library is distributed in the hope that it will be useful,
|
|
rpm-build |
0f2925 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
rpm-build |
0f2925 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
rpm-build |
0f2925 |
* Lesser General Public License for more details.
|
|
rpm-build |
0f2925 |
*
|
|
rpm-build |
0f2925 |
* You should have received a copy of the GNU Lesser General Public
|
|
rpm-build |
0f2925 |
* License along with this library; if not, write to the Free Software
|
|
rpm-build |
0f2925 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** Enumeration over abstract collection of elements.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Enumerations are entirely functional and most of the operations do not
|
|
rpm-build |
0f2925 |
actually require the allocation of data structures. Using enumerations
|
|
rpm-build |
0f2925 |
to manipulate data is therefore efficient and simple. All data structures in
|
|
rpm-build |
0f2925 |
ExtLib such as lists, arrays, etc. have support to convert from and to
|
|
rpm-build |
0f2925 |
enumerations.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
type 'a t
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Final functions}
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
These functions consume the enumeration until
|
|
rpm-build |
0f2925 |
it ends or an exception is raised by the first
|
|
rpm-build |
0f2925 |
argument function.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iter : ('a -> unit) -> 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [iter f e] calls the function [f] with each elements of [e] in turn. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit
|
|
rpm-build |
0f2925 |
(** [iter2 f e1 e2] calls the function [f] with the next elements of [e] and
|
|
rpm-build |
0f2925 |
[e2] repeatedly until one of the two enumerations ends. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fold : ('a -> 'b -> 'b) -> 'b -> 'a t -> 'b
|
|
rpm-build |
0f2925 |
(** [fold f v e] returns [v] if [e] is empty,
|
|
rpm-build |
0f2925 |
otherwise [f aN (... (f a2 (f a1 v)) ...)] where a1..N are
|
|
rpm-build |
0f2925 |
the elements of [e].
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fold2 : ('a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c
|
|
rpm-build |
0f2925 |
(** [fold2] is similar to [fold] but will fold over two enumerations at the
|
|
rpm-build |
0f2925 |
same time until one of the two enumerations ends. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** Indexed functions : these functions are similar to previous ones
|
|
rpm-build |
0f2925 |
except that they call the function with one additional argument which
|
|
rpm-build |
0f2925 |
is an index starting at 0 and incremented after each call to the function. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iteri : (int -> 'a -> unit) -> 'a t -> unit
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iter2i : ( int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val foldi : (int -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fold2i : (int -> 'a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Useful functions} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val find : ('a -> bool) -> 'a t -> 'a
|
|
rpm-build |
0f2925 |
(** [find f e] returns the first element [x] of [e] such that [f x] returns
|
|
rpm-build |
0f2925 |
[true], consuming the enumeration up to and including the
|
|
rpm-build |
0f2925 |
found element, or, raises [Not_found] if no such element exists
|
|
rpm-build |
0f2925 |
in the enumeration, consuming the whole enumeration in the search.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Since [find] consumes a prefix of the enumeration, it can be used several
|
|
rpm-build |
0f2925 |
times on the same enumeration to find the next element. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val is_empty : 'a t -> bool
|
|
rpm-build |
0f2925 |
(** [is_empty e] returns true if [e] does not contains any element. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val peek : 'a t -> 'a option
|
|
rpm-build |
0f2925 |
(** [peek e] returns [None] if [e] is empty or [Some x] where [x] is
|
|
rpm-build |
0f2925 |
the next element of [e]. The element is not removed from the enumeration. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val get : 'a t -> 'a option
|
|
rpm-build |
0f2925 |
(** [get e] returns [None] if [e] is empty or [Some x] where [x] is
|
|
rpm-build |
0f2925 |
the next element of [e], in which case the element is removed from the enumeration. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val next : 'a t -> 'a
|
|
rpm-build |
0f2925 |
(** [next e] returns the next element of [e] (and removes it from enumeration).
|
|
rpm-build |
0f2925 |
@raise No_more_elements if enumeration is empty *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val push : 'a t -> 'a -> unit
|
|
rpm-build |
0f2925 |
(** [push e x] will add [x] at the beginning of [e]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val junk : 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [junk e] removes the first element from the enumeration, if any. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val clone : 'a t -> 'a t
|
|
rpm-build |
0f2925 |
(** [clone e] creates a new enumeration that is copy of [e]. If [e]
|
|
rpm-build |
0f2925 |
is consumed by later operations, the clone will not get affected. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val force : 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [force e] forces the application of all lazy functions and the
|
|
rpm-build |
0f2925 |
enumeration of all elements, exhausting the enumeration.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
An efficient intermediate data structure
|
|
rpm-build |
0f2925 |
of enumerated elements is constructed and [e] will now enumerate over
|
|
rpm-build |
0f2925 |
that data structure. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Lazy constructors}
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
These functions are lazy which means that they will create a new modified
|
|
rpm-build |
0f2925 |
enumeration without actually enumerating any element until they are asked
|
|
rpm-build |
0f2925 |
to do so by the programmer (using one of the functions above).
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
When the resulting enumerations of these functions are consumed, the
|
|
rpm-build |
0f2925 |
underlying enumerations they were created from are also consumed. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val map : ('a -> 'b) -> 'a t -> 'b t
|
|
rpm-build |
0f2925 |
(** [map f e] returns an enumeration over [(f a1, f a2, ... , f aN)] where
|
|
rpm-build |
0f2925 |
a1...N are the elements of [e]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
|
|
rpm-build |
0f2925 |
(** [mapi] is similar to [map] except that [f] is passed one extra argument
|
|
rpm-build |
0f2925 |
which is the index of the element in the enumeration, starting from 0. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val filter : ('a -> bool) -> 'a t -> 'a t
|
|
rpm-build |
0f2925 |
(** [filter f e] returns an enumeration over all elements [x] of [e] such
|
|
rpm-build |
0f2925 |
as [f x] returns [true]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val filter_map : ('a -> 'b option) -> 'a t -> 'b t
|
|
rpm-build |
0f2925 |
(** [filter_map f e] returns an enumeration over all elements [x] such as
|
|
rpm-build |
0f2925 |
[f y] returns [Some x] , where [y] is an element of [e]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val append : 'a t -> 'a t -> 'a t
|
|
rpm-build |
0f2925 |
(** [append e1 e2] returns an enumeration that will enumerate over all
|
|
rpm-build |
0f2925 |
elements of [e1] followed by all elements of [e2]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val concat : 'a t t -> 'a t
|
|
rpm-build |
0f2925 |
(** [concat e] returns an enumeration over all elements of all enumerations
|
|
rpm-build |
0f2925 |
of [e]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Constructors}
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
In this section the word {i shall} denotes a semantic
|
|
rpm-build |
0f2925 |
requirement. The correct operation
|
|
rpm-build |
0f2925 |
of the functions in this interface are conditional
|
|
rpm-build |
0f2925 |
on the client meeting these requirements.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
exception No_more_elements
|
|
rpm-build |
0f2925 |
(** This exception {i shall} be raised by the [next] function of [make]
|
|
rpm-build |
0f2925 |
or [from] when no more elements can be enumerated, it {i shall not}
|
|
rpm-build |
0f2925 |
be raised by any function which is an argument to any
|
|
rpm-build |
0f2925 |
other function specified in the interface.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val empty : unit -> 'a t
|
|
rpm-build |
0f2925 |
(** The empty enumeration : contains no element *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val make : next:(unit -> 'a) -> count:(unit -> int) -> clone:(unit -> 'a t) -> 'a t
|
|
rpm-build |
0f2925 |
(** This function creates a fully defined enumeration.
|
|
rpm-build |
0f2925 |
{ul {li the [next] function {i shall} return the next element of the
|
|
rpm-build |
0f2925 |
enumeration or raise [No_more_elements] if the underlying data structure
|
|
rpm-build |
0f2925 |
does not have any more elements to enumerate.}
|
|
rpm-build |
0f2925 |
{li the [count] function {i shall} return the actual number of remaining
|
|
rpm-build |
0f2925 |
elements in the enumeration.}
|
|
rpm-build |
0f2925 |
{li the [clone] function {i shall} create a clone of the enumeration
|
|
rpm-build |
0f2925 |
such as operations on the original enumeration will not affect the
|
|
rpm-build |
0f2925 |
clone. }}
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
For some samples on how to correctly use [make], you can have a look
|
|
rpm-build |
0f2925 |
at implementation of [ExtList.enum].
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val from : (unit -> 'a) -> 'a t
|
|
rpm-build |
0f2925 |
(** [from next] creates an enumeration from the [next] function.
|
|
rpm-build |
0f2925 |
[next] {i shall} return the next element of the enumeration or raise
|
|
rpm-build |
0f2925 |
[No_more_elements] when no more elements can be enumerated. Since the
|
|
rpm-build |
0f2925 |
enumeration definition is incomplete, a call to [clone] or [count] will
|
|
rpm-build |
0f2925 |
result in a call to [force] that will enumerate all elements in order to
|
|
rpm-build |
0f2925 |
return a correct value. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val init : int -> (int -> 'a) -> 'a t
|
|
rpm-build |
0f2925 |
(** [init n f] creates a new enumeration over elements
|
|
rpm-build |
0f2925 |
[f 0, f 1, ..., f (n-1)] *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Counting} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val count : 'a t -> int
|
|
rpm-build |
0f2925 |
(** [count e] returns the number of remaining elements in [e] without
|
|
rpm-build |
0f2925 |
consuming the enumeration.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Depending of the underlying data structure that is implementing the
|
|
rpm-build |
0f2925 |
enumeration functions, the count operation can be costly, and even sometimes
|
|
rpm-build |
0f2925 |
can cause a call to [force]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fast_count : 'a t -> bool
|
|
rpm-build |
0f2925 |
(** For users worried about the speed of [count] you can call the [fast_count]
|
|
rpm-build |
0f2925 |
function that will give an hint about [count] implementation. Basically, if
|
|
rpm-build |
0f2925 |
the enumeration has been created with [make] or [init] or if [force] has
|
|
rpm-build |
0f2925 |
been called on it, then [fast_count] will return true. *)
|