this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 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 {
35
36 /**
37 * \defgroup TaskBranchMerit Generic merit for branchers based on view and value selection
38 *
39 * \ingroup TaskBranchViewVal
40 */
41 //@{
42 /**
43 * \brief Base-class for merit class
44 */
45 template<class View_, class Val_>
46 class MeritBase {
47 public:
48 /// View type
49 typedef View_ View;
50 /// Corresponding variable type
51 typedef typename View::VarType Var;
52 /// Type of merit
53 typedef Val_ Val;
54 /// Constructor for initialization
55 MeritBase(Space& home, const VarBranch<Var>& vb);
56 /// Constructor for cloning
57 MeritBase(Space& home, MeritBase& mb);
58 /// Whether dispose must always be called (that is, notice is needed)
59 bool notice(void) const;
60 /// Delete view merit class
61 void dispose(Space& home);
62 };
63
64 /**
65 * \brief Merit class for user-defined merit function
66 */
67 template<class View>
68 class MeritFunction : public MeritBase<View,double> {
69 using typename MeritBase<View,double>::Var;
70 public:
71 /// Corresponding merit function type
72 typedef typename BranchTraits<Var>::Merit Function;
73 protected:
74 /// The user-defined merit function
75 SharedData<Function> f;
76 public:
77 /// Constructor for initialization
78 MeritFunction(Space& home, const VarBranch<Var>& vb);
79 /// Constructor for cloning
80 MeritFunction(Space& home, MeritFunction& mf);
81 /// Return degree as merit for view \a x at position \a i
82 double operator ()(const Space& home, View x, int i);
83 /// Whether dispose must always be called (that is, notice is needed)
84 bool notice(void) const;
85 /// Delete view merit class
86 void dispose(Space& home);
87 };
88
89 /**
90 * \brief Merit class for degree
91 */
92 template<class View>
93 class MeritDegree : public MeritBase<View,unsigned int> {
94 using typename MeritBase<View,unsigned int>::Var;
95 public:
96 /// Constructor for initialization
97 MeritDegree(Space& home, const VarBranch<Var>& vb);
98 /// Constructor for cloning
99 MeritDegree(Space& home, MeritDegree& md);
100 /// Return degree as merit for view \a x at position \a i
101 unsigned int operator ()(const Space& home, View x, int i);
102 };
103
104 /**
105 * \brief Merit class for AFC
106 */
107 template<class View>
108 class MeritAFC : public MeritBase<View,double> {
109 using typename MeritBase<View,double>::Var;
110 protected:
111 /// AFC information
112 AFC afc;
113 public:
114 /// Constructor for initialization
115 MeritAFC(Space& home, const VarBranch<Var>& vb);
116 /// Constructor for cloning
117 MeritAFC(Space& home, MeritAFC& ma);
118 /// Return AFC as merit for view \a x at position \a i
119 double operator ()(const Space& home, View x, int i);
120 /// Whether dispose must always be called (that is, notice is needed)
121 bool notice(void) const;
122 /// Dispose view selection
123 void dispose(Space& home);
124 };
125
126 /**
127 * \brief Merit class for action
128 */
129 template<class View>
130 class MeritAction : public MeritBase<View,double> {
131 using typename MeritBase<View,double>::Var;
132 protected:
133 /// Action information
134 Action action;
135 public:
136 /// Constructor for initialization
137 MeritAction(Space& home, const VarBranch<Var>& vb);
138 /// Constructor for cloning
139 MeritAction(Space& home, MeritAction& ma);
140 /// Return action as merit for view \a x at position \a i
141 double operator ()(const Space& home, View x, int i);
142 /// Whether dispose must always be called (that is, notice is needed)
143 bool notice(void) const;
144 /// Dispose view selection
145 void dispose(Space& home);
146 };
147 //@}
148
149 /**
150 * \brief Merit class for CHB
151 */
152 template<class View>
153 class MeritCHB : public MeritBase<View,double> {
154 using typename MeritBase<View,double>::Var;
155 protected:
156 /// CHB information
157 CHB chb;
158 public:
159 /// Constructor for initialization
160 MeritCHB(Space& home, const VarBranch<Var>& vb);
161 /// Constructor for cloning
162 MeritCHB(Space& home, MeritCHB& ma);
163 /// Return action as merit for view \a x at position \a i
164 double operator ()(const Space& home, View x, int i);
165 /// Whether dispose must always be called (that is, notice is needed)
166 bool notice(void) const;
167 /// Dispose view selection
168 void dispose(Space& home);
169 };
170 //@}
171
172
173 // Merit base class
174 template<class View, class Val>
175 forceinline
176 MeritBase<View,Val>::MeritBase(Space&, const VarBranch<Var>&) {}
177 template<class View, class Val>
178 forceinline
179 MeritBase<View,Val>::MeritBase(Space&, MeritBase&) {}
180 template<class View, class Val>
181 forceinline bool
182 MeritBase<View,Val>::notice(void) const {
183 return false;
184 }
185 template<class View, class Val>
186 forceinline void
187 MeritBase<View,Val>::dispose(Space&) {}
188
189 // User-defined function merit
190 template<class View>
191 forceinline
192 MeritFunction<View>::MeritFunction
193 (Space& home, const VarBranch<typename MeritFunction<View>::Var>& vb)
194 : MeritBase<View,double>(home,vb), f(vb.merit()) {
195 if (!f())
196 throw InvalidFunction("MeritFunction::MeritFunction");
197 }
198 template<class View>
199 forceinline
200 MeritFunction<View>::MeritFunction(Space& home, MeritFunction& mf)
201 : MeritBase<View,double>(home,mf), f(mf.f) {
202 }
203 template<class View>
204 forceinline double
205 MeritFunction<View>::operator ()(const Space& home, View x, int i) {
206 typename View::VarType y(x.varimp());
207 GECODE_VALID_FUNCTION(f());
208 return f()(home,y,i);
209 }
210 template<class View>
211 forceinline bool
212 MeritFunction<View>::notice(void) const {
213 return true;
214 }
215 template<class View>
216 forceinline void
217 MeritFunction<View>::dispose(Space&) {
218 f.~SharedData<Function>();
219 }
220
221
222 // Degree merit
223 template<class View>
224 forceinline
225 MeritDegree<View>::MeritDegree
226 (Space& home, const VarBranch<typename MeritDegree<View>::Var>& vb)
227 : MeritBase<View,unsigned int>(home,vb) {}
228 template<class View>
229 forceinline
230 MeritDegree<View>::MeritDegree(Space& home, MeritDegree& md)
231 : MeritBase<View,unsigned int>(home,md) {}
232 template<class View>
233 forceinline unsigned int
234 MeritDegree<View>::operator ()(const Space&, View x, int) {
235 return x.degree();
236 }
237
238 // AFC merit
239 template<class View>
240 forceinline
241 MeritAFC<View>::MeritAFC
242 (Space& home, const VarBranch<typename MeritAFC<View>::Var>& vb)
243 : MeritBase<View,double>(home,vb), afc(vb.afc()) {}
244 template<class View>
245 forceinline
246 MeritAFC<View>::MeritAFC(Space& home, MeritAFC& ma)
247 : MeritBase<View,double>(home,ma), afc(ma.afc) {}
248 template<class View>
249 forceinline double
250 MeritAFC<View>::operator ()(const Space&, View x, int) {
251 return x.afc();
252 }
253 template<class View>
254 forceinline bool
255 MeritAFC<View>::notice(void) const {
256 // Given that AFC is just a fake, this not really necessary
257 return false;
258 }
259 template<class View>
260 forceinline void
261 MeritAFC<View>::dispose(Space&) {
262 // Given that AFC is just a fake, this not really necessary
263 afc.~AFC();
264 }
265
266
267 // Action merit
268 template<class View>
269 forceinline
270 MeritAction<View>::MeritAction
271 (Space& home, const VarBranch<typename MeritAction<View>::Var>& vb)
272 : MeritBase<View,double>(home,vb), action(vb.action()) {}
273 template<class View>
274 forceinline
275 MeritAction<View>::MeritAction(Space& home, MeritAction& ma)
276 : MeritBase<View,double>(home,ma), action(ma.action) {}
277 template<class View>
278 forceinline double
279 MeritAction<View>::operator ()(const Space&, View, int i) {
280 return action[i];
281 }
282 template<class View>
283 forceinline bool
284 MeritAction<View>::notice(void) const {
285 return true;
286 }
287 template<class View>
288 forceinline void
289 MeritAction<View>::dispose(Space&) {
290 action.~Action();
291 }
292
293 // CHB merit
294 template<class View>
295 forceinline
296 MeritCHB<View>::MeritCHB
297 (Space& home, const VarBranch<typename MeritCHB<View>::Var>& vb)
298 : MeritBase<View,double>(home,vb), chb(vb.chb()) {}
299 template<class View>
300 forceinline
301 MeritCHB<View>::MeritCHB(Space& home, MeritCHB& ma)
302 : MeritBase<View,double>(home,ma), chb(ma.chb) {}
303 template<class View>
304 forceinline double
305 MeritCHB<View>::operator ()(const Space&, View, int i) {
306 return chb[i];
307 }
308 template<class View>
309 forceinline bool
310 MeritCHB<View>::notice(void) const {
311 return true;
312 }
313 template<class View>
314 forceinline void
315 MeritCHB<View>::dispose(Space&) {
316 chb.~CHB();
317 }
318
319}
320
321// STATISTICS: kernel-branch