Commit | Line | Data |
---|---|---|
34e49164 C |
1 | (* \r |
2 | * Enum - enumeration over abstract collection of elements.\r | |
3 | * Copyright (C) 2003 Nicolas Cannasse\r | |
4 | * \r | |
5 | * This library is free software; you can redistribute it and/or\r | |
6 | * modify it under the terms of the GNU Lesser General Public\r | |
7 | * License as published by the Free Software Foundation; either\r | |
8 | * version 2.1 of the License, or (at your option) any later version,\r | |
9 | * with the special exception on linking described in file LICENSE.\r | |
10 | *\r | |
11 | * This library is distributed in the hope that it will be useful,\r | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of\r | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\r | |
14 | * Lesser General Public License for more details.\r | |
15 | *\r | |
16 | * You should have received a copy of the GNU Lesser General Public\r | |
17 | * License along with this library; if not, write to the Free Software\r | |
18 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\r | |
19 | *)\r | |
20 | \r | |
21 | (** Enumeration over abstract collection of elements.\r | |
22 | \r | |
23 | Enumerations are entirely functional and most of the operations do not\r | |
24 | actually require the allocation of data structures. Using enumerations\r | |
25 | to manipulate data is therefore efficient and simple. All data structures in\r | |
26 | ExtLib such as lists, arrays, etc. have support to convert from and to\r | |
27 | enumerations.\r | |
28 | *)\r | |
29 | \r | |
30 | \r | |
31 | type 'a t\r | |
32 | \r | |
33 | (** {6 Final functions}\r | |
34 | \r | |
35 | These functions consume the enumeration until\r | |
36 | it ends or an exception is raised by the first\r | |
37 | argument function.\r | |
38 | *)\r | |
39 | \r | |
40 | val iter : ('a -> unit) -> 'a t -> unit\r | |
41 | (** [iter f e] calls the function [f] with each elements of [e] in turn. *)\r | |
42 | \r | |
43 | val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit\r | |
44 | (** [iter2 f e1 e2] calls the function [f] with the next elements of [e] and\r | |
45 | [e2] repeatedly until one of the two enumerations ends. *)\r | |
46 | \r | |
47 | val fold : ('a -> 'b -> 'b) -> 'b -> 'a t -> 'b\r | |
48 | (** [fold f v e] returns v if e is empty,\r | |
49 | otherwise [f (... (f (f v a1) a2) ...) aN] where a1..N are\r | |
50 | the elements of [e]. \r | |
51 | *)\r | |
52 | \r | |
53 | val fold2 : ('a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c\r | |
54 | (** [fold2] is similar to [fold] but will fold over two enumerations at the\r | |
55 | same time until one of the two enumerations ends. *)\r | |
56 | \r | |
57 | (** Indexed functions : these functions are similar to previous ones\r | |
58 | except that they call the function with one additional argument which\r | |
59 | is an index starting at 0 and incremented after each call to the function. *)\r | |
60 | \r | |
61 | val iteri : (int -> 'a -> unit) -> 'a t -> unit\r | |
62 | \r | |
63 | val iter2i : ( int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit\r | |
64 | \r | |
65 | val foldi : (int -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b\r | |
66 | \r | |
67 | val fold2i : (int -> 'a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c\r | |
68 | \r | |
69 | (** {6 Useful functions} *)\r | |
70 | \r | |
71 | val find : ('a -> bool) -> 'a t -> 'a\r | |
72 | (** [find f e] returns the first element [x] of [e] such that [f x] returns\r | |
73 | [true], consuming the enumeration up to and including the\r | |
74 | found element, or, raises [Not_found] if no such element exists\r | |
75 | in the enumeration, consuming the whole enumeration in the search.\r | |
76 | \r | |
77 | Since [find] consumes a prefix of the enumeration, it can be used several \r | |
78 | times on the same enumeration to find the next element. *)\r | |
79 | \r | |
80 | val is_empty : 'a t -> bool\r | |
81 | (** [is_empty e] returns true if [e] does not contains any element. *)\r | |
82 | \r | |
83 | val peek : 'a t -> 'a option\r | |
84 | (** [peek e] returns [None] if [e] is empty or [Some x] where [x] is\r | |
85 | the next element of [e]. The element is not removed from the enumeration. *)\r | |
86 | \r | |
87 | val get : 'a t -> 'a option\r | |
88 | (** [get e] returns [None] if [e] is empty or [Some x] where [x] is\r | |
89 | the next element of [e], in which case the element is removed from the enumeration. *)\r | |
90 | \r | |
91 | val push : 'a t -> 'a -> unit\r | |
92 | (** [push e x] will add [x] at the beginning of [e]. *)\r | |
93 | \r | |
94 | val junk : 'a t -> unit\r | |
95 | (** [junk e] removes the first element from the enumeration, if any. *)\r | |
96 | \r | |
97 | val clone : 'a t -> 'a t\r | |
98 | (** [clone e] creates a new enumeration that is copy of [e]. If [e]\r | |
99 | is consumed by later operations, the clone will not get affected. *)\r | |
100 | \r | |
101 | val force : 'a t -> unit\r | |
102 | (** [force e] forces the application of all lazy functions and the\r | |
103 | enumeration of all elements, exhausting the enumeration. \r | |
104 | \r | |
105 | An efficient intermediate data structure\r | |
106 | of enumerated elements is constructed and [e] will now enumerate over\r | |
107 | that data structure. *)\r | |
108 | \r | |
109 | (** {6 Lazy constructors}\r | |
110 | \r | |
111 | These functions are lazy which means that they will create a new modified\r | |
112 | enumeration without actually enumerating any element until they are asked\r | |
113 | to do so by the programmer (using one of the functions above).\r | |
114 | \r | |
115 | When the resulting enumerations of these functions are consumed, the\r | |
116 | underlying enumerations they were created from are also consumed. *)\r | |
117 | \r | |
118 | val map : ('a -> 'b) -> 'a t -> 'b t\r | |
119 | (** [map f e] returns an enumeration over [(f a1, f a2, ... , f aN)] where\r | |
120 | a1...N are the elements of [e]. *)\r | |
121 | \r | |
122 | val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t\r | |
123 | (** [mapi] is similar to [map] except that [f] is passed one extra argument\r | |
124 | which is the index of the element in the enumeration, starting from 0. *)\r | |
125 | \r | |
126 | val filter : ('a -> bool) -> 'a t -> 'a t\r | |
127 | (** [filter f e] returns an enumeration over all elements [x] of [e] such\r | |
128 | as [f x] returns [true]. *)\r | |
129 | \r | |
130 | val filter_map : ('a -> 'b option) -> 'a t -> 'b t\r | |
131 | (** [filter_map f e] returns an enumeration over all elements [x] such as\r | |
132 | [f y] returns [Some x] , where [y] is an element of [e]. *)\r | |
133 | \r | |
134 | val append : 'a t -> 'a t -> 'a t\r | |
135 | (** [append e1 e2] returns an enumeration that will enumerate over all\r | |
136 | elements of [e1] followed by all elements of [e2]. *)\r | |
137 | \r | |
138 | val concat : 'a t t -> 'a t\r | |
139 | (** [concat e] returns an enumeration over all elements of all enumerations\r | |
140 | of [e]. *)\r | |
141 | \r | |
142 | (** {6 Constructors} \r | |
143 | \r | |
144 | In this section the word {i shall} denotes a semantic\r | |
145 | requirement. The correct operation\r | |
146 | of the functions in this interface are conditional\r | |
147 | on the client meeting these requirements.\r | |
148 | *)\r | |
149 | \r | |
150 | exception No_more_elements\r | |
151 | (** This exception {i shall} be raised by the [next] function of [make] \r | |
152 | or [from] when no more elements can be enumerated, it {i shall not}\r | |
153 | be raised by any function which is an argument to any\r | |
154 | other function specified in the interface.\r | |
155 | *)\r | |
156 | \r | |
157 | val empty : unit -> 'a t\r | |
158 | (** The empty enumeration : contains no element *)\r | |
159 | \r | |
160 | val make : next:(unit -> 'a) -> count:(unit -> int) -> clone:(unit -> 'a t) -> 'a t\r | |
161 | (** This function creates a fully defined enumeration.\r | |
162 | {ul {li the [next] function {i shall} return the next element of the\r | |
163 | enumeration or raise [No_more_elements] if the underlying data structure\r | |
164 | does not have any more elements to enumerate.}\r | |
165 | {li the [count] function {i shall} return the actual number of remaining\r | |
166 | elements in the enumeration.}\r | |
167 | {li the [clone] function {i shall} create a clone of the enumeration\r | |
168 | such as operations on the original enumeration will not affect the\r | |
169 | clone. }}\r | |
170 | \r | |
171 | For some samples on how to correctly use [make], you can have a look\r | |
172 | at implementation of [ExtList.enum]. \r | |
173 | *)\r | |
174 | \r | |
175 | val from : (unit -> 'a) -> 'a t\r | |
176 | (** [from next] creates an enumeration from the [next] function.\r | |
177 | [next] {i shall} return the next element of the enumeration or raise\r | |
178 | [No_more_elements] when no more elements can be enumerated. Since the\r | |
179 | enumeration definition is incomplete, a call to [clone] or [count] will\r | |
180 | result in a call to [force] that will enumerate all elements in order to\r | |
181 | return a correct value. *)\r | |
182 | \r | |
183 | val init : int -> (int -> 'a) -> 'a t\r | |
184 | (** [init n f] creates a new enumeration over elements\r | |
185 | [f 0, f 1, ..., f (n-1)] *)\r | |
186 | \r | |
187 | (** {6 Counting} *)\r | |
188 | \r | |
189 | val count : 'a t -> int\r | |
190 | (** [count e] returns the number of remaining elements in [e] without\r | |
191 | consuming the enumeration.\r | |
192 | \r | |
193 | Depending of the underlying data structure that is implementing the\r | |
194 | enumeration functions, the count operation can be costly, and even sometimes\r | |
195 | can cause a call to [force]. *)\r | |
196 | \r | |
197 | val fast_count : 'a t -> bool\r | |
198 | (** For users worried about the speed of [count] you can call the [fast_count]\r | |
199 | function that will give an hint about [count] implementation. Basically, if\r | |
200 | the enumeration has been created with [make] or [init] or if [force] has\r | |
201 | been called on it, then [fast_count] will return true. *)\r |