Commit | Line | Data |
---|---|---|
97111a47 C |
1 | (* |
2 | * DynArray - Resizeable Ocaml arrays | |
3 | * Copyright (C) 2003 Brian Hurt | |
4 | * Copyright (C) 2003 Nicolas Cannasse | |
5 | * | |
6 | * This library is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU Lesser General Public | |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2.1 of the License, or (at your option) any later version, | |
10 | * with the special exception on linking described in file LICENSE. | |
11 | * | |
12 | * This library is distributed in the hope that it will be useful, | |
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | * Lesser General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU Lesser General Public | |
18 | * License along with this library; if not, write to the Free Software | |
19 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
20 | *) | |
21 | ||
22 | (** Dynamic arrays. | |
23 | ||
24 | A dynamic array is equivalent to a OCaml array that will resize itself | |
25 | when elements are added or removed, except that floats are boxed and | |
26 | that no initialization element is required. | |
27 | *) | |
28 | ||
29 | type 'a t | |
30 | ||
31 | exception Invalid_arg of int * string * string | |
32 | (** When an operation on an array fails, [Invalid_arg] is raised. The | |
33 | integer is the value that made the operation fail, the first string | |
34 | contains the function name that has been called and the second string | |
35 | contains the parameter name that made the operation fail. | |
36 | *) | |
37 | ||
38 | (** {6 Array creation} *) | |
39 | ||
40 | val create : unit -> 'a t | |
41 | (** [create()] returns a new empty dynamic array. *) | |
42 | ||
43 | val make : int -> 'a t | |
44 | (** [make count] returns an array with some memory already allocated so | |
45 | up to [count] elements can be stored into it without resizing. *) | |
46 | ||
47 | val init : int -> (int -> 'a) -> 'a t | |
48 | (** [init n f] returns an array of [n] elements filled with values | |
49 | returned by [f 0 , f 1, ... f (n-1)]. *) | |
50 | ||
51 | (** {6 Array manipulation functions} *) | |
52 | ||
53 | val empty : 'a t -> bool | |
54 | (** Return true if the number of elements in the array is 0. *) | |
55 | ||
56 | val length : 'a t -> int | |
57 | (** Return the number of elements in the array. *) | |
58 | ||
59 | val get : 'a t -> int -> 'a | |
60 | (** [get darr idx] gets the element in [darr] at index [idx]. If [darr] has | |
61 | [len] elements in it, then the valid indexes range from [0] to [len-1]. *) | |
62 | ||
63 | val last : 'a t -> 'a | |
64 | (** [last darr] returns the last element of [darr]. *) | |
65 | ||
66 | val set : 'a t -> int -> 'a -> unit | |
67 | (** [set darr idx v] sets the element of [darr] at index [idx] to value | |
68 | [v]. The previous value is overwritten. *) | |
69 | ||
70 | val insert : 'a t -> int -> 'a -> unit | |
71 | (** [insert darr idx v] inserts [v] into [darr] at index [idx]. All elements | |
72 | of [darr] with an index greater than or equal to [idx] have their | |
73 | index incremented (are moved up one place) to make room for the new | |
74 | element. *) | |
75 | ||
76 | val add : 'a t -> 'a -> unit | |
77 | (** [add darr v] appends [v] onto [darr]. [v] becomes the new | |
78 | last element of [darr]. *) | |
79 | ||
80 | val append : 'a t -> 'a t -> unit | |
81 | (** [append src dst] adds all elements of [src] to the end of [dst]. *) | |
82 | ||
83 | val delete : 'a t -> int -> unit | |
84 | (** [delete darr idx] deletes the element of [darr] at [idx]. All elements | |
85 | with an index greater than [idx] have their index decremented (are | |
86 | moved down one place) to fill in the hole. *) | |
87 | ||
88 | val delete_last : 'a t -> unit | |
89 | (** [delete_last darr] deletes the last element of [darr]. This is equivalent | |
90 | of doing [delete darr ((length darr) - 1)]. *) | |
91 | ||
92 | val delete_range : 'a t -> int -> int -> unit | |
93 | (** [delete_range darr p len] deletes [len] elements starting at index [p]. | |
94 | All elements with an index greater than [p+len] are moved to fill | |
95 | in the hole. *) | |
96 | ||
97 | val clear : 'a t -> unit | |
98 | (** remove all elements from the array and resize it to 0. *) | |
99 | ||
100 | val blit : 'a t -> int -> 'a t -> int -> int -> unit | |
101 | (** [blit src srcidx dst dstidx len] copies [len] elements from [src] | |
102 | starting with index [srcidx] to [dst] starting at [dstidx]. *) | |
103 | ||
104 | val compact : 'a t -> unit | |
105 | (** [compact darr] ensures that the space allocated by the array is minimal.*) | |
106 | ||
107 | (** {6 Array copy and conversion} *) | |
108 | ||
109 | val to_list : 'a t -> 'a list | |
110 | (** [to_list darr] returns the elements of [darr] in order as a list. *) | |
111 | ||
112 | val to_array : 'a t -> 'a array | |
113 | (** [to_array darr] returns the elements of [darr] in order as an array. *) | |
114 | ||
115 | val enum : 'a t -> 'a Enum.t | |
116 | (** [enum darr] returns the enumeration of [darr] elements. *) | |
117 | ||
118 | val of_list : 'a list -> 'a t | |
119 | (** [of_list lst] returns a dynamic array with the elements of [lst] in | |
120 | it in order. *) | |
121 | ||
122 | val of_array : 'a array -> 'a t | |
123 | (** [of_array arr] returns an array with the elements of [arr] in it | |
124 | in order. *) | |
125 | ||
126 | val of_enum : 'a Enum.t -> 'a t | |
127 | (** [of_enum e] returns an array that holds, in order, the elements of [e]. *) | |
128 | ||
129 | val copy : 'a t -> 'a t | |
130 | (** [copy src] returns a fresh copy of [src], such that no modification of | |
131 | [src] affects the copy, or vice versa (all new memory is allocated for | |
132 | the copy). *) | |
133 | ||
134 | val sub : 'a t -> int -> int -> 'a t | |
135 | (** [sub darr start len] returns an array holding the subset of [len] | |
136 | elements from [darr] starting with the element at index [idx]. *) | |
137 | ||
138 | (** {6 Array functional support} *) | |
139 | ||
140 | val iter : ('a -> unit) -> 'a t -> unit | |
141 | (** [iter f darr] calls the function [f] on every element of [darr]. It | |
142 | is equivalent to [for i = 0 to length darr - 1 do f (get darr i) done;] *) | |
143 | ||
144 | val iteri : (int -> 'a -> unit) -> 'a t -> unit | |
145 | (** [iter f darr] calls the function [f] on every element of [darr]. It | |
146 | is equivalent to [for i = 0 to length darr - 1 do f i (get darr i) done;] | |
147 | *) | |
148 | ||
149 | val map : ('a -> 'b) -> 'a t -> 'b t | |
150 | (** [map f darr] applies the function [f] to every element of [darr] | |
151 | and creates a dynamic array from the results - similar to [List.map] or | |
152 | [Array.map]. *) | |
153 | ||
154 | val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t | |
155 | (** [mapi f darr] applies the function [f] to every element of [darr] | |
156 | and creates a dynamic array from the results - similar to [List.mapi] or | |
157 | [Array.mapi]. *) | |
158 | ||
159 | val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a | |
160 | (** [fold_left f x darr] computes | |
161 | [f ( ... ( f ( f (get darr 0) x) (get darr 1) ) ... ) (get darr n-1)], | |
162 | similar to [Array.fold_left] or [List.fold_left]. *) | |
163 | ||
164 | val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b | |
165 | (** [fold_right f darr x] computes | |
166 | [ f (get darr 0) (f (get darr 1) ( ... ( f (get darr n-1) x ) ... ) ) ] | |
167 | similar to [Array.fold_right] or [List.fold_right]. *) | |
168 | ||
169 | val index_of : ('a -> bool) -> 'a t -> int | |
170 | (** [index_of f darr] returns the index of the first element [x] in darr such | |
171 | as [f x] returns [true] or raise [Not_found] if not found. *) | |
172 | ||
173 | val filter : ('a -> bool) -> 'a t -> unit | |
174 | ||
175 | (** {6 Array resizers} *) | |
176 | ||
177 | type resizer_t = currslots:int -> oldlength:int -> newlength:int -> int | |
178 | (** The type of a resizer function. | |
179 | ||
180 | Resizer functions are called whenever elements are added to | |
181 | or removed from the dynamic array to determine what the current number of | |
182 | storage spaces in the array should be. The three named arguments | |
183 | passed to a resizer are the current number of storage spaces in | |
184 | the array, the length of the array before the elements are | |
185 | added or removed, and the length the array will be after the | |
186 | elements are added or removed. If elements are being added, newlength | |
187 | will be larger than oldlength, if elements are being removed, | |
188 | newlength will be smaller than oldlength. If the resizer function | |
189 | returns exactly oldlength, the size of the array is only changed when | |
190 | adding an element while there is not enough space for it. | |
191 | ||
192 | By default, all dynamic arrays are created with the [default_resizer]. | |
193 | When a dynamic array is created from another dynamic array (using [copy], | |
194 | [map] , etc. ) the resizer of the copy will be the same as the original | |
195 | dynamic array resizer. To change the resizer, use the [set_resizer] | |
196 | function. | |
197 | *) | |
198 | ||
199 | val set_resizer : 'a t -> resizer_t -> unit | |
200 | (** Change the resizer for this array. *) | |
201 | ||
202 | val get_resizer : 'a t -> resizer_t | |
203 | (** Get the current resizer function for a given array *) | |
204 | ||
205 | val default_resizer : resizer_t | |
206 | (** The default resizer function the library is using - in this version | |
207 | of DynArray, this is the [exponential_resizer] but should change in | |
208 | next versions. *) | |
209 | ||
210 | val exponential_resizer : resizer_t | |
211 | (** The exponential resizer- The default resizer except when the resizer | |
212 | is being copied from some other darray. | |
213 | ||
214 | [exponential_resizer] works by doubling or halving the number of | |
215 | slots until they "fit". If the number of slots is less than the | |
216 | new length, the number of slots is doubled until it is greater | |
217 | than the new length (or Sys.max_array_size is reached). | |
218 | ||
219 | If the number of slots is more than four times the new length, | |
220 | the number of slots is halved until it is less than four times the | |
221 | new length. | |
222 | ||
223 | Allowing darrays to fall below 25% utilization before shrinking them | |
224 | prevents "thrashing". Consider the case where the caller is constantly | |
225 | adding a few elements, and then removing a few elements, causing | |
226 | the length to constantly cross above and below a power of two. | |
227 | Shrinking the array when it falls below 50% would causing the | |
228 | underlying array to be constantly allocated and deallocated. | |
229 | A few elements would be added, causing the array to be reallocated | |
230 | and have a usage of just above 50%. Then a few elements would be | |
231 | remove, and the array would fall below 50% utilization and be | |
232 | reallocated yet again. The bulk of the array, untouched, would be | |
233 | copied and copied again. By setting the threshold at 25% instead, | |
234 | such "thrashing" only occurs with wild swings- adding and removing | |
235 | huge numbers of elements (more than half of the elements in the array). | |
236 | ||
237 | [exponential_resizer] is a good performing resizer for most | |
238 | applications. A list allocates 2 words for every element, while an | |
239 | array (with large numbers of elements) allocates only 1 word per | |
240 | element (ignoring unboxed floats). On insert, [exponential_resizer] | |
241 | keeps the amount of wasted "extra" array elements below 50%, meaning | |
242 | that less than 2 words per element are used. Even on removals | |
243 | where the amount of wasted space is allowed to rise to 75%, that | |
244 | only means that darray is using 4 words per element. This is | |
245 | generally not a significant overhead. | |
246 | ||
247 | Furthermore, [exponential_resizer] minimizes the number of copies | |
248 | needed- appending n elements into an empty darray with initial size | |
249 | 0 requires between n and 2n elements of the array be copied- O(n) | |
250 | work, or O(1) work per element (on average). A similar argument | |
251 | can be made that deletes from the end of the array are O(1) as | |
252 | well (obviously deletes from anywhere else are O(n) work- you | |
253 | have to move the n or so elements above the deleted element down). | |
254 | ||
255 | *) | |
256 | ||
257 | val step_resizer : int -> resizer_t | |
258 | (** The stepwise resizer- another example of a resizer function, this | |
259 | time of a parameterized resizer. | |
260 | ||
261 | The resizer returned by [step_resizer step] returns the smallest | |
262 | multiple of [step] larger than [newlength] if [currslots] is less | |
263 | then [newlength]-[step] or greater than [newlength]. | |
264 | ||
265 | For example, to make an darray with a step of 10, a length | |
266 | of len, and a null of null, you would do: | |
267 | [make] ~resizer:([step_resizer] 10) len null | |
268 | *) | |
269 | ||
270 | val conservative_exponential_resizer : resizer_t | |
271 | (** [conservative_exponential_resizer] is an example resizer function | |
272 | which uses the oldlength parameter. It only shrinks the array | |
273 | on inserts- no deletes shrink the array, only inserts. It does | |
274 | this by comparing the oldlength and newlength parameters. Other | |
275 | than that, it acts like [exponential_resizer]. | |
276 | *) | |
277 | ||
278 | (** {6 Unsafe operations} **) | |
279 | ||
280 | val unsafe_get : 'a t -> int -> 'a | |
281 | val unsafe_set : 'a t -> int -> 'a -> unit |