Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
sortsup.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Copyright:
7 * Patrick Pekczynski, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Int { namespace Sorted {
35
39 class Rank {
40 public:
42 int min;
44 int max;
45 };
46
54 public:
58 int left;
60 int right;
63 };
64
75
76 template<class View, bool Perm>
77 inline bool
79 bool& subsumed, int& dropfst) {
80
81 dropfst = 0;
82 subsumed = true;
83 int xs = x.size();
84 for (int i = 0; i < xs ; i++) {
85 if (Perm) {
86 subsumed &= (x[i].assigned() &&
87 z[i].assigned() &&
88 y[z[i].val()].assigned());
89 if (subsumed) {
90 if (x[i].val() != y[z[i].val()].val()) {
91 return false;
92 } else {
93 if (z[i].val() == i) {
94 dropfst++;
95 }
96 }
97 }
98 } else {
99 subsumed &= (x[i].assigned() && y[i].assigned());
100 if (subsumed) {
101 if (x[i].val() != y[i].val()) {
102 return false;
103 } else {
104 dropfst++;
105 }
106 }
107 }
108 }
109 return true;
110 }
111
116
118 public:
120 int root;
124 int rank;
126 int name;
134 int iset;
136 int succ;
138 int pred;
139 };
140
147 private:
148 OfflineMinItem* sequence;
149 int* vertices;
150 int n;
151 public:
152 OfflineMin(void);
153 OfflineMin(OfflineMinItem[], int[], int);
158 int find(int x);
163 int find_pc(int x);
165 void unite(int a, int b, int c);
167 void makeset(void);
169 int size(void);
171 };
172
174 n = 0;
175 sequence = NULL;
176 vertices = NULL;
177 }
178
180 n = size;
181 sequence = &s[0];
182 vertices = &v[0];
183 }
184
185 forceinline int
187 while (sequence[x].parent != x) {
188 x = sequence[x].parent;
189 }
190 // x is now the root of the tree
191 // return the set, x belongs to
192 return sequence[x].name;
193 }
194
195 forceinline int
197 int vsize = 0;
198 while (sequence[x].parent != x) {
199 vertices[x] = x;
200 x = sequence[x].parent;
201 }
202 // x is now the root of the tree
203 for (int i=0; i<vsize; i++)
204 sequence[vertices[i]].parent = x;
205 // return the set, x belongs to
206 return sequence[x].name;
207 }
208
209 forceinline void
210 OfflineMin::unite(int a, int b, int c){
211 // c is the union of a and b
212 int ra = sequence[a].root;
213 int rb = sequence[b].root;
214 int large = rb;
215 int small = ra;
216 if (sequence[ra].rank > sequence[rb].rank) {
217 large = ra;
218 small = rb;
219 }
220 sequence[small].parent = large;
221 sequence[large].rank += sequence[small].rank;
222 sequence[large].name = c;
223 sequence[c].root = large;
224 }
225
226 forceinline void
228 for(int i = n; i--; ){
229 OfflineMinItem& cur = sequence[i];
230 cur.rank = 0; // initially each set is empty
231 cur.name = i; // it has its own name
232 cur.root = i; // it is the root node
233 cur.parent = i; // it is its own parent
234 cur.pred = i - 1;
235 cur.succ = i + 1;
236 cur.iset = -5;
237 }
238 }
239
240 forceinline int
242 return n;
243 }
244
247 return sequence[i];
248 }
249
259 template<class View>
261 protected:
263 public:
264 TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
265 bool operator ()(const int i, const int j) {
266 if (x[i].max() == x[j].max()) {
267 return x[i].min() < x[j].min();
268 } else {
269 return x[i].max() < x[j].max();
270 }
271 }
272 };
273
274
284 template<class View>
286 protected:
289 public:
291 const ViewArray<View>& z0) : x(x0), z(z0) {}
292 bool operator ()(const int i, const int j) {
293 if (x[i].max() == x[j].max()) {
294 if (x[i].min() == x[j].min()) {
295 if (z[i].max() == z[j].max()) {
296 return z[i].min() < z[j].min();
297 } else {
298 return z[i].max() < z[j].max();
299 }
300 } else {
301 return x[i].min() < x[j].min();
302 }
303 } else {
304 return x[i].max() < x[j].max();
305 }
306 }
307 };
308
317
318 template<class View>
320 public:
321 bool operator ()(const View& x, const View& y) {
322 if (x.min() == y.min()) {
323 return x.max() < y.max();
324 } else {
325 return x.min() < y.min();
326 }
327 }
328 };
329
330
332 template<class View>
333 class ViewPair {
334 public:
337 };
338
349 template<class View>
351 public:
353 if (x.x.min() == y.x.min()) {
354 if (x.x.max() == y.x.max()) {
355 if (x.z.min() == y.z.min()) {
356 return x.z.max() < y.z.max();
357 } else {
358 return x.z.min() < y.z.min();
359 }
360 } else {
361 return x.x.max() < y.x.max();
362 }
363 } else {
364 return x.x.min() < y.x.min();
365 }
366 }
367 };
368
375
376 template<class View, bool Perm>
377 inline bool
382 bool& subsumed,
383 bool& match_fixed,
384 bool&,
385 bool& noperm_bc) {
386
387 bool x_complete = true;
388 bool y_complete = true;
389 bool z_complete = true;
390
391 for (int i=0; i<y.size(); i++) {
392 x_complete &= x[i].assigned();
393 y_complete &= y[i].assigned();
394 if (Perm) {
395 z_complete &= z[i].assigned();
396 }
397 }
398
399 if (x_complete) {
400 for (int i=0; i<x.size(); i++) {
401 ModEvent me = y[i].eq(home, x[i].val());
402 if (me_failed(me)) {
403 return false;
404 }
405 }
406 if (Perm) {
407 subsumed = false;
408 } else {
409 subsumed = true;
410 }
411 }
412
413 if (y_complete) {
414 bool y_equality = true;
415 for (int i=1; i<y.size(); i++) {
416 y_equality &= (y[i-1].val() == y[i].val());
417 }
418 if (y_equality) {
419 for (int i=0; i<x.size(); i++) {
420 ModEvent me = x[i].eq(home, y[i].val());
421 if (me_failed(me)) {
422 return false;
423 }
424 }
425 if (Perm) {
426 subsumed = false;
427 } else {
428 subsumed = true;
429 }
430 noperm_bc = true;
431 }
432 }
433
434 if (Perm) {
435 if (z_complete) {
436 if (x_complete) {
437 for (int i=0; i<x.size(); i++) {
438 ModEvent me = y[z[i].val()].eq(home, x[i].val());
439 if (me_failed(me)) {
440 return false;
441 }
442 }
443 subsumed = true;
444 return subsumed;
445 }
446 if (y_complete) {
447 for (int i=0; i<x.size(); i++) {
448 ModEvent me = x[i].eq(home, y[z[i].val()].val());
449 if (me_failed(me)) {
450 return false;
451 }
452 }
453 subsumed = true;
454 return subsumed;
455 }
456
457 // validate the permutation
458 int sum = 0;
459 for (int i=0; i<x.size(); i++) {
460 int pi = z[i].val();
461 if (x[i].max() < y[pi].min() ||
462 x[i].min() > y[pi].max()) {
463 return false;
464 }
465 sum += pi;
466 }
467 int n = x.size();
468 int gauss = ( (n * (n + 1)) / 2);
469 // if the sum over all assigned permutation variables is not
470 // equal to the gaussian sum - n they are not distinct, hence invalid
471 if (sum != gauss - n) {
472 return false;
473 }
474 match_fixed = true;
475 }
476 }
477 return true;
478 }
479
486
487 template<class View>
488 forceinline bool
490 ViewArray<View>& z, bool& nofix) {
491 int n = x.size();
492 for (int i=0; i<n; i++) {
493 if (z[i].assigned()) {
494 int v = z[i].val();
495 if (x[i].assigned()) {
496 // channel equality from x to y
497 ModEvent me = y[v].eq(home, x[i].val());
498 if (me_failed(me))
499 return false;
500 nofix |= me_modified(me);
501 } else {
502 if (y[v].assigned()) {
503 // channel equality from y to x
504 ModEvent me = x[i].eq(home, y[v].val());
505 if (me_failed(me))
506 return false;
507 nofix |= me_modified(me);
508 } else {
509 // constrain upper bound
510 ModEvent me = x[i].lq(home, y[v].max());
511 if (me_failed(me))
512 return false;
513 nofix |= me_modified(me);
514
515 // constrain lower bound
516 me = x[i].gq(home, y[v].min());
517 if (me_failed(me))
518 return false;
519 nofix |= me_modified(me);
520
521 // constrain the sorted variable
522 // constrain upper bound
523 me = y[v].lq(home, x[i].max());
524 if (me_failed(me))
525 return false;
526 nofix |= me_modified(me);
527
528 // constrain lower bound
529 me = y[v].gq(home, x[i].min());
530 if (me_failed(me))
531 return false;
532 nofix |= me_modified(me);
533 }
534 }
535 } else {
536 // if the permutation variable is undetermined
537 int l = z[i].min();
538 int r = z[i].max();
539 // upper bound
540 ModEvent me = x[i].lq(home, y[r].max());
541 if (me_failed(me))
542 return false;
543 nofix |= me_modified(me);
544
545 // lower bound
546 me = x[i].gq(home, y[l].min());
547 if (me_failed(me))
548 return false;
549 nofix |= me_modified(me);
550 }
551 }
552 return true;
553 }
554
555
556}}}
557
558
559// STATISTICS: int-prop
Item used to construct the OfflineMin sequence.
Definition sortsup.hpp:117
int pred
Predecessor in the Offline-Min sequence.
Definition sortsup.hpp:138
int root
Root node representing the set the vertex belongs to.
Definition sortsup.hpp:120
int succ
Successor in the Offline-Min sequence.
Definition sortsup.hpp:136
int rank
Ranking of the set given by its cardinality.
Definition sortsup.hpp:124
int name
Name or label of a set.
Definition sortsup.hpp:126
int parent
Predecessor in the tree representation of the set.
Definition sortsup.hpp:122
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition sortsup.hpp:210
OfflineMinItem & operator[](int)
Definition sortsup.hpp:246
void makeset(void)
Initialization of the datastructure.
Definition sortsup.hpp:227
int size(void)
Return the size of the Offline-Min item.
Definition sortsup.hpp:241
Storage class for mininmum and maximum of a variable.
Definition sortsup.hpp:39
int max
stores the mininmum of a variable
Definition sortsup.hpp:44
int min
stores the mininmum of a variable
Definition sortsup.hpp:42
Representation of a strongly connected component.
Definition sortsup.hpp:53
int leftmost
Leftmost y-node in a scc.
Definition sortsup.hpp:56
int left
Direct left neighbour of an y-node in a scc.
Definition sortsup.hpp:58
int right
Direct right neighbour of an y-node in a scc.
Definition sortsup.hpp:60
int rightmost
Rightmost reachable y-node in a scc.
Definition sortsup.hpp:62
bool operator()(const int i, const int j)
Definition sortsup.hpp:292
TupleMaxIncExt(const ViewArray< View > &x0, const ViewArray< View > &z0)
Definition sortsup.hpp:290
bool operator()(const int i, const int j)
Definition sortsup.hpp:265
TupleMaxInc(const ViewArray< View > &x0)
Definition sortsup.hpp:264
Extended view comparison on pairs of views.
Definition sortsup.hpp:350
bool operator()(const ViewPair< View > &x, const ViewPair< View > &y)
Definition sortsup.hpp:352
View comparison on ViewTuples.
Definition sortsup.hpp:319
bool operator()(const View &x, const View &y)
Definition sortsup.hpp:321
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
const int small[]
Small Photo example.
Definition photo.cpp:192
const int large[]
Large Photo example.
Definition photo.cpp:202
const int * pi[]
Definition photo.cpp:14262
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Sorted propagators
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
Definition sortsup.hpp:489
bool array_assigned(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, bool &match_fixed, bool &, bool &noperm_bc)
Check for assignment of a variable array.
Definition sortsup.hpp:378
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
Definition sortsup.hpp:78
Finite domain integers.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
LinIntExpr sum(const IntVarArgs &x)
Construct linear expression as sum of integer variables.
Definition int-expr.cpp:880
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194