10#ifndef MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
11#define MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
15#include <boost/iterator/iterator_facade.hpp>
28template <
typename Term>
31template <
class Term,
class ForwardTraversalIterator,
class Transformer>
33 ForwardTraversalIterator p,
34 const std::size_t size,
35 Transformer transformer);
38template <
typename Term>
43 template <
class Term1,
class ForwardTraversalIterator,
class Transformer>
45 ForwardTraversalIterator p,
46 const std::size_t
size,
47 Transformer transformer);
55 template <
typename ForwardTraversalIterator,
class Transformer >
64 std::size_t new_size = (
size + 1) >> 1;
67 transformer(
reinterpret_cast<Term&
>(target), *(p++));
75 std::size_t new_size =
size >> 1;
78 transformer(
reinterpret_cast<Term&
>(target), *(p++));
84 template <
typename ForwardTraversalIterator,
class Transformer >
85 static void make_tree(
aterm& result, ForwardTraversalIterator& p,
const std::size_t
size, Transformer transformer)
94 [&transformer,&p](
aterm& target)
96 transformer(
reinterpret_cast<Term&
>(target), *(p++));
162 template<
typename ForwardTraversalIterator>
165 make_tree(*
this, first,
size, [](Term& result,
const Term& t) { result=t; });
173 template<
typename ForwardTraversalIterator,
typename Transformer>
217 assert(position <
size);
221 std::size_t left_size = (
size + 1) >> 1;
223 if (position < left_size)
232 return reinterpret_cast<const Term&
>(left);
245 return reinterpret_cast<const Term&
>(right);
250 return vertical_cast<Term>((
static_cast<aterm>(*
this))[0]);
265 return (
empty()) ? 0 : 1;
285 boost::forward_traversal_tag,
416template <
class Term,
class ForwardTraversalIterator,
class Transformer>
418 ForwardTraversalIterator p,
419 const std::size_t size,
420 Transformer transformer)
439 std::stringstream ss;
471 return std::hash<atermpp::aterm>()(t);
The term_appl class represents function application.
const aterm & operator[](const size_type i) const
Returns the i-th argument.
const function_symbol & function() const
Returns the function symbol belonging to an aterm.
This class stores a term followed by N arguments. Where N should be equal to the arity of the functio...
const function_symbol & function() const noexcept
std::size_t m_top_of_stack
unprotected_aterm_core m_stack[maximal_size_of_stack]
static constexpr std::size_t maximal_size_of_stack
void initialise(const term_balanced_tree< Term > &tree)
const Term & dereference() const
Dereference operator.
friend class boost::iterator_core_access
iterator(const iterator &other)
bool equal(const iterator &other) const
Equality operator.
iterator(const term_balanced_tree< Term > &tree)
void increment()
Increments the iterator.
Read-only balanced binary tree of terms.
bool is_node() const
Returns true iff the tree is a node with a left and right subtree.
friend void make_term_balanced_tree(term_balanced_tree< Term1 > &result, ForwardTraversalIterator p, const std::size_t size, Transformer transformer)
static void make_tree_helper(aterm &result, ForwardTraversalIterator &p, const std::size_t size, Transformer transformer)
size_type size() const
Returns the size of the term_balanced_tree.
term_balanced_tree(term_balanced_tree &&) noexcept=default
Move constructor.
bool empty() const
Returns true if tree is empty.
Term & reference
Reference to T.
static const aterm & empty_tree()
static void make_tree(aterm &result, ForwardTraversalIterator &p, const std::size_t size, Transformer transformer)
term_balanced_tree(ForwardTraversalIterator first, const std::size_t size)
Creates an term_balanced_tree with a copy of a range.
std::size_t size_type
An unsigned integral type.
static const function_symbol & tree_single_node_function()
const aterm & left_branch() const
Get the left branch of the tree.
term_balanced_tree(const term_balanced_tree &) noexcept=default
Copy constructor.
Term * pointer
Pointer to T.
Term value_type
The type of object, T stored in the term_balanced_tree.
term_balanced_tree(ForwardTraversalIterator first, const std::size_t size, Transformer transformer)
Creates an term_balanced_tree with a copy of a range, where a transformer is applied to each term bef...
static const function_symbol & tree_node_function()
const Term & operator[](std::size_t position) const
Element indexing operator.
iterator begin() const
Returns an iterator pointing to the beginning of the term_balanced_tree.
iterator end() const
Returns an iterator pointing to the end of the term_balanced_tree.
term_balanced_tree()
Default constructor. Creates an empty tree.
const aterm & right_branch() const
Get the left branch of the tree.
const Term const_reference
Const reference to T.
const Term & element_at(std::size_t position, std::size_t size) const
Get an element at the indicated position.
static const function_symbol & tree_empty_function()
term_balanced_tree(detail::_term_appl *t)
ptrdiff_t difference_type
A signed integral type.
An unprotected term does not change the reference count of the shared term when it is copied or moved...
void swap(unprotected_aterm_core &t) noexcept
Swaps this term with its argument.
bool defined() const
Returns true if this term is not equal to the term assigned by the default constructor of aterms,...
const detail::_aterm * m_term
const function_symbol & function() const
Yields the function symbol in an aterm.
global_function_symbol g_tree_node("@node@", 2)
global_function_symbol g_empty("@empty@", 0)
aterm g_empty_tree(g_empty)
global_function_symbol g_single_tree_node("@single_node@", 1)
The main namespace for the aterm++ library.
std::string pp(const atermpp::aterm &t)
Transform an aterm to an ascii string.
term_balanced_tree< aterm > aterm_balanced_tree
A term_balanced_tree with elements of type aterm.
void make_term_appl(Term &target, const function_symbol &sym, ForwardIterator begin, ForwardIterator end)
Constructor an aterm in a variable based on a function symbol and an forward iterator providing the a...
void make_term_balanced_tree(term_balanced_tree< Term > &result, ForwardTraversalIterator p, const std::size_t size, Transformer transformer)
bool is_aterm_balanced_tree(const aterm &t)
void swap(atermpp::unprotected_aterm_core &t1, atermpp::unprotected_aterm_core &t2) noexcept
Swaps two aterms.
std::size_t operator()(const atermpp::term_balanced_tree< T > &t) const