range-list.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Contributing authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Christian Schulte, 2004
* Guido Tack, 2004
*
* 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 {
class RangeList : public FreeList {
protected:
int _min;
int _max;
public:
RangeList(void);
RangeList(int min, int max);
RangeList(int min, int max, RangeList* n);
int min(void) const;
int max(void) const;
unsigned int width(void) const;
RangeList* next(void) const;
RangeList** nextRef(void);
void min(int n);
void max(int n);
void next(RangeList* n);
template<class Iter>
static void copy(Space& home, RangeList*& r, Iter& i);
template<class Iter>
static void overwrite(Space& home, RangeList*& r, Iter& i);
template<class I>
static void insert(Space& home, RangeList*& r, I& i);
void dispose(Space& home, RangeList* l);
void dispose(Space& home);
static void* operator new(size_t s, Space& home);
static void* operator new(size_t s, void* p);
static void operator delete(void*);
static void operator delete(void*, Space& home);
static void operator delete(void*, void*);
};
/*
* Range lists
*
*/
forceinline
RangeList::RangeList(void) {}
forceinline
RangeList::RangeList(int min, int max, RangeList* n)
: FreeList(n), _min(min), _max(max) {}
forceinline
RangeList::RangeList(int min, int max)
: _min(min), _max(max) {}
forceinline RangeList*
RangeList::next(void) const {
return static_cast<RangeList*>(FreeList::next());
}
forceinline RangeList**
RangeList::nextRef(void) {
return reinterpret_cast<RangeList**>(FreeList::nextRef());
}
forceinline void
RangeList::min(int n) {
_min = n;
}
forceinline void
RangeList::max(int n) {
_max = n;
}
forceinline void
RangeList::next(RangeList* n) {
FreeList::next(n);
}
forceinline int
RangeList::min(void) const {
return _min;
}
forceinline int
RangeList::max(void) const {
return _max;
}
forceinline unsigned int
RangeList::width(void) const {
return static_cast<unsigned int>(_max - _min + 1);
}
forceinline void
RangeList::operator delete(void*) {}
forceinline void
RangeList::operator delete(void*, Space&) {
GECODE_NEVER;
}
forceinline void
RangeList::operator delete(void*, void*) {
GECODE_NEVER;
}
forceinline void*
RangeList::operator new(size_t, Space& home) {
return home.fl_alloc<sizeof(RangeList)>();
}
forceinline void*
RangeList::operator new(size_t, void* p) {
return p;
}
forceinline void
RangeList::dispose(Space& home, RangeList* l) {
home.fl_dispose<sizeof(RangeList)>(this,l);
}
forceinline void
RangeList::dispose(Space& home) {
RangeList* l = this;
while (l->next() != NULL)
l=l->next();
dispose(home,l);
}
template<class Iter>
forceinline void
RangeList::copy(Space& home, RangeList*& r, Iter& i) {
RangeList sentinel; sentinel.next(r);
RangeList* p = &sentinel;
while (i()) {
RangeList* n = new (home) RangeList(i.min(),i.max());
p->next(n); p=n; ++i;
}
p->next(NULL);
r = sentinel.next();
}
template<class Iter>
forceinline void
RangeList::overwrite(Space& home, RangeList*& r, Iter& i) {
RangeList sentinel; sentinel.next(r);
RangeList* p = &sentinel;
RangeList* c = p->next();
while ((c != NULL) && i()) {
c->min(i.min()); c->max(i.max());
p=c; c=c->next(); ++i;
}
if ((c == NULL) && !i())
return;
if (c == NULL) {
assert(i());
// New elements needed
do {
RangeList* n = new (home) RangeList(i.min(),i.max());
p->next(n); p=n; ++i;
} while (i());
} else {
// Dispose excess elements
while (c->next() != NULL)
c=c->next();
p->next()->dispose(home,c);
}
p->next(NULL);
r = sentinel.next();
}
template<class I>
forceinline void
RangeList::insert(Space& home, RangeList*& r, I& i) {
RangeList sentinel;
sentinel.next(r);
RangeList* p = &sentinel;
RangeList* c = p->next();
while ((c != NULL) && i()) {
if ((c->max()+1 < i.min())) {
p=c; c=c->next();
} else if (i.max()+1 < c->min()) {
RangeList* n = new (home) RangeList(i.min(),i.max(),c);
p->next(n); p=n; ++i;
} else {
int min = std::min(c->min(),i.min());
int max = std::max(c->max(),i.max());
RangeList* f=c;
p=c; c=c->next(); ++i;
next:
if ((c != NULL) && (c->min() <= max+1)) {
max = std::max(max,c->max());
p=c; c=c->next();
goto next;
}
if (i() && (i.min() <= max+1)) {
max = std::max(max,i.max());
++i;
goto next;
}
// Dispose now unused elements
if (f->next() != p)
f->next()->dispose(home,p);
f->min(min); f->max(max); f->next(c);
}
}
if (c == NULL) {
while (i()) {
RangeList* n = new (home) RangeList(i.min(),i.max());
p->next(n); p=n;
++i;
}
p->next(NULL);
}
r = sentinel.next();
}
}
// STATISTICS: kernel-other
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition val.hpp:398
Gecode::FreeList::nextRef
FreeList ** nextRef(void)
Return pointer to next link in freelist object.
Definition manager.hpp:253
Gecode::FreeList::FreeList
FreeList(void)
Use uninitialized.
Definition manager.hpp:241
Gecode::FreeList::next
FreeList * next(void) const
Return next freelist object.
Definition manager.hpp:248
Gecode::RangeList
Lists of ranges (intervals).
Definition range-list.hpp:49
Gecode::RangeList::max
int max(void) const
Return maximum.
Definition range-list.hpp:168
Gecode::RangeList::min
int min(void) const
Return minimum.
Definition range-list.hpp:164
Gecode::RangeList::dispose
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive).
Definition range-list.hpp:201
Gecode::RangeList::_min
int _min
Minimum of range.
Definition range-list.hpp:52
Gecode::RangeList::next
RangeList * next(void) const
Return next element.
Definition range-list.hpp:141
Gecode::RangeList::width
unsigned int width(void) const
Return width (distance between maximum and minimum).
Definition range-list.hpp:172
Gecode::RangeList::overwrite
static void overwrite(Space &home, RangeList *&r, Iter &i)
Overwrite rangelist r with ranges from range iterator i.
Definition range-list.hpp:228
Gecode::RangeList::nextRef
RangeList ** nextRef(void)
Return pointer to next element.
Definition range-list.hpp:146
Gecode::RangeList::RangeList
RangeList(void)
Default constructor (noop).
Definition range-list.hpp:130
Gecode::RangeList::insert
static void insert(Space &home, RangeList *&r, I &i)
Insert (as union) ranges from iterator i into r.
Definition range-list.hpp:257
Gecode::RangeList::copy
static void copy(Space &home, RangeList *&r, Iter &i)
Create rangelist r from range iterator i.
Definition range-list.hpp:215
Gecode::RangeList::_max
int _max
Maximum of range.
Definition range-list.hpp:54
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::fl_dispose
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition core.hpp:2827
Test::Base::next
Base * next(void) const
Return next test.
Definition test.hpp:58
Gecode::Iter
Range and value iterators.
Definition iter.hh:41
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