nvalues.hh
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, 2011
*
* 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.
*
*/
#ifndef __GECODE_INT_NVALUES_HH__
#define __GECODE_INT_NVALUES_HH__
#include <gecode/int.hh>
#include <gecode/int/val-set.hh>
namespace Gecode { namespace Int { namespace NValues {
enum RangeEventType {
RET_FST = 0,
RET_LST = 1,
RET_END = 2
};
class RangeEvent {
public:
RangeEventType ret;
int val;
int view;
bool operator <(RangeEvent re) const;
};
class SymBitMatrix : public Support::BitSet<Region> {
protected:
int n;
int pos(int x, int y) const;
public:
SymBitMatrix(Region& r, int n);
bool get(int x, int y) const;
void set(int x, int y);
};
}}}
#include <gecode/int/nvalues/range-event.hpp>
#include <gecode/int/nvalues/sym-bit-matrix.hpp>
#include <gecode/int/view-val-graph.hh>
namespace Gecode { namespace Int { namespace NValues {
class Graph : public ViewValGraph::Graph<IntView> {
protected:
int n_matched;
public:
Graph(void);
int size(void) const;
void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
void sync(void);
/*
* \brief Mark all edges used that can appear in some maximal matching
*
* Return true, if any edge can be in fact pruned.
*/
bool mark(void);
ExecStatus prune(Space& home);
};
}}}
#include <gecode/int/nvalues/graph.hpp>
namespace Gecode { namespace Int { namespace NValues {
template<class VY>
class IntBase
: public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
protected:
using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::x;
using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::y;
ValSet vs;
IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
IntBase(Space& home, IntBase<VY>& p);
void add(Space& home);
void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
void eliminate(Space& home);
ExecStatus all_in_valset(Space& home);
ExecStatus prune_lower(Space& home, int* dis, int n_dis);
ExecStatus prune_upper(Space& home, Graph& g);
public:
virtual PropCost cost(const Space&, const ModEventDelta&) const;
virtual size_t dispose(Space& home);
};
template<class VY>
class EqInt : public IntBase<VY> {
protected:
using IntBase<VY>::x;
using IntBase<VY>::y;
using IntBase<VY>::vs;
using IntBase<VY>::add;
using IntBase<VY>::all_in_valset;
using IntBase<VY>::disjoint;
using IntBase<VY>::prune_lower;
using IntBase<VY>::prune_upper;
Graph g;
EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
EqInt(Space& home, EqInt<VY>& p);
public:
virtual Propagator* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
virtual size_t dispose(Space& home);
};
template<class VY>
class LqInt : public IntBase<VY> {
protected:
using IntBase<VY>::x;
using IntBase<VY>::y;
using IntBase<VY>::vs;
using IntBase<VY>::add;
using IntBase<VY>::all_in_valset;
using IntBase<VY>::disjoint;
using IntBase<VY>::prune_lower;
using IntBase<VY>::prune_upper;
LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
LqInt(Space& home, LqInt<VY>& p);
public:
virtual Propagator* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
virtual size_t dispose(Space& home);
};
template<class VY>
class GqInt : public IntBase<VY> {
protected:
using IntBase<VY>::x;
using IntBase<VY>::y;
using IntBase<VY>::vs;
using IntBase<VY>::add;
using IntBase<VY>::all_in_valset;
using IntBase<VY>::disjoint;
using IntBase<VY>::prune_lower;
using IntBase<VY>::prune_upper;
using IntBase<VY>::eliminate;
Graph g;
GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
GqInt(Space& home, GqInt<VY>& p);
public:
virtual Propagator* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
};
}}}
#include <gecode/int/nvalues/int-base.hpp>
#include <gecode/int/nvalues/int-eq.hpp>
#include <gecode/int/nvalues/int-lq.hpp>
#include <gecode/int/nvalues/int-gq.hpp>
namespace Gecode { namespace Int { namespace NValues {
template<class VY>
class BoolBase : public Propagator {
protected:
static const int VS_ZERO = 1 << 0;
static const int VS_ONE = 1 << 1;
int status;
Council<ViewAdvisor<BoolView> > c;
VY y;
BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
BoolBase(Space& home, BoolBase<VY>& p);
public:
virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
virtual void reschedule(Space& home);
virtual size_t dispose(Space& home);
};
template<class VY>
class EqBool : public BoolBase<VY> {
protected:
using BoolBase<VY>::VS_ZERO;
using BoolBase<VY>::VS_ONE;
using BoolBase<VY>::status;
using BoolBase<VY>::c;
using BoolBase<VY>::y;
EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
EqBool(Space& home, EqBool<VY>& p);
public:
virtual Actor* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
};
template<class VY>
class LqBool : public BoolBase<VY> {
protected:
using BoolBase<VY>::VS_ZERO;
using BoolBase<VY>::VS_ONE;
using BoolBase<VY>::status;
using BoolBase<VY>::c;
using BoolBase<VY>::y;
LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
LqBool(Space& home, LqBool<VY>& p);
public:
virtual Actor* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
};
template<class VY>
class GqBool : public BoolBase<VY> {
protected:
using BoolBase<VY>::VS_ZERO;
using BoolBase<VY>::VS_ONE;
using BoolBase<VY>::status;
using BoolBase<VY>::c;
using BoolBase<VY>::y;
GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
GqBool(Space& home, GqBool<VY>& p);
public:
virtual Actor* copy(Space& home);
virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
};
}}}
#include <gecode/int/nvalues/bool-base.hpp>
#include <gecode/int/nvalues/bool-eq.hpp>
#include <gecode/int/nvalues/bool-lq.hpp>
#include <gecode/int/nvalues/bool-gq.hpp>
#endif
// STATISTICS: int-prop
bool-base.hpp
bool-eq.hpp
bool-gq.hpp
bool-lq.hpp
Gecode::ActorLink::Actor
friend class Actor
Definition core.hpp:590
Gecode::Delta
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::IntView
Integer view for integer variables.
Definition view.hpp:129
Gecode::Int::NValues::BoolBase::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition bool-base.hpp:91
Gecode::Int::NValues::BoolBase::c
Council< ViewAdvisor< BoolView > > c
The advisor council.
Definition nvalues.hh:302
Gecode::Int::NValues::BoolBase::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as low unary).
Definition bool-base.hpp:58
Gecode::Int::NValues::BoolBase::BoolBase
BoolBase(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-base.hpp:38
Gecode::Int::NValues::BoolBase::VS_ONE
static const int VS_ONE
View status: a one has already been encountered.
Definition nvalues.hh:298
Gecode::Int::NValues::BoolBase::y
VY y
The view for counting the number of values.
Definition nvalues.hh:304
Gecode::Int::NValues::BoolBase::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition bool-base.hpp:64
Gecode::Int::NValues::BoolBase::VS_ZERO
static const int VS_ZERO
View status: a zero has already been encountered.
Definition nvalues.hh:296
Gecode::Int::NValues::BoolBase::advise
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Definition bool-base.hpp:70
Gecode::Int::NValues::BoolBase::status
int status
Status information about the views.
Definition nvalues.hh:300
Gecode::Int::NValues::EqBool::EqBool
EqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-eq.hpp:41
Gecode::Int::NValues::EqBool::post
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-eq.hpp:57
Gecode::Int::NValues::EqBool::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-eq.hpp:118
Gecode::Int::NValues::EqBool::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-eq.hpp:51
Gecode::Int::NValues::EqInt::EqInt
EqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-eq.hpp:41
Gecode::Int::NValues::EqInt::copy
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-eq.hpp:102
Gecode::Int::NValues::EqInt::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-eq.hpp:108
Gecode::Int::NValues::EqInt::post
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-eq.hpp:48
Gecode::Int::NValues::EqInt::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-eq.hpp:116
Gecode::Int::NValues::EqInt::g
Graph g
View-value graph.
Definition nvalues.hh:196
Gecode::Int::NValues::GqBool::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-gq.hpp:109
Gecode::Int::NValues::GqBool::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-gq.hpp:50
Gecode::Int::NValues::GqBool::GqBool
GqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-gq.hpp:40
Gecode::Int::NValues::GqBool::post
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-gq.hpp:56
Gecode::Int::NValues::GqInt::post
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-gq.hpp:46
Gecode::Int::NValues::GqInt::copy
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-gq.hpp:98
Gecode::Int::NValues::GqInt::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-gq.hpp:104
Gecode::Int::NValues::GqInt::GqInt
GqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-gq.hpp:41
Gecode::Int::NValues::GqInt::g
Graph g
View-value graph.
Definition nvalues.hh:263
Gecode::Int::NValues::Graph
View-value graph for propagation of upper bound.
Definition nvalues.hh:96
Gecode::Int::NValues::Graph::init
void init(Space &home, const ValSet &vs, const ViewArray< IntView > &x)
Initialize graph including values in vs.
Definition graph.hpp:46
Gecode::Int::NValues::Graph::sync
void sync(void)
Synchronize graph with new view domains.
Definition graph.hpp:90
Gecode::Int::NValues::Graph::Graph
Graph(void)
Construct graph as not yet initialized.
Definition graph.hpp:37
Gecode::Int::NValues::Graph::mark
bool mark(void)
Definition graph.hpp:152
Gecode::Int::NValues::Graph::n_matched
int n_matched
Number of matched edges.
Definition nvalues.hh:99
Gecode::Int::NValues::Graph::prune
ExecStatus prune(Space &home)
Prune all values corresponding to unused edges.
Definition graph.hpp:255
Gecode::Int::NValues::Graph::size
int size(void) const
Return size of maximal matching (excluding assigned views).
Definition graph.hpp:41
Gecode::Int::NValues::IntBase::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-base.hpp:53
Gecode::Int::NValues::IntBase::vs
ValSet vs
Value set storing the values of already assigned views.
Definition nvalues.hh:138
Gecode::Int::NValues::IntBase::prune_lower
ExecStatus prune_lower(Space &home, int *dis, int n_dis)
Definition int-base.hpp:130
Gecode::Int::NValues::IntBase::disjoint
void disjoint(Space &home, Region &r, int *&dis, int &n_dis)
Definition int-base.hpp:80
Gecode::Int::NValues::IntBase::cost
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition int-base.hpp:62
Gecode::Int::NValues::IntBase::add
void add(Space &home)
Add values of assigned views to value set.
Definition int-base.hpp:68
Gecode::Int::NValues::IntBase::eliminate
void eliminate(Space &home)
Eliminate subsumed views (all values included in the value set vs).
Definition int-base.hpp:107
Gecode::Int::NValues::IntBase::all_in_valset
ExecStatus all_in_valset(Space &home)
Propagate that all views must take values from value set.
Definition int-base.hpp:120
Gecode::Int::NValues::IntBase::prune_upper
ExecStatus prune_upper(Space &home, Graph &g)
Definition int-base.hpp:298
Gecode::Int::NValues::IntBase::IntBase
IntBase(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-base.hpp:40
Gecode::Int::NValues::LqBool::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition bool-lq.hpp:50
Gecode::Int::NValues::LqBool::LqBool
LqBool(Home home, int status, ViewArray< BoolView > &x, VY y)
Constructor for posting.
Definition bool-lq.hpp:40
Gecode::Int::NValues::LqBool::post
static ExecStatus post(Home home, ViewArray< BoolView > &x, VY y)
Post propagator for .
Definition bool-lq.hpp:56
Gecode::Int::NValues::LqBool::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition bool-lq.hpp:111
Gecode::Int::NValues::LqInt::post
static ExecStatus post(Home home, ViewArray< IntView > &x, VY y)
Post propagator for .
Definition int-lq.hpp:48
Gecode::Int::NValues::LqInt::LqInt
LqInt(Home home, ValSet &vs, ViewArray< IntView > &x, VY y)
Constructor for posting.
Definition int-lq.hpp:41
Gecode::Int::NValues::LqInt::dispose
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int-lq.hpp:104
Gecode::Int::NValues::LqInt::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int-lq.hpp:112
Gecode::Int::NValues::LqInt::copy
virtual Propagator * copy(Space &home)
Copy propagator during cloning.
Definition int-lq.hpp:98
Gecode::Int::NValues::RangeEvent
Event for range-based overlap analysis.
Definition nvalues.hh:58
Gecode::Int::NValues::RangeEvent::ret
RangeEventType ret
The event type.
Definition nvalues.hh:61
Gecode::Int::NValues::RangeEvent::view
int view
Which view does this range belong to.
Definition nvalues.hh:65
Gecode::Int::NValues::RangeEvent::val
int val
The value for the range (first or last value, depending on type).
Definition nvalues.hh:63
Gecode::Int::NValues::RangeEvent::operator<
bool operator<(RangeEvent re) const
Order events: first by val, then by event type.
Definition range-event.hpp:37
Gecode::Int::NValues::SymBitMatrix::get
bool get(int x, int y) const
Is bit at position x, y set?
Definition sym-bit-matrix.hpp:50
Gecode::Int::NValues::SymBitMatrix::pos
int pos(int x, int y) const
Return position in matrix.
Definition sym-bit-matrix.hpp:39
Gecode::Int::NValues::SymBitMatrix::set
void set(int x, int y)
Set bit at position x, y.
Definition sym-bit-matrix.hpp:57
Gecode::Int::NValues::SymBitMatrix::SymBitMatrix
SymBitMatrix(Region &r, int n)
Initialize matrix for dimension n by n.
Definition sym-bit-matrix.hpp:45
Gecode::Int::NValues::SymBitMatrix::n
int n
Size of matrix.
Definition nvalues.hh:74
Gecode::Int::ValSet
Class for storing values of already assigned views.
Definition val-set.hh:44
Gecode::Int::ViewValGraph::Graph
View-value graph base class.
Definition view-val-graph.hh:294
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::MixNaryOnePropagator
MixNaryOnePropagator(Space &home, MixNaryOnePropagator &p)
Definition pattern.hpp:733
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::x
ViewArray< IntView > x
Definition pattern.hpp:275
Gecode::MixNaryOnePropagator< IntView, PC_INT_DOM, VY, PC_INT_BND >::y
VY y
Definition pattern.hpp:277
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Advisor
friend class Advisor
Definition core.hpp:1068
Gecode::Propagator::Council
friend class Council
Definition core.hpp:1069
Gecode::Propagator::med
ModEventDelta med
A set of modification events (used during propagation).
Definition core.hpp:1075
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::BitSet
Simple bitsets.
Definition bitset.hpp:45
Gecode::ViewArray
View arrays.
Definition array.hpp:253
int.hh
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
Gecode::Int::NValues
Number of values propagators.
Gecode::Int::NValues::RangeEventType
RangeEventType
Event type for range-based overlap analysis.
Definition nvalues.hh:48
Gecode::Int::NValues::RET_FST
@ RET_FST
A range starts.
Definition nvalues.hh:50
Gecode::Int::NValues::RET_LST
@ RET_LST
A range ends.
Definition nvalues.hh:52
Gecode::Int::NValues::RET_END
@ RET_END
No further events.
Definition nvalues.hh:54
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_BND
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:91
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
graph.hpp
int-base.hpp
int-eq.hpp
int-gq.hpp
int-lq.hpp
range-event.hpp
sym-bit-matrix.hpp
val-set.hh
view-val-graph.hh