view.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>
*
* Copyright:
* Christian Schulte, 2012
*
* 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 Pos {
public:
const int pos;
Pos(int p);
Pos(const Pos& p);
};
class GECODE_VTABLE_EXPORT PosChoice : public Choice {
private:
const Pos _pos;
protected:
PosChoice(const PosChoice& c);
public:
PosChoice(const Brancher& b, unsigned int a, const Pos& p);
const Pos& pos(void) const;
virtual void archive(Archive& e) const;
};
template<class View, class Filter, int n>
class ViewBrancher : public Brancher {
protected:
typedef typename View::VarType Var;
ViewArray<View> x;
mutable int start;
ViewSel<View>* vs[n];
Filter f;
Pos pos(Space& home);
View view(const Pos& p) const;
ViewBrancher(Space& home, ViewBrancher<View,Filter,n>& b);
ViewBrancher(Home home, ViewArray<View>& x, ViewSel<View>* vs[n],
BranchFilter<Var> bf);
public:
virtual bool status(const Space& home) const;
virtual size_t dispose(Space& home);
};
/*
* Position information
*
*/
forceinline
Pos::Pos(int p) : pos(p) {}
forceinline
Pos::Pos(const Pos& p) : pos(p.pos) {}
/*
* Choice with position
*
*/
forceinline
PosChoice::PosChoice(const Brancher& b, unsigned int a, const Pos& p)
: Choice(b,a), _pos(p) {}
forceinline const Pos&
PosChoice::pos(void) const {
return _pos;
}
forceinline void
PosChoice::archive(Archive& e) const {
Choice::archive(e);
e << _pos.pos;
}
template<class View, class Filter, int n>
forceinline
ViewBrancher<View,Filter,n>::ViewBrancher(Home home, ViewArray<View>& x0,
ViewSel<View>* vs0[n],
BranchFilter<Var> bf)
: Brancher(home), x(x0), start(0), f(bf) {
for (int i=0; i<n; i++)
vs[i] = vs0[i];
for (int i=0; i<n; i++)
if (f.notice() || vs[i]->notice()) {
home.notice(*this,AP_DISPOSE,true);
break;
}
}
template<class View, class Filter, int n>
forceinline
ViewBrancher<View,Filter,n>::ViewBrancher(Space& home,
ViewBrancher<View,Filter,n>& vb)
: Brancher(home,vb), start(vb.start), f(vb.f) {
x.update(home,vb.x);
for (int i=0; i<n; i++)
vs[i] = vb.vs[i]->copy(home);
}
template<class View, class Filter, int n>
bool
ViewBrancher<View,Filter,n>::status(const Space& home) const {
for (int i=start; i < x.size(); i++)
if (!x[i].assigned() && f(home,x[i],i)) {
start = i;
return true;
}
return false;
}
template<class View, class Filter, int n>
inline Pos
ViewBrancher<View,Filter,n>::pos(Space& home) {
assert(!x[start].assigned());
int s;
if (f) {
if (n == 1) {
s = vs[0]->select(home,x,start,f);
} else {
Region r;
int* ties = r.alloc<int>(x.size()-start+1);
int n_ties;
vs[0]->ties(home,x,start,ties,n_ties,f);
for (int i=1; (i < n-1) && (n_ties > 1); i++)
vs[i]->brk(home,x,ties,n_ties);
if (n_ties > 1)
s = vs[n-1]->select(home,x,ties,n_ties);
else
s = ties[0];
}
} else {
if (n == 1) {
s = vs[0]->select(home,x,start);
} else {
Region r;
int* ties = r.alloc<int>(x.size()-start+1);
int n_ties;
vs[0]->ties(home,x,start,ties,n_ties);
for (int i=1; (i < n-1) && (n_ties > 1); i++)
vs[i]->brk(home,x,ties,n_ties);
if (n_ties > 1)
s = vs[n-1]->select(home,x,ties,n_ties);
else
s = ties[0];
}
}
Pos p(s);
return p;
}
template<class View, class Filter, int n>
forceinline View
ViewBrancher<View,Filter,n>::view(const Pos& p) const {
return x[p.pos];
}
template<class View, class Filter, int n>
forceinline size_t
ViewBrancher<View,Filter,n>::dispose(Space& home) {
for (int i=0; i<n; i++)
if (f.notice() || vs[i]->notice()) {
home.ignore(*this,AP_DISPOSE,true);
break;
}
for (int i=0; i<n; i++)
vs[i]->dispose(home);
(void) Brancher::dispose(home);
return sizeof(ViewBrancher<View,Filter,n>);
}
}
// STATISTICS: kernel-branch
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Archive
Archive representation
Definition archive.hpp:42
Gecode::Brancher
Base-class for branchers.
Definition core.hpp:1442
Gecode::Brancher::Space
friend class Space
Definition core.hpp:1444
Gecode::Brancher::Brancher
Brancher(Home home)
Constructor for creation.
Definition core.hpp:3605
Gecode::Choice::Choice
Choice(const Brancher &b, const unsigned int a)
Initialize for particular brancher b and alternatives a.
Definition core.hpp:3766
Gecode::Choice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition core.cpp:891
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::PosChoice::archive
virtual void archive(Archive &e) const
Archive into e.
Definition view.hpp:130
Gecode::PosChoice::pos
const Pos & pos(void) const
Return position in array.
Definition view.hpp:126
Gecode::PosChoice::PosChoice
PosChoice(const PosChoice &c)
Initialize.
Gecode::Pos
Position information.
Definition view.hpp:44
Gecode::Pos::Pos
Pos(int p)
Create position information.
Definition view.hpp:114
Gecode::Pos::pos
const int pos
Position of view.
Definition view.hpp:47
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::View
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::ViewBrancher::pos
Pos pos(Space &home)
Return position information.
Definition view.hpp:173
Gecode::ViewBrancher::f
Filter f
Filter function.
Definition view.hpp:89
Gecode::ViewBrancher::x
ViewArray< View > x
Views to branch on.
Definition view.hpp:83
Gecode::ViewBrancher::ViewBrancher
ViewBrancher(Space &home, ViewBrancher< View, Filter, n > &b)
Constructor for cloning b.
Definition view.hpp:152
Gecode::ViewBrancher::view
View view(const Pos &p) const
Return view according to position information p.
Definition view.hpp:213
Gecode::ViewBrancher::dispose
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition view.hpp:219
Gecode::ViewBrancher::start
int start
Unassigned views start at x[start].
Definition view.hpp:85
Gecode::ViewBrancher::Var
View::VarType Var
The corresponding variable.
Definition view.hpp:81
Gecode::ViewBrancher::vs
ViewSel< View > * vs[n]
View selection objects.
Definition view.hpp:87
Gecode::ViewBrancher::status
virtual bool status(const Space &home) const
Check status of brancher, return true if alternatives left.
Definition view.hpp:162
Gecode::ViewSel
Abstract class for view selection.
Definition view-sel.hpp:44
Gecode::ViewSel::copy
virtual ViewSel< View > * copy(Space &home)=0
Create copy during cloning.
Gecode::Space::ignore
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Gecode
Gecode toplevel namespace
Gecode::BranchFilter
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition filter.hpp:40
forceinline
#define forceinline
Definition config.hpp:187
GECODE_VTABLE_EXPORT
#define GECODE_VTABLE_EXPORT
Definition support.hh:72