this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 2011
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Set { namespace Rel {
35
36 template<class View0, class View1, ReifyMode rm, bool strict>
37 forceinline
38 ReLq<View0,View1,rm,strict>::ReLq(Home home, View0 y0, View1 y1,
39 Gecode::Int::BoolView y2)
40 : Propagator(home), x0(y0), x1(y1), b(y2) {
41 b.subscribe(home,*this, Gecode::Int::PC_INT_VAL);
42 x0.subscribe(home,*this, PC_SET_ANY);
43 x1.subscribe(home,*this, PC_SET_ANY);
44 }
45
46 template<class View0, class View1, ReifyMode rm, bool strict>
47 forceinline
48 ReLq<View0,View1,rm,strict>::ReLq(Space& home, ReLq& p)
49 : Propagator(home,p) {
50 x0.update(home,p.x0);
51 x1.update(home,p.x1);
52 b.update(home,p.b);
53 }
54
55 template<class View0, class View1, ReifyMode rm, bool strict>
56 PropCost
57 ReLq<View0,View1,rm,strict>::cost(const Space&, const ModEventDelta&) const
58 {
59 return PropCost::ternary(PropCost::LO);
60 }
61
62 template<class View0, class View1, ReifyMode rm, bool strict>
63 void
64 ReLq<View0,View1,rm,strict>::reschedule(Space& home) {
65 b.reschedule(home,*this, Gecode::Int::PC_INT_VAL);
66 x0.reschedule(home,*this, PC_SET_ANY);
67 x1.reschedule(home,*this, PC_SET_ANY);
68 }
69
70 template<class View0, class View1, ReifyMode rm, bool strict>
71 forceinline size_t
72 ReLq<View0,View1,rm,strict>::dispose(Space& home) {
73 b.cancel(home,*this, Gecode::Int::PC_INT_VAL);
74 x0.cancel(home,*this, PC_SET_ANY);
75 x1.cancel(home,*this, PC_SET_ANY);
76 (void) Propagator::dispose(home);
77 return sizeof(*this);
78 }
79
80 template<class View0, class View1, ReifyMode rm, bool strict>
81 ExecStatus
82 ReLq<View0,View1,rm,strict>::post(Home home, View0 x0, View1 x1,
83 Gecode::Int::BoolView b) {
84 if (!same(x0,x1)) {
85 (void) new (home) ReLq<View0,View1,rm,strict>(home,x0,x1,b);
86 } else {
87 if (strict) {
88 if (rm != RM_PMI) {
89 GECODE_ME_CHECK(b.zero(home));
90 }
91 } else {
92 if (rm != RM_IMP) {
93 GECODE_ME_CHECK(b.one(home));
94 }
95 }
96 }
97 return ES_OK;
98 }
99
100 template<class View0, class View1, ReifyMode rm, bool strict>
101 Actor*
102 ReLq<View0,View1,rm,strict>::copy(Space& home) {
103 return new (home) ReLq<View0,View1,rm,strict>(home,*this);
104 }
105
106 template<class View0, class View1, ReifyMode rm, bool strict>
107 ExecStatus
108 ReLq<View0,View1,rm,strict>::propagate(Space& home, const ModEventDelta&) {
109 if (b.one()) {
110 if (rm == RM_PMI)
111 return home.ES_SUBSUMED(*this);
112 GECODE_REWRITE(*this,(Lq<View0,View1,strict>::post(home(*this),x0,x1)));
113 }
114 if (b.zero()) {
115 if (rm == RM_IMP)
116 return home.ES_SUBSUMED(*this);
117 GECODE_REWRITE(*this,
118 (Lq<View1,View0,!strict>::post(home(*this),x1,x0)));
119 }
120 if (x0.cardMax() == 0) {
121 if ( (!strict) || x1.cardMin() > 0) {
122 if (rm != RM_IMP)
123 GECODE_ME_CHECK(b.one_none(home));
124 return home.ES_SUBSUMED(*this);
125 }
126 if (strict && x1.cardMax() == 0) {
127 if (rm != RM_PMI)
128 GECODE_ME_CHECK(b.zero_none(home));
129 return home.ES_SUBSUMED(*this);
130 }
131 }
132
133 if (x0.assigned() && x1.assigned()) {
134 // directly test x0<=x1
135 int min01;
136 {
137 GlbRanges<View0> x0l(x0);
138 GlbRanges<View1> x1l(x1);
139 Iter::Ranges::Diff<GlbRanges<View1>,GlbRanges<View0> > d(x1l,x0l);
140 if (!d()) {
141 if ((!strict) && x0.cardMax() == x1.cardMax()) {
142 // equal
143 if (rm != RM_IMP)
144 GECODE_ME_CHECK(b.one_none(home));
145 } else {
146 // subset
147 if (rm != RM_PMI)
148 GECODE_ME_CHECK(b.zero_none(home));
149 }
150 return home.ES_SUBSUMED(*this);
151 }
152 min01 = d.min();
153 }
154 int min10;
155 {
156 GlbRanges<View0> x0l(x0);
157 GlbRanges<View1> x1l(x1);
158 Iter::Ranges::Diff<GlbRanges<View0>,GlbRanges<View1> > d(x0l,x1l);
159 if (!d()) {
160 if (strict && x0.cardMax() == x1.cardMax()) {
161 // equal
162 if (rm != RM_PMI)
163 GECODE_ME_CHECK(b.zero_none(home));
164 } else {
165 // subset
166 if (rm != RM_IMP)
167 GECODE_ME_CHECK(b.one_none(home));
168 }
169 return home.ES_SUBSUMED(*this);
170 }
171 min10 = d.min();
172 }
173
174 assert(min01 != min10);
175 if (min01<min10) {
176 if (rm != RM_IMP)
177 GECODE_ME_CHECK(b.one_none(home));
178 } else {
179 if (rm != RM_PMI)
180 GECODE_ME_CHECK(b.zero_none(home));
181 }
182 return home.ES_SUBSUMED(*this);
183 }
184
185 // min(x0lb - x1ub) < min(x1ub) -> b=0
186 if (x1.cardMax() > 0) {
187 GlbRanges<View0> x0l(x0);
188 LubRanges<View1> x1u(x1);
189 int x1umin=x1u.min();
190 Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View1> > d(x0l,x1u);
191 if (d() && d.min() < x1umin) {
192 if (rm != RM_PMI)
193 GECODE_ME_CHECK(b.zero_none(home));
194 return home.ES_SUBSUMED(*this);
195 }
196 }
197 // min(x1lb - x0ub) < min(x0ub) -> b=1
198 if (x0.cardMax() > 0) {
199 LubRanges<View0> x0u(x0);
200 GlbRanges<View1> x1l(x1);
201 int x0umin=x0u.min();
202 Iter::Ranges::Diff<GlbRanges<View1>,LubRanges<View0> > d(x1l,x0u);
203 if (d() && d.min() < x0umin) {
204 if (rm != RM_IMP)
205 GECODE_ME_CHECK(b.one_none(home));
206 return home.ES_SUBSUMED(*this);
207 }
208 }
209
210 return ES_FIX;
211 }
212
213}}}
214
215// STATISTICS: set-prop