<!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="Batteries.Bit_set.html">
<link rel="next" href="Batteries.DynArray.html">
<link rel="Up" href="Batteries.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="Index of module types" rel=Appendix href="index_module_types.html">
<link title="BatArray" rel="Chapter" href="BatArray.html">
<link title="BatAvlTree" rel="Chapter" href="BatAvlTree.html">
<link title="BatBase64" rel="Chapter" href="BatBase64.html">
<link title="BatBig_int" rel="Chapter" href="BatBig_int.html">
<link title="BatBigarray" rel="Chapter" href="BatBigarray.html">
<link title="BatBitSet" rel="Chapter" href="BatBitSet.html">
<link title="BatBool" rel="Chapter" href="BatBool.html">
<link title="BatBounded" rel="Chapter" href="BatBounded.html">
<link title="BatBuffer" rel="Chapter" href="BatBuffer.html">
<link title="BatCache" rel="Chapter" href="BatCache.html">
<link title="BatChar" rel="Chapter" href="BatChar.html">
<link title="BatCharParser" rel="Chapter" href="BatCharParser.html">
<link title="BatComplex" rel="Chapter" href="BatComplex.html">
<link title="BatConcurrent" rel="Chapter" href="BatConcurrent.html">
<link title="BatDeque" rel="Chapter" href="BatDeque.html">
<link title="BatDigest" rel="Chapter" href="BatDigest.html">
<link title="BatDllist" rel="Chapter" href="BatDllist.html">
<link title="BatDynArray" rel="Chapter" href="BatDynArray.html">
<link title="BatEnum" rel="Chapter" href="BatEnum.html">
<link title="BatFile" rel="Chapter" href="BatFile.html">
<link title="BatFingerTree" rel="Chapter" href="BatFingerTree.html">
<link title="BatFloat" rel="Chapter" href="BatFloat.html">
<link title="BatFormat" rel="Chapter" href="BatFormat.html">
<link title="BatGc" rel="Chapter" href="BatGc.html">
<link title="BatGenlex" rel="Chapter" href="BatGenlex.html">
<link title="BatGlobal" rel="Chapter" href="BatGlobal.html">
<link title="BatHashcons" rel="Chapter" href="BatHashcons.html">
<link title="BatHashtbl" rel="Chapter" href="BatHashtbl.html">
<link title="BatHeap" rel="Chapter" href="BatHeap.html">
<link title="BatIMap" rel="Chapter" href="BatIMap.html">
<link title="BatIO" rel="Chapter" href="BatIO.html">
<link title="BatISet" rel="Chapter" href="BatISet.html">
<link title="BatInnerIO" rel="Chapter" href="BatInnerIO.html">
<link title="BatInnerPervasives" rel="Chapter" href="BatInnerPervasives.html">
<link title="BatInnerWeaktbl" rel="Chapter" href="BatInnerWeaktbl.html">
<link title="BatInt" rel="Chapter" href="BatInt.html">
<link title="BatInt32" rel="Chapter" href="BatInt32.html">
<link title="BatInt64" rel="Chapter" href="BatInt64.html">
<link title="BatInterfaces" rel="Chapter" href="BatInterfaces.html">
<link title="BatLazyList" rel="Chapter" href="BatLazyList.html">
<link title="BatLexing" rel="Chapter" href="BatLexing.html">
<link title="BatList" rel="Chapter" href="BatList.html">
<link title="BatLog" rel="Chapter" href="BatLog.html">
<link title="BatLogger" rel="Chapter" href="BatLogger.html">
<link title="BatMap" rel="Chapter" href="BatMap.html">
<link title="BatMarshal" rel="Chapter" href="BatMarshal.html">
<link title="BatMultiMap" rel="Chapter" href="BatMultiMap.html">
<link title="BatMultiPMap" rel="Chapter" href="BatMultiPMap.html">
<link title="BatMutex" rel="Chapter" href="BatMutex.html">
<link title="BatNativeint" rel="Chapter" href="BatNativeint.html">
<link title="BatNum" rel="Chapter" href="BatNum.html">
<link title="BatNumber" rel="Chapter" href="BatNumber.html">
<link title="BatOo" rel="Chapter" href="BatOo.html">
<link title="BatOptParse" rel="Chapter" href="BatOptParse.html">
<link title="BatOption" rel="Chapter" href="BatOption.html">
<link title="BatOrd" rel="Chapter" href="BatOrd.html">
<link title="BatParserCo" rel="Chapter" href="BatParserCo.html">
<link title="BatPathGen" rel="Chapter" href="BatPathGen.html">
<link title="BatPervasives" rel="Chapter" href="BatPervasives.html">
<link title="BatPrintexc" rel="Chapter" href="BatPrintexc.html">
<link title="BatPrintf" rel="Chapter" href="BatPrintf.html">
<link title="BatQueue" rel="Chapter" href="BatQueue.html">
<link title="BatRMutex" rel="Chapter" href="BatRMutex.html">
<link title="BatRandom" rel="Chapter" href="BatRandom.html">
<link title="BatRef" rel="Chapter" href="BatRef.html">
<link title="BatRefList" rel="Chapter" href="BatRefList.html">
<link title="BatResult" rel="Chapter" href="BatResult.html">
<link title="BatReturn" rel="Chapter" href="BatReturn.html">
<link title="BatScanf" rel="Chapter" href="BatScanf.html">
<link title="BatSeq" rel="Chapter" href="BatSeq.html">
<link title="BatSet" rel="Chapter" href="BatSet.html">
<link title="BatSplay" rel="Chapter" href="BatSplay.html">
<link title="BatStack" rel="Chapter" href="BatStack.html">
<link title="BatStream" rel="Chapter" href="BatStream.html">
<link title="BatString" rel="Chapter" href="BatString.html">
<link title="BatSubstring" rel="Chapter" href="BatSubstring.html">
<link title="BatSys" rel="Chapter" href="BatSys.html">
<link title="BatText" rel="Chapter" href="BatText.html">
<link title="BatTuple" rel="Chapter" href="BatTuple.html">
<link title="BatUChar" rel="Chapter" href="BatUChar.html">
<link title="BatUTF8" rel="Chapter" href="BatUTF8.html">
<link title="BatUnit" rel="Chapter" href="BatUnit.html">
<link title="BatUnix" rel="Chapter" href="BatUnix.html">
<link title="BatUref" rel="Chapter" href="BatUref.html">
<link title="BatVect" rel="Chapter" href="BatVect.html">
<link title="Batteries" rel="Chapter" href="Batteries.html">
<link title="BatteriesConfig" rel="Chapter" href="BatteriesConfig.html">
<link title="BatteriesPrint" rel="Chapter" href="BatteriesPrint.html">
<link title="BatteriesThread" rel="Chapter" href="BatteriesThread.html">
<link title="Extlib" rel="Chapter" href="Extlib.html"><link title="node functions " rel="Section" href="#6_nodefunctions">
<link title="list conversion " rel="Section" href="#6_listconversion">
<link title="enums " rel="Section" href="#6_enums">
<link title="Boilerplate code" rel="Section" href="#6_Boilerplatecode">
<link title="Printing" rel="Subsection" href="#7_Printing">
<title>Batteries user guide : Batteries.Dllist</title>
</head>
<body>
<div class="navbar"><a class="pre" href="Batteries.Bit_set.html" title="Batteries.Bit_set">Previous</a>
<a class="up" href="Batteries.html" title="Batteries">Up</a>
<a class="post" href="Batteries.DynArray.html" title="Batteries.DynArray">Next</a>
</div>
<h1>Module <a href="type_Batteries.Dllist.html">Batteries.Dllist</a></h1>
<pre><span class="keyword">module</span> Dllist: <code class="type">BatDllist</code></pre><hr width="100%">
<pre><span id="TYPEnode_t"><span class="keyword">type</span> <code class="type">'a</code> node_t</span> </pre>
<pre><span id="TYPEt"><span class="keyword">type</span> <code class="type">'a</code> t</span> = <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code> </pre>
<br>
The type of a non-empty doubly-linked list.<br>
<pre><span class="keyword">include</span> <a href="BatInterfaces.Mappable.html">BatInterfaces.Mappable</a></pre>
<pre><span class="keyword">include</span> <a href="BatEnum.Enumerable.html">BatEnum.Enumerable</a></pre>
<pre><span id="EXCEPTIONEmpty"><span class="keyword">exception</span> Empty</span></pre>
<br>
<h6 id="6_nodefunctions">node functions </h6><br>
<pre><span id="VALcreate"><span class="keyword">val</span> create</span> : <code class="type">'a -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Creates a node. This is an O(1) operation.<br>
</div>
<pre><span id="VALcopy"><span class="keyword">val</span> copy</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Copy the list attached to the given node and return the copy of the given
node. This is an O(N) operation.<br>
</div>
<pre><span id="VALlength"><span class="keyword">val</span> length</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> int</code></pre><div class="info ">
Returns the length of the list. This is an O(N) operation.<br>
</div>
<pre><span id="VALrev"><span class="keyword">val</span> rev</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
List reversal. This is an O(N) operation.
The given node still points to the same element, so
<code class="code">to_list (rev (of_list [1;2;3;4])) = [1;4;3;2]</code><br>
</div>
<pre><span id="VALadd"><span class="keyword">val</span> add</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a -> unit</code></pre><div class="info ">
<code class="code">add n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
the list after node <code class="code">n</code>. This is an O(1) operation.<br>
</div>
<pre><span id="VALappend"><span class="keyword">val</span> append</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">append n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
the list after node <code class="code">n</code>. Returns new node. This is an O(1) operation.<br>
</div>
<pre><span id="VALprepend"><span class="keyword">val</span> prepend</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">prepend n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
the list before node <code class="code">n</code>. Returns new node. This is an O(1) operation.<br>
</div>
<pre><span id="VALpromote"><span class="keyword">val</span> promote</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
<code class="code">promote n</code> Swaps <code class="code">n</code> with <code class="code">next n</code>. This is an O(1) operation.<br>
</div>
<pre><span id="VALdemote"><span class="keyword">val</span> demote</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
<code class="code">demote n</code> Swaps <code class="code">n</code> with <code class="code">prev n</code>. This is an O(1) operation.<br>
</div>
<pre><span id="VALremove"><span class="keyword">val</span> remove</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
Remove node from the list no matter where it is. This is an O(1) operation.<br>
<b>Raises</b> <code>Empty</code> when trying to remove an element from a list of length one.<br>
</div>
<pre><span id="VALdrop"><span class="keyword">val</span> drop</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Remove node from the list no matter where it is. Return next node. This is
an O(1) operation.<br>
<b>Raises</b> <code>Empty</code> when trying to remove an element from a list of length one.<br>
</div>
<pre><span id="VALrev_drop"><span class="keyword">val</span> rev_drop</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Remove node from the list no matter where it is. Return previous node. This
is an O(1) operation.<br>
<b>Raises</b> <code>Empty</code> when trying to remove an element from a list of length one.<br>
</div>
<pre><span id="VALsplice"><span class="keyword">val</span> splice</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
<code class="code">splice n1 n2</code> Connects <code class="code">n1</code> and <code class="code">n2</code> so that
<code class="code">next n1 == n2 <span class="keywordsign">&&</span> prev n2 == n1</code>. This can be used to connect two discrete
lists, or, if used on two nodes within the same list, it can be used to
separate the nodes between <code class="code">n1</code> and <code class="code">n2</code> from the rest of the list. In this
case, those nodes become a discrete list by themselves. This is an O(1)
operation.<br>
</div>
<pre><span id="VALget"><span class="keyword">val</span> get</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a</code></pre><div class="info ">
Given a node, get the data associated with that node. This is an
O(1) operation.<br>
</div>
<pre><span id="VALset"><span class="keyword">val</span> set</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a -> unit</code></pre><div class="info ">
Given a node, set the data associated with that node. This is an O(1)
operation.<br>
</div>
<pre><span id="VALnext"><span class="keyword">val</span> next</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Given a node, get the next element in the list after the node.
<p>
The list is circular, so the last node of the list returns the first
node of the list as it's next node.
<p>
This is an O(1) operation.<br>
</div>
<pre><span id="VALprev"><span class="keyword">val</span> prev</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Given a node, get the previous element in the list before the node.
<p>
The list is circular, so the first node of the list returns the
last element of the list as it's previous node.
<p>
This is an O(1) operation.<br>
</div>
<pre><span id="VALskip"><span class="keyword">val</span> skip</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> int -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">skip n i</code> Return the node that is <code class="code">i</code> nodes after node <code class="code">n</code> in the list.
If <code class="code">i</code> is negative then return the node that is <code class="code">i</code> nodes before node <code class="code">n</code>
in the list. This is an O(N) operation.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a -> unit) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info ">
<code class="code">iter f n</code> Apply <code class="code">f</code> to every element in the list, starting at <code class="code">n</code>. This
is an O(N) operation.<br>
</div>
<pre><span id="VALfold_left"><span class="keyword">val</span> fold_left</span> : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a</code></pre><div class="info ">
Accumulate a value over the entire list.
This works like List.fold_left. This is an O(N) operation.<br>
</div>
<pre><span id="VALfold_right"><span class="keyword">val</span> fold_right</span> : <code class="type">('a -> 'b -> 'b) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'b -> 'b</code></pre><div class="info ">
Accumulate a value over the entire list.
This works like List.fold_right, but since the list is bidirectional,
it doesn't suffer the performance problems of List.fold_right.
This is an O(N) operation.<br>
</div>
<pre><span id="VALfind"><span class="keyword">val</span> find</span> : <code class="type">('a -> bool) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">find p l</code> returns the first element, <code class="code">l</code> or after, for which <code class="code">p</code>
returns true.<br>
<b>Raises</b> <code>Not_found</code> if no such element exists<br>
</div>
<pre><span id="VALfor_all"><span class="keyword">val</span> for_all</span> : <code class="type">('a -> bool) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> bool</code></pre><div class="info ">
Test whether a given predicate returns true for all members of the
given list. O(N)<br>
</div>
<pre><span id="VALexists"><span class="keyword">val</span> exists</span> : <code class="type">('a -> bool) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> bool</code></pre><div class="info ">
Test whether there exists an element of the given list for which
the predicate returns true. O(N)<br>
</div>
<pre><span id="VALmap"><span class="keyword">val</span> map</span> : <code class="type">('a -> 'b) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'b <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Allocate a new list, with entirely new nodes, whose values are
the transforms of the values of the original list. Note that this
does not modify the given list. This is an O(N) operation.<br>
</div>
<pre><span id="VALfilter"><span class="keyword">val</span> filter</span> : <code class="type">('a -> bool) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">filter p l</code> returns a new list, with entirely new nodes, whose
values are all the elements of the list <code class="code">l</code> that satisfy the
predicate <code class="code">p</code>. The order of the elements in the input list is
preserved.<br>
<b>Raises</b> <code>Empty</code> if the resulting list is empty.<br>
</div>
<pre><span id="VALfilter_map"><span class="keyword">val</span> filter_map</span> : <code class="type">('a -> 'b option) -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'b <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
<code class="code">filter_map f l</code> calls <code class="code">(f a0) (f a1) ... (f an)</code> where <code class="code">a0,a1...an</code>
are the elements of <code class="code">l</code>. It returns a new list of elements <code class="code">bi</code>
such as <code class="code">f ai = <span class="constructor">Some</span> bi</code> (when <code class="code">f</code> returns <code class="code"><span class="constructor">None</span></code>, the
corresponding element of <code class="code">l</code> is discarded).<br>
<b>Raises</b> <code>Empty</code> if the resulting list is empty.<br>
</div>
<br>
<h6 id="6_listconversion">list conversion </h6><br>
<pre><span id="VALto_list"><span class="keyword">val</span> to_list</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a list</code></pre><div class="info ">
Converts a dllist to a normal list. This is an O(N) operation.<br>
</div>
<pre><span id="VALof_list"><span class="keyword">val</span> of_list</span> : <code class="type">'a list -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Converts from a normal list to a Dllist and returns the first node.<br>
<b>Raises</b> <code>Empty</code> if given list is empty. This is an O(N) operation.<br>
</div>
<br>
<h6 id="6_enums">enums </h6><br>
<pre><span id="VALenum"><span class="keyword">val</span> enum</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatEnum.html#TYPEt">BatEnum.t</a></code></pre><div class="info ">
Create an enum of the list.
Note that modifying the list while the enum exists will have undefined
effects. This is an O(1) operation.<br>
</div>
<pre><span id="VALrev_enum"><span class="keyword">val</span> rev_enum</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatEnum.html#TYPEt">BatEnum.t</a></code></pre><div class="info ">
Create a reverse enum of the list.
The enumeration starts with the current element of the list:
<code class="code">rev_enum (of_list [1;2;3;4])</code> will generate the enumeration <code class="code">[1;4;3;2]</code>.
<p>
If you want it to start with the last one, see <code class="code">backwards</code>.
<p>
Note that modifying the list while the enum exists will have undefined
effects. This is an O(1) operation.<br>
</div>
<pre><span id="VALbackwards"><span class="keyword">val</span> backwards</span> : <code class="type">'a <a href="BatDllist.html#TYPEnode_t">node_t</a> -> 'a <a href="BatEnum.html#TYPEt">BatEnum.t</a></code></pre><div class="info ">
<code class="code">backwards t</code> is similar to <code class="code">rev_enum t</code> except that the enumeration
starts at the node before the current one:
<p>
<code class="code">backwards (of_list [1;2;3;4])</code> will generate the enumeration <code class="code">[4;3;2;1]</code>.<br>
</div>
<pre><span id="VALof_enum"><span class="keyword">val</span> of_enum</span> : <code class="type">'a <a href="BatEnum.html#TYPEt">BatEnum.t</a> -> 'a <a href="BatDllist.html#TYPEnode_t">node_t</a></code></pre><div class="info ">
Create a dllist from an enum.
This consumes the enum, and allocates a whole new dllist.<br>
<b>Raises</b> <code>Empty</code> if given enum is empty. This is an O(N) operation.<br>
</div>
<br>
<h6 id="6_Boilerplatecode">Boilerplate code</h6><br>
<br>
<div class="h7" id="7_Printing">Printing</div><br>
<pre><span id="VALprint"><span class="keyword">val</span> print</span> : <code class="type">?first:string -><br> ?last:string -><br> ?sep:string -><br> ('a <a href="BatInnerIO.html#TYPEoutput">BatInnerIO.output</a> -> 'b -> unit) -><br> 'a <a href="BatInnerIO.html#TYPEoutput">BatInnerIO.output</a> -> 'b <a href="BatDllist.html#TYPEt">t</a> -> unit</code></pre></body></html>
