tuple-set.cpp
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>
* Mikael Lagerkvist <lagerkvist@gecode.org>
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Linnea Ingmar, 2017
* 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 <gecode/int.hh>
#include <algorithm>
namespace Gecode { namespace Int { namespace Extensional {
typedef ::Gecode::TupleSet::Tuple Tuple;
class TupleCompare {
private:
int arity;
public:
TupleCompare(int a);
bool operator ()(const Tuple& a, const Tuple& b);
};
class PosCompare {
private:
int p;
public:
PosCompare(int p);
bool operator ()(const Tuple& a, const Tuple& b);
};
forceinline
TupleCompare::TupleCompare(int a) : arity(a) {}
forceinline bool
TupleCompare::operator ()(const Tuple& a, const Tuple& b) {
for (int i=0; i<arity; i++)
if (a[i] < b[i])
return true;
else if (a[i] > b[i])
return false;
return false;
}
forceinline
PosCompare::PosCompare(int p0) : p(p0) {}
forceinline bool
PosCompare::operator ()(const Tuple& a, const Tuple& b) {
return a[p] < b[p];
}
}}}
namespace Gecode {
/*
* Tuple set data
*
*/
void
TupleSet::Data::finalize(void) {
using namespace Int::Extensional;
assert(!finalized());
// Mark as finalized
n_free = -1;
// Initialization
if (n_tuples == 0) {
delete td; td=nullptr;
return;
}
// Compact and copy data
Region r;
// Set up tuple pointers
Tuple* tuple = r.alloc<Tuple>(n_tuples);
{
for (int t=0; t<n_tuples; t++)
tuple[t] = td + t*arity;
TupleCompare tc(arity);
Support::quicksort(tuple, n_tuples, tc);
// Remove duplicates
int j=1;
for (int t=1; t<n_tuples; t++) {
for (int a=0; a<arity; a++)
if (tuple[t-1][a] != tuple[t][a])
goto notsame;
goto same;
notsame: ;
tuple[j++] = tuple[t];
same: ;
}
assert(j <= n_tuples);
n_tuples=j;
// Initialize hash key
key = static_cast<std::size_t>(n_tuples);
cmb_hash(key, arity);
// Copy into now possibly smaller area
int* new_td = heap.alloc<int>(n_tuples*arity);
for (int t=0; t<n_tuples; t++) {
for (int a=0; a<arity; a++) {
new_td[t*arity+a] = tuple[t][a];
cmb_hash(key,tuple[t][a]);
}
tuple[t] = new_td + t*arity;
}
heap.rfree(td);
td = new_td;
}
// Only now compute how many tuples are needed!
n_words = BitSetData::data(static_cast<unsigned int>(n_tuples));
// Compute range information
{
/*
* Pass one: compute how many values and ranges are needed
*/
// How many values
unsigned int n_vals = 0U;
// How many ranges
unsigned int n_ranges = 0U;
for (int a=0; a<arity; a++) {
// Sort tuple according to position
PosCompare pc(a);
Support::quicksort(tuple, n_tuples, pc);
// Scan values
{
int max=tuple[0][a];
n_vals++; n_ranges++;
for (int i=1; i<n_tuples; i++) {
assert(tuple[i-1][a] <= tuple[i][a]);
if (max+1 == tuple[i][a]) {
n_vals++;
max=tuple[i][a];
} else if (max+1 < tuple[i][a]) {
n_vals++; n_ranges++;
max=tuple[i][a];
} else {
assert(max == tuple[i][a]);
}
}
}
}
/*
* Pass 2: allocate memory and fill data structures
*/
// Allocate memory for ranges
Range* cr = range = heap.alloc<Range>(n_ranges);
// Allocate and initialize memory for supports
BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
for (unsigned int i=0; i<n_vals * n_words; i++)
cs[i].init();
for (int a=0; a<arity; a++) {
// Set range pointer
vd[a].r = cr;
// Sort tuple according to position
PosCompare pc(a);
Support::quicksort(tuple, n_tuples, pc);
// Update min and max
min = std::min(min,tuple[0][a]);
max = std::max(max,tuple[n_tuples-1][a]);
// Compress into non-overlapping ranges
{
unsigned int j=0U;
vd[a].r[0].max=vd[a].r[0].min=tuple[0][a];
for (int i=1; i<n_tuples; i++) {
assert(tuple[i-1][a] <= tuple[i][a]);
if (vd[a].r[j].max+1 == tuple[i][a]) {
vd[a].r[j].max=tuple[i][a];
} else if (vd[a].r[j].max+1 < tuple[i][a]) {
j++; vd[a].r[j].min=vd[a].r[j].max=tuple[i][a];
} else {
assert(vd[a].r[j].max == tuple[i][a]);
}
}
vd[a].n = j+1U;
cr += j+1U;
}
// Set support pointer and set bits
for (unsigned int i=0U; i<vd[a].n; i++) {
vd[a].r[i].s = cs;
cs += n_words * vd[a].r[i].width();
}
{
int j=0;
for (int i=0; i<n_tuples; i++) {
while (tuple[i][a] > vd[a].r[j].max)
j++;
set(const_cast<BitSetData*>
(vd[a].r[j].supports(n_words,tuple[i][a])),
tuple2idx(tuple[i]));
}
}
}
assert(cs == support + n_words * n_vals);
assert(cr == range + n_ranges);
}
if ((min < Int::Limits::min) || (max > Int::Limits::max))
throw Int::OutOfLimits("TupleSet::finalize()");
assert(finalized());
}
void
TupleSet::Data::resize(void) {
assert(n_free == 0);
int n = static_cast<int>(1+n_tuples*1.5);
td = heap.realloc<int>(td, n_tuples * arity, n * arity);
n_free = n - n_tuples;
}
TupleSet::Data::~Data(void) {
heap.rfree(td);
heap.rfree(vd);
heap.rfree(range);
heap.rfree(support);
}
/*
* Tuple set
*
*/
TupleSet::TupleSet(int a)
: SharedHandle(new Data(a)) {}
void
TupleSet::init(int a) {
object(new Data(a));
}
TupleSet::TupleSet(const TupleSet& ts)
: SharedHandle(ts) {}
TupleSet&
TupleSet::operator =(const TupleSet& ts) {
(void) SharedHandle::operator =(ts);
return *this;
}
TupleSet::TupleSet(int a, const Gecode::DFA& dfa) {
struct Edge {
int i_state;
int o_state;
};
struct State {
int i_deg;
int o_deg;
int n_tuples;
int* tuples;
};
struct Support {
int val;
int n_edges;
Edge* edges;
};
struct Layer {
State* states;
Support* supports;
int n_supports;
};
// Initialize
object(new Data(a));
Region r;
// Number of states
int max_states = dfa.n_states();
// Allocate memory for all layers and states
Layer* layers = r.alloc<Layer>(a+1);
State* states = r.alloc<State>(max_states*(a+1));
for (int i=0; i<max_states*(a+1); i++) {
states[i].i_deg = 0; states[i].o_deg = 0;
states[i].n_tuples = 0;
states[i].tuples = nullptr;
}
for (int i=0; i<a+1; i++) {
layers[i].states = states + i*max_states;
layers[i].n_supports = 0;
}
// Mark initial state as being reachable
layers[0].states[0].i_deg = 1;
layers[0].states[0].n_tuples = 1;
layers[0].states[0].tuples = r.alloc<int>(1);
assert(layers[0].states[0].tuples != nullptr);
// Allocate temporary memory for edges and supports
Edge* edges = r.alloc<Edge>(dfa.max_degree());
Support* supports = r.alloc<Support>(dfa.n_symbols());
// Forward pass: accumulate
for (int i=0; i<a; i++) {
int n_supports=0;
for (DFA::Symbols s(dfa); s(); ++s) {
int n_edges=0;
for (DFA::Transitions t(dfa,s.val()); t(); ++t) {
if (layers[i].states[t.i_state()].i_deg != 0) {
// Create edge
edges[n_edges].i_state = t.i_state();
edges[n_edges].o_state = t.o_state();
n_edges++;
// Adjust degrees
layers[i].states[t.i_state()].o_deg++;
layers[i+1].states[t.o_state()].i_deg++;
// Adjust number of tuples
layers[i+1].states[t.o_state()].n_tuples
+= layers[i].states[t.i_state()].n_tuples;
}
assert(n_edges <= dfa.max_degree());
}
// Found a support for the value
if (n_edges > 0) {
Support& support = supports[n_supports++];
support.val = s.val();
support.n_edges = n_edges;
support.edges = Heap::copy(r.alloc<Edge>(n_edges),edges,n_edges);
}
}
// Create supports
if (n_supports > 0) {
layers[i].supports =
Heap::copy(r.alloc<Support>(n_supports),supports,n_supports);
layers[i].n_supports = n_supports;
} else {
finalize();
return;
}
}
// Mark final states as being reachable
for (int s=dfa.final_fst(); s<dfa.final_lst(); s++) {
if (layers[a].states[s].i_deg != 0U)
layers[a].states[s].o_deg = 1U;
}
// Backward pass: validate
for (int i=a; i--; ) {
for (int j = layers[i].n_supports; j--; ) {
Support& s = layers[i].supports[j];
for (int k = s.n_edges; k--; ) {
int i_state = s.edges[k].i_state;
int o_state = s.edges[k].o_state;
// State is unreachable
if (layers[i+1].states[o_state].o_deg == 0) {
// Adjust degree
--layers[i+1].states[o_state].i_deg;
--layers[i].states[i_state].o_deg;
// Remove edge
assert(s.n_edges > 0);
s.edges[k] = s.edges[--s.n_edges];
}
}
// Lost support
if (s.n_edges == 0)
layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
}
if (layers[i].n_supports == 0U) {
finalize();
return;
}
}
// Generate tuples
for (int i=0; i<a; i++) {
for (int j = layers[i].n_supports; j--; ) {
Support& s = layers[i].supports[j];
for (int k = s.n_edges; k--; ) {
int i_state = s.edges[k].i_state;
int o_state = s.edges[k].o_state;
// Allocate memory for tuples if not done
if (layers[i+1].states[o_state].tuples == nullptr) {
int n_tuples = layers[i+1].states[o_state].n_tuples;
layers[i+1].states[o_state].tuples = r.alloc<int>((i+1)*n_tuples);
layers[i+1].states[o_state].n_tuples = 0;
}
int n = layers[i+1].states[o_state].n_tuples;
// Write tuples
for (int t=0; t < layers[i].states[i_state].n_tuples; t++) {
// Copy the first i number of digits from the previous layer
Heap::copy(&layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)],
&layers[i].states[i_state].tuples[t*i], i);
// Write the last digit
layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
}
layers[i+1].states[o_state].n_tuples
+= layers[i].states[i_state].n_tuples;
}
}
}
// Add tuples to tuple set
for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
for (int i=0; i<layers[a].states[s].n_tuples; i++) {
int* tuple = &layers[a].states[s].tuples[i*a];
add(IntArgs(a,tuple));
}
}
finalize();
}
bool
TupleSet::equal(const TupleSet& t) const {
assert(tuples() == t.tuples());
assert(arity() == t.arity());
assert(min() == t.min());
assert(max() == t.max());
for (int i=0; i<tuples(); i++)
for (int j=0; j<arity(); j++)
if ((*this)[i][j] != t[i][j])
return false;
return true;
}
void
TupleSet::_add(const IntArgs& t) {
if (!*this)
throw Int::UninitializedTupleSet("TupleSet::add()");
if (raw().finalized())
throw Int::AlreadyFinalized("TupleSet::add()");
if (t.size() != raw().arity)
throw Int::ArgumentSizeMismatch("TupleSet::add()");
Tuple a = raw().add();
for (int i=0; i<t.size(); i++)
a[i]=t[i];
}
}
// STATISTICS: int-prop
Gecode::ArgArrayBase::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1607
Gecode::DFA::Symbols
Iterator for DFA symbols.
Definition int.hh:2092
Gecode::DFA::Transitions
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2069
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2049
Gecode::DFA::max_degree
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
Gecode::DFA::n_states
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
Gecode::DFA::final_lst
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
Gecode::DFA::n_symbols
unsigned int n_symbols(void) const
Return the number of symbols.
Definition dfa.hpp:145
Gecode::DFA::final_fst
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
Gecode::Heap::copy
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition heap.hpp:583
Gecode::IntArgs
Passing integer arguments.
Definition int.hh:628
Gecode::Int::AlreadyFinalized
Exception: Tuple set already finalized
Definition exception.hpp:143
Gecode::Int::ArgumentSizeMismatch
Exception: Arguments are of different size
Definition exception.hpp:73
Gecode::Int::Extensional::PosCompare::PosCompare
PosCompare(int p)
Initialize with position p.
Definition tuple-set.cpp:86
Gecode::Int::Extensional::PosCompare::operator()
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition tuple-set.cpp:89
Gecode::Int::Extensional::TupleCompare::TupleCompare
TupleCompare(int a)
Initialize with arity a.
Definition tuple-set.cpp:72
Gecode::Int::Extensional::TupleCompare::operator()
bool operator()(const Tuple &a, const Tuple &b)
Comparison of tuples a and b.
Definition tuple-set.cpp:75
Gecode::Int::OutOfLimits
Exception: Value out of limits
Definition exception.hpp:44
Gecode::Int::UninitializedTupleSet
Exception: uninitialized tuple set
Definition exception.hpp:129
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::SharedHandle::SharedHandle
SharedHandle(void)
Create shared handle with no object pointing to.
Definition shared-object.hpp:122
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
Gecode::Support::BitSetData::data
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
Definition bitset-base.hpp:250
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::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::~Data
virtual ~Data(void)
Delete implementation.
Definition tuple-set.cpp:254
Gecode::TupleSet::Data::arity
int arity
Arity.
Definition int.hh:2235
Gecode::TupleSet::Data::finalize
void finalize(void)
Finalize datastructure (disallows additions of more Tuples).
Definition tuple-set.cpp:103
Gecode::TupleSet::Data::n_tuples
int n_tuples
Number of Tuples.
Definition int.hh:2239
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::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::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
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::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=
TupleSet & operator=(const TupleSet &t)
Assignment operator.
Definition tuple-set.cpp:275
Gecode::TupleSet::Tuple
int * Tuple
Type of a tuple.
Definition int.hh:2197
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::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::init
void init(int a)
Initialize an uninitialized tuple set.
Definition tuple-set.cpp:269
Gecode::TupleSet::arity
int arity(void) const
Arity of tuple set.
Definition tuple-set.hpp:181
int.hh
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Int::Extensional
Extensional propagators
Gecode::Int::Extensional::Tuple
TupleSet::Tuple Tuple
Tuple type.
Definition extensional.hh:358
Gecode::Int::Limits::min
const int min
Smallest allowed integer value.
Definition int.hh:118
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition int.hh:116
Gecode::Int
Finite domain integers.
Gecode::Support
Support algorithms and datastructures
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::cmb_hash
void cmb_hash(std::size_t &seed, const T h)
Combine hash value h into seed.
Definition hash.hpp:44
Gecode::same
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1937
forceinline
#define forceinline
Definition config.hpp:187