this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 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
34#ifndef GECODE_INT_NVALUES_HH
35#define GECODE_INT_NVALUES_HH
36
37#include <gecode/int.hh>
38#include <gecode/int/val-set.hh>
39
40/**
41 * \namespace Gecode::Int::NValues
42 * \brief Number of values propagators
43 */
44
45namespace Gecode { namespace Int { namespace NValues {
46
47 /// Event type for range-based overlap analysis
48 enum RangeEventType {
49 /// A range starts
50 RET_FST = 0,
51 /// A range ends
52 RET_LST = 1,
53 /// No further events
54 RET_END = 2
55 };
56
57 /// Event for range-based overlap analysis
58 class RangeEvent {
59 public:
60 /// The event type
61 RangeEventType ret;
62 /// The value for the range (first or last value, depending on type)
63 int val;
64 /// Which view does this range belong to
65 int view;
66 /// Order events: first by val, then by event type
67 bool operator <(RangeEvent re) const;
68 };
69
70 /// Symmetric diagonal bit matrix
71 class SymBitMatrix : public Support::BitSet<Region> {
72 protected:
73 /// Size of matrix
74 int n;
75 /// Return position in matrix
76 int pos(int x, int y) const;
77 public:
78 /// Initialize matrix for dimension \a n by \a n
79 SymBitMatrix(Region& r, int n);
80 /// Is bit at position \a x, \a y set?
81 bool get(int x, int y) const;
82 /// Set bit at position \a x, \a y
83 void set(int x, int y);
84 };
85
86}}}
87
88#include <gecode/int/nvalues/range-event.hpp>
89#include <gecode/int/nvalues/sym-bit-matrix.hpp>
90
91#include <gecode/int/view-val-graph.hh>
92
93namespace Gecode { namespace Int { namespace NValues {
94
95 /// View-value graph for propagation of upper bound
96 class Graph : public ViewValGraph::Graph<IntView> {
97 protected:
98 /// Number of matched edges
99 int n_matched;
100 public:
101 /// Construct graph as not yet initialized
102 Graph(void);
103 /// Return size of maximal matching (excluding assigned views)
104 int size(void) const;
105 /// Initialize graph including values in \a vs
106 void init(Space& home, const ValSet& vs, const ViewArray<IntView>& x);
107 /// Synchronize graph with new view domains
108 void sync(void);
109 /*
110 * \brief Mark all edges used that can appear in some maximal matching
111 *
112 * Return true, if any edge can be in fact pruned.
113 */
114 bool mark(void);
115 /// Prune all values corresponding to unused edges
116 ExecStatus prune(Space& home);
117 };
118
119}}}
120
121#include <gecode/int/nvalues/graph.hpp>
122
123namespace Gecode { namespace Int { namespace NValues {
124
125 /**
126 * \brief Number of values propagator for integer views base class
127 *
128 * Requires \code #include <gecode/int/nvalues.hh> \endcode
129 * \ingroup FuncIntProp
130 */
131 template<class VY>
132 class IntBase
133 : public MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND> {
134 protected:
135 using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::x;
136 using MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>::y;
137 /// Value set storing the values of already assigned views
138 ValSet vs;
139 /// Constructor for posting
140 IntBase(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
141 /// Constructor for cloning \a p
142 IntBase(Space& home, IntBase<VY>& p);
143 /// Add values of assigned views to value set
144 void add(Space& home);
145 /**
146 * Compute position of disjoint views in \a dis (with length \a n_dis)
147 * and eliminate subsumed views (all values included in the value set
148 * \a vs).
149 */
150 void disjoint(Space& home, Region& r, int*& dis, int& n_dis);
151 /// Eliminate subsumed views (all values included in the value set \a vs)
152 void eliminate(Space& home);
153 /// Propagate that all views must take values from value set
154 ExecStatus all_in_valset(Space& home);
155 /**
156 * Perform pruning of the lower bound based on finding
157 * an independent set, where \a dis and \a n_dis define the
158 * set of disjoint views (not overlapping with the values in
159 * the value set).
160 *
161 * Changes \a dis.
162 */
163 ExecStatus prune_lower(Space& home, int* dis, int n_dis);
164 /**
165 * Perform pruning of the upper bound based on finding
166 * a maximal matching in the view value graph \a g.
167 *
168 * Requires that subsumed views have been eliminated.
169 */
170 ExecStatus prune_upper(Space& home, Graph& g);
171 public:
172 /// Cost function
173 virtual PropCost cost(const Space&, const ModEventDelta&) const;
174 /// Delete propagator and return its size
175 virtual size_t dispose(Space& home);
176 };
177
178 /**
179 * \brief Equal to number of values propagator for integer views
180 *
181 * Requires \code #include <gecode/int/nvalues.hh> \endcode
182 * \ingroup FuncIntProp
183 */
184 template<class VY>
185 class EqInt : public IntBase<VY> {
186 protected:
187 using IntBase<VY>::x;
188 using IntBase<VY>::y;
189 using IntBase<VY>::vs;
190 using IntBase<VY>::add;
191 using IntBase<VY>::all_in_valset;
192 using IntBase<VY>::disjoint;
193 using IntBase<VY>::prune_lower;
194 using IntBase<VY>::prune_upper;
195 /// View-value graph
196 Graph g;
197 /// Constructor for posting
198 EqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
199 /// Constructor for cloning \a p
200 EqInt(Space& home, EqInt<VY>& p);
201 public:
202 /// Copy propagator during cloning
203 virtual Propagator* copy(Space& home);
204 /// Perform propagation
205 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
206 /// Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}=y\f$
207 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
208 /// Delete propagator and return its size
209 virtual size_t dispose(Space& home);
210 };
211
212 /**
213 * \brief Less or equal to number of values propagator for integer views
214 *
215 * Requires \code #include <gecode/int/nvalues.hh> \endcode
216 * \ingroup FuncIntProp
217 */
218 template<class VY>
219 class LqInt : public IntBase<VY> {
220 protected:
221 using IntBase<VY>::x;
222 using IntBase<VY>::y;
223 using IntBase<VY>::vs;
224 using IntBase<VY>::add;
225 using IntBase<VY>::all_in_valset;
226 using IntBase<VY>::disjoint;
227 using IntBase<VY>::prune_lower;
228 using IntBase<VY>::prune_upper;
229 /// Constructor for posting
230 LqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
231 /// Constructor for cloning \a p
232 LqInt(Space& home, LqInt<VY>& p);
233 public:
234 /// Copy propagator during cloning
235 virtual Propagator* copy(Space& home);
236 /// Perform propagation
237 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
238 /// Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\leq y\f$
239 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
240 /// Delete propagator and return its size
241 virtual size_t dispose(Space& home);
242 };
243
244 /**
245 * \brief Greater or equal to number of values propagator for integer views
246 *
247 * Requires \code #include <gecode/int/nvalues.hh> \endcode
248 * \ingroup FuncIntProp
249 */
250 template<class VY>
251 class GqInt : public IntBase<VY> {
252 protected:
253 using IntBase<VY>::x;
254 using IntBase<VY>::y;
255 using IntBase<VY>::vs;
256 using IntBase<VY>::add;
257 using IntBase<VY>::all_in_valset;
258 using IntBase<VY>::disjoint;
259 using IntBase<VY>::prune_lower;
260 using IntBase<VY>::prune_upper;
261 using IntBase<VY>::eliminate;
262 /// View-value graph
263 Graph g;
264 /// Constructor for posting
265 GqInt(Home home, ValSet& vs, ViewArray<IntView>& x, VY y);
266 /// Constructor for cloning \a p
267 GqInt(Space& home, GqInt<VY>& p);
268 public:
269 /// Copy propagator during cloning
270 virtual Propagator* copy(Space& home);
271 /// Perform propagation
272 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
273 /// Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\geq y\f$
274 static ExecStatus post(Home home, ViewArray<IntView>& x, VY y);
275 };
276
277}}}
278
279#include <gecode/int/nvalues/int-base.hpp>
280#include <gecode/int/nvalues/int-eq.hpp>
281#include <gecode/int/nvalues/int-lq.hpp>
282#include <gecode/int/nvalues/int-gq.hpp>
283
284namespace Gecode { namespace Int { namespace NValues {
285
286 /**
287 * \brief Number of values propagator for Boolean views base class
288 *
289 * Requires \code #include <gecode/int/nvalues.hh> \endcode
290 * \ingroup FuncIntProp
291 */
292 template<class VY>
293 class BoolBase : public Propagator {
294 protected:
295 /// View status: a zero has already been encountered
296 static const int VS_ZERO = 1 << 0;
297 /// View status: a one has already been encountered
298 static const int VS_ONE = 1 << 1;
299 /// Status information about the views
300 int status;
301 /// The advisor council
302 Council<ViewAdvisor<BoolView> > c;
303 /// The view for counting the number of values
304 VY y;
305 /// Constructor for posting
306 BoolBase(Home home, int status, ViewArray<BoolView>& x, VY y);
307 /// Constructor for cloning \a p
308 BoolBase(Space& home, BoolBase<VY>& p);
309 public:
310 /// Give advice to propagator
311 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
312 /// Cost function (defined as low unary)
313 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
314 /// Schedule function
315 virtual void reschedule(Space& home);
316 /// Delete propagator and return its size
317 virtual size_t dispose(Space& home);
318 };
319
320 /**
321 * \brief Equal to number of values propagator for Boolean views
322 *
323 * Requires \code #include <gecode/int/nvalues.hh> \endcode
324 * \ingroup FuncIntProp
325 */
326 template<class VY>
327 class EqBool : public BoolBase<VY> {
328 protected:
329 using BoolBase<VY>::VS_ZERO;
330 using BoolBase<VY>::VS_ONE;
331 using BoolBase<VY>::status;
332 using BoolBase<VY>::c;
333 using BoolBase<VY>::y;
334 /// Constructor for posting
335 EqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
336 /// Constructor for cloning \a p
337 EqBool(Space& home, EqBool<VY>& p);
338 public:
339 /// Copy propagator during cloning
340 virtual Actor* copy(Space& home);
341 /// Perform propagation
342 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
343 /**
344 * \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}=y\f$
345 *
346 * The view array \a x is used only temporarily and hence can
347 * be region allocated.
348 */
349 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
350 };
351
352 /**
353 * \brief Less or equal to number of values propagator for Boolean views
354 *
355 * Requires \code #include <gecode/int/nvalues.hh> \endcode
356 * \ingroup FuncIntProp
357 */
358 template<class VY>
359 class LqBool : public BoolBase<VY> {
360 protected:
361 using BoolBase<VY>::VS_ZERO;
362 using BoolBase<VY>::VS_ONE;
363 using BoolBase<VY>::status;
364 using BoolBase<VY>::c;
365 using BoolBase<VY>::y;
366 /// Constructor for posting
367 LqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
368 /// Constructor for cloning \a p
369 LqBool(Space& home, LqBool<VY>& p);
370 public:
371 /// Copy propagator during cloning
372 virtual Actor* copy(Space& home);
373 /// Perform propagation
374 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
375 /**
376 * \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\leq y\f$
377 *
378 * The view array \a x is used only temporarily and hence can
379 * be region allocated.
380 */
381 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
382 };
383
384 /**
385 * \brief Greater or equal to number of values propagator for Boolean views
386 *
387 * Requires \code #include <gecode/int/nvalues.hh> \endcode
388 * \ingroup FuncIntProp
389 */
390 template<class VY>
391 class GqBool : public BoolBase<VY> {
392 protected:
393 using BoolBase<VY>::VS_ZERO;
394 using BoolBase<VY>::VS_ONE;
395 using BoolBase<VY>::status;
396 using BoolBase<VY>::c;
397 using BoolBase<VY>::y;
398 /// Constructor for posting
399 GqBool(Home home, int status, ViewArray<BoolView>& x, VY y);
400 /// Constructor for cloning \a p
401 GqBool(Space& home, GqBool<VY>& p);
402 public:
403 /// Copy propagator during cloning
404 virtual Actor* copy(Space& home);
405 /// Perform propagation
406 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
407 /**
408 * \brief Post propagator for \f$\#\{x_0,\ldots,x_{|x|-1}\}\geq y\f$
409 *
410 * The view array \a x is used only temporarily and hence can
411 * be region allocated.
412 */
413 static ExecStatus post(Home home, ViewArray<BoolView>& x, VY y);
414 };
415
416}}}
417
418#include <gecode/int/nvalues/bool-base.hpp>
419#include <gecode/int/nvalues/bool-eq.hpp>
420#include <gecode/int/nvalues/bool-lq.hpp>
421#include <gecode/int/nvalues/bool-gq.hpp>
422
423#endif
424
425// STATISTICS: int-prop