|
rpm-build |
0f2925 |
(*
|
|
rpm-build |
0f2925 |
* DynArray - Resizeable Ocaml arrays
|
|
rpm-build |
0f2925 |
* Copyright (C) 2003 Brian Hurt
|
|
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 |
(** Dynamic arrays.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
A dynamic array is equivalent to a OCaml array that will resize itself
|
|
rpm-build |
0f2925 |
when elements are added or removed, except that floats are boxed and
|
|
rpm-build |
0f2925 |
that no initialization element is required.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
type 'a t
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
exception Invalid_arg of int * string * string
|
|
rpm-build |
0f2925 |
(** When an operation on an array fails, [Invalid_arg] is raised. The
|
|
rpm-build |
0f2925 |
integer is the value that made the operation fail, the first string
|
|
rpm-build |
0f2925 |
contains the function name that has been called and the second string
|
|
rpm-build |
0f2925 |
contains the parameter name that made the operation fail.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Array creation} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val create : unit -> 'a t
|
|
rpm-build |
0f2925 |
(** [create()] returns a new empty dynamic array. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val make : int -> 'a t
|
|
rpm-build |
0f2925 |
(** [make count] returns an array with some memory already allocated so
|
|
rpm-build |
0f2925 |
up to [count] elements can be stored into it without resizing. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val init : int -> (int -> 'a) -> 'a t
|
|
rpm-build |
0f2925 |
(** [init n f] returns an array of [n] elements filled with values
|
|
rpm-build |
0f2925 |
returned by [f 0 , f 1, ... f (n-1)]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Array manipulation functions} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val empty : 'a t -> bool
|
|
rpm-build |
0f2925 |
(** Return true if the number of elements in the array is 0. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val length : 'a t -> int
|
|
rpm-build |
0f2925 |
(** Return the number of elements in the array. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val get : 'a t -> int -> 'a
|
|
rpm-build |
0f2925 |
(** [get darr idx] gets the element in [darr] at index [idx]. If [darr] has
|
|
rpm-build |
0f2925 |
[len] elements in it, then the valid indexes range from [0] to [len-1]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val last : 'a t -> 'a
|
|
rpm-build |
0f2925 |
(** [last darr] returns the last element of [darr]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val set : 'a t -> int -> 'a -> unit
|
|
rpm-build |
0f2925 |
(** [set darr idx v] sets the element of [darr] at index [idx] to value
|
|
rpm-build |
0f2925 |
[v]. The previous value is overwritten. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val insert : 'a t -> int -> 'a -> unit
|
|
rpm-build |
0f2925 |
(** [insert darr idx v] inserts [v] into [darr] at index [idx]. All elements
|
|
rpm-build |
0f2925 |
of [darr] with an index greater than or equal to [idx] have their
|
|
rpm-build |
0f2925 |
index incremented (are moved up one place) to make room for the new
|
|
rpm-build |
0f2925 |
element. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val add : 'a t -> 'a -> unit
|
|
rpm-build |
0f2925 |
(** [add darr v] appends [v] onto [darr]. [v] becomes the new
|
|
rpm-build |
0f2925 |
last element of [darr]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val append : 'a t -> 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [append src dst] adds all elements of [src] to the end of [dst]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val delete : 'a t -> int -> unit
|
|
rpm-build |
0f2925 |
(** [delete darr idx] deletes the element of [darr] at [idx]. All elements
|
|
rpm-build |
0f2925 |
with an index greater than [idx] have their index decremented (are
|
|
rpm-build |
0f2925 |
moved down one place) to fill in the hole. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val delete_last : 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [delete_last darr] deletes the last element of [darr]. This is equivalent
|
|
rpm-build |
0f2925 |
of doing [delete darr ((length darr) - 1)]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val delete_range : 'a t -> int -> int -> unit
|
|
rpm-build |
0f2925 |
(** [delete_range darr p len] deletes [len] elements starting at index [p].
|
|
rpm-build |
0f2925 |
All elements with an index greater than [p+len] are moved to fill
|
|
rpm-build |
0f2925 |
in the hole. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val clear : 'a t -> unit
|
|
rpm-build |
0f2925 |
(** remove all elements from the array and resize it to 0. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val blit : 'a t -> int -> 'a t -> int -> int -> unit
|
|
rpm-build |
0f2925 |
(** [blit src srcidx dst dstidx len] copies [len] elements from [src]
|
|
rpm-build |
0f2925 |
starting with index [srcidx] to [dst] starting at [dstidx]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val compact : 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [compact darr] ensures that the space allocated by the array is minimal.*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Array copy and conversion} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val to_list : 'a t -> 'a list
|
|
rpm-build |
0f2925 |
(** [to_list darr] returns the elements of [darr] in order as a list. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val to_array : 'a t -> 'a array
|
|
rpm-build |
0f2925 |
(** [to_array darr] returns the elements of [darr] in order as an array. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val enum : 'a t -> 'a Enum.t
|
|
rpm-build |
0f2925 |
(** [enum darr] returns the enumeration of [darr] elements. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val of_list : 'a list -> 'a t
|
|
rpm-build |
0f2925 |
(** [of_list lst] returns a dynamic array with the elements of [lst] in
|
|
rpm-build |
0f2925 |
it in order. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val of_array : 'a array -> 'a t
|
|
rpm-build |
0f2925 |
(** [of_array arr] returns an array with the elements of [arr] in it
|
|
rpm-build |
0f2925 |
in order. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val of_enum : 'a Enum.t -> 'a t
|
|
rpm-build |
0f2925 |
(** [of_enum e] returns an array that holds, in order, the elements of [e]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val copy : 'a t -> 'a t
|
|
rpm-build |
0f2925 |
(** [copy src] returns a fresh copy of [src], such that no modification of
|
|
rpm-build |
0f2925 |
[src] affects the copy, or vice versa (all new memory is allocated for
|
|
rpm-build |
0f2925 |
the copy). *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val sub : 'a t -> int -> int -> 'a t
|
|
rpm-build |
0f2925 |
(** [sub darr start len] returns an array holding the subset of [len]
|
|
rpm-build |
0f2925 |
elements from [darr] starting with the element at index [idx]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Array functional support} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iter : ('a -> unit) -> 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [iter f darr] calls the function [f] on every element of [darr]. It
|
|
rpm-build |
0f2925 |
is equivalent to [for i = 0 to length darr - 1 do f (get darr i) done;] *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val iteri : (int -> 'a -> unit) -> 'a t -> unit
|
|
rpm-build |
0f2925 |
(** [iteri f darr] calls the function [f] on every element of [darr]. It
|
|
rpm-build |
0f2925 |
is equivalent to [for i = 0 to length darr - 1 do f i (get darr i) done;]
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val map : ('a -> 'b) -> 'a t -> 'b t
|
|
rpm-build |
0f2925 |
(** [map f darr] applies the function [f] to every element of [darr]
|
|
rpm-build |
0f2925 |
and creates a dynamic array from the results - similar to [List.map] or
|
|
rpm-build |
0f2925 |
[Array.map]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
|
|
rpm-build |
0f2925 |
(** [mapi f darr] applies the function [f] to every element of [darr]
|
|
rpm-build |
0f2925 |
and creates a dynamic array from the results - similar to [List.mapi] or
|
|
rpm-build |
0f2925 |
[Array.mapi]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
|
|
rpm-build |
0f2925 |
(** [fold_left f x darr] computes
|
|
rpm-build |
0f2925 |
[f ( ... ( f ( f (get darr 0) x) (get darr 1) ) ... ) (get darr n-1)],
|
|
rpm-build |
0f2925 |
similar to [Array.fold_left] or [List.fold_left]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
|
|
rpm-build |
0f2925 |
(** [fold_right f darr x] computes
|
|
rpm-build |
0f2925 |
[ f (get darr 0) (f (get darr 1) ( ... ( f (get darr n-1) x ) ... ) ) ]
|
|
rpm-build |
0f2925 |
similar to [Array.fold_right] or [List.fold_right]. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val index_of : ('a -> bool) -> 'a t -> int
|
|
rpm-build |
0f2925 |
(** [index_of f darr] returns the index of the first element [x] in darr such
|
|
rpm-build |
0f2925 |
as [f x] returns [true] or raise [Not_found] if not found. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val filter : ('a -> bool) -> 'a t -> unit
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Array resizers} *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
type resizer_t = currslots:int -> oldlength:int -> newlength:int -> int
|
|
rpm-build |
0f2925 |
(** The type of a resizer function.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Resizer functions are called whenever elements are added to
|
|
rpm-build |
0f2925 |
or removed from the dynamic array to determine what the current number of
|
|
rpm-build |
0f2925 |
storage spaces in the array should be. The three named arguments
|
|
rpm-build |
0f2925 |
passed to a resizer are the current number of storage spaces in
|
|
rpm-build |
0f2925 |
the array, the length of the array before the elements are
|
|
rpm-build |
0f2925 |
added or removed, and the length the array will be after the
|
|
rpm-build |
0f2925 |
elements are added or removed. If elements are being added, newlength
|
|
rpm-build |
0f2925 |
will be larger than oldlength, if elements are being removed,
|
|
rpm-build |
0f2925 |
newlength will be smaller than oldlength. If the resizer function
|
|
rpm-build |
0f2925 |
returns exactly oldlength, the size of the array is only changed when
|
|
rpm-build |
0f2925 |
adding an element while there is not enough space for it.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
By default, all dynamic arrays are created with the [default_resizer].
|
|
rpm-build |
0f2925 |
When a dynamic array is created from another dynamic array (using [copy],
|
|
rpm-build |
0f2925 |
[map] , etc. ) the resizer of the copy will be the same as the original
|
|
rpm-build |
0f2925 |
dynamic array resizer. To change the resizer, use the [set_resizer]
|
|
rpm-build |
0f2925 |
function.
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val set_resizer : 'a t -> resizer_t -> unit
|
|
rpm-build |
0f2925 |
(** Change the resizer for this array. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val get_resizer : 'a t -> resizer_t
|
|
rpm-build |
0f2925 |
(** Get the current resizer function for a given array *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val default_resizer : resizer_t
|
|
rpm-build |
0f2925 |
(** The default resizer function the library is using - in this version
|
|
rpm-build |
0f2925 |
of DynArray, this is the [exponential_resizer] but should change in
|
|
rpm-build |
0f2925 |
next versions. *)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val exponential_resizer : resizer_t
|
|
rpm-build |
0f2925 |
(** The exponential resizer- The default resizer except when the resizer
|
|
rpm-build |
0f2925 |
is being copied from some other darray.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
[exponential_resizer] works by doubling or halving the number of
|
|
rpm-build |
0f2925 |
slots until they "fit". If the number of slots is less than the
|
|
rpm-build |
0f2925 |
new length, the number of slots is doubled until it is greater
|
|
rpm-build |
0f2925 |
than the new length (or Sys.max_array_size is reached).
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
If the number of slots is more than four times the new length,
|
|
rpm-build |
0f2925 |
the number of slots is halved until it is less than four times the
|
|
rpm-build |
0f2925 |
new length.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Allowing darrays to fall below 25% utilization before shrinking them
|
|
rpm-build |
0f2925 |
prevents "thrashing". Consider the case where the caller is constantly
|
|
rpm-build |
0f2925 |
adding a few elements, and then removing a few elements, causing
|
|
rpm-build |
0f2925 |
the length to constantly cross above and below a power of two.
|
|
rpm-build |
0f2925 |
Shrinking the array when it falls below 50% would causing the
|
|
rpm-build |
0f2925 |
underlying array to be constantly allocated and deallocated.
|
|
rpm-build |
0f2925 |
A few elements would be added, causing the array to be reallocated
|
|
rpm-build |
0f2925 |
and have a usage of just above 50%. Then a few elements would be
|
|
rpm-build |
0f2925 |
remove, and the array would fall below 50% utilization and be
|
|
rpm-build |
0f2925 |
reallocated yet again. The bulk of the array, untouched, would be
|
|
rpm-build |
0f2925 |
copied and copied again. By setting the threshold at 25% instead,
|
|
rpm-build |
0f2925 |
such "thrashing" only occurs with wild swings- adding and removing
|
|
rpm-build |
0f2925 |
huge numbers of elements (more than half of the elements in the array).
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
[exponential_resizer] is a good performing resizer for most
|
|
rpm-build |
0f2925 |
applications. A list allocates 2 words for every element, while an
|
|
rpm-build |
0f2925 |
array (with large numbers of elements) allocates only 1 word per
|
|
rpm-build |
0f2925 |
element (ignoring unboxed floats). On insert, [exponential_resizer]
|
|
rpm-build |
0f2925 |
keeps the amount of wasted "extra" array elements below 50%, meaning
|
|
rpm-build |
0f2925 |
that less than 2 words per element are used. Even on removals
|
|
rpm-build |
0f2925 |
where the amount of wasted space is allowed to rise to 75%, that
|
|
rpm-build |
0f2925 |
only means that darray is using 4 words per element. This is
|
|
rpm-build |
0f2925 |
generally not a significant overhead.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
Furthermore, [exponential_resizer] minimizes the number of copies
|
|
rpm-build |
0f2925 |
needed- appending n elements into an empty darray with initial size
|
|
rpm-build |
0f2925 |
0 requires between n and 2n elements of the array be copied- O(n)
|
|
rpm-build |
0f2925 |
work, or O(1) work per element (on average). A similar argument
|
|
rpm-build |
0f2925 |
can be made that deletes from the end of the array are O(1) as
|
|
rpm-build |
0f2925 |
well (obviously deletes from anywhere else are O(n) work- you
|
|
rpm-build |
0f2925 |
have to move the n or so elements above the deleted element down).
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val step_resizer : int -> resizer_t
|
|
rpm-build |
0f2925 |
(** The stepwise resizer- another example of a resizer function, this
|
|
rpm-build |
0f2925 |
time of a parameterized resizer.
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
The resizer returned by [step_resizer step] returns the smallest
|
|
rpm-build |
0f2925 |
multiple of [step] larger than [newlength] if [currslots] is less
|
|
rpm-build |
0f2925 |
then [newlength]-[step] or greater than [newlength].
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
For example, to make an darray with a step of 10, a length
|
|
rpm-build |
0f2925 |
of len, and a null of null, you would do:
|
|
rpm-build |
0f2925 |
[make] ~resizer:([step_resizer] 10) len null
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val conservative_exponential_resizer : resizer_t
|
|
rpm-build |
0f2925 |
(** [conservative_exponential_resizer] is an example resizer function
|
|
rpm-build |
0f2925 |
which uses the oldlength parameter. It only shrinks the array
|
|
rpm-build |
0f2925 |
on inserts- no deletes shrink the array, only inserts. It does
|
|
rpm-build |
0f2925 |
this by comparing the oldlength and newlength parameters. Other
|
|
rpm-build |
0f2925 |
than that, it acts like [exponential_resizer].
|
|
rpm-build |
0f2925 |
*)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
(** {6 Unsafe operations} **)
|
|
rpm-build |
0f2925 |
|
|
rpm-build |
0f2925 |
val unsafe_get : 'a t -> int -> 'a
|
|
rpm-build |
0f2925 |
val unsafe_set : 'a t -> int -> 'a -> unit
|