LCOV - code coverage report
Current view: top level - atermpp/include/mcrl2/atermpp - aterm_balanced_tree.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 115 116 99.1 %
Date: 2020-09-16 00:45:56 Functions: 75 86 87.2 %
Legend: Lines: hit not hit

          Line data    Source code
       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_appl.h"
      14             : 
      15             : #include <boost/iterator/iterator_facade.hpp>
      16             : 
      17             : namespace atermpp
      18             : {
      19             : 
      20             : namespace
      21             : {
      22         233 :   global_function_symbol g_empty("@empty@", 0);
      23         233 :   global_function_symbol g_tree_node("@node@", 2);
      24         233 :   aterm_appl g_empty_tree(g_empty);
      25             : }
      26             : 
      27             : /// \brief Read-only balanced binary tree of terms.
      28             : template <typename Term>
      29      152161 : class term_balanced_tree : public aterm_appl
      30             : {
      31             :   protected:
      32             : 
      33      160256 :     static const atermpp::function_symbol& tree_empty_function() { return g_empty; }
      34      898897 :     static const function_symbol& tree_node_function() { return g_tree_node; }
      35       18148 :     static const aterm_appl& empty_tree() { return g_empty_tree; }
      36             : 
      37       45896 :     static aterm_appl make_node(const term_balanced_tree& left_tree, const term_balanced_tree& right_tree)
      38             :     {
      39       45896 :       return down_cast<aterm_appl>(detail::g_term_pool().create_appl(tree_node_function(), left_tree, right_tree));
      40             :     }
      41             : 
      42             :     template < typename ForwardTraversalIterator, class Transformer >
      43      100057 :     aterm_appl make_tree(ForwardTraversalIterator& p, const std::size_t size, Transformer transformer )
      44             :     {
      45      100057 :       if (size>1)
      46             :       {
      47       45896 :         std::size_t left_size = (size + 1) >> 1; // size/2 rounded up.
      48       91792 :         const term_balanced_tree left_tree(make_tree(p, left_size, transformer));
      49       45896 :         std::size_t right_size = size >> 1; // size/2 rounded down.
      50       91792 :         const term_balanced_tree right_tree(make_tree(p, right_size, transformer));
      51       45896 :         return make_node(left_tree, right_tree);
      52             :       }
      53             : 
      54       54161 :       if (size==1)
      55             :       {
      56       51897 :         return down_cast<aterm_appl>(static_cast<const aterm&>(transformer(*(p++))));
      57             :       }
      58             : 
      59        2264 :       assert(size==0);
      60        2264 :       return empty_tree();
      61             :     }
      62             : 
      63             :     explicit term_balanced_tree(detail::_term_appl* t)
      64             :          : term_appl(static_cast<detail::_term_appl*>(t))
      65             :     {}
      66             : 
      67             :   public:
      68             : 
      69             :     /// The type of object, T stored in the term_balanced_tree.
      70             :     typedef Term value_type;
      71             :     
      72             :     /// Pointer to T.
      73             :     typedef Term* pointer;
      74             : 
      75             :     /// Reference to T.
      76             :     typedef Term& reference;
      77             : 
      78             :     /// Const reference to T.
      79             :     typedef const Term const_reference;
      80             : 
      81             :     /// An unsigned integral type.
      82             :     typedef std::size_t size_type;
      83             : 
      84             :     /// A signed integral type.
      85             :     typedef ptrdiff_t difference_type;
      86             : 
      87             :     /// \brief Default constructor. Creates an empty tree.
      88       15884 :     term_balanced_tree()
      89       15884 :       : aterm_appl(empty_tree())
      90       15884 :     {}
      91             : 
      92             :     /// \brief Copy constructor.
      93       28310 :     term_balanced_tree(const term_balanced_tree&) noexcept = default;
      94             : 
      95             :     /// \brief Move constructor.
      96        1554 :     term_balanced_tree(term_balanced_tree&&) noexcept = default;
      97             : 
      98             :     /// \brief Assignment operator.
      99             :     term_balanced_tree& operator=(const term_balanced_tree&) noexcept = default;
     100             : 
     101             :     /// \brief Move assign operator.
     102             :     term_balanced_tree& operator=(term_balanced_tree&&) noexcept = default;
     103             : 
     104             :     /// \brief Construction from aterm.
     105       91792 :     explicit term_balanced_tree(const aterm& tree) 
     106       91792 :        : aterm_appl(down_cast<aterm_appl>(tree))
     107             :     {
     108       91792 :     }
     109             : 
     110             :     /// \brief Creates an term_balanced_tree with a copy of a range.
     111             :     /// \param first The start of a range of elements.
     112             :     /// \param size The size of the range of elements.
     113             :     template<typename ForwardTraversalIterator>
     114        1788 :     term_balanced_tree(ForwardTraversalIterator first, const std::size_t size)
     115       16570 :       : aterm_appl(make_tree(first, size, [](const Term& t) { return t; }))
     116             :     {
     117        1788 :     }
     118             : 
     119             :     /// \brief Creates an term_balanced_tree with a copy of a range, where a transformer is applied to each term
     120             :     ///        before adding it to the tree..
     121             :     /// \param[in] first The start of a range of elements.
     122             :     /// \param[in] size The size of the range of elements.
     123             :     /// \param[in] transformer A class with an operator() that is applied to each term before adding it to the tree.
     124             :     template<typename ForwardTraversalIterator, typename Transformer>
     125        6477 :     term_balanced_tree(ForwardTraversalIterator first, const std::size_t size, Transformer transformer)
     126        6477 :       : aterm_appl(make_tree(first, size, transformer))
     127             :     {
     128        6477 :     }
     129             : 
     130             :     /// \brief Get the left branch of the tree
     131             :     /// \details It is assumed that the tree is a node with a left branch.
     132             :     /// \return A reference t the left subtree of the current tree
     133      212146 :     const term_balanced_tree<Term>& left_branch() const
     134             :     {
     135      212146 :       assert(is_node());
     136      212146 :       return down_cast<const term_balanced_tree<Term>>(aterm_appl::operator[](0));
     137             :     }
     138             : 
     139             :     /// \brief Get the left branch of the tree
     140             :     /// \details It is assumed that the tree is a node with a left branch.
     141             :     /// \return A reference t the left subtree of the current tree
     142      205464 :     const term_balanced_tree<Term>& right_branch() const
     143             :     {
     144      205464 :       assert(is_node());
     145      205464 :       return down_cast<const term_balanced_tree<Term>>(aterm_appl::operator[](1));
     146             :     }
     147             : 
     148             :     /// \brief Element indexing operator.
     149             :     /// \param position Index in the tree.
     150             :     /// \details This operation behaves linearly with respect to container size,
     151             :     ///          because it must calculate the size of the container. The operator
     152             :     ///          element_at behaves logarithmically.
     153         210 :     const Term& operator[](std::size_t position) const
     154             :     {
     155         210 :       return element_at(position, size());
     156             :     } 
     157             : 
     158             :     /// \brief Get an element at the indicated position.
     159             :     /// \param position The required position
     160             :     /// \param size The number of elements in the tree.
     161             :     ///                    This is required to make the complexity logarithmic.
     162             :     /// \details By providing the size this operation is logarithmic. If a wrong
     163             :     ///         size is provided the outcome is not determined. See also operator [].
     164             :     /// \return The element at the indicated position.
     165       26433 :     const Term& element_at(std::size_t position, std::size_t size) const
     166             :     {
     167       26433 :       assert(size == this->size());
     168       26433 :       assert(position < size);
     169             : 
     170       26433 :       if (size>1)
     171             :       {
     172       20720 :         std::size_t left_size = (size + 1) >> 1;
     173             : 
     174       41440 :         return (position < left_size) ?
     175       13701 :                left_branch().element_at(position, left_size) :
     176       27739 :                right_branch().element_at(position-left_size, size - left_size);
     177             :       }
     178             : 
     179        5713 :       return vertical_cast<Term>(static_cast<const aterm&>(*this));
     180             :     }
     181             : 
     182             :     /// \brief Returns the size of the term_balanced_tree.
     183             :     /// \details This operator is linear in the size of the balanced tree.
     184             :     /// \return The size of the tree.
     185      272398 :     size_type size() const
     186             :     {
     187      272398 :       if (is_node())
     188             :       {
     189      121347 :         return left_branch().size() + right_branch().size();
     190             :       }
     191      151051 :       return (empty()) ? 0 : 1;
     192             :     }
     193             : 
     194             :     /// \brief Returns true if tree is empty.
     195             :     /// \return True iff the tree is empty.
     196      160256 :     bool empty() const
     197             :     {
     198      160256 :       return m_term->function() == tree_empty_function();
     199             :     }
     200             : 
     201             :     /// \brief Returns true iff the tree is a node with a left and right subtree.
     202             :     /// \return True iff the tree is a node with a left and right subtree.
     203      690008 :     bool is_node() const
     204             :     {
     205      690008 :       return function() == tree_node_function();
     206             :     }
     207             : 
     208             :     class iterator: public boost::iterator_facade<
     209             :       iterator,                            // Derived
     210             :       const Term,                          // Value
     211             :       boost::forward_traversal_tag,        // CategoryOrTraversal
     212             :       const Term&                          // Reference
     213             :       >
     214             :     {
     215             :       private:
     216             :         using Tree = term_balanced_tree<Term>;
     217             :     
     218             :         friend class boost::iterator_core_access;
     219             :     
     220             :         static constexpr std::size_t maximal_size_of_stack = 20;      // We assume here that a tree never has more than 2^20 leaves, o
     221             :                                                            // equivalently that states consist of not more than 2^20 data_expressions.
     222             :         unprotected_aterm m_stack[maximal_size_of_stack];
     223             :         std::size_t m_top_of_stack;                             // First element in the stack that is empty.
     224             :     
     225             :         /// \brief Dereference operator
     226             :         /// \return The value that the iterator references
     227       85842 :         const Term& dereference() const
     228             :         {
     229       85842 :           assert(m_top_of_stack > 0);
     230       85842 :           return static_cast<const Term&>(m_stack[m_top_of_stack-1]);
     231             :         }
     232             :     
     233             :         /// \brief Equality operator
     234       66658 :         bool equal(const iterator& other) const
     235             :         {
     236       66658 :           if (m_top_of_stack != other.m_top_of_stack)
     237             :           {
     238       60538 :             return false; 
     239             :           }
     240             :           
     241        6131 :           for(std::size_t i = 0; i < m_top_of_stack; ++i)
     242             :           { 
     243          11 :             if (m_stack[i] != other.m_stack[i])
     244             :             {
     245           0 :               return false;
     246             :             }
     247             :           }
     248        6120 :           return true;
     249             :         }
     250             :     
     251             :         /// \brief Increments the iterator
     252       85840 :         void increment()
     253             :         {
     254       85840 :           --m_top_of_stack;
     255       85840 :           if (m_top_of_stack>0)
     256             :           {
     257       77004 :             unprotected_aterm current = m_stack[m_top_of_stack-1];
     258       77004 :             if (current.function() != Tree::tree_node_function())
     259             :             {
     260             :               // This subtree is empty.
     261       54173 :               return;
     262             :             }
     263             : 
     264       22831 :             --m_top_of_stack;
     265       22201 :             do
     266             :             {
     267       45032 :               m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
     268       45032 :               current = static_cast<Tree&>(current).left_branch();
     269             :             }
     270       45032 :             while (current.function() == Tree::tree_node_function());
     271             :     
     272       22831 :             m_stack[m_top_of_stack++] = current;
     273             :           }
     274             :         }
     275             :     
     276        9204 :         void initialise(const term_balanced_tree<Term>& tree)
     277             :         {
     278        9204 :           if (tree.empty())
     279             :           {
     280         313 :             return;
     281             :           }
     282             : 
     283        8891 :           unprotected_aterm current = tree;
     284             :     
     285       73023 :           while (current.function() == Tree::tree_node_function())
     286             :           {
     287       32066 :             assert(m_top_of_stack + 1 < maximal_size_of_stack);
     288       32066 :             m_stack[m_top_of_stack++] = static_cast<Tree&>(current).right_branch();
     289       32066 :             current = static_cast<Tree&>(current).left_branch();
     290             :           }
     291             : 
     292        8891 :           assert(m_top_of_stack + 1 < maximal_size_of_stack);
     293        8891 :           m_stack[m_top_of_stack++] = current;
     294             :         }
     295             :     
     296             :       public:
     297             :     
     298       59368 :         iterator()
     299       59368 :           : m_top_of_stack(0)
     300       59368 :         { }
     301             :     
     302        9204 :         iterator(const term_balanced_tree<Term>& tree)
     303        9204 :           : m_top_of_stack(0)
     304             :         {
     305        9204 :           initialise(tree);
     306        9204 :         } 
     307             :     
     308       14627 :         iterator(const iterator& other) 
     309       14627 :            : m_top_of_stack(other.m_top_of_stack)
     310             :         { 
     311       56911 :           for(std::size_t i = 0; i < m_top_of_stack; ++i)
     312             :           {
     313       42284 :             m_stack[i] = other.m_stack[i];
     314             :           }
     315       14627 :         }
     316             :     
     317             :     };
     318             : 
     319             :     /// \brief Returns an iterator pointing to the beginning of the term_balanced_tree.
     320             :     /// \return The beginning of the list.
     321        9204 :     iterator begin() const
     322             :     {
     323        9204 :       return iterator(*this);
     324             :     }
     325             : 
     326             :     /// \brief Returns an iterator pointing to the end of the term_balanced_tree.
     327             :     /// \return The end of the list.
     328       59368 :     iterator end() const
     329             :     {
     330       59368 :       return iterator();
     331             :     }
     332             : 
     333             : };
     334             : 
     335             : /// \brief A term_balanced_tree with elements of type aterm.
     336             : typedef term_balanced_tree<aterm> aterm_balanced_tree;
     337             : 
     338             : template <class Term>
     339           3 : std::string pp(const term_balanced_tree<Term> t)
     340             : {
     341           6 :   std::stringstream ss;
     342          26 :   for(typename term_balanced_tree<Term>::iterator i = t.begin(); i != t.end(); ++i)
     343             :   {
     344          23 :     if (i!=t.begin()) 
     345             :     {
     346          20 :       ss << ", ";
     347             :     }
     348          23 :     ss << pp(*i);
     349             :   }
     350           6 :   return ss.str();
     351             : }
     352             : } // namespace atermpp
     353             : 
     354             : namespace std
     355             : {
     356             : /// \brief Swaps two balanced trees.
     357             : /// \details This operation is more efficient than exchanging terms by an assignment,
     358             : ///          as swapping does not require to change the protection of terms.
     359             : /// \param t1 The first term
     360             : /// \param t2 The second term
     361             : template <class T>
     362             : inline void swap(atermpp::term_balanced_tree<T>& t1, atermpp::term_balanced_tree<T>& t2)
     363             : {
     364             :   t1.swap(t2);
     365             : }
     366             : 
     367             : /// \brief Standard hash function.
     368             : template<class T>
     369             : struct hash<atermpp::term_balanced_tree<T> >
     370             : {
     371       10887 :   std::size_t operator()(const atermpp::term_balanced_tree<T>& t) const
     372             :   {
     373       10887 :     return std::hash<atermpp::aterm>()(t);
     374             :   }
     375             : };
     376             : } // namespace std
     377             : 
     378             : 
     379             : #endif // MCRL2_ATERMPP_ATERM_BALANCED_TREE_H

Generated by: LCOV version 1.13