SparseBitvector.hpp

Go to the documentation of this file.

/*
 * SparseBitvector.hpp
 *
 * Time-stamp: <05/06/01 18:14:47 lars>
 *
 */

#ifndef __SPARSE_BITVECTOR__
#define __SPARSE_BITVECTOR__ t

#include <iostream>
using namespace std;

#include "common/debug.hpp"

class SparseBitvector {
public:
#if DEBUG_LEVEL > 0
  SparseBitvector(int* values, int& length, int capacity) : m_values(values), m_length(length), m_capacity(capacity) {}
#else
  SparseBitvector(int* values, int& length) : m_values(values), m_length(length) {}
#endif

  int length() const { return m_length; }
  int lengthpp() { return m_length++; }
  void setLength(int length) { 
    assert(length <= m_capacity);
    m_length = length;
  }
  void resize(int length) { setLength(length); } // only for compatibility. FIXME: remove one method.
  int operator[] (int position) const { 
    assert(position >= 0);
    assert(position < m_length);
    return m_values[position]; 
  }
  void setElement(int position, int value) const { 
    assert(position >= 0);
    assert(position < m_capacity);
    m_values[position] = value; 
  }
  void push_back(int column) {
    assert(m_length < m_capacity);
    assert(m_length == 0 || column > m_values[m_length-1]); 
    m_values[m_length++] = column;
  }
  int* values() const { return m_values; }

  /*
#if DEBUG_LEVEL > 0
  void set(int* values, int length, int capacity) {
    m_values = values;
    m_length = length;
    m_capacity = capacity;
  }
#else
  void set(int* values, int length) {
    m_values = values;
    m_length = length;
  }
#endif
  */


  /*
   * There are three types of iterators:
   * (i)   iterator -- a read/write iterator for the elements 0..(size-1).
   * (ii)  const_iterator -- a read-only iterator for the elements 0..(size-1).
   * (iii) unbounded iterator -- a read/write iterator for the elements 0..(capacity-1). 
   * 
   * Methods begin/end of const objects automatically create const_iterators.
   *
   * unbounded iterators can be created by the methods beginUnbounded / endUnbounded.
   * 
   * unbounded iterators can be used for writing to a LightVector; when writing / filling the vector 
   * is finished, resizeToEndOf(iter) has to be called. 
   *
   * In debugging mode iterators check bounds, in production mode not. 
   */
#if DEBUG_LEVEL > 0
  // Define bounds checking iterators:
  class iterator {
  public:
    iterator(int* const values, int& size, int index) : m_values(values), m_size(size), m_index(index) {}
    int& operator* () const { 
      assert(m_index >= 0);
      assert(m_index < m_size);
      return m_values[m_index]; 
    }
    iterator& operator++ () { 
      assert(m_index < m_size);
      m_index++;
      return *this;
    }
    iterator operator++ (int) { 
      assert(m_index < m_size);
      iterator iter = *this;
      m_index++;
      return iter;
    }
    iterator& operator-- () { 
      assert(m_index > 0);
      m_index--;
      return *this;
    }
    iterator operator-- (int) { 
      assert(m_index > 0);
      iterator iter = *this;
      m_index--;
      return iter;
    }
    void operator+= (int index) {
      assert(m_index + index <= m_size);
      m_index += index;
    } 
    void operator-= (int index) {
      assert(m_index >= index);
      m_index -= index;
    } 
    bool operator!= (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index != iter.m_index;
    }
    bool operator== (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index == iter.m_index;
    }
    bool operator< (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index < iter.m_index;
    }
    bool operator<= (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index <= iter.m_index;
    }
    bool operator> (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index > iter.m_index;
    }
    bool operator>= (iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index >= iter.m_index;
    }
    int operator- (const iterator& iter) const { 
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index - iter.m_index;
    }
    iterator operator- (const int size) const { 
      assert(m_index - size >= 0);
      assert(m_index - size <= m_size);
      return iterator(m_values, m_size, m_index - size);
    }
    iterator operator+ (const int size) const { 
      assert(m_index + size >= 0);
      assert(m_index + size <= m_size);
      return iterator(m_values, m_size, m_index + size);
    }
    iterator operator= (iterator& iter) {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      m_index = iter.m_index;
      return *this;
    } 
    int index() const { return m_index; }
    // private:
    int * const m_values;
    int& m_size;
    int m_index;
  };

  class const_iterator {
  public:
    const_iterator(int const * const values, int& size, int index) : m_values(values), m_size(size), m_index(index) {}
    int operator* () const { 
      assert(m_index >= 0);
      assert(m_index < m_size);
      return m_values[m_index]; 
    }
    const_iterator& operator++ () { 
      assert(m_index < m_size);
      m_index++;
      return *this;
    }
    const_iterator operator++ (int) { 
      assert(m_index < m_size);
      const_iterator iter = *this;
      m_index++;
      return iter;
    }
    const_iterator& operator-- () { 
      assert(m_index > 0);
      m_index--;
      return *this;
    }
    const_iterator operator-- (int) { 
      assert(m_index > 0);
      const_iterator iter = *this;
      m_index--;
      return iter;
    }
    void operator-= (int index) {
      assert(m_index >= index);
      m_index -= index;
    } 
    void operator+= (int index) {
      assert(m_index + index <= m_size);
      m_index += index;
    } 
    bool operator!= (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index != iter.m_index;
    }
    bool operator== (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index == iter.m_index;
    }
    bool operator< (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index < iter.m_index;
    }
    bool operator<= (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index <= iter.m_index;
    }
    bool operator> (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index > iter.m_index;
    }
    bool operator>= (const_iterator& iter) const {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index >= iter.m_index;
    }
    int operator- (const const_iterator& iter) const { 
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      return m_index - iter.m_index;
    }
    const_iterator operator- (const int size) const { 
      assert(m_index - size >= 0);
      assert(m_index - size <= m_size);
      return const_iterator(m_values, m_size, m_index - size);
    }
    const_iterator operator+ (const int size) const { 
      assert(m_index + size >= 0);
      assert(m_index + size <= m_size);
      return const_iterator(m_values, m_size, m_index + size);
    }
    const_iterator operator= (const_iterator& iter) {
      assert(m_values == iter.m_values);
      assert(m_size == iter.m_size);
      m_index = iter.m_index;
      return *this;
    } 
    int index() const { return m_index; }
  private:
    int const * const m_values;
    int& m_size;
    int m_index;
  };

  iterator begin() { return iterator(m_values, m_length, 0); }
  iterator end() { return iterator(m_values, m_length, m_length); }
  const_iterator begin() const { return const_iterator(m_values, m_length, 0); }
  const_iterator end() const { return const_iterator(m_values, m_length, m_length); }
  iterator beginUnbounded() { return iterator(m_values, m_capacity, 0); }
  iterator endUnbounded() { return iterator(m_values, m_capacity, m_length); }

  void resizeToEndOf(iterator& iter) { resize(iter.index()); }
  void resizeToEndOf(const_iterator& iter) { resize(iter.index()); }

#else
  // Define non-bounds checkings, lightweight iterators: (stolen from Balazs)
  typedef int* iterator;
  typedef int const * const_iterator;

  iterator begin() { return m_values; }
  iterator end() { return m_values + m_length; }
  const_iterator begin() const { return m_values; }
  const_iterator end() const { return m_values + m_length; }
  iterator beginUnbounded() { return m_values; }
  iterator endUnbounded() { return m_values + m_length; }

  void resizeToEndOf(iterator& iter) { resize(iter - m_values); }
  void resizeToEndOf(const_iterator& iter) { resize(iter - m_values); }

#endif


#if DEBUG_LEVEL > 0
  int capacity() const {
    return m_capacity;
  }
#endif

private:
  int* const m_values;
  int& m_length;
#if DEBUG_LEVEL > 0
  int m_capacity;
#endif
};

ostream& operator<< (ostream& out, SparseBitvector const & vector);


// implementation detail: how to retrieve a reference to a row vector?
// - do not use SparseBitvector vector(matrix.getRow(row)) as this employs the copy constructor !
// - do not use capacities of SparseBitvectors in production code. (unnecessary overhead)
#if DEBUG_LEVEL > 0
#define GET_ROW(vector, matrix, row) SparseBitvector vector ( matrix .rowValues( row ), matrix .rowLength( row ), matrix .capacity( row ))
#else
#define GET_ROW(vector, matrix, row) SparseBitvector vector ( matrix .rowValues( row ), matrix .rowLength( row ))
#endif

#endif

---