44 namespace Gecode {
namespace Int {
namespace GCC {
95 bool type(
void)
const;
106 int index(
void)
const;
125 static void*
operator new(
size_t s,
Space& home);
128 static void operator delete(
void*,
Space&) {};
130 static void operator delete(
void*) {};
227 bool sink(
void)
const;
231 int kmin(
void)
const;
233 int kmax(
void)
const;
251 int cap(
BC bc)
const;
376 static void*
operator new(
size_t s,
Space& home);
379 static void operator delete(
void*,
Space&) {};
381 static void operator delete(
void*) {};
500 void*
operator new(
size_t t,
Space& home);
502 void operator delete(
void*,
Space&) {}
515 : e(NULL), fst(NULL), lst(NULL), ie(NULL), idx(i),
516 nf(static_cast<unsigned char>(nf0)), noe(0) {}
564 Node::operator
new(
size_t s,
Space& home) {
565 return home.ralloc(s);
579 Node(NF_NONE,x), ubm(NULL), lbm(NULL) {}
634 int kidx,
int kshift,
int count) :
635 Node(NF_VAL,kshift), _klb(min), _kub(max), _kidx(kidx), _kcount(count),
637 lb(min), ublow(max), ub(max),
823 if (
this == x->
first()) {
829 if (
this == x->
last())
833 Edge* pv = prev_vedge;
834 Edge* nv = next_vedge;
840 if (
this == v->
first()) {
845 if (
this == v->
last())
852 next_edge(NULL), prev_edge(NULL),
853 next_vedge(NULL), prev_vedge(NULL), ef(EF_NONE) {}
872 return (ef & EF_MRKUB) != 0;
874 return (ef & EF_MRKLB) != 0;
977 return (ef & EF_UM) != 0;
979 return (ef & EF_LM) != 0;
995 return (ef & EF_DEL) != 0;
999 Edge::operator
new(
size_t s,
Space& home) {
1000 return home.ralloc(s);
1008 template<
class Card>
1014 n_node(n_var + n_val),
1018 unsigned int noe = 0;
1019 for (
int i=x.
size();
i--; )
1025 for (
int i = n_val;
i--; ) {
1026 int kmi = k[
i].min();
1027 int kma = k[
i].max();
1028 int kc = k[
i].counter();
1038 vals[
i] =
new (home)
1041 vals[
i] =
new (home)
1046 for (
int i = n_var;
i--; ) {
1054 while(vals[j]->val < xi.val())
1056 *xadjacent =
new (home)
Edge(vars[i],vals[j]);
1058 if (vars[i]->first() == NULL)
1059 vars[i]->first(*xadjacent);
1061 vars[
i]->
last(*xadjacent);
1064 if (vals[j]->first() == NULL) {
1065 vals[j]->
first(*xadjacent);
1066 vals[j]->
last(*xadjacent);
1069 vals[j]->
first(*xadjacent);
1074 xadjacent = (*xadjacent)->
next_ref();
1081 template<
class Card>
1086 for (
int i = n_val;
i--; ) {
1101 assert(vrn->
noe == 1);
1103 int vi = vrn->
index();
1106 vars[vi] = vars[--n_var];
1107 vars[vi]->index(vi);
1114 int vidx = vln->
kindex();
1115 if (Card::propagate)
1118 k[vidx].counter(k[vidx].
min());
1124 if (sum_min >= k[vidx].
min())
1125 sum_min -= k[vidx].min();
1126 if (sum_max >= k[vidx].
max())
1127 sum_max -= k[vidx].max();
1130 vals[
i]->cap(
UBC,0);
1131 vals[
i]->cap(
LBC,0);
1137 if (Card::propagate && (k[
i].counter() == 0))
1141 for (
int i = n_val;
i--; )
1142 vals[
i]->index(n_var +
i);
1147 template<
class Card>
1156 if (Card::propagate) {
1157 for (
int i = n_val;
i--; ) {
1165 int rm = v->
kmax() - k[
i].max();
1168 if ((k[
i].
max() != k[
i].counter()) || (k[
i].
max() == 0)) {
1174 if (inc_ubc <= k[
i].
max()) {
1179 v->
cap(
LBC, k[
i].max() - inc_lbc);
1187 v->
cap(
LBC,k[
i].max() - (inc_lbc));
1192 if (inc_lbc < k[
i].
min() && v->
noe > 0) {
1198 for (
int i = n_var;
i--; ) {
1199 Edge* mub = vars[
i]->get_match(
UBC);
1212 assert(x.
size() == n_var);
1213 for (
int i = n_var;
i--; ) {
1216 if (static_cast<int>(x[
i].
size()) != vrn->
noe) {
1221 if ((mub != NULL) && (v != mub->
getVal()->
val)) {
1229 if (v != vln->
val) {
1238 if (vln->
val != v) {
1255 while (e != NULL && (e->
getVal()->
val < xiter.
val())) {
1283 if ((mub != NULL) && mub->
deleted()) {
1289 if ((mlb != NULL) && mlb->
deleted()) {
1300 for (
int i = n_val;
i--; ) {
1301 if ((k[
i].
min() > vals[
i]->noe) && (k[
i].counter() == 0))
1303 vals[
i]->index(n_var +
i);
1307 while (!re.
empty()) {
1312 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(home,vrn))
1317 if (!augmenting_path<LBC>(home,vln))
1326 template<
class Card>
template<BC bc>
1330 for (
int i = n_var;
i--; )
1331 if (vars[
i]->noe == 1) {
1332 ValNode*
v = vars[
i]->first()->getVal();
1333 vars[
i]->first()->free(bc);
1338 for (
int i = n_val;
i--; ) {
1340 if (Card::propagate && (k[
i].counter() == 0))
1343 if (Card::propagate)
1354 if (Card::propagate)
1361 if (vrn->
noe == 1) {
1364 int vi= vrn->
index();
1367 vars[vi] = vars[--n_var];
1368 vars[vi]->index(vi);
1373 }
else if (delall) {
1384 if (sum_min >= k[vidx].
min())
1385 sum_min -= k[vidx].min();
1386 if (sum_max >= k[vidx].
max())
1387 sum_max -= k[vidx].max();
1389 }
else if (v->
kcount() > 0) {
1394 for (
int i = n_var;
i--; )
1397 for (
int i = n_val;
i--; ) {
1398 if (vals[
i]->noe == 0) {
1399 vals[
i]->cap(
UBC,0);
1400 vals[
i]->cap(
LBC,0);
1403 vals[
i]->index(n_var +
i);
1406 for (
int i = n_var;
i--; ) {
1407 if (vars[
i]->noe > 1) {
1408 for (
Edge* e = vars[
i]->first(); e != NULL; e = e->
next()) {
1409 if (!e->matched(bc) && !e->used(bc)) {
1420 template<
class Card>
template<BC bc>
1425 BitSet visited(r,static_cast<unsigned int>(n_node));
1432 bool sp = sn->type();
1437 for (
int i = n_node;
i--; )
1439 vals[
i-n_var]->inedge(NULL);
1440 start[
i] = vals[
i-n_var]->first();
1442 vars[
i]->inedge(NULL);
1443 start[
i] = vars[
i]->first();
1448 visited.
set(static_cast<unsigned int>(v->
index()));
1449 while (!ns.
empty()) {
1452 if (v->
type() == sp) {
1453 e = start[v->
index()];
1454 while ((e != NULL) && e->
matched(bc))
1457 e = start[v->
index()];
1458 while ((e != NULL) && !e->
matched(bc))
1460 start[v->
index()] = e;
1465 if (!visited.
get(static_cast<unsigned int>(w->
index()))) {
1467 bool m = w->
type() ?
1468 static_cast<ValNode*
>(w)->matched(bc) :
1469 static_cast<VarNode*
>(w)->matched(bc);
1470 if (!m && w->
type() != sp) {
1471 if (v->
inedge() != NULL) {
1483 visited.
set(static_cast<unsigned int>(w->
index()));
1494 bool pathfound = !ns.
empty();
1496 while (!ns.
empty()) {
1500 if (t->
type() != sp) {
1512 template<
class Card>
template<BC bc>
1518 for (
int i = n_val;
i--; )
1519 for (
Edge* e = vals[
i]->first(); e != NULL ; e = e->
vnext())
1520 if (!e->getVar()->matched(bc) && !vals[
i]->matched(bc)) {
1521 e->match(bc); card_match++;
1527 if (card_match < sum_min) {
1531 for (
int i = n_val;
i--; )
1532 if (!vals[
i]->matched(
LBC))
1535 while (!free.
empty()) {
1538 if (augmenting_path<LBC>(home,v))
1550 if (card_match < n_var) {
1554 for (
int i = n_var;
i--; )
1555 if (!vars[
i]->matched(
UBC))
1558 while (!free.
empty()) {
1560 if (!v->
matched(
UBC) && augmenting_path<UBC>(home,
v))
1576 template<
class Card>
template<BC bc>
1581 BitSet visited(r,static_cast<unsigned int>(n_node));
1588 for (
int i = n_var;
i--; )
1589 if (!vars[
i]->matched(
LBC)) {
1591 visited.
set(static_cast<unsigned int>(vars[i]->index()));
1593 for (
int i = n_val;
i--; )
1594 if (!vals[
i]->matched(
LBC)) {
1596 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1602 for (
int i = n_val;
i--; )
1603 if (!vals[
i]->matched(
UBC)) {
1605 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1611 while (!ns.
empty()) {
1617 for (
Edge* cur = vln->
first(); cur != NULL; cur = cur->
vnext()) {
1618 VarNode* mate = cur->getVar();
1621 if (cur->matched(
LBC)) {
1624 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1626 visited.
set(static_cast<unsigned int>(mate->
index()));
1631 if (!cur->matched(
UBC)) {
1634 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1636 visited.
set(static_cast<unsigned int>(mate->
index()));
1651 for (
Edge* cur = vrn->
first(); cur != NULL; cur = cur->
next()) {
1652 ValNode* mate = cur->getVal();
1653 if (!cur->matched(
LBC)) {
1655 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1657 visited.
set(static_cast<unsigned int>(mate->
index()));
1669 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1671 visited.
set(static_cast<unsigned int>(mate->
index()));
1682 template<
class Card>
template<BC bc>
1689 int v_index = v->
index();
1690 dfsnum[v_index] =
count;
1691 inscc.
set(static_cast<unsigned int>(v_index));
1692 in_unfinished.
set(static_cast<unsigned int>(v_index));
1700 m = v->
type() ? e->matched(
LBC) : !e->matched(
LBC);
1703 m = v->
type() ? !e->matched(
UBC) : e->matched(
UBC);
1709 int w_index = w->
index();
1711 assert(w_index < n_node);
1712 if (!inscc.
get(static_cast<unsigned int>(w_index))) {
1715 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1717 }
else if (in_unfinished.
get(static_cast<unsigned int>(w_index))) {
1723 assert(roots.
top()->index() < n_node);
1724 while (dfsnum[roots.
top()->index()] > dfsnum[w_index]) {
1731 if (v == roots.
top()) {
1732 while (v != unfinished.
top()) {
1736 in_unfinished.
clear(static_cast<unsigned int>(w->
index()));
1739 assert(v == unfinished.
top());
1740 in_unfinished.
clear(static_cast<unsigned int>(v_index));
1746 template<
class Card>
template<BC bc>
1750 BitSet inscc(r,static_cast<unsigned int>(n_node));
1751 BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
1752 int* dfsnum = r.
alloc<
int>(n_node);
1754 for (
int i = n_node;
i--; )
1761 for (
int i = n_var;
i--; )
1762 dfs<bc>(vars[
i], inscc, in_unfinished, dfsnum,
1763 roots, unfinished, count);
1766 template<
class Card>
1769 return home.ralloc(
t);