mCRL2
Loading...
Searching...
No Matches
aterm_balanced_tree.h
Go to the documentation of this file.
1// Author(s): Jeroen van der Wulp
2// Copyright: see the accompanying file COPYING or copy at
3// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9
10#ifndef MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
11#define MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
12
13/* NOTE: A aterm_balanced_tree is actually not always an aterm_appl, namely when numbers
14 * or lists are stored in it. In that case the balanced tree of size 1 is a number
15 * or a list. So, a proper type for a term_balanced_tree should be "aterm" and not
16 * aterm_appl. This ought to be adapted. */
17
19
20#include <boost/iterator/iterator_facade.hpp>
21
22namespace atermpp
23{
24
25namespace
26{
31}
32
33template <typename Term>
35
36template <class Term, class ForwardTraversalIterator, class Transformer>
38 ForwardTraversalIterator p,
39 const std::size_t size,
40 Transformer transformer);
41
43template <typename Term>
45{
46 protected:
47
48 template <class Term1, class ForwardTraversalIterator, class Transformer>
50 ForwardTraversalIterator p,
51 const std::size_t size,
52 Transformer transformer);
53
54
55 static const function_symbol& tree_empty_function() { return g_empty; }
56 static const function_symbol& tree_single_node_function() { return g_single_tree_node; }
57 static const function_symbol& tree_node_function() { return g_tree_node; }
58 static const aterm_appl& empty_tree() { return g_empty_tree; }
59
60 template < typename ForwardTraversalIterator, class Transformer >
61 static void make_tree_helper(aterm& result, ForwardTraversalIterator& p, const std::size_t size, Transformer transformer)
62 {
63 assert(size>1);
65 [&size, &transformer, &p](aterm& target)
66 {
67 assert(size>1);
68
69 std::size_t new_size = (size + 1) >> 1; // size/2 rounded up.
70 if (new_size==1)
71 {
72 transformer(reinterpret_cast<Term&>(target), *(p++));
73 }
74 else make_tree_helper(target, p, new_size, transformer);
75 },
76 [&size, &transformer, &p](aterm& target)
77 {
78 assert(size>1);
79
80 std::size_t new_size = size >> 1; // size/2 rounded down.
81 if (new_size==1)
82 {
83 transformer(reinterpret_cast<Term&>(target), *(p++));
84 }
85 else make_tree_helper(target, p, new_size, transformer);
86 });
87 }
88
89 template < typename ForwardTraversalIterator, class Transformer >
90 static void make_tree(aterm& result, ForwardTraversalIterator& p, const std::size_t size, Transformer transformer)
91 {
92 if (size==0)
93 {
94 result = empty_tree();
95 }
96 else if (size==1)
97 {
99 [&transformer,&p](aterm& target)
100 {
101 transformer(reinterpret_cast<Term&>(target), *(p++));
102 });
103 }
104 else
105 {
106 make_tree_helper(result, p, size, transformer);
107 }
108 }
109
111 : term_appl(static_cast<detail::_term_appl*>(t))
112 {}
113
114 public:
115
117 typedef Term value_type;
118
120 typedef Term* pointer;
121
123 typedef Term& reference;
124
126 typedef const Term const_reference;
127
129 typedef std::size_t size_type;
130
132 typedef ptrdiff_t difference_type;
133
137 {}
138
140 term_balanced_tree(const term_balanced_tree&) noexcept = default;
141
144
146 term_balanced_tree& operator=(const term_balanced_tree&) noexcept = default;
147
149 term_balanced_tree& operator=(term_balanced_tree&&) noexcept = default;
150
152 explicit term_balanced_tree(const aterm& tree)
155 tree.function() == tree_node_function()?
156 down_cast<aterm_appl>(tree):
158 {
159 assert(function() == tree_empty_function() ||
162 }
163
167 template<typename ForwardTraversalIterator>
168 term_balanced_tree(ForwardTraversalIterator first, const std::size_t size)
169 {
170 make_tree(*this, first, size, [](Term& result, const Term& t) { result=t; });
171 }
172
178 template<typename ForwardTraversalIterator, typename Transformer>
179 term_balanced_tree(ForwardTraversalIterator first, const std::size_t size, Transformer transformer)
180 {
181 make_tree(*this, first, size, transformer);
182 }
183
187 const aterm& left_branch() const
188 {
189 assert(is_node());
190 return aterm_appl::operator[](0);
191 }
192
196 const aterm& right_branch() const
197 {
198 assert(is_node());
199 return aterm_appl::operator[](1);
200 }
201
207 const Term& operator[](std::size_t position) const
208 {
209 return element_at(position, size());
210 }
211
219 const Term& element_at(std::size_t position, std::size_t size) const
220 {
221 assert(size == this->size());
222 assert(position < size);
223
224 if (size>1)
225 {
226 std::size_t left_size = (size + 1) >> 1;
227
228 if (position < left_size)
229 {
230 const aterm& left(left_branch());
231 if (left.function() == tree_node_function())
232 {
233 return down_cast<term_balanced_tree<Term>>(left_branch()).element_at(position, left_size);
234 }
235 else
236 {
237 return reinterpret_cast<const Term&>(left);
238 }
239 }
240 else
241 {
242 // down_cast<term_balanced_tree<Term>>(right_branch()).element_at(position-left_size, size - left_size);
243 const aterm& right(right_branch());
244 if (right.function() == tree_node_function())
245 {
246 return down_cast<term_balanced_tree<Term>>(right_branch()).element_at(position-left_size, size-left_size);
247 }
248 else
249 {
250 return reinterpret_cast<const Term&>(right);
251 }
252 }
253 }
254
255 return vertical_cast<Term>((static_cast<aterm_appl>(*this))[0]);
256 }
257
262 {
263 if (is_node())
264 {
265 const aterm& left=left_branch();
266 std::size_t result = (left.function() == tree_node_function()?down_cast<term_balanced_tree<Term>>(left).size():1);
267 const aterm& right=right_branch();
268 return result + (right.function() == tree_node_function()?down_cast<term_balanced_tree<Term>>(right).size():1);
269 }
270 return (empty()) ? 0 : 1;
271 }
272
275 bool empty() const
276 {
277 return m_term->function() == tree_empty_function();
278 }
279
282 bool is_node() const
283 {
284 return function() == tree_node_function();
285 }
286
287 class iterator: public boost::iterator_facade<
288 iterator, // Derived
289 const Term, // Value
290 boost::forward_traversal_tag, // CategoryOrTraversal
291 const Term& // Reference
292 >
293 {
294 private:
296
298
299 static constexpr std::size_t maximal_size_of_stack = 20; // We assume here that a tree never has more than 2^20 leaves, o
300 // equivalently that states consist of not more than 2^20 data_expressions.
302 std::size_t m_top_of_stack; // First element in the stack that is empty.
303
306 const Term& dereference() const
307 {
308 assert(m_top_of_stack > 0);
309 return static_cast<const Term&>(m_stack[m_top_of_stack-1]);
310 }
311
313 bool equal(const iterator& other) const
314 {
315 if (m_top_of_stack != other.m_top_of_stack)
316 {
317 return false;
318 }
319
320 for(std::size_t i = 0; i < m_top_of_stack; ++i)
321 {
322 if (m_stack[i] != other.m_stack[i])
323 {
324 return false;
325 }
326 }
327 return true;
328 }
329
332 {
334 if (m_top_of_stack>0)
335 {
337 if (current.function() != Tree::tree_node_function())
338 {
339 // This subtree is empty.
340 return;
341 }
342
344 do
345 {
346 m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
347 current = static_cast<Tree&>(current).left_branch();
348 }
349 while (current.function() == Tree::tree_node_function());
350
351 m_stack[m_top_of_stack++] = current;
352 }
353 }
354
356 {
357 if (tree.empty())
358 {
359 return;
360 }
361
362 if (!tree.is_node()) // This is a singleton tree.
363 {
364 m_stack[m_top_of_stack++] = tree[0];
365 }
366 else
367 {
368 unprotected_aterm current = tree;
369
370 while (current.function() == Tree::tree_node_function())
371 {
373 m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
374 current = static_cast<Tree&>(current).left_branch();
375 }
376
378 m_stack[m_top_of_stack++] = current;
379 }
380 }
381
382 public:
383
385 : m_top_of_stack(0)
386 { }
387
389 : m_top_of_stack(0)
390 {
391 initialise(tree);
392 }
393
394 iterator(const iterator& other)
396 {
397 for(std::size_t i = 0; i < m_top_of_stack; ++i)
398 {
399 m_stack[i] = other.m_stack[i];
400 }
401 }
402
403 };
404
408 {
409 return iterator(*this);
410 }
411
414 iterator end() const
415 {
416 return iterator();
417 }
418
419};
420
421template <class Term, class ForwardTraversalIterator, class Transformer>
423 ForwardTraversalIterator p,
424 const std::size_t size,
425 Transformer transformer)
426{
427 term_balanced_tree<Term>::make_tree(result, p, size, transformer);
428}
429
432
433
435{
436 return t.defined() && (t.function()==g_empty ||
437 t.function()==g_single_tree_node ||
438 t.function()==g_tree_node);
439}
440
441template <class Term>
442std::string pp(const term_balanced_tree<Term> t)
443{
444 std::stringstream ss;
445 for(typename term_balanced_tree<Term>::iterator i = t.begin(); i != t.end(); ++i)
446 {
447 if (i!=t.begin())
448 {
449 ss << ", ";
450 }
451 ss << pp(*i);
452 }
453 return ss.str();
454}
455} // namespace atermpp
456
457namespace std
458{
464template <class T>
466{
467 t1.swap(t2);
468}
469
471template<class T>
472struct hash<atermpp::term_balanced_tree<T> >
473{
474 std::size_t operator()(const atermpp::term_balanced_tree<T>& t) const
475 {
476 return std::hash<atermpp::aterm>()(t);
477 }
478};
479} // namespace std
480
481
482#endif // MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
The term_appl class represents function application.
The aterm base class that provides protection of the underlying shared terms.
Definition aterm.h:186
This class stores a term followed by N arguments. Where N should be equal to the arity of the functio...
Definition aterm_appl.h:32
const function_symbol & function() const noexcept
Definition aterm.h:55
const function_symbol & function() const
Returns the function symbol belonging to an aterm_appl.
Definition aterm_appl.h:174
const aterm & operator[](const size_type i) const
Returns the i-th argument.
Definition aterm_appl.h:217
static constexpr std::size_t maximal_size_of_stack
void initialise(const term_balanced_tree< Term > &tree)
const Term & dereference() const
Dereference operator.
unprotected_aterm m_stack[maximal_size_of_stack]
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 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 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.
static const aterm_appl & empty_tree()
An unprotected term does not change the reference count of the shared term when it is copied or moved...
Definition aterm.h:36
const function_symbol & function() const
Yields the function symbol in an aterm.
Definition aterm.h:165
const detail::_aterm * m_term
Definition aterm.h:40
bool defined() const
Returns true if this term is not equal to the term assigned by the default constructor of aterms,...
Definition aterm.h:147
void swap(unprotected_aterm &t) noexcept
Swaps this term with its argument.
Definition aterm.h:156
global_function_symbol g_tree_node("@node@", 2)
global_function_symbol g_empty("@empty@", 0)
global_function_symbol g_single_tree_node("@single_node@", 1)
The main namespace for the aterm++ library.
Definition algorithm.h:21
std::string pp(const atermpp::aterm &t)
Transform an aterm to an ascii string.
Definition aterm.h:362
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_appl in a variable based on a function symbol and an forward iterator providing ...
Definition aterm_appl.h:239
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_appl &t)
STL namespace.
void swap(atermpp::unprotected_aterm &t1, atermpp::unprotected_aterm &t2) noexcept
Swaps two aterms.
Definition aterm.h:384
std::size_t operator()(const atermpp::term_balanced_tree< T > &t) const
#define hash(l, r, m)
Definition tree_set.cpp:23