this repo has no description
dekker.one
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
43namespace Gecode { namespace Int { namespace GCC {
44
45 template<class Card>
46 /// %Sort by increasing cardinality
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
54 /**
55 * \brief Post side constraints for the GCC
56 *
57 */
58 template<class Card>
59 ExecStatus
60 postSideConstraints(Home home, ViewArray<IntView>& x, ViewArray<Card>& k) {
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();
85 Support::quicksort(v,k.size());
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) {
121 Linear::Term<IntView>* t = r.alloc<Linear::Term<IntView> >(k.size());
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
132 /**
133 * \brief Check if GCC is equivalent to distinct
134 *
135 */
136 template<class Card>
137 inline bool
138 isDistinct(ViewArray<IntView>& x, ViewArray<Card>& k) {
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