Generated on for Gecode by doxygen 1.17.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_PRECEDE_OPEN_HPP
35#define GECODE_INT_PRECEDE_OPEN_HPP
36
37#include <gecode/int/precede.hh>
39
40namespace Gecode { namespace Int { namespace Precede {
41
42 template<class View>
43 class Open : public OpenListPropagator<View> {
44 protected:
49
51 class Index : public Advisor {
52 public:
54 int i;
55
57 View x0, int i0)
58 : Advisor(home,p,c), x(x0), i(i0) {}
59
60 Index(Space& home, Index& a)
61 : Advisor(home,a), i(a.i) {
62 x.update(home,a.x);
63 }
64 };
65
67 int before;
68 int after;
70 int alpha;
71 int beta;
73 int gamma;
74
76 int before0, int after0)
77 : OpenListPropagator<View>(home,list), council(home),
78 before(before0), after(after0), alpha(0), beta(0),
79 gamma(Limits::max) {}
80
81 Open(Space& home, Open& p)
82 : OpenListPropagator<View>(home,p), council(home),
83 before(p.before), after(p.after),
84 alpha(p.alpha), beta(p.beta), gamma(p.gamma) {
85 council.update(home,p.council);
86 }
87
88 public:
89 virtual PropCost
90 cost(const Space&, const ModEventDelta&) const {
91 return PropCost::linear(PropCost::LO,list.known_length()-alpha);
92 }
93
94 virtual Actor*
95 copy(Space& home) {
96 return new (home) Open(home,*this);
97 }
98
99 virtual ExecStatus
100 advise(Space& home, Advisor& a0, const Delta&) {
101 Index& a = static_cast<Index&>(a0);
102 const int i = a.i;
103 bool changed = false;
104 if (a.x.assigned()) {
105 if ((a.x.val() == after) && (i < gamma)) {
106 gamma = i;
107 changed = true;
108 }
109 changed |= (i == alpha) || (i == beta);
110 a.dispose(home,council);
111 } else if ((i < alpha) || (i > gamma)) {
112 a.x.cancel(home,a);
113 a.dispose(home,council);
114 } else {
115 changed = ((i == alpha) || (i == beta)) && !a.x.in(before);
116 }
117 return changed ? ES_NOFIX : ES_FIX;
118 }
119
120 virtual ExecStatus
122 const int size = list.known_length();
123 if (before == after) {
124 for (int i=processed; i<size; i++)
125 GECODE_ME_CHECK(list[i].nq(home,before));
126 processed = size;
127 return closed() ? home.ES_SUBSUMED(*this) : ES_FIX;
128 }
129
130 for (int i=processed; i<size; i++) {
131 View x(list[i]);
132 if (x.assigned()) {
133 if (x.val() == after)
134 gamma = std::min(gamma,i);
135 } else if (i <= gamma) {
136 x.subscribe(home,*new (home) Index(home,*this,council,x,i));
137 }
138 }
139 processed = size;
140
141 while ((alpha < size) && !list[alpha].in(before)) {
142 GECODE_ME_CHECK(list[alpha].nq(home,after));
143 alpha++;
144 }
145 if (alpha == size) {
146 beta = size;
147 return closed() ? home.ES_SUBSUMED(*this) : ES_FIX;
148 }
149 View first(list[alpha]);
150 GECODE_ME_CHECK(first.nq(home,after));
151 if (first.assigned())
152 return home.ES_SUBSUMED(*this);
153
154 // An exhausted cursor resumes at the previous end after growth.
155 beta = std::max(beta,alpha+1);
156 while ((beta < size) && !list[beta].in(before))
157 beta++;
158 if (beta > gamma) {
159 GECODE_ME_CHECK(first.eq(home,before));
160 return home.ES_SUBSUMED(*this);
161 }
162 return ES_FIX;
163 }
164
165 virtual void
168 View::schedule(home,*this,ME_INT_DOM);
169 }
170
171 virtual size_t
172 dispose(Space& home) {
173 for (Advisors<Index> as(council); as(); ++as)
174 as.advisor().x.cancel(home,as.advisor());
175 council.dispose(home);
177 return sizeof(*this);
178 }
179
180 static void
182 (void) new (home) Open(home,list,before,after);
183 }
184 };
185
186}}}
187
188#endif
189
190// 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
friend class Council
Definition core.hpp:1310
Class to iterate over advisors of a council.
Definition core.hpp:1282
Generic domain change information to be supplied to advisors.
Definition core.hpp:209
FloatValImpType x
Implementation of float value.
Definition float.hh:420
Home class for posting propagators
Definition core.hpp:863
virtual void reschedule(Space &home)
Schedule function.
OpenListPropagator(Home home, OpenViewList< View > list0)
Keep the view as well as its position for independent disposal.
Definition open.hpp:51
Index(Space &home, Index &a)
Definition open.hpp:60
Index(Space &home, Propagator &p, Council< Index > &c, View x0, int i0)
Definition open.hpp:56
virtual ExecStatus advise(Space &home, Advisor &a0, const Delta &)
Advise function.
Definition open.hpp:100
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:90
Open(Space &home, Open &p)
Definition open.hpp:81
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:172
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:166
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:95
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:121
Council< Index > council
Definition open.hpp:66
int alpha
First and second positions that can still take before.
Definition open.hpp:70
static void post(Home home, OpenViewList< View > list, int before, int after)
Definition open.hpp:181
Open(Home home, OpenViewList< View > list, int before0, int after0)
Definition open.hpp:75
int gamma
First position assigned after, or infinity while none is known.
Definition open.hpp:73
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
size_t size
The size of the propagator (used during subsumption).
Definition core.hpp:1086
friend class Space
Definition core.hpp:1075
friend class Advisor
Definition core.hpp:1077
friend class Council
Definition core.hpp:1078
virtual Val val(const Space &home, View x, int i)=0
Return value of view x at position i.
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Numerical limits for integer variables.
Definition int.hh:119
Value precedence propagators.
Finite domain integers.
Definition lastval.hh:52
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:80
Gecode toplevel namespace
ExecStatus
Definition core.hpp:479
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .