Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
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  * Last modified:
10  * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
11  * $Revision: 10684 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Int { namespace Sorted {
39 
43  class Rank {
44  public:
46  int min;
48  int max;
49  };
50 
57  class SccComponent {
58  public:
60  int leftmost;
62  int left;
64  int right;
66  int rightmost;
67  };
68 
80  template<class View, bool Perm>
81  inline bool
83  bool& subsumed, int& dropfst) {
84 
85  dropfst = 0;
86  subsumed = true;
87  int xs = x.size();
88  for (int i = 0; i < xs ; i++) {
89  if (Perm) {
90  subsumed &= (x[i].assigned() &&
91  z[i].assigned() &&
92  y[z[i].val()].assigned());
93  if (subsumed) {
94  if (x[i].val() != y[z[i].val()].val()) {
95  return false;
96  } else {
97  if (z[i].val() == i) {
98  dropfst++;
99  }
100  }
101  }
102  } else {
103  subsumed &= (x[i].assigned() && y[i].assigned());
104  if (subsumed) {
105  if (x[i].val() != y[i].val()) {
106  return false;
107  } else {
108  dropfst++;
109  }
110  }
111  }
112  }
113  return true;
114  }
115 
122  public:
124  int root;
126  int parent;
128  int rank;
130  int name;
138  int iset;
140  int succ;
142  int pred;
143  };
144 
150  class OfflineMin {
151  private:
152  OfflineMinItem* sequence;
153  int* vertices;
154  int n;
155  public:
156  OfflineMin(void);
157  OfflineMin(OfflineMinItem[], int[], int);
162  int find(int x);
167  int find_pc(int x);
169  void unite(int a, int b, int c);
171  void makeset(void);
173  int size(void);
175  };
176 
178  n = 0;
179  sequence = NULL;
180  vertices = NULL;
181  }
182 
184  n = size;
185  sequence = &s[0];
186  vertices = &v[0];
187  }
188 
189  forceinline int
191  while (sequence[x].parent != x) {
192  x = sequence[x].parent;
193  }
194  // x is now the root of the tree
195  // return the set, x belongs to
196  return sequence[x].name;
197  }
198 
199  forceinline int
201  int vsize = 0;
202  while (sequence[x].parent != x) {
203  vertices[x] = x;
204  x = sequence[x].parent;
205  }
206  // x is now the root of the tree
207  for (int i = vsize; i--; ) {
208  sequence[vertices[i]].parent = x;
209  }
210  // return the set, x belongs to
211  return sequence[x].name;
212  }
213 
214  forceinline void
215  OfflineMin::unite(int a, int b, int c){
216  // c is the union of a and b
217  int ra = sequence[a].root;
218  int rb = sequence[b].root;
219  int large = rb;
220  int small = ra;
221  if (sequence[ra].rank > sequence[rb].rank) {
222  large = ra;
223  small = rb;
224  }
225  sequence[small].parent = large;
226  sequence[large].rank += sequence[small].rank;
227  sequence[large].name = c;
228  sequence[c].root = large;
229  }
230 
231  forceinline void
233  for(int i = n; i--; ){
234  OfflineMinItem& cur = sequence[i];
235  cur.rank = 0; // initially each set is empty
236  cur.name = i; // it has its own name
237  cur.root = i; // it is the root node
238  cur.parent = i; // it is its own parent
239  cur.pred = i - 1;
240  cur.succ = i + 1;
241  cur.iset = -5;
242  }
243  }
244 
245  forceinline int
247  return n;
248  }
249 
252  return sequence[i];
253  }
254 
264  template<class View>
265  class TupleMaxInc {
266  protected:
268  public:
269  TupleMaxInc(const ViewArray<View>& x0) : x(x0) {}
270  bool operator ()(const int i, const int j) {
271  if (x[i].max() == x[j].max()) {
272  return x[i].min() < x[j].min();
273  } else {
274  return x[i].max() < x[j].max();
275  }
276  }
277  };
278 
279 
289  template<class View>
291  protected:
294  public:
296  const ViewArray<View>& z0) : x(x0), z(z0) {}
297  bool operator ()(const int i, const int j) {
298  if (x[i].max() == x[j].max()) {
299  if (x[i].min() == x[j].min()) {
300  if (z[i].max() == z[j].max()) {
301  return z[i].min() < z[j].min();
302  } else {
303  return z[i].max() < z[j].max();
304  }
305  } else {
306  return x[i].min() < x[j].min();
307  }
308  } else {
309  return x[i].max() < x[j].max();
310  }
311  }
312  };
313 
323  template<class View>
324  class TupleMinInc {
325  public:
326  bool operator ()(const View& x, const View& y) {
327  if (x.min() == y.min()) {
328  return x.max() < y.max();
329  } else {
330  return x.min() < y.min();
331  }
332  }
333  };
334 
335 
337  template<class View>
338  class ViewPair {
339  public:
340  View x;
341  View z;
342  };
343 
354  template<class View>
356  public:
357  bool operator ()(const ViewPair<View>& x, const ViewPair<View>& y) {
358  if (x.x.min() == y.x.min()) {
359  if (x.x.max() == y.x.max()) {
360  if (x.z.min() == y.z.min()) {
361  return x.z.max() < y.z.max();
362  } else {
363  return x.z.min() < y.z.min();
364  }
365  } else {
366  return x.x.max() < y.x.max();
367  }
368  } else {
369  return x.x.min() < y.x.min();
370  }
371  }
372  };
373 
381  template<class View, bool Perm>
382  inline bool
385  ViewArray<View>& y,
386  ViewArray<View>& z,
387  bool& subsumed,
388  bool& match_fixed,
389  bool&,
390  bool& noperm_bc) {
391 
392  bool x_complete = true;
393  bool y_complete = true;
394  bool z_complete = true;
395 
396  for (int i = y.size(); i--; ) {
397  x_complete &= x[i].assigned();
398  y_complete &= y[i].assigned();
399  if (Perm) {
400  z_complete &= z[i].assigned();
401  }
402  }
403 
404  if (x_complete) {
405  for (int i = x.size(); i--; ) {
406  ModEvent me = y[i].eq(home, x[i].val());
407  if (me_failed(me)) {
408  return false;
409  }
410  }
411  if (Perm) {
412  subsumed = false;
413  } else {
414  subsumed = true;
415  }
416  }
417 
418  if (y_complete) {
419  bool y_equality = true;
420  for (int i = y.size() - 1; i--; ) {
421  y_equality &= (y[i].val() == y[i + 1].val());
422  }
423  if (y_equality) {
424  for (int i = x.size(); i--; ) {
425  ModEvent me = x[i].eq(home, y[i].val());
426  if (me_failed(me)) {
427  return false;
428  }
429  }
430  if (Perm) {
431  subsumed = false;
432  } else {
433  subsumed = true;
434  }
435  noperm_bc = true;
436  }
437  }
438 
439  if (Perm) {
440  if (z_complete) {
441  if (x_complete) {
442  for (int i = x.size(); i--; ) {
443  ModEvent me = y[z[i].val()].eq(home, x[i].val());
444  if (me_failed(me)) {
445  return false;
446  }
447  }
448  subsumed = true;
449  return subsumed;
450  }
451  if (y_complete) {
452  for (int i = x.size(); i--; ) {
453  ModEvent me = x[i].eq(home, y[z[i].val()].val());
454  if (me_failed(me)) {
455  return false;
456  }
457  }
458  subsumed = true;
459  return subsumed;
460  }
461 
462  // validate the permutation
463  int sum = 0;
464  for (int i = x.size(); i--; ) {
465  int pi = z[i].val();
466  if (x[i].max() < y[pi].min() ||
467  x[i].min() > y[pi].max()) {
468  return false;
469  }
470  sum += pi;
471  }
472  int n = x.size();
473  int gauss = ( (n * (n + 1)) / 2);
474  // if the sum over all assigned permutation variables is not
475  // equal to the gaussian sum - n they are not distinct, hence invalid
476  if (sum != gauss - n) {
477  return false;
478  }
479  match_fixed = true;
480  }
481  }
482  return true;
483  }
484 
492  template<class View>
493  forceinline bool
495  ViewArray<View>& z, bool& nofix) {
496  int n = x.size();
497  for (int i = n; i--; ) {
498  if (z[i].assigned()) {
499  int v = z[i].val();
500  if (x[i].assigned()) {
501  // channel equality from x to y
502  ModEvent me = y[v].eq(home, x[i].val());
503  if (me_failed(me))
504  return false;
505  nofix |= me_modified(me);
506  } else {
507  if (y[v].assigned()) {
508  // channel equality from y to x
509  ModEvent me = x[i].eq(home, y[v].val());
510  if (me_failed(me))
511  return false;
512  nofix |= me_modified(me);
513  } else {
514  // constrain upper bound
515  ModEvent me = x[i].lq(home, y[v].max());
516  if (me_failed(me))
517  return false;
518  nofix |= me_modified(me);
519 
520  // constrain lower bound
521  me = x[i].gq(home, y[v].min());
522  if (me_failed(me))
523  return false;
524  nofix |= me_modified(me);
525 
526  // constrain the sorted variable
527  // constrain upper bound
528  me = y[v].lq(home, x[i].max());
529  if (me_failed(me))
530  return false;
531  nofix |= me_modified(me);
532 
533  // constrain lower bound
534  me = y[v].gq(home, x[i].min());
535  if (me_failed(me))
536  return false;
537  nofix |= me_modified(me);
538  }
539  }
540  } else {
541  // if the permutation variable is undetermined
542  int l = z[i].min();
543  int r = z[i].max();
544  // upper bound
545  ModEvent me = x[i].lq(home, y[r].max());
546  if (me_failed(me))
547  return false;
548  nofix |= me_modified(me);
549 
550  // lower bound
551  me = x[i].gq(home, y[l].min());
552  if (me_failed(me))
553  return false;
554  nofix |= me_modified(me);
555  }
556  }
557  return true;
558  }
559 
560 
561 }}}
562 
563 
564 // STATISTICS: int-prop
TupleMaxIncExt(const ViewArray< View > &x0, const ViewArray< View > &z0)
Definition: sortsup.hpp:295
Index comparison for ViewArray.
Definition: sortsup.hpp:265
Storage class for mininmum and maximum of a variable.
Definition: sortsup.hpp:43
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
int iset
Initial set label.
Definition: sortsup.hpp:138
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:121
int ModEvent
Type for modification events.
Definition: core.hpp:146
View comparison on ViewTuples.
Definition: sortsup.hpp:324
int succ
Successor in the Offline-Min sequence.
Definition: sortsup.hpp:140
bool operator()(const int i, const int j)
Definition: sortsup.hpp:297
bool operator()(const int i, const int j)
Definition: sortsup.hpp:270
Computation spaces.
Definition: core.hpp:1362
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
Definition: sortsup.hpp:494
Gecode::FloatVal c(-8, 8)
OfflineMinItem & operator[](int)
Definition: sortsup.hpp:251
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min
stores the mininmum of a variable
Definition: sortsup.hpp:46
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
int left
Direct left neighbour of an y-node in a scc.
Definition: sortsup.hpp:62
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:66
bool check_subsumption(ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
Subsumption test.
Definition: sortsup.hpp:82
bool operator()(const ViewPair< View > &x, const ViewPair< View > &y)
Definition: sortsup.hpp:357
unsigned int size(I &i)
Size of all ranges of range iterator i.
TupleMaxInc(const ViewArray< View > &x0)
Definition: sortsup.hpp:269
View arrays.
Definition: array.hpp:234
int name
Name or label of a set.
Definition: sortsup.hpp:130
Representation of a strongly connected component.
Definition: sortsup.hpp:57
int right
Direct right neighbour of an y-node in a scc.
Definition: sortsup.hpp:64
const int v[7]
Definition: distinct.cpp:207
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Definition: subsumption.hpp:42
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
int leftmost
Leftmost y-node in a scc.
Definition: sortsup.hpp:60
int parent
Predecessor in the tree representation of the set.
Definition: sortsup.hpp:126
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int max
stores the mininmum of a variable
Definition: sortsup.hpp:48
#define forceinline
Definition: config.hpp:132
Extended Index comparison for ViewArray.
Definition: sortsup.hpp:290
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
int root
Root node representing the set the vertex belongs to.
Definition: sortsup.hpp:124
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition: sortsup.hpp:150
int rank
Ranking of the set given by its cardinality.
Definition: sortsup.hpp:128
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:383
bool operator()(const View &x, const View &y)
Definition: sortsup.hpp:326
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition: sortsup.hpp:215
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
LinFloatExpr sum(const FloatVarArgs &x)
Construct linear float expression as sum of float variables.
Definition: float-expr.cpp:548
int size(void)
Return the size of the Offline-Min item.
Definition: sortsup.hpp:246
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1429
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
void makeset(void)
Initialization of the datastructure.
Definition: sortsup.hpp:232
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58
int pred
Predecessor in the Offline-Min sequence.
Definition: sortsup.hpp:142
Extended view comparison on pairs of views.
Definition: sortsup.hpp:355