Generated on for Gecode by doxygen 1.18.0
open.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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_ARITHMETIC_OPEN_HPP
35#define GECODE_INT_ARITHMETIC_OPEN_HPP
36
39
40namespace Gecode { namespace Int { namespace Arithmetic {
41
43 template<class View>
44 class OpenMax : public OpenListPropagator<View> {
45 protected:
50
51 class Index : public Advisor {
52 public:
53 int i;
54
55 Index(Space& home, Propagator& p, Council<Index>& c, int i0)
56 : Advisor(home,p,c), i(i0) {}
57
58 Index(Space& home, Index& a)
59 : Advisor(home,a), i(a.i) {}
60 };
61
66 int lower;
68 int upper;
70 bool witness;
71
73 View result0, IntPropLevel ipl0)
75 result(result0), ipl(ipl0), c(home),
76 lower(Limits::min), upper(result0.max()), witness(false) {
77 result.subscribe(home,*this,PC_INT_BND);
78 }
79
81 : OpenListPropagator<View>(home,p), ipl(p.ipl), c(home),
83 result.update(home,p.result);
84 c.update(home,p.c);
85 }
86
87 public:
88 virtual Actor*
89 copy(Space& home) {
90 return new (home) OpenMax(home,*this);
91 }
92
93 virtual PropCost
94 cost(const Space&, const ModEventDelta&) const {
95 const int size = list.known_length();
97 ((closed() && !witness) || (result.max() < upper)) ?
98 size : size-processed);
99 }
100
101 virtual ExecStatus
102 advise(Space& home, Advisor& advisor, const Delta& d) {
103 if (View::modevent(d) == ME_INT_DOM)
104 return ES_FIX;
105 Index& a = static_cast<Index&>(advisor);
106 View x = list[a.i];
107 lower = std::max(lower,x.min());
108 if (x.assigned())
109 a.dispose(home,c);
110 return ((lower > result.min()) ||
111 (witness && closed() && c.empty())) ? ES_NOFIX : ES_FIX;
112 }
113
114 virtual ExecStatus
116 const int size = list.known_length();
117 if (result.max() < upper) {
118 for (int i=0; i<processed; i++) {
119 View x = list[i];
120 GECODE_ME_CHECK(x.lq(home,result.max()));
121 }
122 upper = result.max();
123 }
124 for (int i=processed; i<size; i++) {
125 View x = list[i];
126 if (x == result) {
127 witness = true;
128 continue;
129 }
130 GECODE_ME_CHECK(x.lq(home,result.max()));
131 lower = std::max(lower,x.min());
132 if (!x.assigned())
133 x.subscribe(home,*new (home) Index(home,*this,c,i));
134 }
135 processed = size;
136 GECODE_ME_CHECK(result.gq(home,lower));
137 // Future positions can supply the extremum. Enforce an equality witness
138 // only once the list is closed, using the ordinary min/max propagator.
139 if (!closed())
140 return ES_FIX;
141 if (size == 0)
142 return ES_FAILED;
143 if (witness)
144 return (result.assigned() || c.empty()) ?
145 home.ES_SUBSUMED(*this) : ES_FIX;
146 ViewArray<View> variables(home,size);
147 for (int i=0; i<size; i++)
148 variables[i] = list[i];
149 View y = result;
150 if (vbd(ipl) == IPL_DOM)
152 ::post(home(*this),variables,y)));
154 ::post(home(*this),variables,y)));
155 }
156
157 virtual void
160 result.reschedule(home,*this,PC_INT_BND);
161 }
162
163 virtual size_t
164 dispose(Space& home) {
165 if (!home.failed())
166 for (Advisors<Index> as(c); as(); ++as) {
167 View x = list[as.advisor().i];
168 x.cancel(home,as.advisor());
169 }
170 c.dispose(home);
171 result.cancel(home,*this,PC_INT_BND);
173 return sizeof(*this);
174 }
175
176 static void
179 (void) new (home) OpenMax(home,list,result,ipl);
180 }
181 };
182
183}}}
184
185#endif
186
187// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
Advisor(Space &home, Propagator &p, Council< A > &c)
Constructor for creation.
Definition core.hpp:4060
void dispose(Space &home, Council< A > &c)
Dispose the advisor.
Definition core.hpp:4098
friend class Council
Definition core.hpp:1310
Class to iterate over advisors of a council.
Definition core.hpp:1282
bool empty(void) const
Test whether council has advisor left.
Definition core.hpp:4150
void update(Space &home, Council< A > &c)
Update during cloning (copies all advisors).
Definition core.hpp:4160
void dispose(Space &home)
Dispose council.
Definition core.hpp:4216
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
Home class for posting propagators
Definition core.hpp:863
Bounds consistent n-ary maximum propagator.
Domain consistent n-ary maximum propagator.
Index(Space &home, Propagator &p, Council< Index > &c, int i0)
Definition open.hpp:55
Index(Space &home, Index &a)
Definition open.hpp:58
int lower
Maximum lower bound seen so far; bounds only increase.
Definition open.hpp:66
bool witness
The result occurs in the list and supplies its own equality witness.
Definition open.hpp:70
static void post(Home home, OpenViewList< View > list, View result, IntPropLevel ipl)
Definition open.hpp:177
int upper
Result upper bound last applied to all incorporated positions.
Definition open.hpp:68
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:164
OpenMax(Space &home, OpenMax &p)
Definition open.hpp:80
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:89
virtual ExecStatus advise(Space &home, Advisor &advisor, const Delta &d)
Advise function.
Definition open.hpp:102
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:115
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:158
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:94
OpenMax(Home home, OpenViewList< View > list, View result0, IntPropLevel ipl0)
Definition open.hpp:72
virtual void reschedule(Space &home)
Schedule function.
OpenListPropagator(Home home, OpenViewList< View > list0)
View interface to a space-local list with an open length.
Definition int.hh:1044
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
friend class Council
Definition core.hpp:1078
View arrays.
Definition array.hpp:255
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition macros.hpp:116
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
Numerical (arithmetic) propagators.
Numerical limits for integer variables.
Definition int.hh:119
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:80
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
ExecStatus
Definition core.hpp:479
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .