doc/newtree.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
   5 <title>tree.hh: an STL-like C++ tree class</title>
   6 <!-- <link rel="stylesheet" type="text/css" href="../software.css"> -->
   7 <link rel="stylesheet" type="text/css" href="../../../cadabra/web/youngtab.css">
   8 </head>
   9 <body>
  10 <div id="head">
  11 <h1 class="shadow">tree.hh</h1>
  12 <h1 class="intro">tree.hh</h1>
  13 <h2 class="intro">An STL-like C++ tree class</h2>
  14 <h3 class="intro">Copyright &copy; 2001-2007  Kasper Peeters</h3></div>
  15 <div id="content">
  16 <h2>Overview</h2>
  17
  18 <div class="text">
  19 The <code>tree.hh</code> library for C++ provides an STL-like container class
  20 for <i>n</i>-ary trees, templated over the data stored at the nodes.  Various
  21 types of iterators are provided (post-order, pre-order, and
  22 others). Where possible the access methods are compatible with the STL
  23 or alternative algorithms are available. The library is available
  24 under the terms of the GNU General Public License.</div>
  25
  26 <div class="text">Documentation is available in the form of a <a
  27 href="tree-VERSION/tree.ps">postscript</a> and a <a href="tree-VERSION/tree.pdf">pdf</a> file (also
  28 available in the tarball as a LaTeX file). This documentation is still a
  29 bit short and not entirely complete. See the test program (included in
  30 the distribution) for an example of how to use
  31 tree.hh. Also look at the <a href="#example">simple example</a>
  32 below. There is also some <a href="doxygen/html">doxygen generated documentation</a>.</div>
  33
  34
  35 <div class="text">The <code>tree.hh</code> code is available under the terms of the
  36 <a href="http://www.gnu.org/copyleft/gpl.html">GNU
  37 General Public License</a>. If you use <code>tree.hh</code>,
  38 please satisfy my curiosity and write me a small email with
  39 a bit of explanation of your software and the role of my tree
  40 class in it.</div>
  41
  42 <div class="text">The <code>tree.hh</code> library is meant for generic <i>n</i>-ary
  43 trees. If you are only interested in AVL binary search trees
  44 (Adelson,Velskii & Landis), you may want to have a look at the
  45 <a href="http://www.geocities.com/wkaras/gen_cpp/avl_tree.html">C++
  46 AVL tree template</a> page. </div>
  47
  48 <h2>Download</h2>
  49
  50 <div class="text">Everything (the header file, examples, documentation
  51 and all other things referred to on this page) is contained in the
  52 tarball
  53 <blockquote>
  54 <a href="tree-VERSION.tar.gz">tree-VERSION.tar.gz</a></blockquote>
  55 Feel free to copy the
  56 header <a href="tree-VERSION/tree.hh">tree.hh</a> (which is all you need code-wise) into your own
  57 source directory as long as you respect the license (see above).
  58 The list of changes can be found in the <a href="ChangeLog">ChangeLog</a>.</div>
  59
  60 <div class="text">See the intro above for links to the documentation. There is a very
  61 simple demonstration program available, <a
  62 href="tree-VERSION/tree_example.cc">tree_example.cc</a> (also included in the tarball),
  63 which is discussed <a href="#example">below</a>. There is also a small
  64 test program, <a href="tree-VERSION/test_tree.cc">test_tree.cc</a>, which makes use
  65 of the <a
  66 href="tree-VERSION/tree_util.hh">tree_util.hh</a> utility functions by
  67 Linda Buisman; the output
  68 should be exactly identical to the <a
  69 href="tree-VERSION/test_tree.output">test_tree.output</a> file.</div>
  70
  71 <div class="text">The current version works with GNU gcc 3.x and
  72 higher, Borland&nbsp;C++&nbsp;builder and Microsoft Visual C++ 7.1 and
  73 higher. It is compatible with STLport.</div>
  74
  75 <div class="text">Tony Cook has provided a version for the buggy Microsoft Visual C++
  76 compilers up to version 7.0. You will have to use a special
  77 version of the header file, <a href="tree-VERSION/tree_msvc.hh">tree_msvc.hh</a>
  78 (currently based on the original tree.hh version
  79 <strong>MSVC</strong>). The difference is that all members of the
  80 iterator and sibling_iterator subclasses have been moved inside the
  81 class definitions. If you get unresolved symbols in the linking phase,
  82 or other weird compiler errors, you should use this header. Microsoft
  83 users are urged to upgrade to version 7.1 which works with tree.hh out
  84 of the box.</div>
  85
  86 <h2>Mailing list and update announcements</h2>
  87
  88 <div class="text">There is no mailing list, but I can send you an email whenever a new
  89 version of tree.hh becomes available. Just send me an email at
  90 kasper.peeters&nbsp;(at)&nbsp;aei.mpg.de
  91 and ask me to put you on the distribution list. </div>
  92
  93 <div class="text">I also announce major updates on <a
  94 href="http://www.freshmeat.net">Freshmeat</a> though not as often as
  95 by email.</div>
  96
  97 <h2>Projects using tree.hh</h2>
  98
  99 <div class="text">The <code>tree.hh</code> library is used in various projects:
 100 <dl>
 101 <dt><strong><a
 102 href="../cadabra/">Cadabra</a></strong></dt>
 103 <dd>A field-theory motivated approach to symbolic computer algebra.</dd>
 104 <dt><strong><a href="http://www.echem.uni-tuebingen.de/~bs/echem/software/EChem++/echem++.shtml">EChem++</a></strong></dt>
 105 <dd>A project realizing the idea of a Problem Solving Environment
 106 (PSE) in the field of computational electrochemistry.  Computer
 107 controlled experimental measurements, numerical simulation and
 108 analysis of electrochemical processes will be combined under a common
 109 user interface.</dd>
 110 <dt><strong><a
 111 href="http://www.infor.uva.es/~jadiego/">LZCS</a></strong></dt>
 112 <dd>A semistructured document transformation tool. LZCS compresses
 113 structured documents taking advantage of the redundant information
 114 that can appear in the structure. The main idea is that frequently
 115 repeated subtrees may exist and these can be replaced by a backward
 116 reference to their first occurance. See the <a
 117 href="http://www.dcc.uchile.cl/~gnavarro/ps/dcc04.1.ps.gz">accompanying
 118 paper</a> for more details.</dd>
 119 <dt><strong><a href="http://libofx.sourceforge.net/">libOFX</a></strong></dt>
 120 <dd>A parser and an API designed to allow applications to very easily support OFX
 121 command responses, usually provided by financial institutions for
 122 statement downloads.</dd>
 123 <dt><strong>A genetic programming project</strong></dt>
 124 <dd>See this <a
 125 href="http://www.cs.adfa.edu.au/~shanyin/publications/peel.pdf">paper</a> for
 126 more information.</dd>
 127 <dt><strong><a href="http://garraf.epsevg.upc.es/freeling/">FreeLing</a></strong></dt>
 128 <dd> The FreeLing package consists of a library providing language analysis services (such as morfological analysis, date recognition, PoS tagging, etc.)</dd>
 129 </dl>
 130 Let me know about your project when you are using
 131 <code>tree.hh</code>, so that I can add it to the list.</div>
 132
 133 <a name="example"></a>
 134 <h2>Simple example</h2>
 135
 136 <div class="text">The following program constructs a tree of std::string nodes, puts some content in
 137 it and applies the <code>find</code> algorithm to find the node with content
 138 "two". It then prints the content of all the children of this node.
 139 You can download the source <a href="tree-VERSION/tree_example.cc">tree_example.cc</a> if you're too
 140 lazy to type it in.
 141 <blockquote><pre>
 142 #include &lt;algorithm&gt;
 143 #include &lt;string&gt;
 144 #include &lt;iostream&gt;
 145 #include "tree.hh"
 146
 147 using namespace std;
 148
 149 int main(int, char **)
 150    {
 151    tree&lt;string&gt; tr;
 152    tree&lt;string&gt;::iterator top, one, two, loc, banana;
 153
 154    top=tr.begin();
 155    one=tr.insert(top, "one");
 156    two=tr.append_child(one, "two");
 157    tr.append_child(two, "apple");
 158    banana=tr.append_child(two, "banana");
 159    tr.append_child(banana,"cherry");
 160    tr.append_child(two, "peach");
 161    tr.append_child(one,"three");
 162
 163    loc=find(tr.begin(), tr.end(), "two");
 164    if(loc!=tr.end()) {
 165       tree&lt;string&gt;::sibling_iterator sib=tr.begin(loc);
 166       while(sib!=tr.end(loc)) {
 167          cout &lt;&lt; (*sib) &lt;&lt; endl;
 168          ++sib;
 169          }
 170       cout &lt;&lt; endl;
 171       tree&lt;string&gt;::iterator sib2=tr.begin(loc);
 172       tree&lt;string&gt;::iterator end2=tr.end(loc);
 173       while(sib2!=end2) {
 174          for(int i=0; i&lt;tr.depth(sib2)-2; ++i)
 175             cout &lt;&lt; " ";
 176          cout &lt;&lt; (*sib2) &lt;&lt; endl;
 177          ++sib2;
 178          }
 179       }
 180    }
 181 </pre></blockquote>
 182 The output of this program is
 183 <blockquote><pre>
 184 apple
 185 banana
 186 peach
 187
 188 apple
 189 banana
 190  cherry
 191 peach
 192 </pre></blockquote>
 193 Note that this example only has one element at the top of the tree (in
 194 this case that is the node containing "one") but it is possible to
 195 have an arbitary number of such elements (then the tree is more like a
 196 "bush"). Observe the way in which the two types of iterators work. The
 197 first block of output, obtained using the sibling_iterator, only
 198 displays the children directly below "two". The second block iterates
 199 over all children at any depth below "two". In the second output
 200 block, the <code>depth</code> member has been used to determine the
 201 distance of a given node to the root of the tree.  </div>
 202
 203 <h2>Data structure</h2>
 204
 205 <div class="text">The data structure of the <code>tree</code> class is depicted
 206 below (see the documentation for more detailed information).
 207 Each node contains a pointer to the first and last child element,
 208 and each child contains pointers to its previous and next sibling:
 209 <blockquote><small><pre>
 210            first_child        first_child
 211  root_node-+----------node--+----->-------node
 212            |           |    |               |
 213            |           |    |               V   next_sibling
 214            |           |    |               |
 215                        |    |             node
 216                        |    |               |
 217                        |    |               V   next_sibling
 218                        |    | last_child    |
 219                        |    +----->-------node
 220                        |
 221                        V next_sibling
 222                        |
 223                        |     first_child
 224                       node--+----->-------node
 225                        |    |               |
 226                        |    |               V   next_sibling
 227                        |    |               |
 228                        |    +-------------node
 229                        .
 230                        .</pre></small></blockquote>
 231 Iterators come in two types. The normal <code>iterator</code> iterates depth-first
 232 over all nodes. The beginning and end of the tree can be obtained by using the
 233 <code>begin()</code> and <code>end()</code> members. The other type of iterator
 234 only iterates over the nodes at one given depth (ie. over all siblings). One
 235 typically uses these iterators to iterate over all children of a node, in which
 236 case the [begin,end) range can be obtained by calling <code>begin(iterator)</code>
 237 and <code>end(iterator)</code>.</div>
 238
 239 <div class="text">Iterators can be converted from one type to the other; this includes the `end'
 240 iterators (all intervals are as usual closed at the beginning and open
 241 at the end).</div>
 242
 243 <hr noshade size=1>
 244 <p align=right><!-- Begin Nedstat Basic code -->
 245 <!-- Title: tree.hh stl-like container class -->
 246 <!-- URL: http://www.aei.mpg.de/~peekas/tree/ -->
 247 <a target="_blank" href="http://www.nedstatbasic.net/stats?ACQzpQ2TGcFmLelb10QwJ0nRa7UQ"><img
 248 src="http://m1.nedstatbasic.net/n?id=ACQzpQ2TGcFmLelb10QwJ0nRa7UQ"
 249 border="0" width="18" height="18"
 250 alt="Webstats4U - Free web site statistics
 251 Personal homepage website counter"></a>
 252 <!-- End Nedstat Basic code --> $Id: newtree.html,v 1.1 2007/08/21 08:47:14 peekas Exp $
 253 </body>
 254 </html>