LCOV - code coverage report
Current view: top level - lts/include/mcrl2/lts/detail - embedded_list.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 93 95 97.9 %
Date: 2020-07-11 00:44:39 Functions: 89 89 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Author(s): 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             : /// \file lts/detail/embedded_list.h
      10             : 
      11             : #ifndef _EMBEDDED_LIST_H
      12             : #define _EMBEDDED_LIST_H
      13             : 
      14             : #include <cassert>
      15             : #include <vector>
      16             : 
      17             : namespace mcrl2
      18             : {
      19             : namespace lts
      20             : {
      21             : namespace detail
      22             : {
      23             : 
      24             : // The list type below embeds a list in existing data structures. 
      25             : // For instance if elements are stored in a vector, and should also
      26             : // be linked in a particular order in a list this data structure can be 
      27             : // used.
      28             : //
      29             : // For this purpose to each data structure that must be put in an embedded
      30             : // list the embedded_list_node must be added to the data structure. 
      31             : //
      32             : // From that point on the embedded_list data type can be used to construct
      33             : // an embedded list. The data structure, once created will not require
      34             : // extra memory. 
      35             : 
      36             : // prototype.
      37             : template < class TYPE > class embedded_list;
      38             : 
      39             : template <class TYPE>
      40             : class embedded_list_node
      41             : {
      42             :  
      43             :   template < class T > friend class embedded_list;
      44             : 
      45             :   protected:
      46             :      TYPE* m_next;  // Points to the next element in the list. The nullptr if it does not exist.
      47             :      TYPE* m_prev;  // Points to the current element in the list. The nullptr if it does not exist.
      48             : };
      49             : 
      50             : 
      51             : template < class TYPE >
      52             : class embedded_list
      53             : {
      54             :   protected:
      55             :     TYPE* m_first;   // Points to the last element of the list. nulllptr if not valid.
      56             :     TYPE* m_last;    // Points to the first element of the list
      57             :     std::size_t m_size;   // The number of elements in the list.
      58             : 
      59             :   protected:
      60             : 
      61        4753 :     bool check_this_embedded_list() const
      62             :     {
      63        4753 :       std::size_t count_up=0;
      64      173539 :       for(TYPE* walker=m_first; walker!=nullptr && count_up<=m_size ; walker=walker->m_next)
      65             :       {
      66      168786 :         count_up++;
      67             :       }
      68             : 
      69        4753 :       std::size_t count_down=0;
      70      173539 :       for(TYPE* walker=m_last; walker!=nullptr && count_down<=m_size ; walker=walker->m_prev)
      71             :       {
      72      168786 :         count_down++;
      73             :       }
      74             : 
      75        4753 :       return m_size==count_up && m_size==count_down;
      76             :     }
      77             : 
      78        1463 :     bool check_presence(const TYPE& e) const
      79             :     {
      80       30691 :       for(TYPE* walker=m_first; walker!=nullptr; walker=walker->m_next)
      81             :       {
      82       30691 :         if (walker==&e)
      83             :         {
      84        1463 :           return true;
      85             :         }
      86             :       }
      87           0 :       return false;
      88             :     }
      89             : 
      90             : 
      91             : 
      92             :   public:
      93             :     
      94             :     // Constructor.
      95         564 :     embedded_list()
      96         564 :       : m_first(nullptr), m_last(nullptr), m_size(0)
      97         564 :     {}
      98             : 
      99             :     // Copy constructor.
     100             :     embedded_list(const embedded_list& other) = default;
     101             : 
     102             :     // get the size
     103        2764 :     std::size_t size() const
     104             :     {
     105        2764 :       return m_size;
     106             :     }
     107             : 
     108             :     // Get the first element of the list.
     109          90 :     TYPE& front() 
     110             :     {
     111          90 :       assert(m_size>0);
     112          90 :       return *m_first;
     113             :     }
     114             : 
     115             :     // Get the last element of the list.
     116          30 :     TYPE& back() 
     117             :     {
     118          30 :       assert(m_size>0);
     119          30 :       return *m_last;
     120             :     }
     121             : 
     122             :     // Insert an element at the end of the list. Note that the element e is changed.
     123        2507 :     void push_back(TYPE& e)
     124             :     {
     125        2507 :       if (m_first==nullptr)
     126             :       {
     127         319 :         assert(m_last==nullptr && m_size==0);
     128         319 :         m_first= &e;
     129         319 :         e.m_prev= nullptr;
     130             :       }
     131             :       else 
     132             :       {
     133        2188 :         assert(m_last!=nullptr && m_size>0);
     134        2188 :         e.m_prev=m_last;
     135        2188 :         m_last->m_next=&e;
     136             :       }
     137        2507 :       e.m_next=nullptr;
     138        2507 :       m_last= &e;
     139        2507 :       m_size++;
     140        2507 :       assert(check_this_embedded_list());
     141        2507 :     }
     142             : 
     143             :     // Insert an element at the begining of the list. Note that the element e is changed.
     144             :     void push_front(TYPE& e)
     145             :     {
     146             :       if (m_last==nullptr)
     147             :       {
     148             :         assert(m_first==nullptr && m_size==0);
     149             :         m_last= &e;
     150             :         e.m_next= nullptr;
     151             :       }
     152             :       else 
     153             :       {
     154             :         assert(m_first!=nullptr && m_size>0);
     155             :         e.m_next=m_first;
     156             :         m_first->m_prev=&e;
     157             :       }
     158             :       e.m_prev=nullptr;
     159             :       m_first= &e;
     160             :       m_size++;
     161             :       assert(check_this_embedded_list());
     162             :     }
     163             : 
     164             :     // Erase this element from the list. The list is adapted such that it does not contain
     165             :     // element e anymore. Postcondition: The previous and next pointer in e are invalid. 
     166        1463 :     void erase(TYPE& e)
     167             :     {
     168        1463 :       assert(check_presence(e));
     169        1463 :       if (e.m_next==nullptr)
     170             :       {
     171         173 :         assert(&e==m_last);
     172         173 :         m_last=e.m_prev;
     173             :       }
     174             :       else
     175             :       {
     176        1290 :         assert(e.m_next->m_prev!=nullptr);
     177        1290 :         e.m_next->m_prev = e.m_prev;
     178             :       }
     179             : 
     180        1463 :       if (e.m_prev==nullptr)
     181             :       {
     182         676 :         assert(&e==m_first);
     183         676 :         m_first=e.m_next;
     184             :       }
     185             :       else
     186             :       {
     187         787 :         assert(e.m_prev->m_next!=nullptr);
     188         787 :         e.m_prev->m_next = e.m_next;
     189             :       }
     190             : 
     191        1463 :       e.m_next= nullptr;
     192        1463 :       e.m_prev= nullptr;
     193             : 
     194        1463 :       m_size--;
     195             : 
     196        1463 :       assert(check_this_embedded_list());
     197        1463 :     }
     198             : 
     199         271 :     void clear() 
     200             :     {
     201         271 :       m_first=nullptr;
     202         271 :       m_last=nullptr;
     203         271 :       m_size=0;
     204         271 :     }
     205             : 
     206             :     /* Append the list l to the current list.  
     207             :        After this operation the list l is replaced by the empty list
     208             :        to prevent unwanted sharing of lists.  */
     209             :        
     210          44 :     void append(embedded_list& l)
     211             :     {
     212          44 :       if (l.size()==0)
     213             :       {
     214           0 :         return;
     215             :       }
     216             : 
     217          44 :       if (m_size==0)
     218             :       {
     219          31 :         *this=l;
     220             :       }
     221             :       else
     222             :       {
     223          13 :         m_last->m_next=l.m_first;
     224          13 :         l.m_first->m_prev=m_last;
     225          13 :         m_last=l.m_last;
     226          13 :         m_size=m_size+l.m_size;
     227             :       }
     228             :       // Explicitly invalidate l.
     229          44 :       l.m_first=nullptr;
     230          44 :       l.m_last=nullptr;
     231          44 :       l.m_size=0;
     232             :       
     233          44 :       assert(check_this_embedded_list());
     234             :     }
     235             : 
     236             :     class iterator 
     237             :     {
     238             :       protected:
     239             :         TYPE* m_ptr;
     240             : 
     241             :       public:
     242             :         
     243        2009 :         iterator(TYPE* p)
     244        2009 :          : m_ptr(p)
     245        2009 :         {}
     246             : 
     247             :         // Prefix increment
     248        2606 :         iterator operator++() 
     249             :         {
     250        2606 :           iterator old=*this;
     251        2606 :           m_ptr=m_ptr->m_next;
     252        2606 :           return old;
     253             :         }
     254             :         
     255             :         // Postfix increment
     256        1017 :         iterator operator++(int) 
     257             :         {
     258        1017 :           m_ptr=m_ptr->m_next;
     259        1017 :           return *this;
     260             :         }
     261             : 
     262             :         // Dereference of the iterator. 
     263        3623 :         TYPE& operator*() 
     264             :         {
     265        3623 :           return *m_ptr;
     266             :         }
     267             : 
     268             :         // Dereference of the iterator. 
     269         600 :         TYPE* operator->() 
     270             :         {
     271         600 :           return m_ptr;
     272             :         }
     273             : 
     274             :        // Equality operator on iterators.
     275        4470 :        bool operator ==(const iterator& other) const
     276             :        {
     277        4470 :          return m_ptr==other.m_ptr;
     278             :        }
     279             :        // Inequality operator on iterators.
     280        4470 :        bool operator !=(const iterator& other) const
     281             :        {
     282        4470 :          return !(*this==other);
     283             :        }
     284             :         
     285             :     };
     286             : 
     287         739 :     iterator begin() const
     288             :     {
     289         739 :       assert(check_this_embedded_list());
     290         739 :       return m_first;
     291             :     }
     292             : 
     293        1270 :     iterator end() const
     294             :     {
     295        1270 :       return nullptr;
     296             :     }
     297             :     
     298             : };
     299             : 
     300             : } // end namespace detail
     301             : } // end namespace lts
     302             : } // end namespace mcrl2
     303             : #endif //_EMBEDDED_LIST_H

Generated by: LCOV version 1.13