Permalink
Fetching contributors…
Cannot retrieve contributors at this time
4091 lines (4073 sloc) 590 KB
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>STX B+ Tree Template Classes: stx/btree.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
</head>
<body>
<div id="top"><!-- do not remove this div! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">STX B+ Tree Template Classes
&#160;<span id="projectnumber">0.9</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- Generated by Doxygen 1.7.6.1 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main&#160;Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</span>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File&#160;List</span></a></li>
<li><a href="globals.html"><span>File&#160;Members</span></a></li>
</ul>
</div>
</div>
<div class="header">
<div class="headertitle">
<div class="title">stx/btree.h</div> </div>
</div><!--header-->
<div class="contents">
<a href="a00026.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/**</span>
<a name="l00002"></a>00002 <span class="comment"> * \file include/stx/btree.h</span>
<a name="l00003"></a>00003 <span class="comment"> * Contains the main B+ tree implementation template class btree.</span>
<a name="l00004"></a>00004 <span class="comment"> */</span>
<a name="l00005"></a>00005
<a name="l00006"></a>00006 <span class="comment">/*</span>
<a name="l00007"></a>00007 <span class="comment"> * STX B+ Tree Template Classes v0.9</span>
<a name="l00008"></a>00008 <span class="comment"> * Copyright (C) 2008-2013 Timo Bingmann &lt;tb@panthema.net&gt;</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * Boost Software License - Version 1.0 - August 17th, 2003</span>
<a name="l00011"></a>00011 <span class="comment"> *</span>
<a name="l00012"></a>00012 <span class="comment"> * Permission is hereby granted, free of charge, to any person or organization</span>
<a name="l00013"></a>00013 <span class="comment"> * obtaining a copy of the software and accompanying documentation covered by</span>
<a name="l00014"></a>00014 <span class="comment"> * this license (the &quot;Software&quot;) to use, reproduce, display, distribute,</span>
<a name="l00015"></a>00015 <span class="comment"> * execute, and transmit the Software, and to prepare derivative works of the</span>
<a name="l00016"></a>00016 <span class="comment"> * Software, and to permit third-parties to whom the Software is furnished to</span>
<a name="l00017"></a>00017 <span class="comment"> * do so, all subject to the following:</span>
<a name="l00018"></a>00018 <span class="comment"> *</span>
<a name="l00019"></a>00019 <span class="comment"> * The copyright notices in the Software and this entire statement, including</span>
<a name="l00020"></a>00020 <span class="comment"> * the above license grant, this restriction and the following disclaimer, must</span>
<a name="l00021"></a>00021 <span class="comment"> * be included in all copies of the Software, in whole or in part, and all</span>
<a name="l00022"></a>00022 <span class="comment"> * derivative works of the Software, unless such copies or derivative works are</span>
<a name="l00023"></a>00023 <span class="comment"> * solely in the form of machine-executable object code generated by a source</span>
<a name="l00024"></a>00024 <span class="comment"> * language processor.</span>
<a name="l00025"></a>00025 <span class="comment"> *</span>
<a name="l00026"></a>00026 <span class="comment"> * THE SOFTWARE IS PROVIDED &quot;AS IS&quot;, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR</span>
<a name="l00027"></a>00027 <span class="comment"> * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,</span>
<a name="l00028"></a>00028 <span class="comment"> * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT</span>
<a name="l00029"></a>00029 <span class="comment"> * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE</span>
<a name="l00030"></a>00030 <span class="comment"> * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,</span>
<a name="l00031"></a>00031 <span class="comment"> * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER</span>
<a name="l00032"></a>00032 <span class="comment"> * DEALINGS IN THE SOFTWARE.</span>
<a name="l00033"></a>00033 <span class="comment"> */</span>
<a name="l00034"></a>00034
<a name="l00035"></a>00035 <span class="preprocessor">#ifndef _STX_BTREE_H_</span>
<a name="l00036"></a>00036 <span class="preprocessor"></span><span class="preprocessor">#define _STX_BTREE_H_</span>
<a name="l00037"></a>00037 <span class="preprocessor"></span>
<a name="l00038"></a>00038 <span class="comment">// *** Required Headers from the STL</span>
<a name="l00039"></a>00039
<a name="l00040"></a>00040 <span class="preprocessor">#include &lt;algorithm&gt;</span>
<a name="l00041"></a>00041 <span class="preprocessor">#include &lt;functional&gt;</span>
<a name="l00042"></a>00042 <span class="preprocessor">#include &lt;istream&gt;</span>
<a name="l00043"></a>00043 <span class="preprocessor">#include &lt;ostream&gt;</span>
<a name="l00044"></a>00044 <span class="preprocessor">#include &lt;memory&gt;</span>
<a name="l00045"></a>00045 <span class="preprocessor">#include &lt;cstddef&gt;</span>
<a name="l00046"></a>00046 <span class="preprocessor">#include &lt;assert.h&gt;</span>
<a name="l00047"></a>00047
<a name="l00048"></a>00048 <span class="comment">// *** Debugging Macros</span>
<a name="l00049"></a>00049
<a name="l00050"></a>00050 <span class="preprocessor">#ifdef BTREE_DEBUG</span>
<a name="l00051"></a>00051 <span class="preprocessor"></span>
<a name="l00052"></a>00052 <span class="preprocessor">#include &lt;iostream&gt;</span>
<a name="l00053"></a>00053 <span class="comment"></span>
<a name="l00054"></a>00054 <span class="comment">/// Print out debug information to std::cout if BTREE_DEBUG is defined.</span>
<a name="l00055"></a><a class="code" href="a00026.html#acd87b40df0c1d4ead6fac13b49cb5345">00055</a> <span class="comment"></span><span class="preprocessor">#define BTREE_PRINT(x) do { if (debug) (std::cout &lt;&lt; x &lt;&lt; std::endl); } while(0)</span>
<a name="l00056"></a>00056 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00057"></a>00057 <span class="comment">/// Assertion only if BTREE_DEBUG is defined. This is not used in verify().</span>
<a name="l00058"></a><a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb">00058</a> <span class="comment"></span><span class="preprocessor">#define BTREE_ASSERT(x) do { assert(x); } while(0)</span>
<a name="l00059"></a>00059 <span class="preprocessor"></span>
<a name="l00060"></a>00060 <span class="preprocessor">#else</span>
<a name="l00061"></a>00061 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00062"></a>00062 <span class="comment">/// Print out debug information to std::cout if BTREE_DEBUG is defined.</span>
<a name="l00063"></a>00063 <span class="comment"></span><span class="preprocessor">#define BTREE_PRINT(x) do { } while(0)</span>
<a name="l00064"></a>00064 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00065"></a>00065 <span class="comment">/// Assertion only if BTREE_DEBUG is defined. This is not used in verify().</span>
<a name="l00066"></a>00066 <span class="comment"></span><span class="preprocessor">#define BTREE_ASSERT(x) do { } while(0)</span>
<a name="l00067"></a>00067 <span class="preprocessor"></span>
<a name="l00068"></a>00068 <span class="preprocessor">#endif</span>
<a name="l00069"></a>00069 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00070"></a>00070 <span class="comment">/// The maximum of a and b. Used in some compile-time formulas.</span>
<a name="l00071"></a><a class="code" href="a00026.html#a5d7b0c98bc4c3029d6d76199caa35b19">00071</a> <span class="comment"></span><span class="preprocessor">#define BTREE_MAX(a,b) ((a) &lt; (b) ? (b) : (a))</span>
<a name="l00072"></a>00072 <span class="preprocessor"></span>
<a name="l00073"></a>00073 <span class="preprocessor">#ifndef BTREE_FRIENDS</span>
<a name="l00074"></a>00074 <span class="preprocessor"></span><span class="comment">/// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00075"></a>00075 <span class="comment"></span><span class="comment">/// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00076"></a>00076 <span class="comment"></span><span class="comment">/// tree.</span>
<a name="l00077"></a><a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320">00077</a> <span class="comment"></span><span class="preprocessor">#define BTREE_FRIENDS friend class btree_friend;</span>
<a name="l00078"></a>00078 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00079"></a>00079 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00080"></a>00080 <span class="comment">/// STX - Some Template Extensions namespace</span>
<a name="l00081"></a><a class="code" href="a00036.html">00081</a> <span class="comment"></span><span class="keyword">namespace </span>stx {
<a name="l00082"></a>00082 <span class="comment"></span>
<a name="l00083"></a>00083 <span class="comment">/** Generates default traits for a B+ tree used as a set. It estimates leaf and</span>
<a name="l00084"></a>00084 <span class="comment"> * inner node sizes by assuming a cache line size of 256 bytes. */</span>
<a name="l00085"></a>00085 <span class="keyword">template</span> &lt;<span class="keyword">typename</span> _Key&gt;
<a name="l00086"></a><a class="code" href="a00003.html">00086</a> <span class="keyword">struct </span><a class="code" href="a00003.html" title="Generates default traits for a B+ tree used as a set.">btree_default_set_traits</a>
<a name="l00087"></a>00087 {<span class="comment"></span>
<a name="l00088"></a>00088 <span class="comment"> /// If true, the tree will self verify it&#39;s invariants after each insert()</span>
<a name="l00089"></a>00089 <span class="comment"> /// or erase(). The header must have been compiled with BTREE_DEBUG defined.</span>
<a name="l00090"></a><a class="code" href="a00003.html#abbb0859c6f7a2b887863011026e28ab1">00090</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00003.html#abbb0859c6f7a2b887863011026e28ab1" title="If true, the tree will self verify it&#39;s invariants after each insert() or erase().">selfverify</a> = <span class="keyword">false</span>;
<a name="l00091"></a>00091 <span class="comment"></span>
<a name="l00092"></a>00092 <span class="comment"> /// If true, the tree will print out debug information and a tree dump</span>
<a name="l00093"></a>00093 <span class="comment"> /// during insert() or erase() operation. The header must have been</span>
<a name="l00094"></a>00094 <span class="comment"> /// compiled with BTREE_DEBUG defined and key_type must be std::ostream</span>
<a name="l00095"></a>00095 <span class="comment"> /// printable.</span>
<a name="l00096"></a><a class="code" href="a00003.html#ab06ff26a50cb57614ddaf1096b2871bb">00096</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00003.html#ab06ff26a50cb57614ddaf1096b2871bb" title="If true, the tree will print out debug information and a tree dump during insert() or erase() operati...">debug</a> = <span class="keyword">false</span>;
<a name="l00097"></a>00097 <span class="comment"></span>
<a name="l00098"></a>00098 <span class="comment"> /// Number of slots in each leaf of the tree. Estimated so that each node</span>
<a name="l00099"></a>00099 <span class="comment"> /// has a size of about 256 bytes.</span>
<a name="l00100"></a><a class="code" href="a00003.html#ab0bbc6a8fdfa17275dab38f5a9c80efc">00100</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">int</span> <a class="code" href="a00003.html#ab0bbc6a8fdfa17275dab38f5a9c80efc" title="Number of slots in each leaf of the tree.">leafslots</a> = <a class="code" href="a00026.html#a5d7b0c98bc4c3029d6d76199caa35b19" title="The maximum of a and b. Used in some compile-time formulas.">BTREE_MAX</a>( 8, 256 / (<span class="keyword">sizeof</span>(_Key)) );
<a name="l00101"></a>00101 <span class="comment"></span>
<a name="l00102"></a>00102 <span class="comment"> /// Number of slots in each inner node of the tree. Estimated so that each node</span>
<a name="l00103"></a>00103 <span class="comment"> /// has a size of about 256 bytes.</span>
<a name="l00104"></a><a class="code" href="a00003.html#a1a1e1c183cffd510e3fc7e71076bad2b">00104</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">int</span> <a class="code" href="a00003.html#a1a1e1c183cffd510e3fc7e71076bad2b" title="Number of slots in each inner node of the tree.">innerslots</a> = <a class="code" href="a00026.html#a5d7b0c98bc4c3029d6d76199caa35b19" title="The maximum of a and b. Used in some compile-time formulas.">BTREE_MAX</a>( 8, 256 / (<span class="keyword">sizeof</span>(_Key) + <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*)) );
<a name="l00105"></a>00105 <span class="comment"></span>
<a name="l00106"></a>00106 <span class="comment"> /// As of stx-btree-0.9, the code does linear search in find_lower() and</span>
<a name="l00107"></a>00107 <span class="comment"> /// find_upper() instead of binary_search, unless the node size is larger</span>
<a name="l00108"></a>00108 <span class="comment"> /// than this threshold. See notes at</span>
<a name="l00109"></a>00109 <span class="comment"> /// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search</span>
<a name="l00110"></a><a class="code" href="a00003.html#a5f30b3761385f6d26acbd2ad1f91c95a">00110</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">size_t</span> <a class="code" href="a00003.html#a5f30b3761385f6d26acbd2ad1f91c95a" title="As of stx-btree-0.9, the code does linear search in find_lower() and find_upper() instead of binary_s...">binsearch_threshold</a> = 256;
<a name="l00111"></a>00111 };
<a name="l00112"></a>00112 <span class="comment"></span>
<a name="l00113"></a>00113 <span class="comment">/** Generates default traits for a B+ tree used as a map. It estimates leaf and</span>
<a name="l00114"></a>00114 <span class="comment"> * inner node sizes by assuming a cache line size of 256 bytes. */</span>
<a name="l00115"></a>00115 <span class="keyword">template</span> &lt;<span class="keyword">typename</span> _Key, <span class="keyword">typename</span> _Data&gt;
<a name="l00116"></a><a class="code" href="a00002.html">00116</a> <span class="keyword">struct </span><a class="code" href="a00002.html" title="Generates default traits for a B+ tree used as a map.">btree_default_map_traits</a>
<a name="l00117"></a>00117 {<span class="comment"></span>
<a name="l00118"></a>00118 <span class="comment"> /// If true, the tree will self verify it&#39;s invariants after each insert()</span>
<a name="l00119"></a>00119 <span class="comment"> /// or erase(). The header must have been compiled with BTREE_DEBUG defined.</span>
<a name="l00120"></a><a class="code" href="a00002.html#a496dd5b655f8504d804b1751c3b346d4">00120</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00002.html#a496dd5b655f8504d804b1751c3b346d4" title="If true, the tree will self verify it&#39;s invariants after each insert() or erase().">selfverify</a> = <span class="keyword">false</span>;
<a name="l00121"></a>00121 <span class="comment"></span>
<a name="l00122"></a>00122 <span class="comment"> /// If true, the tree will print out debug information and a tree dump</span>
<a name="l00123"></a>00123 <span class="comment"> /// during insert() or erase() operation. The header must have been</span>
<a name="l00124"></a>00124 <span class="comment"> /// compiled with BTREE_DEBUG defined and key_type must be std::ostream</span>
<a name="l00125"></a>00125 <span class="comment"> /// printable.</span>
<a name="l00126"></a><a class="code" href="a00002.html#a89d1e06fd542409800e8b370f9c529dc">00126</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00002.html#a89d1e06fd542409800e8b370f9c529dc" title="If true, the tree will print out debug information and a tree dump during insert() or erase() operati...">debug</a> = <span class="keyword">false</span>;
<a name="l00127"></a>00127 <span class="comment"></span>
<a name="l00128"></a>00128 <span class="comment"> /// Number of slots in each leaf of the tree. Estimated so that each node</span>
<a name="l00129"></a>00129 <span class="comment"> /// has a size of about 256 bytes.</span>
<a name="l00130"></a><a class="code" href="a00002.html#a19d18c5e35448829cc2a62f458d65a4f">00130</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">int</span> <a class="code" href="a00002.html#a19d18c5e35448829cc2a62f458d65a4f" title="Number of slots in each leaf of the tree.">leafslots</a> = <a class="code" href="a00026.html#a5d7b0c98bc4c3029d6d76199caa35b19" title="The maximum of a and b. Used in some compile-time formulas.">BTREE_MAX</a>( 8, 256 / (<span class="keyword">sizeof</span>(_Key) + <span class="keyword">sizeof</span>(_Data)) );
<a name="l00131"></a>00131 <span class="comment"></span>
<a name="l00132"></a>00132 <span class="comment"> /// Number of slots in each inner node of the tree. Estimated so that each node</span>
<a name="l00133"></a>00133 <span class="comment"> /// has a size of about 256 bytes.</span>
<a name="l00134"></a><a class="code" href="a00002.html#a8fb65e8200dda28ef52fa765e14301ff">00134</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">int</span> <a class="code" href="a00002.html#a8fb65e8200dda28ef52fa765e14301ff" title="Number of slots in each inner node of the tree.">innerslots</a> = <a class="code" href="a00026.html#a5d7b0c98bc4c3029d6d76199caa35b19" title="The maximum of a and b. Used in some compile-time formulas.">BTREE_MAX</a>( 8, 256 / (<span class="keyword">sizeof</span>(_Key) + <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*)) );
<a name="l00135"></a>00135 <span class="comment"></span>
<a name="l00136"></a>00136 <span class="comment"> /// As of stx-btree-0.9, the code does linear search in find_lower() and</span>
<a name="l00137"></a>00137 <span class="comment"> /// find_upper() instead of binary_search, unless the node size is larger</span>
<a name="l00138"></a>00138 <span class="comment"> /// than this threshold. See notes at</span>
<a name="l00139"></a>00139 <span class="comment"> /// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search</span>
<a name="l00140"></a><a class="code" href="a00002.html#ae636c1898e7978b0ca36cebd8fe86319">00140</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">size_t</span> <a class="code" href="a00002.html#ae636c1898e7978b0ca36cebd8fe86319" title="As of stx-btree-0.9, the code does linear search in find_lower() and find_upper() instead of binary_s...">binsearch_threshold</a> = 256;
<a name="l00141"></a>00141 };
<a name="l00142"></a>00142 <span class="comment"></span>
<a name="l00143"></a>00143 <span class="comment">/** @brief Basic class implementing a base B+ tree data structure in memory.</span>
<a name="l00144"></a>00144 <span class="comment"> *</span>
<a name="l00145"></a>00145 <span class="comment"> * The base implementation of a memory B+ tree. It is based on the</span>
<a name="l00146"></a>00146 <span class="comment"> * implementation in Cormen&#39;s Introduction into Algorithms, Jan Jannink&#39;s paper</span>
<a name="l00147"></a>00147 <span class="comment"> * and other algorithm resources. Almost all STL-required function calls are</span>
<a name="l00148"></a>00148 <span class="comment"> * implemented. The asymptotic time requirements of the STL are not always</span>
<a name="l00149"></a>00149 <span class="comment"> * fulfilled in theory, however in practice this B+ tree performs better than a</span>
<a name="l00150"></a>00150 <span class="comment"> * red-black tree by using more memory. The insertion function splits the nodes</span>
<a name="l00151"></a>00151 <span class="comment"> * on the recursion unroll. Erase is largely based on Jannink&#39;s ideas.</span>
<a name="l00152"></a>00152 <span class="comment"> *</span>
<a name="l00153"></a>00153 <span class="comment"> * This class is specialized into btree_set, btree_multiset, btree_map and</span>
<a name="l00154"></a>00154 <span class="comment"> * btree_multimap using default template parameters and facade functions.</span>
<a name="l00155"></a>00155 <span class="comment"> */</span>
<a name="l00156"></a>00156 <span class="keyword">template</span> &lt;<span class="keyword">typename</span> _Key, <span class="keyword">typename</span> _Data,
<a name="l00157"></a>00157 <span class="keyword">typename</span> _Value = std::pair&lt;_Key, _Data&gt;,
<a name="l00158"></a>00158 <span class="keyword">typename</span> _Compare = std::less&lt;_Key&gt;,
<a name="l00159"></a>00159 <span class="keyword">typename</span> _Traits = <a class="code" href="a00002.html" title="Generates default traits for a B+ tree used as a map.">btree_default_map_traits&lt;_Key, _Data&gt;</a>,
<a name="l00160"></a>00160 <span class="keywordtype">bool</span> _Duplicates = <span class="keyword">false</span>,
<a name="l00161"></a>00161 <span class="keyword">typename</span> _Alloc = std::allocator&lt;_Value&gt;,
<a name="l00162"></a>00162 <span class="keywordtype">bool</span> _UsedAsSet = <span class="keyword">false</span> &gt;
<a name="l00163"></a><a class="code" href="a00001.html">00163</a> <span class="keyword">class </span><a class="code" href="a00001.html" title="Basic class implementing a base B+ tree data structure in memory.">btree</a>
<a name="l00164"></a>00164 {
<a name="l00165"></a>00165 <span class="keyword">public</span>:
<a name="l00166"></a>00166 <span class="comment">// *** Template Parameter Types</span>
<a name="l00167"></a>00167 <span class="comment"></span>
<a name="l00168"></a>00168 <span class="comment"> /// First template parameter: The key type of the B+ tree. This is stored</span>
<a name="l00169"></a>00169 <span class="comment"> /// in inner nodes and leaves</span>
<a name="l00170"></a><a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a">00170</a> <span class="comment"></span> <span class="keyword">typedef</span> _Key <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">key_type</a>;
<a name="l00171"></a>00171 <span class="comment"></span>
<a name="l00172"></a>00172 <span class="comment"> /// Second template parameter: The data type associated with each</span>
<a name="l00173"></a>00173 <span class="comment"> /// key. Stored in the B+ tree&#39;s leaves</span>
<a name="l00174"></a><a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616">00174</a> <span class="comment"></span> <span class="keyword">typedef</span> _Data <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">data_type</a>;
<a name="l00175"></a>00175 <span class="comment"></span>
<a name="l00176"></a>00176 <span class="comment"> /// Third template parameter: Composition pair of key and data types, this</span>
<a name="l00177"></a>00177 <span class="comment"> /// is required by the STL standard. The B+ tree does not store key and</span>
<a name="l00178"></a>00178 <span class="comment"> /// data together. If value_type == key_type then the B+ tree implements a</span>
<a name="l00179"></a>00179 <span class="comment"> /// set.</span>
<a name="l00180"></a><a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6">00180</a> <span class="comment"></span> <span class="keyword">typedef</span> _Value <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a>;
<a name="l00181"></a>00181 <span class="comment"></span>
<a name="l00182"></a>00182 <span class="comment"> /// Fourth template parameter: Key comparison function object</span>
<a name="l00183"></a><a class="code" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae">00183</a> <span class="comment"></span> <span class="keyword">typedef</span> _Compare <a class="code" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae" title="Fourth template parameter: Key comparison function object.">key_compare</a>;
<a name="l00184"></a>00184 <span class="comment"></span>
<a name="l00185"></a>00185 <span class="comment"> /// Fifth template parameter: Traits object used to define more parameters</span>
<a name="l00186"></a>00186 <span class="comment"> /// of the B+ tree</span>
<a name="l00187"></a><a class="code" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319">00187</a> <span class="comment"></span> <span class="keyword">typedef</span> _Traits <a class="code" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319" title="Fifth template parameter: Traits object used to define more parameters of the B+ tree.">traits</a>;
<a name="l00188"></a>00188 <span class="comment"></span>
<a name="l00189"></a>00189 <span class="comment"> /// Sixth template parameter: Allow duplicate keys in the B+ tree. Used to</span>
<a name="l00190"></a>00190 <span class="comment"> /// implement multiset and multimap.</span>
<a name="l00191"></a><a class="code" href="a00001.html#acd41575a35d1c5d55e955aafc9762454">00191</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00001.html#acd41575a35d1c5d55e955aafc9762454" title="Sixth template parameter: Allow duplicate keys in the B+ tree.">allow_duplicates</a> = _Duplicates;
<a name="l00192"></a>00192 <span class="comment"></span>
<a name="l00193"></a>00193 <span class="comment"> /// Seventh template parameter: STL allocator for tree nodes</span>
<a name="l00194"></a><a class="code" href="a00001.html#aef567d7893cd02d22933a2e68702532b">00194</a> <span class="comment"></span> <span class="keyword">typedef</span> _Alloc <a class="code" href="a00001.html#aef567d7893cd02d22933a2e68702532b" title="Seventh template parameter: STL allocator for tree nodes.">allocator_type</a>;
<a name="l00195"></a>00195 <span class="comment"></span>
<a name="l00196"></a>00196 <span class="comment"> /// Eighth template parameter: boolean indicator whether the btree is used</span>
<a name="l00197"></a>00197 <span class="comment"> /// as a set. In this case all operations on the data arrays are</span>
<a name="l00198"></a>00198 <span class="comment"> /// omitted. This flag is kind of hacky, but required because</span>
<a name="l00199"></a>00199 <span class="comment"> /// sizeof(empty_struct) = 1 due to the C standard. Without the flag, lots</span>
<a name="l00200"></a>00200 <span class="comment"> /// of superfluous copying would occur.</span>
<a name="l00201"></a><a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023">00201</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> = _UsedAsSet;
<a name="l00202"></a>00202
<a name="l00203"></a>00203 <span class="comment">// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00204"></a>00204 <span class="comment">// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00205"></a>00205 <span class="comment">// tree.</span>
<a name="l00206"></a>00206 <a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.">BTREE_FRIENDS</a>
<a name="l00207"></a>00207
<a name="l00208"></a>00208 <span class="keyword">public</span>:
<a name="l00209"></a>00209 <span class="comment">// *** Constructed Types</span>
<a name="l00210"></a>00210 <span class="comment"></span>
<a name="l00211"></a>00211 <span class="comment"> /// Typedef of our own type</span>
<a name="l00212"></a>00212 <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00001.html" title="Basic class implementing a base B+ tree data structure in memory.">btree</a>&lt;<a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">key_type</a>, <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">data_type</a>, <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a>, <a class="code" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae" title="Fourth template parameter: Key comparison function object.">key_compare</a>,
<a name="l00213"></a><a class="code" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14">00213</a> <a class="code" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319" title="Fifth template parameter: Traits object used to define more parameters of the B+ tree.">traits</a>, <a class="code" href="a00001.html#acd41575a35d1c5d55e955aafc9762454" title="Sixth template parameter: Allow duplicate keys in the B+ tree.">allow_duplicates</a>, <a class="code" href="a00001.html#aef567d7893cd02d22933a2e68702532b" title="Seventh template parameter: STL allocator for tree nodes.">allocator_type</a>, <a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a>&gt; <a class="code" href="a00001.html#ad7844e40add49f90fc9e1f2c888afb14" title="Typedef of our own type.">btree_self</a>;
<a name="l00214"></a>00214 <span class="comment"></span>
<a name="l00215"></a>00215 <span class="comment"> /// Size type used to count keys</span>
<a name="l00216"></a><a class="code" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da">00216</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keywordtype">size_t</span> <a class="code" href="a00001.html#aa692f5303dd2c4fee4958cbbfc3db5da" title="Size type used to count keys.">size_type</a>;
<a name="l00217"></a>00217 <span class="comment"></span>
<a name="l00218"></a>00218 <span class="comment"> /// The pair of key_type and data_type, this may be different from value_type.</span>
<a name="l00219"></a><a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31">00219</a> <span class="comment"></span> <span class="keyword">typedef</span> std::pair&lt;key_type, data_type&gt; <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>;
<a name="l00220"></a>00220
<a name="l00221"></a>00221 <span class="keyword">public</span>:
<a name="l00222"></a>00222 <span class="comment">// *** Static Constant Options and Values of the B+ Tree</span>
<a name="l00223"></a>00223 <span class="comment"></span>
<a name="l00224"></a>00224 <span class="comment"> /// Base B+ tree parameter: The number of key/data slots in each leaf</span>
<a name="l00225"></a><a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8">00225</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a> = traits::leafslots;
<a name="l00226"></a>00226 <span class="comment"></span>
<a name="l00227"></a>00227 <span class="comment"> /// Base B+ tree parameter: The number of key slots in each inner node,</span>
<a name="l00228"></a>00228 <span class="comment"> /// this can differ from slots in each leaf.</span>
<a name="l00229"></a><a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0">00229</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a> = traits::innerslots;
<a name="l00230"></a>00230 <span class="comment"></span>
<a name="l00231"></a>00231 <span class="comment"> /// Computed B+ tree parameter: The minimum number of key/data slots used</span>
<a name="l00232"></a>00232 <span class="comment"> /// in a leaf. If fewer slots are used, the leaf will be merged or slots</span>
<a name="l00233"></a>00233 <span class="comment"> /// shifted from it&#39;s siblings.</span>
<a name="l00234"></a><a class="code" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0">00234</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">minleafslots</a> = (<a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a> / 2);
<a name="l00235"></a>00235 <span class="comment"></span>
<a name="l00236"></a>00236 <span class="comment"> /// Computed B+ tree parameter: The minimum number of key slots used</span>
<a name="l00237"></a>00237 <span class="comment"> /// in an inner node. If fewer slots are used, the inner node will be</span>
<a name="l00238"></a>00238 <span class="comment"> /// merged or slots shifted from it&#39;s siblings.</span>
<a name="l00239"></a><a class="code" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654">00239</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node.">mininnerslots</a> = (<a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a> / 2);
<a name="l00240"></a>00240 <span class="comment"></span>
<a name="l00241"></a>00241 <span class="comment"> /// Debug parameter: Enables expensive and thorough checking of the B+ tree</span>
<a name="l00242"></a>00242 <span class="comment"> /// invariants after each insert/erase operation.</span>
<a name="l00243"></a><a class="code" href="a00001.html#a598601fa16cfb97b8b60a4eae6bde5ae">00243</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00001.html#a598601fa16cfb97b8b60a4eae6bde5ae" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...">selfverify</a> = <a class="code" href="a00001.html#a598601fa16cfb97b8b60a4eae6bde5ae" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...">traits::selfverify</a>;
<a name="l00244"></a>00244 <span class="comment"></span>
<a name="l00245"></a>00245 <span class="comment"> /// Debug parameter: Prints out lots of debug information about how the</span>
<a name="l00246"></a>00246 <span class="comment"> /// algorithms change the tree. Requires the header file to be compiled</span>
<a name="l00247"></a>00247 <span class="comment"> /// with BTREE_DEBUG and the key type must be std::ostream printable.</span>
<a name="l00248"></a><a class="code" href="a00001.html#a224f31a88d50490e14f0f291d70ef2fc">00248</a> <span class="comment"></span> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="a00001.html#a224f31a88d50490e14f0f291d70ef2fc" title="Debug parameter: Prints out lots of debug information about how the algorithms change the tree...">debug</a> = <a class="code" href="a00001.html#a224f31a88d50490e14f0f291d70ef2fc" title="Debug parameter: Prints out lots of debug information about how the algorithms change the tree...">traits::debug</a>;
<a name="l00249"></a>00249
<a name="l00250"></a>00250 <span class="keyword">private</span>:
<a name="l00251"></a>00251 <span class="comment">// *** Node Classes for In-Memory Nodes</span>
<a name="l00252"></a>00252 <span class="comment"></span>
<a name="l00253"></a>00253 <span class="comment"> /// The header structure of each node in-memory. This structure is extended</span>
<a name="l00254"></a>00254 <span class="comment"> /// by inner_node or leaf_node.</span>
<a name="l00255"></a><a class="code" href="a00018.html">00255</a> <span class="comment"></span> <span class="keyword">struct </span><a class="code" href="a00018.html" title="The header structure of each node in-memory.">node</a>
<a name="l00256"></a>00256 {<span class="comment"></span>
<a name="l00257"></a>00257 <span class="comment"> /// Level in the b-tree, if level == 0 -&gt; leaf node</span>
<a name="l00258"></a><a class="code" href="a00018.html#a9204f647e868560552dddc001aac8a55">00258</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00018.html#a9204f647e868560552dddc001aac8a55" title="Level in the b-tree, if level == 0 -&gt; leaf node.">level</a>;
<a name="l00259"></a>00259 <span class="comment"></span>
<a name="l00260"></a>00260 <span class="comment"> /// Number of key slotuse use, so number of valid children or data</span>
<a name="l00261"></a>00261 <span class="comment"> /// pointers</span>
<a name="l00262"></a><a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903">00262</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00263"></a>00263 <span class="comment"></span>
<a name="l00264"></a>00264 <span class="comment"> /// Delayed initialisation of constructed node</span>
<a name="l00265"></a><a class="code" href="a00018.html#a5fdccd9e010dc73398fb0694ed803d38">00265</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00018.html#a5fdccd9e010dc73398fb0694ed803d38" title="Delayed initialisation of constructed node.">initialize</a>(<span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> l)
<a name="l00266"></a>00266 {
<a name="l00267"></a>00267 <a class="code" href="a00018.html#a9204f647e868560552dddc001aac8a55" title="Level in the b-tree, if level == 0 -&gt; leaf node.">level</a> = l;
<a name="l00268"></a>00268 <a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a> = 0;
<a name="l00269"></a>00269 }
<a name="l00270"></a>00270 <span class="comment"></span>
<a name="l00271"></a>00271 <span class="comment"> /// True if this is a leaf node</span>
<a name="l00272"></a><a class="code" href="a00018.html#aaf1681ee7b53dffc6a3a7ef0a865f83b">00272</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00018.html#aaf1681ee7b53dffc6a3a7ef0a865f83b" title="True if this is a leaf node.">isleafnode</a>()<span class="keyword"> const</span>
<a name="l00273"></a>00273 <span class="keyword"> </span>{
<a name="l00274"></a>00274 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a9204f647e868560552dddc001aac8a55" title="Level in the b-tree, if level == 0 -&gt; leaf node.">level</a> == 0);
<a name="l00275"></a>00275 }
<a name="l00276"></a>00276 };
<a name="l00277"></a>00277 <span class="comment"></span>
<a name="l00278"></a>00278 <span class="comment"> /// Extended structure of a inner node in-memory. Contains only keys and no</span>
<a name="l00279"></a>00279 <span class="comment"> /// data items.</span>
<a name="l00280"></a><a class="code" href="a00015.html">00280</a> <span class="comment"></span> <span class="keyword">struct </span><a class="code" href="a00015.html" title="Extended structure of a inner node in-memory.">inner_node</a> : <span class="keyword">public</span> <a class="code" href="a00018.html" title="The header structure of each node in-memory.">node</a>
<a name="l00281"></a>00281 {<span class="comment"></span>
<a name="l00282"></a>00282 <span class="comment"> /// Define an related allocator for the inner_node structs.</span>
<a name="l00283"></a><a class="code" href="a00015.html#a0d8b919b9db1069387e966ae4b39c1b5">00283</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> _Alloc::template rebind&lt;inner_node&gt;::other <a class="code" href="a00015.html#a0d8b919b9db1069387e966ae4b39c1b5" title="Define an related allocator for the inner_node structs.">alloc_type</a>;
<a name="l00284"></a>00284 <span class="comment"></span>
<a name="l00285"></a>00285 <span class="comment"> /// Keys of children or data pointers</span>
<a name="l00286"></a><a class="code" href="a00015.html#ac78e5fb3be9571b04e97bd89c6aa22ee">00286</a> <span class="comment"></span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">key_type</a> <a class="code" href="a00015.html#ac78e5fb3be9571b04e97bd89c6aa22ee" title="Keys of children or data pointers.">slotkey</a>[<a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a>];
<a name="l00287"></a>00287 <span class="comment"></span>
<a name="l00288"></a>00288 <span class="comment"> /// Pointers to children</span>
<a name="l00289"></a><a class="code" href="a00015.html#ab573f6af3036dbc374c8914b61bdd2ec">00289</a> <span class="comment"></span> <a class="code" href="a00018.html" title="The header structure of each node in-memory.">node</a>* <a class="code" href="a00015.html#ab573f6af3036dbc374c8914b61bdd2ec" title="Pointers to children.">childid</a>[<a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a>+1];
<a name="l00290"></a>00290 <span class="comment"></span>
<a name="l00291"></a>00291 <span class="comment"> /// Set variables to initial values</span>
<a name="l00292"></a><a class="code" href="a00015.html#ae10027d02927a1c8c2303a419197078c">00292</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00015.html#ae10027d02927a1c8c2303a419197078c" title="Set variables to initial values.">initialize</a>(<span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> l)
<a name="l00293"></a>00293 {
<a name="l00294"></a>00294 <a class="code" href="a00015.html#ae10027d02927a1c8c2303a419197078c" title="Set variables to initial values.">node::initialize</a>(l);
<a name="l00295"></a>00295 }
<a name="l00296"></a>00296 <span class="comment"></span>
<a name="l00297"></a>00297 <span class="comment"> /// True if the node&#39;s slots are full</span>
<a name="l00298"></a><a class="code" href="a00015.html#ac046992e9d115a4c02079f58f8aff124">00298</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00015.html#ac046992e9d115a4c02079f58f8aff124" title="True if the node&#39;s slots are full.">isfull</a>()<span class="keyword"> const</span>
<a name="l00299"></a>00299 <span class="keyword"> </span>{
<a name="l00300"></a>00300 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> == <a class="code" href="a00001.html#a78ae296638b9d6961f9101ddf45bf3e0" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...">innerslotmax</a>);
<a name="l00301"></a>00301 }
<a name="l00302"></a>00302 <span class="comment"></span>
<a name="l00303"></a>00303 <span class="comment"> /// True if few used entries, less than half full</span>
<a name="l00304"></a><a class="code" href="a00015.html#ad1f041a8a15ebbca6d88f4819cc5e179">00304</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00015.html#ad1f041a8a15ebbca6d88f4819cc5e179" title="True if few used entries, less than half full.">isfew</a>()<span class="keyword"> const</span>
<a name="l00305"></a>00305 <span class="keyword"> </span>{
<a name="l00306"></a>00306 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> &lt;= <a class="code" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node.">mininnerslots</a>);
<a name="l00307"></a>00307 }
<a name="l00308"></a>00308 <span class="comment"></span>
<a name="l00309"></a>00309 <span class="comment"> /// True if node has too few entries</span>
<a name="l00310"></a><a class="code" href="a00015.html#aa5aea58745f1e12404802e0dd6863656">00310</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00015.html#aa5aea58745f1e12404802e0dd6863656" title="True if node has too few entries.">isunderflow</a>()<span class="keyword"> const</span>
<a name="l00311"></a>00311 <span class="keyword"> </span>{
<a name="l00312"></a>00312 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> &lt; <a class="code" href="a00001.html#aefbcc95b60d5bae8dd7ba9c25e5b6654" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node.">mininnerslots</a>);
<a name="l00313"></a>00313 }
<a name="l00314"></a>00314 };
<a name="l00315"></a>00315 <span class="comment"></span>
<a name="l00316"></a>00316 <span class="comment"> /// Extended structure of a leaf node in memory. Contains pairs of keys and</span>
<a name="l00317"></a>00317 <span class="comment"> /// data items. Key and data slots are kept in separate arrays, because the</span>
<a name="l00318"></a>00318 <span class="comment"> /// key array is traversed very often compared to accessing the data items.</span>
<a name="l00319"></a><a class="code" href="a00017.html">00319</a> <span class="comment"></span> <span class="keyword">struct </span><a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">leaf_node</a> : <span class="keyword">public</span> <a class="code" href="a00018.html" title="The header structure of each node in-memory.">node</a>
<a name="l00320"></a>00320 {<span class="comment"></span>
<a name="l00321"></a>00321 <span class="comment"> /// Define an related allocator for the leaf_node structs.</span>
<a name="l00322"></a><a class="code" href="a00017.html#a99d5a3d40c5098a75bbcb9404971e4fd">00322</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> _Alloc::template rebind&lt;leaf_node&gt;::other <a class="code" href="a00017.html#a99d5a3d40c5098a75bbcb9404971e4fd" title="Define an related allocator for the leaf_node structs.">alloc_type</a>;
<a name="l00323"></a>00323 <span class="comment"></span>
<a name="l00324"></a>00324 <span class="comment"> /// Double linked list pointers to traverse the leaves</span>
<a name="l00325"></a><a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000">00325</a> <span class="comment"></span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">leaf_node</a> *<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00326"></a>00326 <span class="comment"></span>
<a name="l00327"></a>00327 <span class="comment"> /// Double linked list pointers to traverse the leaves</span>
<a name="l00328"></a><a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367">00328</a> <span class="comment"></span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">leaf_node</a> *<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a>;
<a name="l00329"></a>00329 <span class="comment"></span>
<a name="l00330"></a>00330 <span class="comment"> /// Keys of children or data pointers</span>
<a name="l00331"></a><a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8">00331</a> <span class="comment"></span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">key_type</a> <a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[<a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a>];
<a name="l00332"></a>00332 <span class="comment"></span>
<a name="l00333"></a>00333 <span class="comment"> /// Array of data</span>
<a name="l00334"></a><a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432">00334</a> <span class="comment"></span> <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">data_type</a> <a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432" title="Array of data.">slotdata</a>[<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> ? 1 : <a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a>];
<a name="l00335"></a>00335 <span class="comment"></span>
<a name="l00336"></a>00336 <span class="comment"> /// Set variables to initial values</span>
<a name="l00337"></a><a class="code" href="a00017.html#a3db9141d0f1335ebaacb141ab6eef0d1">00337</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00017.html#a3db9141d0f1335ebaacb141ab6eef0d1" title="Set variables to initial values.">initialize</a>()
<a name="l00338"></a>00338 {
<a name="l00339"></a>00339 <a class="code" href="a00017.html#a3db9141d0f1335ebaacb141ab6eef0d1" title="Set variables to initial values.">node::initialize</a>(0);
<a name="l00340"></a>00340 <a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> = <a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a> = NULL;
<a name="l00341"></a>00341 }
<a name="l00342"></a>00342 <span class="comment"></span>
<a name="l00343"></a>00343 <span class="comment"> /// True if the node&#39;s slots are full</span>
<a name="l00344"></a><a class="code" href="a00017.html#a5f6015492b1e10183eef8a60a33680f4">00344</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00017.html#a5f6015492b1e10183eef8a60a33680f4" title="True if the node&#39;s slots are full.">isfull</a>()<span class="keyword"> const</span>
<a name="l00345"></a>00345 <span class="keyword"> </span>{
<a name="l00346"></a>00346 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> == <a class="code" href="a00001.html#ac6c274f39fce8e14f6a881fc1da39cf8" title="Base B+ tree parameter: The number of key/data slots in each leaf.">leafslotmax</a>);
<a name="l00347"></a>00347 }
<a name="l00348"></a>00348 <span class="comment"></span>
<a name="l00349"></a>00349 <span class="comment"> /// True if few used entries, less than half full</span>
<a name="l00350"></a><a class="code" href="a00017.html#a5dd4c34fed677676beaf1782ee4a873f">00350</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00017.html#a5dd4c34fed677676beaf1782ee4a873f" title="True if few used entries, less than half full.">isfew</a>()<span class="keyword"> const</span>
<a name="l00351"></a>00351 <span class="keyword"> </span>{
<a name="l00352"></a>00352 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> &lt;= <a class="code" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">minleafslots</a>);
<a name="l00353"></a>00353 }
<a name="l00354"></a>00354 <span class="comment"></span>
<a name="l00355"></a>00355 <span class="comment"> /// True if node has too few entries</span>
<a name="l00356"></a><a class="code" href="a00017.html#acb0129f5abf7dafb3d802b7ea25b418c">00356</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00017.html#acb0129f5abf7dafb3d802b7ea25b418c" title="True if node has too few entries.">isunderflow</a>()<span class="keyword"> const</span>
<a name="l00357"></a>00357 <span class="keyword"> </span>{
<a name="l00358"></a>00358 <span class="keywordflow">return</span> (<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a> &lt; <a class="code" href="a00001.html#ad8525611bf3b079ca4ab13dbab9b23c0" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">minleafslots</a>);
<a name="l00359"></a>00359 }
<a name="l00360"></a>00360 <span class="comment"></span>
<a name="l00361"></a>00361 <span class="comment"> /// Set the (key,data) pair in slot. Overloaded function used by</span>
<a name="l00362"></a>00362 <span class="comment"> /// bulk_load().</span>
<a name="l00363"></a><a class="code" href="a00017.html#ab93769e06b9644f7f4c47416d59d312c">00363</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00017.html#ab93769e06b9644f7f4c47416d59d312c" title="Set the (key,data) pair in slot.">set_slot</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> slot, <span class="keyword">const</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>&amp; value)
<a name="l00364"></a>00364 {
<a name="l00365"></a>00365 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> == <span class="keyword">false</span>);
<a name="l00366"></a>00366 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(slot &lt; <a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a>);
<a name="l00367"></a>00367 <a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[slot] = value.first;
<a name="l00368"></a>00368 <a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432" title="Array of data.">slotdata</a>[slot] = value.second;
<a name="l00369"></a>00369 }
<a name="l00370"></a>00370 <span class="comment"></span>
<a name="l00371"></a>00371 <span class="comment"> /// Set the key pair in slot. Overloaded function used by</span>
<a name="l00372"></a>00372 <span class="comment"> /// bulk_load().</span>
<a name="l00373"></a><a class="code" href="a00017.html#a3b2b782408d619ef8d0496930343015d">00373</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="a00017.html#ab93769e06b9644f7f4c47416d59d312c" title="Set the (key,data) pair in slot.">set_slot</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> slot, <span class="keyword">const</span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">key_type</a>&amp; key)
<a name="l00374"></a>00374 {
<a name="l00375"></a>00375 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> == <span class="keyword">true</span>);
<a name="l00376"></a>00376 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(slot &lt; <a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">node::slotuse</a>);
<a name="l00377"></a>00377 <a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[slot] = key;
<a name="l00378"></a>00378 }
<a name="l00379"></a>00379 };
<a name="l00380"></a>00380
<a name="l00381"></a>00381 <span class="keyword">private</span>:
<a name="l00382"></a>00382 <span class="comment">// *** Template Magic to Convert a pair or key/data types to a value_type</span>
<a name="l00383"></a>00383 <span class="comment"></span>
<a name="l00384"></a>00384 <span class="comment"> /// For sets the second pair_type is an empty struct, so the value_type</span>
<a name="l00385"></a>00385 <span class="comment"> /// should only be the first.</span>
<a name="l00386"></a>00386 <span class="comment"></span> <span class="keyword">template</span> &lt;<span class="keyword">typename</span> value_type, <span class="keyword">typename</span> pair_type&gt;
<a name="l00387"></a><a class="code" href="a00007.html">00387</a> <span class="keyword">struct </span><a class="code" href="a00007.html" title="For sets the second pair_type is an empty struct, so the value_type should only be the first...">btree_pair_to_value</a>
<a name="l00388"></a>00388 {<span class="comment"></span>
<a name="l00389"></a>00389 <span class="comment"> /// Convert a fake pair type to just the first component</span>
<a name="l00390"></a><a class="code" href="a00007.html#adf06d39520a423a4a5de3982753025c3">00390</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a> <a class="code" href="a00007.html#adf06d39520a423a4a5de3982753025c3" title="Convert a fake pair type to just the first component.">operator()</a>(<a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>&amp; p)<span class="keyword"> const </span>{
<a name="l00391"></a>00391 <span class="keywordflow">return</span> p.first;
<a name="l00392"></a>00392 }<span class="comment"></span>
<a name="l00393"></a>00393 <span class="comment"> /// Convert a fake pair type to just the first component</span>
<a name="l00394"></a><a class="code" href="a00007.html#a1cac939fc310be496b995ae11d7056d8">00394</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a> <a class="code" href="a00007.html#a1cac939fc310be496b995ae11d7056d8" title="Convert a fake pair type to just the first component.">operator()</a>(<span class="keyword">const</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>&amp; p)<span class="keyword"> const </span>{
<a name="l00395"></a>00395 <span class="keywordflow">return</span> p.first;
<a name="l00396"></a>00396 }
<a name="l00397"></a>00397 };
<a name="l00398"></a>00398 <span class="comment"></span>
<a name="l00399"></a>00399 <span class="comment"> /// For maps value_type is the same as the pair_type</span>
<a name="l00400"></a>00400 <span class="comment"></span> <span class="keyword">template</span> &lt;<span class="keyword">typename</span> value_type&gt;
<a name="l00401"></a><a class="code" href="a00008.html">00401</a> <span class="keyword">struct </span><a class="code" href="a00007.html" title="For sets the second pair_type is an empty struct, so the value_type should only be the first...">btree_pair_to_value</a>&lt;<a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a>, <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a>&gt;
<a name="l00402"></a>00402 {<span class="comment"></span>
<a name="l00403"></a>00403 <span class="comment"> /// Identity &quot;convert&quot; a real pair type to just the first component</span>
<a name="l00404"></a><a class="code" href="a00008.html#a95aefcd10d430360cbdeb2cddb04bfcd">00404</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a> <a class="code" href="a00008.html#a95aefcd10d430360cbdeb2cddb04bfcd" title="Identity &quot;convert&quot; a real pair type to just the first component.">operator()</a>(<a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>&amp; p)<span class="keyword"> const </span>{
<a name="l00405"></a>00405 <span class="keywordflow">return</span> p;
<a name="l00406"></a>00406 }<span class="comment"></span>
<a name="l00407"></a>00407 <span class="comment"> /// Identity &quot;convert&quot; a real pair type to just the first component</span>
<a name="l00408"></a><a class="code" href="a00008.html#a0d3e61d7f25f9de525f295ad24a85140">00408</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">value_type</a> <a class="code" href="a00008.html#a0d3e61d7f25f9de525f295ad24a85140" title="Identity &quot;convert&quot; a real pair type to just the first component.">operator()</a>(<span class="keyword">const</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">pair_type</a>&amp; p)<span class="keyword"> const </span>{
<a name="l00409"></a>00409 <span class="keywordflow">return</span> p;
<a name="l00410"></a>00410 }
<a name="l00411"></a>00411 };
<a name="l00412"></a>00412 <span class="comment"></span>
<a name="l00413"></a>00413 <span class="comment"> /// Using template specialization select the correct converter used by the</span>
<a name="l00414"></a>00414 <span class="comment"> /// iterators</span>
<a name="l00415"></a><a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce">00415</a> <span class="comment"></span> <span class="keyword">typedef</span> btree_pair_to_value&lt;value_type, pair_type&gt; <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>;
<a name="l00416"></a>00416
<a name="l00417"></a>00417 <span class="keyword">public</span>:
<a name="l00418"></a>00418 <span class="comment">// *** Iterators and Reverse Iterators</span>
<a name="l00419"></a>00419
<a name="l00420"></a>00420 <span class="keyword">class </span>iterator;
<a name="l00421"></a>00421 <span class="keyword">class </span>const_iterator;
<a name="l00422"></a>00422 <span class="keyword">class </span>reverse_iterator;
<a name="l00423"></a>00423 <span class="keyword">class </span>const_reverse_iterator;
<a name="l00424"></a>00424 <span class="comment"></span>
<a name="l00425"></a>00425 <span class="comment"> /// STL-like iterator object for B+ tree items. The iterator points to a</span>
<a name="l00426"></a>00426 <span class="comment"> /// specific slot number in a leaf.</span>
<a name="l00427"></a><a class="code" href="a00016.html">00427</a> <span class="comment"></span> <span class="keyword">class </span><a class="code" href="a00016.html" title="STL-like iterator object for B+ tree items.">iterator</a>
<a name="l00428"></a>00428 {
<a name="l00429"></a>00429 <span class="keyword">public</span>:
<a name="l00430"></a>00430 <span class="comment">// *** Types</span>
<a name="l00431"></a>00431 <span class="comment"></span>
<a name="l00432"></a>00432 <span class="comment"> /// The key type of the btree. Returned by key().</span>
<a name="l00433"></a><a class="code" href="a00016.html#a8b03fc63a85738411711197143596475">00433</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">btree::key_type</a> <a class="code" href="a00016.html#a8b03fc63a85738411711197143596475" title="The key type of the btree. Returned by key().">key_type</a>;
<a name="l00434"></a>00434 <span class="comment"></span>
<a name="l00435"></a>00435 <span class="comment"> /// The data type of the btree. Returned by data().</span>
<a name="l00436"></a><a class="code" href="a00016.html#ac28707a6e23e871cb85c7ff7f8119c73">00436</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">btree::data_type</a> <a class="code" href="a00016.html#ac28707a6e23e871cb85c7ff7f8119c73" title="The data type of the btree. Returned by data().">data_type</a>;
<a name="l00437"></a>00437 <span class="comment"></span>
<a name="l00438"></a>00438 <span class="comment"> /// The value type of the btree. Returned by operator*().</span>
<a name="l00439"></a><a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f">00439</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">btree::value_type</a> <a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f" title="The value type of the btree. Returned by operator*().">value_type</a>;
<a name="l00440"></a>00440 <span class="comment"></span>
<a name="l00441"></a>00441 <span class="comment"> /// The pair type of the btree.</span>
<a name="l00442"></a><a class="code" href="a00016.html#a2b722e1077949a356115387bfd606d63">00442</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">btree::pair_type</a> <a class="code" href="a00016.html#a2b722e1077949a356115387bfd606d63" title="The pair type of the btree.">pair_type</a>;
<a name="l00443"></a>00443 <span class="comment"></span>
<a name="l00444"></a>00444 <span class="comment"> /// Reference to the value_type. STL required.</span>
<a name="l00445"></a><a class="code" href="a00016.html#ae1af55705fdbcf4a78144fbd6b3df028">00445</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f" title="The value type of the btree. Returned by operator*().">value_type</a>&amp; <a class="code" href="a00016.html#ae1af55705fdbcf4a78144fbd6b3df028" title="Reference to the value_type. STL required.">reference</a>;
<a name="l00446"></a>00446 <span class="comment"></span>
<a name="l00447"></a>00447 <span class="comment"> /// Pointer to the value_type. STL required.</span>
<a name="l00448"></a><a class="code" href="a00016.html#adfe951a60a834784653dac6d883f73a8">00448</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f" title="The value type of the btree. Returned by operator*().">value_type</a>* <a class="code" href="a00016.html#adfe951a60a834784653dac6d883f73a8" title="Pointer to the value_type. STL required.">pointer</a>;
<a name="l00449"></a>00449 <span class="comment"></span>
<a name="l00450"></a>00450 <span class="comment"> /// STL-magic iterator category</span>
<a name="l00451"></a><a class="code" href="a00016.html#ac67229e1e4649f4b77a27dcbd0beb41d">00451</a> <span class="comment"></span> <span class="keyword">typedef</span> std::bidirectional_iterator_tag <a class="code" href="a00016.html#ac67229e1e4649f4b77a27dcbd0beb41d" title="STL-magic iterator category.">iterator_category</a>;
<a name="l00452"></a>00452 <span class="comment"></span>
<a name="l00453"></a>00453 <span class="comment"> /// STL-magic</span>
<a name="l00454"></a><a class="code" href="a00016.html#a7a8fd55d12a4cb472bcae87285737d77">00454</a> <span class="comment"></span> <span class="keyword">typedef</span> ptrdiff_t <a class="code" href="a00016.html#a7a8fd55d12a4cb472bcae87285737d77" title="STL-magic.">difference_type</a>;
<a name="l00455"></a>00455 <span class="comment"></span>
<a name="l00456"></a>00456 <span class="comment"> /// Our own type</span>
<a name="l00457"></a><a class="code" href="a00016.html#a88e3dfff3f3d4601b35cfd4e7f477960">00457</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00016.html" title="STL-like iterator object for B+ tree items.">iterator</a> <span class="keyword">self</span>;
<a name="l00458"></a>00458
<a name="l00459"></a>00459 <span class="keyword">private</span>:
<a name="l00460"></a>00460 <span class="comment">// *** Members</span>
<a name="l00461"></a>00461 <span class="comment"></span>
<a name="l00462"></a>00462 <span class="comment"> /// The currently referenced leaf node of the tree</span>
<a name="l00463"></a><a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4">00463</a> <span class="comment"></span> <span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a>* <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>;
<a name="l00464"></a>00464 <span class="comment"></span>
<a name="l00465"></a>00465 <span class="comment"> /// Current key/data slot referenced</span>
<a name="l00466"></a><a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8">00466</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>;
<a name="l00467"></a>00467 <span class="comment"></span>
<a name="l00468"></a>00468 <span class="comment"> /// Friendly to the const_iterator, so it may access the two data items</span>
<a name="l00469"></a>00469 <span class="comment"> /// directly.</span>
<a name="l00470"></a><a class="code" href="a00016.html#ac220ce1c155db1ac44146c12d178056f">00470</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00010.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a>;
<a name="l00471"></a>00471 <span class="comment"></span>
<a name="l00472"></a>00472 <span class="comment"> /// Also friendly to the reverse_iterator, so it may access the two</span>
<a name="l00473"></a>00473 <span class="comment"> /// data items directly.</span>
<a name="l00474"></a><a class="code" href="a00016.html#af0a70641f2216cc31420487a62dd3b0d">00474</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00020.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a>;
<a name="l00475"></a>00475 <span class="comment"></span>
<a name="l00476"></a>00476 <span class="comment"> /// Also friendly to the const_reverse_iterator, so it may access the</span>
<a name="l00477"></a>00477 <span class="comment"> /// two data items directly.</span>
<a name="l00478"></a><a class="code" href="a00016.html#a776e261b45ef26d713a4d105a8d7c240">00478</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00011.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a>;
<a name="l00479"></a>00479 <span class="comment"></span>
<a name="l00480"></a>00480 <span class="comment"> /// Also friendly to the base btree class, because erase_iter() needs</span>
<a name="l00481"></a>00481 <span class="comment"> /// to read the currnode and currslot values directly.</span>
<a name="l00482"></a>00482 <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00001.html" title="Basic class implementing a base B+ tree data structure in memory.">btree</a>&lt;<a class="code" href="a00016.html#a8b03fc63a85738411711197143596475" title="The key type of the btree. Returned by key().">key_type</a>, <a class="code" href="a00016.html#ac28707a6e23e871cb85c7ff7f8119c73" title="The data type of the btree. Returned by data().">data_type</a>, <a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f" title="The value type of the btree. Returned by operator*().">value_type</a>, <a class="code" href="a00001.html#a71413b8b8a1440539691a97f4cb61cae" title="Fourth template parameter: Key comparison function object.">key_compare</a>,
<a name="l00483"></a><a class="code" href="a00016.html#a1de115e86b32c4ed13649b6760f1da28">00483</a> <a class="code" href="a00001.html#a8b13a0eb2e558d11830d38de21b82319" title="Fifth template parameter: Traits object used to define more parameters of the B+ tree.">traits</a>, <a class="code" href="a00001.html#acd41575a35d1c5d55e955aafc9762454" title="Sixth template parameter: Allow duplicate keys in the B+ tree.">allow_duplicates</a>, <a class="code" href="a00001.html#aef567d7893cd02d22933a2e68702532b" title="Seventh template parameter: STL allocator for tree nodes.">allocator_type</a>, <a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a>&gt;;
<a name="l00484"></a>00484 <span class="comment"></span>
<a name="l00485"></a>00485 <span class="comment"> /// Evil! A temporary value_type to STL-correctly deliver operator* and</span>
<a name="l00486"></a>00486 <span class="comment"> /// operator-&gt;</span>
<a name="l00487"></a><a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f">00487</a> <span class="comment"></span> <span class="keyword">mutable</span> <a class="code" href="a00016.html#a3ca0d6f7760b4aa78ff47e53e82d7e1f" title="The value type of the btree. Returned by operator*().">value_type</a> <a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00488"></a>00488
<a name="l00489"></a>00489 <span class="comment">// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00490"></a>00490 <span class="comment">// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00491"></a>00491 <span class="comment">// tree.</span>
<a name="l00492"></a>00492 <a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.">BTREE_FRIENDS</a>
<a name="l00493"></a>00493
<a name="l00494"></a>00494 <span class="keyword">public</span>:
<a name="l00495"></a>00495 <span class="comment">// *** Methods</span>
<a name="l00496"></a>00496 <span class="comment"></span>
<a name="l00497"></a>00497 <span class="comment"> /// Default-Constructor of a mutable iterator</span>
<a name="l00498"></a><a class="code" href="a00016.html#a18c4fa1f457e6b7c14cbb610d60e4fdf">00498</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#a18c4fa1f457e6b7c14cbb610d60e4fdf" title="Default-Constructor of a mutable iterator.">iterator</a>()
<a name="l00499"></a>00499 : <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>(NULL), <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>(0)
<a name="l00500"></a>00500 { }
<a name="l00501"></a>00501 <span class="comment"></span>
<a name="l00502"></a>00502 <span class="comment"> /// Initializing-Constructor of a mutable iterator</span>
<a name="l00503"></a><a class="code" href="a00016.html#aafad7b45ec60a4466a4695638ed369a4">00503</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#a18c4fa1f457e6b7c14cbb610d60e4fdf" title="Default-Constructor of a mutable iterator.">iterator</a>(<span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a> *l, <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> s)
<a name="l00504"></a>00504 : <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>(l), <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>(s)
<a name="l00505"></a>00505 { }
<a name="l00506"></a>00506 <span class="comment"></span>
<a name="l00507"></a>00507 <span class="comment"> /// Copy-constructor from a reverse iterator</span>
<a name="l00508"></a><a class="code" href="a00016.html#addb909f2f9d3b008d43e962b3bc0ef01">00508</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#a18c4fa1f457e6b7c14cbb610d60e4fdf" title="Default-Constructor of a mutable iterator.">iterator</a>(<span class="keyword">const</span> <a class="code" href="a00020.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a> &amp;it)
<a name="l00509"></a>00509 : <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>(it.<a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>), <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>(it.<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>)
<a name="l00510"></a>00510 { }
<a name="l00511"></a>00511 <span class="comment"></span>
<a name="l00512"></a>00512 <span class="comment"> /// Dereference the iterator, this is not a value_type&amp; because key and</span>
<a name="l00513"></a>00513 <span class="comment"> /// value are not stored together</span>
<a name="l00514"></a><a class="code" href="a00016.html#ae3399c4dbeb9f3d1cb69f03b0717ef08">00514</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#ae1af55705fdbcf4a78144fbd6b3df028" title="Reference to the value_type. STL required.">reference</a> <a class="code" href="a00016.html#ae3399c4dbeb9f3d1cb69f03b0717ef08" title="Dereference the iterator, this is not a value_type&amp; because key and value are not stored together...">operator*</a>()<span class="keyword"> const</span>
<a name="l00515"></a>00515 <span class="keyword"> </span>{
<a name="l00516"></a>00516 <a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00016.html#a2b722e1077949a356115387bfd606d63" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00016.html#a58add29a798f555f30dc83b75bdc8c46" title="Key of the current slot.">key</a>(),<a class="code" href="a00016.html#a374ee1815c28dcef298e20c36cfc8dbc" title="Writable reference to the current data object.">data</a>()) );
<a name="l00517"></a>00517 <span class="keywordflow">return</span> <a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00518"></a>00518 }
<a name="l00519"></a>00519 <span class="comment"></span>
<a name="l00520"></a>00520 <span class="comment"> /// Dereference the iterator. Do not use this if possible, use key()</span>
<a name="l00521"></a>00521 <span class="comment"> /// and data() instead. The B+ tree does not stored key and data</span>
<a name="l00522"></a>00522 <span class="comment"> /// together.</span>
<a name="l00523"></a><a class="code" href="a00016.html#a8a59d09fca6bbea43b096ea75048551a">00523</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#adfe951a60a834784653dac6d883f73a8" title="Pointer to the value_type. STL required.">pointer</a> <a class="code" href="a00016.html#a8a59d09fca6bbea43b096ea75048551a" title="Dereference the iterator.">operator-&gt;</a>()<span class="keyword"> const</span>
<a name="l00524"></a>00524 <span class="keyword"> </span>{
<a name="l00525"></a>00525 <a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00016.html#a2b722e1077949a356115387bfd606d63" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00016.html#a58add29a798f555f30dc83b75bdc8c46" title="Key of the current slot.">key</a>(),<a class="code" href="a00016.html#a374ee1815c28dcef298e20c36cfc8dbc" title="Writable reference to the current data object.">data</a>()) );
<a name="l00526"></a>00526 <span class="keywordflow">return</span> &amp;<a class="code" href="a00016.html#a3853bb0ba23d1149d7d3e90d08a74e7f" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00527"></a>00527 }
<a name="l00528"></a>00528 <span class="comment"></span>
<a name="l00529"></a>00529 <span class="comment"> /// Key of the current slot</span>
<a name="l00530"></a><a class="code" href="a00016.html#a58add29a798f555f30dc83b75bdc8c46">00530</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="a00016.html#a8b03fc63a85738411711197143596475" title="The key type of the btree. Returned by key().">key_type</a>&amp; <a class="code" href="a00016.html#a58add29a798f555f30dc83b75bdc8c46" title="Key of the current slot.">key</a>()<span class="keyword"> const</span>
<a name="l00531"></a>00531 <span class="keyword"> </span>{
<a name="l00532"></a>00532 <span class="keywordflow">return</span> <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>];
<a name="l00533"></a>00533 }
<a name="l00534"></a>00534 <span class="comment"></span>
<a name="l00535"></a>00535 <span class="comment"> /// Writable reference to the current data object</span>
<a name="l00536"></a><a class="code" href="a00016.html#a374ee1815c28dcef298e20c36cfc8dbc">00536</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00016.html#ac28707a6e23e871cb85c7ff7f8119c73" title="The data type of the btree. Returned by data().">data_type</a>&amp; <a class="code" href="a00016.html#a374ee1815c28dcef298e20c36cfc8dbc" title="Writable reference to the current data object.">data</a>()<span class="keyword"> const</span>
<a name="l00537"></a>00537 <span class="keyword"> </span>{
<a name="l00538"></a>00538 <span class="keywordflow">return</span> <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432" title="Array of data.">slotdata</a>[<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> ? 0 : <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>];
<a name="l00539"></a>00539 }
<a name="l00540"></a>00540 <span class="comment"></span>
<a name="l00541"></a>00541 <span class="comment"> /// Prefix++ advance the iterator to the next slot</span>
<a name="l00542"></a><a class="code" href="a00016.html#affd98a29650798f84818a1de2a0dbc35">00542</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00016.html#affd98a29650798f84818a1de2a0dbc35" title="Prefix++ advance the iterator to the next slot.">operator++</a>()
<a name="l00543"></a>00543 {
<a name="l00544"></a>00544 <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> + 1 &lt; <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>) {
<a name="l00545"></a>00545 ++<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>;
<a name="l00546"></a>00546 }
<a name="l00547"></a>00547 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a> != NULL) {
<a name="l00548"></a>00548 <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a>;
<a name="l00549"></a>00549 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00550"></a>00550 }
<a name="l00551"></a>00551 <span class="keywordflow">else</span> {
<a name="l00552"></a>00552 <span class="comment">// this is end()</span>
<a name="l00553"></a>00553 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00554"></a>00554 }
<a name="l00555"></a>00555
<a name="l00556"></a>00556 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00557"></a>00557 }
<a name="l00558"></a>00558 <span class="comment"></span>
<a name="l00559"></a>00559 <span class="comment"> /// Postfix++ advance the iterator to the next slot</span>
<a name="l00560"></a><a class="code" href="a00016.html#a1367882a6316d3e4d9075ece22ea77bf">00560</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span> <a class="code" href="a00016.html#affd98a29650798f84818a1de2a0dbc35" title="Prefix++ advance the iterator to the next slot.">operator++</a>(<span class="keywordtype">int</span>)
<a name="l00561"></a>00561 {
<a name="l00562"></a>00562 <span class="keyword">self</span> tmp = *<span class="keyword">this</span>; <span class="comment">// copy ourselves</span>
<a name="l00563"></a>00563
<a name="l00564"></a>00564 <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> + 1 &lt; <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>) {
<a name="l00565"></a>00565 ++<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>;
<a name="l00566"></a>00566 }
<a name="l00567"></a>00567 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a> != NULL) {
<a name="l00568"></a>00568 <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a>;
<a name="l00569"></a>00569 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00570"></a>00570 }
<a name="l00571"></a>00571 <span class="keywordflow">else</span> {
<a name="l00572"></a>00572 <span class="comment">// this is end()</span>
<a name="l00573"></a>00573 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00574"></a>00574 }
<a name="l00575"></a>00575
<a name="l00576"></a>00576 <span class="keywordflow">return</span> tmp;
<a name="l00577"></a>00577 }
<a name="l00578"></a>00578 <span class="comment"></span>
<a name="l00579"></a>00579 <span class="comment"> /// Prefix-- backstep the iterator to the last slot</span>
<a name="l00580"></a><a class="code" href="a00016.html#a5807472b2a7f185f65de62b650545f0b">00580</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00016.html#a5807472b2a7f185f65de62b650545f0b" title="Prefix-- backstep the iterator to the last slot.">operator--</a>()
<a name="l00581"></a>00581 {
<a name="l00582"></a>00582 <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> &gt; 0) {
<a name="l00583"></a>00583 --<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>;
<a name="l00584"></a>00584 }
<a name="l00585"></a>00585 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> != NULL) {
<a name="l00586"></a>00586 <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00587"></a>00587 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a> - 1;
<a name="l00588"></a>00588 }
<a name="l00589"></a>00589 <span class="keywordflow">else</span> {
<a name="l00590"></a>00590 <span class="comment">// this is begin()</span>
<a name="l00591"></a>00591 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00592"></a>00592 }
<a name="l00593"></a>00593
<a name="l00594"></a>00594 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00595"></a>00595 }
<a name="l00596"></a>00596 <span class="comment"></span>
<a name="l00597"></a>00597 <span class="comment"> /// Postfix-- backstep the iterator to the last slot</span>
<a name="l00598"></a><a class="code" href="a00016.html#a234e0d078e0373687db74565ad23275b">00598</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span> <a class="code" href="a00016.html#a5807472b2a7f185f65de62b650545f0b" title="Prefix-- backstep the iterator to the last slot.">operator--</a>(<span class="keywordtype">int</span>)
<a name="l00599"></a>00599 {
<a name="l00600"></a>00600 <span class="keyword">self</span> tmp = *<span class="keyword">this</span>; <span class="comment">// copy ourselves</span>
<a name="l00601"></a>00601
<a name="l00602"></a>00602 <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> &gt; 0) {
<a name="l00603"></a>00603 --<a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>;
<a name="l00604"></a>00604 }
<a name="l00605"></a>00605 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> != NULL) {
<a name="l00606"></a>00606 <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00607"></a>00607 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a> - 1;
<a name="l00608"></a>00608 }
<a name="l00609"></a>00609 <span class="keywordflow">else</span> {
<a name="l00610"></a>00610 <span class="comment">// this is begin()</span>
<a name="l00611"></a>00611 <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00612"></a>00612 }
<a name="l00613"></a>00613
<a name="l00614"></a>00614 <span class="keywordflow">return</span> tmp;
<a name="l00615"></a>00615 }
<a name="l00616"></a>00616 <span class="comment"></span>
<a name="l00617"></a>00617 <span class="comment"> /// Equality of iterators</span>
<a name="l00618"></a><a class="code" href="a00016.html#a219e56b7da3e108394d14707f1b05da3">00618</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00016.html#a219e56b7da3e108394d14707f1b05da3" title="Equality of iterators.">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)<span class="keyword"> const</span>
<a name="l00619"></a>00619 <span class="keyword"> </span>{
<a name="l00620"></a>00620 <span class="keywordflow">return</span> (x.currnode == <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>) &amp;&amp; (x.currslot == <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>);
<a name="l00621"></a>00621 }
<a name="l00622"></a>00622 <span class="comment"></span>
<a name="l00623"></a>00623 <span class="comment"> /// Inequality of iterators</span>
<a name="l00624"></a><a class="code" href="a00016.html#ae8b63ca7ab4ca95783fcff9d7381f65d">00624</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00016.html#ae8b63ca7ab4ca95783fcff9d7381f65d" title="Inequality of iterators.">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)<span class="keyword"> const</span>
<a name="l00625"></a>00625 <span class="keyword"> </span>{
<a name="l00626"></a>00626 <span class="keywordflow">return</span> (x.currnode != <a class="code" href="a00016.html#a2342904be584a159fa07a1fe280428b4" title="The currently referenced leaf node of the tree.">currnode</a>) || (x.currslot != <a class="code" href="a00016.html#a7a8172193bcc54048fbc4d38a9b0dde8" title="Current key/data slot referenced.">currslot</a>);
<a name="l00627"></a>00627 }
<a name="l00628"></a>00628 };
<a name="l00629"></a>00629 <span class="comment"></span>
<a name="l00630"></a>00630 <span class="comment"> /// STL-like read-only iterator object for B+ tree items. The iterator</span>
<a name="l00631"></a>00631 <span class="comment"> /// points to a specific slot number in a leaf.</span>
<a name="l00632"></a><a class="code" href="a00010.html">00632</a> <span class="comment"></span> <span class="keyword">class </span><a class="code" href="a00010.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a>
<a name="l00633"></a>00633 {
<a name="l00634"></a>00634 <span class="keyword">public</span>:
<a name="l00635"></a>00635 <span class="comment">// *** Types</span>
<a name="l00636"></a>00636 <span class="comment"></span>
<a name="l00637"></a>00637 <span class="comment"> /// The key type of the btree. Returned by key().</span>
<a name="l00638"></a><a class="code" href="a00010.html#af9bd869933413977b355edecdad03826">00638</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">btree::key_type</a> <a class="code" href="a00010.html#af9bd869933413977b355edecdad03826" title="The key type of the btree. Returned by key().">key_type</a>;
<a name="l00639"></a>00639 <span class="comment"></span>
<a name="l00640"></a>00640 <span class="comment"> /// The data type of the btree. Returned by data().</span>
<a name="l00641"></a><a class="code" href="a00010.html#a3e9bc58f428c88258f0f6dae0d1b262f">00641</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">btree::data_type</a> <a class="code" href="a00010.html#a3e9bc58f428c88258f0f6dae0d1b262f" title="The data type of the btree. Returned by data().">data_type</a>;
<a name="l00642"></a>00642 <span class="comment"></span>
<a name="l00643"></a>00643 <span class="comment"> /// The value type of the btree. Returned by operator*().</span>
<a name="l00644"></a><a class="code" href="a00010.html#a35215b1458e16ce11dd75678d50e10f2">00644</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">btree::value_type</a> <a class="code" href="a00010.html#a35215b1458e16ce11dd75678d50e10f2" title="The value type of the btree. Returned by operator*().">value_type</a>;
<a name="l00645"></a>00645 <span class="comment"></span>
<a name="l00646"></a>00646 <span class="comment"> /// The pair type of the btree.</span>
<a name="l00647"></a><a class="code" href="a00010.html#ad5418a87bffde41e783a232e6304d690">00647</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">btree::pair_type</a> <a class="code" href="a00010.html#ad5418a87bffde41e783a232e6304d690" title="The pair type of the btree.">pair_type</a>;
<a name="l00648"></a>00648 <span class="comment"></span>
<a name="l00649"></a>00649 <span class="comment"> /// Reference to the value_type. STL required.</span>
<a name="l00650"></a><a class="code" href="a00010.html#a419752bbbda4094865f8d8e13d16b2ba">00650</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="a00010.html#a35215b1458e16ce11dd75678d50e10f2" title="The value type of the btree. Returned by operator*().">value_type</a>&amp; <a class="code" href="a00010.html#a419752bbbda4094865f8d8e13d16b2ba" title="Reference to the value_type. STL required.">reference</a>;
<a name="l00651"></a>00651 <span class="comment"></span>
<a name="l00652"></a>00652 <span class="comment"> /// Pointer to the value_type. STL required.</span>
<a name="l00653"></a><a class="code" href="a00010.html#ae6ef73c30bc2db3e007309f4f5791ce1">00653</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="a00010.html#a35215b1458e16ce11dd75678d50e10f2" title="The value type of the btree. Returned by operator*().">value_type</a>* <a class="code" href="a00010.html#ae6ef73c30bc2db3e007309f4f5791ce1" title="Pointer to the value_type. STL required.">pointer</a>;
<a name="l00654"></a>00654 <span class="comment"></span>
<a name="l00655"></a>00655 <span class="comment"> /// STL-magic iterator category</span>
<a name="l00656"></a><a class="code" href="a00010.html#a2fd7333035de59a5c83df70a96a53b7c">00656</a> <span class="comment"></span> <span class="keyword">typedef</span> std::bidirectional_iterator_tag <a class="code" href="a00010.html#a2fd7333035de59a5c83df70a96a53b7c" title="STL-magic iterator category.">iterator_category</a>;
<a name="l00657"></a>00657 <span class="comment"></span>
<a name="l00658"></a>00658 <span class="comment"> /// STL-magic</span>
<a name="l00659"></a><a class="code" href="a00010.html#a3259e576dca916415ada01c0b579c6fb">00659</a> <span class="comment"></span> <span class="keyword">typedef</span> ptrdiff_t <a class="code" href="a00010.html#a3259e576dca916415ada01c0b579c6fb" title="STL-magic.">difference_type</a>;
<a name="l00660"></a>00660 <span class="comment"></span>
<a name="l00661"></a>00661 <span class="comment"> /// Our own type</span>
<a name="l00662"></a><a class="code" href="a00010.html#af6590c93be7bee1df834d22122d703a1">00662</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00010.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <span class="keyword">self</span>;
<a name="l00663"></a>00663
<a name="l00664"></a>00664 <span class="keyword">private</span>:
<a name="l00665"></a>00665 <span class="comment">// *** Members</span>
<a name="l00666"></a>00666 <span class="comment"></span>
<a name="l00667"></a>00667 <span class="comment"> /// The currently referenced leaf node of the tree</span>
<a name="l00668"></a><a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46">00668</a> <span class="comment"></span> <span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a>* <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>;
<a name="l00669"></a>00669 <span class="comment"></span>
<a name="l00670"></a>00670 <span class="comment"> /// Current key/data slot referenced</span>
<a name="l00671"></a><a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde">00671</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>;
<a name="l00672"></a>00672 <span class="comment"></span>
<a name="l00673"></a>00673 <span class="comment"> /// Friendly to the reverse_const_iterator, so it may access the two</span>
<a name="l00674"></a>00674 <span class="comment"> /// data items directly</span>
<a name="l00675"></a><a class="code" href="a00010.html#a776e261b45ef26d713a4d105a8d7c240">00675</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00011.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a>;
<a name="l00676"></a>00676 <span class="comment"></span>
<a name="l00677"></a>00677 <span class="comment"> /// Evil! A temporary value_type to STL-correctly deliver operator* and</span>
<a name="l00678"></a>00678 <span class="comment"> /// operator-&gt;</span>
<a name="l00679"></a><a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5">00679</a> <span class="comment"></span> <span class="keyword">mutable</span> <a class="code" href="a00010.html#a35215b1458e16ce11dd75678d50e10f2" title="The value type of the btree. Returned by operator*().">value_type</a> <a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00680"></a>00680
<a name="l00681"></a>00681 <span class="comment">// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00682"></a>00682 <span class="comment">// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00683"></a>00683 <span class="comment">// tree.</span>
<a name="l00684"></a>00684 <a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.">BTREE_FRIENDS</a>
<a name="l00685"></a>00685
<a name="l00686"></a>00686 <span class="keyword">public</span>:
<a name="l00687"></a>00687 <span class="comment">// *** Methods</span>
<a name="l00688"></a>00688 <span class="comment"></span>
<a name="l00689"></a>00689 <span class="comment"> /// Default-Constructor of a const iterator</span>
<a name="l00690"></a><a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504">00690</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504" title="Default-Constructor of a const iterator.">const_iterator</a>()
<a name="l00691"></a>00691 : <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>(NULL), <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>(0)
<a name="l00692"></a>00692 { }
<a name="l00693"></a>00693 <span class="comment"></span>
<a name="l00694"></a>00694 <span class="comment"> /// Initializing-Constructor of a const iterator</span>
<a name="l00695"></a><a class="code" href="a00010.html#a56aba66f521f1a397d380921437fb689">00695</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504" title="Default-Constructor of a const iterator.">const_iterator</a>(<span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a> *l, <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> s)
<a name="l00696"></a>00696 : <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>(l), <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>(s)
<a name="l00697"></a>00697 { }
<a name="l00698"></a>00698 <span class="comment"></span>
<a name="l00699"></a>00699 <span class="comment"> /// Copy-constructor from a mutable iterator</span>
<a name="l00700"></a><a class="code" href="a00010.html#a8eeaa8f21a999eb9ceba7445a5f2249c">00700</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504" title="Default-Constructor of a const iterator.">const_iterator</a>(<span class="keyword">const</span> <a class="code" href="a00016.html" title="STL-like iterator object for B+ tree items.">iterator</a> &amp;it)
<a name="l00701"></a>00701 : <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>(it.<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>), <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>(it.<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>)
<a name="l00702"></a>00702 { }
<a name="l00703"></a>00703 <span class="comment"></span>
<a name="l00704"></a>00704 <span class="comment"> /// Copy-constructor from a mutable reverse iterator</span>
<a name="l00705"></a><a class="code" href="a00010.html#a804b6134629b6005947bb53896593dc2">00705</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504" title="Default-Constructor of a const iterator.">const_iterator</a>(<span class="keyword">const</span> <a class="code" href="a00020.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a> &amp;it)
<a name="l00706"></a>00706 : <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>(it.<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>), <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>(it.<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>)
<a name="l00707"></a>00707 { }
<a name="l00708"></a>00708 <span class="comment"></span>
<a name="l00709"></a>00709 <span class="comment"> /// Copy-constructor from a const reverse iterator</span>
<a name="l00710"></a><a class="code" href="a00010.html#adf2a0a9f38ed9d19fc35a29e7ca9f501">00710</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#aa398e6e926d38251e31e4448328ee504" title="Default-Constructor of a const iterator.">const_iterator</a>(<span class="keyword">const</span> <a class="code" href="a00011.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a> &amp;it)
<a name="l00711"></a>00711 : <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>(it.<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>), <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>(it.<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>)
<a name="l00712"></a>00712 { }
<a name="l00713"></a>00713 <span class="comment"></span>
<a name="l00714"></a>00714 <span class="comment"> /// Dereference the iterator. Do not use this if possible, use key()</span>
<a name="l00715"></a>00715 <span class="comment"> /// and data() instead. The B+ tree does not stored key and data</span>
<a name="l00716"></a>00716 <span class="comment"> /// together.</span>
<a name="l00717"></a><a class="code" href="a00010.html#a07b48aa4ca141c1f1d53c150f33e591b">00717</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#a419752bbbda4094865f8d8e13d16b2ba" title="Reference to the value_type. STL required.">reference</a> <a class="code" href="a00010.html#a07b48aa4ca141c1f1d53c150f33e591b" title="Dereference the iterator.">operator*</a>()<span class="keyword"> const</span>
<a name="l00718"></a>00718 <span class="keyword"> </span>{
<a name="l00719"></a>00719 <a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00010.html#ad5418a87bffde41e783a232e6304d690" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00010.html#a9b700cfcf53b89ce178833f9bed1df2f" title="Key of the current slot.">key</a>(),<a class="code" href="a00010.html#a0c38df0d4e1f83c33c52c63b2ca6edd9" title="Read-only reference to the current data object.">data</a>()) );
<a name="l00720"></a>00720 <span class="keywordflow">return</span> <a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00721"></a>00721 }
<a name="l00722"></a>00722 <span class="comment"></span>
<a name="l00723"></a>00723 <span class="comment"> /// Dereference the iterator. Do not use this if possible, use key()</span>
<a name="l00724"></a>00724 <span class="comment"> /// and data() instead. The B+ tree does not stored key and data</span>
<a name="l00725"></a>00725 <span class="comment"> /// together.</span>
<a name="l00726"></a><a class="code" href="a00010.html#a670a87d8fccf4c9aab90f5a6b2a22d75">00726</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00010.html#ae6ef73c30bc2db3e007309f4f5791ce1" title="Pointer to the value_type. STL required.">pointer</a> <a class="code" href="a00010.html#a670a87d8fccf4c9aab90f5a6b2a22d75" title="Dereference the iterator.">operator-&gt;</a>()<span class="keyword"> const</span>
<a name="l00727"></a>00727 <span class="keyword"> </span>{
<a name="l00728"></a>00728 <a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00010.html#ad5418a87bffde41e783a232e6304d690" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00010.html#a9b700cfcf53b89ce178833f9bed1df2f" title="Key of the current slot.">key</a>(),<a class="code" href="a00010.html#a0c38df0d4e1f83c33c52c63b2ca6edd9" title="Read-only reference to the current data object.">data</a>()) );
<a name="l00729"></a>00729 <span class="keywordflow">return</span> &amp;<a class="code" href="a00010.html#a390bd1c0e4146b53df1c725a9c52dfa5" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00730"></a>00730 }
<a name="l00731"></a>00731 <span class="comment"></span>
<a name="l00732"></a>00732 <span class="comment"> /// Key of the current slot</span>
<a name="l00733"></a><a class="code" href="a00010.html#a9b700cfcf53b89ce178833f9bed1df2f">00733</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="a00010.html#af9bd869933413977b355edecdad03826" title="The key type of the btree. Returned by key().">key_type</a>&amp; <a class="code" href="a00010.html#a9b700cfcf53b89ce178833f9bed1df2f" title="Key of the current slot.">key</a>()<span class="keyword"> const</span>
<a name="l00734"></a>00734 <span class="keyword"> </span>{
<a name="l00735"></a>00735 <span class="keywordflow">return</span> <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>];
<a name="l00736"></a>00736 }
<a name="l00737"></a>00737 <span class="comment"></span>
<a name="l00738"></a>00738 <span class="comment"> /// Read-only reference to the current data object</span>
<a name="l00739"></a><a class="code" href="a00010.html#a0c38df0d4e1f83c33c52c63b2ca6edd9">00739</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="a00010.html#a3e9bc58f428c88258f0f6dae0d1b262f" title="The data type of the btree. Returned by data().">data_type</a>&amp; <a class="code" href="a00010.html#a0c38df0d4e1f83c33c52c63b2ca6edd9" title="Read-only reference to the current data object.">data</a>()<span class="keyword"> const</span>
<a name="l00740"></a>00740 <span class="keyword"> </span>{
<a name="l00741"></a>00741 <span class="keywordflow">return</span> <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432" title="Array of data.">slotdata</a>[<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> ? 0 : <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>];
<a name="l00742"></a>00742 }
<a name="l00743"></a>00743 <span class="comment"></span>
<a name="l00744"></a>00744 <span class="comment"> /// Prefix++ advance the iterator to the next slot</span>
<a name="l00745"></a><a class="code" href="a00010.html#a70dced9b01dbb9ea963e072c837eff09">00745</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00010.html#a70dced9b01dbb9ea963e072c837eff09" title="Prefix++ advance the iterator to the next slot.">operator++</a>()
<a name="l00746"></a>00746 {
<a name="l00747"></a>00747 <span class="keywordflow">if</span> (<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> + 1 &lt; <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>) {
<a name="l00748"></a>00748 ++<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>;
<a name="l00749"></a>00749 }
<a name="l00750"></a>00750 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a> != NULL) {
<a name="l00751"></a>00751 <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a>;
<a name="l00752"></a>00752 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00753"></a>00753 }
<a name="l00754"></a>00754 <span class="keywordflow">else</span> {
<a name="l00755"></a>00755 <span class="comment">// this is end()</span>
<a name="l00756"></a>00756 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00757"></a>00757 }
<a name="l00758"></a>00758
<a name="l00759"></a>00759 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00760"></a>00760 }
<a name="l00761"></a>00761 <span class="comment"></span>
<a name="l00762"></a>00762 <span class="comment"> /// Postfix++ advance the iterator to the next slot</span>
<a name="l00763"></a><a class="code" href="a00010.html#a18c993a3ff60f293e9a3f37adda41ddb">00763</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span> <a class="code" href="a00010.html#a70dced9b01dbb9ea963e072c837eff09" title="Prefix++ advance the iterator to the next slot.">operator++</a>(<span class="keywordtype">int</span>)
<a name="l00764"></a>00764 {
<a name="l00765"></a>00765 <span class="keyword">self</span> tmp = *<span class="keyword">this</span>; <span class="comment">// copy ourselves</span>
<a name="l00766"></a>00766
<a name="l00767"></a>00767 <span class="keywordflow">if</span> (<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> + 1 &lt; <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>) {
<a name="l00768"></a>00768 ++<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>;
<a name="l00769"></a>00769 }
<a name="l00770"></a>00770 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a> != NULL) {
<a name="l00771"></a>00771 <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a32f06cf3a6f67709039ca40851b03367" title="Double linked list pointers to traverse the leaves.">nextleaf</a>;
<a name="l00772"></a>00772 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00773"></a>00773 }
<a name="l00774"></a>00774 <span class="keywordflow">else</span> {
<a name="l00775"></a>00775 <span class="comment">// this is end()</span>
<a name="l00776"></a>00776 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00777"></a>00777 }
<a name="l00778"></a>00778
<a name="l00779"></a>00779 <span class="keywordflow">return</span> tmp;
<a name="l00780"></a>00780 }
<a name="l00781"></a>00781 <span class="comment"></span>
<a name="l00782"></a>00782 <span class="comment"> /// Prefix-- backstep the iterator to the last slot</span>
<a name="l00783"></a><a class="code" href="a00010.html#a5ec18e7ef4ca59cd65992fc37e86582b">00783</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00010.html#a5ec18e7ef4ca59cd65992fc37e86582b" title="Prefix-- backstep the iterator to the last slot.">operator--</a>()
<a name="l00784"></a>00784 {
<a name="l00785"></a>00785 <span class="keywordflow">if</span> (<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> &gt; 0) {
<a name="l00786"></a>00786 --<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>;
<a name="l00787"></a>00787 }
<a name="l00788"></a>00788 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> != NULL) {
<a name="l00789"></a>00789 <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00790"></a>00790 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a> - 1;
<a name="l00791"></a>00791 }
<a name="l00792"></a>00792 <span class="keywordflow">else</span> {
<a name="l00793"></a>00793 <span class="comment">// this is begin()</span>
<a name="l00794"></a>00794 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00795"></a>00795 }
<a name="l00796"></a>00796
<a name="l00797"></a>00797 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00798"></a>00798 }
<a name="l00799"></a>00799 <span class="comment"></span>
<a name="l00800"></a>00800 <span class="comment"> /// Postfix-- backstep the iterator to the last slot</span>
<a name="l00801"></a><a class="code" href="a00010.html#a625efcb27c39904ffa30e9476262d234">00801</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span> <a class="code" href="a00010.html#a5ec18e7ef4ca59cd65992fc37e86582b" title="Prefix-- backstep the iterator to the last slot.">operator--</a>(<span class="keywordtype">int</span>)
<a name="l00802"></a>00802 {
<a name="l00803"></a>00803 <span class="keyword">self</span> tmp = *<span class="keyword">this</span>; <span class="comment">// copy ourselves</span>
<a name="l00804"></a>00804
<a name="l00805"></a>00805 <span class="keywordflow">if</span> (<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> &gt; 0) {
<a name="l00806"></a>00806 --<a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>;
<a name="l00807"></a>00807 }
<a name="l00808"></a>00808 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> != NULL) {
<a name="l00809"></a>00809 <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00810"></a>00810 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a> - 1;
<a name="l00811"></a>00811 }
<a name="l00812"></a>00812 <span class="keywordflow">else</span> {
<a name="l00813"></a>00813 <span class="comment">// this is begin()</span>
<a name="l00814"></a>00814 <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a> = 0;
<a name="l00815"></a>00815 }
<a name="l00816"></a>00816
<a name="l00817"></a>00817 <span class="keywordflow">return</span> tmp;
<a name="l00818"></a>00818 }
<a name="l00819"></a>00819 <span class="comment"></span>
<a name="l00820"></a>00820 <span class="comment"> /// Equality of iterators</span>
<a name="l00821"></a><a class="code" href="a00010.html#acb7975fe9086511b129da9bc6c579b7f">00821</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00010.html#acb7975fe9086511b129da9bc6c579b7f" title="Equality of iterators.">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)<span class="keyword"> const</span>
<a name="l00822"></a>00822 <span class="keyword"> </span>{
<a name="l00823"></a>00823 <span class="keywordflow">return</span> (x.currnode == <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>) &amp;&amp; (x.currslot == <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>);
<a name="l00824"></a>00824 }
<a name="l00825"></a>00825 <span class="comment"></span>
<a name="l00826"></a>00826 <span class="comment"> /// Inequality of iterators</span>
<a name="l00827"></a><a class="code" href="a00010.html#afe4bead48fa24df2c42b6cff6be9c8fb">00827</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="a00010.html#afe4bead48fa24df2c42b6cff6be9c8fb" title="Inequality of iterators.">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span>&amp; x)<span class="keyword"> const</span>
<a name="l00828"></a>00828 <span class="keyword"> </span>{
<a name="l00829"></a>00829 <span class="keywordflow">return</span> (x.currnode != <a class="code" href="a00010.html#aaf41fc7558a241186e7aeb4fd4c26d46" title="The currently referenced leaf node of the tree.">currnode</a>) || (x.currslot != <a class="code" href="a00010.html#a384e9365c13f059943588447ab9aefde" title="Current key/data slot referenced.">currslot</a>);
<a name="l00830"></a>00830 }
<a name="l00831"></a>00831 };
<a name="l00832"></a>00832 <span class="comment"></span>
<a name="l00833"></a>00833 <span class="comment"> /// STL-like mutable reverse iterator object for B+ tree items. The</span>
<a name="l00834"></a>00834 <span class="comment"> /// iterator points to a specific slot number in a leaf.</span>
<a name="l00835"></a><a class="code" href="a00020.html">00835</a> <span class="comment"></span> <span class="keyword">class </span><a class="code" href="a00020.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a>
<a name="l00836"></a>00836 {
<a name="l00837"></a>00837 <span class="keyword">public</span>:
<a name="l00838"></a>00838 <span class="comment">// *** Types</span>
<a name="l00839"></a>00839 <span class="comment"></span>
<a name="l00840"></a>00840 <span class="comment"> /// The key type of the btree. Returned by key().</span>
<a name="l00841"></a><a class="code" href="a00020.html#a6c51c511a728641235b1b766d370d947">00841</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a73a9d635f33527a1329937f3e5f0ee5a" title="First template parameter: The key type of the B+ tree.">btree::key_type</a> <a class="code" href="a00020.html#a6c51c511a728641235b1b766d370d947" title="The key type of the btree. Returned by key().">key_type</a>;
<a name="l00842"></a>00842 <span class="comment"></span>
<a name="l00843"></a>00843 <span class="comment"> /// The data type of the btree. Returned by data().</span>
<a name="l00844"></a><a class="code" href="a00020.html#adbbb473dc39aa6939320a775270db73b">00844</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#acfb48ad6a3845870e64c38dd1b562616" title="Second template parameter: The data type associated with each key.">btree::data_type</a> <a class="code" href="a00020.html#adbbb473dc39aa6939320a775270db73b" title="The data type of the btree. Returned by data().">data_type</a>;
<a name="l00845"></a>00845 <span class="comment"></span>
<a name="l00846"></a>00846 <span class="comment"> /// The value type of the btree. Returned by operator*().</span>
<a name="l00847"></a><a class="code" href="a00020.html#a4d5aa6d6f89994af073ed8de8023b702">00847</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#ab66ffb9c9a42bea595ef23cf9dbfd8d6" title="Third template parameter: Composition pair of key and data types, this is required by the STL standar...">btree::value_type</a> <a class="code" href="a00020.html#a4d5aa6d6f89994af073ed8de8023b702" title="The value type of the btree. Returned by operator*().">value_type</a>;
<a name="l00848"></a>00848 <span class="comment"></span>
<a name="l00849"></a>00849 <span class="comment"> /// The pair type of the btree.</span>
<a name="l00850"></a><a class="code" href="a00020.html#a29586b9555247c18a0bbc963077277cc">00850</a> <span class="comment"></span> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="a00001.html#a2cddd431e50047766f45902b9f6f5c31" title="The pair of key_type and data_type, this may be different from value_type.">btree::pair_type</a> <a class="code" href="a00020.html#a29586b9555247c18a0bbc963077277cc" title="The pair type of the btree.">pair_type</a>;
<a name="l00851"></a>00851 <span class="comment"></span>
<a name="l00852"></a>00852 <span class="comment"> /// Reference to the value_type. STL required.</span>
<a name="l00853"></a><a class="code" href="a00020.html#aafabdbb26269c865eff146d29d106d95">00853</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00020.html#a4d5aa6d6f89994af073ed8de8023b702" title="The value type of the btree. Returned by operator*().">value_type</a>&amp; <a class="code" href="a00020.html#aafabdbb26269c865eff146d29d106d95" title="Reference to the value_type. STL required.">reference</a>;
<a name="l00854"></a>00854 <span class="comment"></span>
<a name="l00855"></a>00855 <span class="comment"> /// Pointer to the value_type. STL required.</span>
<a name="l00856"></a><a class="code" href="a00020.html#abec59d5ad25b0caaa3dbd19cb1e5c1b4">00856</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00020.html#a4d5aa6d6f89994af073ed8de8023b702" title="The value type of the btree. Returned by operator*().">value_type</a>* <a class="code" href="a00020.html#abec59d5ad25b0caaa3dbd19cb1e5c1b4" title="Pointer to the value_type. STL required.">pointer</a>;
<a name="l00857"></a>00857 <span class="comment"></span>
<a name="l00858"></a>00858 <span class="comment"> /// STL-magic iterator category</span>
<a name="l00859"></a><a class="code" href="a00020.html#aedcdafaa9eadd4eadb05e09b44aa17f9">00859</a> <span class="comment"></span> <span class="keyword">typedef</span> std::bidirectional_iterator_tag <a class="code" href="a00020.html#aedcdafaa9eadd4eadb05e09b44aa17f9" title="STL-magic iterator category.">iterator_category</a>;
<a name="l00860"></a>00860 <span class="comment"></span>
<a name="l00861"></a>00861 <span class="comment"> /// STL-magic</span>
<a name="l00862"></a><a class="code" href="a00020.html#a1821d9cc06d632bfb5d2fcc277413c79">00862</a> <span class="comment"></span> <span class="keyword">typedef</span> ptrdiff_t <a class="code" href="a00020.html#a1821d9cc06d632bfb5d2fcc277413c79" title="STL-magic.">difference_type</a>;
<a name="l00863"></a>00863 <span class="comment"></span>
<a name="l00864"></a>00864 <span class="comment"> /// Our own type</span>
<a name="l00865"></a><a class="code" href="a00020.html#a7730c375657891e38202c564487c5249">00865</a> <span class="comment"></span> <span class="keyword">typedef</span> <a class="code" href="a00020.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a> <span class="keyword">self</span>;
<a name="l00866"></a>00866
<a name="l00867"></a>00867 <span class="keyword">private</span>:
<a name="l00868"></a>00868 <span class="comment">// *** Members</span>
<a name="l00869"></a>00869 <span class="comment"></span>
<a name="l00870"></a>00870 <span class="comment"> /// The currently referenced leaf node of the tree</span>
<a name="l00871"></a><a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd">00871</a> <span class="comment"></span> <span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a>* <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>;
<a name="l00872"></a>00872 <span class="comment"></span>
<a name="l00873"></a>00873 <span class="comment"> /// One slot past the current key/data slot referenced.</span>
<a name="l00874"></a><a class="code" href="a00020.html#a18093d258964badd66e623908a699774">00874</a> <span class="comment"></span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>;
<a name="l00875"></a>00875 <span class="comment"></span>
<a name="l00876"></a>00876 <span class="comment"> /// Friendly to the const_iterator, so it may access the two data items</span>
<a name="l00877"></a>00877 <span class="comment"> /// directly</span>
<a name="l00878"></a><a class="code" href="a00020.html#a67171474c4da6cc8efe0c7fafefd2b2d">00878</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00016.html" title="STL-like iterator object for B+ tree items.">iterator</a>;
<a name="l00879"></a>00879 <span class="comment"></span>
<a name="l00880"></a>00880 <span class="comment"> /// Also friendly to the const_iterator, so it may access the two data</span>
<a name="l00881"></a>00881 <span class="comment"> /// items directly</span>
<a name="l00882"></a><a class="code" href="a00020.html#ac220ce1c155db1ac44146c12d178056f">00882</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00010.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a>;
<a name="l00883"></a>00883 <span class="comment"></span>
<a name="l00884"></a>00884 <span class="comment"> /// Also friendly to the const_iterator, so it may access the two data</span>
<a name="l00885"></a>00885 <span class="comment"> /// items directly</span>
<a name="l00886"></a><a class="code" href="a00020.html#a776e261b45ef26d713a4d105a8d7c240">00886</a> <span class="comment"></span> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="a00011.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a>;
<a name="l00887"></a>00887 <span class="comment"></span>
<a name="l00888"></a>00888 <span class="comment"> /// Evil! A temporary value_type to STL-correctly deliver operator* and</span>
<a name="l00889"></a>00889 <span class="comment"> /// operator-&gt;</span>
<a name="l00890"></a><a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c">00890</a> <span class="comment"></span> <span class="keyword">mutable</span> <a class="code" href="a00020.html#a4d5aa6d6f89994af073ed8de8023b702" title="The value type of the btree. Returned by operator*().">value_type</a> <a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00891"></a>00891
<a name="l00892"></a>00892 <span class="comment">// The macro BTREE_FRIENDS can be used by outside class to access the B+</span>
<a name="l00893"></a>00893 <span class="comment">// tree internals. This was added for wxBTreeDemo to be able to draw the</span>
<a name="l00894"></a>00894 <span class="comment">// tree.</span>
<a name="l00895"></a>00895 <a class="code" href="a00026.html#aec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.">BTREE_FRIENDS</a>
<a name="l00896"></a>00896
<a name="l00897"></a>00897 <span class="keyword">public</span>:
<a name="l00898"></a>00898 <span class="comment">// *** Methods</span>
<a name="l00899"></a>00899 <span class="comment"></span>
<a name="l00900"></a>00900 <span class="comment"> /// Default-Constructor of a reverse iterator</span>
<a name="l00901"></a><a class="code" href="a00020.html#a037a981f590f5cf648a66f84a37a8e01">00901</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#a037a981f590f5cf648a66f84a37a8e01" title="Default-Constructor of a reverse iterator.">reverse_iterator</a>()
<a name="l00902"></a>00902 : <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>(NULL), <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>(0)
<a name="l00903"></a>00903 { }
<a name="l00904"></a>00904 <span class="comment"></span>
<a name="l00905"></a>00905 <span class="comment"> /// Initializing-Constructor of a mutable reverse iterator</span>
<a name="l00906"></a><a class="code" href="a00020.html#af9450ea2c4aa1326fb62099d9a15f10c">00906</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#a037a981f590f5cf648a66f84a37a8e01" title="Default-Constructor of a reverse iterator.">reverse_iterator</a>(<span class="keyword">typename</span> <a class="code" href="a00017.html" title="Extended structure of a leaf node in memory.">btree::leaf_node</a> *l, <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> s)
<a name="l00907"></a>00907 : <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>(l), <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>(s)
<a name="l00908"></a>00908 { }
<a name="l00909"></a>00909 <span class="comment"></span>
<a name="l00910"></a>00910 <span class="comment"> /// Copy-constructor from a mutable iterator</span>
<a name="l00911"></a><a class="code" href="a00020.html#a971eb197745a946766bd4dc9febc9be4">00911</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#a037a981f590f5cf648a66f84a37a8e01" title="Default-Constructor of a reverse iterator.">reverse_iterator</a>(<span class="keyword">const</span> <a class="code" href="a00016.html" title="STL-like iterator object for B+ tree items.">iterator</a> &amp;it)
<a name="l00912"></a>00912 : <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>(it.<a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>), <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>(it.<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>)
<a name="l00913"></a>00913 { }
<a name="l00914"></a>00914 <span class="comment"></span>
<a name="l00915"></a>00915 <span class="comment"> /// Dereference the iterator, this is not a value_type&amp; because key and</span>
<a name="l00916"></a>00916 <span class="comment"> /// value are not stored together</span>
<a name="l00917"></a><a class="code" href="a00020.html#ac4ab8274575df053e010e4ce7f66ef96">00917</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#aafabdbb26269c865eff146d29d106d95" title="Reference to the value_type. STL required.">reference</a> <a class="code" href="a00020.html#ac4ab8274575df053e010e4ce7f66ef96" title="Dereference the iterator, this is not a value_type&amp; because key and value are not stored together...">operator*</a>()<span class="keyword"> const</span>
<a name="l00918"></a>00918 <span class="keyword"> </span>{
<a name="l00919"></a>00919 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> &gt; 0);
<a name="l00920"></a>00920 <a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00020.html#a29586b9555247c18a0bbc963077277cc" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00020.html#af080cb064e66be74b06c471cdbb82f0b" title="Key of the current slot.">key</a>(),<a class="code" href="a00020.html#a913c74f0137024989f6ab3eb1568b961" title="Writable reference to the current data object.">data</a>()) );
<a name="l00921"></a>00921 <span class="keywordflow">return</span> <a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00922"></a>00922 }
<a name="l00923"></a>00923 <span class="comment"></span>
<a name="l00924"></a>00924 <span class="comment"> /// Dereference the iterator. Do not use this if possible, use key()</span>
<a name="l00925"></a>00925 <span class="comment"> /// and data() instead. The B+ tree does not stored key and data</span>
<a name="l00926"></a>00926 <span class="comment"> /// together.</span>
<a name="l00927"></a><a class="code" href="a00020.html#a59e5d71e8750afe41bdebbf01dc2983c">00927</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#abec59d5ad25b0caaa3dbd19cb1e5c1b4" title="Pointer to the value_type. STL required.">pointer</a> <a class="code" href="a00020.html#a59e5d71e8750afe41bdebbf01dc2983c" title="Dereference the iterator.">operator-&gt;</a>()<span class="keyword"> const</span>
<a name="l00928"></a>00928 <span class="keyword"> </span>{
<a name="l00929"></a>00929 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> &gt; 0);
<a name="l00930"></a>00930 <a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a> = <a class="code" href="a00001.html#a76bd9fc84f712e0d962314c1d6a188ce" title="Using template specialization select the correct converter used by the iterators.">pair_to_value_type</a>()( <a class="code" href="a00020.html#a29586b9555247c18a0bbc963077277cc" title="The pair type of the btree.">pair_type</a>(<a class="code" href="a00020.html#af080cb064e66be74b06c471cdbb82f0b" title="Key of the current slot.">key</a>(),<a class="code" href="a00020.html#a913c74f0137024989f6ab3eb1568b961" title="Writable reference to the current data object.">data</a>()) );
<a name="l00931"></a>00931 <span class="keywordflow">return</span> &amp;<a class="code" href="a00020.html#a63ccdf692264f526659802b5326bc13c" title="Evil! A temporary value_type to STL-correctly deliver operator* and operator-&gt;">temp_value</a>;
<a name="l00932"></a>00932 }
<a name="l00933"></a>00933 <span class="comment"></span>
<a name="l00934"></a>00934 <span class="comment"> /// Key of the current slot</span>
<a name="l00935"></a><a class="code" href="a00020.html#af080cb064e66be74b06c471cdbb82f0b">00935</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="a00020.html#a6c51c511a728641235b1b766d370d947" title="The key type of the btree. Returned by key().">key_type</a>&amp; <a class="code" href="a00020.html#af080cb064e66be74b06c471cdbb82f0b" title="Key of the current slot.">key</a>()<span class="keyword"> const</span>
<a name="l00936"></a>00936 <span class="keyword"> </span>{
<a name="l00937"></a>00937 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> &gt; 0);
<a name="l00938"></a>00938 <span class="keywordflow">return</span> <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#af92e519f605cf7b7aae74f6f5d6c8bd8" title="Keys of children or data pointers.">slotkey</a>[<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> - 1];
<a name="l00939"></a>00939 }
<a name="l00940"></a>00940 <span class="comment"></span>
<a name="l00941"></a>00941 <span class="comment"> /// Writable reference to the current data object</span>
<a name="l00942"></a><a class="code" href="a00020.html#a913c74f0137024989f6ab3eb1568b961">00942</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="a00020.html#adbbb473dc39aa6939320a775270db73b" title="The data type of the btree. Returned by data().">data_type</a>&amp; <a class="code" href="a00020.html#a913c74f0137024989f6ab3eb1568b961" title="Writable reference to the current data object.">data</a>()<span class="keyword"> const</span>
<a name="l00943"></a>00943 <span class="keyword"> </span>{
<a name="l00944"></a>00944 <a class="code" href="a00026.html#a6ac57b9b59dae34aea28cda65b0d14bb" title="Assertion only if BTREE_DEBUG is defined. This is not used in verify().">BTREE_ASSERT</a>(<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> &gt; 0);
<a name="l00945"></a>00945 <span class="keywordflow">return</span> <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#ad4fc245fe5b90c21dec069792c3f7432" title="Array of data.">slotdata</a>[<a class="code" href="a00001.html#a636973c0a66512d36c7aa833435ad023" title="Eighth template parameter: boolean indicator whether the btree is used as a set.">used_as_set</a> ? 0 : <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>-1];
<a name="l00946"></a>00946 }
<a name="l00947"></a>00947 <span class="comment"></span>
<a name="l00948"></a>00948 <span class="comment"> /// Prefix++ advance the iterator to the next slot</span>
<a name="l00949"></a><a class="code" href="a00020.html#a83c5c8552459da2b6047762874aec039">00949</a> <span class="comment"></span> <span class="keyword">inline</span> <span class="keyword">self</span>&amp; <a class="code" href="a00020.html#a83c5c8552459da2b6047762874aec039" title="Prefix++ advance the iterator to the next slot.">operator++</a>()
<a name="l00950"></a>00950 {
<a name="l00951"></a>00951 <span class="keywordflow">if</span> (<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> &gt; 1) {
<a name="l00952"></a>00952 --<a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a>;
<a name="l00953"></a>00953 }
<a name="l00954"></a>00954 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (<a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a> != NULL) {
<a name="l00955"></a>00955 <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a> = <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00017.html#a56890dc287b29ae39f3e070a26cae000" title="Double linked list pointers to traverse the leaves.">prevleaf</a>;
<a name="l00956"></a>00956 <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> = <a class="code" href="a00020.html#aa0d19039b62c1900832061ff5ffc0cdd" title="The currently referenced leaf node of the tree.">currnode</a>-&gt;<a class="code" href="a00018.html#a3c6e7088a8ca73d43cec76973bb8f903" title="Number of key slotuse use, so number of valid children or data pointers.">slotuse</a>;
<a name="l00957"></a>00957 }
<a name="l00958"></a>00958 <span class="keywordflow">else</span> {
<a name="l00959"></a>00959 <span class="comment">// this is begin() == rend()</span>
<a name="l00960"></a>00960 <a class="code" href="a00020.html#a18093d258964badd66e623908a699774" title="One slot past the current key/data slot referenced.">currslot</a> = 0;
<a name="l00961"></a>00961 }
<a name="l00962"></a>00962
<a name="l00963"></a>00963 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00964"></a>00964 }
<a name="l00965"></a>00965 <span class="comment"></span><