41 namespace Gecode {
namespace Int {
namespace Extensional {
80 template<
class View,
class Val,
class Degree,
class StateIdx>
87 template<
class View,
class Val,
class Degree,
class StateIdx>
92 template<
class View,
class Val,
class Degree,
class StateIdx>
98 template<
class View,
class Val,
class Degree,
class StateIdx>
104 template<
class View,
class Val,
class Degree,
class StateIdx>
109 template<
class View,
class Val,
class Degree,
class StateIdx>
115 template<
class View,
class Val,
class Degree,
class StateIdx>
126 template<
class View,
class Val,
class Degree,
class StateIdx>
129 template<
class View,
class Val,
class Degree,
class StateIdx>
133 : s1(
l.support), s2(
l.support+
l.
size) {}
134 template<
class View,
class Val,
class Degree,
class StateIdx>
137 s1=
l.support; s2=
l.support+
l.size;
139 template<
class View,
class Val,
class Degree,
class StateIdx>
145 template<
class View,
class Val,
class Degree,
class StateIdx>
150 template<
class View,
class Val,
class Degree,
class StateIdx>
161 template<
class View,
class Val,
class Degree,
class StateIdx>
168 template<
class View,
class Val,
class Degree,
class StateIdx>
179 template<
class View,
class Val,
class Degree,
class StateIdx>
182 : _fst(INT_MAX), _lst(INT_MIN) {}
183 template<
class View,
class Val,
class Degree,
class StateIdx>
186 _fst=INT_MAX; _lst=INT_MIN;
188 template<
class View,
class Val,
class Degree,
class StateIdx>
193 template<
class View,
class Val,
class Degree,
class StateIdx>
199 template<
class View,
class Val,
class Degree,
class StateIdx>
204 template<
class View,
class Val,
class Degree,
class StateIdx>
216 template<
class View,
class Val,
class Degree,
class StateIdx>
221 template<
class View,
class Val,
class Degree,
class StateIdx>
234 template<
class View,
class Val,
class Degree,
class StateIdx>
245 template<
class View,
class Val,
class Degree,
class StateIdx>
250 unsigned int n_e = 0;
251 unsigned int n_s = 0;
253 for (
int i=
n;
i--; ) {
254 n_s += layers[
i].n_states;
257 n_e += layers[
i].support[j].n_edges;
259 n_s += layers[
n].n_states;
261 assert(n_e == n_edges);
262 assert(n_s <= n_states);
263 assert(m_s <= max_states);
267 template<
class View,
class Val,
class Degree,
class StateIdx>
281 for (
int i=static_cast<int>(max_states)*(
n+1);
i--; )
283 for (
int i=
n+1;
i--; )
284 layers[
i].states = states +
i*max_states;
290 i_state(0,0).i_deg = 1;
293 for (
int i=0;
i<
n;
i++) {
301 if (i_state(
i,static_cast<StateIdx>(
t.i_state())).i_deg != 0) {
302 i_state(
i,static_cast<StateIdx>(
t.i_state())).o_deg++;
303 o_state(
i,static_cast<StateIdx>(
t.o_state())).i_deg++;
304 edges[n_edges].
i_state = static_cast<StateIdx>(
t.i_state());
305 edges[n_edges].
o_state = static_cast<StateIdx>(
t.o_state());
312 s.
val = static_cast<Val>(nx.val());
318 if ((layers[
i].
size = j) == 0)
324 if (o_state(
n-1,static_cast<StateIdx>(s)).i_deg != 0)
325 o_state(
n-1,static_cast<StateIdx>(s)).o_deg = 1;
328 for (
int i=
n;
i--; ) {
330 for (
ValSize j=0; j<layers[
i].size; j++) {
333 if (o_state(
i,s.
edges[
d]).o_deg == 0) {
341 layers[
i].support[k++]=s;
343 if ((layers[
i].
size = k) == 0)
347 if (!layers[
i].
x.assigned())
348 layers[
i].
x.subscribe(home, *new (home)
Index(home,*
this,
c,
i));
354 StateIdx* i_map =
r.alloc<StateIdx>(max_states);
356 StateIdx* o_map =
r.alloc<StateIdx>(max_states);
363 for (StateIdx j=max_states; j--; )
364 d += static_cast<unsigned int>(layers[
n].states[j].i_deg);
367 static_cast<unsigned int>
370 for (StateIdx j=max_states; j--; )
371 if ((layers[
n].states[j].o_deg != 0) ||
372 (layers[
n].states[j].i_deg != 0))
376 for (StateIdx j=max_states; j--; ) {
377 layers[
n].states[j].init();
380 layers[
n].states[0].i_deg = static_cast<Degree>(
d);
381 layers[
n].states[0].o_deg = 1;
383 layers[
n].n_states = i_n;
390 StateIdx max_s = i_n;
392 for (
int i=
n;
i--; ) {
394 std::swap(o_map,i_map); i_n=0;
396 for (StateIdx j=max_states; j--; )
397 if ((layers[
i].states[j].o_deg != 0) ||
398 (layers[
i].states[j].i_deg != 0))
400 layers[
i].n_states = i_n;
417 for (
int i=
n+1;
i--; ) {
419 for (StateIdx j=max_states; j--; )
420 if ((layers[
i].states[j].o_deg != 0) ||
421 (layers[
i].states[j].i_deg != 0))
422 a_states[k++] = layers[
i].states[j];
423 assert(k == layers[
i].n_states);
424 layers[
i].states = a_states;
425 a_states += layers[
i].n_states;
440 template<
class View,
class Val,
class Degree,
class StateIdx>
445 if (layers[0].states == NULL) {
447 for (
unsigned int i=n_states;
i--; )
449 layers[
n].states = states;
450 states += layers[
n].n_states;
451 for (
int i=
n;
i--; ) {
452 layers[
i].states = states;
453 states += layers[
i].n_states;
467 if (layers[
i].
size <= layers[
i].
x.size()) {
481 Val
n = static_cast<Val>(layers[
i].
x.val());
483 for (; layers[
i].support[j].val <
n; j++) {
493 assert(layers[
i].support[j].val ==
n);
494 layers[
i].support[0] = layers[
i].support[j++];
506 }
else if (layers[
i].
x.any(
d)) {
512 if (s.
val < static_cast<Val>(rx.min())) {
521 }
else if (s.
val > static_cast<Val>(rx.max())) {
524 layers[
i].support[k++]=s;
541 Val
min = static_cast<Val>(layers[
i].
x.min(
d));
544 for (; layers[
i].support[j].val <
min; j++) {}
545 Val
max = static_cast<Val>(layers[
i].
x.max(
d));
549 for (; (j<s) && (layers[
i].support[j].val <=
max); j++) {
560 layers[
i].support[k++]=layers[
i].support[j++];
568 if (o_mod && (
i > 0)) {
569 o_ch.add(
i-1); fix =
false;
571 if (i_mod && (
i+1 <
n)) {
572 i_ch.add(
i+1); fix =
false;
586 template<
class View,
class Val,
class Degree,
class StateIdx>
591 return sizeof(*this);
594 template<
class View,
class Val,
class Degree,
class StateIdx>
599 for (
int i=i_ch.fst();
i<=i_ch.lst();
i++) {
609 if (i_state(
i,s.
edges[
d]).i_deg == 0) {
622 layers[
i].support[k++]=s;
627 if (o_mod && (
i > 0))
629 if (i_mod && (
i+1 <
n))
634 for (
int i=o_ch.lst();
i>=o_ch.fst();
i--) {
643 if (o_state(
i,s.
edges[
d]).o_deg == 0) {
656 layers[
i].support[k++]=s;
661 if (o_mod && (
i > 0))
665 a_ch.add(i_ch); i_ch.reset();
666 a_ch.add(o_ch); o_ch.reset();
678 template<
class View,
class Val,
class Degree,
class StateIdx>
690 assert(
x.size() > 0);
691 for (
int i=
x.size();
i--; ) {
698 return p->initialize(home,
x,dfa);
701 template<
class View,
class Val,
class Degree,
class StateIdx>
708 max_states(
p.max_states), n_states(
p.n_states), n_edges(
p.n_edges) {
709 c.update(home,share,
p.c);
711 layers[
n].n_states =
p.layers[
n].n_states;
712 layers[
n].states = NULL;
716 for (
int i=
n;
i--; ) {
717 layers[
i].x.update(home,share,
p.layers[
i].x);
718 assert(layers[
i].
x.size() ==
p.layers[
i].size);
719 layers[
i].size =
p.layers[
i].size;
722 layers[
i].support[j].
val =
p.layers[
i].support[j].val;
723 layers[
i].support[j].n_edges =
p.layers[
i].support[j].n_edges;
724 assert(layers[
i].support[j].n_edges > 0);
725 layers[
i].support[j].edges =
727 layers[
i].support[j].n_edges);
728 edges += layers[
i].support[j].n_edges;
730 layers[
i].n_states =
p.layers[
i].n_states;
731 layers[
i].states = NULL;
736 template<
class View,
class Val,
class Degree,
class StateIdx>
743 template<
class View,
class Val,
class Degree,
class StateIdx>
749 while (layers[k].
size == 1) {
750 assert(layers[k].support[0].n_edges == 1);
751 n_states -= layers[k].n_states;
765 n_edges -= static_cast<unsigned int>(k);
779 assert((f >= 0) && (
l <=
n));
782 StateIdx* i_map =
r.alloc<StateIdx>(max_states);
784 StateIdx* o_map =
r.alloc<StateIdx>(max_states);
788 n_states -= layers[
l].n_states;
790 for (StateIdx j=0; j<layers[
l].n_states; j++)
791 if ((layers[
l].states[j].i_deg != 0) ||
792 (layers[
l].states[j].o_deg != 0)) {
793 layers[
l].states[i_n]=layers[
l].states[j];
796 layers[
l].n_states = i_n;
797 n_states += layers[
l].n_states;
809 for (
int i=
l-1;
i>=f;
i--) {
811 std::swap(o_map,i_map); i_n=0;
813 n_states -= layers[
i].n_states;
814 for (StateIdx j=0; j<layers[
i].n_states; j++)
815 if ((layers[
i].states[j].o_deg != 0) ||
816 (layers[
i].states[j].i_deg != 0)) {
817 layers[
i].states[i_n]=layers[
i].states[j];
820 layers[
i].n_states = i_n;
821 n_states += layers[
i].n_states;
837 Support& s = layers[f-1].support[j];
863 switch (t_state_idx) {
919 switch (t_state_idx) {
bool empty(void) const
Test whether actor link is empty (points to itself)
int fst(void) const
Return first position.
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.
void audit(void)
Perform consistency check on data structures.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
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.
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.
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.
Gecode::FloatVal c(-8, 8)
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.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
void operator++(void)
Move to next supported value.
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)
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.
LayeredGraph(Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
Constructor for cloning p.
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.
struct Gecode::@511::NNF::@54::@56 a
For atomic nodes.
Boolean integer variables.
Domain consistent layered graph (regular) propagator.
LayerValues(void)
Default constructor.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
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.
Node * x
Pointer to corresponding Boolean expression node.
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.
IndexRange(void)
Initialize range as empty.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Iterator for DFA transitions (sorted by symbols)
Propagation has not computed fixpoint.
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)
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.
int val(void) const
Return supported value.
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Gecode::Support::IntTypeTraits< Val >::utype ValSize
Type for support size.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
Boolean view for Boolean variables.