<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Crystal Space 1.2.1: csRedBlackTree< K > Class Template Reference (Crystal Space 1.2.1 Public API Reference)</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<table border="0" cellpadding="0" cellspacing="0" width="100%" class="head">
<tr height="59">
<td class="head" width="202" valign="bottom" style="padding-left:0;"><a href="http://www.crystalspace3d.org/"><img src="csblur.png" width="236" height="59" alt="CrystalSpace" border="0"></a></td>
<td class="head"><h2>Public API Reference</h2></td>
</tr>
<tr height="11">
<td colspan="2" class="headshadow" valign="top" style="padding-left:0;"><img src="csblurb.png" width="236" height="11" alt="" border="0"></td>
</tr>
</table>
<div class="content">
<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li class="current"><a href="classes.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="classes.html"><span>Alphabetical List</span></a></li>
<li><a href="annotated.html"><span>Class List</span></a></li>
<li><a href="hierarchy.html"><span>Class Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class Members</span></a></li>
</ul>
</div>
<h1>csRedBlackTree< K > Class Template Reference<br>
<small>
[<a class="el" href="group__util__containers.html">Containers</a>]</small>
</h1><!-- doxytag: class="csRedBlackTree" -->A red-black-tree.
<a href="#_details">More...</a>
<p>
<code>#include <<a class="el" href="redblacktree_8h-source.html">csutil/redblacktree.h</a>></code>
<p>
<p>
<a href="classcsRedBlackTree-members.html">List of all members.</a><table border="0" cellpadding="0" cellspacing="0">
<tr><td></td></tr>
<tr><td colspan="2"><br><h2>Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#bb7a5883317a190a4e38bb64bd8457c1">Contains</a> (const K &key) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Check whether a key is in the tree. <a href="#bb7a5883317a190a4e38bb64bd8457c1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="13164e69faa484c9324747f1aff57c5a"></a><!-- doxytag: member="csRedBlackTree::csRedBlackTree" ref="13164e69faa484c9324747f1aff57c5a" args="(const csRedBlackTree &other)" -->
</td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#13164e69faa484c9324747f1aff57c5a">csRedBlackTree</a> (const <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a> &other)</td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#ee599d5e05f65abe451412798340a917">csRedBlackTree</a> (size_t allocatorBlockSize=4096)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Construct a new tree. <a href="#ee599d5e05f65abe451412798340a917"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#c7518fb2075dedc34a6f116fdeaa4ae1">Delete</a> (const K &key)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Delete a key. <a href="#c7518fb2075dedc34a6f116fdeaa4ae1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#c978b85e102be8e5457546d8bda452f3">DeleteAll</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Delete all keys. <a href="#c978b85e102be8e5457546d8bda452f3"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#e2ef9e81ea1a67253709cf20330244cb">Empty</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Delete all the keys. (Idiomatic alias for <a class="el" href="classcsRedBlackTree.html#c978b85e102be8e5457546d8bda452f3" title="Delete all keys.">DeleteAll()</a>.). <a href="#e2ef9e81ea1a67253709cf20330244cb"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#fda841b60dc8cf996d7cf53b4da401a4">In</a> (const K &key) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Check whether a key is in the tree. <a href="#fda841b60dc8cf996d7cf53b4da401a4"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">const K * </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#28c16110e5c19acce51e7d6fba87044d">Insert</a> (const K &key)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Insert a key. <a href="#28c16110e5c19acce51e7d6fba87044d"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#d7d9c8b92b8b8d646aebe8933ab18eb5">IsEmpty</a> () const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns whether this tree has no nodes. <a href="#d7d9c8b92b8b8d646aebe8933ab18eb5"></a><br></td></tr>
<tr><td colspan="2"><div class="groupHeader"></div></td></tr>
<tr><td class="memTemplParams" nowrap colspan="2"><a class="anchor" name="359da05e1c39a394fee542388707c9a3"></a><!-- doxytag: member="csRedBlackTree::Find" ref="359da05e1c39a394fee542388707c9a3" args="(const K2 &other, const K &fallback) const " -->
template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">const K & </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#359da05e1c39a394fee542388707c9a3">Find</a> (const K2 &other, const K &fallback) const </td></tr>
<tr><td class="memTemplParams" nowrap colspan="2">template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">const K * </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#735f44e12c2527c7ef8cd7e3b9bed188">Find</a> (const K2 &other) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Locate key that is equal to 'other'. <a href="#735f44e12c2527c7ef8cd7e3b9bed188"></a><br></td></tr>
<tr><td colspan="2"><div class="groupHeader"></div></td></tr>
<tr><td class="memTemplParams" nowrap colspan="2">template<typename CB> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">void </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#5bafbe778a22b67aa100c9117e08225c">TraverseInOrder</a> (CB &callback) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Traverse tree. <a href="#5bafbe778a22b67aa100c9117e08225c"></a><br></td></tr>
<tr><td colspan="2"><br><h2>Protected Types</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">enum </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#710657a2c0112807cba841ef81c8af4a">NodeColor</a> { <a class="el" href="classcsRedBlackTree.html#710657a2c0112807cba841ef81c8af4a85952371095a369b526db52e5794b3bf">Black</a> = 0,
<a class="el" href="classcsRedBlackTree.html#710657a2c0112807cba841ef81c8af4aea04a607330d9455e1469e8adc0c6994">Red</a> = 1
}</td></tr>
<tr><td colspan="2"><br><h2>Protected Member Functions</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#af8653b108b856d260c850d9dfb0bb74">DeleteFixup</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *nilParent)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Fix up the RB tree after a deletion. <a href="#af8653b108b856d260c850d9dfb0bb74"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#9348a537f054590c8b33ba9801c29252">DeleteNode</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Delete a node from the tree. <a href="#9348a537f054590c8b33ba9801c29252"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#d0c22bf6ee82dec27a25b3b111102db9">InsertFixup</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Fix up the RB tree after an insert. <a href="#d0c22bf6ee82dec27a25b3b111102db9"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#bb4bfa4479562905674a3796e3964994">IsBlack</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Check whether a node is black. Note that 0 nodes are by definition black. <a href="#bb4bfa4479562905674a3796e3964994"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#ccf46a723137943cc1531bca8783fdd1">IsRed</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Check whether a node is red. <a href="#ccf46a723137943cc1531bca8783fdd1"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#f77be1ed91062181779ac0ca07a1cb78">LocateNode</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, const K &key) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Find the node for a key. <a href="#f77be1ed91062181779ac0ca07a1cb78"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#92a6a4c594ac8b7b888113a0424117fe">RecursiveCopy</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *&to, <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *parent, const <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *from)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Duplicate a subtree. <a href="#92a6a4c594ac8b7b888113a0424117fe"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#03a25871df78216416fb1fb8f8ad6f03">RecursiveInsert</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *parent, <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *&node, const K &key)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Locate the place where a new node needs to be inserted. <a href="#03a25871df78216416fb1fb8f8ad6f03"></a><br></td></tr>
<tr><td class="memTemplParams" nowrap colspan="2">template<typename CB> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">void </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#f973147533424b32acbf425f9bc91f0f">RecursiveTraverseInOrder</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, CB &callback) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Traverse tree. <a href="#f973147533424b32acbf425f9bc91f0f"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#5c85e583feacd98f9b25750941840075">RotateLeft</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *pivot)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Left-rotate subtree around 'pivot'. <a href="#5c85e583feacd98f9b25750941840075"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#d3eed6215e3c2d441199131f2ac7df3e">RotateRight</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *pivot)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Right-rotate subtree around 'pivot'. <a href="#d3eed6215e3c2d441199131f2ac7df3e"></a><br></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#de3655e4ae89a39283f0d4a581f3ebac">Successor</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Return smallest node with a key greater than 'node's. <a href="#de3655e4ae89a39283f0d4a581f3ebac"></a><br></td></tr>
<tr><td colspan="2"><div class="groupHeader"></div></td></tr>
<tr><td class="memTemplParams" nowrap colspan="2"><a class="anchor" name="2b6b7e7f550305ebd1b5b123c30175ad"></a><!-- doxytag: member="csRedBlackTree::Find" ref="2b6b7e7f550305ebd1b5b123c30175ad" args="(const K2 &other, K &fallback)" -->
template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">K & </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#2b6b7e7f550305ebd1b5b123c30175ad">Find</a> (const K2 &other, K &fallback)</td></tr>
<tr><td class="memTemplParams" nowrap colspan="2">template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">K * </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#60f8bd27940aee03161e5ee8ad61381f">Find</a> (const K2 &other)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Locate key that is equal to 'other'. <a href="#60f8bd27940aee03161e5ee8ad61381f"></a><br></td></tr>
<tr><td colspan="2"><div class="groupHeader"></div></td></tr>
<tr><td class="memTemplParams" nowrap colspan="2"><a class="anchor" name="e5f6c699c04c4ee6e4884ca3b4e2cb79"></a><!-- doxytag: member="csRedBlackTree::RecursiveFind" ref="e5f6c699c04c4ee6e4884ca3b4e2cb79" args="(Node *node, const K2 &other, K &fallback)" -->
template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">K & </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#e5f6c699c04c4ee6e4884ca3b4e2cb79">RecursiveFind</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, const K2 &other, K &fallback)</td></tr>
<tr><td class="memTemplParams" nowrap colspan="2"><a class="anchor" name="dbaca9b303dcce78b342ecb99c8f4146"></a><!-- doxytag: member="csRedBlackTree::RecursiveFind" ref="dbaca9b303dcce78b342ecb99c8f4146" args="(Node *node, const K2 &other, const K &fallback) const " -->
template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">const K & </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#dbaca9b303dcce78b342ecb99c8f4146">RecursiveFind</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, const K2 &other, const K &fallback) const </td></tr>
<tr><td class="memTemplParams" nowrap colspan="2"><a class="anchor" name="412771547330fef2500d672b0088b2d7"></a><!-- doxytag: member="csRedBlackTree::RecursiveFind" ref="412771547330fef2500d672b0088b2d7" args="(Node *node, const K2 &other)" -->
template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">K * </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#412771547330fef2500d672b0088b2d7">RecursiveFind</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, const K2 &other)</td></tr>
<tr><td class="memTemplParams" nowrap colspan="2">template<typename K2> </td></tr>
<tr><td class="memTemplItemLeft" nowrap align="right" valign="top">const K * </td><td class="memTemplItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#7a531ac03a134b880e0a2df2b3e3f974">RecursiveFind</a> (<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *node, const K2 &other) const </td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Locate key that is equal to 'other'. <a href="#7a531ac03a134b880e0a2df2b3e3f974"></a><br></td></tr>
<tr><td colspan="2"><br><h2>Protected Attributes</h2></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="ab641d26f1c241e1d1e57046778244eb"></a><!-- doxytag: member="csRedBlackTree::nodeAlloc" ref="ab641d26f1c241e1d1e57046778244eb" args="" -->
<a class="el" href="classcsBlockAllocator.html">csBlockAllocator</a><br>
< <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a>,<br>
<a class="el" href="classCS_1_1Memory_1_1AllocatorAlign.html">CS::Memory::AllocatorAlign</a>< 2 > > </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#ab641d26f1c241e1d1e57046778244eb">nodeAlloc</a></td></tr>
<tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="anchor" name="7e659dd5f85a01611a663aa88f9107ec"></a><!-- doxytag: member="csRedBlackTree::root" ref="7e659dd5f85a01611a663aa88f9107ec" args="" -->
<a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classcsRedBlackTree.html#7e659dd5f85a01611a663aa88f9107ec">root</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="structcsRedBlackTree_1_1Node.html">Node</a></td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">A node in the tree. <a href="structcsRedBlackTree_1_1Node.html#_details">More...</a><br></td></tr>
</table>
<hr><a name="_details"></a><h2>Detailed Description</h2>
<h3>template<typename K><br>
class csRedBlackTree< K ></h3>
A red-black-tree.
<p>
<dl class="remark" compact><dt><b>Remarks:</b></dt><dd>Does not allow duplicate keys. <p>
Uses csComparator<> for key comparisons. <p>
Only stores keys. If you need a key-value-map, look at <a class="el" href="classcsRedBlackTreeMap.html" title="Key-value-map, backed by csRedBlackTree.">csRedBlackTreeMap</a>. </dd></dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00047">47</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<hr><h2>Member Enumeration Documentation</h2>
<a class="anchor" name="710657a2c0112807cba841ef81c8af4a"></a><!-- doxytag: member="csRedBlackTree::NodeColor" ref="710657a2c0112807cba841ef81c8af4a" args="" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">enum <a class="el" href="classcsRedBlackTree.html#710657a2c0112807cba841ef81c8af4a">csRedBlackTree::NodeColor</a><code> [protected]</code> </td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
<dl compact><dt><b>Enumerator: </b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"><em><a class="anchor" name="710657a2c0112807cba841ef81c8af4a85952371095a369b526db52e5794b3bf"></a><!-- doxytag: member="Black" ref="710657a2c0112807cba841ef81c8af4a85952371095a369b526db52e5794b3bf" args="" -->Black</em> </td><td>
</td></tr>
<tr><td valign="top"><em><a class="anchor" name="710657a2c0112807cba841ef81c8af4aea04a607330d9455e1469e8adc0c6994"></a><!-- doxytag: member="Red" ref="710657a2c0112807cba841ef81c8af4aea04a607330d9455e1469e8adc0c6994" args="" -->Red</em> </td><td>
</td></tr>
</table>
</dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00050">50</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<hr><h2>Constructor & Destructor Documentation</h2>
<a class="anchor" name="ee599d5e05f65abe451412798340a917"></a><!-- doxytag: member="csRedBlackTree::csRedBlackTree" ref="ee599d5e05f65abe451412798340a917" args="(size_t allocatorBlockSize=4096)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::<a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a> </td>
<td>(</td>
<td class="paramtype">size_t </td>
<td class="paramname"> <em>allocatorBlockSize</em> = <code>4096</code> </td>
<td> ) </td>
<td width="100%"><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Construct a new tree.
<p>
<dl compact><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>allocatorBlockSize</em> </td><td>Block size in bytes used by the internal block allocator for nodes. </td></tr>
</table>
</dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00447">447</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<hr><h2>Member Function Documentation</h2>
<a class="anchor" name="bb7a5883317a190a4e38bb64bd8457c1"></a><!-- doxytag: member="csRedBlackTree::Contains" ref="bb7a5883317a190a4e38bb64bd8457c1" args="(const K &key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Contains </td>
<td>(</td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Check whether a key is in the tree.
<p>
<dl class="remark" compact><dt><b>Remarks:</b></dt><dd>This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some. </dd></dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00489">489</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="c7518fb2075dedc34a6f116fdeaa4ae1"></a><!-- doxytag: member="csRedBlackTree::Delete" ref="c7518fb2075dedc34a6f116fdeaa4ae1" args="(const K &key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Delete </td>
<td>(</td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em> </td>
<td> ) </td>
<td width="100%"><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Delete a key.
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>Whether the deletion was successful. Fails if the key is not in the tree. </dd></dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00472">472</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="c978b85e102be8e5457546d8bda452f3"></a><!-- doxytag: member="csRedBlackTree::DeleteAll" ref="c978b85e102be8e5457546d8bda452f3" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::DeleteAll </td>
<td>(</td>
<td class="paramname"> </td>
<td> ) </td>
<td width="100%"><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Delete all keys.
<p>
<p>Reimplemented in <a class="el" href="classcsRedBlackTreeMap.html#ded0c9ec9ce6e82f440b6adec0171181">csRedBlackTreeMap< K, T ></a>.</p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00506">506</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00512">csRedBlackTree< csRedBlackTreePayload< K, T > >::Empty()</a>.</p>
</div>
</div><p>
<a class="anchor" name="af8653b108b856d260c850d9dfb0bb74"></a><!-- doxytag: member="csRedBlackTree::DeleteFixup" ref="af8653b108b856d260c850d9dfb0bb74" args="(Node *node, Node *nilParent)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::DeleteFixup </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>nilParent</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Fix up the RB tree after a deletion.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00251">251</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00214">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteNode()</a>.</p>
</div>
</div><p>
<a class="anchor" name="9348a537f054590c8b33ba9801c29252"></a><!-- doxytag: member="csRedBlackTree::DeleteNode" ref="9348a537f054590c8b33ba9801c29252" args="(Node *node)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::DeleteNode </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em> </td>
<td> ) </td>
<td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Delete a node from the tree.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00214">214</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00472">csRedBlackTree< csRedBlackTreePayload< K, T > >::Delete()</a>.</p>
</div>
</div><p>
<a class="anchor" name="e2ef9e81ea1a67253709cf20330244cb"></a><!-- doxytag: member="csRedBlackTree::Empty" ref="e2ef9e81ea1a67253709cf20330244cb" args="()" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Empty </td>
<td>(</td>
<td class="paramname"> </td>
<td> ) </td>
<td width="100%"><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Delete all the keys. (Idiomatic alias for <a class="el" href="classcsRedBlackTree.html#c978b85e102be8e5457546d8bda452f3" title="Delete all keys.">DeleteAll()</a>.).
<p>
<p>Reimplemented in <a class="el" href="classcsRedBlackTreeMap.html#2033603f8749d7126f0832976ea7b7aa">csRedBlackTreeMap< K, T ></a>.</p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00512">512</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="735f44e12c2527c7ef8cd7e3b9bed188"></a><!-- doxytag: member="csRedBlackTree::Find" ref="735f44e12c2527c7ef8cd7e3b9bed188" args="(const K2 &other) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<div class="memtemplate">
template<typename K2> </div>
<table class="memname">
<tr>
<td class="memname">const K* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Find </td>
<td>(</td>
<td class="paramtype">const K2 & </td>
<td class="paramname"> <em>other</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Locate key that is equal to 'other'.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00494">494</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="60f8bd27940aee03161e5ee8ad61381f"></a><!-- doxytag: member="csRedBlackTree::Find" ref="60f8bd27940aee03161e5ee8ad61381f" args="(const K2 &other)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<div class="memtemplate">
template<typename K2> </div>
<table class="memname">
<tr>
<td class="memname">K* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Find </td>
<td>(</td>
<td class="paramtype">const K2 & </td>
<td class="paramname"> <em>other</em> </td>
<td> ) </td>
<td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Locate key that is equal to 'other'.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00415">415</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="fda841b60dc8cf996d7cf53b4da401a4"></a><!-- doxytag: member="csRedBlackTree::In" ref="fda841b60dc8cf996d7cf53b4da401a4" args="(const K &key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::In </td>
<td>(</td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Check whether a key is in the tree.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00480">480</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00489">csRedBlackTree< csRedBlackTreePayload< K, T > >::Contains()</a>.</p>
</div>
</div><p>
<a class="anchor" name="28c16110e5c19acce51e7d6fba87044d"></a><!-- doxytag: member="csRedBlackTree::Insert" ref="28c16110e5c19acce51e7d6fba87044d" args="(const K &key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">const K* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Insert </td>
<td>(</td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em> </td>
<td> ) </td>
<td width="100%"><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Insert a key.
<p>
<dl class="return" compact><dt><b>Returns:</b></dt><dd>A pointer to the copy of the key stored in the tree, or 0 if the key already exists. </dd></dl>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00460">460</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="d0c22bf6ee82dec27a25b3b111102db9"></a><!-- doxytag: member="csRedBlackTree::InsertFixup" ref="d0c22bf6ee82dec27a25b3b111102db9" args="(Node *node)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::InsertFixup </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em> </td>
<td> ) </td>
<td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Fix up the RB tree after an insert.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00151">151</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00460">csRedBlackTree< csRedBlackTreePayload< K, T > >::Insert()</a>.</p>
</div>
</div><p>
<a class="anchor" name="bb4bfa4479562905674a3796e3964994"></a><!-- doxytag: member="csRedBlackTree::IsBlack" ref="bb4bfa4479562905674a3796e3964994" args="(Node *node) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::IsBlack </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Check whether a node is black. Note that 0 nodes are by definition black.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00145">145</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00251">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteFixup()</a>.</p>
</div>
</div><p>
<a class="anchor" name="d7d9c8b92b8b8d646aebe8933ab18eb5"></a><!-- doxytag: member="csRedBlackTree::IsEmpty" ref="d7d9c8b92b8b8d646aebe8933ab18eb5" args="() const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::IsEmpty </td>
<td>(</td>
<td class="paramname"> </td>
<td> ) </td>
<td width="100%"> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Returns whether this tree has no nodes.
<p>
<p>Reimplemented in <a class="el" href="classcsRedBlackTreeMap.html#5c30a0cb98550ffbc0820bf1e37ee300">csRedBlackTreeMap< K, T ></a>.</p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00514">514</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<a class="anchor" name="ccf46a723137943cc1531bca8783fdd1"></a><!-- doxytag: member="csRedBlackTree::IsRed" ref="ccf46a723137943cc1531bca8783fdd1" args="(Node *node) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">bool <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::IsRed </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Check whether a node is red.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00148">148</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00251">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteFixup()</a>, and <a class="el" href="redblacktree_8h-source.html#l00151">csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup()</a>.</p>
</div>
</div><p>
<a class="anchor" name="f77be1ed91062181779ac0ca07a1cb78"></a><!-- doxytag: member="csRedBlackTree::LocateNode" ref="f77be1ed91062181779ac0ca07a1cb78" args="(Node *node, const K &key) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a>* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::LocateNode </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Find the node for a key.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00322">322</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00472">csRedBlackTree< csRedBlackTreePayload< K, T > >::Delete()</a>, <a class="el" href="redblacktree_8h-source.html#l00480">csRedBlackTree< csRedBlackTreePayload< K, T > >::In()</a>, and <a class="el" href="redblacktree_8h-source.html#l00322">csRedBlackTree< csRedBlackTreePayload< K, T > >::LocateNode()</a>.</p>
</div>
</div><p>
<a class="anchor" name="92a6a4c594ac8b7b888113a0424117fe"></a><!-- doxytag: member="csRedBlackTree::RecursiveCopy" ref="92a6a4c594ac8b7b888113a0424117fe" args="(Node *&to, Node *parent, const Node *from)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RecursiveCopy </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *& </td>
<td class="paramname"> <em>to</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>parent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const <a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>from</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Duplicate a subtree.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00427">427</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00449">csRedBlackTree< csRedBlackTreePayload< K, T > >::csRedBlackTree()</a>, and <a class="el" href="redblacktree_8h-source.html#l00427">csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveCopy()</a>.</p>
</div>
</div><p>
<a class="anchor" name="7a531ac03a134b880e0a2df2b3e3f974"></a><!-- doxytag: member="csRedBlackTree::RecursiveFind" ref="7a531ac03a134b880e0a2df2b3e3f974" args="(Node *node, const K2 &other) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<div class="memtemplate">
template<typename K2> </div>
<table class="memname">
<tr>
<td class="memname">const K* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RecursiveFind </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const K2 & </td>
<td class="paramname"> <em>other</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Locate key that is equal to 'other'.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00355">355</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00415">csRedBlackTree< csRedBlackTreePayload< K, T > >::Find()</a>, and <a class="el" href="redblacktree_8h-source.html#l00355">csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveFind()</a>.</p>
</div>
</div><p>
<a class="anchor" name="03a25871df78216416fb1fb8f8ad6f03"></a><!-- doxytag: member="csRedBlackTree::RecursiveInsert" ref="03a25871df78216416fb1fb8f8ad6f03" args="(Node *parent, Node *&node, const K &key)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a>* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RecursiveInsert </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>parent</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> *& </td>
<td class="paramname"> <em>node</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">const K & </td>
<td class="paramname"> <em>key</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Locate the place where a new node needs to be inserted.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00082">82</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00460">csRedBlackTree< csRedBlackTreePayload< K, T > >::Insert()</a>, and <a class="el" href="redblacktree_8h-source.html#l00082">csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveInsert()</a>.</p>
</div>
</div><p>
<a class="anchor" name="f973147533424b32acbf425f9bc91f0f"></a><!-- doxytag: member="csRedBlackTree::RecursiveTraverseInOrder" ref="f973147533424b32acbf425f9bc91f0f" args="(Node *node, CB &callback) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<div class="memtemplate">
template<typename CB> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RecursiveTraverseInOrder </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">CB & </td>
<td class="paramname"> <em>callback</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Traverse tree.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00405">405</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00405">csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveTraverseInOrder()</a>, and <a class="el" href="redblacktree_8h-source.html#l00519">csRedBlackTree< csRedBlackTreePayload< K, T > >::TraverseInOrder()</a>.</p>
</div>
</div><p>
<a class="anchor" name="5c85e583feacd98f9b25750941840075"></a><!-- doxytag: member="csRedBlackTree::RotateLeft" ref="5c85e583feacd98f9b25750941840075" args="(Node *pivot)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RotateLeft </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>pivot</em> </td>
<td> ) </td>
<td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Left-rotate subtree around 'pivot'.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00105">105</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00251">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteFixup()</a>, and <a class="el" href="redblacktree_8h-source.html#l00151">csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup()</a>.</p>
</div>
</div><p>
<a class="anchor" name="d3eed6215e3c2d441199131f2ac7df3e"></a><!-- doxytag: member="csRedBlackTree::RotateRight" ref="d3eed6215e3c2d441199131f2ac7df3e" args="(Node *pivot)" -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::RotateRight </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>pivot</em> </td>
<td> ) </td>
<td width="100%"><code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Right-rotate subtree around 'pivot'.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00125">125</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00251">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteFixup()</a>, and <a class="el" href="redblacktree_8h-source.html#l00151">csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup()</a>.</p>
</div>
</div><p>
<a class="anchor" name="de3655e4ae89a39283f0d4a581f3ebac"></a><!-- doxytag: member="csRedBlackTree::Successor" ref="de3655e4ae89a39283f0d4a581f3ebac" args="(Node *node) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<table class="memname">
<tr>
<td class="memname"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a>* <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::Successor </td>
<td>(</td>
<td class="paramtype"><a class="el" href="structcsRedBlackTree_1_1Node.html">Node</a> * </td>
<td class="paramname"> <em>node</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline, protected]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Return smallest node with a key greater than 'node's.
<p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00335">335</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
<p>Referenced by <a class="el" href="redblacktree_8h-source.html#l00214">csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteNode()</a>.</p>
</div>
</div><p>
<a class="anchor" name="5bafbe778a22b67aa100c9117e08225c"></a><!-- doxytag: member="csRedBlackTree::TraverseInOrder" ref="5bafbe778a22b67aa100c9117e08225c" args="(CB &callback) const " -->
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template<typename K> </div>
<div class="memtemplate">
template<typename CB> </div>
<table class="memname">
<tr>
<td class="memname">void <a class="el" href="classcsRedBlackTree.html">csRedBlackTree</a>< K >::TraverseInOrder </td>
<td>(</td>
<td class="paramtype">CB & </td>
<td class="paramname"> <em>callback</em> </td>
<td> ) </td>
<td width="100%"> const<code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>
Traverse tree.
<p>
<p>Reimplemented in <a class="el" href="classcsRedBlackTreeMap.html#5d77be825a7295d7afa92bea103ddbc9">csRedBlackTreeMap< K, T ></a>.</p>
<p>Definition at line <a class="el" href="redblacktree_8h-source.html#l00519">519</a> of file <a class="el" href="redblacktree_8h-source.html">redblacktree.h</a>.</p>
</div>
</div><p>
<hr>The documentation for this class was generated from the following file:<ul>
<li>csutil/<a class="el" href="redblacktree_8h-source.html">redblacktree.h</a></ul>
<hr size="1"><address><small>Generated for Crystal Space 1.2.1 by
<a href="http://www.doxygen.org/index.html">doxygen</a> 1.5.3
</small></address> </div></body> </html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bad97183153701b09df5fae1052b1c30
>
files
>
938
