bitmap.h

Go to the documentation of this file.

/*
  Copyright (C) 2004,2005 Fokko du Cloux
  part of the Atlas of Lie Groups and Representations

  For license information see the LICENSE file
*/

#ifndef BITMAP_H  /* guard against multiple inclusions */
#define BITMAP_H

#include <vector>
#include <cassert>

#include "bitmap_fwd.h"

#include "constants.h"

/******** type definitions **************************************************/

namespace atlas {

namespace bitmap {
class BitMap
{
  size_t d_capacity;
  std::vector<unsigned long> d_map;
  static unsigned long posBits;
  static unsigned long baseBits;
  static unsigned long baseShift;

 public:

// type definitions

  typedef unsigned long value_type;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef ptrdiff_t difference_type;
  typedef unsigned long size_type;

// iterators
  class iterator;
  typedef iterator const_iterator;
  iterator begin() const;
  iterator end() const;

// constructors and destructors
 BitMap() : d_capacity(0), d_map() {} // create a bitmap without capacity

  explicit BitMap(unsigned long n)
    : d_capacity(n), d_map((d_capacity+posBits)>>baseShift,0)
  {}

  BitMap(const BitMap& b) : d_capacity(b.d_capacity), d_map(b.d_map) {}

  // convert range defined by iterators into a BitMap
  template <typename I>
    BitMap(unsigned long n, const I& first, const I& last);

  // an easier version for a full vector
  template <typename U> // unsigned integral type
  BitMap(unsigned long n,const std::vector<U>& v)
    : d_capacity(n), d_map((d_capacity+posBits)>>baseShift)
  {
    for (size_t i=0; i<v.size(); ++i)
      insert(v[i]);
  }

  template <typename I, typename J>
    BitMap(const I& first, const I& last, const J& fsub, const J& lsub);


// assignment
  BitMap& operator= (const BitMap&);

// accessors
  unsigned long capacity() const { return d_capacity; }
  size_type size() const; // the number of bits that are set in the bitmap

  bool operator< (const BitMap& b) const { return d_map < b.d_map; }
  bool operator== (const BitMap& b) const { return d_map == b.d_map; }
  bool operator!=(const BitMap& b) const { return d_map != b.d_map; }

  bool empty() const; // whether |size()==0|
  bool full() const; // whether |size()==capacity()|

  bool isMember(unsigned long n) const
  {
    if (n >= d_capacity)
      return false;
    return (d_map[n >> baseShift] & constants::bitMask[n&posBits])!=0;
  }

  // Whether all elements of |b| satisfy |isMember|
  bool contains(const BitMap& b) const;

  // Whether none of the elements of |b| satisfy |isMember|
  bool disjoint(const BitMap& b) const;

  unsigned long n_th(unsigned long n) const;

  unsigned long position(unsigned long n) const;

  unsigned long front() const;

  // decrement |n| (at least once) until it points to a member
  // return value indicates whether this succeeded
  bool back_up(unsigned long& n) const;

  // get a range of bits as unsigned long value; see bitmap.ccp for details
  unsigned long range(unsigned long first, unsigned long number) const;

  BitMap operator& (const BitMap& other) const
  { BitMap result(*this); result&=other; return result; }

  BitMap operator| (const BitMap& other) const
  { BitMap result(*this); result|=other; return result; }

  BitMap operator^ (const BitMap& other) const
  { BitMap result(*this); result^=other; return result; }


// manipulators

  // WARNING: the following looks like an accessor, but complements |*this|
  BitMap& operator~ ();

 // these operators allow argument to have less capacity than |*this|
  bool operator&= (const BitMap&);

  BitMap& operator|= (const BitMap&);

  BitMap& operator^= (const BitMap&);

  BitMap& andnot(const BitMap& b); // remove bits of |b|

  BitMap& operator>>= (unsigned long delta); // shift right (decrease)
  BitMap& operator<<= (unsigned long delta); // shift left (increase)

  void insert(unsigned long n)
  {
    assert(n<d_capacity);
    d_map[n >> baseShift] |= constants::bitMask[n & posBits];
  }

  void remove(unsigned long n)
  {
    assert(n<d_capacity);
    d_map[n >> baseShift] &= ~constants::bitMask[n & posBits];
  }

  void set_to(unsigned long n,bool b)
  { if (b) insert(n); else remove(n); }

  void set_mod2(unsigned long n, unsigned long v) { set_to(n,(v&1)!=0); }

  void flip(unsigned long n)
  {
    assert(n<d_capacity);
    d_map[n >> baseShift] ^= constants::bitMask[n & posBits];
  }


 void fill(); // set all bits
 void reset() { d_map.assign(d_map.size(),0ul);  } // clear all bits
 void fill(size_t start,size_t stop); // set consecutive range of bits
 void clear(size_t start,size_t stop); // clear consecutive range of bits
 // insert a range of values (which need not be listed increasingly)
 template<typename I>
   void insert(I, I);

 // this was called |resize|, but sets |capacity()|, whence the new name
 void set_capacity(unsigned long n); // any new bits will start out cleared
 void extend_capacity(bool b); // extend capacity by |1|, adding member if |b|

 // set an interval of bits from those (least significant ones) of source
 void setRange(unsigned long start, unsigned long amount, unsigned long source);

 void swap(BitMap&);

}; // |class BitMap|



class BitMap::iterator // is really a const_iterator
{
  std::vector<unsigned long>::const_iterator d_chunk; // point to current chunk
  unsigned long d_bitAddress; // value returned if dereferenced
  unsigned long d_capacity; // beyond-the-end bit-address, normally constant

 public:

// associated types
  typedef std::forward_iterator_tag iterator_category;
  typedef unsigned long value_type;
  typedef ptrdiff_t difference_type;
  typedef const value_type* pointer;
  typedef const value_type& reference;

// constructors and destructors
  iterator() {}

  iterator(const iterator &j):d_chunk(j.d_chunk), d_bitAddress(j.d_bitAddress),
    d_capacity(j.d_capacity) {}

  iterator(const std::vector<unsigned long>::const_iterator& p,
       unsigned long n, unsigned long c)
    :d_chunk(p), d_bitAddress(n), d_capacity(c) {}

// assignment
  iterator& operator= (const iterator& i);

// accessors
  bool operator== (const iterator& i) const
    { return d_bitAddress == i.d_bitAddress; } //  |d_chunk| is ignored!
  bool operator!= (const iterator& i) const
    { return d_bitAddress != i.d_bitAddress; } //  |d_chunk| is ignored!
  bool operator() () const { return d_bitAddress != d_capacity; }

  const value_type& operator* () const { return d_bitAddress; }

// manipulators
  iterator& operator++ ();

  iterator operator++ (int);

  void change_owner(const BitMap& b); // adapt |d_chunk| to point into |b|
}; // |class BitMap::iterator|

} // |namespace bitmap|

} // |namespace atlas|

#endif