---

IndexSetUtilities.hh

#ifndef INDEXSETUTILITES
#define INDEXSETUTILITES

#include "IotrUtilities.hh"
#include<vector>
#include<assert.h>

class IndexSetIterator {
  const int * index;
  int n, k, end, cval, rval, notFoundValue;
public:
  int currentValue() { return cval; }
  int rangeValue() { return rval; }
  int runLength() { return end - cval + 1; }
  int endSequence() { return end; }
  IndexSetIterator( const int * ii, int nn, int nf ) :
    index(ii), n(nn), k(0), end(-1), cval(0), rval(0), notFoundValue(nf)
  {}
  int empty() { return cval == notFoundValue; }
  int next()
  {
    if( cval >= end ) { // No more elts in the run, start a new sequence
      return this->nextSequence();
    } else { 
      rval++;
      return ++cval;
    }
  }
  int nextSequence()
  {
    rval += this->runLength(); // skipping "run" values in the range
    if( k < n ) { 
      int ind = index[k++];
      if( ind >= 0 ) {
        end = ind;
        return cval = ind;
      } else {
        cval = index[k++];
        end = cval - ind - 1;
        return cval;
      }
    } else { // Empty stack
      end = notFoundValue;  k = n;
      return cval = notFoundValue;
    }
  }
  int next( int n )
  {
    rval += n;
    int i = n;
    while( i > 0 ) {
      if( cval + i <= end ) {
        cval += i; i = 0;
      } else {
        i -= this->runLength();
        this->nextSequence();
      }
    }
    return cval;
  }
  int seekAtLeast( int val )
  {
    while( cval != notFoundValue && val > end ) {
      // val is not in the current sequence
      this->nextSequence();
    }
    if( cval != notFoundValue && val > cval ) {
      rval += (val - cval);
      cval  = val;
    }
    return cval;
  }
};


class IndexSetCollector {
  std::vector<int> index;
  int run, start,  mRange;
public:
  IndexSetCollector() : run(0), start(0), mRange(0) {}
  IndexSetCollector( int capacity ) :
    run(0), start(0), mRange(0)
  {
    index.reserve( capacity );
  }
  void reserve( int n ) { index.reserve( n ); }
  int * indices() { return index.size() > 0 ? &index[0] : 0; }
  int nindices() { return index.size(); }
  int range() { return mRange; }
  int last() { return mRange - 1; }

  int writeSequence( int elt, int erun ) {
    if( elt > start + run ) { // New sequence, write the old
      this->flush();
      run = erun;  start = elt;
    } else if ( elt == start + run ) {
      run += erun; 
    } else { // an invalid elt to write
      return 1;
    }
    mRange += erun;
    return 0;
  }
  int write( int val )
  {
    return this->writeSequence( val, 1 );
  }
  void flush()
  {
    if( run == 1 ) {
      index.push_back(start);
    } else if( run > 2 ) {
      index.push_back(-run); index.push_back(start);
    } else if ( run == 2 ) {
      index.push_back( start ); index.push_back( start + 1 );
    }
  }
};


template<class T> inline void 
condensed_index_loop( const int index[], int n, const T & op )
{
  int i = 0;
  int k = 0;
  while( k < n ) {
    int ind = index[k]; k++;
    if( ind >= 0 ) {
      op( i, ind );
      i++;
    } else {
      int start  = index[k]; k++;
      int end    = start - ind;
      for( int j = start; j < end; j++ ) {
        op( i, j );
        i++;
      }
    }
  }
}


#endif

---