<!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.h File Reference</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>
</div>
<div class="contents">
<h1>stx/btree.h File Reference</h1>Contains the main B+ tree implementation template class btree. <a href="#_details">More...</a>
<p>
<code>#include <algorithm></code><br>
<code>#include <functional></code><br>
<code>#include <istream></code><br>
<code>#include <ostream></code><br>
<code>#include <assert.h></code><br>
<code>#include <iostream></code><br>
<p>
<a href="btree_8h-source.html">Go to the source code of this file.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Namespaces</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">namespace </td><td class="memItemRight" valign="bottom"><a class="el" href="namespacestx.html">stx</a></td></tr>
<tr><td colspan="2"><br><h2>Classes</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree__default__set__traits.html">stx::btree_default_set_traits< _Key ></a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Generates default traits for a B+ tree used as a set. <a href="structstx_1_1btree__default__set__traits.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree__default__map__traits.html">stx::btree_default_map_traits< _Key, _Data ></a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Generates default traits for a B+ tree used as a map. <a href="structstx_1_1btree__default__map__traits.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates ></a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Basic class implementing a base B+ tree data structure in memory. <a href="classstx_1_1btree.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree_1_1node.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">The header structure of each <a class="el" href="structstx_1_1btree_1_1node.html" title="The header structure of each node in-memory.">node</a> in-memory. <a href="structstx_1_1btree_1_1node.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree_1_1inner__node.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::inner_node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Extended structure of a inner <a class="el" href="structstx_1_1btree_1_1node.html" title="The header structure of each node in-memory.">node</a> in-memory. <a href="structstx_1_1btree_1_1inner__node.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree_1_1leaf__node.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leaf_node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Extended structure of a leaf <a class="el" href="structstx_1_1btree_1_1node.html" title="The header structure of each node in-memory.">node</a> in memory. <a href="structstx_1_1btree_1_1leaf__node.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><b>stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree_pair_to_value< value_type, pair_type ></b></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><b>stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree_pair_to_value< value_type, value_type ></b></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree_1_1iterator.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::iterator</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">STL-like <a class="el" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> object for B+ tree items. <a href="classstx_1_1btree_1_1iterator.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree_1_1const__iterator.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_iterator</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">STL-like read-only <a class="el" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> object for B+ tree items. <a href="classstx_1_1btree_1_1const__iterator.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree_1_1reverse__iterator.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">STL-like mutable reverse <a class="el" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> object for B+ tree items. <a href="classstx_1_1btree_1_1reverse__iterator.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree_1_1const__reverse__iterator.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">STL-like read-only reverse <a class="el" href="classstx_1_1btree_1_1iterator.html" title="STL-like iterator object for B+ tree items.">iterator</a> object for B+ tree items. <a href="classstx_1_1btree_1_1const__reverse__iterator.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><a class="el" href="structstx_1_1btree_1_1tree__stats.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">A small struct containing basic statistics about the B+ tree. <a href="structstx_1_1btree_1_1tree__stats.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="classstx_1_1btree_1_1value__compare.html">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_compare</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Function class to compare value_type objects. Required by the STL. <a href="classstx_1_1btree_1_1value__compare.html#_details">More...</a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><b>stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::result_t</b></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">struct </td><td class="memItemRight" valign="bottom"><b>stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::dump_header</b></td></tr>
<tr><td colspan="2"><br><h2>Defines</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="btree_8h.html#cd87b40df0c1d4ead6fac13b49cb5345">BTREE_PRINT</a>(x) do { if (debug) (std::cout << x); } while(0)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Print out debug information to std::cout if BTREE_DEBUG is defined. <a href="#cd87b40df0c1d4ead6fac13b49cb5345"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="btree_8h.html#6ac57b9b59dae34aea28cda65b0d14bb">BTREE_ASSERT</a>(x) do { assert(x); } while(0)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Assertion only if BTREE_DEBUG is defined. This is not used in verify(). <a href="#6ac57b9b59dae34aea28cda65b0d14bb"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="btree_8h.html#5d7b0c98bc4c3029d6d76199caa35b19">BTREE_MAX</a>(a, b) ((a) < (b) ? (b) : (a))</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">The maximum of a and b. Used in some compile-time formulas. <a href="#5d7b0c98bc4c3029d6d76199caa35b19"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">#define </td><td class="memItemRight" valign="bottom"><a class="el" href="btree_8h.html#ec07a93b351ce398f789007a441a4320">BTREE_FRIENDS</a> friend class btree_friend;</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals. <a href="#ec07a93b351ce398f789007a441a4320"></a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
Contains the main B+ tree implementation template class btree.
<p>
<p>Definition in file <a class="el" href="btree_8h-source.html">btree.h</a>.</p>
<hr><h2>Define Documentation</h2>
<a class="anchor" name="6ac57b9b59dae34aea28cda65b0d14bb"></a><!-- doxytag: member="btree.h::BTREE_ASSERT" ref="6ac57b9b59dae34aea28cda65b0d14bb" args="(x)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define BTREE_ASSERT </td>
<td>(</td>
<td class="paramtype">x </td>
<td class="paramname"> </td>
<td> ) </td>
<td> do { assert(x); } while(0)</td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Assertion only if BTREE_DEBUG is defined. This is not used in verify().
<p>
<p>Definition at line <a class="el" href="btree_8h-source.html#l00046">46</a> of file <a class="el" href="btree_8h-source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="btree_8h-source.html#l01397">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear()</a>, <a class="el" href="btree_8h-source.html#l01083">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::data()</a>, <a class="el" href="btree_8h-source.html#l00875">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::data()</a>, <a class="el" href="btree_8h-source.html#l02400">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend()</a>, <a class="el" href="btree_8h-source.html#l01505">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_lower()</a>, <a class="el" href="btree_8h-source.html#l01552">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_upper()</a>, <a class="el" href="btree_8h-source.html#l02054">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_descend()</a>, <a class="el" href="btree_8h-source.html#l02008">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_start()</a>, <a class="el" href="btree_8h-source.html#l01076">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::key()</a>, <a class="el" href="btree_8h-source.html#l00868">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::key()</a>, <a class="el" href="btree_8h-source.html#l02708">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_inner()</a>, <a class="el" href="btree_8h-source.html#l02677">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_leaves()</a>, <a class="el" href="btree_8h-source.html#l01056">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::operator*()</a>, <a class="el" href="btree_8h-source.html#l00848">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::operator*()</a>, <a class="el" href="btree_8h-source.html#l01067">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator::operator->()</a>, <a class="el" href="btree_8h-source.html#l00859">stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator::operator->()</a>, <a class="el" href="btree_8h-source.html#l03351">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore_node()</a>, <a class="el" href="btree_8h-source.html#l02802">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_inner()</a>, <a class="el" href="btree_8h-source.html#l02755">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_leaf()</a>, <a class="el" href="btree_8h-source.html#l02916">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_inner()</a>, <a class="el" href="btree_8h-source.html#l02862">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_leaf()</a>, <a class="el" href="btree_8h-source.html#l02234">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_inner_node()</a>, and <a class="el" href="btree_8h-source.html#l02194">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_leaf_node()</a>.</p>
</div>
</div><p>
<a class="anchor" name="ec07a93b351ce398f789007a441a4320"></a><!-- doxytag: member="btree.h::BTREE_FRIENDS" ref="ec07a93b351ce398f789007a441a4320" args="" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define BTREE_FRIENDS friend class btree_friend; </td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
<p>
This was added for wxBTreeDemo to be able to draw the tree.
<p>Definition at line <a class="el" href="btree_8h-source.html#l00065">65</a> of file <a class="el" href="btree_8h-source.html">btree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="5d7b0c98bc4c3029d6d76199caa35b19"></a><!-- doxytag: member="btree.h::BTREE_MAX" ref="5d7b0c98bc4c3029d6d76199caa35b19" args="(a, b)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define BTREE_MAX </td>
<td>(</td>
<td class="paramtype">a, <tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">b </td>
<td class="paramname"> </td>
<td> ) </td>
<td> ((a) < (b) ? (b) : (a))</td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
The maximum of a and b. Used in some compile-time formulas.
<p>
<p>Definition at line <a class="el" href="btree_8h-source.html#l00059">59</a> of file <a class="el" href="btree_8h-source.html">btree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="cd87b40df0c1d4ead6fac13b49cb5345"></a><!-- doxytag: member="btree.h::BTREE_PRINT" ref="cd87b40df0c1d4ead6fac13b49cb5345" args="(x)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define BTREE_PRINT </td>
<td>(</td>
<td class="paramtype">x </td>
<td class="paramname"> </td>
<td> ) </td>
<td> do { if (debug) (std::cout << x); } while(0)</td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Print out debug information to std::cout if BTREE_DEBUG is defined.
<p>
<p>Definition at line <a class="el" href="btree_8h-source.html#l00043">43</a> of file <a class="el" href="btree_8h-source.html">btree.h</a>.</p>
<p>Referenced by <a class="el" href="btree_8h-source.html#l03324">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::dump_node()</a>, <a class="el" href="btree_8h-source.html#l02335">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one()</a>, <a class="el" href="btree_8h-source.html#l02400">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend()</a>, <a class="el" href="btree_8h-source.html#l01505">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_lower()</a>, <a class="el" href="btree_8h-source.html#l01552">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_upper()</a>, <a class="el" href="btree_8h-source.html#l02054">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_descend()</a>, <a class="el" href="btree_8h-source.html#l02708">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_inner()</a>, <a class="el" href="btree_8h-source.html#l02677">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::merge_leaves()</a>, <a class="el" href="btree_8h-source.html#l03287">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore()</a>, <a class="el" href="btree_8h-source.html#l02802">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_inner()</a>, <a class="el" href="btree_8h-source.html#l02755">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_left_leaf()</a>, <a class="el" href="btree_8h-source.html#l02916">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_inner()</a>, <a class="el" href="btree_8h-source.html#l02862">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::shift_right_leaf()</a>, <a class="el" href="btree_8h-source.html#l02234">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_inner_node()</a>, <a class="el" href="btree_8h-source.html#l02194">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_leaf_node()</a>, and <a class="el" href="btree_8h-source.html#l03073">stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_node()</a>.</p>
</div>
</div><p>
</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>
