LCOV - code coverage report
Current view: top level - atermpp/include/mcrl2/atermpp - aterm_list.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 67 67 100.0 %
Date: 2020-09-16 00:45:56 Functions: 535 702 76.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Author(s): Wieger Wesselink, Jan Friso Groote
       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_LIST_H
      11             : #define MCRL2_ATERMPP_ATERM_LIST_H
      12             : 
      13             : #include "mcrl2/atermpp/detail/aterm_list.h"
      14             : #include "mcrl2/atermpp/detail/aterm_list_iterator.h"
      15             : #include "mcrl2/atermpp/type_traits.h"
      16             : 
      17             : namespace atermpp
      18             : {
      19             : 
      20             : /// \brief A list of aterm objects.
      21             : template <typename Term>
      22   185424145 : class term_list: public aterm
      23             : {
      24             : protected:
      25             :   /// \brief Constructor for term lists from internally constructed terms delivered as reference.
      26             :   explicit term_list(detail::_aterm* t) noexcept :aterm(t)
      27             :   {
      28             :     assert(!defined() || type_is_list());
      29             :   }
      30             : 
      31             : public:
      32             :   /// The type of object, T stored in the term_list.
      33             :   typedef Term value_type;
      34             : 
      35             :   /// Pointer to T.
      36             :   typedef Term* pointer;
      37             : 
      38             :   /// Reference to T.
      39             :   typedef Term& reference;
      40             : 
      41             :   /// Const reference to T.
      42             :   typedef const Term& const_reference;
      43             : 
      44             :   /// An unsigned integral type.
      45             :   typedef std::size_t size_type;
      46             : 
      47             :   /// A signed integral type.
      48             :   typedef ptrdiff_t difference_type;
      49             : 
      50             :   /// Iterator used to iterate through an term_list.
      51             :   typedef term_list_iterator<Term> iterator;
      52             : 
      53             :   /// Const iterator used to iterate through an term_list.
      54             :   typedef term_list_iterator<Term> const_iterator;
      55             : 
      56             :   /// \brief Default constructor. Creates an empty list.
      57    47493887 :   term_list() noexcept
      58    47493887 :     : aterm(detail::g_term_pool().empty_list())
      59    47493887 :   {}
      60             : 
      61             :   /// \brief Copy constructor.
      62             :   /// \param t A list.
      63    12393404 :   term_list(const term_list<Term>& t) noexcept
      64    12393404 :     : aterm(t)
      65             :   {
      66    12393404 :     assert(!defined() || type_is_list());
      67    12393404 :   }
      68             : 
      69             :   /// \brief Move constructor.
      70             :   /// \param t A list.
      71     2681395 :   term_list(term_list<Term>&& t) noexcept
      72     2681395 :     : aterm(std::move(t))
      73             :   {
      74     2681395 :     assert(!defined() || type_is_list());
      75     2681395 :   }
      76             : 
      77             :   /// This class has user-declared copy constructor so declare copy and move assignment.
      78             :   term_list& operator=(const term_list& other) noexcept = default;
      79             :   term_list& operator=(term_list&& other) noexcept = default;
      80             : 
      81             :   /// \brief Creates a term_list with the elements from first to last.
      82             :   /// \details It is assumed that the range can be traversed from last to first.
      83             :   /// \param first The start of a range of elements.
      84             :   /// \param last The end of a range of elements.
      85             :   template <class Iter>
      86    22293191 :   explicit term_list(Iter first, Iter last, typename std::enable_if<std::is_base_of<
      87             :                 std::bidirectional_iterator_tag,
      88             :                 typename std::iterator_traits<Iter>::iterator_category
      89             :             >::value>::type* = nullptr) :
      90             :       aterm(detail::make_list_backward<Term,Iter,
      91    22293191 :                 detail::do_not_convert_term<Term> >(first, last,detail::do_not_convert_term<Term>()))
      92             :   {
      93    22293191 :     assert(!defined() || type_is_list());
      94    22293191 :   }
      95             : 
      96             :   /// \brief Creates a term_list with the elements from first to last converting the elements before inserting.
      97             :   /// \details It is assumed that the range can be traversed from last to first. The operator () in the class
      98             :   ///          ATermConverter is applied to each element before inserting it in the list.
      99             :   /// \param first The start of a range of elements.
     100             :   /// \param last The end of a range of elements.
     101             :   /// \param convert_to_aterm A class with a () operation, which is applied to each element
     102             :   ///                   before it is put into the list.
     103             :   template <class Iter, class ATermConverter>
     104          40 :   explicit term_list(Iter first, Iter last, const ATermConverter& convert_to_aterm,
     105             :             typename std::enable_if<std::is_base_of<
     106             :               std::bidirectional_iterator_tag,
     107             :               typename std::iterator_traits<Iter>::iterator_category
     108             :             >::value>::type* = 0):
     109          40 :        aterm(detail::make_list_backward<Term,Iter,ATermConverter>(first, last, convert_to_aterm))
     110             :   {
     111          40 :     assert(!defined() || type_is_list());
     112          40 :   }
     113             : 
     114             :   /// \brief Creates a term_list with the elements from first to last, converting and filtering the list.
     115             :   /// \details It is assumed that the range can be traversed from last to first. The operator () in the class
     116             :   ///          ATermConverter is applied to each element before inserting it in the list. Elements are only
     117             :   ///          inserted if the operator () of the class ATermFilter yields true when applied to such an element.
     118             :   /// \param first The start of a range of elements.
     119             :   /// \param last The end of a range of elements.
     120             :   /// \param convert_to_aterm A class with a () operation, which is applied to each element
     121             :   ///                   before it is put into the list.
     122             :   /// \param aterm_filter A class with an operator () that is used to determine whether elements can be inserted in the list.
     123             :   template <class Iter, class ATermConverter, class ATermFilter>
     124           1 :   explicit term_list(Iter first, Iter last, const ATermConverter& convert_to_aterm, const ATermFilter& aterm_filter,
     125             :             typename std::enable_if<std::is_base_of<
     126             :               std::bidirectional_iterator_tag,
     127             :               typename std::iterator_traits<Iter>::iterator_category
     128             :             >::value>::type* = 0):
     129           1 :        aterm(detail::make_list_backward<Term,Iter,ATermConverter,ATermFilter>(first, last, convert_to_aterm, aterm_filter))
     130             :   {
     131           1 :     assert(!defined() || type_is_list());
     132           1 :   }
     133             : 
     134             :   /// \brief Creates a term_list from the elements from first to last.
     135             :   /// \details The range is traversed from first to last. This requires
     136             :   ///           to copy the elements internally, which is less efficient
     137             :   ///           than this function with random access iterators as arguments.
     138             :   /// \param first The start of a range of elements.
     139             :   /// \param last The end of a range of elements.
     140             :   template <class Iter>
     141     1806132 :   explicit term_list(Iter first, Iter last,
     142             :                      typename std::enable_if< !std::is_base_of<
     143             :                        std::bidirectional_iterator_tag,
     144             :                        typename std::iterator_traits<Iter>::iterator_category
     145             :                      >::value>::type* = nullptr):
     146             :        aterm(detail::make_list_forward<Term,Iter,detail::do_not_convert_term<Term> >
     147     1806132 :                                (first, last, detail::do_not_convert_term<Term>()))
     148             :   {
     149     1806132 :     assert(!defined() || type_is_list());
     150     1806132 :   }
     151             : 
     152             :   /// \brief Creates a term_list from the elements from first to last converting the elements before inserting.
     153             :   /// \details The range is traversed from first to last. This requires
     154             :   ///           to copy the elements internally, which is less efficient
     155             :   ///           than this function with random access iterators as arguments.
     156             :   ///           The operator () in the class
     157             :   ///           ATermConverter is applied to each element before inserting it in the list.
     158             :   /// \param first The start of a range of elements.
     159             :   /// \param last The end of a range of elements.
     160             :   /// \param convert_to_aterm A class with a () operation, whic is applied to each element
     161             :   ///                      before it is put into the list.
     162             :   template <class Iter, class  ATermConverter>
     163     2241984 :   explicit term_list(Iter first, Iter last, const ATermConverter& convert_to_aterm,
     164             :                      typename std::enable_if< !std::is_base_of<
     165             :                        std::random_access_iterator_tag,
     166             :                        typename std::iterator_traits<Iter>::iterator_category
     167             :                      >::value>::type* = nullptr):
     168             :        aterm(detail::make_list_forward<Term,Iter,ATermConverter>
     169     2241984 :                                (first, last, convert_to_aterm))
     170             :   {
     171     2241984 :     assert(!defined() || type_is_list());
     172     2241984 :   }
     173             : 
     174             :   /// \brief Creates a term_list from the elements from first to last converting and filtering the elements before inserting.
     175             :   /// \details The range is traversed from first to last. This requires
     176             :   ///           to copy the elements internally, which is less efficient
     177             :   ///           than this function with random access iterators as arguments.
     178             :   ///           The operator () in the class ATermConverter is applied to
     179             :   ///           each element before inserting it in the list. Elements are only
     180             :   ///           inserted if the operator () of the class ATermFilter yields true when applied to such an element.
     181             :   /// \param first The start of a range of elements.
     182             :   /// \param last The end of a range of elements.
     183             :   /// \param convert_to_aterm A class with a () operation, whic is applied to each element
     184             :   ///                      before it is put into the list.
     185             :   /// \param aterm_filter A class with an operator () that is used to determine whether elements can be inserted in the list.
     186             :   template <class Iter, class  ATermConverter, class ATermFilter>
     187           1 :   explicit term_list(Iter first, Iter last, const ATermConverter& convert_to_aterm, const ATermFilter& aterm_filter,
     188             :                      typename std::enable_if< !std::is_base_of<
     189             :                        std::random_access_iterator_tag,
     190             :                        typename std::iterator_traits<Iter>::iterator_category
     191             :                      >::value>::type* = nullptr):
     192             :        aterm(detail::make_list_forward<Term,Iter,ATermConverter>
     193           1 :                                (first, last, convert_to_aterm, aterm_filter))
     194             :   {
     195           1 :     assert(!defined() || type_is_list());
     196           1 :   }
     197             : 
     198             :   /// \brief A constructor based on an initializer list.
     199             :   /// \details This constructor is not made explicit to conform to initializer lists in standard containers.
     200             :   /// \param init The initialiser list.
     201    13006257 :   term_list(std::initializer_list<Term> init)
     202             :     : aterm(detail::make_list_backward<Term,
     203             :                                        typename std::initializer_list<Term>::const_iterator,
     204             :                                        detail::do_not_convert_term<Term> >
     205    13006257 :                 (init.begin(), init.end(), detail::do_not_convert_term<Term>()))
     206             :   {
     207    13006257 :     assert(!defined() || type_is_list());
     208    13006257 :   }
     209             : 
     210             :   /// \brief Returns the tail of the list.
     211             :   /// \return The tail of the list.
     212     1746418 :   const term_list<Term>& tail() const
     213             :   {
     214     1746418 :     assert(!empty());
     215     1746418 :     return (static_cast<const detail::_aterm_list<Term>&>(*m_term)).tail();
     216             :   }
     217             : 
     218             :   /// \brief Removes the first element of the list.
     219      570650 :   void pop_front()
     220             :   {
     221      570650 :     *this = tail();
     222      570650 :   }
     223             : 
     224             :   /// \brief Returns the first element of the list.
     225             :   /// \return The term at the head of the list.
     226     2504848 :   const Term& front() const
     227             :   {
     228     2504848 :     return static_cast<const detail::_aterm_list<Term>&>(*m_term).head();
     229             :   }
     230             : 
     231             :   /// \brief Inserts a new element at the beginning of the current list.
     232             :   /// \param el The term that is added.
     233             :   void push_front(const Term& el);
     234             : 
     235             :   /// \brief Construct and insert a new element at the beginning of the current list.
     236             :   /// \param el The term that is added.
     237             :   template<typename ...Args>
     238             :   void emplace_front(Args&&... arguments);
     239             : 
     240             :   /// \brief Returns the size of the term_list.
     241             :   /// \details The complexity of this function is linear in the size of the list.
     242             :   /// \return The size of the list.
     243   161662339 :   size_type size() const
     244             :   {
     245   161662339 :     std::size_t size=0;
     246   432976171 :     for(const_iterator i=begin(); i!=end(); ++i)
     247             :     {
     248   271313832 :       ++size;
     249             :     }
     250   161662339 :     return size;
     251             :   }
     252             : 
     253             :   /// \brief Returns true if the list's size is 0.
     254             :   /// \return True iff the list is empty.
     255     9086034 :   bool empty() const
     256             :   {
     257     9086034 :     return m_term->function() == detail::g_term_pool().as_empty_list();
     258             :   }
     259             : 
     260             :   /// \brief Returns a const_iterator pointing to the beginning of the term_list.
     261             :   /// \return The beginning of the list.
     262   343235308 :   const_iterator begin() const
     263             :   {
     264   343235308 :     return const_iterator(m_term);
     265             :   }
     266             : 
     267             :   /// \brief Returns a const_iterator pointing to the end of the term_list.
     268             :   /// \return The end of the list.
     269   627103862 :   const_iterator end() const
     270             :   {
     271   627103862 :     return const_iterator(detail::address(detail::g_term_pool().empty_list()));
     272             :   }
     273             : 
     274             :   /// \brief Returns the largest possible size of the term_list.
     275             :   /// \return The largest possible size of the list.
     276             :   size_type max_size() const
     277             :   {
     278             :     return std::numeric_limits<std::size_t>::max();
     279             :   }
     280             : };
     281             : 
     282             : /// \cond INTERNAL_DOCS
     283             : namespace detail
     284             : {
     285             : 
     286             : /// \brief Template specialization to make a term_list recognizable as a container type (see
     287             : ///        type_traits.h and detail/type_traits_impl.h).
     288             : template < typename T >
     289             : struct is_container_impl< atermpp::term_list< T > > : public std::true_type
     290             : { };
     291             : 
     292             : 
     293             : template <class Term>
     294             : class _aterm_list : public _aterm_appl<2>
     295             : {
     296             : public:
     297             :   /// \returns A reference to the head of the list.
     298   313292577 :   const Term& head() const { return static_cast<const Term&>(arg(0)); }
     299             : 
     300             :   /// \returns A reference to the tail of the list.
     301   586756401 :   const term_list<Term>& tail() const { return static_cast<const term_list<Term>&>(arg(1)); }
     302             : };
     303             : 
     304             : } // namespace detail
     305             : /// \endcond
     306             : 
     307             : 
     308             : /// \brief A term_list with elements of type aterm.
     309             : typedef term_list<aterm> aterm_list;
     310             : 
     311             : 
     312             : /// \brief Returns the list with the elements in reversed order.
     313             : /// \param l A list.
     314             : /// \details This operator is linear in the size of the list.
     315             : /// \return The reversed list.
     316             : template <typename Term>
     317             : inline
     318             : term_list<Term> reverse(const term_list<Term>& l);
     319             : 
     320             : /// \brief Returns the list with the elements sorted according to the <-operator on the addresses of terms. 
     321             : /// \param l A list.
     322             : /// \param ordering An total orderings relation on Term, by default the ordering relation on Terms. 
     323             : /// \details This operator has complexity nlog n where n is the size of the list.
     324             : /// \return The sorted list.
     325             : template <typename Term>
     326             : inline
     327             : term_list<Term> sort_list(const term_list<Term>& l, 
     328             :                           const std::function<bool(const Term&, const Term&)>& ordering 
     329          18 :                                       = [](const Term& t1, const Term& t2){ return t1<t2;});
     330             : 
     331             : 
     332             : /// \brief Returns the concatenation of two lists with convertible element types.
     333             : ///  \details The type of the result is either the type of l, if the elements of m
     334             : ///           can be converted implicitly to the type of the elements of l. Otherwise if the
     335             : ///           elements of l can be converted implicitly to the type of the elements
     336             : ///           of m, the result type is that or m.
     337             : /// \param l A list.
     338             : /// \param m A list.
     339             : /// \details The complexity of this operator is linear in the length of l.
     340             : /// \return The concatenation of the lists l followed by m.
     341             : 
     342             : template <typename Term1, typename Term2>
     343             : inline
     344             : typename std::conditional<std::is_convertible<Term2,Term1>::value,term_list<Term1>,term_list<Term2>>::type
     345             : operator+(const term_list<Term1>& l, const term_list<Term2>& m);
     346             : 
     347             : 
     348             : /// \brief Appends a new element at the end of the list. Note
     349             : ///        that the complexity of this function is O(n), with n the number of
     350             : ///        elements in the list!!!
     351             : /// \param l The list to which the term is appended.
     352             : /// \param el A term.
     353             : /// \return The list l with elem appended at the end.
     354             : template <typename Term>
     355             : inline
     356             : term_list<Term> push_back(const term_list<Term>& l, const Term& el);
     357             : 
     358             : } // namespace atermpp
     359             : 
     360             : 
     361             : namespace std
     362             : {
     363             : //
     364             : /// \brief Swaps two term_lists.
     365             : /// \details This operation is more efficient than exchanging terms by an assignment,
     366             : ///          as swapping does not require to change the protection of terms.
     367             : /// \param t1 The first term
     368             : /// \param t2 The second term
     369             : template <class T>
     370        1016 : inline void swap(atermpp::term_list<T>& t1, atermpp::term_list<T>& t2) noexcept
     371             : {
     372        1016 :   t1.swap(t2);
     373        1016 : }
     374             : 
     375             : /// \brief The standard hash class.
     376             : template <class Term>
     377             : struct hash<atermpp::term_list<Term> >
     378             : {
     379             :   /// \brief A specialization of the standard std::hash function.
     380             :   /// \param l The list for which a hash value is calculated.
     381             :   /// \return A hash value for l.
     382       40482 :   std::size_t operator()(const atermpp::term_list<Term>& l) const
     383             :   {
     384             :     std::hash<atermpp::aterm> hasher;
     385       40482 :     return hasher(l);
     386             :   }
     387             : };
     388             : 
     389             : } // namespace std
     390             : 
     391             : #include "mcrl2/atermpp/detail/aterm_list_implementation.h"
     392             : 
     393             : #endif // MCRL2_ATERMPP_ATERM_LIST_H

Generated by: LCOV version 1.13