cached.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Contributing authors:
* Samuel Gagnon <samuel.gagnon92@gmail.com>
*
* Copyright:
* Guido Tack, 2011
* Samuel Gagnon, 2018
*
* 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 {
/*
* Constructors and initialization
*
*/
template<class View>
forceinline
CachedView<View>::CachedView(void) : _size(0) {}
template<class View>
forceinline
CachedView<View>::CachedView(const View& y)
: DerivedView<View>(y), _firstRange(NULL), _lastRange(NULL),
_size(0) {}
/*
* Value access
*
*/
template<class View>
forceinline int
CachedView<View>::min(void) const {
return x.min();
}
template<class View>
forceinline int
CachedView<View>::max(void) const {
return x.max();
}
template<class View>
forceinline int
CachedView<View>::med(void) const {
return x.med();
}
template<class View>
forceinline int
CachedView<View>::val(void) const {
return x.val();
}
#ifdef GECODE_HAS_CBS
template<class View>
forceinline int
CachedView<View>::baseval(int val) const {
return val;
}
#endif
template<class View>
forceinline unsigned int
CachedView<View>::width(void) const {
return x.width();
}
template<class View>
forceinline unsigned int
CachedView<View>::size(void) const {
return x.size();
}
template<class View>
forceinline unsigned int
CachedView<View>::regret_min(void) const {
return x.regret_min();
}
template<class View>
forceinline unsigned int
CachedView<View>::regret_max(void) const {
return x.regret_max();
}
/*
* Domain tests
*
*/
template<class View>
forceinline bool
CachedView<View>::range(void) const {
return x.range();
}
template<class View>
forceinline bool
CachedView<View>::in(int n) const {
return x.in(n);
}
template<class View>
forceinline bool
CachedView<View>::in(long long int n) const {
return x.in(n);
}
/*
* Domain update by value
*
*/
template<class View>
forceinline ModEvent
CachedView<View>::lq(Space& home, int n) {
return x.lq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::lq(Space& home, long long int n) {
return x.lq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::le(Space& home, int n) {
return x.le(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::le(Space& home, long long int n) {
return x.le(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::gq(Space& home, int n) {
return x.gq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::gq(Space& home, long long int n) {
return x.gq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::gr(Space& home, int n) {
return x.gr(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::gr(Space& home, long long int n) {
return x.gr(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::nq(Space& home, int n) {
return x.nq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::nq(Space& home, long long int n) {
return x.nq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::eq(Space& home, int n) {
return x.eq(home,n);
}
template<class View>
forceinline ModEvent
CachedView<View>::eq(Space& home, long long int n) {
return x.eq(home,n);
}
/*
* Iterator-based domain update
*
*/
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::narrow_r(Space& home, I& i, bool depend) {
return x.narrow_r(home,i,depend);
}
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::inter_r(Space& home, I& i, bool depend) {
return x.inter_r(home,i,depend);
}
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::minus_r(Space& home, I& i, bool depend) {
return x.minus_r(home,i,depend);
}
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::narrow_v(Space& home, I& i, bool depend) {
return x.narrow_v(home,i,depend);
}
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::inter_v(Space& home, I& i, bool depend) {
return x.inter_v(home,i,depend);
}
template<class View>
template<class I>
forceinline ModEvent
CachedView<View>::minus_v(Space& home, I& i, bool depend) {
return x.minus_v(home,i,depend);
}
/*
* Propagator modification events
*
*/
template<class View>
forceinline ModEventDelta
CachedView<View>::med(ModEvent me) {
return View::med(me);
}
/*
* Delta information for advisors
*
*/
template<class View>
forceinline int
CachedView<View>::min(const Delta& d) const {
return x.min(d);
}
template<class View>
forceinline int
CachedView<View>::max(const Delta& d) const {
return x.max(d);
}
template<class View>
forceinline unsigned int
CachedView<View>::width(const Delta& d) const {
return x.width(d);
}
template<class View>
forceinline bool
CachedView<View>::any(const Delta& d) const {
return x.any(d);
}
/*
* Cloning
*
*/
template<class View>
void
CachedView<View>::update(Space& home, CachedView<View>& y) {
DerivedView<View>::update(home,y);
if (y._firstRange) {
_firstRange = new (home) RangeList(y._firstRange->min(),
y._firstRange->max(),NULL);
RangeList* cur = _firstRange;
for (RangeList* y_cur = y._firstRange->next(); y_cur != NULL;
y_cur = y_cur->next()) {
RangeList* next =
new (home) RangeList(y_cur->min(),y_cur->max(),NULL);
cur->next(next);
cur = next;
}
_lastRange = cur;
_size = y._size;
}
}
/*
* Cache operations
*
*/
template<class View>
void
CachedView<View>::initCache(Space& home, const IntSet& s) {
_firstRange = NULL;
for (int i=s.ranges(); i--;) {
_firstRange = new (home) RangeList(s.min(i),s.max(i),_firstRange);
if (i==s.ranges()-1)
_lastRange = _firstRange;
}
_size = s.size();
}
template<class View>
void
CachedView<View>::cache(Space& home) {
_firstRange->dispose(home,_lastRange);
ViewRanges<View> xr(x);
_firstRange = new (home) RangeList(xr.min(),xr.max(),NULL);
++xr;
RangeList* cur = _firstRange;
for (; xr(); ++xr) {
RangeList* next = new (home) RangeList(xr.min(),xr.max(),NULL);
cur->next(next);
cur = next;
}
_lastRange = cur;
_size = x.size();
}
template<class View>
forceinline bool
CachedView<View>::modified(void) const {
return x.size() != _size;
}
template<class View>
class ViewRanges<CachedView<View> >
: public ViewRanges<View> {
public:
ViewRanges(void);
ViewRanges(const CachedView<View>& x);
void init(const CachedView<View>& x);
};
template<class View>
forceinline
ViewRanges<CachedView<View> >::ViewRanges(void) {}
template<class View>
forceinline
ViewRanges<CachedView<View> >::ViewRanges(const CachedView<View>& x) {
ViewRanges<IntView>::init(x.base());
}
template<class View>
forceinline void
ViewRanges<CachedView<View> >::init(const CachedView<View>& x) {
ViewRanges<View>::init(x.base());
}
template<class View>
forceinline
ViewDiffRanges<View>::ViewDiffRanges(void) {}
template<class View>
forceinline
ViewDiffRanges<View>::ViewDiffRanges(const CachedView<View>& x)
: cr(x._firstRange), dr(x.base()) {
Super::init(cr,dr);
}
template<class View>
forceinline void
ViewDiffRanges<View>::init(const CachedView<View>& x) {
cr.init(x._firstRange);
dr.init(x.base());
Super::init(cr,dr);
}
/*
* View comparison
*
*/
template<class View>
forceinline bool
operator ==(const CachedView<View>& x, const CachedView<View>& y) {
return (x.base() == y.base()) && (x.offset() == y.offset());
}
template<class View>
forceinline bool
operator !=(const CachedView<View>& x, const CachedView<View>& y) {
return !(x == y);
}
}}
// STATISTICS: int-var
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::DerivedView::base
View base(void) const
Return view from which this view is derived.
Definition view.hpp:605
Gecode::DerivedView::x
View x
View from which this view is derived.
Definition view.hpp:238
Gecode::DerivedView::DerivedView
DerivedView(void)
Default constructor.
Definition view.hpp:584
Gecode::DerivedView::me
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition view.hpp:639
Gecode::DerivedView::update
void update(Space &home, DerivedView< View > &y)
Update this view to be a clone of view y.
Definition view.hpp:681
Gecode::IntSet
Integer sets.
Definition int.hh:174
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::ranges
int ranges(void) const
Return number of ranges of the specification.
Definition int-set-1.hpp:171
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition int-set-1.hpp:198
Gecode::Int::CachedView
Cached integer view.
Definition view.hpp:1166
Gecode::Int::CachedView::gq
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition cached.hpp:154
Gecode::Int::CachedView::size
unsigned int size(void) const
Return size (cardinality) of domain.
Definition cached.hpp:93
Gecode::Int::CachedView::any
bool any(const Delta &d) const
Test whether arbitrary values got pruned.
Definition cached.hpp:269
Gecode::Int::CachedView::le
ModEvent le(Space &home, int n)
Restrict domain values to be less than n.
Definition cached.hpp:144
Gecode::Int::CachedView::med
int med(void) const
Return median of domain (greatest element not greater than the median).
Definition cached.hpp:70
Gecode::Int::CachedView::width
unsigned int width(void) const
Return width of domain (distance between maximum and minimum).
Definition cached.hpp:88
Gecode::Int::CachedView::inter_v
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition cached.hpp:225
Gecode::Int::CachedView::narrow_r
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition cached.hpp:201
Gecode::Int::CachedView::minus_v
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition cached.hpp:231
Gecode::Int::CachedView::eq
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition cached.hpp:184
Gecode::Int::CachedView::_firstRange
RangeList * _firstRange
First cached range.
Definition view.hpp:1171
Gecode::Int::CachedView::_lastRange
RangeList * _lastRange
Last cached range.
Definition view.hpp:1173
Gecode::Int::CachedView::minus_r
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition cached.hpp:213
Gecode::Int::CachedView::in
bool in(int n) const
Test whether n is contained in domain.
Definition cached.hpp:118
Gecode::Int::CachedView::initCache
void initCache(Space &home, const IntSet &s)
Initialize cache to set s.
Definition cached.hpp:307
Gecode::Int::CachedView::regret_max
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value).
Definition cached.hpp:103
Gecode::Int::CachedView::narrow_v
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition cached.hpp:219
Gecode::Int::CachedView::_size
unsigned int _size
Size of cached domain.
Definition view.hpp:1175
Gecode::Int::CachedView::range
bool range(void) const
Test whether domain is a range.
Definition cached.hpp:113
Gecode::Int::CachedView::val
int val(void) const
Return assigned value (only if assigned).
Definition cached.hpp:75
Gecode::Int::CachedView::cache
void cache(Space &home)
Update cache to current domain.
Definition cached.hpp:319
Gecode::Int::CachedView::lq
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition cached.hpp:134
Gecode::Int::CachedView::inter_r
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition cached.hpp:207
Gecode::Int::CachedView::gr
ModEvent gr(Space &home, int n)
Restrict domain values to be greater than n.
Definition cached.hpp:164
Gecode::Int::CachedView::regret_min
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value).
Definition cached.hpp:98
Gecode::Int::CachedView::min
int min(void) const
Return minimum of domain.
Definition cached.hpp:60
Gecode::Int::CachedView::modified
bool modified(void) const
Check whether cache differs from current domain.
Definition cached.hpp:336
Gecode::Int::CachedView::nq
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition cached.hpp:174
Gecode::Int::CachedView::update
void update(Space &home, CachedView< View > &y)
Update this view to be a clone of view y.
Definition cached.hpp:281
Gecode::Int::CachedView::max
int max(void) const
Return maximum of domain.
Definition cached.hpp:65
Gecode::Int::CachedView::CachedView
CachedView(void)
Default constructor.
Definition cached.hpp:46
Gecode::Int::ViewDiffRanges::init
void init(const CachedView< View > &x)
Initialize with ranges for view x.
Definition cached.hpp:389
Gecode::Int::ViewDiffRanges::dr
ViewRanges< View > dr
Current domain iterator.
Definition view.hpp:1361
Gecode::Int::ViewDiffRanges::cr
Iter::Ranges::RangeList cr
Cached domain iterator.
Definition view.hpp:1359
Gecode::Int::ViewDiffRanges::ViewDiffRanges
ViewDiffRanges(void)
Default constructor.
Definition cached.hpp:378
Gecode::Int::ViewRanges< CachedView< View > >::init
void init(const CachedView< View > &x)
Initialize with ranges for view x.
Definition cached.hpp:372
Gecode::Int::ViewRanges< CachedView< View > >::ViewRanges
ViewRanges(void)
Default constructor.
Definition cached.hpp:362
Gecode::Int::ViewRanges
Range iterator for integer views.
Definition view.hpp:54
Gecode::Int::ViewRanges::max
int max(void) const
Return largest value of range.
Gecode::Int::ViewRanges::min
int min(void) const
Return smallest value of range.
Gecode::Int::ViewRanges::init
void init(const View &x)
Initialize with ranges for view x.
Gecode::Int::ViewRanges::ViewRanges
ViewRanges(void)
Default constructor.
Gecode::Iter::Ranges::Diff< Iter::Ranges::RangeList, ViewRanges< View > >::init
void init(Iter::Ranges::RangeList &i, ViewRanges< View > &j)
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::next
RangeList * next(void) const
Return next element.
Definition range-list.hpp:141
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::View
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Int
Finite domain integers.
Gecode::Int::operator==
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:401
Gecode::Int::operator!=
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition cached.hpp:406
Gecode
Gecode toplevel namespace
Gecode::ModEvent
int ModEvent
Type for modification events.
Definition core.hpp:62
forceinline
#define forceinline
Definition config.hpp:187