Sophie: ocaml-extlib-1.5.1-3mdv2010.0 i586

ocaml-extlib-1.5.1-3mdv2010.0.i586.rpm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="previous" href="Dllist.html">
<link rel="next" href="Enum.html">
<link rel="Up" href="index.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of class methods" rel=Appendix href="index_methods.html">
<link title="Index of classes" rel=Appendix href="index_classes.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Base64" rel="Chapter" href="Base64.html">
<link title="BitSet" rel="Chapter" href="BitSet.html">
<link title="Dllist" rel="Chapter" href="Dllist.html">
<link title="DynArray" rel="Chapter" href="DynArray.html">
<link title="Enum" rel="Chapter" href="Enum.html">
<link title="ExtArray" rel="Chapter" href="ExtArray.html">
<link title="ExtHashtbl" rel="Chapter" href="ExtHashtbl.html">
<link title="ExtList" rel="Chapter" href="ExtList.html">
<link title="ExtString" rel="Chapter" href="ExtString.html">
<link title="Global" rel="Chapter" href="Global.html">
<link title="IO" rel="Chapter" href="IO.html">
<link title="OptParse" rel="Chapter" href="OptParse.html">
<link title="Option" rel="Chapter" href="Option.html">
<link title="PMap" rel="Chapter" href="PMap.html">
<link title="RefList" rel="Chapter" href="RefList.html">
<link title="Std" rel="Chapter" href="Std.html">
<link title="UChar" rel="Chapter" href="UChar.html">
<link title="UTF8" rel="Chapter" href="UTF8.html">
<link title="Unzip" rel="Chapter" href="Unzip.html"><link title="Array creation" rel="Section" href="#6_Arraycreation">
<link title="Array manipulation functions" rel="Section" href="#6_Arraymanipulationfunctions">
<link title="Array copy and conversion" rel="Section" href="#6_Arraycopyandconversion">
<link title="Array functional support" rel="Section" href="#6_Arrayfunctionalsupport">
<link title="Array resizers" rel="Section" href="#6_Arrayresizers">
<link title="Unsafe operations" rel="Section" href="#6_Unsafeoperations">
<title>DynArray</title>
</head>
<body>
<div class="navbar"><a href="Dllist.html">Previous</a>
&nbsp;<a href="index.html">Up</a>
&nbsp;<a href="Enum.html">Next</a>
</div>
<center><h1>Module <a href="type_DynArray.html">DynArray</a></h1></center>
<br>
<pre><span class="keyword">module</span> DynArray: <code class="code">sig</code> <a href="DynArray.html">..</a> <code class="code">end</code></pre>Dynamic arrays.
<p>

   A dynamic array is equivalent to a OCaml array that will resize itself
   when elements are added or removed, except that floats are boxed and
   that no initialization element is required.<br>
<hr width="100%">
<pre><span class="keyword">type</span> <a name="TYPEt"></a><code class="type">'a</code> t </pre>

<pre><span class="keyword">exception</span> <a name="EXCEPTIONInvalid_arg"></a>Invalid_arg <span class="keyword">of</span> <code class="type">int * string * string</code></pre>
<div class="info">
When an operation on an array fails, <code class="code">Invalid_arg</code> is raised. The
	integer is the value that made the operation fail, the first string
	contains the function name that has been called and the second string
	contains the parameter name that made the operation fail.<br>
</div>
<br>
<a name="6_Arraycreation"></a>
<h6>Array creation</h6><br>
<pre><span class="keyword">val</span> <a name="VALcreate"></a>create : <code class="type">unit -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">create()</code> returns a new empty dynamic array.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALmake"></a>make : <code class="type">int -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">make count</code> returns an array with some memory already allocated so
	up to <code class="code">count</code> elements can be stored into it without resizing.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALinit"></a>init : <code class="type">int -> (int -> 'a) -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">init n f</code> returns an array of <code class="code">n</code> elements filled with values
	returned by <code class="code">f 0 , f 1, ... f (n-1)</code>.<br>
</div>
<br>
<a name="6_Arraymanipulationfunctions"></a>
<h6>Array manipulation functions</h6><br>
<pre><span class="keyword">val</span> <a name="VALempty"></a>empty : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> bool</code></pre><div class="info">
Return true if the number of elements in the array is 0.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALlength"></a>length : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int</code></pre><div class="info">
Return the number of elements in the array.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALget"></a>get : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a</code></pre><div class="info">
<code class="code">get darr idx</code> gets the element in <code class="code">darr</code> at index <code class="code">idx</code>. If <code class="code">darr</code> has
	<code class="code">len</code> elements in it, then the valid indexes range from <code class="code">0</code> to <code class="code">len-1</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALlast"></a>last : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">last darr</code> returns the last element of <code class="code">darr</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALset"></a>set : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a -> unit</code></pre><div class="info">
<code class="code">set darr idx v</code> sets the element of <code class="code">darr</code> at index <code class="code">idx</code> to value
	<code class="code">v</code>.  The previous value is overwritten.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALinsert"></a>insert : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a -> unit</code></pre><div class="info">
<code class="code">insert darr idx v</code> inserts <code class="code">v</code> into <code class="code">darr</code> at index <code class="code">idx</code>.  All elements
	of <code class="code">darr</code> with an index greater than or equal to <code class="code">idx</code> have their
	index incremented (are moved up one place) to make room for the new
	element.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALadd"></a>add : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a -> unit</code></pre><div class="info">
<code class="code">add darr v</code> appends <code class="code">v</code> onto <code class="code">darr</code>.  <code class="code">v</code> becomes the new
	last element of <code class="code">darr</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALappend"></a>append : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">append src dst</code> adds all elements of <code class="code">src</code> to the end of <code class="code">dst</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALdelete"></a>delete : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> unit</code></pre><div class="info">
<code class="code">delete darr idx</code> deletes the element of <code class="code">darr</code> at <code class="code">idx</code>.  All elements
	with an index greater than <code class="code">idx</code> have their index decremented (are
	moved down one place) to fill in the hole.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALdelete_last"></a>delete_last : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">delete_last darr</code> deletes the last element of <code class="code">darr</code>. This is equivalent
	of doing <code class="code">delete darr ((length darr) - 1)</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALdelete_range"></a>delete_range : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> int -> unit</code></pre><div class="info">
<code class="code">delete_range darr p len</code> deletes <code class="code">len</code> elements starting at index <code class="code">p</code>.
	All elements with an index greater than <code class="code">p+len</code> are moved to fill
	in the hole.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALclear"></a>clear : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
remove all elements from the array and resize it to 0.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALblit"></a>blit : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a <a href="DynArray.html#TYPEt">t</a> -> int -> int -> unit</code></pre><div class="info">
<code class="code">blit src srcidx dst dstidx len</code> copies <code class="code">len</code> elements from <code class="code">src</code>
	starting with index <code class="code">srcidx</code> to <code class="code">dst</code> starting at <code class="code">dstidx</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcompact"></a>compact : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">compact darr</code> ensures that the space allocated by the array is minimal.<br>
</div>
<br>
<a name="6_Arraycopyandconversion"></a>
<h6>Array copy and conversion</h6><br>
<pre><span class="keyword">val</span> <a name="VALto_list"></a>to_list : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a list</code></pre><div class="info">
<code class="code">to_list darr</code> returns the elements of <code class="code">darr</code> in order as a list.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALto_array"></a>to_array : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a array</code></pre><div class="info">
<code class="code">to_array darr</code> returns the elements of <code class="code">darr</code> in order as an array.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALenum"></a>enum : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a <a href="Enum.html#TYPEt">Enum.t</a></code></pre><div class="info">
<code class="code">enum darr</code> returns the enumeration of <code class="code">darr</code> elements.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALof_list"></a>of_list : <code class="type">'a list -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">of_list lst</code> returns a dynamic array with the elements of <code class="code">lst</code> in
	it in order.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALof_array"></a>of_array : <code class="type">'a array -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">of_array arr</code> returns an array with the elements of <code class="code">arr</code> in it
	in order.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALof_enum"></a>of_enum : <code class="type">'a <a href="Enum.html#TYPEt">Enum.t</a> -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">of_enum e</code> returns an array that holds, in order, the elements of <code class="code">e</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALcopy"></a>copy : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">copy src</code> returns a fresh copy of <code class="code">src</code>, such that no modification of
	<code class="code">src</code> affects the copy, or vice versa (all new memory is allocated for
	the copy).<br>
</div>
<pre><span class="keyword">val</span> <a name="VALsub"></a>sub : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> int -> 'a <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">sub darr start len</code> returns an array holding the subset of <code class="code">len</code>
	elements from <code class="code">darr</code> starting with the element at index <code class="code">idx</code>.<br>
</div>
<br>
<a name="6_Arrayfunctionalsupport"></a>
<h6>Array functional support</h6><br>
<pre><span class="keyword">val</span> <a name="VALiter"></a>iter : <code class="type">('a -> unit) -> 'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">iter f darr</code> calls the function <code class="code">f</code> on every element of <code class="code">darr</code>.  It
	is equivalent to <code class="code">for i = 0 to length darr - 1 do f (get darr i) done;</code><br>
</div>
<pre><span class="keyword">val</span> <a name="VALiteri"></a>iteri : <code class="type">(int -> 'a -> unit) -> 'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><div class="info">
<code class="code">iter f darr</code> calls the function <code class="code">f</code> on every element of <code class="code">darr</code>.  It
	is equivalent to <code class="code">for i = 0 to length darr - 1 do f i (get darr i) done;</code><br>
</div>
<pre><span class="keyword">val</span> <a name="VALmap"></a>map : <code class="type">('a -> 'b) -> 'a <a href="DynArray.html#TYPEt">t</a> -> 'b <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">map f darr</code> applies the function <code class="code">f</code> to every element of <code class="code">darr</code>
	and creates a dynamic array from the results - similar to <code class="code">List.map</code> or
	<code class="code">Array.map</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALmapi"></a>mapi : <code class="type">(int -> 'a -> 'b) -> 'a <a href="DynArray.html#TYPEt">t</a> -> 'b <a href="DynArray.html#TYPEt">t</a></code></pre><div class="info">
<code class="code">mapi f darr</code> applies the function <code class="code">f</code> to every element of <code class="code">darr</code>
	and creates a dynamic array from the results - similar to <code class="code">List.mapi</code> or
	<code class="code">Array.mapi</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfold_left"></a>fold_left : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="DynArray.html#TYPEt">t</a> -> 'a</code></pre><div class="info">
<code class="code">fold_left f x darr</code> computes
	<code class="code">f ( ... ( f ( f (get darr 0) x) (get darr 1) ) ... ) (get darr n-1)</code>,
	similar to <code class="code">Array.fold_left</code> or <code class="code">List.fold_left</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfold_right"></a>fold_right : <code class="type">('a -> 'b -> 'b) -> 'a <a href="DynArray.html#TYPEt">t</a> -> 'b -> 'b</code></pre><div class="info">
<code class="code">fold_right f darr x</code> computes
	<code class="code"> f (get darr 0) (f (get darr 1) ( ... ( f (get darr n-1) x ) ... ) ) </code>
	similar to <code class="code">Array.fold_right</code> or <code class="code">List.fold_right</code>.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALindex_of"></a>index_of : <code class="type">('a -> bool) -> 'a <a href="DynArray.html#TYPEt">t</a> -> int</code></pre><div class="info">
<code class="code">index_of f darr</code> returns the index of the first element <code class="code">x</code> in darr such
	as <code class="code">f x</code> returns <code class="code">true</code> or raise <code class="code">Not_found</code> if not found.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALfilter"></a>filter : <code class="type">('a -> bool) -> 'a <a href="DynArray.html#TYPEt">t</a> -> unit</code></pre><br>
<a name="6_Arrayresizers"></a>
<h6>Array resizers</h6><br>
<pre><span class="keyword">type</span> <a name="TYPEresizer_t"></a><code class="type"></code>resizer_t = <code class="type">currslots:int -> oldlength:int -> newlength:int -> int</code> </pre>
<div class="info">
The type of a resizer function.
<p>

	Resizer functions are called whenever elements are added to
	or removed from the dynamic array to determine what the current number of
	storage spaces in the array should be.  The three named arguments
	passed to a resizer are the current number of storage spaces in
	the array, the length of the array before the elements are
	added or removed, and the length the array will be after the
	elements are added or removed.  If elements are being added, newlength
	will be larger than oldlength, if elements are being removed,
	newlength will be smaller than oldlength. If the resizer function
	returns exactly oldlength, the size of the array is only changed when
	adding an element while there is not enough space for it.
<p>

	By default, all dynamic arrays are created with the <code class="code">default_resizer</code>.
	When a dynamic array is created from another dynamic array (using <code class="code">copy</code>,
	<code class="code">map</code> , etc. ) the resizer of the copy will be the same as the original
	dynamic array resizer. To change the resizer, use the <code class="code">set_resizer</code>
	function.<br>
</div>

<pre><span class="keyword">val</span> <a name="VALset_resizer"></a>set_resizer : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> <a href="DynArray.html#TYPEresizer_t">resizer_t</a> -> unit</code></pre><div class="info">
Change the resizer for this array.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALget_resizer"></a>get_resizer : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> <a href="DynArray.html#TYPEresizer_t">resizer_t</a></code></pre><div class="info">
Get the current resizer function for a given array<br>
</div>
<pre><span class="keyword">val</span> <a name="VALdefault_resizer"></a>default_resizer : <code class="type"><a href="DynArray.html#TYPEresizer_t">resizer_t</a></code></pre><div class="info">
The default resizer function the library is using - in this version
	of DynArray, this is the <code class="code">exponential_resizer</code> but should change in
	next versions.<br>
</div>
<pre><span class="keyword">val</span> <a name="VALexponential_resizer"></a>exponential_resizer : <code class="type"><a href="DynArray.html#TYPEresizer_t">resizer_t</a></code></pre><div class="info">
The exponential resizer- The default resizer except when the resizer
	is being copied from some other darray.
<p>

	<code class="code">exponential_resizer</code> works by doubling or halving the number of
	slots until they "fit".  If the number of slots is less than the
	new length, the number of slots is doubled until it is greater
	than the new length (or Sys.max_array_size is reached).
<p>

	If the number of slots is more than four times the new length,
	the number of slots is halved until it is less than four times the
	new length.
<p>

	Allowing darrays to fall below 25% utilization before shrinking them
	prevents "thrashing".  Consider the case where the caller is constantly
	adding a few elements, and then removing a few elements, causing
	the length to constantly cross above and below a power of two.
	Shrinking the array when it falls below 50% would causing the
	underlying array to be constantly allocated and deallocated.
	A few elements would be added, causing the array to be reallocated
	and have a usage of just above 50%.  Then a few elements would be
	remove, and the array would fall below 50% utilization and be
	reallocated yet again.  The bulk of the array, untouched, would be
	copied and copied again.  By setting the threshold at 25% instead,
	such "thrashing" only occurs with wild swings- adding and removing
	huge numbers of elements (more than half of the elements in the array).
<p>

	<code class="code">exponential_resizer</code> is a good performing resizer for most
	applications.  A list allocates 2 words for every element, while an
	array (with large numbers of elements) allocates only 1 word per
	element (ignoring unboxed floats).  On insert, <code class="code">exponential_resizer</code>
	keeps the amount of wasted "extra" array elements below 50%, meaning
	that less than 2 words per element are used.  Even on removals
	where the amount of wasted space is allowed to rise to 75%, that
	only means that darray is using 4 words per element.  This is
	generally not a significant overhead.
<p>

	Furthermore, <code class="code">exponential_resizer</code> minimizes the number of copies
	needed- appending n elements into an empty darray with initial size
	0 requires between n and 2n elements of the array be copied- O(n)
	work, or O(1) work per element (on average).  A similar argument
	can be made that deletes from the end of the array are O(1) as
	well (obviously deletes from anywhere else are O(n) work- you
	have to move the n or so elements above the deleted element down).<br>
</div>
<pre><span class="keyword">val</span> <a name="VALstep_resizer"></a>step_resizer : <code class="type">int -> <a href="DynArray.html#TYPEresizer_t">resizer_t</a></code></pre><div class="info">
The stepwise resizer- another example of a resizer function, this
	time of a parameterized resizer.
<p>

	The resizer returned by <code class="code">step_resizer step</code> returns the smallest
	multiple of <code class="code">step</code> larger than <code class="code">newlength</code> if <code class="code">currslots</code> is less
	then <code class="code">newlength</code>-<code class="code">step</code> or greater than <code class="code">newlength</code>.
<p>

	For example, to make an darray with a step of 10, a length
	of len, and a null of null, you would do:
	<code class="code">make</code> ~resizer:(<code class="code">step_resizer</code> 10) len null<br>
</div>
<pre><span class="keyword">val</span> <a name="VALconservative_exponential_resizer"></a>conservative_exponential_resizer : <code class="type"><a href="DynArray.html#TYPEresizer_t">resizer_t</a></code></pre><div class="info">
<code class="code">conservative_exponential_resizer</code> is an example resizer function
	which uses the oldlength parameter.  It only shrinks the array
	on inserts- no deletes shrink the array, only inserts.  It does
	this by comparing the oldlength and newlength parameters.  Other
	than that, it acts like <code class="code">exponential_resizer</code>.<br>
</div>
<br>
<a name="6_Unsafeoperations"></a>
<h6>Unsafe operations</h6> *<br>
<pre><span class="keyword">val</span> <a name="VALunsafe_get"></a>unsafe_get : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a</code></pre><pre><span class="keyword">val</span> <a name="VALunsafe_set"></a>unsafe_set : <code class="type">'a <a href="DynArray.html#TYPEt">t</a> -> int -> 'a -> unit</code></pre></body></html>