44 namespace Gecode {
namespace Int {
namespace GCC {
96 bool type(
void)
const;
106 int index(
void)
const;
126 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;
377 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) {
1222 if ((mub != NULL) && (v != mub->
getVal()->
val)) {
1230 if (v != vln->
val) {
1239 if (vln->
val != v) {
1258 while (e != NULL && (e->
getVal()->
val < xiter.
val())) {
1286 if ((mub != NULL) && mub->
deleted()) {
1292 if ((mlb != NULL) && mlb->
deleted()) {
1303 for (
int i = n_val;
i--; ) {
1304 if ((k[
i].
min() > vals[
i]->noe) && (k[
i].counter() == 0))
1306 vals[
i]->index(n_var +
i);
1310 while (!re.
empty()) {
1315 if (!vrn->
matched(
UBC) && !augmenting_path<UBC>(home,vrn))
1320 if (!augmenting_path<LBC>(home,vln))
1329 template<
class Card>
template<BC bc>
1333 for (
int i = n_var;
i--; )
1334 if (vars[
i]->noe == 1) {
1335 ValNode*
v = vars[
i]->first()->getVal();
1336 vars[
i]->first()->free(bc);
1341 for (
int i = n_val;
i--; ) {
1343 if (Card::propagate && (k[
i].counter() == 0))
1346 if (Card::propagate)
1357 if (Card::propagate)
1364 if (vrn->
noe == 1) {
1367 int vi= vrn->
index();
1370 vars[vi] = vars[--n_var];
1371 vars[vi]->index(vi);
1376 }
else if (delall) {
1387 if (sum_min >= k[vidx].
min())
1388 sum_min -= k[vidx].min();
1389 if (sum_max >= k[vidx].
max())
1390 sum_max -= k[vidx].max();
1392 }
else if (v->
kcount() > 0) {
1397 for (
int i = n_var;
i--; )
1400 for (
int i = n_val;
i--; ) {
1401 if (vals[
i]->noe == 0) {
1402 vals[
i]->cap(
UBC,0);
1403 vals[
i]->cap(
LBC,0);
1406 vals[
i]->index(n_var +
i);
1409 for (
int i = n_var;
i--; )
1410 if (vars[
i]->noe > 1)
1411 for (
Edge* e = vars[
i]->first(); e != NULL; e = e->
next())
1412 if (!e->matched(bc) && !e->used(bc)) {
1421 template<
class Card>
template<BC bc>
1426 BitSet visited(r,static_cast<unsigned int>(n_node));
1433 bool sp = sn->type();
1438 for (
int i = n_node;
i--; )
1440 vals[
i-n_var]->inedge(NULL);
1441 start[
i] = vals[
i-n_var]->first();
1443 vars[
i]->inedge(NULL);
1444 start[
i] = vars[
i]->first();
1449 visited.
set(static_cast<unsigned int>(v->
index()));
1450 while (!ns.
empty()) {
1453 if (v->
type() == sp) {
1454 e = start[v->
index()];
1455 while ((e != NULL) && e->
matched(bc))
1458 e = start[v->
index()];
1459 while ((e != NULL) && !e->
matched(bc))
1461 start[v->
index()] = e;
1466 if (!visited.
get(static_cast<unsigned int>(w->
index()))) {
1468 bool m = w->
type() ?
1469 static_cast<ValNode*
>(w)->matched(bc) :
1470 static_cast<VarNode*
>(w)->matched(bc);
1471 if (!m && w->
type() != sp) {
1472 if (v->
inedge() != NULL) {
1484 visited.
set(static_cast<unsigned int>(w->
index()));
1495 bool pathfound = !ns.
empty();
1497 while (!ns.
empty()) {
1501 if (t->
type() != sp) {
1513 template<
class Card>
template<BC bc>
1519 for (
int i = n_val;
i--; )
1520 for (
Edge* e = vals[
i]->first(); e != NULL ; e = e->
vnext())
1521 if (!e->getVar()->matched(bc) && !vals[
i]->matched(bc)) {
1522 e->match(bc); card_match++;
1528 if (card_match < sum_min) {
1532 for (
int i = n_val;
i--; )
1533 if (!vals[
i]->matched(
LBC))
1536 while (!free.
empty()) {
1539 if (augmenting_path<LBC>(home,v))
1551 if (card_match < n_var) {
1555 for (
int i = n_var;
i--; )
1556 if (!vars[
i]->matched(
UBC))
1559 while (!free.
empty()) {
1561 if (!v->
matched(
UBC) && augmenting_path<UBC>(home,
v))
1577 template<
class Card>
template<BC bc>
1582 BitSet visited(r,static_cast<unsigned int>(n_node));
1589 for (
int i = n_var;
i--; )
1590 if (!vars[
i]->matched(
LBC)) {
1592 visited.
set(static_cast<unsigned int>(vars[i]->index()));
1594 for (
int i = n_val;
i--; )
1595 if (!vals[
i]->matched(
LBC)) {
1597 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1603 for (
int i = n_val;
i--; )
1604 if (!vals[
i]->matched(
UBC)) {
1606 visited.
set(static_cast<unsigned int>(vals[i]->index()));
1612 while (!ns.
empty()) {
1618 for (
Edge* cur = vln->
first(); cur != NULL; cur = cur->
vnext()) {
1619 VarNode* mate = cur->getVar();
1622 if (cur->matched(
LBC)) {
1625 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1627 visited.
set(static_cast<unsigned int>(mate->
index()));
1632 if (!cur->matched(
UBC)) {
1635 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1637 visited.
set(static_cast<unsigned int>(mate->
index()));
1652 for (
Edge* cur = vrn->
first(); cur != NULL; cur = cur->
next()) {
1653 ValNode* mate = cur->getVal();
1654 if (!cur->matched(
LBC)) {
1656 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1658 visited.
set(static_cast<unsigned int>(mate->
index()));
1670 if (!visited.
get(static_cast<unsigned int>(mate->
index()))) {
1672 visited.
set(static_cast<unsigned int>(mate->
index()));
1683 template<
class Card>
template<BC bc>
1690 int v_index = v->
index();
1691 dfsnum[v_index] =
count;
1692 inscc.
set(static_cast<unsigned int>(v_index));
1693 in_unfinished.
set(static_cast<unsigned int>(v_index));
1701 m = v->
type() ? e->matched(
LBC) : !e->matched(
LBC);
1704 m = v->
type() ? !e->matched(
UBC) : e->matched(
UBC);
1710 int w_index = w->
index();
1712 assert(w_index < n_node);
1713 if (!inscc.
get(static_cast<unsigned int>(w_index))) {
1716 dfs<bc>(w, inscc, in_unfinished, dfsnum,
1718 }
else if (in_unfinished.
get(static_cast<unsigned int>(w_index))) {
1724 assert(roots.
top()->index() < n_node);
1725 while (dfsnum[roots.
top()->index()] > dfsnum[w_index]) {
1732 if (v == roots.
top()) {
1733 while (v != unfinished.
top()) {
1737 in_unfinished.
clear(static_cast<unsigned int>(w->
index()));
1740 assert(v == unfinished.
top());
1741 in_unfinished.
clear(static_cast<unsigned int>(v_index));
1747 template<
class Card>
template<BC bc>
1751 BitSet inscc(r,static_cast<unsigned int>(n_node));
1752 BitSet in_unfinished(r,static_cast<unsigned int>(n_node));
1753 int* dfsnum = r.
alloc<
int>(n_node);
1755 for (
int i = n_node;
i--; )
1762 for (
int i = n_var;
i--; )
1763 dfs<bc>(vars[
i], inscc, in_unfinished, dfsnum,
1764 roots, unfinished, count);
1767 template<
class Card>
1770 return home.ralloc(t);