<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> <title>C++ API frePPLe: frepple::utils::Tree Class Reference</title> <link href="doxygen.css" rel="stylesheet" type="text/css"> <link href="tabs.css" rel="stylesheet" type="text/css"> <link href="../styles.css" rel="stylesheet" type="text/css"> </head> <body> <div id="container"> <div id="menubar"> <div id="logo" align="center"> <br/><img src='../frepple.bmp' alt="frepple" /><br/> <a href='http://www.frepple.com/'> <strong>a Free<br/>Production Planning<br/>Library</strong> </a> </div> <div id="menu"> <br/> <h3><a href='../Main/HomePage.html'>Main</a></h3> <h3><a href='../UI/Main.html'>User Manual</a></h3> <h3><a href='../Tutorial/Main.html'>Tutorial</a></h3> <h3><a href='../Frepple/Main.html'>Reference Manual</a></h3> <h3><a href='../Main/FAQ.html'>FAQ</a></h3> <h3><a href='index.html'>C++ API</a></h3> <br/> </div> </div> <div id="content"> <br/> <!-- Generated by Doxygen 1.6.1 --> <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 class="current"><a href="annotated.html"><span>Classes</span></a></li> <li><a href="files.html"><span>Files</span></a></li> <li><a href="dirs.html"><span>Directories</span></a></li> </ul> </div> <div class="tabs"> <ul> <li><a href="annotated.html"><span>Class List</span></a></li> <li><a href="classes.html"><span>Class Index</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> <div class="navpath"><a class="el" href="a00256.html">frepple</a>::<a class="el" href="a00257.html">utils</a>::<a class="el" href="a00181.html">Tree</a> </div> </div> <div class="contents"> <h1>frepple::utils::Tree Class Reference</h1><!-- doxytag: class="frepple::utils::Tree" --><!-- doxytag: inherits="frepple::utils::NonCopyable" --> <p>This class implements a binary tree data structure. It is used as a container for entities keyed by their name. <a href="#_details">More...</a></p> <p><code>#include <<a class="el" href="a00252_source.html">utils.h</a>></code></p> <div class="dynheader"> Inheritance diagram for frepple::utils::Tree:</div> <div class="dynsection"> <div class="center"><img src="a00646.png" border="0" usemap="#frepple_1_1utils_1_1_tree_inherit__map" alt="Inheritance graph"/></div> <map name="frepple_1_1utils_1_1_tree_inherit__map" id="frepple_1_1utils_1_1_tree_inherit__map"> <area shape="rect" id="node2" href="a00119.html" title="Class NonCopyable is a base class. Derive your own class from it when you want to..." alt="" coords="5,6,181,34"/> </map> <center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div> <p><a href="a00647.html">List of all members.</a></p> <table border="0" cellpadding="0" cellspacing="0"> <tr><td colspan="2"><h2>Classes</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top">class </td><td class="memItemRight" valign="bottom"><a class="el" href="a00182.html">TreeNode</a></td></tr> <tr><td class="mdescLeft"> </td><td class="mdescRight">This class represents a node in the tree. <a href="a00182.html#_details">More...</a><br/></td></tr> <tr><td colspan="2"><h2>Public Types</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top">enum </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a1d874ef9d1fb1325aec8069d9a578f39">NodeColor</a> { <a class="el" href="a00181.html#a1d874ef9d1fb1325aec8069d9a578f39a8efd9fdac156d90ea714f4085c33f9c4">red</a>, <a class="el" href="a00181.html#a1d874ef9d1fb1325aec8069d9a578f39aa79abd32771092aea18764ad563a4470">black</a>, <a class="el" href="a00181.html#a1d874ef9d1fb1325aec8069d9a578f39a77de76fed566d26afbd93930e7a53807">none</a> }</td></tr> <tr><td colspan="2"><h2>Public Member Functions</h2></td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#ad44c460c1fb9648e83d703e6cdc64d19">begin</a> () const </td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#ad31e0db332aa55c29567d28b4f47a2d4">clear</a> ()</td></tr> <tr><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a8c11861060dcf9ee45054b73c26ee77d">empty</a> () const </td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a3c12d98627c9d46864dfd6b5e994878c">end</a> () const </td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#af97a2348168870409e23348bdb409970">erase</a> (<a class="el" href="a00182.html">TreeNode</a> *x)</td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a4a093c89ed8ddd0e791622d76dc3dee6">find</a> (const string &k) const </td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#ac82ef64b4e7e5c7604b50a2327ca8f59">findLowerBound</a> (const string &k, bool *f) const </td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#ad86b27fab36285d7564f42dfed3570d7">insert</a> (<a class="el" href="a00182.html">TreeNode</a> *v, <a class="el" href="a00182.html">TreeNode</a> *hint)</td></tr> <tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="a00182.html">TreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#afa8f41efd3bf1ba8345458a875cc9da7">insert</a> (<a class="el" href="a00182.html">TreeNode</a> *v)</td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a58ae0b2a0f6601a34a842027f4277730">rename</a> (<a class="el" href="a00182.html">TreeNode</a> *obj, string newname)</td></tr> <tr><td class="memItemLeft" align="right" valign="top">size_t </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a7ae0f783f775996f5ac010769caa9af8">size</a> () const </td></tr> <tr><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a919e920952e8fdc82ac2ed333d57deb0">Tree</a> (bool b=false)</td></tr> <tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#ad0759a0db4bb6b71307d42a344e76f85">verify</a> () const </td></tr> <tr><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="a00181.html#a301579e895c7b7007f7fd3c7037c82cc">~Tree</a> ()</td></tr> </table> <hr/><a name="_details"></a><h2>Detailed Description</h2> <p>This class implements a binary tree data structure. It is used as a container for entities keyed by their name. </p> <p>Technically, the data structure can be described as a red-black tree with intrusive tree nodes. </p> <dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="a00085.html" title="Base class for objects using a string as their primary key.">HasName</a> </dd></dl> <p>Definition at line <a class="el" href="a00252_source.html#l03431">3431</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> <hr/><h2>Member Enumeration Documentation</h2> <a class="anchor" id="a1d874ef9d1fb1325aec8069d9a578f39"></a><!-- doxytag: member="frepple::utils::Tree::NodeColor" ref="a1d874ef9d1fb1325aec8069d9a578f39" args="" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">enum <a class="el" href="a00181.html#a1d874ef9d1fb1325aec8069d9a578f39">frepple::utils::Tree::NodeColor</a></td> </tr> </table> </div> <div class="memdoc"> <p>The algorithm assigns a color to each node in the tree. The color is used to keep the tree balanced.<br/> A node with color 'none' is a node that hasn't been inserted yet in the tree. </p> <dl><dt><b>Enumerator: </b></dt><dd><table border="0" cellspacing="2" cellpadding="0"> <tr><td valign="top"><em><a class="anchor" id="a1d874ef9d1fb1325aec8069d9a578f39a8efd9fdac156d90ea714f4085c33f9c4"></a><!-- doxytag: member="red" ref="a1d874ef9d1fb1325aec8069d9a578f39a8efd9fdac156d90ea714f4085c33f9c4" args="" -->red</em> </td><td> </td></tr> <tr><td valign="top"><em><a class="anchor" id="a1d874ef9d1fb1325aec8069d9a578f39aa79abd32771092aea18764ad563a4470"></a><!-- doxytag: member="black" ref="a1d874ef9d1fb1325aec8069d9a578f39aa79abd32771092aea18764ad563a4470" args="" -->black</em> </td><td> </td></tr> <tr><td valign="top"><em><a class="anchor" id="a1d874ef9d1fb1325aec8069d9a578f39a77de76fed566d26afbd93930e7a53807"></a><!-- doxytag: member="none" ref="a1d874ef9d1fb1325aec8069d9a578f39a77de76fed566d26afbd93930e7a53807" args="" -->none</em> </td><td> </td></tr> </table> </dd> </dl> <p>Definition at line <a class="el" href="a00252_source.html#l03439">3439</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <hr/><h2>Constructor & Destructor Documentation</h2> <a class="anchor" id="a919e920952e8fdc82ac2ed333d57deb0"></a><!-- doxytag: member="frepple::utils::Tree::Tree" ref="a919e920952e8fdc82ac2ed333d57deb0" args="(bool b=false)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">frepple::utils::Tree::Tree </td> <td>(</td> <td class="paramtype">bool </td> <td class="paramname"> <em>b</em> = <code>false</code></td> <td> ) </td> <td><code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Default constructor. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03536">3536</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="a301579e895c7b7007f7fd3c7037c82cc"></a><!-- doxytag: member="frepple::utils::Tree::~Tree" ref="a301579e895c7b7007f7fd3c7037c82cc" args="()" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">frepple::utils::Tree::~Tree </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td><code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Destructor.<br/> By default, the objects in the tree are not deleted when the tree is deleted. This is done for performance reasons: the program can shut down faster. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03550">3550</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <hr/><h2>Member Function Documentation</h2> <a class="anchor" id="ad44c460c1fb9648e83d703e6cdc64d19"></a><!-- doxytag: member="frepple::utils::Tree::begin" ref="ad44c460c1fb9648e83d703e6cdc64d19" args="() const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">TreeNode</a>* frepple::utils::Tree::begin </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Returns an iterator to the start of the list.<br/> The user will need to take care of properly acquiring a read lock on on the tree object. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03556">3556</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="ad31e0db332aa55c29567d28b4f47a2d4"></a><!-- doxytag: member="frepple::utils::Tree::clear" ref="ad31e0db332aa55c29567d28b4f47a2d4" args="()" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void frepple::utils::Tree::clear </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Remove all elements from the tree. </p> <p>Definition at line <a class="el" href="a00222_source.html#l00036">36</a> of file <a class="el" href="a00222_source.html">name.cpp</a>.</p> </div> </div> <a class="anchor" id="a8c11861060dcf9ee45054b73c26ee77d"></a><!-- doxytag: member="frepple::utils::Tree::empty" ref="a8c11861060dcf9ee45054b73c26ee77d" args="() const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">bool frepple::utils::Tree::empty </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Returns true if the list is empty.<br/> Its complexity is O(1). </p> <p>Definition at line <a class="el" href="a00252_source.html#l03566">3566</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="a3c12d98627c9d46864dfd6b5e994878c"></a><!-- doxytag: member="frepple::utils::Tree::end" ref="a3c12d98627c9d46864dfd6b5e994878c" args="() const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">TreeNode</a>* frepple::utils::Tree::end </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Returns an iterator pointing beyond the last element in the list.<br/> The user will need to take care of properly acquiring a read lock on on the tree object. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03562">3562</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="af97a2348168870409e23348bdb409970"></a><!-- doxytag: member="frepple::utils::Tree::erase" ref="af97a2348168870409e23348bdb409970" args="(TreeNode *x)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void frepple::utils::Tree::erase </td> <td>(</td> <td class="paramtype"><a class="el" href="a00182.html">TreeNode</a> * </td> <td class="paramname"> <em>x</em></td> <td> ) </td> <td></td> </tr> </table> </div> <div class="memdoc"> <p>Remove a node from the tree. </p> <p>Definition at line <a class="el" href="a00222_source.html#l00190">190</a> of file <a class="el" href="a00222_source.html">name.cpp</a>.</p> </div> </div> <a class="anchor" id="a4a093c89ed8ddd0e791622d76dc3dee6"></a><!-- doxytag: member="frepple::utils::Tree::find" ref="a4a093c89ed8ddd0e791622d76dc3dee6" args="(const string &k) const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">TreeNode</a>* frepple::utils::Tree::find </td> <td>(</td> <td class="paramtype">const string & </td> <td class="paramname"> <em>k</em></td> <td> ) </td> <td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Search for an element in the tree.<br/> Profiling shows this function has a significant impact on the CPU time (mainly because of the string comparisons), and has been optimized as much as possible. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03613">3613</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="ac82ef64b4e7e5c7604b50a2327ca8f59"></a><!-- doxytag: member="frepple::utils::Tree::findLowerBound" ref="ac82ef64b4e7e5c7604b50a2327ca8f59" args="(const string &k, bool *f) const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">TreeNode</a>* frepple::utils::Tree::findLowerBound </td> <td>(</td> <td class="paramtype">const string & </td> <td class="paramname"> <em>k</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">bool * </td> <td class="paramname"> <em>f</em></td><td> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td><td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Find the element with this given key or the element immediately preceding it.<br/> The second argument is a boolean that is set to true when the element is found in the list. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03631">3631</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="ad86b27fab36285d7564f42dfed3570d7"></a><!-- doxytag: member="frepple::utils::Tree::insert" ref="ad86b27fab36285d7564f42dfed3570d7" args="(TreeNode *v, TreeNode *hint)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">Tree::TreeNode</a> * frepple::utils::Tree::insert </td> <td>(</td> <td class="paramtype"><a class="el" href="a00182.html">TreeNode</a> * </td> <td class="paramname"> <em>v</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype"><a class="el" href="a00182.html">TreeNode</a> * </td> <td class="paramname"> <em>hint</em></td><td> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td><td></td> </tr> </table> </div> <div class="memdoc"> <p>Insert a new node in the tree. The second argument is a hint on the proper location in the tree.<br/> Profiling shows this function has a significant impact on the cpu time (mainly because of the string comparisons), and has been optimized as much as possible. </p> <p>Definition at line <a class="el" href="a00222_source.html#l00057">57</a> of file <a class="el" href="a00222_source.html">name.cpp</a>.</p> </div> </div> <a class="anchor" id="afa8f41efd3bf1ba8345458a875cc9da7"></a><!-- doxytag: member="frepple::utils::Tree::insert" ref="afa8f41efd3bf1ba8345458a875cc9da7" args="(TreeNode *v)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="a00182.html">TreeNode</a>* frepple::utils::Tree::insert </td> <td>(</td> <td class="paramtype"><a class="el" href="a00182.html">TreeNode</a> * </td> <td class="paramname"> <em>v</em></td> <td> ) </td> <td><code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Insert a new node in the tree. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03652">3652</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="a58ae0b2a0f6601a34a842027f4277730"></a><!-- doxytag: member="frepple::utils::Tree::rename" ref="a58ae0b2a0f6601a34a842027f4277730" args="(TreeNode *obj, string newname)" --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void frepple::utils::Tree::rename </td> <td>(</td> <td class="paramtype"><a class="el" href="a00182.html">TreeNode</a> * </td> <td class="paramname"> <em>obj</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">string </td> <td class="paramname"> <em>newname</em></td><td> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td><td><code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>Renames an existing node, and adjusts its position in the tree. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03573">3573</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="a7ae0f783f775996f5ac010769caa9af8"></a><!-- doxytag: member="frepple::utils::Tree::size" ref="a7ae0f783f775996f5ac010769caa9af8" args="() const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">size_t frepple::utils::Tree::size </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td> const<code> [inline]</code></td> </tr> </table> </div> <div class="memdoc"> <p>This method returns the number of nodes inserted in this tree.<br/> Its complexity is O(1), so it can be called on large trees without any performance impact. </p> <p>Definition at line <a class="el" href="a00252_source.html#l03590">3590</a> of file <a class="el" href="a00252_source.html">utils.h</a>.</p> </div> </div> <a class="anchor" id="ad0759a0db4bb6b71307d42a344e76f85"></a><!-- doxytag: member="frepple::utils::Tree::verify" ref="ad0759a0db4bb6b71307d42a344e76f85" args="() const " --> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void frepple::utils::Tree::verify </td> <td>(</td> <td class="paramname"></td> <td> ) </td> <td> const</td> </tr> </table> </div> <div class="memdoc"> <p>Verifies the integrity of the tree and returns true if everything is correct.<br/> The tree should be locked before calling this function. </p> <p>Definition at line <a class="el" href="a00222_source.html#l00379">379</a> of file <a class="el" href="a00222_source.html">name.cpp</a>.</p> </div> </div> <hr/>The documentation for this class was generated from the following files:<ul> <li><a class="el" href="a00252_source.html">utils.h</a></li> <li><a class="el" href="a00222_source.html">name.cpp</a></li> </ul> </div> <hr size="1"/><address style="align: right;"><small>Documentation generated for frePPLe by <a href="http://www.doxygen.org/index.html"> <img src="doxygen.png" alt="doxygen" align="middle" border="0"/></a></small></address> </div> </div> </body> </html>