<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>STX B+ Tree Template Classes: stx/btree_set.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.6 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</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>
</ul>
</div>
<h1>stx/btree_set.h</h1><a href="btree__set_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// $Id: btree_set.h 113 2008-09-07 15:25:51Z tb $</span>
<a name="l00006"></a>00006 <span class="comment"></span><span class="comment">/*</span>
<a name="l00007"></a>00007 <span class="comment"> * STX B+ Tree Template Classes v0.8.3</span>
<a name="l00008"></a>00008 <span class="comment"> * Copyright (C) 2008 Timo Bingmann</span>
<a name="l00009"></a>00009 <span class="comment"> *</span>
<a name="l00010"></a>00010 <span class="comment"> * This library is free software; you can redistribute it and/or modify it</span>
<a name="l00011"></a>00011 <span class="comment"> * under the terms of the GNU Lesser General Public License as published by the</span>
<a name="l00012"></a>00012 <span class="comment"> * Free Software Foundation; either version 2.1 of the License, or (at your</span>
<a name="l00013"></a>00013 <span class="comment"> * option) any later version.</span>
<a name="l00014"></a>00014 <span class="comment"> *</span>
<a name="l00015"></a>00015 <span class="comment"> * This library is distributed in the hope that it will be useful, but WITHOUT</span>
<a name="l00016"></a>00016 <span class="comment"> * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or</span>
<a name="l00017"></a>00017 <span class="comment"> * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License</span>
<a name="l00018"></a>00018 <span class="comment"> * for more details.</span>
<a name="l00019"></a>00019 <span class="comment"> *</span>
<a name="l00020"></a>00020 <span class="comment"> * You should have received a copy of the GNU Lesser General Public License</span>
<a name="l00021"></a>00021 <span class="comment"> * along with this library; if not, write to the Free Software Foundation,</span>
<a name="l00022"></a>00022 <span class="comment"> * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA</span>
<a name="l00023"></a>00023 <span class="comment"> */</span>
<a name="l00024"></a>00024
<a name="l00025"></a>00025 <span class="preprocessor">#ifndef _STX_BTREE_SET_H_</span>
<a name="l00026"></a>00026 <span class="preprocessor"></span><span class="preprocessor">#define _STX_BTREE_SET_H_</span>
<a name="l00027"></a>00027 <span class="preprocessor"></span>
<a name="l00028"></a>00028 <span class="preprocessor">#include <<a class="code" href="btree_8h.html" title="Contains the main B+ tree implementation template class btree.">stx/btree.h</a>></span>
<a name="l00029"></a>00029
<a name="l00030"></a>00030 <span class="keyword">namespace </span>stx {
<a name="l00031"></a>00031
<a name="l00049"></a>00049 <span class="keyword">template</span> <<span class="keyword">typename</span> _Key,
<a name="l00050"></a>00050 <span class="keyword">typename</span> _Compare = std::less<_Key>,
<a name="l00051"></a>00051 <span class="keyword">typename</span> _Traits = btree_default_set_traits<_Key> >
<a name="l00052"></a><a class="code" href="classstx_1_1btree__set.html">00052</a> <span class="keyword">class </span><a class="code" href="classstx_1_1btree__set.html" title="Specialized B+ tree template class implementing STL&#39;s set container.">btree_set</a>
<a name="l00053"></a>00053 {
<a name="l00054"></a>00054 <span class="keyword">public</span>:
<a name="l00055"></a>00055 <span class="comment">// *** Template Parameter Types</span>
<a name="l00056"></a>00056
<a name="l00059"></a><a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c">00059</a> <span class="keyword">typedef</span> _Key <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>;
<a name="l00060"></a>00060
<a name="l00062"></a><a class="code" href="classstx_1_1btree__set.html#194fe0d02f120a2b49d53a6788191cad">00062</a> <span class="keyword">typedef</span> _Compare <a class="code" href="classstx_1_1btree__set.html#194fe0d02f120a2b49d53a6788191cad" title="Second template parameter: Key comparison function object.">key_compare</a>;
<a name="l00063"></a>00063
<a name="l00066"></a><a class="code" href="classstx_1_1btree__set.html#b06119d9fef5746d356f67fdc3c4e7b9">00066</a> <span class="keyword">typedef</span> _Traits <a class="code" href="classstx_1_1btree__set.html#b06119d9fef5746d356f67fdc3c4e7b9" title="Third template parameter: Traits object used to define more parameters of the B+...">traits</a>;
<a name="l00067"></a>00067
<a name="l00071"></a>00071 <a class="code" href="btree_8h.html#ec07a93b351ce398f789007a441a4320" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals...">BTREE_FRIENDS</a>
<a name="l00072"></a>00072
<a name="l00073"></a>00073 <span class="keyword">private</span>:
<a name="l00074"></a>00074 <span class="comment">// *** The data_type</span>
<a name="l00075"></a>00075
<a name="l00077"></a><a class="code" href="structstx_1_1btree__set_1_1empty__struct.html">00077</a> <span class="keyword">struct </span><a class="code" href="structstx_1_1btree__set_1_1empty__struct.html" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals...">empty_struct</a>
<a name="l00078"></a>00078 {
<a name="l00079"></a>00079 };
<a name="l00080"></a>00080
<a name="l00081"></a>00081 <span class="keyword">public</span>:
<a name="l00082"></a>00082 <span class="comment">// *** Constructed Types</span>
<a name="l00083"></a>00083
<a name="l00085"></a><a class="code" href="classstx_1_1btree__set.html#ba90fcc1bc06eef41130790b8e9a1cde">00085</a> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structstx_1_1btree__set_1_1empty__struct.html" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals...">empty_struct</a> <a class="code" href="structstx_1_1btree__set_1_1empty__struct.html" title="The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals...">data_type</a>;
<a name="l00086"></a>00086
<a name="l00088"></a><a class="code" href="classstx_1_1btree__set.html#2ac96a547429ce330240b0cfa738ca98">00088</a> <span class="keyword">typedef</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> <a class="code" href="classstx_1_1btree__set.html#2ac96a547429ce330240b0cfa738ca98" title="Construct the set value_type: the key_type.">value_type</a>;
<a name="l00089"></a>00089
<a name="l00091"></a><a class="code" href="classstx_1_1btree__set.html#c36dc246679795a399c2cd8ee0c8d03a">00091</a> <span class="keyword">typedef</span> <a class="code" href="classstx_1_1btree__set.html" title="Specialized B+ tree template class implementing STL&#39;s set container.">btree_set<key_type, key_compare, traits></a> <span class="keyword">self</span>;
<a name="l00092"></a>00092
<a name="l00094"></a><a class="code" href="classstx_1_1btree__set.html#c6a0bba366143b72a73f5b6ccf49c030">00094</a> <span class="keyword">typedef</span> <a class="code" href="classstx_1_1btree.html" title="Basic class implementing a base B+ tree data structure in memory.">stx::btree<key_type, data_type, value_type, key_compare, traits, false></a> <a class="code" href="classstx_1_1btree.html" title="Basic class implementing a base B+ tree data structure in memory.">btree_impl</a>;
<a name="l00095"></a>00095
<a name="l00097"></a><a class="code" href="classstx_1_1btree__set.html#e47874da1778d7b88f7ed0d060076795">00097</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree_1_1value__compare.html" title="Function class to compare value_type objects. Required by the STL.">btree_impl::value_compare</a> <a class="code" href="classstx_1_1btree_1_1value__compare.html" title="Function class to compare value_type objects. Required by the STL.">value_compare</a>;
<a name="l00098"></a>00098
<a name="l00100"></a><a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa">00100</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree.html#973470864b67129983ea4e1aa2132ac5" title="Size type used to count keys.">btree_impl::size_type</a> <a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa" title="Size type used to count keys.">size_type</a>;
<a name="l00101"></a>00101
<a name="l00103"></a><a class="code" href="classstx_1_1btree__set.html#dcd05145516e714afee70db2756f558e">00103</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structstx_1_1btree_1_1tree__stats.html" title="A small struct containing basic statistics about the B+ tree.">btree_impl::tree_stats</a> <a class="code" href="structstx_1_1btree_1_1tree__stats.html" title="A small struct containing basic statistics about the B+ tree.">tree_stats</a>;
<a name="l00104"></a>00104
<a name="l00105"></a>00105 <span class="keyword">public</span>:
<a name="l00106"></a>00106 <span class="comment">// *** Static Constant Options and Values of the B+ Tree</span>
<a name="l00107"></a>00107
<a name="l00109"></a><a class="code" href="classstx_1_1btree__set.html#379fc29196c47e63b3b8d7d6899db987">00109</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="classstx_1_1btree__set.html#379fc29196c47e63b3b8d7d6899db987" title="Base B+ tree parameter: The number of key slots in each leaf.">leafslotmax</a> = <a class="code" href="classstx_1_1btree.html#12a39ca671e962924f4acf879a44eafc" title="Base B+ tree parameter: The number of key/data slots in each leaf.">btree_impl::leafslotmax</a>;
<a name="l00110"></a>00110
<a name="l00113"></a><a class="code" href="classstx_1_1btree__set.html#e7d95054a8b86eae9a3930cf42a6e365">00113</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="classstx_1_1btree__set.html#e7d95054a8b86eae9a3930cf42a6e365" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ...">innerslotmax</a> = <a class="code" href="classstx_1_1btree.html#83a18c2fb7f4e9cfd47ce7545d004324" title="Base B+ tree parameter: The number of key slots in each inner node, this can differ...">btree_impl::innerslotmax</a>;
<a name="l00114"></a>00114
<a name="l00118"></a><a class="code" href="classstx_1_1btree__set.html#27a7625c31206d57ad14028f2902e437">00118</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="classstx_1_1btree__set.html#27a7625c31206d57ad14028f2902e437" title="Computed B+ tree parameter: The minimum number of key slots used in a leaf.">minleafslots</a> = <a class="code" href="classstx_1_1btree.html#c53c2fe18cd06916a25c3b2a6e0486eb" title="Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.">btree_impl::minleafslots</a>;
<a name="l00119"></a>00119
<a name="l00123"></a><a class="code" href="classstx_1_1btree__set.html#45451da5c748aaedbd67eb5c244ddd08">00123</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span> <a class="code" href="classstx_1_1btree__set.html#45451da5c748aaedbd67eb5c244ddd08" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node...">mininnerslots</a> = <a class="code" href="classstx_1_1btree.html#14312352a7289cee65f1793b0183f60e" title="Computed B+ tree parameter: The minimum number of key slots used in an inner node...">btree_impl::mininnerslots</a>;
<a name="l00124"></a>00124
<a name="l00127"></a><a class="code" href="classstx_1_1btree__set.html#4cfd7d5d6009ea390022693d8de27c32">00127</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#4cfd7d5d6009ea390022693d8de27c32" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants...">selfverify</a> = <a class="code" href="classstx_1_1btree.html#ee2e25b0fccc7147fd8be0bcf8630b5b" title="Debug parameter: Enables expensive and thorough checking of the B+ tree invariants...">btree_impl::selfverify</a>;
<a name="l00128"></a>00128
<a name="l00132"></a><a class="code" href="classstx_1_1btree__set.html#5882a378d17483151ac58fdede3344c9">00132</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#5882a378d17483151ac58fdede3344c9" title="Debug parameter: Prints out lots of debug information about how the algorithms change...">debug</a> = <a class="code" href="classstx_1_1btree.html#ac6ff74fe9fb9e87958d73c28cb9eef4" title="Debug parameter: Prints out lots of debug information about how the algorithms change...">btree_impl::debug</a>;
<a name="l00133"></a>00133
<a name="l00135"></a><a class="code" href="classstx_1_1btree__set.html#a4256f4a03d4904787eec811005c7632">00135</a> <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#a4256f4a03d4904787eec811005c7632" title="Operational parameter: Allow duplicate keys in the btree.">allow_duplicates</a> = <a class="code" href="classstx_1_1btree.html#35378979c13861883affefda9ad95df7" title="Sixth template parameter: Allow duplicate keys in the B+ tree.">btree_impl::allow_duplicates</a>;
<a name="l00136"></a>00136
<a name="l00137"></a>00137 <span class="keyword">public</span>:
<a name="l00138"></a>00138 <span class="comment">// *** Iterators and Reverse Iterators</span>
<a name="l00139"></a>00139
<a name="l00142"></a><a class="code" href="classstx_1_1btree__set.html#0ef466a0144bb72f06eaf918147f01ec">00142</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">btree_impl::iterator</a> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a>;
<a name="l00143"></a>00143
<a name="l00146"></a><a class="code" href="classstx_1_1btree__set.html#e005c2b6bd8d0121f30f9d7d5012c6c0">00146</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">btree_impl::const_iterator</a> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a>;
<a name="l00147"></a>00147
<a name="l00149"></a><a class="code" href="classstx_1_1btree__set.html#4ac1acf4e0db5968072b6ae3aa6ffe05">00149</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree_1_1reverse__iterator.html" title="STL-like mutable reverse iterator object for B+ tree items.">btree_impl::reverse_iterator</a> <a class="code" href="classstx_1_1btree_1_1reverse__iterator.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a>;
<a name="l00150"></a>00150
<a name="l00152"></a><a class="code" href="classstx_1_1btree__set.html#6d0d40380ec160a20ddcabf80935f899">00152</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classstx_1_1btree_1_1const__reverse__iterator.html" title="STL-like read-only reverse iterator object for B+ tree items.">btree_impl::const_reverse_iterator</a> <a class="code" href="classstx_1_1btree_1_1const__reverse__iterator.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a>;
<a name="l00153"></a>00153
<a name="l00154"></a>00154 <span class="keyword">private</span>:
<a name="l00155"></a>00155 <span class="comment">// *** Tree Implementation Object</span>
<a name="l00156"></a>00156
<a name="l00158"></a><a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951">00158</a> <a class="code" href="classstx_1_1btree.html" title="Basic class implementing a base B+ tree data structure in memory.">btree_impl</a> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>;
<a name="l00159"></a>00159
<a name="l00160"></a>00160 <span class="keyword">public</span>:
<a name="l00161"></a>00161 <span class="comment">// *** Constructors and Destructor</span>
<a name="l00162"></a>00162
<a name="l00165"></a><a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e">00165</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e" title="Default constructor initializing an empty B+ tree with the standard key comparison...">btree_set</a>()
<a name="l00166"></a>00166 : <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>()
<a name="l00167"></a>00167 {
<a name="l00168"></a>00168 }
<a name="l00169"></a>00169
<a name="l00172"></a><a class="code" href="classstx_1_1btree__set.html#4cbc4685f8ee72cc147aa1084ae90de8">00172</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e" title="Default constructor initializing an empty B+ tree with the standard key comparison...">btree_set</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#194fe0d02f120a2b49d53a6788191cad" title="Second template parameter: Key comparison function object.">key_compare</a> &kcf)
<a name="l00173"></a>00173 : <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>(kcf)
<a name="l00174"></a>00174 {
<a name="l00175"></a>00175 }
<a name="l00176"></a>00176
<a name="l00178"></a>00178 <span class="keyword">template</span> <<span class="keyword">class</span> InputIterator>
<a name="l00179"></a><a class="code" href="classstx_1_1btree__set.html#71bf764b0118a9ccfd6b20250aa0aac7">00179</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e" title="Default constructor initializing an empty B+ tree with the standard key comparison...">btree_set</a>(InputIterator first, InputIterator last)
<a name="l00180"></a>00180 : <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>()
<a name="l00181"></a>00181 {
<a name="l00182"></a>00182 <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(first, last);
<a name="l00183"></a>00183 }
<a name="l00184"></a>00184
<a name="l00187"></a>00187 <span class="keyword">template</span> <<span class="keyword">class</span> InputIterator>
<a name="l00188"></a><a class="code" href="classstx_1_1btree__set.html#e51563096e959a2099f74e55db6c6520">00188</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e" title="Default constructor initializing an empty B+ tree with the standard key comparison...">btree_set</a>(InputIterator first, InputIterator last, <span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#194fe0d02f120a2b49d53a6788191cad" title="Second template parameter: Key comparison function object.">key_compare</a> &kcf)
<a name="l00189"></a>00189 : <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>(kcf)
<a name="l00190"></a>00190 {
<a name="l00191"></a>00191 <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(first, last);
<a name="l00192"></a>00192 }
<a name="l00193"></a>00193
<a name="l00195"></a><a class="code" href="classstx_1_1btree__set.html#de061369c452ede6f18d4012919ebf39">00195</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#de061369c452ede6f18d4012919ebf39" title="Frees up all used B+ tree memory pages.">~btree_set</a>()
<a name="l00196"></a>00196 {
<a name="l00197"></a>00197 }
<a name="l00198"></a>00198
<a name="l00200"></a><a class="code" href="classstx_1_1btree__set.html#ab1f97a7d71811c5eb8f0dc55fc0b1b8">00200</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#ab1f97a7d71811c5eb8f0dc55fc0b1b8" title="Fast swapping of two identical B+ tree objects.">swap</a>(<span class="keyword">self</span>& from)
<a name="l00201"></a>00201 {
<a name="l00202"></a>00202 std::swap(<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>, from.tree);
<a name="l00203"></a>00203 }
<a name="l00204"></a>00204
<a name="l00205"></a>00205 <span class="keyword">public</span>:
<a name="l00206"></a>00206 <span class="comment">// *** Key and Value Comparison Function Objects</span>
<a name="l00207"></a>00207
<a name="l00209"></a><a class="code" href="classstx_1_1btree__set.html#93466e2999a28011466ce56a0a807083">00209</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#194fe0d02f120a2b49d53a6788191cad" title="Second template parameter: Key comparison function object.">key_compare</a> <a class="code" href="classstx_1_1btree__set.html#93466e2999a28011466ce56a0a807083" title="Constant access to the key comparison object sorting the B+ tree.">key_comp</a>()<span class="keyword"> const</span>
<a name="l00210"></a>00210 <span class="keyword"> </span>{
<a name="l00211"></a>00211 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#43d1c2683f2dc078aa25e49820e9c237" title="Constant access to the key comparison object sorting the B+ tree.">key_comp</a>();
<a name="l00212"></a>00212 }
<a name="l00213"></a>00213
<a name="l00216"></a><a class="code" href="classstx_1_1btree__set.html#a2d20f3b698f2017e580792b87e0f3a4">00216</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1value__compare.html" title="Function class to compare value_type objects. Required by the STL.">value_compare</a> <a class="code" href="classstx_1_1btree__set.html#a2d20f3b698f2017e580792b87e0f3a4" title="Constant access to a constructed value_type comparison object.">value_comp</a>()<span class="keyword"> const</span>
<a name="l00217"></a>00217 <span class="keyword"> </span>{
<a name="l00218"></a>00218 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#94273af1fe4b9e2e0c0b6daeaa5f5950" title="Constant access to a constructed value_type comparison object.">value_comp</a>();
<a name="l00219"></a>00219 }
<a name="l00220"></a>00220
<a name="l00221"></a>00221 <span class="keyword">public</span>:
<a name="l00222"></a>00222 <span class="comment">// *** Fast Destruction of the B+ Tree</span>
<a name="l00223"></a>00223
<a name="l00225"></a><a class="code" href="classstx_1_1btree__set.html#bab3a966a2d26cd83777d45b67b4ec3f">00225</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#bab3a966a2d26cd83777d45b67b4ec3f" title="Frees all keys and all nodes of the tree.">clear</a>()
<a name="l00226"></a>00226 {
<a name="l00227"></a>00227 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#cf6ccb1acc05ef2845dfa97c81b1be9f" title="Frees all key/data pairs and all nodes of the tree.">clear</a>();
<a name="l00228"></a>00228 }
<a name="l00229"></a>00229
<a name="l00230"></a>00230 <span class="keyword">public</span>:
<a name="l00231"></a>00231 <span class="comment">// *** STL Iterator Construction Functions</span>
<a name="l00232"></a>00232
<a name="l00235"></a><a class="code" href="classstx_1_1btree__set.html#536f8fa8442d0f664447de0518c60041">00235</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#536f8fa8442d0f664447de0518c60041" title="Constructs a read/data-write iterator that points to the first slot in the first...">begin</a>()
<a name="l00236"></a>00236 {
<a name="l00237"></a>00237 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#6551b60cb8a2f717555ceac61f34b957" title="Constructs a read/data-write iterator that points to the first slot in the first...">begin</a>();
<a name="l00238"></a>00238 }
<a name="l00239"></a>00239
<a name="l00242"></a><a class="code" href="classstx_1_1btree__set.html#13feaae3a8bf995dee827c12b30b4bf7">00242</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#13feaae3a8bf995dee827c12b30b4bf7" title="Constructs a read/data-write iterator that points to the first invalid slot in the...">end</a>()
<a name="l00243"></a>00243 {
<a name="l00244"></a>00244 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#14f8bf63680c8950aab8c5d54e580a14" title="Constructs a read/data-write iterator that points to the first invalid slot in the...">end</a>();
<a name="l00245"></a>00245 }
<a name="l00246"></a>00246
<a name="l00249"></a><a class="code" href="classstx_1_1btree__set.html#2e1b042c615f436a2ece31e3175f1218">00249</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <a class="code" href="classstx_1_1btree__set.html#536f8fa8442d0f664447de0518c60041" title="Constructs a read/data-write iterator that points to the first slot in the first...">begin</a>()<span class="keyword"> const</span>
<a name="l00250"></a>00250 <span class="keyword"> </span>{
<a name="l00251"></a>00251 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#6551b60cb8a2f717555ceac61f34b957" title="Constructs a read/data-write iterator that points to the first slot in the first...">begin</a>();
<a name="l00252"></a>00252 }
<a name="l00253"></a>00253
<a name="l00256"></a><a class="code" href="classstx_1_1btree__set.html#55c93868b956919ff8d9ef051ac74b74">00256</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <a class="code" href="classstx_1_1btree__set.html#13feaae3a8bf995dee827c12b30b4bf7" title="Constructs a read/data-write iterator that points to the first invalid slot in the...">end</a>()<span class="keyword"> const</span>
<a name="l00257"></a>00257 <span class="keyword"> </span>{
<a name="l00258"></a>00258 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#14f8bf63680c8950aab8c5d54e580a14" title="Constructs a read/data-write iterator that points to the first invalid slot in the...">end</a>();
<a name="l00259"></a>00259 }
<a name="l00260"></a>00260
<a name="l00263"></a><a class="code" href="classstx_1_1btree__set.html#9268f3d41b5891e0286e8f91dc47cb8d">00263</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1reverse__iterator.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a> <a class="code" href="classstx_1_1btree__set.html#9268f3d41b5891e0286e8f91dc47cb8d" title="Constructs a read/data-write reverse iterator that points to the first invalid slot...">rbegin</a>()
<a name="l00264"></a>00264 {
<a name="l00265"></a>00265 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#4d3a4b24d8cc56c589800655cf83c806" title="Constructs a read/data-write reverse iterator that points to the first invalid slot...">rbegin</a>();
<a name="l00266"></a>00266 }
<a name="l00267"></a>00267
<a name="l00270"></a><a class="code" href="classstx_1_1btree__set.html#f3ee6d465463b801fb2f5a69715033b1">00270</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1reverse__iterator.html" title="STL-like mutable reverse iterator object for B+ tree items.">reverse_iterator</a> <a class="code" href="classstx_1_1btree__set.html#f3ee6d465463b801fb2f5a69715033b1" title="Constructs a read/data-write reverse iterator that points to the first slot in the...">rend</a>()
<a name="l00271"></a>00271 {
<a name="l00272"></a>00272 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#6d9e5a5b0ec598a76e602aa6a19900ff" title="Constructs a read/data-write reverse iterator that points to the first slot in the...">rend</a>();
<a name="l00273"></a>00273 }
<a name="l00274"></a>00274
<a name="l00277"></a><a class="code" href="classstx_1_1btree__set.html#62ece7640ddc04133eea04d3755d9dd1">00277</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1const__reverse__iterator.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a> <a class="code" href="classstx_1_1btree__set.html#9268f3d41b5891e0286e8f91dc47cb8d" title="Constructs a read/data-write reverse iterator that points to the first invalid slot...">rbegin</a>()<span class="keyword"> const</span>
<a name="l00278"></a>00278 <span class="keyword"> </span>{
<a name="l00279"></a>00279 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#4d3a4b24d8cc56c589800655cf83c806" title="Constructs a read/data-write reverse iterator that points to the first invalid slot...">rbegin</a>();
<a name="l00280"></a>00280 }
<a name="l00281"></a>00281
<a name="l00284"></a><a class="code" href="classstx_1_1btree__set.html#ed2af689eeed71485d8f031d8e96c7fc">00284</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1const__reverse__iterator.html" title="STL-like read-only reverse iterator object for B+ tree items.">const_reverse_iterator</a> <a class="code" href="classstx_1_1btree__set.html#f3ee6d465463b801fb2f5a69715033b1" title="Constructs a read/data-write reverse iterator that points to the first slot in the...">rend</a>()<span class="keyword"> const</span>
<a name="l00285"></a>00285 <span class="keyword"> </span>{
<a name="l00286"></a>00286 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#6d9e5a5b0ec598a76e602aa6a19900ff" title="Constructs a read/data-write reverse iterator that points to the first slot in the...">rend</a>();
<a name="l00287"></a>00287 }
<a name="l00288"></a>00288
<a name="l00289"></a>00289 <span class="keyword">public</span>:
<a name="l00290"></a>00290 <span class="comment">// *** Access Functions to the Item Count</span>
<a name="l00291"></a>00291
<a name="l00293"></a><a class="code" href="classstx_1_1btree__set.html#76b2b68ccf5c2b6b49731eb6278d1b68">00293</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa" title="Size type used to count keys.">size_type</a> <a class="code" href="classstx_1_1btree__set.html#76b2b68ccf5c2b6b49731eb6278d1b68" title="Return the number of keys in the B+ tree.">size</a>()<span class="keyword"> const</span>
<a name="l00294"></a>00294 <span class="keyword"> </span>{
<a name="l00295"></a>00295 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#5e32032d192795a5f25b49e23e3ef1a1" title="Return the number of key/data pairs in the B+ tree.">size</a>();
<a name="l00296"></a>00296 }
<a name="l00297"></a>00297
<a name="l00299"></a><a class="code" href="classstx_1_1btree__set.html#8354d3dead85ff276bb077af9eb427c6">00299</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#8354d3dead85ff276bb077af9eb427c6" title="Returns true if there is at least one key in the B+ tree.">empty</a>()<span class="keyword"> const</span>
<a name="l00300"></a>00300 <span class="keyword"> </span>{
<a name="l00301"></a>00301 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#ee6ae1b8d5832d3cd829a3962b776cd5" title="Returns true if there is at least one key/data pair in the B+ tree.">empty</a>();
<a name="l00302"></a>00302 }
<a name="l00303"></a>00303
<a name="l00306"></a><a class="code" href="classstx_1_1btree__set.html#1a4c6cd6f34e042077d0b8cc94cfacc3">00306</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa" title="Size type used to count keys.">size_type</a> <a class="code" href="classstx_1_1btree__set.html#1a4c6cd6f34e042077d0b8cc94cfacc3" title="Returns the largest possible size of the B+ Tree.">max_size</a>()<span class="keyword"> const</span>
<a name="l00307"></a>00307 <span class="keyword"> </span>{
<a name="l00308"></a>00308 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#ae330348c9f4b6051864da4ebd157662" title="Returns the largest possible size of the B+ Tree.">max_size</a>();
<a name="l00309"></a>00309 }
<a name="l00310"></a>00310
<a name="l00312"></a><a class="code" href="classstx_1_1btree__set.html#839619b04dcab0265b7ef37feff1603e">00312</a> <span class="keyword">inline</span> <span class="keyword">const</span> <a class="code" href="structstx_1_1btree_1_1tree__stats.html" title="A small struct containing basic statistics about the B+ tree.">tree_stats</a>& <a class="code" href="classstx_1_1btree__set.html#839619b04dcab0265b7ef37feff1603e" title="Return a const reference to the current statistics.">get_stats</a>()<span class="keyword"> const</span>
<a name="l00313"></a>00313 <span class="keyword"> </span>{
<a name="l00314"></a>00314 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#8748bb3788c1e1d65dbfe9500d33a134" title="Return a const reference to the current statistics.">get_stats</a>();
<a name="l00315"></a>00315 }
<a name="l00316"></a>00316
<a name="l00317"></a>00317 <span class="keyword">public</span>:
<a name="l00318"></a>00318 <span class="comment">// *** Standard Access Functions Querying the Tree by Descending to a Leaf</span>
<a name="l00319"></a>00319
<a name="l00322"></a><a class="code" href="classstx_1_1btree__set.html#e586763f864de1de158f83456171419f">00322</a> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#e586763f864de1de158f83456171419f" title="Non-STL function checking whether a key is in the B+ tree.">exists</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)<span class="keyword"> const</span>
<a name="l00323"></a>00323 <span class="keyword"> </span>{
<a name="l00324"></a>00324 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#9405c7a274bcc76f27b4e84c49fcaa0d" title="Non-STL function checking whether a key is in the B+ tree.">exists</a>(key);
<a name="l00325"></a>00325 }
<a name="l00326"></a>00326
<a name="l00329"></a><a class="code" href="classstx_1_1btree__set.html#9ea2f19fd2c94746ed2d370a184c9c89">00329</a> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#9ea2f19fd2c94746ed2d370a184c9c89" title="Tries to locate a key in the B+ tree and returns an iterator to the key slot if found...">find</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)
<a name="l00330"></a>00330 {
<a name="l00331"></a>00331 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#2be7e3a978a71f86e433a0244c7414c6" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot...">find</a>(key);
<a name="l00332"></a>00332 }
<a name="l00333"></a>00333
<a name="l00336"></a><a class="code" href="classstx_1_1btree__set.html#084877c736d87902fd16a59fa64f1c2f">00336</a> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <a class="code" href="classstx_1_1btree__set.html#9ea2f19fd2c94746ed2d370a184c9c89" title="Tries to locate a key in the B+ tree and returns an iterator to the key slot if found...">find</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)<span class="keyword"> const</span>
<a name="l00337"></a>00337 <span class="keyword"> </span>{
<a name="l00338"></a>00338 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#2be7e3a978a71f86e433a0244c7414c6" title="Tries to locate a key in the B+ tree and returns an iterator to the key/data slot...">find</a>(key);
<a name="l00339"></a>00339 }
<a name="l00340"></a>00340
<a name="l00344"></a><a class="code" href="classstx_1_1btree__set.html#c22ac79184b385d5239a0295c6022990">00344</a> <a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa" title="Size type used to count keys.">size_type</a> <a class="code" href="classstx_1_1btree__set.html#c22ac79184b385d5239a0295c6022990" title="Tries to locate a key in the B+ tree and returns the number of identical key entries...">count</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)<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="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#36754fc4a90de86806a91cc22eafbe78" title="Tries to locate a key in the B+ tree and returns the number of identical key entries...">count</a>(key);
<a name="l00347"></a>00347 }
<a name="l00348"></a>00348
<a name="l00351"></a><a class="code" href="classstx_1_1btree__set.html#7c0b80e2afa450a956f5b08fc6292e05">00351</a> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#7c0b80e2afa450a956f5b08fc6292e05" title="Searches the B+ tree and returns an iterator to the first key less or equal to the...">lower_bound</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)
<a name="l00352"></a>00352 {
<a name="l00353"></a>00353 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#74e859adf01a516a382579a614f12673" title="Searches the B+ tree and returns an iterator to the first key less or equal to the...">lower_bound</a>(key);
<a name="l00354"></a>00354 }
<a name="l00355"></a>00355
<a name="l00358"></a><a class="code" href="classstx_1_1btree__set.html#b65b12b6497c9498ebd1e9f0100b1c36">00358</a> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <a class="code" href="classstx_1_1btree__set.html#7c0b80e2afa450a956f5b08fc6292e05" title="Searches the B+ tree and returns an iterator to the first key less or equal to the...">lower_bound</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)<span class="keyword"> const</span>
<a name="l00359"></a>00359 <span class="keyword"> </span>{
<a name="l00360"></a>00360 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#74e859adf01a516a382579a614f12673" title="Searches the B+ tree and returns an iterator to the first key less or equal to the...">lower_bound</a>(key);
<a name="l00361"></a>00361 }
<a name="l00362"></a>00362
<a name="l00365"></a><a class="code" href="classstx_1_1btree__set.html#532bd789241075b67f45c9866d4f62c7">00365</a> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#532bd789241075b67f45c9866d4f62c7" title="Searches the B+ tree and returns an iterator to the first key greater than the parameter...">upper_bound</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)
<a name="l00366"></a>00366 {
<a name="l00367"></a>00367 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#789cbe4a94251e756041c5504127ac50" title="Searches the B+ tree and returns an iterator to the first key greater than the parameter...">upper_bound</a>(key);
<a name="l00368"></a>00368 }
<a name="l00369"></a>00369
<a name="l00372"></a><a class="code" href="classstx_1_1btree__set.html#21a46286c0bdb3f9450e70a6df86bd72">00372</a> <a class="code" href="classstx_1_1btree_1_1const__iterator.html" title="STL-like read-only iterator object for B+ tree items.">const_iterator</a> <a class="code" href="classstx_1_1btree__set.html#532bd789241075b67f45c9866d4f62c7" title="Searches the B+ tree and returns an iterator to the first key greater than the parameter...">upper_bound</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)<span class="keyword"> const</span>
<a name="l00373"></a>00373 <span class="keyword"> </span>{
<a name="l00374"></a>00374 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#789cbe4a94251e756041c5504127ac50" title="Searches the B+ tree and returns an iterator to the first key greater than the parameter...">upper_bound</a>(key);
<a name="l00375"></a>00375 }
<a name="l00376"></a>00376
<a name="l00378"></a><a class="code" href="classstx_1_1btree__set.html#9bf38ca1f5676d20740e25e9bc2983f3">00378</a> <span class="keyword">inline</span> std::pair<iterator, iterator> <a class="code" href="classstx_1_1btree__set.html#9bf38ca1f5676d20740e25e9bc2983f3" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)
<a name="l00379"></a>00379 {
<a name="l00380"></a>00380 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#598ffaab5e27bf4e10de0f757938744c" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(key);
<a name="l00381"></a>00381 }
<a name="l00382"></a>00382
<a name="l00384"></a><a class="code" href="classstx_1_1btree__set.html#2dcdc87563e21efca3f12ed776eb01b9">00384</a> <span class="keyword">inline</span> std::pair<const_iterator, const_iterator> <a class="code" href="classstx_1_1btree__set.html#9bf38ca1f5676d20740e25e9bc2983f3" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& key)<span class="keyword"> const</span>
<a name="l00385"></a>00385 <span class="keyword"> </span>{
<a name="l00386"></a>00386 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#598ffaab5e27bf4e10de0f757938744c" title="Searches the B+ tree and returns both lower_bound() and upper_bound().">equal_range</a>(key);
<a name="l00387"></a>00387 }
<a name="l00388"></a>00388
<a name="l00389"></a>00389 <span class="keyword">public</span>:
<a name="l00390"></a>00390 <span class="comment">// *** B+ Tree Object Comparison Functions</span>
<a name="l00391"></a>00391
<a name="l00394"></a><a class="code" href="classstx_1_1btree__set.html#7a5adcbc988892065c4ab8b3259fbeeb">00394</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#7a5adcbc988892065c4ab8b3259fbeeb" title="Equality relation of B+ trees of the same type.">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00395"></a>00395 <span class="keyword"> </span>{
<a name="l00396"></a>00396 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> == other.tree);
<a name="l00397"></a>00397 }
<a name="l00398"></a>00398
<a name="l00400"></a><a class="code" href="classstx_1_1btree__set.html#63e3a4b184129cab73c9df4235dee617">00400</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#63e3a4b184129cab73c9df4235dee617" title="Inequality relation. Based on operator==.">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00401"></a>00401 <span class="keyword"> </span>{
<a name="l00402"></a>00402 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> != other.tree);
<a name="l00403"></a>00403 }
<a name="l00404"></a>00404
<a name="l00407"></a><a class="code" href="classstx_1_1btree__set.html#c7f0c3c52efe5858ce1c704d775a9f57">00407</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#c7f0c3c52efe5858ce1c704d775a9f57" title="Total ordering relation of B+ trees of the same type.">operator<</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00408"></a>00408 <span class="keyword"> </span>{
<a name="l00409"></a>00409 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> < other.tree);
<a name="l00410"></a>00410 }
<a name="l00411"></a>00411
<a name="l00413"></a><a class="code" href="classstx_1_1btree__set.html#3bd1a49228960088f2b196c3319e2383">00413</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#3bd1a49228960088f2b196c3319e2383" title="Greater relation. Based on operator&lt;.">operator></a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00414"></a>00414 <span class="keyword"> </span>{
<a name="l00415"></a>00415 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> > other.tree);
<a name="l00416"></a>00416 }
<a name="l00417"></a>00417
<a name="l00419"></a><a class="code" href="classstx_1_1btree__set.html#a61a0fa7d6132bf772a2a97f612effed">00419</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#a61a0fa7d6132bf772a2a97f612effed" title="Less-equal relation. Based on operator&lt;.">operator<=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00420"></a>00420 <span class="keyword"> </span>{
<a name="l00421"></a>00421 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> <= other.tree);
<a name="l00422"></a>00422 }
<a name="l00423"></a>00423
<a name="l00425"></a><a class="code" href="classstx_1_1btree__set.html#a4c446d3b22e86d7169bcccea185849e">00425</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#a4c446d3b22e86d7169bcccea185849e" title="Greater-equal relation. Based on operator&lt;.">operator>=</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)<span class="keyword"> const</span>
<a name="l00426"></a>00426 <span class="keyword"> </span>{
<a name="l00427"></a>00427 <span class="keywordflow">return</span> (<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> >= other.tree);
<a name="l00428"></a>00428 }
<a name="l00429"></a>00429
<a name="l00430"></a>00430 <span class="keyword">public</span>:
<a name="l00432"></a>00432
<a name="l00434"></a><a class="code" href="classstx_1_1btree__set.html#23590115c49db234c3bbf274260a4249">00434</a> <span class="keyword">inline</span> <span class="keyword">self</span>& <a class="code" href="classstx_1_1btree__set.html#23590115c49db234c3bbf274260a4249" title="*** Fast Copy: Assign Operator and Copy Constructors">operator= </a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)
<a name="l00435"></a>00435 {
<a name="l00436"></a>00436 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &other)
<a name="l00437"></a>00437 {
<a name="l00438"></a>00438 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a> = other.tree;
<a name="l00439"></a>00439 }
<a name="l00440"></a>00440 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00441"></a>00441 }
<a name="l00442"></a>00442
<a name="l00445"></a><a class="code" href="classstx_1_1btree__set.html#a4c84be7d7671d9275f6662b5d156861">00445</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree__set.html#cab87faa1f497148d145297082edc62e" title="Default constructor initializing an empty B+ tree with the standard key comparison...">btree_set</a>(<span class="keyword">const</span> <span class="keyword">self</span> &other)
<a name="l00446"></a>00446 : <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>(other.<a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>)
<a name="l00447"></a>00447 {
<a name="l00448"></a>00448 }
<a name="l00449"></a>00449
<a name="l00450"></a>00450 <span class="keyword">public</span>:
<a name="l00451"></a>00451 <span class="comment">// *** Public Insertion Functions</span>
<a name="l00452"></a>00452
<a name="l00455"></a><a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e">00455</a> <span class="keyword">inline</span> std::pair<iterator, bool> <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a>& x)
<a name="l00456"></a>00456 {
<a name="l00457"></a>00457 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#45d95a83fbbfa0211a972b8f7451a19c" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(x, <a class="code" href="classstx_1_1btree__set.html#ba90fcc1bc06eef41130790b8e9a1cde" title="The empty data_type.">data_type</a>());
<a name="l00458"></a>00458 }
<a name="l00459"></a>00459
<a name="l00462"></a><a class="code" href="classstx_1_1btree__set.html#e453b064ec05bd1bdfcb7cce0a24392e">00462</a> <span class="keyword">inline</span> <a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(<a class="code" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> hint, <span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &x)
<a name="l00463"></a>00463 {
<a name="l00464"></a>00464 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#45d95a83fbbfa0211a972b8f7451a19c" title="Attempt to insert a key/data pair into the B+ tree.">insert2</a>(hint, x, <a class="code" href="classstx_1_1btree__set.html#ba90fcc1bc06eef41130790b8e9a1cde" title="The empty data_type.">data_type</a>());
<a name="l00465"></a>00465 }
<a name="l00466"></a>00466
<a name="l00469"></a>00469 <span class="keyword">template</span> <<span class="keyword">typename</span> InputIterator>
<a name="l00470"></a><a class="code" href="classstx_1_1btree__set.html#133f72e15bc39a9477a2a6f244758796">00470</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(InputIterator first, InputIterator last)
<a name="l00471"></a>00471 {
<a name="l00472"></a>00472 InputIterator iter = first;
<a name="l00473"></a>00473 <span class="keywordflow">while</span>(iter != last)
<a name="l00474"></a>00474 {
<a name="l00475"></a>00475 <a class="code" href="classstx_1_1btree__set.html#b8aba3bf358d01b5a97e56276b13826e" title="Attempt to insert a key into the B+ tree.">insert</a>(*iter);
<a name="l00476"></a>00476 ++iter;
<a name="l00477"></a>00477 }
<a name="l00478"></a>00478 }
<a name="l00479"></a>00479
<a name="l00480"></a>00480 <span class="keyword">public</span>:
<a name="l00481"></a>00481 <span class="comment">// *** Public Erase Functions</span>
<a name="l00482"></a>00482
<a name="l00485"></a><a class="code" href="classstx_1_1btree__set.html#c94f639718ce957263bacc2f69db9dee">00485</a> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#c94f639718ce957263bacc2f69db9dee" title="Erases the key from the set.">erase_one</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)
<a name="l00486"></a>00486 {
<a name="l00487"></a>00487 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#c01d4b6b26e5c8447e92651168b006d4" title="Erases one (the first) of the key/data pairs associated with the given key.">erase_one</a>(key);
<a name="l00488"></a>00488 }
<a name="l00489"></a>00489
<a name="l00491"></a><a class="code" href="classstx_1_1btree__set.html#fc1e821040345e46a60daeae0d598f88">00491</a> <a class="code" href="classstx_1_1btree__set.html#85e1b660ae997807864b066cf8b4c7fa" title="Size type used to count keys.">size_type</a> <a class="code" href="classstx_1_1btree__set.html#fc1e821040345e46a60daeae0d598f88" title="Erases all the key/data pairs associated with the given key.">erase</a>(<span class="keyword">const</span> <a class="code" href="classstx_1_1btree__set.html#509db03a02c4649b0f718162673fa20c" title="First template parameter: The key type of the B+ tree.">key_type</a> &key)
<a name="l00492"></a>00492 {
<a name="l00493"></a>00493 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#97f6c7874f508e5d1498161a0181606e" title="Erases all the key/data pairs associated with the given key.">erase</a>(key);
<a name="l00494"></a>00494 }
<a name="l00495"></a>00495
<a name="l00496"></a>00496 <span class="preprocessor">#ifdef BTREE_TODO</span>
<a name="l00498"></a><a class="code" href="classstx_1_1btree__set.html#959b822dc08b8a3e20ddaf142f4b1804">00498</a> <span class="preprocessor"> void erase(iterator iter)</span>
<a name="l00499"></a>00499 <span class="preprocessor"></span> {
<a name="l00500"></a>00500
<a name="l00501"></a>00501 }
<a name="l00502"></a>00502 <span class="preprocessor">#endif</span>
<a name="l00503"></a>00503 <span class="preprocessor"></span>
<a name="l00504"></a>00504 <span class="preprocessor">#ifdef BTREE_TODO</span>
<a name="l00507"></a><a class="code" href="classstx_1_1btree__set.html#540aeddb33fa1cc5cbf6ce5692232050">00507</a> <span class="preprocessor"> void erase(iterator </span><span class="comment">/* first */</span>, iterator <span class="comment">/* last */</span>)
<a name="l00508"></a>00508 {
<a name="l00509"></a>00509 abort();
<a name="l00510"></a>00510 }
<a name="l00511"></a>00511 <span class="preprocessor">#endif</span>
<a name="l00512"></a>00512 <span class="preprocessor"></span>
<a name="l00513"></a>00513 <span class="preprocessor">#ifdef BTREE_DEBUG</span>
<a name="l00514"></a>00514 <span class="preprocessor"></span><span class="keyword">public</span>:
<a name="l00515"></a>00515 <span class="comment">// *** Debug Printing</span>
<a name="l00516"></a>00516
<a name="l00520"></a><a class="code" href="classstx_1_1btree__set.html#e432364dd6dc37053e73ba5a614756db">00520</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#e432364dd6dc37053e73ba5a614756db" title="Print out the B+ tree structure with keys onto the given ostream.">print</a>(std::ostream &os)<span class="keyword"> const</span>
<a name="l00521"></a>00521 <span class="keyword"> </span>{
<a name="l00522"></a>00522 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#97664fdfb85917808eee2aa8487c5e39" title="Print out the B+ tree structure with keys onto the given ostream.">print</a>(os);
<a name="l00523"></a>00523 }
<a name="l00524"></a>00524
<a name="l00526"></a><a class="code" href="classstx_1_1btree__set.html#fcca0d9bd3cbe770a87c0b679b143cd5">00526</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#fcca0d9bd3cbe770a87c0b679b143cd5" title="Print out only the leaves via the double linked list.">print_leaves</a>(std::ostream &os)<span class="keyword"> const</span>
<a name="l00527"></a>00527 <span class="keyword"> </span>{
<a name="l00528"></a>00528 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#8270dcc972930a6f2c9f112af8b65075" title="Print out only the leaves via the double linked list.">print_leaves</a>(os);
<a name="l00529"></a>00529 }
<a name="l00530"></a>00530
<a name="l00531"></a>00531 <span class="preprocessor">#endif</span>
<a name="l00532"></a>00532 <span class="preprocessor"></span>
<a name="l00533"></a>00533 <span class="keyword">public</span>:
<a name="l00534"></a>00534 <span class="comment">// *** Verification of B+ Tree Invariants</span>
<a name="l00535"></a>00535
<a name="l00538"></a><a class="code" href="classstx_1_1btree__set.html#8d6f812e88b5801a743ac39cdd7cc955">00538</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#8d6f812e88b5801a743ac39cdd7cc955" title="Run a thorough verification of all B+ tree invariants.">verify</a>()<span class="keyword"> const</span>
<a name="l00539"></a>00539 <span class="keyword"> </span>{
<a name="l00540"></a>00540 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#e382217f25916442745eb83520b20c12" title="Run a thorough verification of all B+ tree invariants.">verify</a>();
<a name="l00541"></a>00541 }
<a name="l00542"></a>00542
<a name="l00543"></a>00543 <span class="keyword">public</span>:
<a name="l00544"></a>00544
<a name="l00549"></a><a class="code" href="classstx_1_1btree__set.html#8c2e34ae16d8c7865c269ff0e79f9353">00549</a> <span class="keywordtype">void</span> <a class="code" href="classstx_1_1btree__set.html#8c2e34ae16d8c7865c269ff0e79f9353" title="Dump the contents of the B+ tree out onto an ostream as a binary image.">dump</a>(std::ostream &os)<span class="keyword"> const</span>
<a name="l00550"></a>00550 <span class="keyword"> </span>{
<a name="l00551"></a>00551 <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#4d83f35e94a64b82ca3648d40fb31507" title="Dump the contents of the B+ tree out onto an ostream as a binary image.">dump</a>(os);
<a name="l00552"></a>00552 }
<a name="l00553"></a>00553
<a name="l00558"></a><a class="code" href="classstx_1_1btree__set.html#723f25c9b0522c05b621afe3313f1b1f">00558</a> <span class="keywordtype">bool</span> <a class="code" href="classstx_1_1btree__set.html#723f25c9b0522c05b621afe3313f1b1f" title="Restore a binary image of a dumped B+ tree from an istream.">restore</a>(std::istream &is)
<a name="l00559"></a>00559 {
<a name="l00560"></a>00560 <span class="keywordflow">return</span> <a class="code" href="classstx_1_1btree__set.html#66e4971de8926f226c1c1e9fed74f951" title="The contained implementation object.">tree</a>.<a class="code" href="classstx_1_1btree.html#f386da3ca44e31b73f68b50630df3ab9" title="Restore a binary image of a dumped B+ tree from an istream.">restore</a>(is);
<a name="l00561"></a>00561 }
<a name="l00562"></a>00562 };
<a name="l00563"></a>00563
<a name="l00564"></a>00564 } <span class="comment">// namespace stx</span>
<a name="l00565"></a>00565
<a name="l00566"></a>00566 <span class="preprocessor">#endif // _STX_BTREE_SET_H_</span>
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Sun Sep 7 17:32:39 2008 for STX B+ Tree Template Classes by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.6 </small></address>
</body>
</html>
