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, 2006
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_CHANNEL_HH
35#define GECODE_INT_CHANNEL_HH
36
37#include <gecode/int.hh>
38#include <gecode/int/distinct.hh>
39
40/**
41 * \namespace Gecode::Int::Channel
42 * \brief %Channel propagators
43 */
44
45namespace Gecode { namespace Int { namespace Channel {
46
47 /// Processing stack
48 typedef Support::StaticStack<int,Region> ProcessStack;
49
50 /**
51 * \brief Base-class for channel propagators
52 *
53 */
54 template<class Info, class Offset, PropCond pc>
55 class Base : public Propagator {
56 protected:
57 /// Number of views (actually twice as many for both x and y)
58 int n;
59 /// Total number of not assigned views (not known to be assigned)
60 int n_na;
61 /// Offset transformation for x variables
62 Offset ox;
63 /// Offset transformation for y variables
64 Offset oy;
65 /// View and information for both \a x and \a y
66 Info* xy;
67 /// Constructor for cloning \a p
68 Base(Space& home, Base<Info,Offset,pc>& p);
69 /// Constructor for posting
70 Base(Home home, int n, Info* xy, Offset& ox, Offset& oy);
71 public:
72 /// Propagation cost (defined as low quadratic)
73 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
74 /// Schedule function
75 virtual void reschedule(Space& home);
76 /// Delete propagator and return its size
77 virtual size_t dispose(Space& home);
78 };
79
80
81 /**
82 * \brief Combine view with information for value propagation
83 *
84 */
85 template<class View> class ValInfo;
86
87 /**
88 * \brief Naive channel propagator
89 *
90 * Only propagates if views become assigned. If \a shared is true,
91 * the same views can be contained in both \a x and \a y.
92 *
93 * Requires \code #include <gecode/int/channel.hh> \endcode
94 * \ingroup FuncIntProp
95 */
96 template<class View, class Offset, bool shared>
97 class Val : public Base<ValInfo<View>,Offset,PC_INT_VAL> {
98 protected:
99 using Base<ValInfo<View>,Offset,PC_INT_VAL>::n;
100 using Base<ValInfo<View>,Offset,PC_INT_VAL>::n_na;
101 using Base<ValInfo<View>,Offset,PC_INT_VAL>::xy;
102 using Base<ValInfo<View>,Offset,PC_INT_VAL>::ox;
103 using Base<ValInfo<View>,Offset,PC_INT_VAL>::oy;
104 /// Constructor for cloning \a p
105 Val(Space& home, Val& p);
106 /// Constructor for posting
107 Val(Home home, int n, ValInfo<View>* xy, Offset& ox, Offset& oy);
108 public:
109 /// Copy propagator during cloning
110 virtual Actor* copy(Space& home);
111 /// Perform propagation
112 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
113 /// Post propagator for channeling
114 static ExecStatus post(Home home, int n, ValInfo<View>* xy,
115 Offset& ox, Offset& oy);
116 };
117
118 /**
119 * \brief Combine view with information for domain propagation
120 *
121 */
122 template<class View, class Offset> class DomInfo;
123
124 /**
125 * \brief Domain consistent channel propagator
126 *
127 * If \a shared is true, the same views can be contained in both
128 * \a x and \a y.
129 *
130 * Requires \code #include <gecode/int/channel.hh> \endcode
131 * \ingroup FuncIntProp
132 */
133 template<class View, class Offset, bool shared>
134 class Dom : public Base<DomInfo<View,Offset>,Offset,PC_INT_DOM> {
135 protected:
136 using Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>::n;
137 using Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>::n_na;
138 using Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>::xy;
139 using Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>::ox;
140 using Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>::oy;
141 /// Propagation controller for propagating distinct
142 Distinct::DomCtrl<View> dc;
143 /// Constructor for cloning \a p
144 Dom(Space& home, Dom& p);
145 /// Constructor for posting
146 Dom(Home home, int n, DomInfo<View,Offset>* xy, Offset& ox, Offset& oy);
147 public:
148 /// Copy propagator during cloning
149 virtual Actor* copy(Space& home);
150 /**
151 * \brief Cost function
152 *
153 * If in stage for naive value propagation, the cost is
154 * low quadratic. Otherwise it is high quadratic.
155 */
156 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
157 /// Perform propagation
158 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
159 /// Post propagator for channeling on \a xy
160 static ExecStatus post(Home home, int n, DomInfo<View,Offset>* xy,
161 Offset& ox, Offset& oy);
162 };
163
164 /**
165 * \brief Link propagator for a single Boolean view
166 *
167 * Requires \code #include <gecode/int/channel.hh> \endcode
168 * \ingroup FuncIntProp
169 */
170 class LinkSingle :
171 public MixBinaryPropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_VAL> {
172 private:
173 using MixBinaryPropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_VAL>::x0;
174 using MixBinaryPropagator<BoolView,PC_BOOL_VAL,IntView,PC_INT_VAL>::x1;
175
176 /// Constructor for cloning \a p
177 LinkSingle(Space& home, LinkSingle& p);
178 /// Constructor for posting
179 LinkSingle(Home home, BoolView x0, IntView x1);
180 public:
181 /// Copy propagator during cloning
182 virtual Actor* copy(Space& home);
183 /// Cost function (defined as low unary)
184 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
185 /// Perform propagation
186 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
187 /// Post propagator for \f$ x_0 = x_1\f$
188 static ExecStatus post(Home home, BoolView x0, IntView x1);
189 };
190
191 /**
192 * \brief Link propagator for multiple Boolean views
193 *
194 * Requires \code #include <gecode/int/channel.hh> \endcode
195 * \ingroup FuncIntProp
196 */
197 class LinkMulti :
198 public MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM> {
199 private:
200 using MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>::x;
201 using MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>::y;
202 /// The advisor council
203 Council<Advisor> c;
204 /// Value for propagator being idle
205 static const int S_NONE = 0;
206 /// Value for propagator having detected a one
207 static const int S_ONE = 1;
208 /// Value for propagator currently running
209 static const int S_RUN = 2;
210 /// Propagator status
211 int status;
212 /// Offset value
213 int o;
214 /// Constructor for cloning \a p
215 LinkMulti(Space& home, LinkMulti& p);
216 /// Constructor for posting
217 LinkMulti(Home home, ViewArray<BoolView>& x, IntView y, int o0);
218 public:
219 /// Copy propagator during cloning
220 GECODE_INT_EXPORT
221 virtual Actor* copy(Space& home);
222 /// Cost function (low unary if \a y is assigned, low linear otherwise)
223 GECODE_INT_EXPORT
224 virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
225 /// Schedule function
226 GECODE_INT_EXPORT
227 virtual void reschedule(Space& home);
228 /// Give advice to propagator
229 GECODE_INT_EXPORT
230 virtual ExecStatus advise(Space& home, Advisor& a, const Delta& d);
231 /// Perform propagation
232 GECODE_INT_EXPORT
233 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
234 /// Post propagator for \f$ x_i = 1\leftrightarrow y=i+o\f$
235 static ExecStatus post(Home home,
236 ViewArray<BoolView>& x, IntView y, int o);
237 /// Delete propagator and return its size
238 GECODE_INT_EXPORT
239 virtual size_t dispose(Space& home);
240 };
241
242}}}
243
244#include <gecode/int/channel/base.hpp>
245#include <gecode/int/channel/val.hpp>
246#include <gecode/int/channel/dom.hpp>
247
248#include <gecode/int/channel/link-single.hpp>
249#include <gecode/int/channel/link-multi.hpp>
250
251#endif
252
253// STATISTICS: int-prop
254