Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.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  * Last modified:
16  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
17  * $Revision: 13068 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <gecode/int/linear.hh>
45 #include <gecode/int/distinct.hh>
46 
47 namespace Gecode { namespace Int { namespace GCC {
48 
49  template<class Card>
51  class CardLess : public Support::Less<Card> {
52  public:
53  bool operator ()(const Card& x, const Card& y) {
54  return x.card() < y.card();
55  }
56  };
57 
62  template<class Card>
65  CardLess<Card> cl;
66  Support::quicksort(&k[0], k.size(), cl);
67  Region r(home);
68 
69  {
70  int smin = 0;
71  int smax = 0;
72  for (int i = k.size(); i--; ) {
73  GECODE_ME_CHECK((k[i].gq(home, 0)));
74  GECODE_ME_CHECK((k[i].lq(home, x.size())));
75  smin += k[i].min();
76  smax += k[i].max();
77  }
78 
79  // not enough variables to satisfy min req
80  if ((x.size() < smin) || (smax < x.size()))
81  return ES_FAILED;
82  }
83 
84  // Remove all values from the x that are not in v
85  {
86  int* v = r.alloc<int>(k.size());
87  for (int i=k.size(); i--;)
88  v[i]=k[i].card();
89  Support::quicksort(v,k.size());
90  for (int i=x.size(); i--; ) {
91  Iter::Values::Array iv(v,k.size());
92  GECODE_ME_CHECK(x[i].inter_v(home, iv, false));
93  }
94  }
95 
96  // Remove all values with 0 max occurrence
97  // and remove corresponding occurrence variables from k
98  {
99  // The number of zeroes
100  int n_z = 0;
101  for (int i=k.size(); i--;)
102  if (k[i].max() == 0)
103  n_z++;
104 
105  if (n_z > 0) {
106  int* z = r.alloc<int>(n_z);
107  n_z = 0;
108  int n_k = 0;
109  for (int i=0; i<k.size(); i++)
110  if (k[i].max() == 0) {
111  z[n_z++] = k[i].card();
112  } else {
113  k[n_k++] = k[i];
114  }
115  k.size(n_k);
116  Support::quicksort(z,n_z);
117  for (int i=x.size(); i--;) {
118  Iter::Values::Array zi(z,n_z);
119  GECODE_ME_CHECK(x[i].minus_v(home,zi,false));
120  }
121  }
122  }
123 
124  if (Card::propagate) {
126  for (int i = k.size(); i--; ) {
127  t[i].a=1; t[i].x=k[i].base();
128  }
129  Linear::post(home,t,k.size(),IRT_EQ,x.size(),ICL_BND);
130  }
131 
132  return ES_OK;
133  }
134 
135 
140  template<class Card>
141  inline bool
143  if (Card::propagate) {
144  Region r(home);
146  for (int i = x.size(); i--; ){
147  ViewRanges<IntView> iter(x[i]);
148  xrange[i] = iter;
149  }
150  Iter::Ranges::NaryUnion drl(r, &xrange[0], x.size());
151  if (static_cast<unsigned int>(k.size()) == Iter::Ranges::size(drl)) {
152  for (int i=k.size(); i--;)
153  if (k[i].min() != 1 || k[i].max() != 1)
154  return false;
155  return true;
156  } else {
157  return false;
158  }
159  } else {
160  for (int i=k.size(); i--;)
161  if (k[i].min() != 0 || k[i].max() != 1)
162  return false;
163  return true;
164  }
165  }
166 
167 }}}
168 
169 // STATISTICS: int-prop
NodeType t
Type of node.
Definition: bool-expr.cpp:234
void post(Home home, Term< BoolView > *t, int n, IntRelType irt, IntView x, int c, IntConLevel)
Post propagator for linear constraint over Booleans.
Definition: bool-post.cpp:608
int a
Coefficient.
Definition: linear.hh:1313
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
Value iterator for array of integers
Comparison class for sorting using <.
Definition: sort.hpp:165
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
bool operator()(const Card &x, const Card &y)
Definition: post.hpp:53
Range iterator for integer variable views
Definition: int.hpp:236
Handle to region.
Definition: region.hpp:61
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
bool isDistinct(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition: post.hpp:142
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition: post.hpp:64
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
Equality ( )
Definition: int.hh:904
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Range iterator for union of iterators.
unsigned int size(I &i)
Size of all ranges of range iterator i.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
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
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ExecStatus
Definition: core.hpp:523
Execution is okay.
Definition: core.hpp:527
Class for describing linear term .
Definition: linear.hh:1310
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Bounds propagation or consistency.
Definition: int.hh:939
Gecode toplevel namespace
Sort by increasing cardinality
Definition: post.hpp:51
Home class for posting propagators
Definition: core.hpp:717