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 */