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_MAP_H
      11             : #define MCRL2_PG_DENSE_MAP_H
      12             : 
      13             : #include <vector>
      14             : #include <memory>
      15             : #include <utility>
      16             : 
      17             : /*! \ingroup Containers
      18             : 
      19             :     A map-like data structure with keys from a dense integer range.
      20             : 
      21             :     Each map instance has a fixed range of possible keys.  Memory used and time
      22             :     required to iterate over the set is proportional to the size of the range
      23             :     (*not* the  size of the set, i.e. the number of elements).
      24             : 
      25             :     Internally, the DenseMap uses an array of key/value-pairs to store its
      26             :     contents.  A special `Unused` value marks the absence of stored elements.
      27             :     Note that this is quite different from DenseSet!
      28             : 
      29             :     Note that the `Unused` template parameter must never be used as a value
      30             :     stored in the map.  `Used` on the other hand, may be any valid value.  It
      31             :     will be used internally to mark the end of the stored data.
      32             : 
      33             :     \see DenseSet
      34             : */
      35             : 
      36             : // N.B. this class is far from finished!
      37             : 
      38             : template<class Key, class Val, Val Used = Val(0), Val Unused = Val(-1),
      39             :     class Alloc = std::allocator<std::pair<Key, Val> > >
      40             : class DenseMap
      41             : {
      42             : public:
      43             :     typedef std::pair<Key, Val> value_type;
      44             : 
      45             :     class Iterator
      46             :     {
      47             :         value_type *pos_;
      48             : 
      49             :     public:
      50           0 :         Iterator(value_type *pos) : pos_(pos) { };
      51             :         Iterator(const Iterator &it) : pos_(it.pos_) { };
      52             :         Iterator& operator=(const Iterator &it) { pos_ = it.pos_; }
      53             : 
      54             :         bool operator== (const Iterator &other) { return pos_ == other.pos_; }
      55           0 :         bool operator!= (const Iterator &other) { return pos_ != other.pos_; }
      56             :         bool operator<  (const Iterator &other) { return pos_ <  other.pos_; }
      57             :         bool operator>  (const Iterator &other) { return pos_ >  other.pos_; }
      58             :         bool operator<= (const Iterator &other) { return pos_ <= other.pos_; }
      59             :         bool operator>= (const Iterator &other) { return pos_ >= other.pos_; }
      60             : 
      61           0 :         value_type operator*() { return *pos_; };
      62           0 :         value_type *operator->() { return pos_; };
      63             :     };
      64             : 
      65             :     typedef Iterator iterator;
      66             :     typedef Iterator const_iterator;
      67             : 
      68           0 :     DenseMap(Key begin, Key end, const Alloc &alloc = Alloc())
      69           0 :         : range_begin(begin), range_end(end < begin ? begin : end),
      70           0 :           range_size_(range_end - range_begin),
      71           0 :           values_(alloc), used_(0)
      72             :     {
      73           0 :         values_.reserve(range_size_ + 1);
      74           0 :         for (Key k = range_begin; k != range_end; ++k)
      75             :         {
      76           0 :             values_.push_back(value_type(k, Unused));
      77             :         }
      78           0 :         values_.push_back(value_type(range_end, Used));  // end of data marker
      79           0 :     }
      80             : 
      81             :     std::size_t size() const { return used_; }
      82             :     bool empty() const { return used_ == 0; }
      83             : 
      84             :     void clear()
      85             :     {
      86             :         if (used_ > 0)
      87             :         {
      88             :             for ( typename std::vector<value_type>::iterator
      89             :                     it = values_.begin(); it != values_.end(); ++it )
      90             :             {
      91             :                 *it->second = Unused;
      92             :             }
      93             :             used_ = 0;
      94             :         }
      95             :     }
      96             : 
      97             :     iterator begin()
      98             :     {
      99             :         Val *v = &values_[0];
     100             :         while (v->second == Unused) ++v;
     101             :         return iterator(v);
     102             :     }
     103             : 
     104           0 :     iterator end()
     105             :     {
     106           0 :         return iterator(&values_[range_size_]);
     107             :     }
     108             : 
     109             :     const_iterator begin() const
     110             :     {
     111             :         return iterator(const_cast<DenseMap*>(this)->begin());  // HACK
     112             :     }
     113             : 
     114             :     const_iterator end() const
     115             :     {
     116             :         return iterator(const_cast<DenseMap*>(this)->end());  // HACK
     117             :     }
     118             : 
     119           0 :     iterator find(Key k)
     120             :     {
     121           0 :         if ( /* k >= range_begin && k < range_end && */
     122           0 :             values_[k - range_begin].second != Unused)
     123             :         {
     124           0 :             return iterator(&values_[k - range_begin]);
     125             :         }
     126             :         else
     127             :         {
     128           0 :             return end();
     129             :         }
     130             :     }
     131             : 
     132             :     const_iterator find(Key k) const
     133             :     {
     134             :         return const_iterator(const_cast<DenseMap*>(this)->find(k));  // HACK
     135             :     }
     136             : 
     137           0 :     Val &operator[](Key k)
     138             :     {
     139           0 :         value_type &kv = values_[k - range_begin];
     140           0 :         if (kv.second == Unused)
     141             :         {
     142           0 :             kv.second = Val();
     143           0 :             ++used_;
     144             :         }
     145           0 :         return kv.second;
     146             :     }
     147             : 
     148             :     std::pair<iterator, bool> insert(const value_type &new_kv)
     149             :     {
     150             :         value_type &kv = values_[new_kv.first - range_begin];
     151             :         bool inserted = (kv.second == Unused);
     152             :         kv.second = new_kv.second;
     153             :         return std::pair<iterator, bool>(iterator(&kv), inserted);
     154             :     }
     155             : 
     156             : public:
     157             :     const Key range_begin, range_end;
     158             : 
     159             : private:
     160             :     const std::size_t range_size_;
     161             :     std::vector<value_type> values_;
     162             :     std::size_t used_;
     163             : 
     164             : private:
     165             :     DenseMap(const DenseMap &);
     166             :     DenseMap &operator=(const DenseMap &);
     167             : };
     168             : 
     169             : #endif /* ndef MCRL2_PG_DENSE_MAP_H */