// STL-like templated tree class.
//
// Copyright (C) 2001-2020 Kasper Peeters <kasper@phi-sci.com>
// Distributed under the GNU General Public License version 3.
//
// Special permission to use tree.hh under the conditions of a
// different license can be requested from the author.
/** \mainpage tree.hh
\author Kasper Peeters
\version 3.18
\date 13-Feb-2021
\see http://tree.phi-sci.com/
\see http://github.com/kpeeters/tree.hh/
The tree.hh library for C++ provides an STL-like container class
for n-ary trees, templated over the data stored at the
nodes. Various types of iterators are provided (post-order,
pre-order, and others). Where possible the access methods are
compatible with the STL or alternative algorithms are
available.
*/
#ifndef tree_hh_
#define tree_hh_
#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>
#include <queue>
#include <algorithm>
#include <cstddef>
#include <string>
/// A node in the tree, combining links to other nodes as well as the actual data.
template<class T>
class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
public:
tree_node_();
tree_node_(const T&);
tree_node_(T&&);
tree_node_<T> *parent;
tree_node_<T> *first_child, *last_child;
tree_node_<T> *prev_sibling, *next_sibling;
T data;
};
template<class T>
tree_node_<T>::tree_node_()
: parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0)
{
}
template<class T>
tree_node_<T>::tree_node_(const T& val)
: parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), data(val)
{
}
template<class T>
tree_node_<T>::tree_node_(T&& val)
: parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), data(val)
{
}
// Throw an exception with a stacktrace.
//template <class E>
//void throw_with_trace(const E& e)
// {
// throw boost::enable_error_info(e)
// << traced(boost::stacktrace::stacktrace());
// }
class navigation_error : public std::logic_error {
public:
navigation_error(const std::string& s) : std::logic_error(s)
{
// assert(1==0);
// std::ostringstream str;
// std::cerr << boost::stacktrace::stacktrace() << std::endl;
// str << boost::stacktrace::stacktrace();
// stacktrace=str.str();
}
// virtual const char *what() const noexcept override
// {
// return (std::logic_error::what()+std::string("; ")+stacktrace).c_str();
// }
//
// std::string stacktrace;
};
template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree {
protected:
typedef tree_node_<T> tree_node;
public:
/// Value of the data stored at a node.
typedef T value_type;
class iterator_base;
class pre_order_iterator;
class post_order_iterator;
class sibling_iterator;
class leaf_iterator;
tree(); // empty constructor
tree(const T&); // constructor setting given element as head
tree(const iterator_base&);
tree(const tree<T, tree_node_allocator>&); // copy constructor
tree(tree<T, tree_node_allocator>&&); // move constructor
~tree();
tree<T,tree_node_allocator>& operator=(const tree<T, tree_node_allocator>&); // copy assignment
tree<T,tree_node_allocator>& operator=(tree<T, tree_node_allocator>&&); // move assignment
/// Base class for iterators, only pointers stored, no traversal logic.
#ifdef __SGI_STL_PORT
class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
#else
class iterator_base {
#endif
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
iterator_base();
iterator_base(tree_node *);
T& operator*() const;
T* operator->() const;
/// When called, the next increment/decrement skips children of this node.
void skip_children();
void skip_children(bool skip);
/// Number of children of the node pointed to by the iterator.
unsigned int number_of_children() const;
sibling_iterator begin() const;
sibling_iterator end() const;
tree_node *node;
protected:
bool skip_current_children_;
};
/// Depth-first iterator, first accessing the node, then its children.
class pre_order_iterator : public iterator_base {
public:
pre_order_iterator();
pre_order_iterator(tree_node *);
pre_order_iterator(const iterator_base&);
pre_order_iterator(const sibling_iterator&);
bool operator==(const pre_order_iterator&) const;
bool operator!=(const pre_order_iterator&) const;
pre_order_iterator& operator++();
pre_order_iterator& operator--();
pre_order_iterator operator++(int);
pre_order_iterator operator--(int);
pre_order_iterator& operator+=(unsigned int);
pre_order_iterator& operator-=(unsigned int);
pre_order_iterator& next_skip_children();
};
/// Depth-first iterator, first accessing the children, then the node itself.
class post_order_iterator : public iterator_base {
public:
post_order_iterator();
post_order_iterator(tree_node *);
post_order_iterator(const iterator_base&);
post_order_iterator(const sibling_iterator&);
bool operator==(const post_order_iterator&) const;
bool operator!=(const post_order_iterator&) const;
post_order_iterator& operator++();
post_order_iterator& operator--();
post_order_iterator operator++(int);
post_order_iterator operator--(int);
post_order_iterator& operator+=(unsigned int);
post_order_iterator& operator-=(unsigned int);
/// Set iterator to the first child as deep as possible down the tree.
void descend_all();
};
/// Breadth-first iterator, using a queue
class breadth_first_queued_iterator : public iterator_base {
public:
breadth_first_queued_iterator();
breadth_first_queued_iterator(tree_node *);
breadth_first_queued_iterator(const iterator_base&);
bool operator==(const breadth_first_queued_iterator&) const;
bool operator!=(const breadth_first_queued_iterator&) const;
breadth_first_queued_iterator& operator++();
breadth_first_queued_iterator operator++(int);
breadth_first_queued_iterator& operator+=(unsigned int);
private:
std::queue<tree_node *> traversal_queue;
};
/// The default iterator types throughout the tree class.
typedef pre_order_iterator iterator;
typedef breadth_first_queued_iterator breadth_first_iterator;
/// Iterator which traverses only the nodes at a given depth from the root.
class fixed_depth_iterator : public iterator_base {
public:
fixed_depth_iterator();
fixed_depth_iterator(tree_node *);
fixed_depth_iterator(const iterator_base&);
fixed_depth_iterator(const sibling_iterator&);
fixed_depth_iterator(const fixed_depth_iterator&);
bool operator==(const fixed_depth_iterator&) const;
bool operator!=(const fixed_depth_iterator&) const;
fixed_depth_iterator& operator++();
fixed_depth_iterator& operator--();
fixed_depth_iterator operator++(int);
fixed_depth_iterator operator--(int);
fixed_depth_iterator& operator+=(unsigned int);
fixed_depth_iterator& operator-=(unsigned int);
tree_node *top_node;
};
/// Iterator which traverses only the nodes which are siblings of each other.
class sibling_iterator : public iterator_base {
public:
sibling_iterator();
sibling_iterator(tree_node *);
sibling_iterator(const sibling_iterator&);
sibling_iterator(const iterator_base&);
bool operator==(const sibling_itera
