tuple-set.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2007
* 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.
*
*/
#include <sstream>
namespace Gecode {
/*
* Ranges
*
*/
forceinline unsigned int
TupleSet::Range::width(void) const {
return static_cast<unsigned int>(max - min + 1);
}
forceinline const TupleSet::BitSetData*
TupleSet::Range::supports(unsigned int n_words, int n) const {
assert((min <= n) && (n <= max));
return s + n_words * static_cast<unsigned int>(n - min);
}
/*
* Tuple set data
*
*/
forceinline
TupleSet::Data::Data(int a)
: arity(a), n_words(0U), // To be initialized in finalize
n_tuples(0), n_free(n_initial_free),
min(Int::Limits::max), max(Int::Limits::min), key(0),
td(heap.alloc<int>(n_initial_free * a)),
vd(heap.alloc<ValueData>(a)),
range(nullptr), support(nullptr) {
}
forceinline bool
TupleSet::Data::finalized(void) const {
return n_free < 0;
}
forceinline TupleSet::Tuple
TupleSet::Data::add(void) {
if (n_free == 0)
resize();
assert(n_free > 0);
n_free--;
Tuple t = td + n_tuples*arity;
n_tuples++;
return t;
}
forceinline TupleSet::Tuple
TupleSet::Data::get(int i) const {
assert((i >= 0) && (i < n_tuples));
return td + i*arity;
}
forceinline unsigned int
TupleSet::ValueData::start(int k) const {
if (n > 1U) {
unsigned int l=0U, h=n-1U;
while (true) {
assert(l<=h);
unsigned int m = l + ((h-l) >> 1);
if (k < r[m].min)
h=m-1U;
else if (k > r[m].max)
l=m+1U;
else
return m;
}
GECODE_NEVER;
} else {
return 0U;
}
}
forceinline void
TupleSet::Data::set(BitSetData* d, unsigned int i) {
d[i / BitSetData::bpb].set(i % BitSetData::bpb);
}
forceinline bool
TupleSet::Data::get(const BitSetData* d, unsigned int i) {
return d[i / BitSetData::bpb].get(i % BitSetData::bpb);
}
forceinline unsigned int
TupleSet::Data::tuple2idx(Tuple t) const {
return static_cast<unsigned int>((t - td) / static_cast<unsigned int>(arity));
}
forceinline const TupleSet::Range*
TupleSet::Data::fst(int i) const {
return &vd[i].r[0];
}
forceinline const TupleSet::Range*
TupleSet::Data::lst(int i) const {
return &vd[i].r[vd[i].n-1U];
}
/*
* Tuple set
*
*/
forceinline TupleSet&
TupleSet::add(const IntArgs& t) {
_add(t); return *this;
}
forceinline
TupleSet::TupleSet(void) {}
forceinline
TupleSet::operator bool(void) const {
return object() != nullptr;
}
forceinline void
TupleSet::finalize(void) {
Data* d = static_cast<Data*>(object());
if (!d->finalized())
d->finalize();
}
forceinline bool
TupleSet::finalized(void) const {
return static_cast<Data*>(object())->finalized();
}
forceinline TupleSet::Data&
TupleSet::data(void) const {
assert(finalized());
return *static_cast<Data*>(object());
}
forceinline TupleSet::Data&
TupleSet::raw(void) const {
return *static_cast<Data*>(object());
}
forceinline bool
TupleSet::operator !=(const TupleSet& t) const {
return !(*this == t);
}
forceinline int
TupleSet::arity(void) const {
return raw().arity;
}
forceinline int
TupleSet::tuples(void) const {
return raw().n_tuples;
}
forceinline unsigned int
TupleSet::words(void) const {
return data().n_words;
}
forceinline int
TupleSet::min(void) const {
return data().min;
}
forceinline int
TupleSet::max(void) const {
return data().max;
}
forceinline TupleSet::Tuple
TupleSet::operator [](int i) const {
return data().get(i);
}
forceinline const TupleSet::Range*
TupleSet::fst(int i) const {
return data().fst(i);
}
forceinline const TupleSet::Range*
TupleSet::lst(int i) const {
return data().lst(i);
}
forceinline bool
TupleSet::operator ==(const TupleSet& t) const {
if (tuples() != t.tuples())
return false;
if (arity() != t.arity())
return false;
if (min() != t.min())
return false;
if (max() != t.max())
return false;
return equal(t);
}
forceinline std::size_t
TupleSet::hash(void) const {
return data().key;
}
template<class Char, class Traits>
std::basic_ostream<Char,Traits>&
operator <<(std::basic_ostream<Char,Traits>& os, const TupleSet& ts) {
std::basic_ostringstream<Char,Traits> s;
s.copyfmt(os); s.width(0);
s << "Number of tuples: " << ts.tuples()
<< " (number of words: " << ts.words() << " with "
<< Support::BitSetData::bpb << " bits)" << std::endl;
for (int a=0; a < ts.arity(); a++) {
unsigned int size = 0U;
for (const TupleSet::Range* c=ts.fst(a); c<=ts.lst(a); c++)
size += c->width();
s << "\t[" << a << "] size: " << size
<< ", width: "
<< static_cast<unsigned int>(ts.lst(a)->max - ts.fst(a)->min + 1)
<< ", ranges: "
<< (ts.lst(a) - ts.fst(a) + 1U)
<< std::endl;
}
return os << s.str();
}
/*
* Range iterator
*
*/
forceinline
TupleSet::Ranges::Ranges(const TupleSet& ts, int i) {
c = &(ts.data().vd[i].r[0]);
l = c + ts.data().vd[i].n;
}
forceinline bool
TupleSet::Ranges::operator ()(void) const {
return c<l;
}
forceinline void
TupleSet::Ranges::operator ++(void) {
c++;
}
forceinline int
TupleSet::Ranges::min(void) const {
return c->min;
}
forceinline int
TupleSet::Ranges::max(void) const {
return c->max;
}
forceinline unsigned int
TupleSet::Ranges::width(void) const {
return c->width();
}
}
// STATISTICS: int-prop
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
Gecode::Support::BitSetData::bpb
static const unsigned int bpb
Bits per base.
Definition bitset-base.hpp:79
Gecode::TupleSet::Data
Data stored for a Table.
Definition int.hh:2229
Gecode::TupleSet::Data::max
int max
Largest value.
Definition int.hh:2245
Gecode::TupleSet::Data::n_free
int n_free
Number of free tuple entries of arity.
Definition int.hh:2241
Gecode::TupleSet::Data::resize
void resize(void)
Resize tuple data.
Definition tuple-set.cpp:247
Gecode::TupleSet::Data::support
BitSetData * support
Pointer to all support data.
Definition int.hh:2255
Gecode::TupleSet::Data::Data
Data(int a)
Initialize as empty tuple set with arity a.
Definition tuple-set.hpp:61
Gecode::TupleSet::Data::n_words
unsigned int n_words
Number of words for support.
Definition int.hh:2237
Gecode::TupleSet::Data::min
int min
Smallest value.
Definition int.hh:2243
Gecode::TupleSet::Data::set
static void set(BitSetData *d, unsigned int n)
Set bit n in bitset data d.
Definition tuple-set.hpp:113
Gecode::TupleSet::Data::arity
int arity
Arity.
Definition int.hh:2235
Gecode::TupleSet::Data::n_tuples
int n_tuples
Number of Tuples.
Definition int.hh:2239
Gecode::TupleSet::Data::get
Tuple get(int i) const
Return tuple with number i.
Definition tuple-set.hpp:87
Gecode::TupleSet::Data::td
int * td
Tuple data.
Definition int.hh:2249
Gecode::TupleSet::Data::tuple2idx
unsigned int tuple2idx(Tuple t) const
Map tuple address to index.
Definition tuple-set.hpp:123
Gecode::TupleSet::Data::range
Range * range
Pointer to all ranges.
Definition int.hh:2253
Gecode::TupleSet::Data::lst
const Range * lst(int i) const
Return last range for position i.
Definition tuple-set.hpp:132
Gecode::TupleSet::Data::finalized
bool finalized(void) const
Is datastructure finalized.
Definition tuple-set.hpp:71
Gecode::TupleSet::Data::vd
ValueData * vd
Value data.
Definition int.hh:2251
Gecode::TupleSet::Data::fst
const Range * fst(int i) const
Return first range for position i.
Definition tuple-set.hpp:128
Gecode::TupleSet::Data::n_initial_free
static const int n_initial_free
Initial number of free tuples.
Definition int.hh:2232
Gecode::TupleSet::Data::key
std::size_t key
Hash key.
Definition int.hh:2247
Gecode::TupleSet::Data::add
Tuple add(void)
Return newly added tuple.
Definition tuple-set.hpp:76
Gecode::TupleSet::Range
Range information.
Definition int.hh:2201
Gecode::TupleSet::Range::s
BitSetData * s
Begin of supports.
Definition int.hh:2208
Gecode::TupleSet::Range::width
unsigned int width(void) const
Return the width.
Definition tuple-set.hpp:45
Gecode::TupleSet::Range::max
int max
Maximum value.
Definition int.hh:2206
Gecode::TupleSet::Range::min
int min
Minimum value.
Definition int.hh:2204
Gecode::TupleSet::Range::supports
const BitSetData * supports(unsigned int n_words, int n) const
Return the supports for value n.
Definition tuple-set.hpp:50
Gecode::TupleSet::Ranges::operator()
bool operator()(void) const
Test whether iterator is still at a range.
Definition tuple-set.hpp:266
Gecode::TupleSet::Ranges::Ranges
Ranges(const TupleSet &ts, int i)
Initialize for column i.
Definition tuple-set.hpp:260
Gecode::TupleSet::Ranges::max
int max(void) const
Return largest value of range.
Definition tuple-set.hpp:279
Gecode::TupleSet::Ranges::l
const Range * l
Last range.
Definition int.hh:2364
Gecode::TupleSet::Ranges::min
int min(void) const
Return smallest value of range.
Definition tuple-set.hpp:275
Gecode::TupleSet::Ranges::operator++
void operator++(void)
Move iterator to next range (if possible).
Definition tuple-set.hpp:270
Gecode::TupleSet::Ranges::c
const Range * c
Current range.
Definition int.hh:2362
Gecode::TupleSet::Ranges::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
Definition tuple-set.hpp:283
Gecode::TupleSet::ValueData
Data about values in the table.
Definition int.hh:2216
Gecode::TupleSet::ValueData::start
unsigned int start(int n) const
Find start range for value n.
Definition tuple-set.hpp:93
Gecode::TupleSet::ValueData::n
unsigned int n
Number of ranges.
Definition int.hh:2219
Gecode::TupleSet::ValueData::r
Range * r
Ranges.
Definition int.hh:2221
Gecode::TupleSet
Class represeting a set of tuples.
Definition int.hh:2191
Gecode::TupleSet::TupleSet
TupleSet(void)
Construct an unitialized tuple set.
Definition tuple-set.hpp:147
Gecode::TupleSet::_add
void _add(const IntArgs &t)
Add tuple t to tuple set.
Definition tuple-set.cpp:460
Gecode::TupleSet::tuples
int tuples(void) const
Number of tuples.
Definition tuple-set.hpp:185
Gecode::TupleSet::max
int max(void) const
Return maximal value in all tuples.
Definition tuple-set.hpp:197
Gecode::TupleSet::operator!=
bool operator!=(const TupleSet &t) const
Test whether tuple set is different from t.
Definition tuple-set.hpp:177
Gecode::TupleSet::finalized
bool finalized(void) const
Is tuple set finalized.
Definition tuple-set.hpp:162
Gecode::TupleSet::add
TupleSet & add(const IntArgs &t)
Add tuple t to tuple set.
Definition tuple-set.hpp:142
Gecode::TupleSet::operator==
bool operator==(const TupleSet &t) const
Test whether tuple set is equal to t.
Definition tuple-set.hpp:214
Gecode::TupleSet::operator<<
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const TupleSet &ts)
Definition tuple-set.hpp:234
Gecode::TupleSet::operator[]
Tuple operator[](int i) const
Get tuple i.
Definition tuple-set.hpp:201
Gecode::TupleSet::lst
const Range * lst(int i) const
Return last range for position i.
Definition tuple-set.hpp:209
Gecode::TupleSet::Tuple
int * Tuple
Type of a tuple.
Definition int.hh:2197
Gecode::TupleSet::hash
std::size_t hash(void) const
Return hash key.
Definition tuple-set.hpp:227
Gecode::TupleSet::finalize
void finalize(void)
Finalize tuple set.
Definition tuple-set.hpp:155
Gecode::TupleSet::equal
bool equal(const TupleSet &t) const
Test whether tuple set is equal to t.
Definition tuple-set.cpp:447
Gecode::TupleSet::fst
const Range * fst(int i) const
Return first range for position i.
Definition tuple-set.hpp:205
Gecode::TupleSet::words
unsigned int words(void) const
Return number of required bit set words.
Definition tuple-set.hpp:189
Gecode::TupleSet::min
int min(void) const
Return minimal value in all tuples.
Definition tuple-set.hpp:193
Gecode::TupleSet::raw
Data & raw(void) const
Get raw data (must be initialized).
Definition tuple-set.hpp:172
Gecode::TupleSet::BitSetData
Gecode::Support::BitSetData BitSetData
Import bit set data type.
Definition int.hh:2199
Gecode::TupleSet::data
Data & data(void) const
Get data (must be initialized and finalized).
Definition tuple-set.hpp:167
Gecode::TupleSet::arity
int arity(void) const
Arity of tuple set.
Definition tuple-set.hpp:181
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Int::Limits
Numerical limits for integer variables.
Definition int.hh:114
Gecode::Int
Finite domain integers.
Gecode
Gecode toplevel namespace
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
forceinline
#define forceinline
Definition config.hpp:187
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56