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>
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>
172 :
Advisor(home,share,a), i(a.i) {}
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;
255 m_s =
std::max(m_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)
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;
408 for (Degree d=s.
n_edges; d--; ) {
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;
456 for (Degree d=s.
n_edges; d--; ) {
457 i_state(i,s.
edges[d]).o_deg++;
458 o_state(i,s.
edges[d]).i_deg++;
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++) {
487 for (Degree d=s.
n_edges; d--; ) {
489 o_mod |= i_dec(i,s.
edges[d]);
490 i_mod |= o_dec(i,s.
edges[d]);
493 assert(layers[i].support[j].val == n);
494 layers[
i].support[0] = layers[
i].support[j++];
500 for (Degree d=s.
n_edges; d--; ) {
502 o_mod |= i_dec(i,s.
edges[d]);
503 i_mod |= o_dec(i,s.
edges[d]);
506 }
else if (layers[i].
x.any(d)) {
512 if (s.
val < static_cast<Val>(rx.min())) {
515 for (Degree d=s.
n_edges; d--; ) {
517 o_mod |= i_dec(i,s.
edges[d]);
518 i_mod |= o_dec(i,s.
edges[d]);
521 }
else if (s.
val > static_cast<Val>(rx.max())) {
524 layers[
i].support[k++]=s;
534 for (Degree d=s.
n_edges; d--; ) {
536 o_mod |= i_dec(i,s.
edges[d]);
537 i_mod |= o_dec(i,s.
edges[d]);
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++) {
552 for (Degree d=s.
n_edges; d--; ) {
554 o_mod |= i_dec(i,s.
edges[d]);
555 i_mod |= o_dec(i,s.
edges[d]);
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) {
611 o_mod |= i_dec(i,s.
edges[
d]);
612 i_mod |= o_dec(i,s.
edges[
d]);
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) {
645 o_mod |= i_dec(i,s.
edges[
d]);
646 (void) o_dec(i,s.
edges[
d]);
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--; ) {
701 template<
class View,
class Val,
class Degree,
class StateIdx>
707 n(p.
n), layers(home.alloc<
Layer>(
n+1)),
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);
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) {
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>