Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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 
34 namespace Gecode { namespace Int { namespace Sorted {
35 
39  class Rank {
40  public:
42  int min;
44  int max;
45  };
46 
53  class SccComponent {
54  public:
56  int leftmost;
58  int left;
60  int right;
62  int rightmost;
63  };
64 
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 
118  public:
120  int root;
122  int parent;
124  int rank;
126  int name;
134  int iset;
136  int succ;
138  int pred;
139  };
140 
146  class OfflineMin {
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>
260  class TupleMaxInc {
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 
318  template<class View>
319  class TupleMinInc {
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:
335  View x;
336  View z;
337  };
338 
349  template<class View>
351  public:
352  bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
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 
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 
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
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:546
Post propagator for SetVar x
Definition: set.hh:767
Pair of views.
Definition: sortsup.hpp:333
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
TupleMaxIncExt(const ViewArray< View > &x0, const ViewArray< View > &z0)
Definition: sortsup.hpp:290
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
int iset
Initial set label.
Definition: sortsup.hpp:134
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
const int * pi[]
Definition: photo.cpp:14262
void makeset(void)
Initialization of the datastructure.
Definition: sortsup.hpp:227
int find(int x)
Definition: sortsup.hpp:186
unsigned int size(I &i)
Size of all ranges of range iterator i.
const int small[]
Small Photo example.
Definition: photo.cpp:192
ViewArray< View > x
Definition: sortsup.hpp:262
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
bool operator()(const int i, const int j)
Definition: sortsup.hpp:292
int max
stores the mininmum of a variable
Definition: sortsup.hpp:44
Computation spaces.
Definition: core.hpp:1742
int min
stores the mininmum of a variable
Definition: sortsup.hpp:42
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:38
bool assigned(void) const
Test whether view is assigned.
Definition: var.hpp:111
ViewArray< View > z
Definition: sortsup.hpp:288
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
ViewArray< View > x
Definition: sortsup.hpp:287
int succ
Successor in the Offline-Min sequence.
Definition: sortsup.hpp:136
int right
Direct right neighbour of an y-node in a scc.
Definition: sortsup.hpp:60
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
Definition: sortsup.hpp:78
Gecode toplevel namespace
VarImp * x
Pointer to variable implementation.
Definition: var.hpp:50
int find_pc(int x)
Definition: sortsup.hpp:196
bool operator()(const ViewPair< View > &x, const ViewPair< View > &y)
Definition: sortsup.hpp:352
Extended Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:285
OfflineMinItem & operator[](int)
Definition: sortsup.hpp:246
View z
Definition: sortsup.hpp:336
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition: sortsup.hpp:210
int name
Name or label of a set.
Definition: sortsup.hpp:126
bool operator()(const int i, const int j)
Definition: sortsup.hpp:265
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:260
View x
Definition: sortsup.hpp:335
TupleMaxInc(const ViewArray< View > &x0)
Definition: sortsup.hpp:264
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:62
int ModEvent
Type for modification events.
Definition: core.hpp:62
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
Extended view comparison on pairs of views.
Definition: sortsup.hpp:350
const int large[]
Large Photo example.
Definition: photo.cpp:202
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:117
int parent
Predecessor in the tree representation of the set.
Definition: sortsup.hpp:122
const int v[7]
Definition: distinct.cpp:259
bool operator()(const View &x, const View &y)
Definition: sortsup.hpp:321
OfflineMin(void)
Definition: sortsup.hpp:173
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
RegSimpleB rb
int rank
Ranking of the set given by its cardinality.
Definition: sortsup.hpp:124
RegSimpleA ra
View comparison on ViewTuples.
Definition: sortsup.hpp:319
int size(void)
Return the size of the Offline-Min item.
Definition: sortsup.hpp:241
#define forceinline
Definition: config.hpp:192
int root
Root node representing the set the vertex belongs to.
Definition: sortsup.hpp:120
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
Gecode::FloatVal c(-8, 8)
View arrays.
Definition: array.hpp:253
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition: sortsup.hpp:146
Gecode::IntArgs i({1, 2, 3, 4})
int pred
Predecessor in the Offline-Min sequence.
Definition: sortsup.hpp:138
Storage class for mininmum and maximum of a variable.
Definition: sortsup.hpp:39
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