Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
post.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  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2004/2005
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/int/linear.hh>
41 #include <gecode/int/distinct.hh>
42 
43 namespace Gecode { namespace Int { namespace GCC {
44 
45  template<class Card>
47  class CardLess : public Support::Less<Card> {
48  public:
49  bool operator ()(const Card& x, const Card& y) {
50  return x.card() < y.card();
51  }
52  };
53 
58  template<class Card>
61  CardLess<Card> cl;
62  Support::quicksort(&k[0], k.size(), cl);
63  Region r;
64 
65  {
66  int smin = 0;
67  int smax = 0;
68  for (int i = k.size(); i--; ) {
69  GECODE_ME_CHECK((k[i].gq(home, 0)));
70  GECODE_ME_CHECK((k[i].lq(home, x.size())));
71  smin += k[i].min();
72  smax += k[i].max();
73  }
74 
75  // not enough variables to satisfy min req
76  if ((x.size() < smin) || (smax < x.size()))
77  return ES_FAILED;
78  }
79 
80  // Remove all values from the x that are not in v
81  {
82  int* v = r.alloc<int>(k.size());
83  for (int i=k.size(); i--;)
84  v[i]=k[i].card();
86  for (int i=x.size(); i--; ) {
87  Iter::Values::Array iv(v,k.size());
88  GECODE_ME_CHECK(x[i].inter_v(home, iv, false));
89  }
90  }
91 
92  // Remove all values with 0 max occurrence
93  // and remove corresponding occurrence variables from k
94  {
95  // The number of zeroes
96  int n_z = 0;
97  for (int i=k.size(); i--;)
98  if (k[i].max() == 0)
99  n_z++;
100 
101  if (n_z > 0) {
102  int* z = r.alloc<int>(n_z);
103  n_z = 0;
104  int n_k = 0;
105  for (int i=0; i<k.size(); i++)
106  if (k[i].max() == 0) {
107  z[n_z++] = k[i].card();
108  } else {
109  k[n_k++] = k[i];
110  }
111  k.size(n_k);
112  Support::quicksort(z,n_z);
113  for (int i=x.size(); i--;) {
114  Iter::Values::Array zi(z,n_z);
115  GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
116  }
117  }
118  }
119 
120  if (Card::propagate) {
122  for (int i = k.size(); i--; ) {
123  t[i].a=1; t[i].x=k[i].base();
124  }
125  Linear::post(home,t,k.size(),IRT_EQ,x.size(),IPL_BND);
126  }
127 
128  return ES_OK;
129  }
130 
131 
136  template<class Card>
137  inline bool
139  if (Card::propagate) {
140  Region r;
141  ViewRanges<IntView>* xrange = r.alloc<ViewRanges<IntView> >(x.size());
142  for (int i = x.size(); i--; ){
143  ViewRanges<IntView> iter(x[i]);
144  xrange[i] = iter;
145  }
146  Iter::Ranges::NaryUnion drl(r, &xrange[0], x.size());
147  if (static_cast<unsigned int>(k.size()) == Iter::Ranges::size(drl)) {
148  for (int i=k.size(); i--;)
149  if (k[i].min() != 1 || k[i].max() != 1)
150  return false;
151  return true;
152  } else {
153  return false;
154  }
155  } else {
156  for (int i=k.size(); i--;)
157  if (k[i].min() != 0 || k[i].max() != 1)
158  return false;
159  return true;
160  }
161  }
162 
163 }}}
164 
165 // STATISTICS: int-prop
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Home class for posting propagators
Definition: core.hpp:856
Sort by increasing cardinality
Definition: post.hpp:47
bool operator()(const Card &x, const Card &y)
Definition: post.hpp:49
Class for describing linear term .
Definition: linear.hh:1336
Range iterator for integer variable views
Definition: int.hpp:246
Range iterator for union of iterators.
Value iterator for array of integers
Handle to region.
Definition: region.hpp:55
Comparison class for sorting using <.
Definition: sort.hpp:161
View arrays.
Definition: array.hpp:253
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1156
ExecStatus
Definition: core.hpp:472
@ ES_OK
Execution is okay.
Definition: core.hpp:476
@ ES_FAILED
Execution has resulted in failure.
Definition: core.hpp:474
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
void post(Home home, Term< BoolView > *t, int n, IntRelType irt, IntView x, int c, IntPropLevel)
Post propagator for linear constraint over Booleans.
Definition: bool-post.cpp:589
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
@ IRT_EQ
Equality ( )
Definition: int.hh:926
@ IPL_BND
Bounds propagation.
Definition: int.hh:978
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition: post.hpp:138
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition: post.hpp:60
unsigned int size(I &i)
Size of all ranges of range iterator i.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259