tiny-bit-set.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Linnea Ingmar <linnea.ingmar@hotmail.com>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Linnea Ingmar, 2017
* Christian Schulte, 2017
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Int { namespace Extensional {
/*
* Tiny bit-set
*
*/
template<unsigned int sz>
forceinline
TinyBitSet<sz>::TinyBitSet(Space&, unsigned int n) {
assert(n <= sz);
for (unsigned int i=0U; i<n; i++)
_bits[i].init(true);
for (unsigned int i=n; i<sz; i++)
_bits[i].init(false);
}
template<unsigned int sz>
template<unsigned int largersz>
forceinline
TinyBitSet<sz>::TinyBitSet(Space&, const TinyBitSet<largersz>& sbs) {
GECODE_ASSUME(sz <= largersz);
assert(!sbs.empty());
for (unsigned int i=0U; i<sz; i++)
_bits[i] = sbs._bits[i];
assert(!empty());
}
template<unsigned int sz>
template<class IndexType>
forceinline
TinyBitSet<sz>::TinyBitSet(Space&, const BitSet<IndexType>& sbs) {
assert(sz == sbs.width());
assert(!sbs.empty());
for (unsigned int i=0U; i<sz; i++)
_bits[i].init(false);
for (unsigned int i=0U; i<sbs.words(); i++)
_bits[sbs._index[i]] = sbs._bits[i];
assert(!empty());
}
template<unsigned int sz>
forceinline void
TinyBitSet<sz>::clear_mask(BitSetData* mask) {
for (unsigned int i=0U; i<sz; i++) {
mask[i].init(false);
assert(mask[i].none());
}
}
template<unsigned int sz>
forceinline void
TinyBitSet<sz>::add_to_mask(const BitSetData* b, BitSetData* mask) const {
for (unsigned int i=0U; i<sz; i++)
mask[i] = BitSetData::o(mask[i],b[i]);
}
template<unsigned int sz>
template<bool sparse>
forceinline void
TinyBitSet<sz>::intersect_with_mask(const BitSetData* mask) {
for (unsigned int i=0U; i<sz; i++)
_bits[i] = BitSetData::a(_bits[i], mask[i]);
}
template<unsigned int sz>
forceinline void
TinyBitSet<sz>::intersect_with_masks(const BitSetData* a,
const BitSetData* b) {
for (unsigned int i=0U; i<sz; i++)
_bits[i] = BitSetData::a(_bits[i], BitSetData::o(a[i],b[i]));
}
template<unsigned int sz>
forceinline void
TinyBitSet<sz>::nand_with_mask(const BitSetData* b) {
for (unsigned int i=0U; i<sz; i++)
_bits[i] = BitSetData::a(_bits[i],~(b[i]));
}
template<unsigned int sz>
forceinline void
TinyBitSet<sz>::flush(void) {
for (unsigned int i=0U; i<sz; i++)
_bits[i].init(false);
assert(empty());
}
template<unsigned int sz>
forceinline bool
TinyBitSet<sz>::intersects(const BitSetData* b) {
for (unsigned int i=0U; i<sz; i++)
if (!BitSetData::a(_bits[i],b[i]).none())
return true;
return false;
}
template<unsigned int sz>
forceinline unsigned long long int
TinyBitSet<sz>::ones(const BitSetData* b) const {
unsigned long long int o = 0U;
for (unsigned int i=0U; i<sz; i++)
o += static_cast<unsigned long long int>
(BitSetData::a(_bits[i],b[i]).ones());
return o;
}
template<unsigned int sz>
forceinline unsigned long long int
TinyBitSet<sz>::ones(void) const {
unsigned long long int o = 0U;
for (unsigned int i=0U; i<sz; i++)
o += static_cast<unsigned long long int>(_bits[i].ones());
return o;
}
template<unsigned int sz>
forceinline unsigned long long int
TinyBitSet<sz>::bits(void) const {
return (static_cast<unsigned long long int>(sz) *
static_cast<unsigned long long int>(BitSetData::bpb));
}
template<unsigned int sz>
forceinline bool
TinyBitSet<sz>::empty(void) const { // Linear complexity...
for (unsigned int i=0U; i<sz; i++)
if (!_bits[i].none())
return false;
return true;
}
template<unsigned int sz>
forceinline unsigned int
TinyBitSet<sz>::width(void) const {
assert(!empty());
for (unsigned int i=sz; i--; )
if (!_bits[i].none())
return i+1U;
GECODE_NEVER;
return 0U;
}
template<unsigned int sz>
forceinline unsigned int
TinyBitSet<sz>::words(void) const {
return width();
}
template<unsigned int sz>
forceinline unsigned int
TinyBitSet<sz>::size(void) const {
return sz;
}
}}}
// STATISTICS: int-prop
Gecode::Int::Extensional::BitSet
Bit-set.
Definition extensional.hh:235
Gecode::Int::Extensional::BitSet::width
unsigned int width(void) const
Return the highest active index.
Definition bit-set.hpp:66
Gecode::Int::Extensional::BitSet::_bits
BitSetData * _bits
Words.
Definition extensional.hh:244
Gecode::Int::Extensional::BitSet::_index
IndexType * _index
Indices.
Definition extensional.hh:242
Gecode::Int::Extensional::BitSet::empty
bool empty(void) const
Check whether the set is empty.
Definition bit-set.hpp:48
Gecode::Int::Extensional::BitSet::words
unsigned int words(void) const
Return the number of required bit set words.
Definition bit-set.hpp:54
Gecode::Int::Extensional::TinyBitSet::intersect_with_mask
void intersect_with_mask(const BitSetData *mask)
Intersect with mask, sparse mask if sparse is true.
Definition tiny-bit-set.hpp:99
Gecode::Int::Extensional::TinyBitSet::words
unsigned int words(void) const
Return the number of required bit set words.
Definition tiny-bit-set.hpp:185
Gecode::Int::Extensional::TinyBitSet::width
unsigned int width(void) const
Return the highest active index.
Definition tiny-bit-set.hpp:173
Gecode::Int::Extensional::TinyBitSet::intersects
bool intersects(const BitSetData *b)
Check if has a non-empty intersection with the set.
Definition tiny-bit-set.hpp:129
Gecode::Int::Extensional::TinyBitSet::add_to_mask
void add_to_mask(const BitSetData *b, BitSetData *mask) const
Add to mask.
Definition tiny-bit-set.hpp:91
Gecode::Int::Extensional::TinyBitSet::bits
unsigned long long int bits(void) const
Return an upper bound on the number of bits.
Definition tiny-bit-set.hpp:157
Gecode::Int::Extensional::TinyBitSet::ones
unsigned long long int ones(void) const
Return the number of ones.
Definition tiny-bit-set.hpp:148
Gecode::Int::Extensional::TinyBitSet::size
unsigned int size(void) const
Return the total number of words.
Definition tiny-bit-set.hpp:191
Gecode::Int::Extensional::TinyBitSet::empty
bool empty(void) const
Check whether the set is empty.
Definition tiny-bit-set.hpp:164
Gecode::Int::Extensional::TinyBitSet::_bits
BitSetData _bits[_size]
Words.
Definition extensional.hh:306
Gecode::Int::Extensional::TinyBitSet::intersect_with_masks
void intersect_with_masks(const BitSetData *a, const BitSetData *b)
Intersect with the "or" of and b.
Definition tiny-bit-set.hpp:106
Gecode::Int::Extensional::TinyBitSet::flush
void flush(void)
Make the set empty.
Definition tiny-bit-set.hpp:121
Gecode::Int::Extensional::TinyBitSet::nand_with_mask
void nand_with_mask(const BitSetData *b)
Perform "nand" with b.
Definition tiny-bit-set.hpp:114
Gecode::Int::Extensional::TinyBitSet::clear_mask
void clear_mask(BitSetData *mask)
Clear the first limit words in mask.
Definition tiny-bit-set.hpp:82
Gecode::Int::Extensional::TinyBitSet::TinyBitSet
friend class TinyBitSet
Definition extensional.hh:303
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::BitSetData::bpb
static const unsigned int bpb
Bits per base.
Definition bitset-base.hpp:79
Gecode::Support::BitSetData::init
void init(bool setbits=false)
Initialize with all bits set if setbits.
Definition bitset-base.hpp:246
Gecode::Support::BitSetData::a
void a(BitSetData a)
Perform "and" with a.
Definition bitset-base.hpp:346
Gecode::Support::BitSetData::o
void o(BitSetData a)
Perform "or" with a.
Definition bitset-base.hpp:362
Gecode::Int::Extensional
Extensional propagators
Gecode::Int::Extensional::BitSetData
Gecode::Support::BitSetData BitSetData
Import type.
Definition extensional.hh:226
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56
GECODE_ASSUME
#define GECODE_ASSUME(p)
Assert certain property.
Definition macros.hpp:114