Repository files navigation

by Kasper Peeters <kasper.peeters@phi-sci.com>

Thetree.hh library for C++ provides an STL-like container class forn-ary trees, templated over the data stored at the nodes. Varioustypes of iterators are provided (post-order, pre-order, andothers). Where possible the access methods are compatible with the STLor alternative algorithms are available.

The library should work with any C++11 compiler, and has been used andtested on all major platforms (Linux, Windows, macOS, Android, iOS).

The library is available under the terms of the GNU General PublicLicense version 2 or 3.

The tree.hh is header-only; you only need to copy thesrc/tree.hhheader file into your project and you are good to go.

Then scan the example below and consult thedocumentation.

The following is a small sample program to illustrate how tree.hh is used:

#include <algorithm>#include <string>#include <iostream>#include "tree.hh"using namespace std;int main(int, char **)   {   tree<string> tr;   tree<string>::iterator top, one, two, loc, banana;   top=tr.begin();   one=tr.insert(top, "one");   two=tr.append_child(one, "two");   tr.append_child(two, "apple");   banana=tr.append_child(two, "banana");   tr.append_child(banana,"cherry");   tr.append_child(two, "peach");   tr.append_child(one,"three");   loc=find(tr.begin(), tr.end(), "two");   if(loc!=tr.end()) {   tree<string>::sibling_iterator sib=tr.begin(loc);   while(sib!=tr.end(loc)) {     cout << (*sib) << endl;     ++sib;     }   cout << endl;   tree<string>::iterator sib2=tr.begin(loc);   tree<string>::iterator end2=tr.end(loc);   while(sib2!=end2) {     for(int i=0; i<tr.depth(sib2)-2; ++i)        cout << " ";     cout << (*sib2) << endl;     ++sib2;     }   }}

The output of this program is:

applebananapeachapplebanana cherrypeach

Note that this example only has one element at the top of the tree (inthis case that is the node containing one) but it is possible tohave an arbitary number of such elements (then the tree is more like a"bush"). Observe the way in which the two types of iterators work. Thefirst block of output, obtained using the sibling_iterator, onlydisplays the children directly below two. The second block iteratesover all children at any depth below two. In the second outputblock, the depth member has been used to determine the distance of agiven node to the root of the tree.

Thetree.hh library is used in various projects:

• Cadabra (https://cadabra.science/), a field-theory motivatedapproach to symbolic computer algebra.
• Taxator-tk (https://github.com/fungs/taxator-tk/), a set of programsfor the taxonomic analysis of nucleotide sequence data.
• Gnash (http://www.gnu.org/software/gnash/), a GNU Flash movieplayer. Previously, it was only possible to play flash movies withproprietary software. While there are some other free flash players,none support anything beyond SWF v4. Gnash is based on GameSWF, andsupports many SWF v7 features.
• htmlcxx (http://htmlcxx.sourceforge.net/), a simple non-validatingcss1 and html parser for C++.
• Principles of Compiler Design(http://www.cs.sfu.ca/~anoop/courses/CMPT-379-Fall-2007/index.html),a course in compiler design at the Simon Fraser University, Canada.
• liborigin (http://sourceforge.net/projects/liborigin/), a libraryfor reading OriginLab OPJ project files, which is used by QtiPlot(http://soft.proindependent.com/qtiplot.html) and LabPlot(http://labplot.sourceforge.net/), two applications for dataanalysis and visualisation.
• EChem++(http://www.echem.uni-tuebingen.de/~bs/echem/software/EChem++/echem++.shtml),a project realizing the idea of a Problem Solving Environment (PSE)in the field of computational electrochemistry. Computer controlledexperimental measurements, numerical simulation and analysis ofelectrochemical processes will be combined under a common userinterface.
• LZCS (http://www.infor.uva.es/~jadiego/), a semistructured documenttransformation tool. LZCS compresses structured documents takingadvantage of the redundant information that can appear in thestructure. The main idea is that frequently repeated subtrees mayexist and these can be replaced by a backward reference to theirfirst occurance. See the paper(http://www.dcc.uchile.cl/~gnavarro/ps/dcc04.1.ps.gz).
• libOFX (http://libofx.sourceforge.net/), a parser and an APIdesigned to allow applications to very easily support OFX commandresponses, usually provided by financial institutions for statementdownloads.
• A genetic programming project(http://www.cs.adfa.edu.au/~shanyin/publications/peel.pdf).
• FreeLing (http://nlp.lsi.upc.edu/freeling/) a library providinglanguage analysis services (such as morfological analysis, daterecognition, PoS tagging, and so on.

Let me know about your project when you are usingtree.hh, so thatI can add it to the list.

In principle, the tree.hh code is available under the terms of the GNUGeneral Public License version 3. However, if you would like to usetree.hh under different conditions, contact me and we will worksomething out.