<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>LibOFX: tree.hh 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.0 -->
<div class="tabs">
<ul>
<li><a href="main.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li id="current"><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="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul></div>
<h1>tree.hh</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* </span>
<a name="l00002"></a>00002 <span class="comment"></span>
<a name="l00003"></a>00003 <span class="comment"> $Id: tree.hh,v 1.6 2006/07/20 04:41:16 benoitg Exp $</span>
<a name="l00004"></a>00004 <span class="comment"></span>
<a name="l00005"></a>00005 <span class="comment"> STL-like templated tree class.</span>
<a name="l00006"></a>00006 <span class="comment"> Copyright (C) 2001-2005 Kasper Peeters <kasper.peeters@aei.mpg.de>.</span>
<a name="l00007"></a>00007 <span class="comment"></span>
<a name="l00008"></a>00008 <span class="comment">*/</span>
<a name="l00009"></a>00009
<a name="l00026"></a>00026 <span class="comment">/*</span>
<a name="l00027"></a>00027 <span class="comment"> This program is free software; you can redistribute it and/or modify</span>
<a name="l00028"></a>00028 <span class="comment"> it under the terms of the GNU General Public License as published by</span>
<a name="l00029"></a>00029 <span class="comment"> the Free Software Foundation; version 2.</span>
<a name="l00030"></a>00030 <span class="comment"> </span>
<a name="l00031"></a>00031 <span class="comment"> This program is distributed in the hope that it will be useful,</span>
<a name="l00032"></a>00032 <span class="comment"> but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00033"></a>00033 <span class="comment"> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span>
<a name="l00034"></a>00034 <span class="comment"> GNU General Public License for more details.</span>
<a name="l00035"></a>00035 <span class="comment"> </span>
<a name="l00036"></a>00036 <span class="comment"> You should have received a copy of the GNU General Public License</span>
<a name="l00037"></a>00037 <span class="comment"> along with this program; if not, write to the Free Software</span>
<a name="l00038"></a>00038 <span class="comment"> Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA</span>
<a name="l00039"></a>00039 <span class="comment">*/</span>
<a name="l00040"></a>00040
<a name="l00058"></a>00058 <span class="preprocessor">#ifndef tree_hh_</span>
<a name="l00059"></a>00059 <span class="preprocessor"></span><span class="preprocessor">#define tree_hh_</span>
<a name="l00060"></a>00060 <span class="preprocessor"></span>
<a name="l00061"></a>00061 <span class="preprocessor">#include <cassert></span>
<a name="l00062"></a>00062 <span class="preprocessor">#include <memory></span>
<a name="l00063"></a>00063 <span class="preprocessor">#include <stdexcept></span>
<a name="l00064"></a>00064 <span class="preprocessor">#include <iterator></span>
<a name="l00065"></a>00065 <span class="preprocessor">#include <set></span>
<a name="l00066"></a>00066
<a name="l00067"></a>00067 <span class="comment">// HP-style construct/destroy have gone from the standard,</span>
<a name="l00068"></a>00068 <span class="comment">// so here is a copy.</span>
<a name="l00069"></a>00069
<a name="l00070"></a>00070 <span class="keyword">namespace </span>kp {
<a name="l00071"></a>00071
<a name="l00072"></a>00072 <span class="keyword">template</span> <<span class="keyword">class</span> T1, <span class="keyword">class</span> T2>
<a name="l00073"></a>00073 <span class="keywordtype">void</span> <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">constructor</a>(T1* p, T2& val)
<a name="l00074"></a>00074 {
<a name="l00075"></a>00075 <span class="keyword">new</span> ((<span class="keywordtype">void</span> *) p) T1(val);
<a name="l00076"></a>00076 }
<a name="l00077"></a>00077
<a name="l00078"></a>00078 <span class="keyword">template</span> <<span class="keyword">class</span> T1>
<a name="l00079"></a>00079 <span class="keywordtype">void</span> <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">constructor</a>(T1* p)
<a name="l00080"></a>00080 {
<a name="l00081"></a>00081 <span class="keyword">new</span> ((<span class="keywordtype">void</span> *) p) T1;
<a name="l00082"></a>00082 }
<a name="l00083"></a>00083
<a name="l00084"></a>00084 <span class="keyword">template</span> <<span class="keyword">class</span> T1>
<a name="l00085"></a>00085 <span class="keywordtype">void</span> <a class="code" href="namespacekp.html#a6813c11eeb1c091cdd1eff62de70914">destructor</a>(T1* p)
<a name="l00086"></a>00086 {
<a name="l00087"></a>00087 p->~T1();
<a name="l00088"></a>00088 }
<a name="l00089"></a>00089
<a name="l00090"></a>00090 };
<a name="l00091"></a>00091
<a name="l00093"></a>00093 <span class="keyword">template</span><<span class="keyword">class</span> T>
<a name="l00094"></a>00094 <span class="keyword">class </span><a class="code" href="classtree__node__.html">tree_node_</a> { <span class="comment">// size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.</span>
<a name="l00095"></a>00095 <span class="keyword">public</span>:
<a name="l00096"></a><a class="code" href="classtree__node__.html#60597bf2f8288fdd616c52f8a5a4e477">00096</a> <a class="code" href="classtree__node__.html">tree_node_<T></a> *<a class="code" href="classtree__node__.html#60597bf2f8288fdd616c52f8a5a4e477">parent</a>;
<a name="l00097"></a><a class="code" href="classtree__node__.html#611d3c41c716dae6bf2012e3d9152933">00097</a> <a class="code" href="classtree__node__.html">tree_node_<T></a> *<a class="code" href="classtree__node__.html#d51591496e654515b662095f70d1fc1a">first_child</a>, *<a class="code" href="classtree__node__.html#611d3c41c716dae6bf2012e3d9152933">last_child</a>;
<a name="l00098"></a><a class="code" href="classtree__node__.html#e7b8325f91c0b4460552cef6b9aec159">00098</a> <a class="code" href="classtree__node__.html">tree_node_<T></a> *<a class="code" href="classtree__node__.html#e7b8325f91c0b4460552cef6b9aec159">prev_sibling</a>, *<a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>;
<a name="l00099"></a>00099 T <a class="code" href="classtree__node__.html#4c15077a3ad0552413d1268ee4be1bef">data</a>;
<a name="l00100"></a>00100 }; <span class="comment">// __attribute__((packed));</span>
<a name="l00101"></a>00101
<a name="l00102"></a>00102 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator = std::allocator<tree_node_<T> > >
<a name="l00103"></a>00103 <span class="keyword">class </span><a class="code" href="classtree.html">tree</a> {
<a name="l00104"></a>00104 <span class="keyword">protected</span>:
<a name="l00105"></a><a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">00105</a> <span class="keyword">typedef</span> <a class="code" href="classtree__node__.html">tree_node_<T></a> <a class="code" href="classtree__node__.html">tree_node</a>;
<a name="l00106"></a>00106 <span class="keyword">public</span>:
<a name="l00108"></a><a class="code" href="classtree.html#1e7bcd21e7420f7922a1bca79080acfa">00108</a> <span class="keyword">typedef</span> T <a class="code" href="classOfxGenericContainer.html">value_type</a>;
<a name="l00109"></a>00109
<a name="l00110"></a>00110 <span class="keyword">class </span>iterator_base;
<a name="l00111"></a>00111 <span class="keyword">class </span>pre_order_iterator;
<a name="l00112"></a>00112 <span class="keyword">class </span>post_order_iterator;
<a name="l00113"></a>00113 <span class="keyword">class </span>sibling_iterator;
<a name="l00114"></a>00114
<a name="l00115"></a>00115 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree</a>();
<a name="l00116"></a>00116 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree</a>(<span class="keyword">const</span> T&);
<a name="l00117"></a>00117 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree</a>(<span class="keyword">const</span> iterator_base&);
<a name="l00118"></a>00118 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree</a>(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>&);
<a name="l00119"></a>00119 <a class="code" href="classtree.html#f0169b515c95f4299fd2d984137b7868">~tree</a>();
<a name="l00120"></a>00120 <span class="keywordtype">void</span> <a class="code" href="classtree.html#9561c0c73b0605f32bf82a026eaf216a">operator=</a>(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>&);
<a name="l00121"></a>00121
<a name="l00123"></a>00123 <span class="preprocessor">#ifdef __SGI_STL_PORT</span>
<a name="l00124"></a>00124 <span class="preprocessor"></span> <span class="keyword">class </span>iterator_base : <span class="keyword">public</span> stlport::bidirectional_iterator<T, ptrdiff_t> {
<a name="l00125"></a>00125 <span class="preprocessor">#else</span>
<a name="l00126"></a>00126 <span class="preprocessor"></span> <span class="keyword">class </span><a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a> {
<a name="l00127"></a>00127 <span class="preprocessor">#endif</span>
<a name="l00128"></a>00128 <span class="preprocessor"></span> <span class="keyword">public</span>:
<a name="l00129"></a><a class="code" href="classtree_1_1iterator__base.html#ab430bec9e607ae24cdd2bdffe3faf70">00129</a> <span class="keyword">typedef</span> T <a class="code" href="classtree_1_1iterator__base.html#ab430bec9e607ae24cdd2bdffe3faf70">value_type</a>;
<a name="l00130"></a><a class="code" href="classtree_1_1iterator__base.html#0665bed45269b6f7b97809ea9920008e">00130</a> <span class="keyword">typedef</span> T* <a class="code" href="classtree_1_1iterator__base.html#0665bed45269b6f7b97809ea9920008e">pointer</a>;
<a name="l00131"></a><a class="code" href="classtree_1_1iterator__base.html#063faf883017de195e7e72cf55be6914">00131</a> <span class="keyword">typedef</span> T& <a class="code" href="classtree_1_1iterator__base.html#063faf883017de195e7e72cf55be6914">reference</a>;
<a name="l00132"></a><a class="code" href="classtree_1_1iterator__base.html#a2b239ac4db713d5b191e696584a9076">00132</a> <span class="keyword">typedef</span> size_t <a class="code" href="classtree_1_1iterator__base.html#a2b239ac4db713d5b191e696584a9076">size_type</a>;
<a name="l00133"></a><a class="code" href="classtree_1_1iterator__base.html#eff66472181aa05d50c7ffe4a91dc4c0">00133</a> <span class="keyword">typedef</span> ptrdiff_t <a class="code" href="classtree_1_1iterator__base.html#eff66472181aa05d50c7ffe4a91dc4c0">difference_type</a>;
<a name="l00134"></a><a class="code" href="classtree_1_1iterator__base.html#7d0ace14418254eaab7526f1d0aabf40">00134</a> <span class="keyword">typedef</span> std::bidirectional_iterator_tag <a class="code" href="classtree_1_1iterator__base.html#7d0ace14418254eaab7526f1d0aabf40">iterator_category</a>;
<a name="l00135"></a>00135
<a name="l00136"></a>00136 <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a>();
<a name="l00137"></a>00137 <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a>(<a class="code" href="classtree__node__.html">tree_node</a> *);
<a name="l00138"></a>00138
<a name="l00139"></a>00139 T& <a class="code" href="classtree_1_1iterator__base.html#a5d7acb4ad37b640d3fa7dec6da4896b">operator*</a>() <span class="keyword">const</span>;
<a name="l00140"></a>00140 T* <a class="code" href="classtree_1_1iterator__base.html#8f48a56f39396b1e6e5a7b44f603b871">operator-></a>() <span class="keyword">const</span>;
<a name="l00141"></a>00141
<a name="l00143"></a>00143 <span class="keywordtype">void</span> <a class="code" href="classtree_1_1iterator__base.html#a0be7989b9dd4c5bcdcc0d47a56d11fb">skip_children</a>();
<a name="l00145"></a>00145 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree_1_1iterator__base.html#e6f2ec470dac0149858add00617f51a7">number_of_children</a>() <span class="keyword">const</span>;
<a name="l00146"></a>00146
<a name="l00147"></a>00147 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>() <span class="keyword">const</span>;
<a name="l00148"></a>00148 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>() <span class="keyword">const</span>;
<a name="l00149"></a>00149
<a name="l00150"></a><a class="code" href="classtree_1_1iterator__base.html#8e012d9505968cd1b51afab5bb4f2bf0">00150</a> <a class="code" href="classtree__node__.html">tree_node</a> *<a class="code" href="classtree_1_1iterator__base.html#8e012d9505968cd1b51afab5bb4f2bf0">node</a>;
<a name="l00151"></a>00151 <span class="keyword">protected</span>:
<a name="l00152"></a>00152 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1iterator__base.html#88239267268c728952e0cd89b9326e82">skip_current_children_</a>;
<a name="l00153"></a>00153 };
<a name="l00154"></a>00154
<a name="l00156"></a>00156 <span class="keyword">class </span><a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> : <span class="keyword">public</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a> {
<a name="l00157"></a>00157 <span class="keyword">public</span>:
<a name="l00158"></a>00158 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>();
<a name="l00159"></a>00159 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>(<a class="code" href="classtree__node__.html">tree_node</a> *);
<a name="l00160"></a>00160 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&);
<a name="l00161"></a>00161 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>&);
<a name="l00162"></a>00162
<a name="l00163"></a>00163 <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>&) <span class="keyword">const</span>;
<a name="l00164"></a>00164 <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>&) <span class="keyword">const</span>;
<a name="l00165"></a>00165 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>& operator++();
<a name="l00166"></a>00166 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>& operator--();
<a name="l00167"></a>00167 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> operator++(<span class="keywordtype">int</span>);
<a name="l00168"></a>00168 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> operator--(<span class="keywordtype">int</span>);
<a name="l00169"></a>00169 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>& operator+=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00170"></a>00170 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a>& operator-=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00171"></a>00171 };
<a name="l00172"></a>00172
<a name="l00174"></a>00174 <span class="keyword">class </span>post_order_iterator : <span class="keyword">public</span> <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a> {
<a name="l00175"></a>00175 <span class="keyword">public</span>:
<a name="l00176"></a>00176 post_order_iterator();
<a name="l00177"></a>00177 post_order_iterator(<a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *);
<a name="l00178"></a>00178 post_order_iterator(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a>&);
<a name="l00179"></a>00179 post_order_iterator(<span class="keyword">const</span> sibling_iterator&);
<a name="l00180"></a>00180
<a name="l00181"></a>00181 <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> post_order_iterator&) <span class="keyword">const</span>;
<a name="l00182"></a>00182 <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> post_order_iterator&) <span class="keyword">const</span>;
<a name="l00183"></a>00183 post_order_iterator& operator++();
<a name="l00184"></a>00184 post_order_iterator& operator--();
<a name="l00185"></a>00185 post_order_iterator operator++(<span class="keywordtype">int</span>);
<a name="l00186"></a>00186 post_order_iterator operator--(<span class="keywordtype">int</span>);
<a name="l00187"></a>00187 post_order_iterator& operator+=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00188"></a>00188 post_order_iterator& operator-=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00189"></a>00189
<a name="l00191"></a>00191 <span class="keywordtype">void</span> descend_all();
<a name="l00192"></a>00192 };
<a name="l00193"></a>00193
<a name="l00195"></a><a class="code" href="classtree.html#2079982538b88d21fe1ccea34fe7ce0e">00195</a> <span class="keyword">typedef</span> pre_order_iterator <a class="code" href="classtree.html#2079982538b88d21fe1ccea34fe7ce0e">iterator</a>;
<a name="l00196"></a>00196
<a name="l00198"></a>00198 <span class="keyword">class </span>fixed_depth_iterator : <span class="keyword">public</span> <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a> {
<a name="l00199"></a>00199 <span class="keyword">public</span>:
<a name="l00200"></a>00200 fixed_depth_iterator();
<a name="l00201"></a>00201 fixed_depth_iterator(<a class="code" href="classtree__node__.html">tree_node</a> *);
<a name="l00202"></a>00202 fixed_depth_iterator(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">iterator_base</a>&);
<a name="l00203"></a>00203 fixed_depth_iterator(<span class="keyword">const</span> sibling_iterator&);
<a name="l00204"></a>00204 fixed_depth_iterator(<span class="keyword">const</span> fixed_depth_iterator&);
<a name="l00205"></a>00205
<a name="l00206"></a>00206 <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> fixed_depth_iterator&) <span class="keyword">const</span>;
<a name="l00207"></a>00207 <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> fixed_depth_iterator&) <span class="keyword">const</span>;
<a name="l00208"></a>00208 fixed_depth_iterator& operator++();
<a name="l00209"></a>00209 fixed_depth_iterator& operator--();
<a name="l00210"></a>00210 fixed_depth_iterator operator++(<span class="keywordtype">int</span>);
<a name="l00211"></a>00211 fixed_depth_iterator operator--(<span class="keywordtype">int</span>);
<a name="l00212"></a>00212 fixed_depth_iterator& operator+=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00213"></a>00213 fixed_depth_iterator& operator-=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00214"></a>00214
<a name="l00215"></a><a class="code" href="classtree_1_1fixed__depth__iterator.html#5f6c92f12c4281e94e950ccd70833985">00215</a> <a class="code" href="classtree__node__.html">tree_node</a> *first_parent_;
<a name="l00216"></a>00216 <span class="keyword">private</span>:
<a name="l00217"></a>00217 <span class="keywordtype">void</span> set_first_parent_();
<a name="l00218"></a>00218 <span class="keywordtype">void</span> find_leftmost_parent_();
<a name="l00219"></a>00219 };
<a name="l00220"></a>00220
<a name="l00222"></a>00222 <span class="keyword">class </span><a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> : <span class="keyword">public</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a> {
<a name="l00223"></a>00223 <span class="keyword">public</span>:
<a name="l00224"></a>00224 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>();
<a name="l00225"></a>00225 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>(<a class="code" href="classtree__node__.html">tree_node</a> *);
<a name="l00226"></a>00226 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>&);
<a name="l00227"></a>00227 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&);
<a name="l00228"></a>00228
<a name="l00229"></a>00229 <span class="keywordtype">bool</span> operator==(<span class="keyword">const</span> <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>&) <span class="keyword">const</span>;
<a name="l00230"></a>00230 <span class="keywordtype">bool</span> operator!=(<span class="keyword">const</span> <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>&) <span class="keyword">const</span>;
<a name="l00231"></a>00231 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>& operator++();
<a name="l00232"></a>00232 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>& operator--();
<a name="l00233"></a>00233 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> operator++(<span class="keywordtype">int</span>);
<a name="l00234"></a>00234 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> operator--(<span class="keywordtype">int</span>);
<a name="l00235"></a>00235 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>& operator+=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00236"></a>00236 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>& operator-=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>);
<a name="l00237"></a>00237
<a name="l00238"></a>00238 <a class="code" href="classtree__node__.html">tree_node</a> *range_first() <span class="keyword">const</span>;
<a name="l00239"></a>00239 <a class="code" href="classtree__node__.html">tree_node</a> *range_last() <span class="keyword">const</span>;
<a name="l00240"></a><a class="code" href="classtree_1_1sibling__iterator.html#204f7449ee908f982d21cc3d334d25bc">00240</a> <a class="code" href="classtree__node__.html">tree_node</a> *parent_;
<a name="l00241"></a>00241 <span class="keyword">private</span>:
<a name="l00242"></a>00242 <span class="keywordtype">void</span> set_parent_();
<a name="l00243"></a>00243 };
<a name="l00244"></a>00244
<a name="l00246"></a>00246 <span class="keyword">inline</span> <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>() <span class="keyword">const</span>;
<a name="l00248"></a>00248 <span class="keyword">inline</span> <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>() <span class="keyword">const</span>;
<a name="l00250"></a>00250 <a class="code" href="classtree_1_1post__order__iterator.html">post_order_iterator</a> <a class="code" href="classtree.html#044e579efaa40f08d46b08db116bcfd9">begin_post</a>() <span class="keyword">const</span>;
<a name="l00252"></a>00252 <a class="code" href="classtree_1_1post__order__iterator.html">post_order_iterator</a> <a class="code" href="classtree.html#9366cb2996612e92fc8333f62ad12ec4">end_post</a>() <span class="keyword">const</span>;
<a name="l00254"></a>00254 <a class="code" href="classtree_1_1fixed__depth__iterator.html">fixed_depth_iterator</a> <a class="code" href="classtree.html#bd58303fa5dc63e5bc8158de82a711e0">begin_fixed</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) <span class="keyword">const</span>;
<a name="l00256"></a>00256 <a class="code" href="classtree_1_1fixed__depth__iterator.html">fixed_depth_iterator</a> <a class="code" href="classtree.html#c1944e7457c73af439a433ae3ea4892c">end_fixed</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) <span class="keyword">const</span>;
<a name="l00258"></a>00258 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00260"></a>00260 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00261"></a>00261
<a name="l00263"></a>00263 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#c4fad296716ff3afde3556c598f41a7f">parent</a>(iter) <span class="keyword">const</span>;
<a name="l00265"></a>00265 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#291bee91cf202e130095b1867b9bd356">previous_sibling</a>(iter) <span class="keyword">const</span>;
<a name="l00267"></a>00267 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#7a09a0eeccff8c96d1351859c007d2ff">next_sibling</a>(iter) <span class="keyword">const</span>;
<a name="l00269"></a>00269 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#012d4dbcc58401d8a1f9e97ec41898b9">next_at_same_depth</a>(iter) <span class="keyword">const</span>;
<a name="l00270"></a>00270
<a name="l00272"></a>00272 <span class="keywordtype">void</span> <a class="code" href="classtree.html#a8cf6dfe17504abfc0ffabb5a4ba9d0a">clear</a>();
<a name="l00274"></a>00274 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#3eb424c89446ae17a747d2aca2cdda4b">erase</a>(iter);
<a name="l00276"></a>00276 <span class="keywordtype">void</span> <a class="code" href="classtree.html#05d5fd71c206efc8ac30df5cd46176bc">erase_children</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&);
<a name="l00277"></a>00277
<a name="l00279"></a>00279 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>);
<a name="l00281"></a>00281 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> T& x);
<a name="l00283"></a>00283 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, iter other_position);
<a name="l00285"></a>00285 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#92ab22e0a98d8899c0d1b6c9d0a85465">append_children</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> from, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> to);
<a name="l00286"></a>00286
<a name="l00288"></a>00288 <a class="code" href="classtree_1_1pre__order__iterator.html">pre_order_iterator</a> <a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">set_head</a>(<span class="keyword">const</span> T& x);
<a name="l00290"></a>00290 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">insert</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> T& x);
<a name="l00292"></a>00292 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">insert</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> T& x);
<a name="l00294"></a>00294 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#d66d55d58b48ce0a8d7a5b41abe923d5">insert_subtree</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">subtree</a>);
<a name="l00296"></a>00296 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#215ab56bd13f59c661eb2298e373ff3e">insert_after</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> T& x);
<a name="l00297"></a>00297
<a name="l00299"></a>00299 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> T& x);
<a name="l00301"></a>00301 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& from);
<a name="l00303"></a>00303 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> orig_begin, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> orig_end,
<a name="l00304"></a>00304 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> new_begin, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> new_end);
<a name="l00305"></a>00305
<a name="l00307"></a>00307 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#479c8e3f748608a9b9fb91e58e18998c">flatten</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>);
<a name="l00309"></a>00309 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#32b88523e2d5b6c78381b7da9455be5e">reparent</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>);
<a name="l00311"></a>00311 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#32b88523e2d5b6c78381b7da9455be5e">reparent</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, iter from);
<a name="l00312"></a>00312
<a name="l00314"></a>00314 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#e7f72ba46cd061f71720c731b4a9bf63">move_after</a>(iter target, iter source);
<a name="l00316"></a>00316 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#b45aa15042445a81b13873d3ef4a2e86">move_before</a>(iter target, iter source);
<a name="l00318"></a>00318 <span class="keyword">template</span><<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#a4f8b906b2758eec530e28387b819284">move_ontop</a>(iter target, iter source);
<a name="l00319"></a>00319
<a name="l00321"></a>00321 <span class="keywordtype">void</span> <a class="code" href="classtree.html#1e3cd901f8f8d8a3da0e1d32e9282db1">merge</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a>,
<a name="l00322"></a>00322 <span class="keywordtype">bool</span> duplicate_leaves=<span class="keyword">false</span>);
<a name="l00324"></a>00324 <span class="keywordtype">void</span> <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">sort</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> from, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> to, <span class="keywordtype">bool</span> deep=<span class="keyword">false</span>);
<a name="l00325"></a>00325 <span class="keyword">template</span><<span class="keyword">class</span> StrictWeakOrdering>
<a name="l00326"></a>00326 <span class="keywordtype">void</span> <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">sort</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> from, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> to, StrictWeakOrdering comp, <span class="keywordtype">bool</span> deep=<span class="keyword">false</span>);
<a name="l00328"></a>00328 <span class="keyword">template</span><<span class="keyword">typename</span> iter>
<a name="l00329"></a>00329 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">equal</a>(<span class="keyword">const</span> iter& one, <span class="keyword">const</span> iter& two, <span class="keyword">const</span> iter& three) <span class="keyword">const</span>;
<a name="l00330"></a>00330 <span class="keyword">template</span><<span class="keyword">typename</span> iter, <span class="keyword">class</span> BinaryPredicate>
<a name="l00331"></a>00331 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">equal</a>(<span class="keyword">const</span> iter& one, <span class="keyword">const</span> iter& two, <span class="keyword">const</span> iter& three, BinaryPredicate) <span class="keyword">const</span>;
<a name="l00332"></a>00332 <span class="keyword">template</span><<span class="keyword">typename</span> iter>
<a name="l00333"></a>00333 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#5decf01c6fcd8516b8d1152fe574aabc">equal_subtree</a>(<span class="keyword">const</span> iter& one, <span class="keyword">const</span> iter& two) <span class="keyword">const</span>;
<a name="l00334"></a>00334 <span class="keyword">template</span><<span class="keyword">typename</span> iter, <span class="keyword">class</span> BinaryPredicate>
<a name="l00335"></a>00335 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#5decf01c6fcd8516b8d1152fe574aabc">equal_subtree</a>(<span class="keyword">const</span> iter& one, <span class="keyword">const</span> iter& two, BinaryPredicate) <span class="keyword">const</span>;
<a name="l00337"></a>00337 <a class="code" href="classtree.html">tree</a> <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">subtree</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> from, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> to) <span class="keyword">const</span>;
<a name="l00338"></a>00338 <span class="keywordtype">void</span> <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">subtree</a>(<a class="code" href="classtree.html">tree</a>&, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> from, <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> to) <span class="keyword">const</span>;
<a name="l00340"></a>00340 <span class="keywordtype">void</span> <a class="code" href="classtree.html#e842f9b70235bc2412b3c43bca759448">swap</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> it);
<a name="l00341"></a>00341
<a name="l00343"></a>00343 <span class="keywordtype">int</span> <a class="code" href="classtree.html#efe4460d7a0f4c0e309649e3ebfe3c3d">size</a>() <span class="keyword">const</span>;
<a name="l00345"></a>00345 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#e600fb282f7534e75811d14a1d1d0aba">empty</a>() <span class="keyword">const</span>;
<a name="l00347"></a>00347 <span class="keywordtype">int</span> <a class="code" href="classtree.html#85338176eaaf8421fa0ef06d1d5e8e40">depth</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00349"></a>00349 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree_1_1iterator__base.html#e6f2ec470dac0149858add00617f51a7">number_of_children</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00351"></a>00351 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree.html#f3613943778560ad57787486e071af12">number_of_siblings</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00353"></a>00353 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#a860f37aa4ec8955ef18a9b1936f0665">is_in_subtree</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>,
<a name="l00354"></a>00354 <span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>) <span class="keyword">const</span>;
<a name="l00356"></a>00356 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#9155b3955497913a965acf612caf02fd">is_valid</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>&) <span class="keyword">const</span>;
<a name="l00357"></a>00357
<a name="l00359"></a>00359 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree.html#de5ec1ba55f94165062e50d01ec35d86">index</a>(<a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> it) <span class="keyword">const</span>;
<a name="l00361"></a>00361 <a class="code" href="classtree_1_1sibling__iterator.html">sibling_iterator</a> <a class="code" href="classtree.html#446c722c82607f8b3243a9153b665d19">child</a>(<span class="keyword">const</span> <a class="code" href="classtree_1_1iterator__base.html">iterator_base</a>& <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span>) <span class="keyword">const</span>;
<a name="l00362"></a>00362
<a name="l00364"></a>00364 <span class="keyword">class </span><a class="code" href="classtree_1_1iterator__base__less.html">iterator_base_less</a> {
<a name="l00365"></a>00365 <span class="keyword">public</span>:
<a name="l00366"></a><a class="code" href="classtree_1_1iterator__base__less.html#0e8b78b396e8b767d61e1dd316aaa3e5">00366</a> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::iterator_base</a>& one,
<a name="l00367"></a>00367 <span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::iterator_base</a>& two)<span class="keyword"> const</span>
<a name="l00368"></a>00368 <span class="keyword"> </span>{
<a name="l00369"></a>00369 <span class="keywordflow">return</span> one.node < two.node;
<a name="l00370"></a>00370 }
<a name="l00371"></a>00371 };
<a name="l00372"></a><a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">00372</a> <a class="code" href="classtree__node__.html">tree_node</a> *<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>, *<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>; <span class="comment">// head/feet are always dummy; if an iterator points to them it is invalid</span>
<a name="l00373"></a>00373 <span class="keyword">private</span>:
<a name="l00374"></a>00374 tree_node_allocator alloc_;
<a name="l00375"></a>00375 <span class="keywordtype">void</span> head_initialise_();
<a name="l00376"></a>00376 <span class="keywordtype">void</span> copy_(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>& other);
<a name="l00377"></a>00377
<a name="l00379"></a>00379 <span class="keyword">template</span><<span class="keyword">class</span> StrictWeakOrdering>
<a name="l00380"></a>00380 <span class="keyword">class </span>compare_nodes {
<a name="l00381"></a>00381 <span class="keyword">public</span>:
<a name="l00382"></a>00382 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
<a name="l00383"></a>00383
<a name="l00384"></a>00384 <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *a, <span class="keyword">const</span> <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *b)
<a name="l00385"></a>00385 {
<a name="l00386"></a>00386 <span class="keyword">static</span> StrictWeakOrdering comp;
<a name="l00387"></a>00387 <span class="keywordflow">return</span> comp(a->data, b->data);
<a name="l00388"></a>00388 }
<a name="l00389"></a>00389 <span class="keyword">private</span>:
<a name="l00390"></a>00390 StrictWeakOrdering comp_;
<a name="l00391"></a>00391 };
<a name="l00392"></a>00392 };
<a name="l00393"></a>00393
<a name="l00394"></a>00394 <span class="comment">//template <class T, class tree_node_allocator></span>
<a name="l00395"></a>00395 <span class="comment">//class iterator_base_less {</span>
<a name="l00396"></a>00396 <span class="comment">// public:</span>
<a name="l00397"></a>00397 <span class="comment">// bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,</span>
<a name="l00398"></a>00398 <span class="comment">// const typename tree<T, tree_node_allocator>::iterator_base& two) const</span>
<a name="l00399"></a>00399 <span class="comment">// {</span>
<a name="l00400"></a>00400 <span class="comment">// txtout << "operatorclass<" << one.node < two.node << std::endl;</span>
<a name="l00401"></a>00401 <span class="comment">// return one.node < two.node;</span>
<a name="l00402"></a>00402 <span class="comment">// }</span>
<a name="l00403"></a>00403 <span class="comment">//};</span>
<a name="l00404"></a>00404
<a name="l00405"></a>00405 <span class="comment">//template <class T, class tree_node_allocator></span>
<a name="l00406"></a>00406 <span class="comment">//bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,</span>
<a name="l00407"></a>00407 <span class="comment">// const typename tree<T, tree_node_allocator>::iterator& two)</span>
<a name="l00408"></a>00408 <span class="comment">// {</span>
<a name="l00409"></a>00409 <span class="comment">// txtout << "operator< " << one.node < two.node << std::endl;</span>
<a name="l00410"></a>00410 <span class="comment">// if(one.node < two.node) return true;</span>
<a name="l00411"></a>00411 <span class="comment">// return false;</span>
<a name="l00412"></a>00412 <span class="comment">// }</span>
<a name="l00413"></a>00413
<a name="l00414"></a>00414 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00415"></a>00415 <span class="keywordtype">bool</span> operator>(<span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::iterator_base</a>& one,
<a name="l00416"></a>00416 <span class="keyword">const</span> <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::iterator_base</a>& two)
<a name="l00417"></a>00417 {
<a name="l00418"></a>00418 <span class="keywordflow">if</span>(one.node > two.node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00419"></a>00419 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00420"></a>00420 }
<a name="l00421"></a>00421
<a name="l00422"></a>00422
<a name="l00423"></a>00423
<a name="l00424"></a>00424 <span class="comment">// Tree</span>
<a name="l00425"></a>00425
<a name="l00426"></a>00426 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00427"></a>00427 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree<T, tree_node_allocator>::tree</a>()
<a name="l00428"></a>00428 {
<a name="l00429"></a>00429 head_initialise_();
<a name="l00430"></a>00430 }
<a name="l00431"></a>00431
<a name="l00432"></a>00432 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00433"></a>00433 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree<T, tree_node_allocator>::tree</a>(<span class="keyword">const</span> T& x)
<a name="l00434"></a>00434 {
<a name="l00435"></a>00435 head_initialise_();
<a name="l00436"></a>00436 <a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">set_head</a>(x);
<a name="l00437"></a>00437 }
<a name="l00438"></a>00438
<a name="l00439"></a>00439 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00440"></a>00440 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree<T, tree_node_allocator>::tree</a>(<span class="keyword">const</span> iterator_base& other)
<a name="l00441"></a>00441 {
<a name="l00442"></a>00442 head_initialise_();
<a name="l00443"></a>00443 <a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">set_head</a>((*other));
<a name="l00444"></a>00444 <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), other);
<a name="l00445"></a>00445 }
<a name="l00446"></a>00446
<a name="l00447"></a>00447 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00448"></a>00448 <a class="code" href="classtree.html#f0169b515c95f4299fd2d984137b7868">tree<T, tree_node_allocator>::~tree</a>()
<a name="l00449"></a>00449 {
<a name="l00450"></a>00450 <a class="code" href="classtree.html#a8cf6dfe17504abfc0ffabb5a4ba9d0a">clear</a>();
<a name="l00451"></a>00451 alloc_.deallocate(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>,1);
<a name="l00452"></a>00452 alloc_.deallocate(<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>,1);
<a name="l00453"></a>00453 }
<a name="l00454"></a>00454
<a name="l00455"></a>00455 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00456"></a>00456 <span class="keywordtype">void</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::head_initialise_</a>()
<a name="l00457"></a>00457 {
<a name="l00458"></a>00458 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a> = alloc_.allocate(1,0); <span class="comment">// MSVC does not have default second argument </span>
<a name="l00459"></a>00459 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a> = alloc_.allocate(1,0);
<a name="l00460"></a>00460
<a name="l00461"></a>00461 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#60597bf2f8288fdd616c52f8a5a4e477">parent</a>=0;
<a name="l00462"></a>00462 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#d51591496e654515b662095f70d1fc1a">first_child</a>=0;
<a name="l00463"></a>00463 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#611d3c41c716dae6bf2012e3d9152933">last_child</a>=0;
<a name="l00464"></a>00464 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#e7b8325f91c0b4460552cef6b9aec159">prev_sibling</a>=0; <span class="comment">//head;</span>
<a name="l00465"></a>00465 <a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>=<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>; <span class="comment">//head;</span>
<a name="l00466"></a>00466
<a name="l00467"></a>00467 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>-><a class="code" href="classtree__node__.html#60597bf2f8288fdd616c52f8a5a4e477">parent</a>=0;
<a name="l00468"></a>00468 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>-><a class="code" href="classtree__node__.html#d51591496e654515b662095f70d1fc1a">first_child</a>=0;
<a name="l00469"></a>00469 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>-><a class="code" href="classtree__node__.html#611d3c41c716dae6bf2012e3d9152933">last_child</a>=0;
<a name="l00470"></a>00470 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>-><a class="code" href="classtree__node__.html#e7b8325f91c0b4460552cef6b9aec159">prev_sibling</a>=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>;
<a name="l00471"></a>00471 <a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>=0;
<a name="l00472"></a>00472 }
<a name="l00473"></a>00473
<a name="l00474"></a>00474 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00475"></a>00475 <span class="keywordtype">void</span> <a class="code" href="classtree.html#9561c0c73b0605f32bf82a026eaf216a">tree<T, tree_node_allocator>::operator=</a>(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>& other)
<a name="l00476"></a>00476 {
<a name="l00477"></a>00477 copy_(other);
<a name="l00478"></a>00478 }
<a name="l00479"></a>00479
<a name="l00480"></a>00480 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00481"></a>00481 <a class="code" href="classtree.html#a064a1d9dceac9b918c5247919a4a325">tree<T, tree_node_allocator>::tree</a>(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>& other)
<a name="l00482"></a>00482 {
<a name="l00483"></a>00483 head_initialise_();
<a name="l00484"></a>00484 copy_(other);
<a name="l00485"></a>00485 }
<a name="l00486"></a>00486
<a name="l00487"></a>00487 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00488"></a>00488 <span class="keywordtype">void</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::copy_</a>(<span class="keyword">const</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator></a>& other)
<a name="l00489"></a>00489 {
<a name="l00490"></a>00490 <a class="code" href="classtree.html#a8cf6dfe17504abfc0ffabb5a4ba9d0a">clear</a>();
<a name="l00491"></a>00491 pre_order_iterator it=other.<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), to=<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>();
<a name="l00492"></a>00492 <span class="keywordflow">while</span>(it!=other.<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>()) {
<a name="l00493"></a>00493 to=<a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">insert</a>(to, (*it));
<a name="l00494"></a>00494 it.skip_children();
<a name="l00495"></a>00495 ++it;
<a name="l00496"></a>00496 }
<a name="l00497"></a>00497 to=<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>();
<a name="l00498"></a>00498 it=other.<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>();
<a name="l00499"></a>00499 <span class="keywordflow">while</span>(it!=other.<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>()) {
<a name="l00500"></a>00500 to=<a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(to, it);
<a name="l00501"></a>00501 to.skip_children();
<a name="l00502"></a>00502 it.skip_children();
<a name="l00503"></a>00503 ++to;
<a name="l00504"></a>00504 ++it;
<a name="l00505"></a>00505 }
<a name="l00506"></a>00506 }
<a name="l00507"></a>00507
<a name="l00508"></a>00508 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00509"></a>00509 <span class="keywordtype">void</span> <a class="code" href="classtree.html#a8cf6dfe17504abfc0ffabb5a4ba9d0a">tree<T, tree_node_allocator>::clear</a>()
<a name="l00510"></a>00510 {
<a name="l00511"></a>00511 <span class="keywordflow">if</span>(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>)
<a name="l00512"></a>00512 <span class="keywordflow">while</span>(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>!=<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>)
<a name="l00513"></a>00513 <a class="code" href="classtree.html#3eb424c89446ae17a747d2aca2cdda4b">erase</a>(pre_order_iterator(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>));
<a name="l00514"></a>00514 }
<a name="l00515"></a>00515
<a name="l00516"></a>00516 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00517"></a>00517 <span class="keywordtype">void</span> <a class="code" href="classtree.html#05d5fd71c206efc8ac30df5cd46176bc">tree<T, tree_node_allocator>::erase_children</a>(<span class="keyword">const</span> iterator_base& it)
<a name="l00518"></a>00518 {
<a name="l00519"></a>00519 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *cur=it.node->first_child;
<a name="l00520"></a>00520 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *prev=0;
<a name="l00521"></a>00521
<a name="l00522"></a>00522 <span class="keywordflow">while</span>(cur!=0) {
<a name="l00523"></a>00523 prev=cur;
<a name="l00524"></a>00524 cur=cur->next_sibling;
<a name="l00525"></a>00525 <a class="code" href="classtree.html#05d5fd71c206efc8ac30df5cd46176bc">erase_children</a>(pre_order_iterator(prev));
<a name="l00526"></a>00526 <a class="code" href="namespacekp.html#a6813c11eeb1c091cdd1eff62de70914">kp::destructor</a>(&prev->data);
<a name="l00527"></a>00527 alloc_.deallocate(prev,1);
<a name="l00528"></a>00528 }
<a name="l00529"></a>00529 it.node->first_child=0;
<a name="l00530"></a>00530 it.node->last_child=0;
<a name="l00531"></a>00531 }
<a name="l00532"></a>00532
<a name="l00533"></a>00533 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00534"></a>00534 <span class="keyword">template</span><<span class="keyword">class</span> iter>
<a name="l00535"></a>00535 iter <a class="code" href="classtree.html#3eb424c89446ae17a747d2aca2cdda4b">tree<T, tree_node_allocator>::erase</a>(iter it)
<a name="l00536"></a>00536 {
<a name="l00537"></a>00537 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *cur=it.node;
<a name="l00538"></a>00538 assert(cur!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>);
<a name="l00539"></a>00539 iter ret=it;
<a name="l00540"></a>00540 ret.skip_children();
<a name="l00541"></a>00541 ++ret;
<a name="l00542"></a>00542 <a class="code" href="classtree.html#05d5fd71c206efc8ac30df5cd46176bc">erase_children</a>(it);
<a name="l00543"></a>00543 <span class="keywordflow">if</span>(cur->prev_sibling==0) {
<a name="l00544"></a>00544 cur->parent->first_child=cur->next_sibling;
<a name="l00545"></a>00545 }
<a name="l00546"></a>00546 <span class="keywordflow">else</span> {
<a name="l00547"></a>00547 cur->prev_sibling->next_sibling=cur->next_sibling;
<a name="l00548"></a>00548 }
<a name="l00549"></a>00549 <span class="keywordflow">if</span>(cur->next_sibling==0) {
<a name="l00550"></a>00550 cur->parent->last_child=cur->prev_sibling;
<a name="l00551"></a>00551 }
<a name="l00552"></a>00552 <span class="keywordflow">else</span> {
<a name="l00553"></a>00553 cur->next_sibling->prev_sibling=cur->prev_sibling;
<a name="l00554"></a>00554 }
<a name="l00555"></a>00555
<a name="l00556"></a>00556 <a class="code" href="namespacekp.html#a6813c11eeb1c091cdd1eff62de70914">kp::destructor</a>(&cur->data);
<a name="l00557"></a>00557 alloc_.deallocate(cur,1);
<a name="l00558"></a>00558 <span class="keywordflow">return</span> ret;
<a name="l00559"></a>00559 }
<a name="l00560"></a>00560
<a name="l00561"></a>00561 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00562"></a>00562 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a> <a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">tree<T, tree_node_allocator>::begin</a>()<span class="keyword"> const</span>
<a name="l00563"></a>00563 <span class="keyword"> </span>{
<a name="l00564"></a>00564 <span class="keywordflow">return</span> pre_order_iterator(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>);
<a name="l00565"></a>00565 }
<a name="l00566"></a>00566
<a name="l00567"></a>00567 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00568"></a>00568 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a> <a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">tree<T, tree_node_allocator>::end</a>()<span class="keyword"> const</span>
<a name="l00569"></a>00569 <span class="keyword"> </span>{
<a name="l00570"></a>00570 <span class="keywordflow">return</span> pre_order_iterator(<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>);
<a name="l00571"></a>00571 }
<a name="l00572"></a>00572
<a name="l00573"></a>00573 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00574"></a>00574 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a> <a class="code" href="classtree.html#044e579efaa40f08d46b08db116bcfd9">tree<T, tree_node_allocator>::begin_post</a>()<span class="keyword"> const</span>
<a name="l00575"></a>00575 <span class="keyword"> </span>{
<a name="l00576"></a>00576 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>;
<a name="l00577"></a>00577 <span class="keywordflow">if</span>(tmp!=<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>) {
<a name="l00578"></a>00578 <span class="keywordflow">while</span>(tmp->first_child)
<a name="l00579"></a>00579 tmp=tmp->first_child;
<a name="l00580"></a>00580 }
<a name="l00581"></a>00581 <span class="keywordflow">return</span> post_order_iterator(tmp);
<a name="l00582"></a>00582 }
<a name="l00583"></a>00583
<a name="l00584"></a>00584 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00585"></a>00585 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a> <a class="code" href="classtree.html#9366cb2996612e92fc8333f62ad12ec4">tree<T, tree_node_allocator>::end_post</a>()<span class="keyword"> const</span>
<a name="l00586"></a>00586 <span class="keyword"> </span>{
<a name="l00587"></a>00587 <span class="keywordflow">return</span> post_order_iterator(<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>);
<a name="l00588"></a>00588 }
<a name="l00589"></a>00589
<a name="l00590"></a>00590 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00591"></a>00591 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a> <a class="code" href="classtree.html#bd58303fa5dc63e5bc8158de82a711e0">tree<T, tree_node_allocator>::begin_fixed</a>(<span class="keyword">const</span> iterator_base& pos, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> dp)<span class="keyword"> const</span>
<a name="l00592"></a>00592 <span class="keyword"> </span>{
<a name="l00593"></a>00593 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=pos.node;
<a name="l00594"></a>00594 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> curdepth=0;
<a name="l00595"></a>00595 <span class="keywordflow">while</span>(curdepth<dp) { <span class="comment">// go down one level</span>
<a name="l00596"></a>00596 <span class="keywordflow">while</span>(tmp->first_child==0) {
<a name="l00597"></a>00597 tmp=tmp->next_sibling;
<a name="l00598"></a>00598 <span class="keywordflow">if</span>(tmp==0)
<a name="l00599"></a>00599 <span class="keywordflow">throw</span> std::range_error(<span class="stringliteral">"tree: begin_fixed out of range"</span>);
<a name="l00600"></a>00600 }
<a name="l00601"></a>00601 tmp=tmp->first_child;
<a name="l00602"></a>00602 ++curdepth;
<a name="l00603"></a>00603 }
<a name="l00604"></a>00604 <span class="keywordflow">return</span> tmp;
<a name="l00605"></a>00605 }
<a name="l00606"></a>00606
<a name="l00607"></a>00607 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00608"></a>00608 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a> <a class="code" href="classtree.html#c1944e7457c73af439a433ae3ea4892c">tree<T, tree_node_allocator>::end_fixed</a>(<span class="keyword">const</span> iterator_base& pos, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> dp)<span class="keyword"> const</span>
<a name="l00609"></a>00609 <span class="keyword"> </span>{
<a name="l00610"></a>00610 assert(1==0); <span class="comment">// FIXME: not correct yet</span>
<a name="l00611"></a>00611 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=pos.node;
<a name="l00612"></a>00612 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> curdepth=1;
<a name="l00613"></a>00613 <span class="keywordflow">while</span>(curdepth<dp) { <span class="comment">// go down one level</span>
<a name="l00614"></a>00614 <span class="keywordflow">while</span>(tmp->first_child==0) {
<a name="l00615"></a>00615 tmp=tmp->next_sibling;
<a name="l00616"></a>00616 <span class="keywordflow">if</span>(tmp==0)
<a name="l00617"></a>00617 <span class="keywordflow">throw</span> std::range_error(<span class="stringliteral">"tree: end_fixed out of range"</span>);
<a name="l00618"></a>00618 }
<a name="l00619"></a>00619 tmp=tmp->first_child;
<a name="l00620"></a>00620 ++curdepth;
<a name="l00621"></a>00621 }
<a name="l00622"></a>00622 <span class="keywordflow">return</span> tmp;
<a name="l00623"></a>00623 }
<a name="l00624"></a>00624
<a name="l00625"></a>00625 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00626"></a>00626 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">tree<T, tree_node_allocator>::begin</a>(<span class="keyword">const</span> iterator_base& pos)<span class="keyword"> const</span>
<a name="l00627"></a>00627 <span class="keyword"> </span>{
<a name="l00628"></a>00628 <span class="keywordflow">if</span>(pos.node->first_child==0) {
<a name="l00629"></a>00629 <span class="keywordflow">return</span> <a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>(pos);
<a name="l00630"></a>00630 }
<a name="l00631"></a>00631 <span class="keywordflow">return</span> pos.node->first_child;
<a name="l00632"></a>00632 }
<a name="l00633"></a>00633
<a name="l00634"></a>00634 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00635"></a>00635 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">tree<T, tree_node_allocator>::end</a>(<span class="keyword">const</span> iterator_base& pos)<span class="keyword"> const</span>
<a name="l00636"></a>00636 <span class="keyword"> </span>{
<a name="l00637"></a>00637 sibling_iterator ret(0);
<a name="l00638"></a>00638 ret.parent_=pos.node;
<a name="l00639"></a>00639 <span class="keywordflow">return</span> ret;
<a name="l00640"></a>00640 }
<a name="l00641"></a>00641
<a name="l00642"></a>00642 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00643"></a>00643 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l00644"></a>00644 iter <a class="code" href="classtree.html#c4fad296716ff3afde3556c598f41a7f">tree<T, tree_node_allocator>::parent</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>)<span class="keyword"> const</span>
<a name="l00645"></a>00645 <span class="keyword"> </span>{
<a name="l00646"></a>00646 assert(position.node!=0);
<a name="l00647"></a>00647 <span class="keywordflow">return</span> iter(position.node->parent);
<a name="l00648"></a>00648 }
<a name="l00649"></a>00649
<a name="l00650"></a>00650 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00651"></a>00651 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l00652"></a>00652 iter <a class="code" href="classtree.html#291bee91cf202e130095b1867b9bd356">tree<T, tree_node_allocator>::previous_sibling</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>)<span class="keyword"> const</span>
<a name="l00653"></a>00653 <span class="keyword"> </span>{
<a name="l00654"></a>00654 assert(position.node!=0);
<a name="l00655"></a>00655 iter ret(position);
<a name="l00656"></a>00656 ret.node=position.node->prev_sibling;
<a name="l00657"></a>00657 <span class="keywordflow">return</span> ret;
<a name="l00658"></a>00658 }
<a name="l00659"></a>00659
<a name="l00660"></a>00660 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00661"></a>00661 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l00662"></a>00662 iter <a class="code" href="classtree.html#7a09a0eeccff8c96d1351859c007d2ff">tree<T, tree_node_allocator>::next_sibling</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>)<span class="keyword"> const</span>
<a name="l00663"></a>00663 <span class="keyword"> </span>{
<a name="l00664"></a>00664 assert(position.node!=0);
<a name="l00665"></a>00665 iter ret(position);
<a name="l00666"></a>00666 ret.node=position.node->next_sibling;
<a name="l00667"></a>00667 <span class="keywordflow">return</span> ret;
<a name="l00668"></a>00668 }
<a name="l00669"></a>00669
<a name="l00670"></a>00670 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00671"></a>00671 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l00672"></a>00672 iter <a class="code" href="classtree.html#012d4dbcc58401d8a1f9e97ec41898b9">tree<T, tree_node_allocator>::next_at_same_depth</a>(iter <a class="code" href="messages_8cpp.html#4da8008b6f110050513003edf67a2495">position</a>)<span class="keyword"> const</span>
<a name="l00673"></a>00673 <span class="keyword"> </span>{
<a name="l00674"></a>00674 assert(position.node!=0);
<a name="l00675"></a>00675 iter ret(position);
<a name="l00676"></a>00676
<a name="l00677"></a>00677 <span class="keywordflow">if</span>(position.node->next_sibling) {
<a name="l00678"></a>00678 ret.node=position.node->next_sibling;
<a name="l00679"></a>00679 }
<a name="l00680"></a>00680 <span class="keywordflow">else</span> {
<a name="l00681"></a>00681 <span class="keywordtype">int</span> relative_depth=0;
<a name="l00682"></a>00682 upper:
<a name="l00683"></a>00683 <span class="keywordflow">do</span> {
<a name="l00684"></a>00684 ret.node=ret.node->parent;
<a name="l00685"></a>00685 <span class="keywordflow">if</span>(ret.node==0) <span class="keywordflow">return</span> ret;
<a name="l00686"></a>00686 --relative_depth;
<a name="l00687"></a>00687 } <span class="keywordflow">while</span>(ret.node->next_sibling==0);
<a name="l00688"></a>00688 lower:
<a name="l00689"></a>00689 ret.node=ret.node->next_sibling;
<a name="l00690"></a>00690 <span class="keywordflow">while</span>(ret.node->first_child==0) {
<a name="l00691"></a>00691 <span class="keywordflow">if</span>(ret.node->next_sibling==0)
<a name="l00692"></a>00692 <span class="keywordflow">goto</span> upper;
<a name="l00693"></a>00693 ret.node=ret.node->next_sibling;
<a name="l00694"></a>00694 <span class="keywordflow">if</span>(ret.node==0) <span class="keywordflow">return</span> ret;
<a name="l00695"></a>00695 }
<a name="l00696"></a>00696 <span class="keywordflow">while</span>(relative_depth<0 && ret.node->first_child!=0) {
<a name="l00697"></a>00697 ret.node=ret.node->first_child;
<a name="l00698"></a>00698 ++relative_depth;
<a name="l00699"></a>00699 }
<a name="l00700"></a>00700 <span class="keywordflow">if</span>(relative_depth<0) {
<a name="l00701"></a>00701 <span class="keywordflow">if</span>(ret.node->next_sibling==0) <span class="keywordflow">goto</span> upper;
<a name="l00702"></a>00702 <span class="keywordflow">else</span> <span class="keywordflow">goto</span> lower;
<a name="l00703"></a>00703 }
<a name="l00704"></a>00704 }
<a name="l00705"></a>00705 <span class="keywordflow">return</span> ret;
<a name="l00706"></a>00706 }
<a name="l00707"></a>00707
<a name="l00708"></a>00708 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00709"></a>00709 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l00710"></a>00710 iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">tree<T, tree_node_allocator>::append_child</a>(iter position)
<a name="l00711"></a>00711 {
<a name="l00712"></a>00712 assert(position.node!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>);
<a name="l00713"></a>00713
<a name="l00714"></a>00714 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00715"></a>00715 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data);
<a name="l00716"></a>00716 tmp->first_child=0;
<a name="l00717"></a>00717 tmp->last_child=0;
<a name="l00718"></a>00718
<a name="l00719"></a>00719 tmp->parent=position.node;
<a name="l00720"></a>00720 <span class="keywordflow">if</span>(position.node->last_child!=0) {
<a name="l00721"></a>00721 position.node->last_child->next_sibling=tmp;
<a name="l00722"></a>00722 }
<a name="l00723"></a>00723 <span class="keywordflow">else</span> {
<a name="l00724"></a>00724 position.node->first_child=tmp;
<a name="l00725"></a>00725 }
<a name="l00726"></a>00726 tmp->prev_sibling=position.node->last_child;
<a name="l00727"></a>00727 position.node->last_child=tmp;
<a name="l00728"></a>00728 tmp->next_sibling=0;
<a name="l00729"></a>00729 <span class="keywordflow">return</span> tmp;
<a name="l00730"></a>00730 }
<a name="l00731"></a>00731
<a name="l00732"></a>00732 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00733"></a>00733 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00734"></a>00734 iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">tree<T, tree_node_allocator>::append_child</a>(iter position, <span class="keyword">const</span> T& x)
<a name="l00735"></a>00735 {
<a name="l00736"></a>00736 <span class="comment">// If your program fails here you probably used 'append_child' to add the top</span>
<a name="l00737"></a>00737 <span class="comment">// node to an empty tree. From version 1.45 the top element should be added</span>
<a name="l00738"></a>00738 <span class="comment">// using 'insert'. See the documentation for further information, and sorry about</span>
<a name="l00739"></a>00739 <span class="comment">// the API change.</span>
<a name="l00740"></a>00740 assert(position.node!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>);
<a name="l00741"></a>00741
<a name="l00742"></a>00742 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00743"></a>00743 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data, x);
<a name="l00744"></a>00744 tmp->first_child=0;
<a name="l00745"></a>00745 tmp->last_child=0;
<a name="l00746"></a>00746
<a name="l00747"></a>00747 tmp->parent=position.node;
<a name="l00748"></a>00748 <span class="keywordflow">if</span>(position.node->last_child!=0) {
<a name="l00749"></a>00749 position.node->last_child->next_sibling=tmp;
<a name="l00750"></a>00750 }
<a name="l00751"></a>00751 <span class="keywordflow">else</span> {
<a name="l00752"></a>00752 position.node->first_child=tmp;
<a name="l00753"></a>00753 }
<a name="l00754"></a>00754 tmp->prev_sibling=position.node->last_child;
<a name="l00755"></a>00755 position.node->last_child=tmp;
<a name="l00756"></a>00756 tmp->next_sibling=0;
<a name="l00757"></a>00757 <span class="keywordflow">return</span> tmp;
<a name="l00758"></a>00758 }
<a name="l00759"></a>00759
<a name="l00760"></a>00760 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00761"></a>00761 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00762"></a>00762 iter <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">tree<T, tree_node_allocator>::append_child</a>(iter position, iter other)
<a name="l00763"></a>00763 {
<a name="l00764"></a>00764 assert(position.node!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>);
<a name="l00765"></a>00765
<a name="l00766"></a>00766 sibling_iterator aargh=<a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(position, <a class="code" href="classtree.html#1e7bcd21e7420f7922a1bca79080acfa">value_type</a>());
<a name="l00767"></a>00767 <span class="keywordflow">return</span> <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(aargh, other);
<a name="l00768"></a>00768 }
<a name="l00769"></a>00769
<a name="l00770"></a>00770 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00771"></a>00771 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00772"></a>00772 iter <a class="code" href="classtree.html#92ab22e0a98d8899c0d1b6c9d0a85465">tree<T, tree_node_allocator>::append_children</a>(iter position, sibling_iterator from, sibling_iterator to)
<a name="l00773"></a>00773 {
<a name="l00774"></a>00774 iter ret=from;
<a name="l00775"></a>00775
<a name="l00776"></a>00776 <span class="keywordflow">while</span>(from!=to) {
<a name="l00777"></a>00777 <a class="code" href="classtree.html#d66d55d58b48ce0a8d7a5b41abe923d5">insert_subtree</a>(position.end(), from);
<a name="l00778"></a>00778 ++from;
<a name="l00779"></a>00779 }
<a name="l00780"></a>00780 <span class="keywordflow">return</span> ret;
<a name="l00781"></a>00781 }
<a name="l00782"></a>00782
<a name="l00783"></a>00783 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00784"></a>00784 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a> <a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">tree<T, tree_node_allocator>::set_head</a>(<span class="keyword">const</span> T& x)
<a name="l00785"></a>00785 {
<a name="l00786"></a>00786 assert(<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>==<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>);
<a name="l00787"></a>00787 <span class="keywordflow">return</span> <a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">insert</a>(<a class="code" href="classtree.html#2079982538b88d21fe1ccea34fe7ce0e">iterator</a>(<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>), x);
<a name="l00788"></a>00788 }
<a name="l00789"></a>00789
<a name="l00790"></a>00790 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00791"></a>00791 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00792"></a>00792 iter <a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">tree<T, tree_node_allocator>::insert</a>(iter position, <span class="keyword">const</span> T& x)
<a name="l00793"></a>00793 {
<a name="l00794"></a>00794 <span class="keywordflow">if</span>(position.node==0) {
<a name="l00795"></a>00795 position.node=<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>; <span class="comment">// Backward compatibility: when calling insert on a null node,</span>
<a name="l00796"></a>00796 <span class="comment">// insert before the feet.</span>
<a name="l00797"></a>00797 }
<a name="l00798"></a>00798 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00799"></a>00799 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data, x);
<a name="l00800"></a>00800 tmp->first_child=0;
<a name="l00801"></a>00801 tmp->last_child=0;
<a name="l00802"></a>00802
<a name="l00803"></a>00803 tmp->parent=position.node->parent;
<a name="l00804"></a>00804 tmp->next_sibling=position.node;
<a name="l00805"></a>00805 tmp->prev_sibling=position.node->prev_sibling;
<a name="l00806"></a>00806 position.node->prev_sibling=tmp;
<a name="l00807"></a>00807
<a name="l00808"></a>00808 <span class="keywordflow">if</span>(tmp->prev_sibling==0) {
<a name="l00809"></a>00809 <span class="keywordflow">if</span>(tmp->parent) <span class="comment">// when inserting nodes at the head, there is no parent</span>
<a name="l00810"></a>00810 tmp->parent->first_child=tmp;
<a name="l00811"></a>00811 }
<a name="l00812"></a>00812 <span class="keywordflow">else</span>
<a name="l00813"></a>00813 tmp->prev_sibling->next_sibling=tmp;
<a name="l00814"></a>00814 <span class="keywordflow">return</span> tmp;
<a name="l00815"></a>00815 }
<a name="l00816"></a>00816
<a name="l00817"></a>00817 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00818"></a>00818 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">tree<T, tree_node_allocator>::insert</a>(sibling_iterator position, <span class="keyword">const</span> T& x)
<a name="l00819"></a>00819 {
<a name="l00820"></a>00820 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00821"></a>00821 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data, x);
<a name="l00822"></a>00822 tmp->first_child=0;
<a name="l00823"></a>00823 tmp->last_child=0;
<a name="l00824"></a>00824
<a name="l00825"></a>00825 tmp->next_sibling=position.node;
<a name="l00826"></a>00826 <span class="keywordflow">if</span>(position.node==0) { <span class="comment">// iterator points to end of a subtree</span>
<a name="l00827"></a>00827 tmp->parent=position.parent_;
<a name="l00828"></a>00828 tmp->prev_sibling=position.range_last();
<a name="l00829"></a>00829 tmp->parent->last_child=tmp;
<a name="l00830"></a>00830 }
<a name="l00831"></a>00831 <span class="keywordflow">else</span> {
<a name="l00832"></a>00832 tmp->parent=position.node->parent;
<a name="l00833"></a>00833 tmp->prev_sibling=position.node->prev_sibling;
<a name="l00834"></a>00834 position.node->prev_sibling=tmp;
<a name="l00835"></a>00835 }
<a name="l00836"></a>00836
<a name="l00837"></a>00837 <span class="keywordflow">if</span>(tmp->prev_sibling==0) {
<a name="l00838"></a>00838 <span class="keywordflow">if</span>(tmp->parent) <span class="comment">// when inserting nodes at the head, there is no parent</span>
<a name="l00839"></a>00839 tmp->parent->first_child=tmp;
<a name="l00840"></a>00840 }
<a name="l00841"></a>00841 <span class="keywordflow">else</span>
<a name="l00842"></a>00842 tmp->prev_sibling->next_sibling=tmp;
<a name="l00843"></a>00843 <span class="keywordflow">return</span> tmp;
<a name="l00844"></a>00844 }
<a name="l00845"></a>00845
<a name="l00846"></a>00846 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00847"></a>00847 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00848"></a>00848 iter <a class="code" href="classtree.html#215ab56bd13f59c661eb2298e373ff3e">tree<T, tree_node_allocator>::insert_after</a>(iter position, <span class="keyword">const</span> T& x)
<a name="l00849"></a>00849 {
<a name="l00850"></a>00850 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00851"></a>00851 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data, x);
<a name="l00852"></a>00852 tmp->first_child=0;
<a name="l00853"></a>00853 tmp->last_child=0;
<a name="l00854"></a>00854
<a name="l00855"></a>00855 tmp->parent=position.node->parent;
<a name="l00856"></a>00856 tmp->prev_sibling=position.node;
<a name="l00857"></a>00857 tmp->next_sibling=position.node->next_sibling;
<a name="l00858"></a>00858 position.node->next_sibling=tmp;
<a name="l00859"></a>00859
<a name="l00860"></a>00860 <span class="keywordflow">if</span>(tmp->next_sibling==0) {
<a name="l00861"></a>00861 <span class="keywordflow">if</span>(tmp->parent) <span class="comment">// when inserting nodes at the head, there is no parent</span>
<a name="l00862"></a>00862 tmp->parent->last_child=tmp;
<a name="l00863"></a>00863 }
<a name="l00864"></a>00864 <span class="keywordflow">else</span> {
<a name="l00865"></a>00865 tmp->next_sibling->prev_sibling=tmp;
<a name="l00866"></a>00866 }
<a name="l00867"></a>00867 <span class="keywordflow">return</span> tmp;
<a name="l00868"></a>00868 }
<a name="l00869"></a>00869
<a name="l00870"></a>00870 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00871"></a>00871 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00872"></a>00872 iter <a class="code" href="classtree.html#d66d55d58b48ce0a8d7a5b41abe923d5">tree<T, tree_node_allocator>::insert_subtree</a>(iter position, <span class="keyword">const</span> iterator_base& subtree)
<a name="l00873"></a>00873 {
<a name="l00874"></a>00874 <span class="comment">// insert dummy</span>
<a name="l00875"></a>00875 iter it=<a class="code" href="classtree.html#c3d19d3a42f91618267674f2c236aad9">insert</a>(position, <a class="code" href="classtree.html#1e7bcd21e7420f7922a1bca79080acfa">value_type</a>());
<a name="l00876"></a>00876 <span class="comment">// replace dummy with subtree</span>
<a name="l00877"></a>00877 <span class="keywordflow">return</span> <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(it, <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">subtree</a>);
<a name="l00878"></a>00878 }
<a name="l00879"></a>00879
<a name="l00880"></a>00880 <span class="comment">// template <class T, class tree_node_allocator></span>
<a name="l00881"></a>00881 <span class="comment">// template <class iter></span>
<a name="l00882"></a>00882 <span class="comment">// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)</span>
<a name="l00883"></a>00883 <span class="comment">// {</span>
<a name="l00884"></a>00884 <span class="comment">// // insert dummy</span>
<a name="l00885"></a>00885 <span class="comment">// iter it(insert(position, value_type()));</span>
<a name="l00886"></a>00886 <span class="comment">// // replace dummy with subtree</span>
<a name="l00887"></a>00887 <span class="comment">// return replace(it, subtree);</span>
<a name="l00888"></a>00888 <span class="comment">// }</span>
<a name="l00889"></a>00889
<a name="l00890"></a>00890 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00891"></a>00891 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00892"></a>00892 iter <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">tree<T, tree_node_allocator>::replace</a>(iter position, <span class="keyword">const</span> T& x)
<a name="l00893"></a>00893 {
<a name="l00894"></a>00894 <a class="code" href="namespacekp.html#a6813c11eeb1c091cdd1eff62de70914">kp::destructor</a>(&position.node->data);
<a name="l00895"></a>00895 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&position.node->data, x);
<a name="l00896"></a>00896 <span class="keywordflow">return</span> position;
<a name="l00897"></a>00897 }
<a name="l00898"></a>00898
<a name="l00899"></a>00899 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00900"></a>00900 <span class="keyword">template</span> <<span class="keyword">class</span> iter>
<a name="l00901"></a>00901 iter <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">tree<T, tree_node_allocator>::replace</a>(iter position, <span class="keyword">const</span> iterator_base& from)
<a name="l00902"></a>00902 {
<a name="l00903"></a>00903 assert(position.node!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>);
<a name="l00904"></a>00904 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *current_from=from.node;
<a name="l00905"></a>00905 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *start_from=from.node;
<a name="l00906"></a>00906 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *current_to =position.node;
<a name="l00907"></a>00907
<a name="l00908"></a>00908 <span class="comment">// replace the node at position with head of the replacement tree at from</span>
<a name="l00909"></a>00909 <a class="code" href="classtree.html#05d5fd71c206efc8ac30df5cd46176bc">erase_children</a>(position);
<a name="l00910"></a>00910 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* tmp = alloc_.allocate(1,0);
<a name="l00911"></a>00911 <a class="code" href="namespacekp.html#d1c6c23984a78bfc8336c7ca244d6f1c">kp::constructor</a>(&tmp->data, (*from));
<a name="l00912"></a>00912 tmp->first_child=0;
<a name="l00913"></a>00913 tmp->last_child=0;
<a name="l00914"></a>00914 <span class="keywordflow">if</span>(current_to->prev_sibling==0) {
<a name="l00915"></a>00915 current_to->parent->first_child=tmp;
<a name="l00916"></a>00916 }
<a name="l00917"></a>00917 <span class="keywordflow">else</span> {
<a name="l00918"></a>00918 current_to->prev_sibling->next_sibling=tmp;
<a name="l00919"></a>00919 }
<a name="l00920"></a>00920 tmp->prev_sibling=current_to->prev_sibling;
<a name="l00921"></a>00921 <span class="keywordflow">if</span>(current_to->next_sibling==0) {
<a name="l00922"></a>00922 current_to->parent->last_child=tmp;
<a name="l00923"></a>00923 }
<a name="l00924"></a>00924 <span class="keywordflow">else</span> {
<a name="l00925"></a>00925 current_to->next_sibling->prev_sibling=tmp;
<a name="l00926"></a>00926 }
<a name="l00927"></a>00927 tmp->next_sibling=current_to->next_sibling;
<a name="l00928"></a>00928 tmp->parent=current_to->parent;
<a name="l00929"></a>00929 <a class="code" href="namespacekp.html#a6813c11eeb1c091cdd1eff62de70914">kp::destructor</a>(&current_to->data);
<a name="l00930"></a>00930 alloc_.deallocate(current_to,1);
<a name="l00931"></a>00931 current_to=tmp;
<a name="l00932"></a>00932
<a name="l00933"></a>00933 <span class="comment">// only at this stage can we fix 'last'</span>
<a name="l00934"></a>00934 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *last=from.node->next_sibling;
<a name="l00935"></a>00935
<a name="l00936"></a>00936 pre_order_iterator toit=tmp;
<a name="l00937"></a>00937 <span class="comment">// copy all children</span>
<a name="l00938"></a>00938 <span class="keywordflow">do</span> {
<a name="l00939"></a>00939 assert(current_from!=0);
<a name="l00940"></a>00940 <span class="keywordflow">if</span>(current_from->first_child != 0) {
<a name="l00941"></a>00941 current_from=current_from->first_child;
<a name="l00942"></a>00942 toit=<a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(toit, current_from->data);
<a name="l00943"></a>00943 }
<a name="l00944"></a>00944 <span class="keywordflow">else</span> {
<a name="l00945"></a>00945 <span class="keywordflow">while</span>(current_from->next_sibling==0 && current_from!=start_from) {
<a name="l00946"></a>00946 current_from=current_from->parent;
<a name="l00947"></a>00947 toit=<a class="code" href="classtree.html#c4fad296716ff3afde3556c598f41a7f">parent</a>(toit);
<a name="l00948"></a>00948 assert(current_from!=0);
<a name="l00949"></a>00949 }
<a name="l00950"></a>00950 current_from=current_from->next_sibling;
<a name="l00951"></a>00951 <span class="keywordflow">if</span>(current_from!=last) {
<a name="l00952"></a>00952 toit=<a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(<a class="code" href="classtree.html#c4fad296716ff3afde3556c598f41a7f">parent</a>(toit), current_from->data);
<a name="l00953"></a>00953 }
<a name="l00954"></a>00954 }
<a name="l00955"></a>00955 } <span class="keywordflow">while</span>(current_from!=last);
<a name="l00956"></a>00956
<a name="l00957"></a>00957 <span class="keywordflow">return</span> current_to;
<a name="l00958"></a>00958 }
<a name="l00959"></a>00959
<a name="l00960"></a>00960 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l00961"></a>00961 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">tree<T, tree_node_allocator>::replace</a>(
<a name="l00962"></a>00962 sibling_iterator orig_begin,
<a name="l00963"></a>00963 sibling_iterator orig_end,
<a name="l00964"></a>00964 sibling_iterator new_begin,
<a name="l00965"></a>00965 sibling_iterator new_end)
<a name="l00966"></a>00966 {
<a name="l00967"></a>00967 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *orig_first=orig_begin.node;
<a name="l00968"></a>00968 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *new_first=new_begin.node;
<a name="l00969"></a>00969 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *orig_last=orig_first;
<a name="l00970"></a>00970 <span class="keywordflow">while</span>((++orig_begin)!=orig_end)
<a name="l00971"></a>00971 orig_last=orig_last->next_sibling;
<a name="l00972"></a>00972 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *new_last=new_first;
<a name="l00973"></a>00973 <span class="keywordflow">while</span>((++new_begin)!=new_end)
<a name="l00974"></a>00974 new_last=new_last->next_sibling;
<a name="l00975"></a>00975
<a name="l00976"></a>00976 <span class="comment">// insert all siblings in new_first..new_last before orig_first</span>
<a name="l00977"></a>00977 <span class="keywordtype">bool</span> first=<span class="keyword">true</span>;
<a name="l00978"></a>00978 pre_order_iterator ret;
<a name="l00979"></a>00979 <span class="keywordflow">while</span>(1==1) {
<a name="l00980"></a>00980 pre_order_iterator tt=<a class="code" href="classtree.html#d66d55d58b48ce0a8d7a5b41abe923d5">insert_subtree</a>(pre_order_iterator(orig_first), pre_order_iterator(new_first));
<a name="l00981"></a>00981 <span class="keywordflow">if</span>(first) {
<a name="l00982"></a>00982 ret=tt;
<a name="l00983"></a>00983 first=<span class="keyword">false</span>;
<a name="l00984"></a>00984 }
<a name="l00985"></a>00985 <span class="keywordflow">if</span>(new_first==new_last)
<a name="l00986"></a>00986 <span class="keywordflow">break</span>;
<a name="l00987"></a>00987 new_first=new_first->next_sibling;
<a name="l00988"></a>00988 }
<a name="l00989"></a>00989
<a name="l00990"></a>00990 <span class="comment">// erase old range of siblings</span>
<a name="l00991"></a>00991 <span class="keywordtype">bool</span> last=<span class="keyword">false</span>;
<a name="l00992"></a>00992 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *next=orig_first;
<a name="l00993"></a>00993 <span class="keywordflow">while</span>(1==1) {
<a name="l00994"></a>00994 <span class="keywordflow">if</span>(next==orig_last)
<a name="l00995"></a>00995 last=<span class="keyword">true</span>;
<a name="l00996"></a>00996 next=next->next_sibling;
<a name="l00997"></a>00997 <a class="code" href="classtree.html#3eb424c89446ae17a747d2aca2cdda4b">erase</a>((pre_order_iterator)orig_first);
<a name="l00998"></a>00998 <span class="keywordflow">if</span>(last)
<a name="l00999"></a>00999 <span class="keywordflow">break</span>;
<a name="l01000"></a>01000 orig_first=next;
<a name="l01001"></a>01001 }
<a name="l01002"></a>01002 <span class="keywordflow">return</span> ret;
<a name="l01003"></a>01003 }
<a name="l01004"></a>01004
<a name="l01005"></a>01005 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01006"></a>01006 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l01007"></a>01007 iter <a class="code" href="classtree.html#479c8e3f748608a9b9fb91e58e18998c">tree<T, tree_node_allocator>::flatten</a>(iter position)
<a name="l01008"></a>01008 {
<a name="l01009"></a>01009 <span class="keywordflow">if</span>(position.node->first_child==0)
<a name="l01010"></a>01010 <span class="keywordflow">return</span> position;
<a name="l01011"></a>01011
<a name="l01012"></a>01012 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=position.node->first_child;
<a name="l01013"></a>01013 <span class="keywordflow">while</span>(tmp) {
<a name="l01014"></a>01014 tmp->parent=position.node->parent;
<a name="l01015"></a>01015 tmp=tmp->next_sibling;
<a name="l01016"></a>01016 }
<a name="l01017"></a>01017 <span class="keywordflow">if</span>(position.node->next_sibling) {
<a name="l01018"></a>01018 position.node->last_child->next_sibling=position.node->next_sibling;
<a name="l01019"></a>01019 position.node->next_sibling->prev_sibling=position.node->last_child;
<a name="l01020"></a>01020 }
<a name="l01021"></a>01021 <span class="keywordflow">else</span> {
<a name="l01022"></a>01022 position.node->parent->last_child=position.node->last_child;
<a name="l01023"></a>01023 }
<a name="l01024"></a>01024 position.node->next_sibling=position.node->first_child;
<a name="l01025"></a>01025 position.node->next_sibling->prev_sibling=position.node;
<a name="l01026"></a>01026 position.node->first_child=0;
<a name="l01027"></a>01027 position.node->last_child=0;
<a name="l01028"></a>01028
<a name="l01029"></a>01029 <span class="keywordflow">return</span> position;
<a name="l01030"></a>01030 }
<a name="l01031"></a>01031
<a name="l01032"></a>01032
<a name="l01033"></a>01033 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01034"></a>01034 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l01035"></a>01035 iter <a class="code" href="classtree.html#32b88523e2d5b6c78381b7da9455be5e">tree<T, tree_node_allocator>::reparent</a>(iter position, sibling_iterator begin, sibling_iterator end)
<a name="l01036"></a>01036 {
<a name="l01037"></a>01037 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *first=begin.node;
<a name="l01038"></a>01038 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *last=first;
<a name="l01039"></a>01039 <span class="keywordflow">if</span>(begin==end) <span class="keywordflow">return</span> begin;
<a name="l01040"></a>01040 <span class="comment">// determine last node</span>
<a name="l01041"></a>01041 <span class="keywordflow">while</span>((++begin)!=end) {
<a name="l01042"></a>01042 last=last->next_sibling;
<a name="l01043"></a>01043 }
<a name="l01044"></a>01044 <span class="comment">// move subtree</span>
<a name="l01045"></a>01045 <span class="keywordflow">if</span>(first->prev_sibling==0) {
<a name="l01046"></a>01046 first->parent->first_child=last->next_sibling;
<a name="l01047"></a>01047 }
<a name="l01048"></a>01048 <span class="keywordflow">else</span> {
<a name="l01049"></a>01049 first->prev_sibling->next_sibling=last->next_sibling;
<a name="l01050"></a>01050 }
<a name="l01051"></a>01051 <span class="keywordflow">if</span>(last->next_sibling==0) {
<a name="l01052"></a>01052 last->parent->last_child=first->prev_sibling;
<a name="l01053"></a>01053 }
<a name="l01054"></a>01054 <span class="keywordflow">else</span> {
<a name="l01055"></a>01055 last->next_sibling->prev_sibling=first->prev_sibling;
<a name="l01056"></a>01056 }
<a name="l01057"></a>01057 <span class="keywordflow">if</span>(position.node->first_child==0) {
<a name="l01058"></a>01058 position.node->first_child=first;
<a name="l01059"></a>01059 position.node->last_child=last;
<a name="l01060"></a>01060 first->prev_sibling=0;
<a name="l01061"></a>01061 }
<a name="l01062"></a>01062 <span class="keywordflow">else</span> {
<a name="l01063"></a>01063 position.node->last_child->next_sibling=first;
<a name="l01064"></a>01064 first->prev_sibling=position.node->last_child;
<a name="l01065"></a>01065 position.node->last_child=last;
<a name="l01066"></a>01066 }
<a name="l01067"></a>01067 last->next_sibling=0;
<a name="l01068"></a>01068
<a name="l01069"></a>01069 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *pos=first;
<a name="l01070"></a>01070 <span class="keywordflow">while</span>(1==1) {
<a name="l01071"></a>01071 pos->parent=position.node;
<a name="l01072"></a>01072 <span class="keywordflow">if</span>(pos==last) <span class="keywordflow">break</span>;
<a name="l01073"></a>01073 pos=pos->next_sibling;
<a name="l01074"></a>01074 }
<a name="l01075"></a>01075
<a name="l01076"></a>01076 <span class="keywordflow">return</span> first;
<a name="l01077"></a>01077 }
<a name="l01078"></a>01078
<a name="l01079"></a>01079 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01080"></a>01080 <span class="keyword">template</span> <<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#32b88523e2d5b6c78381b7da9455be5e">tree<T, tree_node_allocator>::reparent</a>(iter position, iter from)
<a name="l01081"></a>01081 {
<a name="l01082"></a>01082 <span class="keywordflow">if</span>(from.node->first_child==0) <span class="keywordflow">return</span> position;
<a name="l01083"></a>01083 <span class="keywordflow">return</span> <a class="code" href="classtree.html#32b88523e2d5b6c78381b7da9455be5e">reparent</a>(position, from.node->first_child, end(from));
<a name="l01084"></a>01084 }
<a name="l01085"></a>01085
<a name="l01086"></a>01086 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01087"></a>01087 <span class="keyword">template</span> <<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#e7f72ba46cd061f71720c731b4a9bf63">tree<T, tree_node_allocator>::move_after</a>(iter target, iter source)
<a name="l01088"></a>01088 {
<a name="l01089"></a>01089 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *dst=target.node;
<a name="l01090"></a>01090 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *src=source.node;
<a name="l01091"></a>01091 assert(dst);
<a name="l01092"></a>01092 assert(src);
<a name="l01093"></a>01093
<a name="l01094"></a>01094 <span class="keywordflow">if</span>(dst==src) <span class="keywordflow">return</span> source;
<a name="l01095"></a>01095
<a name="l01096"></a>01096 <span class="comment">// take src out of the tree</span>
<a name="l01097"></a>01097 <span class="keywordflow">if</span>(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
<a name="l01098"></a>01098 <span class="keywordflow">else</span> src->parent->first_child=src->next_sibling;
<a name="l01099"></a>01099 <span class="keywordflow">if</span>(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
<a name="l01100"></a>01100 <span class="keywordflow">else</span> src->parent->last_child=src->prev_sibling;
<a name="l01101"></a>01101
<a name="l01102"></a>01102 <span class="comment">// connect it to the new point</span>
<a name="l01103"></a>01103 <span class="keywordflow">if</span>(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
<a name="l01104"></a>01104 <span class="keywordflow">else</span> dst->parent->last_child=src;
<a name="l01105"></a>01105 src->next_sibling=dst->next_sibling;
<a name="l01106"></a>01106 dst->next_sibling=src;
<a name="l01107"></a>01107 src->prev_sibling=dst;
<a name="l01108"></a>01108 src->parent=dst->parent;
<a name="l01109"></a>01109 <span class="keywordflow">return</span> src;
<a name="l01110"></a>01110 }
<a name="l01111"></a>01111
<a name="l01112"></a>01112
<a name="l01113"></a>01113 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01114"></a>01114 <span class="keyword">template</span> <<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#b45aa15042445a81b13873d3ef4a2e86">tree<T, tree_node_allocator>::move_before</a>(iter target, iter source)
<a name="l01115"></a>01115 {
<a name="l01116"></a>01116 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *dst=target.node;
<a name="l01117"></a>01117 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *src=source.node;
<a name="l01118"></a>01118 assert(dst);
<a name="l01119"></a>01119 assert(src);
<a name="l01120"></a>01120
<a name="l01121"></a>01121 <span class="keywordflow">if</span>(dst==src) <span class="keywordflow">return</span> source;
<a name="l01122"></a>01122
<a name="l01123"></a>01123 <span class="comment">// take src out of the tree</span>
<a name="l01124"></a>01124 <span class="keywordflow">if</span>(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
<a name="l01125"></a>01125 <span class="keywordflow">else</span> src->parent->first_child=src->next_sibling;
<a name="l01126"></a>01126 <span class="keywordflow">if</span>(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
<a name="l01127"></a>01127 <span class="keywordflow">else</span> src->parent->last_child=src->prev_sibling;
<a name="l01128"></a>01128
<a name="l01129"></a>01129 <span class="comment">// connect it to the new point</span>
<a name="l01130"></a>01130 <span class="keywordflow">if</span>(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
<a name="l01131"></a>01131 <span class="keywordflow">else</span> dst->parent->first_child=src;
<a name="l01132"></a>01132 src->prev_sibling=dst->prev_sibling;
<a name="l01133"></a>01133 dst->prev_sibling=src;
<a name="l01134"></a>01134 src->next_sibling=dst;
<a name="l01135"></a>01135 src->parent=dst->parent;
<a name="l01136"></a>01136 <span class="keywordflow">return</span> src;
<a name="l01137"></a>01137 }
<a name="l01138"></a>01138
<a name="l01139"></a>01139 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01140"></a>01140 <span class="keyword">template</span> <<span class="keyword">typename</span> iter> iter <a class="code" href="classtree.html#a4f8b906b2758eec530e28387b819284">tree<T, tree_node_allocator>::move_ontop</a>(iter target, iter source)
<a name="l01141"></a>01141 {
<a name="l01142"></a>01142 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *dst=target.node;
<a name="l01143"></a>01143 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *src=source.node;
<a name="l01144"></a>01144 assert(dst);
<a name="l01145"></a>01145 assert(src);
<a name="l01146"></a>01146
<a name="l01147"></a>01147 <span class="keywordflow">if</span>(dst==src) <span class="keywordflow">return</span> source;
<a name="l01148"></a>01148
<a name="l01149"></a>01149 <span class="comment">// remember connection points</span>
<a name="l01150"></a>01150 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *b_prev_sibling=dst->prev_sibling;
<a name="l01151"></a>01151 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *b_next_sibling=dst->next_sibling;
<a name="l01152"></a>01152 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *b_parent=dst->parent;
<a name="l01153"></a>01153
<a name="l01154"></a>01154 <span class="comment">// remove target</span>
<a name="l01155"></a>01155 <a class="code" href="classtree.html#3eb424c89446ae17a747d2aca2cdda4b">erase</a>(target);
<a name="l01156"></a>01156
<a name="l01157"></a>01157 <span class="comment">// take src out of the tree</span>
<a name="l01158"></a>01158 <span class="keywordflow">if</span>(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
<a name="l01159"></a>01159 <span class="keywordflow">else</span> src->parent->first_child=src->next_sibling;
<a name="l01160"></a>01160 <span class="keywordflow">if</span>(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
<a name="l01161"></a>01161 <span class="keywordflow">else</span> src->parent->last_child=src->prev_sibling;
<a name="l01162"></a>01162
<a name="l01163"></a>01163 <span class="comment">// connect it to the new point</span>
<a name="l01164"></a>01164 <span class="keywordflow">if</span>(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
<a name="l01165"></a>01165 <span class="keywordflow">else</span> b_parent->first_child=src;
<a name="l01166"></a>01166 <span class="keywordflow">if</span>(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
<a name="l01167"></a>01167 <span class="keywordflow">else</span> b_parent->last_child=src;
<a name="l01168"></a>01168 src->prev_sibling=b_prev_sibling;
<a name="l01169"></a>01169 src->next_sibling=b_next_sibling;
<a name="l01170"></a>01170 src->parent=b_parent;
<a name="l01171"></a>01171 <span class="keywordflow">return</span> src;
<a name="l01172"></a>01172 }
<a name="l01173"></a>01173
<a name="l01174"></a>01174 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01175"></a>01175 <span class="keywordtype">void</span> <a class="code" href="classtree.html#1e3cd901f8f8d8a3da0e1d32e9282db1">tree<T, tree_node_allocator>::merge</a>(sibling_iterator to1, sibling_iterator to2,
<a name="l01176"></a>01176 sibling_iterator from1, sibling_iterator from2,
<a name="l01177"></a>01177 <span class="keywordtype">bool</span> duplicate_leaves)
<a name="l01178"></a>01178 {
<a name="l01179"></a>01179 sibling_iterator fnd;
<a name="l01180"></a>01180 <span class="keywordflow">while</span>(from1!=from2) {
<a name="l01181"></a>01181 <span class="keywordflow">if</span>((fnd=std::find(to1, to2, (*from1))) != to2) { <span class="comment">// element found</span>
<a name="l01182"></a>01182 <span class="keywordflow">if</span>(from1.begin()==from1.end()) { <span class="comment">// full depth reached</span>
<a name="l01183"></a>01183 <span class="keywordflow">if</span>(duplicate_leaves)
<a name="l01184"></a>01184 <a class="code" href="classtree.html#8d68e95f5088d48cb54fd6ae381729f0">append_child</a>(<a class="code" href="classtree.html#c4fad296716ff3afde3556c598f41a7f">parent</a>(to1), (*from1));
<a name="l01185"></a>01185 }
<a name="l01186"></a>01186 <span class="keywordflow">else</span> { <span class="comment">// descend further</span>
<a name="l01187"></a>01187 <a class="code" href="classtree.html#1e3cd901f8f8d8a3da0e1d32e9282db1">merge</a>(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
<a name="l01188"></a>01188 }
<a name="l01189"></a>01189 }
<a name="l01190"></a>01190 <span class="keywordflow">else</span> { <span class="comment">// element missing</span>
<a name="l01191"></a>01191 <a class="code" href="classtree.html#d66d55d58b48ce0a8d7a5b41abe923d5">insert_subtree</a>(to2, from1);
<a name="l01192"></a>01192 }
<a name="l01193"></a>01193 ++from1;
<a name="l01194"></a>01194 }
<a name="l01195"></a>01195 }
<a name="l01196"></a>01196
<a name="l01197"></a>01197
<a name="l01198"></a>01198 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01199"></a>01199 <span class="keywordtype">void</span> <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">tree<T, tree_node_allocator>::sort</a>(sibling_iterator from, sibling_iterator to, <span class="keywordtype">bool</span> deep)
<a name="l01200"></a>01200 {
<a name="l01201"></a>01201 std::less<T> comp;
<a name="l01202"></a>01202 <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">sort</a>(from, to, comp, deep);
<a name="l01203"></a>01203 }
<a name="l01204"></a>01204
<a name="l01205"></a>01205 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01206"></a>01206 <span class="keyword">template</span> <<span class="keyword">class</span> StrictWeakOrdering>
<a name="l01207"></a>01207 <span class="keywordtype">void</span> <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">tree<T, tree_node_allocator>::sort</a>(sibling_iterator from, sibling_iterator to,
<a name="l01208"></a>01208 StrictWeakOrdering comp, <span class="keywordtype">bool</span> deep)
<a name="l01209"></a>01209 {
<a name="l01210"></a>01210 <span class="keywordflow">if</span>(from==to) <span class="keywordflow">return</span>;
<a name="l01211"></a>01211 <span class="comment">// make list of sorted nodes</span>
<a name="l01212"></a>01212 <span class="comment">// CHECK: if multiset stores equivalent nodes in the order in which they</span>
<a name="l01213"></a>01213 <span class="comment">// are inserted, then this routine should be called 'stable_sort'.</span>
<a name="l01214"></a>01214 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
<a name="l01215"></a>01215 sibling_iterator it=from, it2=to;
<a name="l01216"></a>01216 <span class="keywordflow">while</span>(it != to) {
<a name="l01217"></a>01217 nodes.insert(it.node);
<a name="l01218"></a>01218 ++it;
<a name="l01219"></a>01219 }
<a name="l01220"></a>01220 <span class="comment">// reassemble</span>
<a name="l01221"></a>01221 --it2;
<a name="l01222"></a>01222
<a name="l01223"></a>01223 <span class="comment">// prev and next are the nodes before and after the sorted range</span>
<a name="l01224"></a>01224 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *prev=from.node->prev_sibling;
<a name="l01225"></a>01225 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *next=it2.node->next_sibling;
<a name="l01226"></a>01226 <span class="keyword">typename</span> std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> ><a class="code" href="classtree.html#2079982538b88d21fe1ccea34fe7ce0e">::iterator</a> nit=nodes.<a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">begin</a>(), eit=nodes.<a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">end</a>();
<a name="l01227"></a>01227 <span class="keywordflow">if</span>(prev==0) {
<a name="l01228"></a>01228 <span class="keywordflow">if</span>((*nit)->parent!=0) <span class="comment">// to catch "sorting the head" situations, when there is no parent</span>
<a name="l01229"></a>01229 (*nit)->parent->first_child=(*nit);
<a name="l01230"></a>01230 }
<a name="l01231"></a>01231 <span class="keywordflow">else</span> prev->next_sibling=(*nit);
<a name="l01232"></a>01232
<a name="l01233"></a>01233 --eit;
<a name="l01234"></a>01234 <span class="keywordflow">while</span>(nit!=eit) {
<a name="l01235"></a>01235 (*nit)->prev_sibling=prev;
<a name="l01236"></a>01236 <span class="keywordflow">if</span>(prev)
<a name="l01237"></a>01237 prev->next_sibling=(*nit);
<a name="l01238"></a>01238 prev=(*nit);
<a name="l01239"></a>01239 ++nit;
<a name="l01240"></a>01240 }
<a name="l01241"></a>01241 <span class="comment">// prev now points to the last-but-one node in the sorted range</span>
<a name="l01242"></a>01242 <span class="keywordflow">if</span>(prev)
<a name="l01243"></a>01243 prev->next_sibling=(*eit);
<a name="l01244"></a>01244
<a name="l01245"></a>01245 <span class="comment">// eit points to the last node in the sorted range.</span>
<a name="l01246"></a>01246 (*eit)->next_sibling=next;
<a name="l01247"></a>01247 (*eit)->prev_sibling=prev; <span class="comment">// missed in the loop above</span>
<a name="l01248"></a>01248 <span class="keywordflow">if</span>(next==0) {
<a name="l01249"></a>01249 <span class="keywordflow">if</span>((*eit)->parent!=0) <span class="comment">// to catch "sorting the head" situations, when there is no parent</span>
<a name="l01250"></a>01250 (*eit)->parent->last_child=(*eit);
<a name="l01251"></a>01251 }
<a name="l01252"></a>01252 <span class="keywordflow">else</span> next->prev_sibling=(*eit);
<a name="l01253"></a>01253
<a name="l01254"></a>01254 <span class="keywordflow">if</span>(deep) { <span class="comment">// sort the children of each node too</span>
<a name="l01255"></a>01255 sibling_iterator bcs(*nodes.begin());
<a name="l01256"></a>01256 sibling_iterator ecs(*eit);
<a name="l01257"></a>01257 ++ecs;
<a name="l01258"></a>01258 <span class="keywordflow">while</span>(bcs!=ecs) {
<a name="l01259"></a>01259 <a class="code" href="classtree.html#498ec42a5eb44cba8bf9ef6e7fd5db9e">sort</a>(<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(bcs), <a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>(bcs), comp, deep);
<a name="l01260"></a>01260 ++bcs;
<a name="l01261"></a>01261 }
<a name="l01262"></a>01262 }
<a name="l01263"></a>01263 }
<a name="l01264"></a>01264
<a name="l01265"></a>01265 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01266"></a>01266 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l01267"></a>01267 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">tree<T, tree_node_allocator>::equal</a>(<span class="keyword">const</span> iter& one_, <span class="keyword">const</span> iter& two, <span class="keyword">const</span> iter& three_)<span class="keyword"> const</span>
<a name="l01268"></a>01268 <span class="keyword"> </span>{
<a name="l01269"></a>01269 std::equal_to<T> comp;
<a name="l01270"></a>01270 <span class="keywordflow">return</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">equal</a>(one_, two, three_, comp);
<a name="l01271"></a>01271 }
<a name="l01272"></a>01272
<a name="l01273"></a>01273 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01274"></a>01274 <span class="keyword">template</span> <<span class="keyword">typename</span> iter>
<a name="l01275"></a>01275 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#5decf01c6fcd8516b8d1152fe574aabc">tree<T, tree_node_allocator>::equal_subtree</a>(<span class="keyword">const</span> iter& one_, <span class="keyword">const</span> iter& two_)<span class="keyword"> const</span>
<a name="l01276"></a>01276 <span class="keyword"> </span>{
<a name="l01277"></a>01277 std::equal_to<T> comp;
<a name="l01278"></a>01278 <span class="keywordflow">return</span> <a class="code" href="classtree.html#5decf01c6fcd8516b8d1152fe574aabc">equal_subtree</a>(one_, two_, comp);
<a name="l01279"></a>01279 }
<a name="l01280"></a>01280
<a name="l01281"></a>01281 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01282"></a>01282 <span class="keyword">template</span> <<span class="keyword">typename</span> iter, <span class="keyword">class</span> BinaryPredicate>
<a name="l01283"></a>01283 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">tree<T, tree_node_allocator>::equal</a>(<span class="keyword">const</span> iter& one_, <span class="keyword">const</span> iter& two, <span class="keyword">const</span> iter& three_, BinaryPredicate fun)<span class="keyword"> const</span>
<a name="l01284"></a>01284 <span class="keyword"> </span>{
<a name="l01285"></a>01285 pre_order_iterator one(one_), three(three_);
<a name="l01286"></a>01286
<a name="l01287"></a>01287 <span class="comment">// if(one==two && is_valid(three) && three.number_of_children()!=0)</span>
<a name="l01288"></a>01288 <span class="comment">// return false;</span>
<a name="l01289"></a>01289 <span class="keywordflow">while</span>(one!=two && <a class="code" href="classtree.html#9155b3955497913a965acf612caf02fd">is_valid</a>(three)) {
<a name="l01290"></a>01290 <span class="keywordflow">if</span>(!fun(*one,*three))
<a name="l01291"></a>01291 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01292"></a>01292 <span class="keywordflow">if</span>(one.number_of_children()!=three.number_of_children())
<a name="l01293"></a>01293 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01294"></a>01294 ++one;
<a name="l01295"></a>01295 ++three;
<a name="l01296"></a>01296 }
<a name="l01297"></a>01297 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01298"></a>01298 }
<a name="l01299"></a>01299
<a name="l01300"></a>01300 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01301"></a>01301 <span class="keyword">template</span> <<span class="keyword">typename</span> iter, <span class="keyword">class</span> BinaryPredicate>
<a name="l01302"></a>01302 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#5decf01c6fcd8516b8d1152fe574aabc">tree<T, tree_node_allocator>::equal_subtree</a>(<span class="keyword">const</span> iter& one_, <span class="keyword">const</span> iter& two_, BinaryPredicate fun)<span class="keyword"> const</span>
<a name="l01303"></a>01303 <span class="keyword"> </span>{
<a name="l01304"></a>01304 pre_order_iterator one(one_), two(two_);
<a name="l01305"></a>01305
<a name="l01306"></a>01306 <span class="keywordflow">if</span>(!fun(*one,*two)) <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01307"></a>01307 <span class="keywordflow">if</span>(<a class="code" href="classtree.html#bf7233c3c57bc8b844e4bb6b420727c4">number_of_children</a>(one)!=<a class="code" href="classtree.html#bf7233c3c57bc8b844e4bb6b420727c4">number_of_children</a>(two)) <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01308"></a>01308 <span class="keywordflow">return</span> <a class="code" href="classtree.html#066b1a4018f9ed74effee262980aaaae">equal</a>(<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(one),<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>(one),<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(two),fun);
<a name="l01309"></a>01309 }
<a name="l01310"></a>01310
<a name="l01311"></a>01311 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01312"></a>01312 <a class="code" href="classtree.html">tree<T, tree_node_allocator></a> <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">tree<T, tree_node_allocator>::subtree</a>(sibling_iterator from, sibling_iterator to)<span class="keyword"> const</span>
<a name="l01313"></a>01313 <span class="keyword"> </span>{
<a name="l01314"></a>01314 <a class="code" href="classtree.html">tree</a> tmp;
<a name="l01315"></a>01315 tmp.<a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">set_head</a>(<a class="code" href="classtree.html#1e7bcd21e7420f7922a1bca79080acfa">value_type</a>());
<a name="l01316"></a>01316 tmp.<a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(tmp.<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), tmp.<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>(), from, to);
<a name="l01317"></a>01317 <span class="keywordflow">return</span> tmp;
<a name="l01318"></a>01318 }
<a name="l01319"></a>01319
<a name="l01320"></a>01320 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01321"></a>01321 <span class="keywordtype">void</span> <a class="code" href="classtree.html#f7c1b796877be85cdf6912e3142313cf">tree<T, tree_node_allocator>::subtree</a>(<a class="code" href="classtree.html">tree</a>& tmp, sibling_iterator from, sibling_iterator to)<span class="keyword"> const</span>
<a name="l01322"></a>01322 <span class="keyword"> </span>{
<a name="l01323"></a>01323 tmp.<a class="code" href="classtree.html#f11d736ea971ab93651350161f5a7535">set_head</a>(<a class="code" href="classtree.html#1e7bcd21e7420f7922a1bca79080acfa">value_type</a>());
<a name="l01324"></a>01324 tmp.<a class="code" href="classtree.html#4885e968c82655ebebea5d0927b7e9f4">replace</a>(tmp.<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), tmp.<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>(), from, to);
<a name="l01325"></a>01325 }
<a name="l01326"></a>01326
<a name="l01327"></a>01327 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01328"></a>01328 <span class="keywordtype">int</span> <a class="code" href="classtree.html#efe4460d7a0f4c0e309649e3ebfe3c3d">tree<T, tree_node_allocator>::size</a>()<span class="keyword"> const</span>
<a name="l01329"></a>01329 <span class="keyword"> </span>{
<a name="l01330"></a>01330 <span class="keywordtype">int</span> i=0;
<a name="l01331"></a>01331 pre_order_iterator it=<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), eit=<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>();
<a name="l01332"></a>01332 <span class="keywordflow">while</span>(it!=eit) {
<a name="l01333"></a>01333 ++i;
<a name="l01334"></a>01334 ++it;
<a name="l01335"></a>01335 }
<a name="l01336"></a>01336 <span class="keywordflow">return</span> i;
<a name="l01337"></a>01337 }
<a name="l01338"></a>01338
<a name="l01339"></a>01339 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01340"></a>01340 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#e600fb282f7534e75811d14a1d1d0aba">tree<T, tree_node_allocator>::empty</a>()<span class="keyword"> const</span>
<a name="l01341"></a>01341 <span class="keyword"> </span>{
<a name="l01342"></a>01342 pre_order_iterator it=<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>(), eit=<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>();
<a name="l01343"></a>01343 <span class="keywordflow">return</span> (it==eit);
<a name="l01344"></a>01344 }
<a name="l01345"></a>01345
<a name="l01346"></a>01346 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01347"></a>01347 <span class="keywordtype">int</span> <a class="code" href="classtree.html#85338176eaaf8421fa0ef06d1d5e8e40">tree<T, tree_node_allocator>::depth</a>(<span class="keyword">const</span> iterator_base& it)<span class="keyword"> const</span>
<a name="l01348"></a>01348 <span class="keyword"> </span>{
<a name="l01349"></a>01349 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a>* pos=it.node;
<a name="l01350"></a>01350 assert(pos!=0);
<a name="l01351"></a>01351 <span class="keywordtype">int</span> ret=0;
<a name="l01352"></a>01352 <span class="keywordflow">while</span>(pos->parent!=0) {
<a name="l01353"></a>01353 pos=pos->parent;
<a name="l01354"></a>01354 ++ret;
<a name="l01355"></a>01355 }
<a name="l01356"></a>01356 <span class="keywordflow">return</span> ret;
<a name="l01357"></a>01357 }
<a name="l01358"></a>01358
<a name="l01359"></a>01359 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01360"></a>01360 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree.html#bf7233c3c57bc8b844e4bb6b420727c4">tree<T, tree_node_allocator>::number_of_children</a>(<span class="keyword">const</span> iterator_base& it)<span class="keyword"> const</span>
<a name="l01361"></a>01361 <span class="keyword"> </span>{
<a name="l01362"></a>01362 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *pos=it.node->first_child;
<a name="l01363"></a>01363 <span class="keywordflow">if</span>(pos==0) <span class="keywordflow">return</span> 0;
<a name="l01364"></a>01364
<a name="l01365"></a>01365 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ret=1;
<a name="l01366"></a>01366 <span class="comment">// while(pos!=it.node->last_child) {</span>
<a name="l01367"></a>01367 <span class="comment">// ++ret;</span>
<a name="l01368"></a>01368 <span class="comment">// pos=pos->next_sibling;</span>
<a name="l01369"></a>01369 <span class="comment">// }</span>
<a name="l01370"></a>01370 <span class="keywordflow">while</span>((pos=pos->next_sibling))
<a name="l01371"></a>01371 ++ret;
<a name="l01372"></a>01372 <span class="keywordflow">return</span> ret;
<a name="l01373"></a>01373 }
<a name="l01374"></a>01374
<a name="l01375"></a>01375 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01376"></a>01376 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree.html#f3613943778560ad57787486e071af12">tree<T, tree_node_allocator>::number_of_siblings</a>(<span class="keyword">const</span> iterator_base& it)<span class="keyword"> const</span>
<a name="l01377"></a>01377 <span class="keyword"> </span>{
<a name="l01378"></a>01378 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *pos=it.node;
<a name="l01379"></a>01379 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ret=0;
<a name="l01380"></a>01380 <span class="keywordflow">while</span>(pos->next_sibling &&
<a name="l01381"></a>01381 pos->next_sibling!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a> &&
<a name="l01382"></a>01382 pos-><a class="code" href="classtree__node__.html#195a647282d6ab1de50d9ac87aa42bce">next_sibling</a>!=<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>) {
<a name="l01383"></a>01383 ++ret;
<a name="l01384"></a>01384 pos=pos->next_sibling;
<a name="l01385"></a>01385 }
<a name="l01386"></a>01386 <span class="keywordflow">return</span> ret;
<a name="l01387"></a>01387 }
<a name="l01388"></a>01388
<a name="l01389"></a>01389 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01390"></a>01390 <span class="keywordtype">void</span> <a class="code" href="classtree.html#e842f9b70235bc2412b3c43bca759448">tree<T, tree_node_allocator>::swap</a>(sibling_iterator it)
<a name="l01391"></a>01391 {
<a name="l01392"></a>01392 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *nxt=it.node->next_sibling;
<a name="l01393"></a>01393 <span class="keywordflow">if</span>(nxt) {
<a name="l01394"></a>01394 <span class="keywordflow">if</span>(it.node->prev_sibling)
<a name="l01395"></a>01395 it.node->prev_sibling->next_sibling=nxt;
<a name="l01396"></a>01396 <span class="keywordflow">else</span>
<a name="l01397"></a>01397 it.node->parent->first_child=nxt;
<a name="l01398"></a>01398 nxt->prev_sibling=it.node->prev_sibling;
<a name="l01399"></a>01399 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *nxtnxt=nxt->next_sibling;
<a name="l01400"></a>01400 <span class="keywordflow">if</span>(nxtnxt)
<a name="l01401"></a>01401 nxtnxt->prev_sibling=it.node;
<a name="l01402"></a>01402 <span class="keywordflow">else</span>
<a name="l01403"></a>01403 it.node->parent->last_child=it.node;
<a name="l01404"></a>01404 nxt->next_sibling=it.node;
<a name="l01405"></a>01405 it.node->prev_sibling=nxt;
<a name="l01406"></a>01406 it.node->next_sibling=nxtnxt;
<a name="l01407"></a>01407 }
<a name="l01408"></a>01408 }
<a name="l01409"></a>01409
<a name="l01410"></a>01410 <span class="comment">// template <class BinaryPredicate></span>
<a name="l01411"></a>01411 <span class="comment">// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(</span>
<a name="l01412"></a>01412 <span class="comment">// sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to, </span>
<a name="l01413"></a>01413 <span class="comment">// BinaryPredicate fun) const</span>
<a name="l01414"></a>01414 <span class="comment">// {</span>
<a name="l01415"></a>01415 <span class="comment">// assert(1==0); // this routine is not finished yet.</span>
<a name="l01416"></a>01416 <span class="comment">// while(from!=to) {</span>
<a name="l01417"></a>01417 <span class="comment">// if(fun(*subfrom, *from)) {</span>
<a name="l01418"></a>01418 <span class="comment">// </span>
<a name="l01419"></a>01419 <span class="comment">// }</span>
<a name="l01420"></a>01420 <span class="comment">// }</span>
<a name="l01421"></a>01421 <span class="comment">// return to;</span>
<a name="l01422"></a>01422 <span class="comment">// }</span>
<a name="l01423"></a>01423
<a name="l01424"></a>01424 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01425"></a>01425 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#a860f37aa4ec8955ef18a9b1936f0665">tree<T, tree_node_allocator>::is_in_subtree</a>(<span class="keyword">const</span> iterator_base& it, <span class="keyword">const</span> iterator_base& begin,
<a name="l01426"></a>01426 <span class="keyword">const</span> iterator_base& end)<span class="keyword"> const</span>
<a name="l01427"></a>01427 <span class="keyword"> </span>{
<a name="l01428"></a>01428 <span class="comment">// FIXME: this should be optimised.</span>
<a name="l01429"></a>01429 pre_order_iterator tmp=<a class="code" href="classtree.html#b7835af8e94710f5b39486b67952200e">begin</a>;
<a name="l01430"></a>01430 <span class="keywordflow">while</span>(tmp!=<a class="code" href="classtree.html#fba36da36f09bdefc3c8a8b31443dc13">end</a>) {
<a name="l01431"></a>01431 <span class="keywordflow">if</span>(tmp==it) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01432"></a>01432 ++tmp;
<a name="l01433"></a>01433 }
<a name="l01434"></a>01434 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01435"></a>01435 }
<a name="l01436"></a>01436
<a name="l01437"></a>01437 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01438"></a>01438 <span class="keywordtype">bool</span> <a class="code" href="classtree.html#9155b3955497913a965acf612caf02fd">tree<T, tree_node_allocator>::is_valid</a>(<span class="keyword">const</span> iterator_base& it)<span class="keyword"> const</span>
<a name="l01439"></a>01439 <span class="keyword"> </span>{
<a name="l01440"></a>01440 <span class="keywordflow">if</span>(it.node==0 || it.node==<a class="code" href="classtree.html#e1dbb80115ba483e37d081a2256c239b">feet</a>) <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01441"></a>01441 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01442"></a>01442 }
<a name="l01443"></a>01443
<a name="l01444"></a>01444 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01445"></a>01445 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree.html#de5ec1ba55f94165062e50d01ec35d86">tree<T, tree_node_allocator>::index</a>(sibling_iterator it)<span class="keyword"> const</span>
<a name="l01446"></a>01446 <span class="keyword"> </span>{
<a name="l01447"></a>01447 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ind=0;
<a name="l01448"></a>01448 <span class="keywordflow">if</span>(it.node->parent==0) {
<a name="l01449"></a>01449 <span class="keywordflow">while</span>(it.node->prev_sibling!=<a class="code" href="classtree.html#10991cbf1497e125c0ef04d6e292e32b">head</a>) {
<a name="l01450"></a>01450 it.node=it.node->prev_sibling;
<a name="l01451"></a>01451 ++ind;
<a name="l01452"></a>01452 }
<a name="l01453"></a>01453 }
<a name="l01454"></a>01454 <span class="keywordflow">else</span> {
<a name="l01455"></a>01455 <span class="keywordflow">while</span>(it.node->prev_sibling!=0) {
<a name="l01456"></a>01456 it.node=it.node->prev_sibling;
<a name="l01457"></a>01457 ++ind;
<a name="l01458"></a>01458 }
<a name="l01459"></a>01459 }
<a name="l01460"></a>01460 <span class="keywordflow">return</span> ind;
<a name="l01461"></a>01461 }
<a name="l01462"></a>01462
<a name="l01463"></a>01463
<a name="l01464"></a>01464 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01465"></a>01465 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree.html#446c722c82607f8b3243a9153b665d19">tree<T, tree_node_allocator>::child</a>(<span class="keyword">const</span> iterator_base& it, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)<span class="keyword"> const</span>
<a name="l01466"></a>01466 <span class="keyword"> </span>{
<a name="l01467"></a>01467 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=it.node->first_child;
<a name="l01468"></a>01468 <span class="keywordflow">while</span>(num--) {
<a name="l01469"></a>01469 assert(tmp!=0);
<a name="l01470"></a>01470 tmp=tmp->next_sibling;
<a name="l01471"></a>01471 }
<a name="l01472"></a>01472 <span class="keywordflow">return</span> tmp;
<a name="l01473"></a>01473 }
<a name="l01474"></a>01474
<a name="l01475"></a>01475
<a name="l01476"></a>01476
<a name="l01477"></a>01477
<a name="l01478"></a>01478 <span class="comment">// Iterator base</span>
<a name="l01479"></a>01479
<a name="l01480"></a>01480 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01481"></a>01481 <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">tree<T, tree_node_allocator>::iterator_base::iterator_base</a>()
<a name="l01482"></a>01482 : node(0), skip_current_children_(<a class="code" href="inc_2libofx_8h.html#65e9886d74aaee76545e83dd09011727">false</a>)
<a name="l01483"></a>01483 {
<a name="l01484"></a>01484 }
<a name="l01485"></a>01485
<a name="l01486"></a>01486 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01487"></a>01487 <a class="code" href="classtree_1_1iterator__base.html#1be2e6802acca5f281ddc7e5d67bd61c">tree<T, tree_node_allocator>::iterator_base::iterator_base</a>(tree_node *tn)
<a name="l01488"></a>01488 : node(tn), skip_current_children_(<a class="code" href="inc_2libofx_8h.html#65e9886d74aaee76545e83dd09011727">false</a>)
<a name="l01489"></a>01489 {
<a name="l01490"></a>01490 }
<a name="l01491"></a>01491
<a name="l01492"></a>01492 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01493"></a>01493 T& <a class="code" href="classtree_1_1iterator__base.html#a5d7acb4ad37b640d3fa7dec6da4896b">tree<T, tree_node_allocator>::iterator_base::operator*</a>()<span class="keyword"> const</span>
<a name="l01494"></a>01494 <span class="keyword"> </span>{
<a name="l01495"></a>01495 <span class="keywordflow">return</span> node->data;
<a name="l01496"></a>01496 }
<a name="l01497"></a>01497
<a name="l01498"></a>01498 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01499"></a>01499 T* <a class="code" href="classtree_1_1iterator__base.html#8f48a56f39396b1e6e5a7b44f603b871">tree<T, tree_node_allocator>::iterator_base::operator-></a>()<span class="keyword"> const</span>
<a name="l01500"></a>01500 <span class="keyword"> </span>{
<a name="l01501"></a>01501 <span class="keywordflow">return</span> &(node->data);
<a name="l01502"></a>01502 }
<a name="l01503"></a>01503
<a name="l01504"></a>01504 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01505"></a>01505 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1post__order__iterator.html#c3f88c8437a5cb33d6e2af8ac1a67356">tree<T, tree_node_allocator>::post_order_iterator::operator!=</a>(<span class="keyword">const</span> post_order_iterator& other)<span class="keyword"> const</span>
<a name="l01506"></a>01506 <span class="keyword"> </span>{
<a name="l01507"></a>01507 <span class="keywordflow">if</span>(other.node!=this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01508"></a>01508 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01509"></a>01509 }
<a name="l01510"></a>01510
<a name="l01511"></a>01511 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01512"></a>01512 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1post__order__iterator.html#c46e226f573949fad2a05cec13a426ed">tree<T, tree_node_allocator>::post_order_iterator::operator==</a>(<span class="keyword">const</span> post_order_iterator& other)<span class="keyword"> const</span>
<a name="l01513"></a>01513 <span class="keyword"> </span>{
<a name="l01514"></a>01514 <span class="keywordflow">if</span>(other.node==this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01515"></a>01515 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01516"></a>01516 }
<a name="l01517"></a>01517
<a name="l01518"></a>01518 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01519"></a>01519 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1pre__order__iterator.html#7b3b6771303a3276f600339b5cdc2dab">tree<T, tree_node_allocator>::pre_order_iterator::operator!=</a>(<span class="keyword">const</span> pre_order_iterator& other)<span class="keyword"> const</span>
<a name="l01520"></a>01520 <span class="keyword"> </span>{
<a name="l01521"></a>01521 <span class="keywordflow">if</span>(other.node!=this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01522"></a>01522 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01523"></a>01523 }
<a name="l01524"></a>01524
<a name="l01525"></a>01525 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01526"></a>01526 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1pre__order__iterator.html#71ef877a3fdbf2732de1b109aa4456b0">tree<T, tree_node_allocator>::pre_order_iterator::operator==</a>(<span class="keyword">const</span> pre_order_iterator& other)<span class="keyword"> const</span>
<a name="l01527"></a>01527 <span class="keyword"> </span>{
<a name="l01528"></a>01528 <span class="keywordflow">if</span>(other.node==this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01529"></a>01529 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01530"></a>01530 }
<a name="l01531"></a>01531
<a name="l01532"></a>01532 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01533"></a>01533 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1sibling__iterator.html#afc4a99dc8e8f1ffe12967db53553950">tree<T, tree_node_allocator>::sibling_iterator::operator!=</a>(<span class="keyword">const</span> sibling_iterator& other)<span class="keyword"> const</span>
<a name="l01534"></a>01534 <span class="keyword"> </span>{
<a name="l01535"></a>01535 <span class="keywordflow">if</span>(other.node!=this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01536"></a>01536 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01537"></a>01537 }
<a name="l01538"></a>01538
<a name="l01539"></a>01539 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01540"></a>01540 <span class="keywordtype">bool</span> <a class="code" href="classtree_1_1sibling__iterator.html#b25126f45303e55f89c67e214f609da0">tree<T, tree_node_allocator>::sibling_iterator::operator==</a>(<span class="keyword">const</span> sibling_iterator& other)<span class="keyword"> const</span>
<a name="l01541"></a>01541 <span class="keyword"> </span>{
<a name="l01542"></a>01542 <span class="keywordflow">if</span>(other.node==this->node) <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l01543"></a>01543 <span class="keywordflow">else</span> <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01544"></a>01544 }
<a name="l01545"></a>01545
<a name="l01546"></a>01546 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01547"></a>01547 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#e963353ec3487a984cd244a37b63e131">tree<T, tree_node_allocator>::iterator_base::begin</a>()<span class="keyword"> const</span>
<a name="l01548"></a>01548 <span class="keyword"> </span>{
<a name="l01549"></a>01549 sibling_iterator ret(node->first_child);
<a name="l01550"></a>01550 ret.parent_=this->node;
<a name="l01551"></a>01551 <span class="keywordflow">return</span> ret;
<a name="l01552"></a>01552 }
<a name="l01553"></a>01553
<a name="l01554"></a>01554 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01555"></a>01555 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree_1_1iterator__base.html#3c62bfda36d4ce0952f6ae3b6f621f95">tree<T, tree_node_allocator>::iterator_base::end</a>()<span class="keyword"> const</span>
<a name="l01556"></a>01556 <span class="keyword"> </span>{
<a name="l01557"></a>01557 sibling_iterator ret(0);
<a name="l01558"></a>01558 ret.parent_=node;
<a name="l01559"></a>01559 <span class="keywordflow">return</span> ret;
<a name="l01560"></a>01560 }
<a name="l01561"></a>01561
<a name="l01562"></a>01562 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01563"></a>01563 <span class="keywordtype">void</span> <a class="code" href="classtree_1_1iterator__base.html#a0be7989b9dd4c5bcdcc0d47a56d11fb">tree<T, tree_node_allocator>::iterator_base::skip_children</a>()
<a name="l01564"></a>01564 {
<a name="l01565"></a>01565 skip_current_children_=<span class="keyword">true</span>;
<a name="l01566"></a>01566 }
<a name="l01567"></a>01567
<a name="l01568"></a>01568 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01569"></a>01569 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="classtree_1_1iterator__base.html#e6f2ec470dac0149858add00617f51a7">tree<T, tree_node_allocator>::iterator_base::number_of_children</a>()<span class="keyword"> const</span>
<a name="l01570"></a>01570 <span class="keyword"> </span>{
<a name="l01571"></a>01571 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *pos=node->first_child;
<a name="l01572"></a>01572 <span class="keywordflow">if</span>(pos==0) <span class="keywordflow">return</span> 0;
<a name="l01573"></a>01573
<a name="l01574"></a>01574 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ret=1;
<a name="l01575"></a>01575 <span class="keywordflow">while</span>(pos!=node->last_child) {
<a name="l01576"></a>01576 ++ret;
<a name="l01577"></a>01577 pos=pos->next_sibling;
<a name="l01578"></a>01578 }
<a name="l01579"></a>01579 <span class="keywordflow">return</span> ret;
<a name="l01580"></a>01580 }
<a name="l01581"></a>01581
<a name="l01582"></a>01582
<a name="l01583"></a>01583
<a name="l01584"></a>01584 <span class="comment">// Pre-order iterator</span>
<a name="l01585"></a>01585
<a name="l01586"></a>01586 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01587"></a>01587 <a class="code" href="classtree_1_1pre__order__iterator.html#aa4abe430ae678fa7d7753d9599be049">tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator</a>()
<a name="l01588"></a>01588 : iterator_base(0)
<a name="l01589"></a>01589 {
<a name="l01590"></a>01590 }
<a name="l01591"></a>01591
<a name="l01592"></a>01592 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01593"></a>01593 <a class="code" href="classtree_1_1pre__order__iterator.html#aa4abe430ae678fa7d7753d9599be049">tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator</a>(tree_node *tn)
<a name="l01594"></a>01594 : iterator_base(tn)
<a name="l01595"></a>01595 {
<a name="l01596"></a>01596 }
<a name="l01597"></a>01597
<a name="l01598"></a>01598 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01599"></a>01599 <a class="code" href="classtree_1_1pre__order__iterator.html#aa4abe430ae678fa7d7753d9599be049">tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator</a>(<span class="keyword">const</span> iterator_base &other)
<a name="l01600"></a>01600 : iterator_base(other.node)
<a name="l01601"></a>01601 {
<a name="l01602"></a>01602 }
<a name="l01603"></a>01603
<a name="l01604"></a>01604 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01605"></a>01605 <a class="code" href="classtree_1_1pre__order__iterator.html#aa4abe430ae678fa7d7753d9599be049">tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator</a>(<span class="keyword">const</span> sibling_iterator& other)
<a name="l01606"></a>01606 : iterator_base(other.node)
<a name="l01607"></a>01607 {
<a name="l01608"></a>01608 <span class="keywordflow">if</span>(this->node==0) {
<a name="l01609"></a>01609 <span class="keywordflow">if</span>(other.range_last()!=0)
<a name="l01610"></a>01610 this->node=other.range_last();
<a name="l01611"></a>01611 <span class="keywordflow">else</span>
<a name="l01612"></a>01612 this->node=other.parent_;
<a name="l01613"></a>01613 this->skip_children();
<a name="l01614"></a>01614 ++(*this);
<a name="l01615"></a>01615 }
<a name="l01616"></a>01616 }
<a name="l01617"></a>01617
<a name="l01618"></a>01618 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01619"></a>01619 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a>& <a class="code" href="classtree_1_1pre__order__iterator.html#07b77d1591ad7f05e4531489561d36d2">tree<T, tree_node_allocator>::pre_order_iterator::operator++</a>()
<a name="l01620"></a>01620 {
<a name="l01621"></a>01621 assert(this->node!=0);
<a name="l01622"></a>01622 <span class="keywordflow">if</span>(!this->skip_current_children_ && this->node->first_child != 0) {
<a name="l01623"></a>01623 this->node=this->node->first_child;
<a name="l01624"></a>01624 }
<a name="l01625"></a>01625 <span class="keywordflow">else</span> {
<a name="l01626"></a>01626 this->skip_current_children_=<span class="keyword">false</span>;
<a name="l01627"></a>01627 <span class="keywordflow">while</span>(this->node->next_sibling==0) {
<a name="l01628"></a>01628 this->node=this->node->parent;
<a name="l01629"></a>01629 <span class="keywordflow">if</span>(this->node==0)
<a name="l01630"></a>01630 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01631"></a>01631 }
<a name="l01632"></a>01632 this->node=this->node->next_sibling;
<a name="l01633"></a>01633 }
<a name="l01634"></a>01634 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01635"></a>01635 }
<a name="l01636"></a>01636
<a name="l01637"></a>01637 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01638"></a>01638 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a>& <a class="code" href="classtree_1_1pre__order__iterator.html#4e2dd21653724b6413d9949caf9bb107">tree<T, tree_node_allocator>::pre_order_iterator::operator--</a>()
<a name="l01639"></a>01639 {
<a name="l01640"></a>01640 assert(this->node!=0);
<a name="l01641"></a>01641 <span class="keywordflow">if</span>(this->node->prev_sibling) {
<a name="l01642"></a>01642 this->node=this->node->prev_sibling;
<a name="l01643"></a>01643 <span class="keywordflow">while</span>(this->node->last_child)
<a name="l01644"></a>01644 this->node=this->node->last_child;
<a name="l01645"></a>01645 }
<a name="l01646"></a>01646 <span class="keywordflow">else</span> {
<a name="l01647"></a>01647 this->node=this->node->parent;
<a name="l01648"></a>01648 <span class="keywordflow">if</span>(this->node==0)
<a name="l01649"></a>01649 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01650"></a>01650 }
<a name="l01651"></a>01651 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01652"></a>01652 }
<a name="l01653"></a>01653
<a name="l01654"></a>01654 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01655"></a>01655 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a> <a class="code" href="classtree_1_1pre__order__iterator.html#07b77d1591ad7f05e4531489561d36d2">tree<T, tree_node_allocator>::pre_order_iterator::operator++</a>(<span class="keywordtype">int</span> n)
<a name="l01656"></a>01656 {
<a name="l01657"></a>01657 pre_order_iterator copy = *<span class="keyword">this</span>;
<a name="l01658"></a>01658 ++(*this);
<a name="l01659"></a>01659 <span class="keywordflow">return</span> copy;
<a name="l01660"></a>01660 }
<a name="l01661"></a>01661
<a name="l01662"></a>01662 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01663"></a>01663 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a> <a class="code" href="classtree_1_1pre__order__iterator.html#4e2dd21653724b6413d9949caf9bb107">tree<T, tree_node_allocator>::pre_order_iterator::operator--</a>(<span class="keywordtype">int</span> n)
<a name="l01664"></a>01664 {
<a name="l01665"></a>01665 pre_order_iterator copy = *<span class="keyword">this</span>;
<a name="l01666"></a>01666 --(*this);
<a name="l01667"></a>01667 <span class="keywordflow">return</span> copy;
<a name="l01668"></a>01668 }
<a name="l01669"></a>01669
<a name="l01670"></a>01670 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01671"></a>01671 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a>& <a class="code" href="classtree_1_1pre__order__iterator.html#5ab66cd50ae22c9b246231b41b7720f5">tree<T, tree_node_allocator>::pre_order_iterator::operator+=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01672"></a>01672 {
<a name="l01673"></a>01673 <span class="keywordflow">while</span>(num>0) {
<a name="l01674"></a>01674 ++(*this);
<a name="l01675"></a>01675 --num;
<a name="l01676"></a>01676 }
<a name="l01677"></a>01677 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l01678"></a>01678 }
<a name="l01679"></a>01679
<a name="l01680"></a>01680 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01681"></a>01681 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::pre_order_iterator</a>& <a class="code" href="classtree_1_1pre__order__iterator.html#722aedfd8f8be3490324a587d17cb133">tree<T, tree_node_allocator>::pre_order_iterator::operator-=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01682"></a>01682 {
<a name="l01683"></a>01683 <span class="keywordflow">while</span>(num>0) {
<a name="l01684"></a>01684 --(*this);
<a name="l01685"></a>01685 --num;
<a name="l01686"></a>01686 }
<a name="l01687"></a>01687 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l01688"></a>01688 }
<a name="l01689"></a>01689
<a name="l01690"></a>01690
<a name="l01691"></a>01691
<a name="l01692"></a>01692 <span class="comment">// Post-order iterator</span>
<a name="l01693"></a>01693
<a name="l01694"></a>01694 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01695"></a>01695 <a class="code" href="classtree_1_1post__order__iterator.html#f6d2a1ff77da1ca318447faef819fb22">tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator</a>()
<a name="l01696"></a>01696 : iterator_base(0)
<a name="l01697"></a>01697 {
<a name="l01698"></a>01698 }
<a name="l01699"></a>01699
<a name="l01700"></a>01700 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01701"></a>01701 <a class="code" href="classtree_1_1post__order__iterator.html#f6d2a1ff77da1ca318447faef819fb22">tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator</a>(tree_node *tn)
<a name="l01702"></a>01702 : iterator_base(tn)
<a name="l01703"></a>01703 {
<a name="l01704"></a>01704 }
<a name="l01705"></a>01705
<a name="l01706"></a>01706 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01707"></a>01707 <a class="code" href="classtree_1_1post__order__iterator.html#f6d2a1ff77da1ca318447faef819fb22">tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator</a>(<span class="keyword">const</span> iterator_base &other)
<a name="l01708"></a>01708 : iterator_base(other.node)
<a name="l01709"></a>01709 {
<a name="l01710"></a>01710 }
<a name="l01711"></a>01711
<a name="l01712"></a>01712 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01713"></a>01713 <a class="code" href="classtree_1_1post__order__iterator.html#f6d2a1ff77da1ca318447faef819fb22">tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator</a>(<span class="keyword">const</span> sibling_iterator& other)
<a name="l01714"></a>01714 : iterator_base(other.node)
<a name="l01715"></a>01715 {
<a name="l01716"></a>01716 <span class="keywordflow">if</span>(this->node==0) {
<a name="l01717"></a>01717 <span class="keywordflow">if</span>(other.range_last()!=0)
<a name="l01718"></a>01718 this->node=other.range_last();
<a name="l01719"></a>01719 <span class="keywordflow">else</span>
<a name="l01720"></a>01720 this->node=other.parent_;
<a name="l01721"></a>01721 this->skip_children();
<a name="l01722"></a>01722 ++(*this);
<a name="l01723"></a>01723 }
<a name="l01724"></a>01724 }
<a name="l01725"></a>01725
<a name="l01726"></a>01726 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01727"></a>01727 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a>& <a class="code" href="classtree_1_1post__order__iterator.html#baba42c4ecb0a0bb8b21b0c28dfa3009">tree<T, tree_node_allocator>::post_order_iterator::operator++</a>()
<a name="l01728"></a>01728 {
<a name="l01729"></a>01729 assert(this->node!=0);
<a name="l01730"></a>01730 <span class="keywordflow">if</span>(this->node->next_sibling==0) {
<a name="l01731"></a>01731 this->node=this->node->parent;
<a name="l01732"></a>01732 this->skip_current_children_=<span class="keyword">false</span>;
<a name="l01733"></a>01733 }
<a name="l01734"></a>01734 <span class="keywordflow">else</span> {
<a name="l01735"></a>01735 this->node=this->node->next_sibling;
<a name="l01736"></a>01736 <span class="keywordflow">if</span>(this->skip_current_children_) {
<a name="l01737"></a>01737 this->skip_current_children_=<span class="keyword">false</span>;
<a name="l01738"></a>01738 }
<a name="l01739"></a>01739 <span class="keywordflow">else</span> {
<a name="l01740"></a>01740 <span class="keywordflow">while</span>(this->node->first_child)
<a name="l01741"></a>01741 this->node=this->node->first_child;
<a name="l01742"></a>01742 }
<a name="l01743"></a>01743 }
<a name="l01744"></a>01744 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01745"></a>01745 }
<a name="l01746"></a>01746
<a name="l01747"></a>01747 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01748"></a>01748 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a>& <a class="code" href="classtree_1_1post__order__iterator.html#f70bbd10b24ca0cf1c674e4ef40899db">tree<T, tree_node_allocator>::post_order_iterator::operator--</a>()
<a name="l01749"></a>01749 {
<a name="l01750"></a>01750 assert(this->node!=0);
<a name="l01751"></a>01751 <span class="keywordflow">if</span>(this->skip_current_children_ || this->node->last_child==0) {
<a name="l01752"></a>01752 this->skip_current_children_=<span class="keyword">false</span>;
<a name="l01753"></a>01753 <span class="keywordflow">while</span>(this->node->prev_sibling==0)
<a name="l01754"></a>01754 this->node=this->node->parent;
<a name="l01755"></a>01755 this->node=this->node->prev_sibling;
<a name="l01756"></a>01756 }
<a name="l01757"></a>01757 <span class="keywordflow">else</span> {
<a name="l01758"></a>01758 this->node=this->node->last_child;
<a name="l01759"></a>01759 }
<a name="l01760"></a>01760 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01761"></a>01761 }
<a name="l01762"></a>01762
<a name="l01763"></a>01763 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01764"></a>01764 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a> <a class="code" href="classtree_1_1post__order__iterator.html#baba42c4ecb0a0bb8b21b0c28dfa3009">tree<T, tree_node_allocator>::post_order_iterator::operator++</a>(<span class="keywordtype">int</span>)
<a name="l01765"></a>01765 {
<a name="l01766"></a>01766 post_order_iterator copy = *<span class="keyword">this</span>;
<a name="l01767"></a>01767 ++(*this);
<a name="l01768"></a>01768 <span class="keywordflow">return</span> copy;
<a name="l01769"></a>01769 }
<a name="l01770"></a>01770
<a name="l01771"></a>01771 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01772"></a>01772 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a> <a class="code" href="classtree_1_1post__order__iterator.html#f70bbd10b24ca0cf1c674e4ef40899db">tree<T, tree_node_allocator>::post_order_iterator::operator--</a>(<span class="keywordtype">int</span>)
<a name="l01773"></a>01773 {
<a name="l01774"></a>01774 post_order_iterator copy = *<span class="keyword">this</span>;
<a name="l01775"></a>01775 --(*this);
<a name="l01776"></a>01776 <span class="keywordflow">return</span> copy;
<a name="l01777"></a>01777 }
<a name="l01778"></a>01778
<a name="l01779"></a>01779
<a name="l01780"></a>01780 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01781"></a>01781 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a>& <a class="code" href="classtree_1_1post__order__iterator.html#0b6c2246f41b0a2ff8e4c9d9efcee879">tree<T, tree_node_allocator>::post_order_iterator::operator+=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01782"></a>01782 {
<a name="l01783"></a>01783 <span class="keywordflow">while</span>(num>0) {
<a name="l01784"></a>01784 ++(*this);
<a name="l01785"></a>01785 --num;
<a name="l01786"></a>01786 }
<a name="l01787"></a>01787 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l01788"></a>01788 }
<a name="l01789"></a>01789
<a name="l01790"></a>01790 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01791"></a>01791 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::post_order_iterator</a>& <a class="code" href="classtree_1_1post__order__iterator.html#93b7ddae75f30985a0d81f38bcbaa306">tree<T, tree_node_allocator>::post_order_iterator::operator-=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01792"></a>01792 {
<a name="l01793"></a>01793 <span class="keywordflow">while</span>(num>0) {
<a name="l01794"></a>01794 --(*this);
<a name="l01795"></a>01795 --num;
<a name="l01796"></a>01796 }
<a name="l01797"></a>01797 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l01798"></a>01798 }
<a name="l01799"></a>01799
<a name="l01800"></a>01800 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01801"></a>01801 <span class="keywordtype">void</span> <a class="code" href="classtree_1_1post__order__iterator.html#ca4676b4986854521cfa2c7d84f62204">tree<T, tree_node_allocator>::post_order_iterator::descend_all</a>()
<a name="l01802"></a>01802 {
<a name="l01803"></a>01803 assert(this->node!=0);
<a name="l01804"></a>01804 <span class="keywordflow">while</span>(this->node->first_child)
<a name="l01805"></a>01805 this->node=this->node->first_child;
<a name="l01806"></a>01806 }
<a name="l01807"></a>01807
<a name="l01808"></a>01808
<a name="l01809"></a>01809 <span class="comment">// Fixed depth iterator</span>
<a name="l01810"></a>01810
<a name="l01811"></a>01811 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01812"></a>01812 <a class="code" href="classtree_1_1fixed__depth__iterator.html#10f1d20ec2b62e4370a560ebcd84ad54">tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator</a>()
<a name="l01813"></a>01813 : iterator_base()
<a name="l01814"></a>01814 {
<a name="l01815"></a>01815 set_first_parent_();
<a name="l01816"></a>01816 }
<a name="l01817"></a>01817
<a name="l01818"></a>01818 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01819"></a>01819 <a class="code" href="classtree_1_1fixed__depth__iterator.html#10f1d20ec2b62e4370a560ebcd84ad54">tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator</a>(tree_node *tn)
<a name="l01820"></a>01820 : iterator_base(tn)
<a name="l01821"></a>01821 {
<a name="l01822"></a>01822 set_first_parent_();
<a name="l01823"></a>01823 }
<a name="l01824"></a>01824
<a name="l01825"></a>01825 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01826"></a>01826 <a class="code" href="classtree_1_1fixed__depth__iterator.html#10f1d20ec2b62e4370a560ebcd84ad54">tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator</a>(<span class="keyword">const</span> iterator_base& other)
<a name="l01827"></a>01827 : iterator_base(other.node)
<a name="l01828"></a>01828 {
<a name="l01829"></a>01829 set_first_parent_();
<a name="l01830"></a>01830 }
<a name="l01831"></a>01831
<a name="l01832"></a>01832 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01833"></a>01833 <a class="code" href="classtree_1_1fixed__depth__iterator.html#10f1d20ec2b62e4370a560ebcd84ad54">tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator</a>(<span class="keyword">const</span> sibling_iterator& other)
<a name="l01834"></a>01834 : iterator_base(other.node), first_parent_(other.parent_)
<a name="l01835"></a>01835 {
<a name="l01836"></a>01836 find_leftmost_parent_();
<a name="l01837"></a>01837 }
<a name="l01838"></a>01838
<a name="l01839"></a>01839 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01840"></a>01840 <a class="code" href="classtree_1_1fixed__depth__iterator.html#10f1d20ec2b62e4370a560ebcd84ad54">tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator</a>(<span class="keyword">const</span> fixed_depth_iterator& other)
<a name="l01841"></a>01841 : iterator_base(other.node), first_parent_(other.first_parent_)
<a name="l01842"></a>01842 {
<a name="l01843"></a>01843 }
<a name="l01844"></a>01844
<a name="l01845"></a>01845 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01846"></a>01846 <span class="keywordtype">void</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_</a>()
<a name="l01847"></a>01847 {
<a name="l01848"></a>01848 <span class="keywordflow">return</span>; <span class="comment">// FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking if</span>
<a name="l01849"></a>01849 <span class="comment">// it is ever to work at the 'head' level.</span>
<a name="l01850"></a>01850 first_parent_=0;
<a name="l01851"></a>01851 <span class="keywordflow">if</span>(this->node==0) <span class="keywordflow">return</span>;
<a name="l01852"></a>01852 <span class="keywordflow">if</span>(this->node->parent!=0)
<a name="l01853"></a>01853 first_parent_=this->node->parent;
<a name="l01854"></a>01854 <span class="keywordflow">if</span>(first_parent_)
<a name="l01855"></a>01855 find_leftmost_parent_();
<a name="l01856"></a>01856 }
<a name="l01857"></a>01857
<a name="l01858"></a>01858 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01859"></a>01859 <span class="keywordtype">void</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_</a>()
<a name="l01860"></a>01860 {
<a name="l01861"></a>01861 <span class="keywordflow">return</span>; <span class="comment">// FIXME: see 'set_first_parent()'</span>
<a name="l01862"></a>01862 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmppar=first_parent_;
<a name="l01863"></a>01863 <span class="keywordflow">while</span>(tmppar->prev_sibling) {
<a name="l01864"></a>01864 tmppar=tmppar->prev_sibling;
<a name="l01865"></a>01865 <span class="keywordflow">if</span>(tmppar->first_child)
<a name="l01866"></a>01866 first_parent_=tmppar;
<a name="l01867"></a>01867 }
<a name="l01868"></a>01868 }
<a name="l01869"></a>01869
<a name="l01870"></a>01870 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01871"></a>01871 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a>& <a class="code" href="classtree_1_1fixed__depth__iterator.html#71bcee62caa033974d5c0d94ab0dc0c6">tree<T, tree_node_allocator>::fixed_depth_iterator::operator++</a>()
<a name="l01872"></a>01872 {
<a name="l01873"></a>01873 assert(this->node!=0);
<a name="l01874"></a>01874
<a name="l01875"></a>01875 <span class="keywordflow">if</span>(this->node->next_sibling) {
<a name="l01876"></a>01876 this->node=this->node->next_sibling;
<a name="l01877"></a>01877 }
<a name="l01878"></a>01878 <span class="keywordflow">else</span> {
<a name="l01879"></a>01879 <span class="keywordtype">int</span> relative_depth=0;
<a name="l01880"></a>01880 upper:
<a name="l01881"></a>01881 <span class="keywordflow">do</span> {
<a name="l01882"></a>01882 this->node=this->node->parent;
<a name="l01883"></a>01883 <span class="keywordflow">if</span>(this->node==0) <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01884"></a>01884 --relative_depth;
<a name="l01885"></a>01885 } <span class="keywordflow">while</span>(this->node->next_sibling==0);
<a name="l01886"></a>01886 lower:
<a name="l01887"></a>01887 this->node=this->node->next_sibling;
<a name="l01888"></a>01888 <span class="keywordflow">while</span>(this->node->first_child==0) {
<a name="l01889"></a>01889 <span class="keywordflow">if</span>(this->node->next_sibling==0)
<a name="l01890"></a>01890 <span class="keywordflow">goto</span> upper;
<a name="l01891"></a>01891 this->node=this->node->next_sibling;
<a name="l01892"></a>01892 <span class="keywordflow">if</span>(this->node==0) <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01893"></a>01893 }
<a name="l01894"></a>01894 <span class="keywordflow">while</span>(relative_depth<0 && this->node->first_child!=0) {
<a name="l01895"></a>01895 this->node=this->node->first_child;
<a name="l01896"></a>01896 ++relative_depth;
<a name="l01897"></a>01897 }
<a name="l01898"></a>01898 <span class="keywordflow">if</span>(relative_depth<0) {
<a name="l01899"></a>01899 <span class="keywordflow">if</span>(this->node->next_sibling==0) <span class="keywordflow">goto</span> upper;
<a name="l01900"></a>01900 <span class="keywordflow">else</span> <span class="keywordflow">goto</span> lower;
<a name="l01901"></a>01901 }
<a name="l01902"></a>01902 }
<a name="l01903"></a>01903 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01904"></a>01904
<a name="l01905"></a>01905 <span class="comment">// if(this->node->next_sibling!=0) {</span>
<a name="l01906"></a>01906 <span class="comment">// this->node=this->node->next_sibling;</span>
<a name="l01907"></a>01907 <span class="comment">// assert(this->node!=0);</span>
<a name="l01908"></a>01908 <span class="comment">// if(this->node->parent==0 && this->node->next_sibling==0) // feet element</span>
<a name="l01909"></a>01909 <span class="comment">// this->node=0;</span>
<a name="l01910"></a>01910 <span class="comment">// }</span>
<a name="l01911"></a>01911 <span class="comment">// else {</span>
<a name="l01912"></a>01912 <span class="comment">// tree_node *par=this->node->parent;</span>
<a name="l01913"></a>01913 <span class="comment">// do {</span>
<a name="l01914"></a>01914 <span class="comment">// par=par->next_sibling;</span>
<a name="l01915"></a>01915 <span class="comment">// if(par==0) { // FIXME: need to keep track of this!</span>
<a name="l01916"></a>01916 <span class="comment">// this->node=0;</span>
<a name="l01917"></a>01917 <span class="comment">// return *this;</span>
<a name="l01918"></a>01918 <span class="comment">// }</span>
<a name="l01919"></a>01919 <span class="comment">// } while(par->first_child==0);</span>
<a name="l01920"></a>01920 <span class="comment">// this->node=par->first_child;</span>
<a name="l01921"></a>01921 <span class="comment">// }</span>
<a name="l01922"></a>01922 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01923"></a>01923 }
<a name="l01924"></a>01924
<a name="l01925"></a>01925 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01926"></a>01926 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a>& <a class="code" href="classtree_1_1fixed__depth__iterator.html#39a2c5b5048ec0dfff33fbb55bd7767e">tree<T, tree_node_allocator>::fixed_depth_iterator::operator--</a>()
<a name="l01927"></a>01927 {
<a name="l01928"></a>01928 assert(this->node!=0);
<a name="l01929"></a>01929 <span class="keywordflow">if</span>(this->node->prev_sibling!=0) {
<a name="l01930"></a>01930 this->node=this->node->prev_sibling;
<a name="l01931"></a>01931 assert(this->node!=0);
<a name="l01932"></a>01932 <span class="keywordflow">if</span>(this->node->parent==0 && this->node->prev_sibling==0) <span class="comment">// head element</span>
<a name="l01933"></a>01933 this->node=0;
<a name="l01934"></a>01934 }
<a name="l01935"></a>01935 <span class="keywordflow">else</span> {
<a name="l01936"></a>01936 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *par=this->node->parent;
<a name="l01937"></a>01937 <span class="keywordflow">do</span> {
<a name="l01938"></a>01938 par=par->prev_sibling;
<a name="l01939"></a>01939 <span class="keywordflow">if</span>(par==0) { <span class="comment">// FIXME: need to keep track of this!</span>
<a name="l01940"></a>01940 this->node=0;
<a name="l01941"></a>01941 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01942"></a>01942 }
<a name="l01943"></a>01943 } <span class="keywordflow">while</span>(par->last_child==0);
<a name="l01944"></a>01944 this->node=par->last_child;
<a name="l01945"></a>01945 }
<a name="l01946"></a>01946 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01947"></a>01947 }
<a name="l01948"></a>01948
<a name="l01949"></a>01949 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01950"></a>01950 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a> <a class="code" href="classtree_1_1fixed__depth__iterator.html#71bcee62caa033974d5c0d94ab0dc0c6">tree<T, tree_node_allocator>::fixed_depth_iterator::operator++</a>(<span class="keywordtype">int</span>)
<a name="l01951"></a>01951 {
<a name="l01952"></a>01952 fixed_depth_iterator copy = *<span class="keyword">this</span>;
<a name="l01953"></a>01953 ++(*this);
<a name="l01954"></a>01954 <span class="keywordflow">return</span> copy;
<a name="l01955"></a>01955 }
<a name="l01956"></a>01956
<a name="l01957"></a>01957 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01958"></a>01958 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a> <a class="code" href="classtree_1_1fixed__depth__iterator.html#39a2c5b5048ec0dfff33fbb55bd7767e">tree<T, tree_node_allocator>::fixed_depth_iterator::operator--</a>(<span class="keywordtype">int</span>)
<a name="l01959"></a>01959 {
<a name="l01960"></a>01960 fixed_depth_iterator copy = *<span class="keyword">this</span>;
<a name="l01961"></a>01961 --(*this);
<a name="l01962"></a>01962 <span class="keywordflow">return</span> copy;
<a name="l01963"></a>01963 }
<a name="l01964"></a>01964
<a name="l01965"></a>01965 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01966"></a>01966 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a>& <a class="code" href="classtree_1_1fixed__depth__iterator.html#e8ccf119ae29e96044d9a4eeca2a539d">tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01967"></a>01967 {
<a name="l01968"></a>01968 <span class="keywordflow">while</span>(num>0) {
<a name="l01969"></a>01969 --(*this);
<a name="l01970"></a>01970 --(num);
<a name="l01971"></a>01971 }
<a name="l01972"></a>01972 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l01973"></a>01973 }
<a name="l01974"></a>01974
<a name="l01975"></a>01975 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01976"></a>01976 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::fixed_depth_iterator</a>& <a class="code" href="classtree_1_1fixed__depth__iterator.html#6909c400794c6feb49d75b99dbf6aa00">tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l01977"></a>01977 {
<a name="l01978"></a>01978 <span class="keywordflow">while</span>(num>0) {
<a name="l01979"></a>01979 ++(*this);
<a name="l01980"></a>01980 --(num);
<a name="l01981"></a>01981 }
<a name="l01982"></a>01982 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01983"></a>01983 }
<a name="l01984"></a>01984
<a name="l01985"></a>01985 <span class="comment">// FIXME: add the other members of fixed_depth_iterator.</span>
<a name="l01986"></a>01986
<a name="l01987"></a>01987
<a name="l01988"></a>01988 <span class="comment">// Sibling iterator</span>
<a name="l01989"></a>01989
<a name="l01990"></a>01990 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01991"></a>01991 <a class="code" href="classtree_1_1sibling__iterator.html#daaf56c800ed241d36802abab3925a2a">tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator</a>()
<a name="l01992"></a>01992 : iterator_base()
<a name="l01993"></a>01993 {
<a name="l01994"></a>01994 set_parent_();
<a name="l01995"></a>01995 }
<a name="l01996"></a>01996
<a name="l01997"></a>01997 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l01998"></a>01998 <a class="code" href="classtree_1_1sibling__iterator.html#daaf56c800ed241d36802abab3925a2a">tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator</a>(tree_node *tn)
<a name="l01999"></a>01999 : iterator_base(tn)
<a name="l02000"></a>02000 {
<a name="l02001"></a>02001 set_parent_();
<a name="l02002"></a>02002 }
<a name="l02003"></a>02003
<a name="l02004"></a>02004 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02005"></a>02005 <a class="code" href="classtree_1_1sibling__iterator.html#daaf56c800ed241d36802abab3925a2a">tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator</a>(<span class="keyword">const</span> iterator_base& other)
<a name="l02006"></a>02006 : iterator_base(other.node)
<a name="l02007"></a>02007 {
<a name="l02008"></a>02008 set_parent_();
<a name="l02009"></a>02009 }
<a name="l02010"></a>02010
<a name="l02011"></a>02011 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02012"></a>02012 <a class="code" href="classtree_1_1sibling__iterator.html#daaf56c800ed241d36802abab3925a2a">tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator</a>(<span class="keyword">const</span> sibling_iterator& other)
<a name="l02013"></a>02013 : iterator_base(other), parent_(other.parent_)
<a name="l02014"></a>02014 {
<a name="l02015"></a>02015 }
<a name="l02016"></a>02016
<a name="l02017"></a>02017 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02018"></a>02018 <span class="keywordtype">void</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator::set_parent_</a>()
<a name="l02019"></a>02019 {
<a name="l02020"></a>02020 parent_=0;
<a name="l02021"></a>02021 <span class="keywordflow">if</span>(this->node==0) <span class="keywordflow">return</span>;
<a name="l02022"></a>02022 <span class="keywordflow">if</span>(this->node->parent!=0)
<a name="l02023"></a>02023 parent_=this->node->parent;
<a name="l02024"></a>02024 }
<a name="l02025"></a>02025
<a name="l02026"></a>02026 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02027"></a>02027 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a>& <a class="code" href="classtree_1_1sibling__iterator.html#8d0d647a7843432b5ccc18724fcc3493">tree<T, tree_node_allocator>::sibling_iterator::operator++</a>()
<a name="l02028"></a>02028 {
<a name="l02029"></a>02029 <span class="keywordflow">if</span>(this->node)
<a name="l02030"></a>02030 this->node=this->node->next_sibling;
<a name="l02031"></a>02031 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l02032"></a>02032 }
<a name="l02033"></a>02033
<a name="l02034"></a>02034 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02035"></a>02035 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a>& <a class="code" href="classtree_1_1sibling__iterator.html#7e91377755da77acd20d5b9356f7498e">tree<T, tree_node_allocator>::sibling_iterator::operator--</a>()
<a name="l02036"></a>02036 {
<a name="l02037"></a>02037 <span class="keywordflow">if</span>(this->node) this->node=this->node->prev_sibling;
<a name="l02038"></a>02038 <span class="keywordflow">else</span> {
<a name="l02039"></a>02039 assert(parent_);
<a name="l02040"></a>02040 this->node=parent_->last_child;
<a name="l02041"></a>02041 }
<a name="l02042"></a>02042 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l02043"></a>02043 }
<a name="l02044"></a>02044
<a name="l02045"></a>02045 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02046"></a>02046 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree_1_1sibling__iterator.html#8d0d647a7843432b5ccc18724fcc3493">tree<T, tree_node_allocator>::sibling_iterator::operator++</a>(<span class="keywordtype">int</span>)
<a name="l02047"></a>02047 {
<a name="l02048"></a>02048 sibling_iterator copy = *<span class="keyword">this</span>;
<a name="l02049"></a>02049 ++(*this);
<a name="l02050"></a>02050 <span class="keywordflow">return</span> copy;
<a name="l02051"></a>02051 }
<a name="l02052"></a>02052
<a name="l02053"></a>02053 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02054"></a>02054 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a> <a class="code" href="classtree_1_1sibling__iterator.html#7e91377755da77acd20d5b9356f7498e">tree<T, tree_node_allocator>::sibling_iterator::operator--</a>(<span class="keywordtype">int</span>)
<a name="l02055"></a>02055 {
<a name="l02056"></a>02056 sibling_iterator copy = *<span class="keyword">this</span>;
<a name="l02057"></a>02057 --(*this);
<a name="l02058"></a>02058 <span class="keywordflow">return</span> copy;
<a name="l02059"></a>02059 }
<a name="l02060"></a>02060
<a name="l02061"></a>02061 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02062"></a>02062 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a>& <a class="code" href="classtree_1_1sibling__iterator.html#d36b6994a50c0f73154b08ab35abf336">tree<T, tree_node_allocator>::sibling_iterator::operator+=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l02063"></a>02063 {
<a name="l02064"></a>02064 <span class="keywordflow">while</span>(num>0) {
<a name="l02065"></a>02065 ++(*this);
<a name="l02066"></a>02066 --num;
<a name="l02067"></a>02067 }
<a name="l02068"></a>02068 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l02069"></a>02069 }
<a name="l02070"></a>02070
<a name="l02071"></a>02071 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02072"></a>02072 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::sibling_iterator</a>& <a class="code" href="classtree_1_1sibling__iterator.html#f7b0a37317400fe16a1ad422c1ee6fa1">tree<T, tree_node_allocator>::sibling_iterator::operator-=</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> num)
<a name="l02073"></a>02073 {
<a name="l02074"></a>02074 <span class="keywordflow">while</span>(num>0) {
<a name="l02075"></a>02075 --(*this);
<a name="l02076"></a>02076 --num;
<a name="l02077"></a>02077 }
<a name="l02078"></a>02078 <span class="keywordflow">return</span> (*<span class="keyword">this</span>);
<a name="l02079"></a>02079 }
<a name="l02080"></a>02080
<a name="l02081"></a>02081 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02082"></a>02082 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::tree_node</a> *<a class="code" href="classtree_1_1sibling__iterator.html#3b9e5fe406a2d980b9f19a9f938bf722">tree<T, tree_node_allocator>::sibling_iterator::range_first</a>()<span class="keyword"> const</span>
<a name="l02083"></a>02083 <span class="keyword"> </span>{
<a name="l02084"></a>02084 <a class="code" href="classtree.html#672d078d87ae97c58b732a940d7b8ca8">tree_node</a> *tmp=parent_->first_child;
<a name="l02085"></a>02085 <span class="keywordflow">return</span> tmp;
<a name="l02086"></a>02086 }
<a name="l02087"></a>02087
<a name="l02088"></a>02088 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> tree_node_allocator>
<a name="l02089"></a>02089 <span class="keyword">typename</span> <a class="code" href="classtree.html">tree<T, tree_node_allocator>::tree_node</a> *<a class="code" href="classtree_1_1sibling__iterator.html#85964367124955ec024ac2707b5c87bd">tree<T, tree_node_allocator>::sibling_iterator::range_last</a>()<span class="keyword"> const</span>
<a name="l02090"></a>02090 <span class="keyword"> </span>{
<a name="l02091"></a>02091 <span class="keywordflow">return</span> parent_->last_child;
<a name="l02092"></a>02092 }
<a name="l02093"></a>02093
<a name="l02094"></a>02094
<a name="l02095"></a>02095 <span class="preprocessor">#endif</span>
<a name="l02096"></a>02096 <span class="preprocessor"></span>
<a name="l02097"></a>02097 <span class="comment">// Local variables:</span>
<a name="l02098"></a>02098 <span class="comment">// default-tab-width: 3</span>
<a name="l02099"></a>02099 <span class="comment">// End:</span>
</pre></div><hr size="1"><address style="align: right;"><small>Generated on Mon Feb 9 21:22:00 2009 for LibOFX by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.0 </small></address>
</body>
</html>
distrib
>
Mageia
>
1
>
i586
>
media
>
core-release
>
by-pkgid
>
0c518cc2e176451ea9eb99bff1e3388d
>
files
>
191
