int-set.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2003
*
* 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>
namespace Gecode {
IntSet::IntSetObject*
IntSet::IntSetObject::allocate(int n) {
IntSetObject* o = new IntSetObject;
o->n = n;
o->r = heap.alloc<Range>(n);
return o;
}
bool
IntSet::IntSetObject::in(int n) const {
int l = 0;
int r = this->n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
return true;
} else if (l == r) {
return false;
} else if (n < this->r[m].min) {
r=m-1;
} else {
l=m+1;
}
}
return false;
}
bool
IntSet::IntSetObject::equal(const IntSetObject& iso) const {
assert((size == iso.size) || (n == iso.n));
for (int i=0; i<n; i++)
if ((r[i].min != iso.r[i].min) || (r[i].max != iso.r[i].max))
return false;
return true;
}
IntSet::IntSetObject::~IntSetObject(void) {
heap.free<Range>(r,n);
}
class IntSet::MinInc {
public:
bool operator ()(const Range &x, const Range &y);
};
forceinline bool
IntSet::MinInc::operator ()(const Range &x, const Range &y) {
return x.min < y.min;
}
void
IntSet::normalize(Range* r, int n) {
if (n > 0) {
// Sort ranges
{
MinInc lt_mi;
Support::quicksort<Range>(r, n, lt_mi);
}
// Conjoin continuous ranges
{
int min = r[0].min;
int max = r[0].max;
int i = 1;
int j = 0;
while (i < n) {
if (max+1 < r[i].min) {
r[j].min = min; r[j].max = max; j++;
min = r[i].min; max = r[i].max; i++;
} else {
max = std::max(max,r[i].max); i++;
}
}
r[j].min = min; r[j].max = max;
n=j+1;
}
IntSetObject* o = IntSetObject::allocate(n);
unsigned int s = 0;
for (int i=0; i<n; i++) {
s += static_cast<unsigned int>(r[i].max-r[i].min+1);
o->r[i]=r[i];
}
o->size = s;
object(o);
}
}
void
IntSet::init(const int r[], int n) {
assert(n > 0);
Region reg;
Range* dr = reg.alloc<Range>(n);
for (int i=0; i<n; i++) {
dr[i].min=r[i]; dr[i].max=r[i];
}
normalize(&dr[0],n);
}
void
IntSet::init(const int r[][2], int n) {
assert(n > 0);
Region reg;
Range* dr = reg.alloc<Range>(n);
int j = 0;
for (int i=0; i<n; i++)
if (r[i][0] <= r[i][1]) {
dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
}
normalize(&dr[0],j);
}
IntSet::IntSet(std::initializer_list<int> r) {
int n = static_cast<int>(r.size());
assert(n > 0);
Region reg;
Range* dr = reg.alloc<Range>(n);
int j=0;
for (int k : r) {
dr[j].min=dr[j].max=k; j++;
}
normalize(&dr[0],j);
}
IntSet::IntSet(std::initializer_list<std::pair<int,int>> r) {
int n = static_cast<int>(r.size());
assert(n > 0);
Region reg;
Range* dr = reg.alloc<Range>(n);
int j=0;
for (const std::pair<int,int>& k : r)
if (k.first <= k.second) {
dr[j].min=k.first; dr[j].max=k.second; j++;
}
normalize(&dr[0],j);
}
void
IntSet::init(int n, int m) {
if (n <= m) {
IntSetObject* o = IntSetObject::allocate(1);
o->r[0].min = n; o->r[0].max = m;
o->size = static_cast<unsigned int>(m - n + 1);
object(o);
}
}
const IntSet IntSet::empty;
}
// STATISTICS: int-var
Gecode::Heap::free
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:457
Gecode::Heap::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition heap.hpp:431
Gecode::IntSet::MinInc
Sort ranges according to increasing minimum.
Definition int-set.cpp:80
Gecode::IntSet::MinInc::operator()
bool operator()(const Range &x, const Range &y)
Definition int-set.cpp:86
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition int-set-1.hpp:152
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition int-set-1.hpp:158
Gecode::IntSet::max
int max(void) const
Return maximum of entire set.
Definition int-set-1.hpp:192
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition int-set-1.hpp:198
Gecode::IntSet::IntSet
IntSet(void)
Initialize as empty set.
Definition int-set-1.hpp:43
Gecode::IntSet::empty
static const IntSet empty
Empty set.
Definition int.hh:283
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
int.hh
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Test::Int::Dom::r
const int r[4][2]
Definition dom.cpp:152
forceinline
#define forceinline
Definition config.hpp:187