Parma_Polyhedra_Library::Bit_Row Class Reference
[C++ Language Interface]

A row in a matrix of bits. More...

#include <Bit_Row.defs.hh>

List of all members.

Public Member Functions

 Bit_Row ()
 Default constructor.
 Bit_Row (const Bit_Row &y)
 Copy-constructor.
 ~Bit_Row ()
 Destructor.
Bit_Rowoperator= (const Bit_Row &y)
 Assignment operator.
void swap (Bit_Row &y)
 Swaps *this with y.
bool operator[] (unsigned long k) const
 Returns the truth value corresponding to the bit in position k.
void set (unsigned long k)
 Sets the bit in position k.
void set_until (unsigned long k)
 Sets bits up to position k (excluded).
void clear (unsigned long k)
 Clears the bit in position k.
void clear_from (unsigned long k)
 Clears bits from position k (included) onward.
void clear ()
 Clears all the bits of the row.
unsigned long first () const
 Returns the index of the first set bit or ULONG_MAX if no bit is set.
unsigned long next (unsigned long position) const
 Returns the index of the first set bit after position or ULONG_MAX if no bit after position is set.
unsigned long last () const
 Returns the index of the last set bit or ULONG_MAX if no bit is set.
unsigned long prev (unsigned long position) const
 Returns the index of the first set bit before position or ULONG_MAX if no bits before position is set.
unsigned long count_ones () const
 Returns the number of set bits in the row.
bool empty () const
 Returns true if no bit is set in the row.
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
bool OK () const
 Checks if all the invariants are satisfied.

Static Private Member Functions

static unsigned int first_one (mp_limb_t w)
 Assuming w is nonzero, returns the index of the first set bit in w.
static unsigned int last_one (mp_limb_t w)
 Assuming w is nonzero, returns the index of the last set bit in w.

Private Attributes

mpz_t vec
 Bit-vector representing the row.

Friends

int compare (const Bit_Row &x, const Bit_Row &y)
 The basic comparison function.
bool operator== (const Bit_Row &x, const Bit_Row &y)
 Returns true if and only if x and y are equal.
bool operator!= (const Bit_Row &x, const Bit_Row &y)
 Returns true if and only if x and y are not equal.
bool subset_or_equal (const Bit_Row &x, const Bit_Row &y)
 Set-theoretic inclusion test.
bool subset_or_equal (const Bit_Row &x, const Bit_Row &y, bool &strict_subset)
 Set-theoretic inclusion test: sets strict_subset to a Boolean indicating whether the inclusion is strict or not.
bool strict_subset (const Bit_Row &x, const Bit_Row &y)
 Set-theoretic strict inclusion test.
void set_union (const Bit_Row &x, const Bit_Row &y, Bit_Row &z)
 Set-theoretic union.
void set_intersection (const Bit_Row &x, const Bit_Row &y, Bit_Row &z)
 Set-theoretic intersection.
void set_difference (const Bit_Row &x, const Bit_Row &y, Bit_Row &z)
 Set-theoretic difference.

Related Functions

(Note that these are not member functions.)

void swap (Parma_Polyhedra_Library::Bit_Row &x, Parma_Polyhedra_Library::Bit_Row &y)
 Specializes std::swap.
void iter_swap (std::vector< Parma_Polyhedra_Library::Bit_Row >::iterator x, std::vector< Parma_Polyhedra_Library::Bit_Row >::iterator y)
 Specializes std::iter_swap.


Detailed Description

A row in a matrix of bits.

Definition at line 111 of file Bit_Row.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Bit_Row::Bit_Row (  )  [inline]

Default constructor.

Definition at line 34 of file Bit_Row.inlines.hh.

References vec.

00034                  {
00035   mpz_init(vec);
00036 }

Parma_Polyhedra_Library::Bit_Row::Bit_Row ( const Bit_Row y  )  [inline]

Copy-constructor.

Definition at line 39 of file Bit_Row.inlines.hh.

References vec.

00039                                  {
00040   mpz_init_set(vec, y.vec);
00041 }

Parma_Polyhedra_Library::Bit_Row::~Bit_Row (  )  [inline]

Destructor.

Definition at line 44 of file Bit_Row.inlines.hh.

References vec.

00044                   {
00045   mpz_clear(vec);
00046 }


Member Function Documentation

Bit_Row & Parma_Polyhedra_Library::Bit_Row::operator= ( const Bit_Row y  )  [inline]

Assignment operator.

Definition at line 49 of file Bit_Row.inlines.hh.

References vec.

00049                                    {
00050   mpz_set(vec, y.vec);
00051   return *this;
00052 }

void Parma_Polyhedra_Library::Bit_Row::swap ( Bit_Row y  )  [inline]

Swaps *this with y.

Definition at line 81 of file Bit_Row.inlines.hh.

References vec.

Referenced by Parma_Polyhedra_Library::Bit_Matrix::add_row(), iter_swap(), and swap().

00081                         {
00082   mpz_swap(vec, y.vec);
00083 }

bool Parma_Polyhedra_Library::Bit_Row::operator[] ( unsigned long  k  )  const

Returns the truth value corresponding to the bit in position k.

Definition at line 205 of file Bit_Row.cc.

References vec.

00205                                                   {
00206   const mp_size_t vec_size = vec->_mp_size;
00207   assert(vec_size >= 0);
00208 
00209   unsigned long i = k / GMP_NUMB_BITS;
00210   if (i >= static_cast<unsigned long>(vec_size))
00211     return false;
00212 
00213   mp_limb_t limb = *(vec->_mp_d + i);
00214   return (limb >> (k % GMP_NUMB_BITS)) & 1;
00215 }

void Parma_Polyhedra_Library::Bit_Row::set ( unsigned long  k  )  [inline]

void Parma_Polyhedra_Library::Bit_Row::set_until ( unsigned long  k  ) 

Sets bits up to position k (excluded).

void Parma_Polyhedra_Library::Bit_Row::clear ( unsigned long  k  )  [inline]

void Parma_Polyhedra_Library::Bit_Row::clear_from ( unsigned long  k  )  [inline]

Clears bits from position k (included) onward.

Definition at line 65 of file Bit_Row.inlines.hh.

References vec.

00065                                          {
00066   mpz_tdiv_r_2exp(vec, vec, k);
00067 }

void Parma_Polyhedra_Library::Bit_Row::clear (  )  [inline]

Clears all the bits of the row.

Definition at line 86 of file Bit_Row.inlines.hh.

References vec.

00086                {
00087   mpz_set_ui(vec, 0UL);
00088 }

unsigned long Parma_Polyhedra_Library::Bit_Row::first (  )  const

Returns the index of the first set bit or ULONG_MAX if no bit is set.

Definition at line 103 of file Bit_Row.cc.

References first_one(), PPL_BITS_PER_GMP_LIMB, and vec.

00103                         {
00104   const mp_size_t vec_size = vec->_mp_size;
00105   assert(vec_size >= 0);
00106   mp_size_t li = 0;
00107   mp_srcptr p = vec->_mp_d;
00108   for (; li < vec_size; ++li, ++p) {
00109     const mp_limb_t limb = *p;
00110     if (limb != 0)
00111       return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
00112   }
00113   return ULONG_MAX;
00114 }

unsigned long Parma_Polyhedra_Library::Bit_Row::next ( unsigned long  position  )  const

Returns the index of the first set bit after position or ULONG_MAX if no bit after position is set.

Definition at line 117 of file Bit_Row.cc.

References first_one(), PPL_BITS_PER_GMP_LIMB, and vec.

00117                                              {
00118   ++position;
00119 
00120   // The alternative implementation using the mpz_scan1() function
00121   // of GMP was measured to be slower that ours.  Here it is, in
00122   // case mpz_scan1() is improved.
00123   //
00124   // unsigned long r = mpz_scan1(vec, position);
00125   // return (r == ULONG_MAX) ? -1 : r;
00126 
00127   mp_size_t li = position / PPL_BITS_PER_GMP_LIMB;
00128   const mp_size_t vec_size = vec->_mp_size;
00129   assert(vec_size >= 0);
00130   if (li >= vec_size)
00131     return ULONG_MAX;
00132 
00133   // Get the first limb.
00134   mp_srcptr p = vec->_mp_d + li;
00135 
00136   // Mask off any bits before `position' in the first limb.
00137   mp_limb_t limb = *p & (~(mp_limb_t) 0) << (position % PPL_BITS_PER_GMP_LIMB);
00138 
00139   while (true) {
00140     if (limb != 0)
00141       return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
00142     ++li;
00143     if (li == vec_size)
00144       break;
00145     ++p;
00146     limb = *p;
00147   }
00148   return ULONG_MAX;
00149 }

unsigned long Parma_Polyhedra_Library::Bit_Row::last (  )  const

Returns the index of the last set bit or ULONG_MAX if no bit is set.

Definition at line 152 of file Bit_Row.cc.

References last_one(), PPL_BITS_PER_GMP_LIMB, and vec.

Referenced by Parma_Polyhedra_Library::Bit_Matrix::OK().

00152                        {
00153   mp_size_t li = vec->_mp_size;
00154   assert(li >= 0);
00155   if (li == 0)
00156     return ULONG_MAX;
00157   --li;
00158   const mp_srcptr p = vec->_mp_d + li;
00159   const mp_limb_t limb = *p;
00160   assert(limb != 0);
00161   return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
00162 }

unsigned long Parma_Polyhedra_Library::Bit_Row::prev ( unsigned long  position  )  const

Returns the index of the first set bit before position or ULONG_MAX if no bits before position is set.

Definition at line 165 of file Bit_Row.cc.

References last_one(), PPL_BITS_PER_GMP_LIMB, and vec.

00165                                              {
00166   if (position == 0)
00167     return ULONG_MAX;
00168 
00169   --position;
00170 
00171   const mp_size_t vec_size = vec->_mp_size;
00172   assert(vec_size > 0);
00173   mp_size_t li = position / PPL_BITS_PER_GMP_LIMB;
00174 
00175   mp_limb_t limb;
00176   mp_srcptr p = vec->_mp_d;
00177 
00178   // Get the first limb.
00179   if (li >= vec_size) {
00180     li = vec_size - 1;
00181     p += li;
00182     limb = *p;
00183   }
00184   else {
00185     const mp_limb_t mask
00186       = (~(mp_limb_t) 0)
00187       >> (PPL_BITS_PER_GMP_LIMB - 1 - position % PPL_BITS_PER_GMP_LIMB);
00188     p += li;
00189     limb = *p & mask;
00190   }
00191 
00192   while (true) {
00193     if (limb != 0)
00194       return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
00195     if (li == 0)
00196       break;
00197     --li;
00198     --p;
00199     limb = *p;
00200   }
00201   return ULONG_MAX;
00202 }

unsigned long Parma_Polyhedra_Library::Bit_Row::count_ones (  )  const [inline]

Returns the number of set bits in the row.

Definition at line 70 of file Bit_Row.inlines.hh.

References vec.

Referenced by Parma_Polyhedra_Library::Polyhedron::conversion().

00070                           {
00071   assert(vec->_mp_size >= 0);
00072   return mpn_popcount(vec->_mp_d, vec->_mp_size);
00073 }

bool Parma_Polyhedra_Library::Bit_Row::empty (  )  const [inline]

Returns true if no bit is set in the row.

Definition at line 76 of file Bit_Row.inlines.hh.

References vec.

Referenced by Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().

00076                      {
00077   return mpz_sgn(vec) == 0;
00078 }

memory_size_type Parma_Polyhedra_Library::Bit_Row::total_memory_in_bytes (  )  const [inline]

Returns the total size in bytes of the memory occupied by *this.

Definition at line 96 of file Bit_Row.inlines.hh.

References external_memory_in_bytes().

00096                                      {
00097   return sizeof(*this) + external_memory_in_bytes();
00098 }

memory_size_type Parma_Polyhedra_Library::Bit_Row::external_memory_in_bytes (  )  const [inline]

Returns the size in bytes of the memory managed by *this.

Definition at line 91 of file Bit_Row.inlines.hh.

References vec.

Referenced by total_memory_in_bytes().

00091                                         {
00092   return vec[0]._mp_alloc * PPL_SIZEOF_MP_LIMB_T;
00093 }

bool Parma_Polyhedra_Library::Bit_Row::OK (  )  const

Checks if all the invariants are satisfied.

Definition at line 347 of file Bit_Row.cc.

References vec.

Referenced by Parma_Polyhedra_Library::Bit_Matrix::OK().

00347                      {
00348   const mp_size_t vec_size = vec->_mp_size;
00349   const mp_size_t vec_alloc = vec->_mp_alloc;
00350   return vec_size >= 0
00351     && vec_alloc >= vec_size
00352     && (vec_size == 0 || mpz_getlimbn(vec, vec_size-1) != 0);
00353 }

unsigned int Parma_Polyhedra_Library::Bit_Row::first_one ( mp_limb_t  w  )  [static, private]

Assuming w is nonzero, returns the index of the first set bit in w.

Definition at line 35 of file Bit_Row.cc.

Referenced by first(), and next().

00035                                  {
00036   unsigned int r = 0;
00037   w = w & -w;
00038 #if PPL_SIZEOF_MP_LIMB_T == 8
00039   if ((w & 0xffffffff) == 0) {
00040     w >>= 32;
00041     r += 32;
00042   }
00043 #elif PPL_SIZEOF_MP_LIMB_T != 4
00044 #error "Size of mp_limb_t not supported by Bit_Row::first_one(mp_limb_t w)."
00045 #endif
00046   if ((w & 0xffff) == 0) {
00047     w >>= 16;
00048     r += 16;
00049   }
00050   if ((w & 0xff) == 0) {
00051     w >>= 8;
00052     r += 8;
00053   }
00054   if (w & 0xf0)
00055     r += 4;
00056   if (w & 0xcc)
00057     r += 2;
00058   if (w & 0xaa)
00059     r += 1;
00060   return r;
00061 }

unsigned int Parma_Polyhedra_Library::Bit_Row::last_one ( mp_limb_t  w  )  [static, private]

Assuming w is nonzero, returns the index of the last set bit in w.

Definition at line 65 of file Bit_Row.cc.

Referenced by last(), and prev().

00065                                 {
00066   unsigned int r = 0;
00067 #if PPL_SIZEOF_MP_LIMB_T == 8
00068   if (w &
00069 #if PPL_SIZEOF_LONG == 8
00070       0xffffffff00000000
00071 #else
00072       0xffffffff00000000LL
00073 #endif
00074       ) {
00075     w >>= 32;
00076     r += 32;
00077   }
00078 #elif PPL_SIZEOF_MP_LIMB_T != 4
00079 #error "Size of mp_limb_t not supported by Bit_Row::last_one(mp_limb_t w)."
00080 #endif
00081   if (w & 0xffff0000) {
00082     w >>= 16;
00083     r += 16;
00084   }
00085   if (w & 0xff00) {
00086     w >>= 8;
00087     r += 8;
00088   }
00089   if (w & 0xf0) {
00090     w >>= 4;
00091     r += 4;
00092   }
00093   if (w & 0xc) {
00094     w >>= 2;
00095     r += 2;
00096   }
00097   if (w & 0x2)
00098     r += 1;
00099   return r;
00100 }


Friends And Related Function Documentation

int compare ( const Bit_Row x,
const Bit_Row y 
) [friend]

The basic comparison function.

Compares x with y starting from the least significant bits. The ordering is total and has the following property: if x and y are two rows seen as sets of naturals, if x is a strict subset of y, then x comes before y.

Returns

  • -1 if x comes before y in the ordering;
  • 0 if x and y are equal;
  • 1 if x comes after y in the ordering.

Definition at line 219 of file Bit_Row.cc.

00219                                                {
00220   const mp_size_t x_size = x.vec->_mp_size;
00221   assert(x_size >= 0);
00222   const mp_size_t y_size = y.vec->_mp_size;
00223   assert(y_size >= 0);
00224   mp_size_t size = (x_size > y_size ? y_size : x_size);
00225   mp_srcptr xp = x.vec->_mp_d;
00226   mp_srcptr yp = y.vec->_mp_d;
00227   while (size > 0) {
00228     const mp_limb_t xl = *xp;
00229     const mp_limb_t yl = *yp;
00230     if (xl != yl) {
00231       // Get the ones where they are different.
00232       const mp_limb_t diff = xl ^ yl;
00233       // First bit that is different.
00234       const mp_limb_t mask = diff & ~(diff-1);
00235       return (xl & mask) ? 1 : -1;
00236     }
00237     ++xp;
00238     ++yp;
00239     --size;
00240   }
00241   return x_size == y_size ? 0 : (x_size > y_size ? 1 : -1);
00242 }

bool operator== ( const Bit_Row x,
const Bit_Row y 
) [friend]

Returns true if and only if x and y are equal.

Definition at line 320 of file Bit_Row.cc.

00320                                                   {
00321   const mp_size_t x_vec_size = x.vec->_mp_size;
00322   assert(x_vec_size >= 0);
00323   const mp_size_t y_vec_size = y.vec->_mp_size;
00324   assert(y_vec_size >= 0);
00325 
00326   if (x_vec_size != y_vec_size)
00327     return false;
00328 
00329   return mpn_cmp(x.vec->_mp_d, y.vec->_mp_d, x_vec_size) == 0;
00330 }

bool operator!= ( const Bit_Row x,
const Bit_Row y 
) [friend]

Returns true if and only if x and y are not equal.

Definition at line 334 of file Bit_Row.cc.

00334                                                   {
00335   const mp_size_t x_vec_size = x.vec->_mp_size;
00336   assert(x_vec_size >= 0);
00337   const mp_size_t y_vec_size = y.vec->_mp_size;
00338   assert(y_vec_size >= 0);
00339 
00340   if (x_vec_size != y_vec_size)
00341     return true;
00342 
00343   return mpn_cmp(x.vec->_mp_d, y.vec->_mp_d, x_vec_size) != 0;
00344 }

bool subset_or_equal ( const Bit_Row x,
const Bit_Row y 
) [friend]

Set-theoretic inclusion test.

Definition at line 246 of file Bit_Row.cc.

00246                                                        {
00247   mp_size_t x_size = x.vec->_mp_size;
00248   assert(x_size >= 0);
00249   mp_size_t y_size = y.vec->_mp_size;
00250   assert(y_size >= 0);
00251   if (x_size > y_size)
00252     return false;
00253   mp_srcptr xp = x.vec->_mp_d;
00254   mp_srcptr yp = y.vec->_mp_d;
00255   while (x_size > 0) {
00256     if (*xp & ~*yp)
00257       return false;
00258     ++xp;
00259     ++yp;
00260     --x_size;
00261   }
00262   return true;
00263 }

bool subset_or_equal ( const Bit_Row x,
const Bit_Row y,
bool &  strict_subset 
) [friend]

Set-theoretic inclusion test: sets strict_subset to a Boolean indicating whether the inclusion is strict or not.

Definition at line 267 of file Bit_Row.cc.

00268                                           {
00269   mp_size_t x_size = x.vec->_mp_size;
00270   assert(x_size >= 0);
00271   mp_size_t y_size = y.vec->_mp_size;
00272   assert(y_size >= 0);
00273   if (x_size > y_size)
00274     return false;
00275   strict_subset = (x_size < y_size);
00276   mp_srcptr xp = x.vec->_mp_d;
00277   mp_srcptr yp = y.vec->_mp_d;
00278   while (x_size > 0) {
00279     const mp_limb_t xl = *xp;
00280     const mp_limb_t yl = *yp;
00281     if (xl & ~yl)
00282       return false;
00283     if (!strict_subset && xl != yl)
00284       strict_subset = true;
00285     ++xp;
00286     ++yp;
00287     --x_size;
00288   }
00289   return true;
00290 }

bool strict_subset ( const Bit_Row x,
const Bit_Row y 
) [friend]

Set-theoretic strict inclusion test.

Definition at line 294 of file Bit_Row.cc.

00294                                                      {
00295   mp_size_t x_size = x.vec->_mp_size;
00296   assert(x_size >= 0);
00297   mp_size_t y_size = y.vec->_mp_size;
00298   assert(y_size >= 0);
00299   if (x_size > y_size)
00300     return false;
00301   bool different = (x_size < y_size);
00302   mp_srcptr xp = x.vec->_mp_d;
00303   mp_srcptr yp = y.vec->_mp_d;
00304   while (x_size > 0) {
00305     const mp_limb_t xl = *xp;
00306     const mp_limb_t yl = *yp;
00307     if (xl & ~yl)
00308       return false;
00309     if (!different && xl != yl)
00310       different = true;
00311     ++xp;
00312     ++yp;
00313     --x_size;
00314   }
00315   return different;
00316 }

void set_union ( const Bit_Row x,
const Bit_Row y,
Bit_Row z 
) [friend]

Set-theoretic union.

Definition at line 111 of file Bit_Row.inlines.hh.

00111                                                           {
00112   mpz_ior(z.vec, x.vec, y.vec);
00113 }

void set_intersection ( const Bit_Row x,
const Bit_Row y,
Bit_Row z 
) [friend]

Set-theoretic intersection.

Definition at line 117 of file Bit_Row.inlines.hh.

00117                                                                  {
00118   mpz_and(z.vec, x.vec, y.vec);
00119 }

void set_difference ( const Bit_Row x,
const Bit_Row y,
Bit_Row z 
) [friend]

Set-theoretic difference.

Definition at line 123 of file Bit_Row.inlines.hh.

00123                                                                {
00124   DIRTY_TEMP0(mpz_class, complement_y);
00125   mpz_com(complement_y.get_mpz_t(), y.vec);
00126   mpz_and(z.vec, x.vec, complement_y.get_mpz_t());
00127 }

Specializes std::swap.

Definition at line 136 of file Bit_Row.inlines.hh.

References swap().

00137                                         {
00138   x.swap(y);
00139 }

void iter_swap ( std::vector< Parma_Polyhedra_Library::Bit_Row >::iterator  x,
std::vector< Parma_Polyhedra_Library::Bit_Row >::iterator  y 
) [related]

Specializes std::iter_swap.

Definition at line 143 of file Bit_Row.inlines.hh.

References swap().

00144                                                                {
00145   swap(*x, *y);
00146 }


Member Data Documentation

Bit-vector representing the row.

Definition at line 192 of file Bit_Row.defs.hh.

Referenced by Bit_Row(), clear(), clear_from(), count_ones(), empty(), external_memory_in_bytes(), first(), last(), next(), OK(), operator=(), operator[](), prev(), set(), swap(), and ~Bit_Row().


The documentation for this class was generated from the following files:

Generated on Sat Oct 11 10:41:06 2008 for PPL by  doxygen 1.5.6