cksequence implementation with memory compaction
authorHarshitha Menon <gplkrsh2@illinois.edu>
Sat, 29 Oct 2011 06:52:19 +0000 (01:52 -0500)
committerHarshitha Menon <gplkrsh2@illinois.edu>
Sat, 29 Oct 2011 06:52:19 +0000 (01:52 -0500)
src/scripts/Makefile
src/util/cksequence.h [new file with mode: 0644]
src/util/cksequence_factory.h [new file with mode: 0644]
src/util/cksequence_internal.h [new file with mode: 0644]
src/util/random_sequence.h [new file with mode: 0644]
src/util/strided_sequence.h [new file with mode: 0644]

index dc7e4c636eea6c40340395df89a6f58fd8c03eed..c9648d61215dbbd27485141482767c1841397d75 100644 (file)
@@ -205,7 +205,7 @@ CONVCOMHEADERS= 3dgridrouter.h hypercuberouter.h hypercubetopology.h        \
 # This is a bit unusual, but makes client linking simpler.
 UTILHEADERS=pup.h pupf.h pup_c.h pup_stl.h pup_mpi.h pup_toNetwork.h pup_toNetwork4.h pup_paged.h pup_cmialloc.h\
        ckimage.h ckdll.h ckhashtable.h ckbitvector.h cklists.h ckliststring.h \
-       ckstatistics.h ckvector3d.h conv-lists.h RTH.h ckcomplex.h \
+       cksequence.h ckstatistics.h ckvector3d.h conv-lists.h RTH.h ckcomplex.h \
        sockRoutines.h sockRoutines.c ckpool.h BGLTorus.h BGPTorus.h \
        TopoManager.h XT3Torus.h XTTorus.h cmimemcpy.h simd.h SSE-Double.h SSE-Float.h crc32.h
 
@@ -250,6 +250,7 @@ CKHEADERS=ck.h ckstream.h envelope.h init.h qd.h charm.h charm++.h \
          ControlPoints.decl.h PathHistory.decl.h \
          pathHistory.h envelope-path.h \
           controlPoints.h controlPointsf.h arrayRedistributor.h cp_effects.h register.h stats.h   \
+         cksequence_internal.h cksequence_factory.h random_sequence.h strided_sequence.h \
          $(CVHEADERS) $(CONVCOMHEADERS)
 
 ALLHEADERS=$(CKHEADERS) \
diff --git a/src/util/cksequence.h b/src/util/cksequence.h
new file mode 100644 (file)
index 0000000..8c715f6
--- /dev/null
@@ -0,0 +1,465 @@
+#ifndef SEQUENCE_H_
+#define SEQUENCE_H_
+
+#include "cksequence_factory.h"
+#include "cksequence_internal.h"
+#include "pup.h"
+
+#include <list>
+#include <math.h>
+
+#define CHAR_SIZE 8
+
+/**
+* Iterates over the elements in the CkSequence. Consists of the standard
+* functionalities of an iterator.
+* Sample usage:
+*   CkSequence<int>::iterator it  = s.begin();
+*
+* @tparam T
+*/
+template <typename T>
+class CkSequenceIterator {
+ public:
+
+  CkSequenceIterator() {}
+  
+  CkSequenceIterator(CkSequenceIteratorInternal<T>* it) : it_(it) {}
+
+  /**
+  * Constructs the CkSequenceIterator given an internal implementation of the
+  * CkSequenceIterator
+  *
+  * @Param it internal implementation of the Iterator
+  */
+  CkSequenceIterator(typename std::list<CkSequenceInternal<T> *>::iterator
+       subsequence_list_it,
+       typename std::list<CkSequenceInternal<T> *>::iterator
+       subsequence_list_it_end) {
+    subsequence_list_it_ = subsequence_list_it;
+    subsequence_list_it_end_ = subsequence_list_it_end;
+    if (subsequence_list_it_ == subsequence_list_it_end_) {
+      it_ = NULL;
+      it_end_ = NULL;
+    } else {
+      it_ = (*subsequence_list_it_)->begin();
+      it_end_ = (*subsequence_list_it_)->end();
+    }
+  }
+
+  ~CkSequenceIterator() {
+//    delete it_;
+  }
+
+  T operator*() {
+    return **it_;
+  }
+
+  void operator++() {
+    ++(*it_);
+    if (*it_ == *it_end_) {
+      if (++subsequence_list_it_ == subsequence_list_it_end_) {
+        it_ = NULL;
+        it_end_ = NULL;
+      } else {
+        it_ = (*subsequence_list_it_)->begin();
+        it_end_ = (*subsequence_list_it_)->end();
+      }
+    }
+  }
+
+  void operator++(int) {
+    ++(*it_);
+    if (*it_ == *it_end_) {
+      if (++subsequence_list_it_ == subsequence_list_it_end_) {
+        it_ = NULL;
+        it_end_ = NULL;
+      } else {
+        it_ = (*subsequence_list_it_)->begin();
+        it_end_ = (*subsequence_list_it_)->end();
+      }
+    }
+
+  }
+
+  bool operator==(const CkSequenceIterator& rhs) const {
+    if (it_ == NULL || rhs.it_ == NULL) {
+      return (this->it_ == rhs.it_);
+    }
+    return (*(this->it_) == *(rhs.it_));
+  }
+
+  bool operator!=(const CkSequenceIterator& rhs) const {
+    if (it_ == NULL || rhs.it_ == NULL) {
+      return (this->it_ != rhs.it_);
+    }
+    return (*(this->it_) != *(rhs.it_));
+  }
+
+ private:
+  CkSequenceIteratorInternal<T>* it_;
+  CkSequenceIteratorInternal<T>* it_end_;
+  typename std::list<CkSequenceInternal<T>* >::iterator subsequence_list_it_;
+  typename std::list<CkSequenceInternal<T>* >::iterator subsequence_list_it_end_;
+  int index_;
+};
+
+/**
+* Data Structure to store a sequence of any type, typically int, short, long
+* etc. Two types of CkSequences are currently supported, RANDOM and STRIDE. By
+* default, a RandomCkSequence is created. This class Delegates the calls to the
+* internal implementation of CkSequence
+*
+* Sample Usage:
+*   CkSequence<int> s_default;
+*   CkSequence<int> seq_random(CkSequence<int>::RANDOM);
+*
+* @tparam T
+*/
+template <typename T>
+class CkSequence {
+
+ public:
+
+
+  /**
+  * Creates a RandomSequence by default
+  */
+  CkSequence() : bit_vector_(NULL), compact_(false) {}
+
+  /**
+  * Creates Sequence object based on the vector passed in. The default sequence
+  * created is RandomSequence.
+  *
+  * @Param l containing the elements to be stored
+  */
+  template <typename GenericIterator>
+  CkSequence(const GenericIterator begin, const GenericIterator end) {
+    compact_ = false;
+    min_ = 0;
+    max_ = 0;
+    num_elements_ = 0;
+    if (begin == end) {
+      return;
+    }
+
+    // Find the min and the max element
+    min_ = *begin;
+    for (GenericIterator it = begin; it != end; ++it) {
+      num_elements_++;
+      if (max_ < *it) {
+        max_ = *it;
+      }
+      if (*it < min_) {
+        min_ = *it;
+      }
+    }
+
+    // Allocate memory for the bit vector
+    bit_vector_ = (char *) malloc ((max_+1)/CHAR_SIZE + 1);
+    memset(bit_vector_, 0, (max_+1)/CHAR_SIZE + 1);
+
+    for (GenericIterator it = begin; it != end; ++it) {
+      Set(bit_vector_, (*it));
+    }
+  }
+
+  template <typename GenericIterator>
+  void Insert(const GenericIterator begin, const GenericIterator end) {
+    compact_ = false;
+    min_ = 0;
+    max_ = 0;
+    num_elements_ = 0;
+    if (begin == end) {
+      return;
+    }
+
+    // Find the min and the max element
+    min_ = *begin;
+    for (GenericIterator it = begin; it != end; ++it) {
+      num_elements_++;
+      if (max_ < *it) {
+        max_ = *it;
+      }
+      if (*it < min_) {
+        min_ = *it;
+      }
+    }
+
+    // Allocate memory for the bit vector
+    bit_vector_ = (char *) malloc ((max_+1)/CHAR_SIZE + 1);
+    memset(bit_vector_, 0, (max_+1)/CHAR_SIZE + 1);
+
+    for (GenericIterator it = begin; it != end; ++it) {
+      Set(bit_vector_, (*it));
+    }
+  }
+
+
+  ~CkSequence() {
+    if (bit_vector_ != NULL) {
+      delete bit_vector_;
+      bit_vector_ = NULL;
+    }
+    for (int i = 0; i < subsequence_list_.size(); i++) {
+      //delete subsequence_list_[i];
+    }
+  }
+
+  /**
+  * Inserts the element in to the CkSequence Data Structure.
+  *
+  * @Param element to be inserted
+  */
+  void Insert(const T& element);
+
+  void InsertIntoStrided(typename std::list<CkSequenceInternal<T> *>::iterator
+      iter, const T& element);
+
+  /**
+  * Removes the element from the CkSequence Data Structure
+  *
+  * @Param element to be removed
+  */
+  void Remove(const T& element);
+
+  /**
+  * Called when the elements have been inserted into the sequence and no further
+  * modification would happen
+  */
+  void DoneInserting();
+
+  /**
+  * Identifies if the sequence has a stride pattern and if so returns true and
+  * sets stride to the identified stride.
+  *
+  * @Param stride sets it to be the stride for the given sequence
+  *
+  * @Returns true if there is a stride pattern else false
+  */
+
+  int num_elements() const;
+
+  int mem_size() const;
+
+  typedef CkSequenceIterator<T> iterator;
+
+  /**
+  * Returns the begin of the CkSequence.
+  * Sample Usage:
+  *   CkSequence<int>::iterator it = s.begin();
+  *
+  * @Returns  the iterator pointing to the begin
+  */
+  iterator begin() {
+    if (compact_) {
+      return iterator(subsequence_list_.begin(), subsequence_list_.end());
+    } else {
+      return iterator(new BitVectorIterator<T>(bit_vector_, 0, min_, max_));
+    }
+  }
+
+  /**
+   * Returns the end of the CkSequence
+   * Sample Usage:
+   *   CkSequence<int>::iterator it = s.end();
+   *
+   * @Returns   the iterator to the end
+   */
+  iterator end() {
+    if (compact_) {
+      return iterator(NULL);
+    } else {
+      return iterator(new BitVectorIterator<T>(bit_vector_, 0, max_+1, max_));
+    }
+  }
+
+  void pup(PUP::er &p) {
+    p|min_;
+    p|max_;
+    p|num_elements_;
+    p|compact_;
+    if (p.isUnpacking() && !compact_) {
+      bit_vector_ = (char *) malloc((max_+1)/CHAR_SIZE + 1);
+    }
+    if (!compact_) {
+      PUParray(p, bit_vector_, (max_+1)/CHAR_SIZE + 1);
+    }
+    if (!p.isUnpacking()) {
+      int size = subsequence_list_.size();
+      p|size;
+      int type;
+      for (typename std::list<CkSequenceInternal<T>*>::iterator it =
+          subsequence_list_.begin(); it != subsequence_list_.end(); it++) {
+        type = (*it)->type();
+        p|type;
+        p|(**it);
+      }
+    } else {
+      int size;
+      int type;
+      p|size;
+
+      for (int i=0; i < size; i++) {
+        p|type;
+        CkSequenceInternal<T>* seq_internal;
+        if (type == STRIDE) {
+          seq_internal = new StridedSequence<T>();
+        } else {
+          seq_internal = new RandomSequence<T>();
+        }
+        p|(*seq_internal);
+        subsequence_list_.push_back(seq_internal);
+      }
+    }
+  }
+
+ private:
+
+  void Compact();
+
+  T min_;
+  T max_;
+  T num_elements_;
+
+  // Storing the sequence 
+  bool compact_;
+  char* bit_vector_;
+
+  // Contains the combination of different types of sequences namely Random and
+  // Strided. 
+  std::list<CkSequenceInternal<T>*> subsequence_list_;
+};
+
+
+template <class T>
+inline void CkSequence<T>::Insert(const T& element) {
+  if (compact_) {
+    CkAbort("Cannot insert after DoneInserting() is called\n");
+  }
+  if ((element/CHAR_SIZE) > ((max_+1)/CHAR_SIZE)) {
+    bit_vector_ = (char *) realloc(bit_vector_, (element+1)/CHAR_SIZE + 1);
+    int diff = ((element + 1) / CHAR_SIZE) - ((max_+1) / CHAR_SIZE);
+    memset(&bit_vector_[((max_+1)/CHAR_SIZE) + 1], 0, diff);
+  }
+
+  Set(bit_vector_, element);
+
+  if (element > max_) {
+    max_ = element;
+  } else if (element < min_) {
+    min_ = element;
+  }
+}
+
+template <class T>
+inline void CkSequence<T>::Remove(const T& element) {
+  if (compact_) {
+    CkAbort("Cannot insert after DoneInserting() is called\n");
+  }
+  Reset(bit_vector_, element);
+}
+
+template <class T>
+inline int CkSequence<T>::num_elements() const {
+  if (subsequence_list_.size() <= 0) {
+    return 0;
+  }
+//  return subsequence_list_[0]->num_elements();
+}
+
+template <class T>
+inline int CkSequence<T>::mem_size() const {
+  int sum = 0;
+  for (int i = 0; i < subsequence_list_.size(); ++i) {
+ //   sum += subsequence_list_[i]->mem_size();
+  }
+  return sum;
+}
+
+template <typename T>
+inline void CkSequence<T>::Compact() {
+  compact_ = true;
+  std::cout << "Compacting!!!\n";
+  int seq_begin_ele = min_;
+  int prev_ele = min_;
+  int prev_prev_ele = min_;
+  int prev_prev_prev_ele = min_;
+
+  int end_stride = min_;
+
+  int start_random = min_;
+  int end_random = min_;
+
+  int stride = -1;
+  std::cout << "Current size " << ((max_+1)/CHAR_SIZE + 1) << std::endl;
+
+
+  int tmp_stride = 0;
+  bool is_strided = false;
+
+  for (T i = min_+ 1; i <= max_; i++) {
+    if (IsSet(bit_vector_,i)) {
+      tmp_stride = i - prev_ele;
+
+      if (tmp_stride == stride) {
+        // Start of strided pattern
+        if (!is_strided && seq_begin_ele != prev_prev_ele) {
+          std::cout << "Create random " << seq_begin_ele  << " end " << prev_prev_prev_ele<< std::endl;
+          CkSequenceInternal<T>* sequence_internal =
+            CkSequenceFactory<T>::CreateRandomSequence(bit_vector_,
+                seq_begin_ele, prev_prev_prev_ele);
+          subsequence_list_.push_back(sequence_internal);
+          seq_begin_ele = prev_prev_ele;
+        }
+
+        is_strided = true;
+        end_stride = i;
+      } else if (tmp_stride != stride) {
+        // End of stride pattern
+        if (is_strided) {
+          std::cout << "Create stride " << seq_begin_ele<< " stride " << stride
+            << " end stride " << end_stride  << " new seq end " << i << " count " << (end_stride - seq_begin_ele)/stride + 1<< std::endl;
+
+          CkSequenceInternal<T>* sequence_internal =
+            CkSequenceFactory<T>::CreateStridedSequence(seq_begin_ele, stride,
+                end_stride);
+          subsequence_list_.push_back(sequence_internal);
+          seq_begin_ele = i;
+          prev_prev_prev_ele = i;
+          prev_prev_ele = i;
+          tmp_stride = -1;
+        }
+
+        start_random = i;
+        is_strided = false;
+      }
+      prev_prev_prev_ele = prev_prev_ele;
+      prev_prev_ele = prev_ele;
+      stride = tmp_stride;
+      prev_ele = i;
+    }
+  }
+
+  if (is_strided) {
+    std::cout << "Create stride " << seq_begin_ele<< " stride " << stride
+      << " end stride " << end_stride  << " count " << (end_stride - seq_begin_ele)/stride + 1<< std::endl;
+    CkSequenceInternal<T>* sequence_internal =
+      CkSequenceFactory<T>::CreateStridedSequence(seq_begin_ele, stride, end_stride);
+    subsequence_list_.push_back(sequence_internal);
+  } else {
+    CkSequenceInternal<T>* sequence_internal =
+      CkSequenceFactory<T>::CreateRandomSequence(bit_vector_, seq_begin_ele,start_random);
+    subsequence_list_.push_back(sequence_internal);
+  }
+  delete bit_vector_;
+  bit_vector_ = NULL;
+}
+
+template <class T>
+inline void CkSequence<T>::DoneInserting() {
+  std::cout << "Done inserting\n";
+  Compact();
+}
+
+#endif // SEQUENCE_H_
diff --git a/src/util/cksequence_factory.h b/src/util/cksequence_factory.h
new file mode 100644 (file)
index 0000000..dbec3cf
--- /dev/null
@@ -0,0 +1,42 @@
+#ifndef SEQUENCE_FACTORY_H_
+#define SEQUENCE_FACTORY_H_
+
+#include "random_sequence.h"
+#include "cksequence_internal.h"
+#include "strided_sequence.h"
+
+/**
+* Factory that creates different kinds of CkSequences. Currently, there are two
+* types of CkSequences, namely, RANDOM and STRIDE
+*
+* @tparam T
+*/
+template <typename T>
+class CkSequenceFactory {
+ public:
+  static CkSequenceInternal<T>* CreateRandomSequence() {
+    return new RandomSequence<T>();
+  }
+
+  template <typename GenericIterator>
+  static CkSequenceInternal<T>* CreateRandomSequence(const GenericIterator& begin,
+      const GenericIterator& end) {
+    return new RandomSequence<T>(begin, end);
+  }
+
+  static CkSequenceInternal<T>* CreateRandomSequence(char* bit_vector, int
+      start_ele, int end_ele) {
+    return new RandomSequence<T>(bit_vector, start_ele, end_ele);
+  }
+
+  static CkSequenceInternal<T>* CreateStridedSequence() {
+    return new StridedSequence<T>();
+  }
+
+  static CkSequenceInternal<T>* CreateStridedSequence(T start_element, T stride,
+      T end_element) {
+    return new StridedSequence<T>(start_element, stride, end_element);
+  }
+};
+
+#endif   // SEQUENCE_FACTORY_H_
diff --git a/src/util/cksequence_internal.h b/src/util/cksequence_internal.h
new file mode 100644 (file)
index 0000000..2833c0b
--- /dev/null
@@ -0,0 +1,68 @@
+#ifndef SEQUENCE_INTERNAL_H
+#define SEQUENCE_INTERNAL_H
+
+#include <vector>
+#include "pup.h"
+
+  /**
+  * There are two types of sequences, RANDOM and STRIDE.
+  */
+  enum Type {RANDOM, STRIDE};
+template <typename T>
+struct StrideInfo {
+  T start_element;
+  T stride;
+  T end_element;
+};
+
+/**
+* Interface(Abstract Class) for the Internal implementation of the Iterator
+*
+* @tparam T
+*/
+template <typename T>
+class CkSequenceIteratorInternal {
+ public:
+
+
+  virtual T operator*() = 0;
+  virtual void operator++() = 0;
+  virtual void operator++(int) = 0;
+  virtual void operator--() = 0;
+  virtual void operator--(int) = 0;
+  virtual bool operator==(const CkSequenceIteratorInternal& rhs) const = 0;
+  virtual bool operator!=(const CkSequenceIteratorInternal& rhs) const = 0;
+};
+
+/**
+* Interface(Abstract class) for the Internal implementation of the CkSequence
+*
+* @tparam T
+*/
+template <typename T>
+class CkSequenceInternal {
+ public:
+
+
+  virtual void Insert(const T& element) = 0;
+
+  virtual void Remove(const T& element) = 0;
+
+  virtual int num_elements() const = 0;
+
+  virtual T min() const = 0;
+
+  virtual T max() const = 0;
+
+  virtual Type type() const = 0;
+
+  virtual CkSequenceIteratorInternal<T>* begin() = 0;
+
+  virtual CkSequenceIteratorInternal<T>* end() = 0;
+
+  // Returns the size of the memory for internal representation of the elements
+  virtual int mem_size() const = 0;
+  virtual void pup(PUP::er &p) = 0;
+};
+
+#endif  // SEQUENCE_INTERNAL_H
diff --git a/src/util/random_sequence.h b/src/util/random_sequence.h
new file mode 100644 (file)
index 0000000..bd7d470
--- /dev/null
@@ -0,0 +1,238 @@
+#ifndef RANDOM_SEQUENCE_H_
+#define RANDOM_SEQUENCE_H_
+
+#include "cksequence_internal.h"
+#include "pup.h"
+
+#include <vector>
+#include <algorithm>
+#include <string.h>
+#include <iostream>
+
+#define Set(a, ind) a[(ind/8)] = (a[(ind/8)] | (1<<(ind%8)))
+#define Reset(a, ind) a[(ind/8)] = (a[(ind/8)] & (~(1<<(ind%8))))
+#define IsSet(a, ind) (a[(ind/8)] & (1<<(ind%8)))
+
+/**
+* Iterator for the RandomSequence   
+*
+* @tparam T
+*/
+template <typename T>
+class RandomIterator : public CkSequenceIteratorInternal<T> {
+ public:
+  typename std::vector<T>::iterator it_;
+
+  RandomIterator() {}
+
+  RandomIterator(typename std::vector<T>::iterator it) : it_(it) {}
+
+  T& operator*() {
+    return *it_;
+  }
+
+  void operator++() {
+    ++it_;
+  }
+
+  void operator++(int) {
+    ++it_;
+  }
+
+  void operator--() {
+    --it_;
+  }
+
+  void operator--(int) {
+    --it_;
+  }
+
+  bool operator==(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->it_ == ((RandomIterator *)&rhs)->it_);
+  }
+
+  bool operator!=(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->it_ != ((RandomIterator *)&rhs)->it_);
+  }
+};
+
+template <typename T>
+class BitVectorIterator : public CkSequenceIteratorInternal<T> {
+ public:
+  BitVectorIterator() {}
+
+  BitVectorIterator(char*& bit_vector, int start, int index, int max) :
+      bit_vector_(bit_vector), start_(start), index_(index), max_(max) {
+    while ((index_ < max_ + 1) && !IsSet(bit_vector_, index_)) {
+      index_++;
+    }
+  }
+
+  T operator*() {
+    return (start_ + index_);
+  }
+
+  void operator++() {
+    while ((++index_ < max_+1) && !IsSet(bit_vector_, index_)) {
+    }
+  }
+
+  void operator++(int) {
+    while ((++index_ < max_+1) && !IsSet(bit_vector_, index_)) {
+    }
+  }
+
+  void operator--() {
+  }
+
+  void operator--(int) {
+  }
+
+  bool operator==(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->bit_vector_ == ((BitVectorIterator *)&rhs)->bit_vector_ &&
+        this->index_ == ((BitVectorIterator *)&rhs)->index_);
+  }
+
+  bool operator!=(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->bit_vector_ != ((BitVectorIterator *)&rhs)->bit_vector_ ||
+        this->index_ != ((BitVectorIterator *)&rhs)->index_);
+  }
+
+ private:
+  char* bit_vector_;
+  int start_;
+  int index_;
+  int max_;
+};
+
+
+/**
+*
+* @tparam T
+*/
+template <typename T>
+class RandomSequence : public CkSequenceInternal<T> {
+
+ public:
+  
+  RandomSequence() {
+  }
+
+  RandomSequence(char*& bit_vector, int start, int end) {
+    min_ = start % 8;
+    start_ = start - min_;
+    max_ = min_ + (end - start);
+    std::cout << "starting element " << start_ << " ending ele " << end << " max " << max_ << " min " << min_ << std::endl;
+    bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
+    memcpy(bit_vector_, &bit_vector[(start/8)], (max_+1)/8 + 1);
+  }
+
+  template <typename GenericIterator>
+  RandomSequence(const GenericIterator& begin, const GenericIterator& end) {
+    num_elements_ = 0;
+    max_ = 0;
+    if (begin == end) {
+      return;
+    }
+    min_ = *begin;
+    for (GenericIterator it = begin; it != end; ++it) {
+      num_elements_++;
+      if (max_ < *it) {
+        max_ = *it;
+      }
+      if (*it < min_) {
+        min_ = *it;
+      }
+    }
+    max_;
+    std::cout << "max " << max_ << std::endl;
+    bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
+    memset(bit_vector_, 0, (max_+1)/8 + 1);
+
+    for (GenericIterator it = begin; it != end; ++it) {
+      Set(bit_vector_, (*it));
+    }
+    std::cout << "Malloc bits " << ((max_+1)/8 + 1) << std::endl;
+  }
+
+  ~RandomSequence() {
+  }
+
+  void Insert(const T& element);
+
+  void Remove(const T& element);
+
+  int num_elements() const;
+
+  int mem_size() const;
+
+  T min() const {
+    return start_;
+  }
+
+  T max() const {
+    return start_ + max_;
+  }
+
+  Type type() const {
+    return RANDOM;
+  }
+
+  CkSequenceIteratorInternal<T>* begin() {
+    return new BitVectorIterator<T>(bit_vector_, start_, min_, max_);
+  }
+
+  CkSequenceIteratorInternal<T>* end() {
+    return new BitVectorIterator<T>(bit_vector_, start_, max_+1, max_);
+  }
+
+  void pup(PUP::er &p) {
+    p|num_elements_;
+    p|start_;
+    p|min_;
+    p|max_;
+    if (p.isUnpacking()) {
+      bit_vector_ = (char *) malloc ((max_+1)/8 + 1);
+    }
+    PUParray(p, bit_vector_, ((max_+1)/8 + 1));
+  }
+
+ private:
+  int num_elements_;
+  T start_;
+  T min_;
+  T max_;
+  char* bit_vector_;
+};
+
+template <typename T>
+inline void RandomSequence<T>::Insert(const T& element) {
+  int ele_ind = element - start_;
+  if (ele_ind/8 > (max_+1)/8) {
+    int diff = ((ele_ind + 1) / 8) - (( max_ + 1) / 8);
+    bit_vector_ = (char *) realloc(bit_vector_, (ele_ind+1)/8 + 1);
+    memset(&bit_vector_[((max_+1)/8) + 1], 0, diff);
+  }
+  Set(bit_vector_, ele_ind);
+  if (ele_ind > max_) { 
+    max_ = ele_ind;
+  }
+}
+
+template <typename T>
+inline void RandomSequence<T>::Remove(const T& element) {
+}
+
+template <typename T>
+inline int RandomSequence<T>::num_elements() const {
+  return num_elements_;
+}
+
+template <typename T>
+inline int RandomSequence<T>::mem_size() const {
+//  return sizeof(T) * container_.size();
+  return ((max_+1)/8 + 3);
+}
+
+
+#endif  // RANDOM_SEQUENCE_H_
diff --git a/src/util/strided_sequence.h b/src/util/strided_sequence.h
new file mode 100644 (file)
index 0000000..96904ba
--- /dev/null
@@ -0,0 +1,131 @@
+#ifndef STRIDED_SEQUENCE_H_
+#define STRIDED_SEQUENCE_H_
+
+#include "cksequence_internal.h"
+#include "pup.h"
+
+#include <vector>
+#include <iostream>
+
+template <typename T>
+class StridedIterator : public CkSequenceIteratorInternal<T> {
+ public:
+  T element_;
+  T stride_;
+
+  StridedIterator() {
+  }
+
+  StridedIterator(T element) : element_(element), stride_(0) {
+  }
+
+  StridedIterator(T element, T stride) : element_(element), stride_(stride) {
+  }
+
+  T operator*() {
+    return element_;
+  }
+
+  void operator++() {
+    element_ += stride_;
+  }
+
+  void operator++(int) {
+    element_ += stride_;
+  }
+
+  void operator--() {
+    element_ -= stride_;
+  }
+
+  void operator--(int) {
+    element_ -= stride_;
+  }
+
+  bool operator==(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->element_ == ((StridedIterator*)&rhs)->element_);
+  }
+
+  bool operator!=(const CkSequenceIteratorInternal<T>& rhs) const {
+    return (this->element_ != ((StridedIterator*)&rhs)->element_);
+  }
+
+  
+
+};
+
+template <typename T>
+class StridedSequence : public CkSequenceInternal<T> {
+ public:
+  StridedSequence() : start_element_(1), stride_(1), last_element_(1) {
+  }
+
+  StridedSequence(T start_element, T stride, int end_element) :
+      start_element_(start_element),
+      stride_(stride),
+      last_element_(end_element) {
+  }
+
+  void Insert(const T& element);
+
+  void Remove(const T& element);
+  
+  int num_elements() const;
+
+  T min() const {
+    return start_element_;
+  }
+
+  T max() const {
+    return last_element_;
+  }
+
+  T stride() const {
+    return stride_;
+  }
+
+  Type type() const { 
+    return STRIDE;
+  }
+
+  int mem_size() const;
+
+  CkSequenceIteratorInternal<T>* begin() {
+    return new StridedIterator<T>(start_element_, stride_);
+  }
+
+  CkSequenceIteratorInternal<T>* end() {
+    return new StridedIterator<T>(last_element_ + stride_);
+  }
+
+  void pup(PUP::er &p) {
+    p|start_element_;
+    p|stride_;
+    p|last_element_;
+  }
+
+ private:
+  T start_element_;
+  T stride_;
+  T last_element_;
+};
+
+template <class T>
+inline void StridedSequence<T>::Insert(const T& element) {
+}
+
+template <class T>
+inline void StridedSequence<T>::Remove(const T& element) {
+}
+
+template <class T>
+inline int StridedSequence<T>::num_elements() const {
+  return (((last_element_ - start_element_) / stride_)  + 1);
+}
+
+template <class T>
+inline int StridedSequence<T>::mem_size() const {
+  return sizeof(T)*3;
+}
+
+#endif   // STRIDED_SEQUENCE_H_