LCOV - code coverage report
Current view: top level - pg/include/mcrl2/pg - DenseSet.h (source / functions) Hit Total Coverage
Test: mcrl2_coverage.info.cleaned Lines: 0 48 0.0 %
Date: 2024-03-08 02:52:28 Functions: 0 17 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Copyright (c) 2009-2013 University of Twente
       2             : // Copyright (c) 2009-2013 Michael Weber <michaelw@cs.utwente.nl>
       3             : // Copyright (c) 2009-2013 Maks Verver <maksverver@geocities.com>
       4             : // Copyright (c) 2009-2013 Eindhoven University of Technology
       5             : //
       6             : // Distributed under the Boost Software License, Version 1.0.
       7             : // (See accompanying file LICENSE_1_0.txt or copy at
       8             : // http://www.boost.org/LICENSE_1_0.txt)
       9             : 
      10             : #ifndef MCRL2_PG_DENSE_SET_H
      11             : #define MCRL2_PG_DENSE_SET_H
      12             : 
      13             : #include <cstddef>
      14             : #include <cstdlib>
      15             : #include <memory>
      16             : #include <utility>
      17             : 
      18             : /*! \defgroup Containers
      19             : 
      20             :     Custom container data structures.
      21             : */
      22             : 
      23             : /*! \ingroup Containers
      24             : 
      25             :     A set-like data structure that stores values from a dense integer range.
      26             : 
      27             :     Each set instance has a fixed range of possible values; elements stored are
      28             :     integers that must lie within this range.  Memory used and time required to
      29             :     iterate over the set is proportional to the size of the range (*not* the 
      30             :     size of the set, i.e. the number of elements).
      31             : 
      32             :     Internally, the DenseSet uses an array of bools to note the presence/absence
      33             :     of elements, which typically requires one byte per value in range.
      34             : 
      35             :     \see DenseMap
      36             : */
      37             : 
      38             : // N.B. this class is far from finished!
      39             : 
      40             : template< class Key, class Alloc = std::allocator<bool> >
      41             : class DenseSet
      42             : {
      43             : public:
      44             :     class Iterator
      45             :     {
      46             :         const DenseSet *set_;
      47             :         Key key_;
      48             : 
      49             :     public:
      50             :         typedef ptrdiff_t                  difference_type;
      51             :         typedef std::forward_iterator_tag  iterator_category;
      52             :         typedef Key                        value_type;
      53             :         typedef Key*                       pointer;
      54             :         typedef Key&                       reference;
      55             : 
      56           0 :         Iterator(const DenseSet *set, Key key) : set_(set), key_(key) { }
      57           0 :         Iterator(const Iterator &it) : set_(it.set_), key_(it.key_) { }
      58             : 
      59           0 :         Iterator& operator=(const Iterator &it)
      60             :         {
      61           0 :             set_ = it.set_;
      62           0 :             key_ = it.key_;
      63           0 :             return *this;
      64             :         }
      65             : 
      66             :         bool operator== (const Iterator &other) const { return key_ == other.key_; }
      67           0 :         bool operator!= (const Iterator &other) const { return key_ != other.key_; }
      68             :         bool operator<  (const Iterator &other) const { return key_ <  other.key_; }
      69             :         bool operator>  (const Iterator &other) const { return key_ >  other.key_; }
      70             :         bool operator<= (const Iterator &other) const { return key_ <= other.key_; }
      71             :         bool operator>= (const Iterator &other) const { return key_ >= other.key_; }
      72             : 
      73           0 :         value_type operator*() { return key_; }
      74             : 
      75           0 :         Iterator& operator++()
      76             :         {
      77           0 :             do ++key_; while (!set_->used_[key_]);
      78           0 :             return *this;
      79             :         }
      80             : 
      81             :         Iterator& operator++(int)
      82             :         {
      83             :             Iterator copy = *this;
      84             :             ++*this;
      85             :             return copy;
      86             :         }
      87             :     };
      88             : 
      89             :     typedef std::size_t size_type;
      90             :     typedef Key value_type;
      91             :     typedef Iterator iterator;
      92             :     typedef Iterator const_iterator;
      93             : 
      94           0 :     DenseSet(Key begin, Key end, const Alloc &alloc = Alloc())
      95           0 :         : range_begin(begin), range_end(end < begin ? begin : end),
      96           0 :           range_size_(range_end - range_begin), alloc_(alloc),
      97           0 :           used_(alloc_.allocate(range_size_ + 1)), num_used_(0)
      98             :     {
      99           0 :         for (size_type i = 0; i < range_size_; ++i) used_[i] = false;
     100           0 :         used_[range_size_] = true;  // marks end of data
     101           0 :     }
     102             : 
     103           0 :     ~DenseSet()
     104             :     {
     105           0 :         alloc_.deallocate(used_, range_size_ + 1);
     106           0 :     }
     107             : 
     108           0 :     size_type size() const
     109             :     {
     110           0 :         return num_used_;
     111             :     }
     112             : 
     113           0 :     bool empty() const
     114             :     {
     115           0 :         return num_used_ == 0;
     116             :     }
     117             : 
     118             :     void clear()
     119             :     {
     120             :         if (num_used_ > 0)
     121             :         {
     122             :             for (size_type i = 0; i < range_size_; ++i) used_[i] = false;
     123             :             num_used_ = 0;
     124             :         }
     125             :     }
     126             : 
     127           0 :     iterator begin()
     128             :     {
     129           0 :         Key k = range_begin;
     130           0 :         while (!used_[k - range_begin]) ++k;
     131           0 :         return iterator(this, k);
     132             :     }
     133             : 
     134           0 :     iterator end()
     135             :     {
     136           0 :         return iterator(this, range_size_);
     137             :     }
     138             : 
     139           0 :     const_iterator begin() const
     140             :     {
     141           0 :         return iterator(const_cast<DenseSet*>(this)->begin());  // HACK
     142             :     }
     143             : 
     144           0 :     const_iterator end() const
     145             :     {
     146           0 :         return iterator(const_cast<DenseSet*>(this)->end());  // HACK
     147             :     }
     148             : 
     149           0 :     iterator find(const Key &k)
     150             :     {
     151           0 :         if ( /* k >= range_begin && k < range_end && */ used_[k - range_begin] )
     152             :         {
     153           0 :             return iterator(this, k);
     154             :         }
     155             :         else
     156             :         {
     157           0 :             return end();
     158             :         }
     159             :     }
     160             : 
     161             :     const_iterator find(const Key &k) const
     162             :     {
     163             :         return const_iterator(const_cast<DenseSet*>(this)->find(k));  // HACK
     164             :     }
     165             : 
     166           0 :     size_type count(const Key &k) const
     167             :     {
     168           0 :         return used_[k - range_begin];
     169             :     }
     170             : 
     171           0 :     std::pair<iterator, bool> insert(const Key &k)
     172             :     {
     173           0 :         bool &u = used_[k - range_begin];
     174           0 :         if (u)
     175             :         {
     176           0 :             return std::pair<iterator, bool>(iterator(this, k), false);
     177             :         }
     178             :         else
     179             :         {
     180           0 :             u = true;
     181           0 :             ++num_used_;
     182           0 :             return std::pair<iterator, bool>(iterator(this, k), true);
     183             :         }
     184             :     }
     185             : 
     186             :     template <class InputIterator>
     187             :     void insert(InputIterator it, InputIterator end)
     188             :     {
     189             :         for ( ; it != end; ++it)
     190             :         {
     191             :             Key k = *it;
     192             :             used_[k - range_begin] = true;
     193             :         }
     194             :     }
     195             : 
     196             : public:
     197             :     const Key range_begin, range_end;
     198             : 
     199             : private:
     200             :     const size_type range_size_;
     201             :     Alloc           alloc_;
     202             :     bool            *used_;
     203             :     std::size_t          num_used_;
     204             : 
     205             :     friend class Iterator;
     206             : 
     207             : private:
     208             :     DenseSet(const DenseSet &);
     209             :     DenseSet &operator=(const DenseSet &);
     210             : };
     211             : 
     212             : #endif /* ndef MCRL2_PG_DENSE_SET_H */

Generated by: LCOV version 1.14