#include <Bit_Row.defs.hh>
Public Member Functions | |
Bit_Row () | |
Default constructor. | |
Bit_Row (const Bit_Row &y) | |
Copy-constructor. | |
~Bit_Row () | |
Destructor. | |
Bit_Row & | operator= (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 . |
Definition at line 111 of file Bit_Row.defs.hh.
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 }
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] |
Sets the bit in position k
.
Definition at line 55 of file Bit_Row.inlines.hh.
References vec.
Referenced by Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), Parma_Polyhedra_Library::BD_Shape< T >::shortest_path_reduction_assign(), Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().
00055 { 00056 mpz_setbit(vec, k); 00057 }
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] |
Clears the bit in position k
.
Definition at line 60 of file Bit_Row.inlines.hh.
References vec.
Referenced by Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), Parma_Polyhedra_Library::BD_Shape< T >::shortest_path_reduction_assign(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().
00060 { 00061 mpz_clrbit(vec, k); 00062 }
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.
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 }
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
x
comes before y
in the ordering;x
and y
are equal;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 }
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 }
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 }
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 }
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 }
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 }
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 }
void swap | ( | Parma_Polyhedra_Library::Bit_Row & | x, | |
Parma_Polyhedra_Library::Bit_Row & | y | |||
) | [related] |
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 }
mpz_t Parma_Polyhedra_Library::Bit_Row::vec [private] |
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().