this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christopher Mears <chris.mears@monash.edu>
5 *
6 * Copyright:
7 * Christopher Mears, 2012
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 LDSB {
35
36 template<class View, int n, class Val, unsigned int a,
37 class Filter, class Print>
38 LDSBSetBrancher<View,n,Val,a,Filter,Print>
39 ::LDSBSetBrancher(Home home, ViewArray<View>& x,
40 ViewSel<View>* vs[n],
41 ValSelCommitBase<View,Val>* vsc,
42 SymmetryImp<View>** syms, int nsyms,
43 BranchFilter<typename LDSBSetBrancher<View,n,Val,a,Filter,Print>::Var> bf,
44 VarValPrint<typename LDSBSetBrancher<View,n,Val,a,Filter,Print>::Var,Val> vvp)
45 : LDSBBrancher<View,n,Val,a,Filter,Print>
46 (home, x, vs, vsc, syms, nsyms, bf, vvp),
47 _prevPos(-1),
48 _copiedSyms(nullptr),
49 _nCopiedSyms(0),
50 _stable(false) {
51 // Put all the value symmetries at the end of the list.
52 int seen = 0;
53 int dest = this->_nsyms - 1;
54 for (int i = 0 ; i < this->_nsyms - seen ; i++) {
55 if (dynamic_cast<ValueSymmetryImp<View>*>(this->_syms[i])) {
56 SymmetryImp<View>* t = this->_syms[i];
57 this->_syms[i] = this->_syms[dest];
58 this->_syms[dest] = t;
59 dest--;
60 seen++;
61 }
62 }
63 _nValueSymmetries = seen;
64 _nNonValueSymmetries = this->_nsyms - seen;
65 }
66
67 template<class View, int n, class Val, unsigned int a,
68 class Filter, class Print>
69 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
70 LDSBSetBrancher(Space& home,
71 LDSBSetBrancher<View,n,Val,a,Filter,Print>& b)
72 : LDSBBrancher<View,n,Val,a,Filter,Print>(home,b),
73 _prevPos(b._prevPos),
74 _nNonValueSymmetries(b._nNonValueSymmetries),
75 _nValueSymmetries(b._nValueSymmetries),
76 _nCopiedSyms(b._nCopiedSyms),
77 _leftBranchValues(b._leftBranchValues),
78 _stable(b._stable) {
79 if (_nCopiedSyms > 0) {
80 _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
81 for (int i = 0 ; i < _nCopiedSyms ; i++)
82 _copiedSyms[i] = static_cast<ValueSymmetryImp<View>*>(
83 b._copiedSyms[i]->copy(home));
84 } else {
85 _copiedSyms = nullptr;
86 }
87 }
88
89 /**
90 * \brief Bulk update of a value symmetry \a s, using \a usedValues
91 *
92 * Calculates the intersection and difference of the values in the
93 * symmetry and \a usedValues, updates the symmetry to eliminate the
94 * used values, and makes a new symmetry containing the intersection
95 * values, if there are at least two. Returns the new symmetry, or
96 * nullptr if the intersection has fewer than two elements.
97 */
98 template <class View>
99 ValueSymmetryImp<View>*
100 specialUpdate(Space& home, ValueSymmetryImp<View>* s, IntSet usedValues) {
101 // Calculate intersection and difference.
102 IntArgs intersection;
103 IntArgs difference;
104 int n = 0;
105 for (int i = s->values.next(s->values.offset()) ;
106 i <= s->values.max_bit() ; i = s->values.next(i+1)) {
107 n++;
108 if (usedValues.in(i))
109 intersection << i;
110 else
111 difference << i;
112 }
113
114 for (IntSetValues v(usedValues) ; v() ; ++v) {
115 s->update(Literal(0, v.val()));
116 }
117
118 if (intersection.size() < 2)
119 return nullptr;
120 int *a = new int[intersection.size()];
121 for (int i = 0 ; i < intersection.size() ; i++) {
122 a[i] = intersection[i];
123 }
124 ValueSymmetryImp<View>* ns =
125 new (home) ValueSymmetryImp<View>(home, a, intersection.size());
126 delete [] a;
127 return ns;
128 }
129
130 template<class View, int n, class Val, unsigned int a,
131 class Filter, class Print>
132 void
133 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
134 updatePart1(Space& home, int choicePos) {
135 if (_nValueSymmetries > 0) {
136 // If this is a different variable from the last commit, restore
137 // the old value symmetries and update the copy.
138 if (choicePos != _prevPos) {
139 if (_prevPos != -1) {
140 int i = 0;
141 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
142 this->_syms[j] = _copiedSyms[i];
143 i++;
144 }
145
146 for (int i = 0 ; i < _nCopiedSyms ; i++) {
147 ValueSymmetryImp<View>* ns =
148 specialUpdate(home, _copiedSyms[i], _leftBranchValues);
149 if (ns) {
150 this->_syms = home.realloc<SymmetryImp<View>*>(this->_syms,
151 this->_nsyms,
152 this->_nsyms+1);
153 this->_syms[this->_nsyms] = ns;
154 this->_nsyms++;
155 this->_nValueSymmetries++;
156 }
157 }
158 }
159
160 // Reset for current variable, make copy of value symmetries
161 _leftBranchValues = IntSet::empty;
162 _prevPos = choicePos;
163 if (_nCopiedSyms > 0) home.free(_copiedSyms, _nCopiedSyms);
164 _nCopiedSyms = _nValueSymmetries;
165 _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
166 {
167 int i = 0;
168 for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
169 ValueSymmetryImp<View>* vsi =
170 static_cast<ValueSymmetryImp<View>*>(this->_syms[j]);
171 _copiedSyms[i] =
172 static_cast<ValueSymmetryImp<View>*>(vsi->copy(home));
173 i++;
174 }
175 }
176 }
177 }
178 }
179
180 // Compute choice
181 template<class View, int n, class Val, unsigned int a,
182 class Filter, class Print>
183 const Choice*
184 LDSBSetBrancher<View,n,Val,a,Filter,Print>::choice(Space& home) {
185 // Making the PVC here is not so nice, I think.
186 const Choice* c = ViewValBrancher<View,n,Val,a,Filter,Print>::choice(home);
187 const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
188
189 // Compute symmetries.
190
191 int choicePos = pvc->pos().pos;
192 delete c;
193
194 assert(!_stable);
195 updatePart1(home, choicePos);
196
197 return LDSBBrancher<View,n,Val,a,Filter,Print>::choice(home);
198 }
199
200 template<class View, int n, class Val, unsigned int a,
201 class Filter, class Print>
202 ExecStatus
203 LDSBSetBrancher<View,n,Val,a,Filter,Print>
204 ::commit(Space& home, const Choice& c, unsigned int b) {
205 const LDSBChoice<Val>& pvc
206 = static_cast<const LDSBChoice<Val>&>(c);
207 int choicePos = pvc.pos().pos;
208 int choiceVal = pvc.val();
209
210 if (!_stable)
211 updatePart1(home, choicePos);
212
213 if (b == 0) {
214 IntArgs ia;
215 for (IntSetValues v(_leftBranchValues) ; v() ; ++v) {
216 ia << v.val();
217 }
218 ia << choiceVal;
219 _leftBranchValues = IntSet(ia);
220
221 // Post the branching constraint.
222 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
223 ::commit(home, c, b);
224 GECODE_ES_CHECK(fromBase);
225 for (int i = 0 ; i < this->_nsyms ; i++)
226 this->_syms[i]->update(Literal(choicePos, choiceVal));
227 } else if (b == 1) {
228 // Post the branching constraint.
229 ExecStatus fromBase = ViewValBrancher<View,n,Val,a,Filter,Print>
230 ::commit(home, c, b);
231 GECODE_ES_CHECK(fromBase);
232
233 // Post prunings.
234 int nliterals = pvc.nliterals();
235 const Literal* literals = pvc.literals();
236 for (int i = 0 ; i < nliterals ; i++) {
237 const Literal& l = literals[i];
238 ModEvent me = prune<View>(home, this->x[l._variable], l._value);
239 GECODE_ME_CHECK(me);
240 }
241 }
242
243 return ES_OK;
244 }
245
246 template<class View, int n, class Val, unsigned int a,
247 class Filter, class Print>
248 Actor*
249 LDSBSetBrancher<View,n,Val,a,Filter,Print>::copy(Space& home) {
250 return new (home) LDSBSetBrancher<View,n,Val,a,Filter,Print>
251 (home,*this);
252 }
253
254 template<class View, int n, class Val, unsigned int a,
255 class Filter, class Print>
256 forceinline void
257 LDSBSetBrancher<View,n,Val,a,Filter,Print>::
258 post(Home home, ViewArray<View>& x,
259 ViewSel<View>* vs[n], ValSelCommitBase<View,Val>* vsc,
260 SymmetryImp<View>** syms, int nsyms,
261 BranchFilter<typename LDSBSetBrancher<View,n,Val,a,Filter,Print>::Var> bf,
262 VarValPrint<typename LDSBSetBrancher<View,n,Val,a,Filter,Print>::Var,Val> vvp) {
263 (void) new (home) LDSBSetBrancher<View,n,Val,a,Filter,Print>
264 (home,x,vs,vsc,syms,nsyms,bf,vvp);
265 }
266
267 template<class View, int n, class Val, unsigned int a>
268 forceinline void
269 postldsbsetbrancher(Home home,
270 ViewArray<View>& x,
271 ViewSel<View>* vs[n],
272 ValSelCommitBase<View,Val>* vsc,
273 SymmetryImp<View>** syms, int nsyms,
274 BranchFilter<typename View::VarType> bf,
275 VarValPrint<typename View::VarType,Val> vvp) {
276 if (bf) {
277 if (vvp) {
278 LDSBSetBrancher<View,n,Val,a,BrancherFilter<View>,BrancherPrint<View,Val> >
279 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
280 } else {
281 LDSBSetBrancher<View,n,Val,a,BrancherFilter<View>,BrancherNoPrint<View,Val> >
282 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
283 }
284 } else {
285 if (vvp) {
286 LDSBSetBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherPrint<View,Val> >
287 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
288 } else {
289 LDSBSetBrancher<View,n,Val,a,BrancherNoFilter<View>,BrancherNoPrint<View,Val> >
290 ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
291 }
292 }
293 }
294
295}}}
296
297// STATISTICS: set-branch