37 namespace Gecode {
namespace Int {
namespace Extensional {
76 template<
class View,
class Val,
class Degree,
class StateIdx>
83 template<
class View,
class Val,
class Degree,
class StateIdx>
86 return layers[
i].states[is];
88 template<
class View,
class Val,
class Degree,
class StateIdx>
94 template<
class View,
class Val,
class Degree,
class StateIdx>
98 return --i_state(i,e).o_deg == 0;
100 template<
class View,
class Val,
class Degree,
class StateIdx>
103 return layers[i+1].states[os];
105 template<
class View,
class Val,
class Degree,
class StateIdx>
111 template<
class View,
class Val,
class Degree,
class StateIdx>
115 return --o_state(i,e).i_deg == 0;
122 template<
class View,
class Val,
class Degree,
class StateIdx>
125 template<
class View,
class Val,
class Degree,
class StateIdx>
129 : s1(l.support), s2(l.support+l.
size) {}
130 template<
class View,
class Val,
class Degree,
class StateIdx>
135 template<
class View,
class Val,
class Degree,
class StateIdx>
141 template<
class View,
class Val,
class Degree,
class StateIdx>
146 template<
class View,
class Val,
class Degree,
class StateIdx>
157 template<
class View,
class Val,
class Degree,
class StateIdx>
164 template<
class View,
class Val,
class Degree,
class StateIdx>
174 template<
class View,
class Val,
class Degree,
class StateIdx>
177 : _fst(INT_MAX), _lst(INT_MIN) {}
178 template<
class View,
class Val,
class Degree,
class StateIdx>
181 _fst=INT_MAX; _lst=INT_MIN;
183 template<
class View,
class Val,
class Degree,
class StateIdx>
188 template<
class View,
class Val,
class Degree,
class StateIdx>
194 template<
class View,
class Val,
class Degree,
class StateIdx>
199 template<
class View,
class Val,
class Degree,
class StateIdx>
211 template<
class View,
class Val,
class Degree,
class StateIdx>
216 template<
class View,
class Val,
class Degree,
class StateIdx>
229 template<
class View,
class Val,
class Degree,
class StateIdx>
240 template<
class View,
class Val,
class Degree,
class StateIdx>
245 unsigned int n_e = 0;
246 unsigned int n_s = 0;
248 for (
int i=
n; i--; ) {
257 assert(n_s <= n_states);
262 template<
class View,
class Val,
class Degree,
class StateIdx>
276 for (
int i=0; i<static_cast<int>(
max_states)*(
n+1); i++)
278 for (
int i=0; i<
n+1; i++)
288 for (
int i=0; i<
n; i++) {
296 if (
i_state(i,static_cast<StateIdx>(
t.i_state())).
i_deg != 0) {
307 s.
val =
static_cast<Val
>(nx.val());
320 o_state(n-1,static_cast<StateIdx>(s)).o_deg = 1;
323 for (
int i=n; i--; ) {
343 layers[i].x.subscribe(home, *new (home)
Index(home,*
this,
c,i));
359 d += static_cast<unsigned int>(
layers[n].states[j].i_deg);
362 static_cast<unsigned int>
365 for (StateIdx j=max_states; j--; )
366 if ((
layers[n].states[j].o_deg != 0) ||
371 for (StateIdx j=max_states; j--; ) {
385 StateIdx max_s = i_n;
387 for (
int i=n; i--; ) {
391 for (StateIdx j=max_states; j--; )
392 if ((
layers[i].states[j].o_deg != 0) ||
393 (
layers[i].states[j].i_deg != 0))
403 for (Degree deg=ls.
n_edges; deg--; ) {
412 for (
int i=n+1; i--; ) {
414 for (StateIdx j=max_states; j--; )
415 if ((
layers[i].states[j].o_deg != 0) ||
435 template<
class View,
class Val,
class Degree,
class StateIdx>
440 if (
layers[0].states == NULL) {
442 for (
unsigned int i=0; i<
n_states; i++)
446 for (
int i=
n; i--; ) {
451 for (Degree deg=s.
n_edges; deg--; ) {
476 Val
n =
static_cast<Val
>(
layers[
i].
x.val());
482 for (Degree deg=s.
n_edges; deg--; ) {
488 assert(
layers[i].support[j].val == n);
495 for (Degree deg=ls.
n_edges; deg--; ) {
501 }
else if (
layers[i].
x.any(d)) {
507 if (ls.
val < static_cast<Val>(rx.min())) {
510 for (Degree deg=ls.
n_edges; deg--; ) {
516 }
else if (ls.
val > static_cast<Val>(rx.max())) {
529 for (Degree deg=ls.
n_edges; deg--; ) {
544 for (; (j<s) && (
layers[i].support[j].val <= max); j++) {
547 for (Degree deg=ls.
n_edges; deg--; ) {
563 if (o_mod && (i > 0)) {
566 if (i_mod && (i+1 <
n)) {
581 template<
class View,
class Val,
class Degree,
class StateIdx>
586 return sizeof(*this);
589 template<
class View,
class Val,
class Degree,
class StateIdx>
595 template<
class View,
class Val,
class Degree,
class StateIdx>
628 if (o_mod && (i > 0))
630 if (i_mod && (i+1 <
n))
662 if (o_mod && (i > 0))
679 template<
class View,
class Val,
class Degree,
class StateIdx>
691 assert(x.
size() > 0);
692 for (
int i=0; i<x.
size(); i++) {
702 template<
class View,
class Val,
class Degree,
class StateIdx>
716 for (
int i=0; i<
n; i++) {
736 template<
class View,
class Val,
class Degree,
class StateIdx>
743 template<
class View,
class Val,
class Degree,
class StateIdx>
765 n_edges -=
static_cast<unsigned int>(k);
779 assert((f >= 0) && (l <=
n));
791 if ((
layers[l].states[j].i_deg != 0) ||
809 for (
int i=l-1; i>=
f; i--) {
815 if ((
layers[i].states[j].o_deg != 0) ||
816 (
layers[i].states[j].i_deg != 0)) {
863 switch (t_state_idx) {
872 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned char>
876 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned char>
889 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned short int>
893 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned short int>
906 <
typename VarTraits<Var>::View,
short int,
unsigned short int,
unsigned int>
910 <
typename VarTraits<Var>::View,
short int,
unsigned int,
unsigned int>
919 switch (t_state_idx) {
928 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned char>
932 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned char>
945 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned short int>
949 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned short int>
962 <
typename VarTraits<Var>::View,int,
unsigned short int,
unsigned int>
966 <
typename VarTraits<Var>::View,int,
unsigned int,
unsigned int>
IndexRange i_ch
Index range with in-degree modifications.
int fst(void) const
Return first position.
void init(void)
Initialize links (self-linked)
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
int final_fst(void) const
Return the number of the first final state.
int size(void) const
Return size of array (number of elements)
void audit(void)
Perform consistency check on data structures.
Edge defined by in-state and out-state
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Council< Index > c
The advisor council.
Iterator for DFA symbols.
ExecStatus ES_SUBSUMED(Propagator &p)
const FloatNum max
Largest allowed float value.
int n
Number of layers (and views)
Iterator for telling variable domains by scanning support.
IndexRange a_ch
Index range for any change (for compression)
StateIdx n_states
Number of states used by outgoing edges.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Traits class for variables.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
unsigned int n_states
Total number of states.
Index(Space &home, Propagator &p, Council< Index > &c, int i)
Create index advisor.
IntType u_type(unsigned int n)
Return type required to represent n.
void init(const Layer &l)
Initialize for support of layer l.
StateIdx i_state
Number of in-state.
Base-class for propagators.
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Class to iterate over advisors of a council.
Value iterator for integer views.
void lshift(int n)
Shift index range by n elements to the left.
Propagation has computed fixpoint.
Int::IntView View
The variable type of an IntView.
Support information for a value
bool i_dec(int i, const Edge &e)
Decrement out degree for in state of edge e for layer i.
IndexRange o_ch
Index range with out-degree modifications.
LayeredGraph(Space &home, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
Base-class for both propagators and branchers.
Range iterator for integer views.
IntType s_type(signed int n)
Return type required to represent n.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
State & o_state(int i, StateIdx os)
Return out state for layer i and state index os.
ValSize size
Number of supported values.
StateIdx o_state
Number of out-state.
Deterministic finite automaton (DFA)
int p
Number of positive literals for node type.
const FloatNum min
Smallest allowed float value.
void operator++(void)
Move to next supported value.
Support * support
Supported values.
Gecode::IntArgs i({1, 2, 3, 4})
Execution has resulted in failure.
Range approximation of which positions have changed.
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
bool assigned(void) const
Test if all variables are assigned.
int lst(void) const
Return last position.
Layer for a view in the layered graph
Degree n_edges
Number of supporting edges.
int symbol_max(void) const
Return largest symbol in DFA.
unsigned int size(I &i)
Size of all ranges of range iterator i.
size_t size
The size of the propagator (used during subsumption)
Layer * layers
The layers of the graph.
StateIdx max_states
Maximal number of states per layer.
ExecStatus post_lgp(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Select small types for the layered graph propagator.
void reset(void)
Reset range to be empty.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Traits to for information about integer types.
Degree o_deg
The out-degree (number of outgoing edges) Initialize with zeroes.
State * states
States used by outgoing edges.
Boolean integer variables.
Domain consistent layered graph (regular) propagator.
Post propagator for SetVar SetOpType SetVar SetRelType r
LayerValues(void)
Default constructor.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
Integer view for integer variables.
static ExecStatus post(Home home, const VarArgArray< Var > &x, const DFA &dfa)
Post propagator on views x and DFA dfa.
Generic domain change information to be supplied to advisors.
bool empty(void) const
Test whether range is empty.
Advisors for views (by position in array)
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
virtual size_t dispose(Space &home)
Delete actor and return its size.
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
IndexRange(void)
Initialize range as empty.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Iterator for DFA transitions (sorted by symbols)
Post propagator for SetVar x
Propagation has not computed fixpoint.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
int n_states(void) const
Return the number of states.
bool operator()(void) const
Test whether more values supported.
void add(int i)
Add index i to range.
Edge * edges
Supporting edges in layered graph.
Int::BoolView View
The variable type of an IntView.
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (defined as high linear)
State & i_state(int i, StateIdx is)
Return in state for layer i and state index is.
Gecode toplevel namespace
Argument array for variables.
int symbol_min(void) const
Return smallest symbol in DFA.
ExecStatus initialize(Space &home, const VarArgArray< Var > &x, const DFA &dfa)
Initialize layered graph.
States are described by number of incoming and outgoing edges.
Degree i_deg
The in-degree (number of incoming edges)
virtual void reschedule(Space &home)
Schedule function.
bool o_dec(int i, const Edge &e)
Decrement in degree for out state of edge e for layer i.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
IntType
Description of integer types.
int final_lst(void) const
Return the number of the last final state.
int ModEventDelta
Modification event deltas.
Home class for posting propagators
#define GECODE_NEVER
Assert that this command is never executed.
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
int val(void) const
Return supported value.
unsigned int n_edges
Total number of edges.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
int i
The position of the view in the view array.
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Boolean view for Boolean variables.