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