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

Generated by: LCOV version 1.13