Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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>
42
43namespace 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>
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);
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
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
int a
Coefficient.
Definition linear.hh:1339
Range iterator for integer views.
Definition view.hpp:54
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:1162
void post(Home home, Term< IntView > *t, int n, IntRelType irt, int c, IntPropLevel=IPL_DEF)
Post propagator for linear constraint over integers.
Definition int-post.cpp:219
#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:941
@ IPL_BND
Bounds propagation.
Definition int.hh:993
Global cardinality propagators (Counting)
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
Finite domain integers.
unsigned int size(I &i)
Size of all ranges of range iterator i.
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773