src/util/random_sequence.h

   1 #ifndef RANDOM_SEQUENCE_H_
   2 #define RANDOM_SEQUENCE_H_
   3
   4 #include "cksequence_internal.h"
   5 #include "pup.h"
   6
   7 #include <vector>
   8 #include <algorithm>
   9 #include <string.h>
  10 #include <iostream>
  11
  12 #define Set(a, ind) a[(ind/8)] = (a[(ind/8)] | (1<<(ind%8)))
  13 #define Reset(a, ind) a[(ind/8)] = (a[(ind/8)] & (~(1<<(ind%8))))
  14 #define IsSet(a, ind) (a[(ind/8)] & (1<<(ind%8)))
  15
  16 /**
  17 * Iterator for the RandomSequence
  18 *
  19 * @tparam T
  20 */
  21 template <typename T>
  22 class RandomIterator : public CkSequenceIteratorInternal<T> {
  23  public:
  24   typename std::vector<T>::iterator it_;
  25
  26   RandomIterator() {}
  27
  28   RandomIterator(typename std::vector<T>::iterator it) : it_(it) {}
  29
  30   T& operator*() {
  31     return *it_;
  32   }
  33
  34   void operator++() {
  35     ++it_;
  36   }
  37
  38   void operator++(int) {
  39     ++it_;
  40   }
  41
  42   void operator--() {
  43     --it_;
  44   }
  45
  46   void operator--(int) {
  47     --it_;
  48   }
  49
  50   bool operator==(const CkSequenceIteratorInternal<T>& rhs) const {
  51     return (this->it_ == ((RandomIterator *)&rhs)->it_);
  52   }
  53
  54   bool operator!=(const CkSequenceIteratorInternal<T>& rhs) const {
  55     return (this->it_ != ((RandomIterator *)&rhs)->it_);
  56   }
  57 };
  58
  59 template <typename T>
  60 class BitVectorIterator : public CkSequenceIteratorInternal<T> {
  61  public:
  62   BitVectorIterator() {}
  63
  64   BitVectorIterator(char*& bit_vector, int start, int index, int max) :
  65       bit_vector_(bit_vector), start_(start), index_(index), max_(max) {
  66     while ((index_ < max_ + 1) && !IsSet(bit_vector_, index_)) {
  67       index_++;
  68     }
  69   }
  70
  71   T operator*() {
  72     return (start_ + index_);
  73   }
  74
  75   void operator++() {
  76     while ((++index_ < max_+1) && !IsSet(bit_vector_, index_)) {
  77     }
  78   }
  79
  80   void operator++(int) {
  81     while ((++index_ < max_+1) && !IsSet(bit_vector_, index_)) {
  82     }
  83   }
  84
  85   void operator--() {
  86   }
  87
  88   void operator--(int) {
  89   }
  90
  91   bool operator==(const CkSequenceIteratorInternal<T>& rhs) const {
  92     return (this->bit_vector_ == ((BitVectorIterator *)&rhs)->bit_vector_ &&
  93         this->index_ == ((BitVectorIterator *)&rhs)->index_);
  94   }
  95
  96   bool operator!=(const CkSequenceIteratorInternal<T>& rhs) const {
  97     return (this->bit_vector_ != ((BitVectorIterator *)&rhs)->bit_vector_ ||
  98         this->index_ != ((BitVectorIterator *)&rhs)->index_);
  99   }
 100
 101  private:
 102   char* bit_vector_;
 103   int start_;
 104   int index_;
 105   int max_;
 106 };
 107
 108
 109 /**
 110 *
 111 * @tparam T
 112 */
 113 template <typename T>
 114 class RandomSequence : public CkSequenceInternal<T> {
 115
 116  public:
 117
 118   RandomSequence() {
 119   }
 120
 121   RandomSequence(char*& bit_vector, int start, int end) {
 122     min_ = start % 8;
 123     start_ = start - min_;
 124     max_ = min_ + (end - start);
 125     std::cout << "starting element " << start_ << " ending ele " << end << " max " << max_ << " min " << min_ << std::endl;
 126     bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
 127     memcpy(bit_vector_, &bit_vector[(start/8)], (max_+1)/8 + 1);
 128   }
 129
 130   template <typename GenericIterator>
 131   RandomSequence(const GenericIterator& begin, const GenericIterator& end) {
 132     num_elements_ = 0;
 133     max_ = 0;
 134     if (begin == end) {
 135       return;
 136     }
 137     min_ = *begin;
 138     for (GenericIterator it = begin; it != end; ++it) {
 139       num_elements_++;
 140       if (max_ < *it) {
 141         max_ = *it;
 142       }
 143       if (*it < min_) {
 144         min_ = *it;
 145       }
 146     }
 147     max_;
 148     std::cout << "max " << max_ << std::endl;
 149     bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
 150     memset(bit_vector_, 0, (max_+1)/8 + 1);
 151
 152     for (GenericIterator it = begin; it != end; ++it) {
 153       Set(bit_vector_, (*it));
 154     }
 155     std::cout << "Malloc bits " << ((max_+1)/8 + 1) << std::endl;
 156   }
 157
 158   ~RandomSequence() {
 159   }
 160
 161   void Insert(const T& element);
 162
 163   void Remove(const T& element);
 164
 165   int num_elements() const;
 166
 167   int mem_size() const;
 168
 169   T min() const {
 170     return start_;
 171   }
 172
 173   T max() const {
 174     return start_ + max_;
 175   }
 176
 177   Type type() const {
 178     return RANDOM;
 179   }
 180
 181   CkSequenceIteratorInternal<T>* begin() {
 182     return new BitVectorIterator<T>(bit_vector_, start_, min_, max_);
 183   }
 184
 185   CkSequenceIteratorInternal<T>* end() {
 186     return new BitVectorIterator<T>(bit_vector_, start_, max_+1, max_);
 187   }
 188
 189   void pup(PUP::er &p) {
 190     p|num_elements_;
 191     p|start_;
 192     p|min_;
 193     p|max_;
 194     if (p.isUnpacking()) {
 195       bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
 196     }
 197     PUParray(p, bit_vector_, ((max_+1)/8 + 1));
 198   }
 199
 200  private:
 201   int num_elements_;
 202   T start_;
 203   T min_;
 204   T max_;
 205   char* bit_vector_;
 206 };
 207
 208 template <typename T>
 209 inline void RandomSequence<T>::Insert(const T& element) {
 210   int ele_ind = element - start_;
 211   if (ele_ind/8 > (max_+1)/8) {
 212     int diff = ((ele_ind + 1) / 8) - (( max_ + 1) / 8);
 213     bit_vector_ = (char *) realloc(bit_vector_, (ele_ind+1)/8 + 1);
 214     memset(&bit_vector_[((max_+1)/8) + 1], 0, diff);
 215   }
 216   Set(bit_vector_, ele_ind);
 217   if (ele_ind > max_) {
 218     max_ = ele_ind;
 219   }
 220 }
 221
 222 template <typename T>
 223 inline void RandomSequence<T>::Remove(const T& element) {
 224 }
 225
 226 template <typename T>
 227 inline int RandomSequence<T>::num_elements() const {
 228   return num_elements_;
 229 }
 230
 231 template <typename T>
 232 inline int RandomSequence<T>::mem_size() const {
 233 //  return sizeof(T) * container_.size();
 234   return ((max_+1)/8 + 3);
 235 }
 236
 237
 238 #endif  // RANDOM_SEQUENCE_H_