commons/ocamlextra/dynArray.mli

   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