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#include "mcrl2/atermpp/aterm.h"
14
15#include <boost/iterator/iterator_facade.hpp>
16
17namespace atermpp
18{
19
20namespace
21{
26}
27
28template <typename Term>
30
31template <class Term, class ForwardTraversalIterator, class Transformer>
33 ForwardTraversalIterator p,
34 const std::size_t size,
35 Transformer transformer);
36
38template <typename Term>
40{
41 protected:
42
43 template <class Term1, class ForwardTraversalIterator, class Transformer>
45 ForwardTraversalIterator p,
46 const std::size_t size,
47 Transformer transformer);
48
49
50 static const function_symbol& tree_empty_function() { return g_empty; }
51 static const function_symbol& tree_single_node_function() { return g_single_tree_node; }
52 static const function_symbol& tree_node_function() { return g_tree_node; }
53 static const aterm& empty_tree() { return g_empty_tree; }
54
55 template < typename ForwardTraversalIterator, class Transformer >
56 static void make_tree_helper(aterm& result, ForwardTraversalIterator& p, const std::size_t size, Transformer transformer)
57 {
58 assert(size>1);
60 [&size, &transformer, &p](aterm& target)
61 {
62 assert(size>1);
63
64 std::size_t new_size = (size + 1) >> 1; // size/2 rounded up.
65 if (new_size==1)
66 {
67 transformer(reinterpret_cast<Term&>(target), *(p++));
68 }
69 else make_tree_helper(target, p, new_size, transformer);
70 },
71 [&size, &transformer, &p](aterm& target)
72 {
73 assert(size>1);
74
75 std::size_t new_size = size >> 1; // size/2 rounded down.
76 if (new_size==1)
77 {
78 transformer(reinterpret_cast<Term&>(target), *(p++));
79 }
80 else make_tree_helper(target, p, new_size, transformer);
81 });
82 }
83
84 template < typename ForwardTraversalIterator, class Transformer >
85 static void make_tree(aterm& result, ForwardTraversalIterator& p, const std::size_t size, Transformer transformer)
86 {
87 if (size==0)
88 {
89 result = empty_tree();
90 }
91 else if (size==1)
92 {
94 [&transformer,&p](aterm& target)
95 {
96 transformer(reinterpret_cast<Term&>(target), *(p++));
97 });
98 }
99 else
100 {
101 make_tree_helper(result, p, size, transformer);
102 }
103 }
104
106 : aterm(t)
107 {}
108
109 public:
110
112 typedef Term value_type;
113
115 typedef Term* pointer;
116
118 typedef Term& reference;
119
121 typedef const Term const_reference;
122
124 typedef std::size_t size_type;
125
127 typedef ptrdiff_t difference_type;
128
131 : aterm(empty_tree())
132 {}
133
135 term_balanced_tree(const term_balanced_tree&) noexcept = default;
136
139
141 term_balanced_tree& operator=(const term_balanced_tree&) noexcept = default;
142
144 term_balanced_tree& operator=(term_balanced_tree&&) noexcept = default;
145
147 explicit term_balanced_tree(const aterm& tree)
148 : aterm(tree.function() == tree_empty_function() ||
150 tree.function() == tree_node_function()?
151 tree:
153 {
154 assert(function() == tree_empty_function() ||
157 }
158
162 template<typename ForwardTraversalIterator>
163 term_balanced_tree(ForwardTraversalIterator first, const std::size_t size)
164 {
165 make_tree(*this, first, size, [](Term& result, const Term& t) { result=t; });
166 }
167
173 template<typename ForwardTraversalIterator, typename Transformer>
174 term_balanced_tree(ForwardTraversalIterator first, const std::size_t size, Transformer transformer)
175 {
176 make_tree(*this, first, size, transformer);
177 }
178
182 const aterm& left_branch() const
183 {
184 assert(is_node());
185 return aterm::operator[](0);
186 }
187
191 const aterm& right_branch() const
192 {
193 assert(is_node());
194 return aterm::operator[](1);
195 }
196
202 const Term& operator[](std::size_t position) const
203 {
204 return element_at(position, size());
205 }
206
214 const Term& element_at(std::size_t position, std::size_t size) const
215 {
216 assert(size == this->size());
217 assert(position < size);
218
219 if (size>1)
220 {
221 std::size_t left_size = (size + 1) >> 1;
222
223 if (position < left_size)
224 {
225 const aterm& left(left_branch());
226 if (left.function() == tree_node_function())
227 {
228 return down_cast<term_balanced_tree<Term>>(left_branch()).element_at(position, left_size);
229 }
230 else
231 {
232 return reinterpret_cast<const Term&>(left);
233 }
234 }
235 else
236 {
237 // down_cast<term_balanced_tree<Term>>(right_branch()).element_at(position-left_size, size - left_size);
238 const aterm& right(right_branch());
239 if (right.function() == tree_node_function())
240 {
241 return down_cast<term_balanced_tree<Term>>(right_branch()).element_at(position-left_size, size-left_size);
242 }
243 else
244 {
245 return reinterpret_cast<const Term&>(right);
246 }
247 }
248 }
249
250 return vertical_cast<Term>((static_cast<aterm>(*this))[0]);
251 }
252
257 {
258 if (is_node())
259 {
260 const aterm& left=left_branch();
261 std::size_t result = (left.function() == tree_node_function()?down_cast<term_balanced_tree<Term>>(left).size():1);
262 const aterm& right=right_branch();
263 return result + (right.function() == tree_node_function()?down_cast<term_balanced_tree<Term>>(right).size():1);
264 }
265 return (empty()) ? 0 : 1;
266 }
267
270 bool empty() const
271 {
272 return m_term->function() == tree_empty_function();
273 }
274
277 bool is_node() const
278 {
279 return function() == tree_node_function();
280 }
281
282 class iterator: public boost::iterator_facade<
283 iterator, // Derived
284 const Term, // Value
285 boost::forward_traversal_tag, // CategoryOrTraversal
286 const Term& // Reference
287 >
288 {
289 private:
291
293
294 static constexpr std::size_t maximal_size_of_stack = 20; // We assume here that a tree never has more than 2^20 leaves, o
295 // equivalently that states consist of not more than 2^20 data_expressions.
297 std::size_t m_top_of_stack; // First element in the stack that is empty.
298
301 const Term& dereference() const
302 {
303 assert(m_top_of_stack > 0);
304 return static_cast<const Term&>(m_stack[m_top_of_stack-1]);
305 }
306
308 bool equal(const iterator& other) const
309 {
310 if (m_top_of_stack != other.m_top_of_stack)
311 {
312 return false;
313 }
314
315 for(std::size_t i = 0; i < m_top_of_stack; ++i)
316 {
317 if (m_stack[i] != other.m_stack[i])
318 {
319 return false;
320 }
321 }
322 return true;
323 }
324
327 {
329 if (m_top_of_stack>0)
330 {
332 if (current.function() != Tree::tree_node_function())
333 {
334 // This subtree is empty.
335 return;
336 }
337
339 do
340 {
341 m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
342 current = static_cast<Tree&>(current).left_branch();
343 }
344 while (current.function() == Tree::tree_node_function());
345
346 m_stack[m_top_of_stack++] = current;
347 }
348 }
349
351 {
352 if (tree.empty())
353 {
354 return;
355 }
356
357 if (!tree.is_node()) // This is a singleton tree.
358 {
359 m_stack[m_top_of_stack++] = tree[0];
360 }
361 else
362 {
363 unprotected_aterm_core current = tree;
364
365 while (current.function() == Tree::tree_node_function())
366 {
368 m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
369 current = static_cast<Tree&>(current).left_branch();
370 }
371
373 m_stack[m_top_of_stack++] = current;
374 }
375 }
376
377 public:
378
380 : m_top_of_stack(0)
381 { }
382
384 : m_top_of_stack(0)
385 {
386 initialise(tree);
387 }
388
389 iterator(const iterator& other)
391 {
392 for(std::size_t i = 0; i < m_top_of_stack; ++i)
393 {
394 m_stack[i] = other.m_stack[i];
395 }
396 }
397
398 };
399
403 {
404 return iterator(*this);
405 }
406
409 iterator end() const
410 {
411 return iterator();
412 }
413
414};
415
416template <class Term, class ForwardTraversalIterator, class Transformer>
418 ForwardTraversalIterator p,
419 const std::size_t size,
420 Transformer transformer)
421{
422 term_balanced_tree<Term>::make_tree(result, p, size, transformer);
423}
424
427
428
429inline bool is_aterm_balanced_tree(const aterm& t)
430{
431 return t.defined() && (t.function()==g_empty ||
432 t.function()==g_single_tree_node ||
433 t.function()==g_tree_node);
434}
435
436template <class Term>
437std::string pp(const term_balanced_tree<Term> t)
438{
439 std::stringstream ss;
440 for(typename term_balanced_tree<Term>::iterator i = t.begin(); i != t.end(); ++i)
441 {
442 if (i!=t.begin())
443 {
444 ss << ", ";
445 }
446 ss << pp(*i);
447 }
448 return ss.str();
449}
450} // namespace atermpp
451
452namespace std
453{
459template <class T>
461{
462 t1.swap(t2);
463}
464
466template<class T>
467struct hash<atermpp::term_balanced_tree<T> >
468{
469 std::size_t operator()(const atermpp::term_balanced_tree<T>& t) const
470 {
471 return std::hash<atermpp::aterm>()(t);
472 }
473};
474} // namespace std
475
476
477#endif // MCRL2_ATERMPP_ATERM_BALANCED_TREE_H
The term_appl class represents function application.
const aterm & operator[](const size_type i) const
Returns the i-th argument.
Definition aterm.h:187
const function_symbol & function() const
Returns the function symbol belonging to an aterm.
Definition aterm.h:144
This class stores a term followed by N arguments. Where N should be equal to the arity of the functio...
Definition aterm.h:34
const function_symbol & function() const noexcept
Definition aterm_core.h:55
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.
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 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...
Definition aterm_core.h:32
void swap(unprotected_aterm_core &t) noexcept
Swaps this term with its argument.
Definition aterm_core.h:152
bool defined() const
Returns true if this term is not equal to the term assigned by the default constructor of aterms,...
Definition aterm_core.h:143
const detail::_aterm * m_term
Definition aterm_core.h:36
const function_symbol & function() const
Yields the function symbol in an aterm.
Definition aterm_core.h:161
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:440
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...
Definition aterm.h:213
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)
STL namespace.
void swap(atermpp::unprotected_aterm_core &t1, atermpp::unprotected_aterm_core &t2) noexcept
Swaps two aterms.
Definition aterm.h:462
std::size_t operator()(const atermpp::term_balanced_tree< T > &t) const
#define hash(l, r, m)
Definition tree_set.cpp:23