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
34#include <gecode/set/ldsb.hh>
35#include <gecode/set/branch.hh>
36#include <map>
37
38namespace Gecode {
39 using namespace Int::LDSB;
40 /*
41 * Implementation of some SymmetryHandle methods.
42 */
43
44 SymmetryHandle VariableSymmetry(const SetVarArgs& x) {
45 ArgArray<VarImpBase*> a(x.size());
46 for (int i = 0 ; i < x.size() ; i++)
47 a[i] = x[i].varimp();
48 return SymmetryHandle(new VariableSymmetryObject(a));
49 }
50 SymmetryHandle VariableSequenceSymmetry(const SetVarArgs& x, int ss) {
51 ArgArray<VarImpBase*> a(x.size());
52 for (int i = 0 ; i < x.size() ; i++)
53 a[i] = x[i].varimp();
54 return SymmetryHandle(new VariableSequenceSymmetryObject(a, ss));
55 }
56}
57
58namespace Gecode { namespace Int { namespace LDSB {
59 template <>
60 ModEvent prune<Set::SetView>(Space& home, Set::SetView x, int v) {
61 return x.exclude(home, v);
62 }
63}}}
64
65namespace Gecode { namespace Set { namespace LDSB {
66
67 /// Map from variable implementation to index
68 class VariableMap : public std::map<VarImpBase*,int> {};
69
70 /*
71 * The createSetSym function is an almost exact copy of
72 * createIntSym/createBoolSym.
73 */
74 SymmetryImp<SetView>* createSetSym(Space& home, const SymmetryHandle& s,
75 VariableMap variableMap) {
76 VariableSymmetryObject* varref =
77 dynamic_cast<VariableSymmetryObject*>(s.ref);
78 ValueSymmetryObject* valref =
79 dynamic_cast<ValueSymmetryObject*>(s.ref);
80 VariableSequenceSymmetryObject* varseqref =
81 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
82 ValueSequenceSymmetryObject* valseqref =
83 dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
84 if (varref) {
85 int n = varref->nxs;
86 int* indices = home.alloc<int>(n);
87 for (int i = 0 ; i < n ; i++) {
88 VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
89 if (index == variableMap.end())
90 throw
91 Int::LDSBUnbranchedVariable("VariableSymmetryObject::createSet");
92 indices[i] = index->second;
93 }
94 return new (home) VariableSymmetryImp<SetView>(home, indices, n);
95 }
96 if (valref) {
97 int n = valref->values.size();
98 int *vs = home.alloc<int>(n);
99 int i = 0;
100 for (IntSetValues v(valref->values) ; v() ; ++v) {
101 vs[i] = v.val();
102 i++;
103 }
104 return new (home) ValueSymmetryImp<SetView>(home, vs, n);
105 }
106 if (varseqref) {
107 int n = varseqref->nxs;
108 int* indices = home.alloc<int>(n);
109 for (int i = 0 ; i < n ; i++) {
110 VariableMap::const_iterator index =
111 variableMap.find(varseqref->xs[i]);
112 if (index == variableMap.end())
113 throw
114 Int::LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createSet");
115 indices[i] = index->second;
116 }
117 return new (home) VariableSequenceSymmetryImp<SetView>(home, indices, n,
118 varseqref->seq_size);
119 }
120 if (valseqref) {
121 unsigned int n = valseqref->values.size();
122 int *vs = home.alloc<int>(n);
123 for (unsigned int i = 0 ; i < n ; i++)
124 vs[i] = valseqref->values[i];
125 return new (home) ValueSequenceSymmetryImp<SetView>(home, vs, n,
126 valseqref->seq_size);
127 }
128 GECODE_NEVER;
129 return nullptr;
130 }
131}}}
132
133namespace Gecode {
134
135 using namespace Set::LDSB;
136
137 void
138 branch(Home home, const SetVarArgs& x,
139 SetVarBranch vars, SetValBranch vals,
140 const Symmetries& syms,
141 SetBranchFilter bf,
142 SetVarValPrint vvp) {
143 using namespace Set;
144 if (home.failed()) return;
145 vars.expand(home,x);
146 ViewArray<SetView> xv(home,x);
147 ViewSel<SetView>* vs[1] = {
148 Branch::viewsel(home,vars)
149 };
150
151 // Construct mapping from each variable in the array to its index
152 // in the array.
153 VariableMap variableMap;
154 for (int i = 0 ; i < x.size() ; i++)
155 variableMap[x[i].varimp()] = i;
156
157 // Convert the modelling-level Symmetries object into an array of
158 // SymmetryImp objects.
159 int n = syms.size();
160 SymmetryImp<SetView>** array =
161 static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
162 for (int i = 0 ; i < n ; i++) {
163 array[i] = createSetSym(home, syms[i], variableMap);
164 }
165
166 postldsbsetbrancher<SetView,1,int,2>
167 (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
168 }
169
170 void
171 branch(Home home, const SetVarArgs& x,
172 TieBreak<SetVarBranch> vars, SetValBranch vals,
173 const Symmetries& syms,
174 SetBranchFilter bf,
175 SetVarValPrint vvp) {
176 using namespace Set;
177 if (home.failed()) return;
178 vars.a.expand(home,x);
179 if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
180 (vars.a.select() == SetVarBranch::SEL_RND))
181 vars.b = SET_VAR_NONE();
182 vars.b.expand(home,x);
183 if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
184 (vars.b.select() == SetVarBranch::SEL_RND))
185 vars.c = SET_VAR_NONE();
186 vars.c.expand(home,x);
187 if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
188 (vars.c.select() == SetVarBranch::SEL_RND))
189 vars.d = SET_VAR_NONE();
190 vars.d.expand(home,x);
191 if (vars.b.select() == SetVarBranch::SEL_NONE) {
192 branch(home,x,vars.a,vals,syms,bf,vvp);
193 } else {
194 // Construct mapping from each variable in the array to its index
195 // in the array.
196 VariableMap variableMap;
197 for (int i = 0 ; i < x.size() ; i++)
198 variableMap[x[i].varimp()] = i;
199
200 // Convert the modelling-level Symmetries object into an array of
201 // SymmetryImp objects.
202 int n = syms.size();
203 SymmetryImp<SetView>** array =
204 static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
205 for (int i = 0 ; i < n ; i++) {
206 array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
207 }
208
209 ViewArray<SetView> xv(home,x);
210 ValSelCommitBase<SetView,int>* vsc = Branch::valselcommit(home,vals);
211 if (vars.c.select() == SetVarBranch::SEL_NONE) {
212 ViewSel<SetView>* vs[2] = {
213 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
214 };
215 postldsbsetbrancher<SetView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
216 } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
217 ViewSel<SetView>* vs[3] = {
218 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
219 Branch::viewsel(home,vars.c)
220 };
221 postldsbsetbrancher<SetView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
222 } else {
223 ViewSel<SetView>* vs[4] = {
224 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
225 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
226 };
227 postldsbsetbrancher<SetView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
228 }
229 }
230 }
231
232}
233
234// STATISTICS: set-branch