Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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:
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);
170  OfflineMinItem& operator [](int);
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 = vsize; i--; ) {
204  sequence[vertices[i]].parent = x;
205  }
206  // return the set, x belongs to
207  return sequence[x].name;
208  }
209 
210  forceinline void
211  OfflineMin::unite(int a, int b, int c){
212  // c is the union of a and b
213  int ra = sequence[a].root;
214  int rb = sequence[b].root;
215  int large = rb;
216  int small = ra;
217  if (sequence[ra].rank > sequence[rb].rank) {
218  large = ra;
219  small = rb;
220  }
221  sequence[small].parent = large;
222  sequence[large].rank += sequence[small].rank;
223  sequence[large].name = c;
224  sequence[c].root = large;
225  }
226 
227  forceinline void
229  for(int i = n; i--; ){
230  OfflineMinItem& cur = sequence[i];
231  cur.rank = 0; // initially each set is empty
232  cur.name = i; // it has its own name
233  cur.root = i; // it is the root node
234  cur.parent = i; // it is its own parent
235  cur.pred = i - 1;
236  cur.succ = i + 1;
237  cur.iset = -5;
238  }
239  }
240 
241  forceinline int
243  return n;
244  }
245 
248  return sequence[i];
249  }
250 
260  template<class View>
261  class TupleMaxInc {
262  protected:
264  public:
265  TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
266  bool operator ()(const int i, const int j) {
267  if (x[i].max() == x[j].max()) {
268  return x[i].min() < x[j].min();
269  } else {
270  return x[i].max() < x[j].max();
271  }
272  }
273  };
274 
275 
285  template<class View>
287  protected:
290  public:
292  const ViewArray<View>& z0) : x(x0), z(z0) {}
293  bool operator ()(const int i, const int j) {
294  if (x[i].max() == x[j].max()) {
295  if (x[i].min() == x[j].min()) {
296  if (z[i].max() == z[j].max()) {
297  return z[i].min() < z[j].min();
298  } else {
299  return z[i].max() < z[j].max();
300  }
301  } else {
302  return x[i].min() < x[j].min();
303  }
304  } else {
305  return x[i].max() < x[j].max();
306  }
307  }
308  };
309 
319  template<class View>
320  class TupleMinInc {
321  public:
322  bool operator ()(const View& x, const View& y) {
323  if (x.min() == y.min()) {
324  return x.max() < y.max();
325  } else {
326  return x.min() < y.min();
327  }
328  }
329  };
330 
331 
333  template<class View>
334  class ViewPair {
335  public:
336  View x;
337  View z;
338  };
339 
350  template<class View>
352  public:
353  bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
354  if (x.x.min() == y.x.min()) {
355  if (x.x.max() == y.x.max()) {
356  if (x.z.min() == y.z.min()) {
357  return x.z.max() < y.z.max();
358  } else {
359  return x.z.min() < y.z.min();
360  }
361  } else {
362  return x.x.max() < y.x.max();
363  }
364  } else {
365  return x.x.min() < y.x.min();
366  }
367  }
368  };
369 
377  template<class View, bool Perm>
378  inline bool
383  bool& subsumed,
384  bool& match_fixed,
385  bool&,
386  bool& noperm_bc) {
387 
388  bool x_complete = true;
389  bool y_complete = true;
390  bool z_complete = true;
391 
392  for (int i = y.size(); i--; ) {
393  x_complete &= x[i].assigned();
394  y_complete &= y[i].assigned();
395  if (Perm) {
396  z_complete &= z[i].assigned();
397  }
398  }
399 
400  if (x_complete) {
401  for (int i = x.size(); i--; ) {
402  ModEvent me = y[i].eq(home, x[i].val());
403  if (me_failed(me)) {
404  return false;
405  }
406  }
407  if (Perm) {
408  subsumed = false;
409  } else {
410  subsumed = true;
411  }
412  }
413 
414  if (y_complete) {
415  bool y_equality = true;
416  for (int i = y.size() - 1; i--; ) {
417  y_equality &= (y[i].val() == y[i + 1].val());
418  }
419  if (y_equality) {
420  for (int i = x.size(); i--; ) {
421  ModEvent me = x[i].eq(home, y[i].val());
422  if (me_failed(me)) {
423  return false;
424  }
425  }
426  if (Perm) {
427  subsumed = false;
428  } else {
429  subsumed = true;
430  }
431  noperm_bc = true;
432  }
433  }
434 
435  if (Perm) {
436  if (z_complete) {
437  if (x_complete) {
438  for (int i = x.size(); i--; ) {
439  ModEvent me = y[z[i].val()].eq(home, x[i].val());
440  if (me_failed(me)) {
441  return false;
442  }
443  }
444  subsumed = true;
445  return subsumed;
446  }
447  if (y_complete) {
448  for (int i = x.size(); i--; ) {
449  ModEvent me = x[i].eq(home, y[z[i].val()].val());
450  if (me_failed(me)) {
451  return false;
452  }
453  }
454  subsumed = true;
455  return subsumed;
456  }
457 
458  // validate the permutation
459  int sum = 0;
460  for (int i = x.size(); i--; ) {
461  int pi = z[i].val();
462  if (x[i].max() < y[pi].min() ||
463  x[i].min() > y[pi].max()) {
464  return false;
465  }
466  sum += pi;
467  }
468  int n = x.size();
469  int gauss = ( (n * (n + 1)) / 2);
470  // if the sum over all assigned permutation variables is not
471  // equal to the gaussian sum - n they are not distinct, hence invalid
472  if (sum != gauss - n) {
473  return false;
474  }
475  match_fixed = true;
476  }
477  }
478  return true;
479  }
480 
488  template<class View>
489  forceinline bool
491  ViewArray<View>& z, bool& nofix) {
492  int n = x.size();
493  for (int i = n; i--; ) {
494  if (z[i].assigned()) {
495  int v = z[i].val();
496  if (x[i].assigned()) {
497  // channel equality from x to y
498  ModEvent me = y[v].eq(home, x[i].val());
499  if (me_failed(me))
500  return false;
501  nofix |= me_modified(me);
502  } else {
503  if (y[v].assigned()) {
504  // channel equality from y to x
505  ModEvent me = x[i].eq(home, y[v].val());
506  if (me_failed(me))
507  return false;
508  nofix |= me_modified(me);
509  } else {
510  // constrain upper bound
511  ModEvent me = x[i].lq(home, y[v].max());
512  if (me_failed(me))
513  return false;
514  nofix |= me_modified(me);
515 
516  // constrain lower bound
517  me = x[i].gq(home, y[v].min());
518  if (me_failed(me))
519  return false;
520  nofix |= me_modified(me);
521 
522  // constrain the sorted variable
523  // constrain upper bound
524  me = y[v].lq(home, x[i].max());
525  if (me_failed(me))
526  return false;
527  nofix |= me_modified(me);
528 
529  // constrain lower bound
530  me = y[v].gq(home, x[i].min());
531  if (me_failed(me))
532  return false;
533  nofix |= me_modified(me);
534  }
535  }
536  } else {
537  // if the permutation variable is undetermined
538  int l = z[i].min();
539  int r = z[i].max();
540  // upper bound
541  ModEvent me = x[i].lq(home, y[r].max());
542  if (me_failed(me))
543  return false;
544  nofix |= me_modified(me);
545 
546  // lower bound
547  me = x[i].gq(home, y[l].min());
548  if (me_failed(me))
549  return false;
550  nofix |= me_modified(me);
551  }
552  }
553  return true;
554  }
555 
556 
557 }}}
558 
559 
560 // STATISTICS: int-prop
TupleMaxIncExt(const ViewArray< View > &x0, const ViewArray< View > &z0)
Definition: sortsup.hpp:291
Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:261
Storage class for mininmum and maximum of a variable.
Definition: sortsup.hpp:39
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
int iset
Initial set label.
Definition: sortsup.hpp:134
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:38
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:117
int ModEvent
Type for modification events.
Definition: core.hpp:62
const int large[]
Large Photo example.
Definition: photo.cpp:202
View comparison on ViewTuples.
Definition: sortsup.hpp:320
int succ
Successor in the Offline-Min sequence.
Definition: sortsup.hpp:136
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
Definition: sortsup.hpp:490
Gecode::FloatVal c(-8, 8)
OfflineMinItem & operator[](int)
Definition: sortsup.hpp:247
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min
stores the mininmum of a variable
Definition: sortsup.hpp:42
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int left
Direct left neighbour of an y-node in a scc.
Definition: sortsup.hpp:58
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:62
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
Definition: sortsup.hpp:78
unsigned int size(I &i)
Size of all ranges of range iterator i.
TupleMaxInc(const ViewArray< View > &x0)
Definition: sortsup.hpp:265
const int * pi[]
Definition: photo.cpp:14262
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:765
View arrays.
Definition: array.hpp:224
int name
Name or label of a set.
Definition: sortsup.hpp:126
Representation of a strongly connected component.
Definition: sortsup.hpp:53
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
int right
Direct right neighbour of an y-node in a scc.
Definition: sortsup.hpp:60
const int v[7]
Definition: distinct.cpp:259
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
int leftmost
Leftmost y-node in a scc.
Definition: sortsup.hpp:56
int parent
Predecessor in the tree representation of the set.
Definition: sortsup.hpp:122
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
int max
stores the mininmum of a variable
Definition: sortsup.hpp:44
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1420
Extended Index comparison for ViewArray<Tuple>.
Definition: sortsup.hpp:286
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:59
int root
Root node representing the set the vertex belongs to.
Definition: sortsup.hpp:120
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition: sortsup.hpp:146
int rank
Ranking of the set given by its cardinality.
Definition: sortsup.hpp:124
Post propagator for SetVar x
Definition: set.hh:765
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:379
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition: sortsup.hpp:211
Gecode toplevel namespace
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:546
const int small[]
Small Photo example.
Definition: photo.cpp:192
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1199
int size(void)
Return the size of the Offline-Min item.
Definition: sortsup.hpp:242
void makeset(void)
Initialization of the datastructure.
Definition: sortsup.hpp:228
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:54
int pred
Predecessor in the Offline-Min sequence.
Definition: sortsup.hpp:138
Extended view comparison on pairs of views.
Definition: sortsup.hpp:351