Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
int.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * David Rijsman <David.Rijsman@quintiq.com>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 *
9 * Copyright:
10 * David Rijsman, 2009
11 * Christian Schulte, 2009
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38namespace Gecode { namespace Int { namespace Sequence {
39
40 template<class View, class Val>
43 int q0, int l0, int u0)
44 : Propagator(home), x(x0), s(s0), q(q0), l(l0), u(u0),
45 vvsamax(home,x,s0,q0), vvsamin(home,x,s0,q0), ac(home),
46 tofail(false) {
47 home.notice(*this,AP_DISPOSE);
48 bool assigned = false;
49 for (int i=x.size(); i--; ) {
50 if (undecided(x[i],s))
51 x[i].subscribe(home,*new (home) SupportAdvisor<View>(home,*this,ac,i));
52 if (x[i].assigned())
53 assigned = true;
54 }
55 View::schedule(home,*this,assigned ? ME_INT_VAL : ME_INT_BND);
56 }
57
58 template<class View, class Val>
61 : Propagator(home,p), s(p.s), q(p.q), l(p.l), u(p.u),
62 vvsamax(), vvsamin(), tofail(p.tofail) {
63 x.update(home,p.x);
64 ac.update(home,p.ac);
65 vvsamax.update(home,p.vvsamax);
66 vvsamin.update(home,p.vvsamin);
67 }
68
69 template<class View,class Val>
72 SupportAdvisor<View>& a = static_cast<SupportAdvisor<View>&>(_a);
73 ExecStatus status = vvsamax.advise(home,x,s,q,a.i,d);
74 if ( ES_NOFIX == vvsamin.advise(home,x,s,q,a.i,d) ) {
75 status = ES_NOFIX;
76 }
77
78 if (!undecided(x[a.i],s)) {
79 if (!x[a.i].assigned())
80 x[a.i].cancel(home,a);
81
82 if ( ES_NOFIX == status ) {
83 return home.ES_NOFIX_DISPOSE(ac,a);
84 } else {
85 return home.ES_FIX_DISPOSE(ac,a);
86 }
87 }
88
89 if ((status == ES_FAILED) && disabled()) {
90 tofail = true;
91 return ES_FIX;
92 }
93
94 return status;
95 }
96
97 template<class View, class Val>
98 forceinline size_t
100 home.ignore(*this,AP_DISPOSE);
101 ac.dispose(home);
102 s.~Val();
103 (void) Propagator::dispose(home);
104 return sizeof(*this);
105 }
106
107 template<class View, class Val>
109 Sequence<View,Val>::check(ViewArray<View>& x, Val s, int q, int l, int u) {
110 Region r;
111 // could do this with an array of length q...
112 int* upper = r.alloc<int>(x.size()+1);
113 int* lower = r.alloc<int>(x.size()+1);
114 upper[0] = 0;
115 lower[0] = 0;
116 for ( int j=0; j<x.size(); j++ ) {
117 upper[j+1] = upper[j];
118 lower[j+1] = lower[j];
119 if (includes(x[j],s)) {
120 upper[j+1] += 1;
121 } else if (excludes(x[j],s)) {
122 lower[j+1] += 1;
123 }
124 if ( j+1 >= q && (q - l < lower[j+1] - lower[j+1-q] || upper[j+1] - upper[j+1-q] > u) ) {
125 return ES_FAILED;
126 }
127 }
128 return ES_OK;
129 }
130
131 template<class View, class Val>
133 Sequence<View,Val>::post(Home home, ViewArray<View>& x, Val s, int q, int l, int u) {
134 GECODE_ES_CHECK(check(x,s,q,l,u));
135 Sequence<View,Val>* p = new (home) Sequence<View,Val>(home,x,s,q,l,u);
136
137 GECODE_ES_CHECK(p->vvsamax.propagate(home,x,s,q,l,u));
138 GECODE_ES_CHECK(p->vvsamin.propagate(home,x,s,q,l,u));
139
140 return ES_OK;
141 }
142
143 template<class View, class Val>
144 Actor*
146 return new (home) Sequence<View,Val>(home,*this);
147 }
148
149 template<class View, class Val>
152 return PropCost::cubic(PropCost::HI,x.size());
153 }
154
155 template<class View, class Val>
156 void
158 for (int i=x.size(); i--; )
159 if (!undecided(x[i],s))
160 x[i].schedule(home,*this,x[i].assigned() ? ME_INT_VAL : ME_INT_BND);
161 if (tofail)
162 View::schedule(home,*this,ME_INT_BND);
163 }
164
165 template<class View, class Val>
168 if (tofail)
169 return ES_FAILED;
170
171 GECODE_ES_CHECK(vvsamax.propagate(home,x,s,q,l,u));
172 GECODE_ES_CHECK(vvsamin.propagate(home,x,s,q,l,u));
173
174 for (int i=x.size(); i--; )
175 if (undecided(x[i],s))
176 return ES_FIX;
177
178 return home.ES_SUBSUMED(*this);
179 }
180
181}}}
182
183// STATISTICS: int-prop
184
NNF * l
Left subtree.
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
int p
Number of positive literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Base-class for advisors.
Definition core.hpp:1292
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
Home class for posting propagators
Definition core.hpp:856
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3219
Sequence propagator for array of integers
Definition sequence.hh:101
virtual void reschedule(Space &home)
Schedule function.
Definition int.hpp:157
ExecStatus advise(Space &home, Advisor &_a, const Delta &d)
Advise function.
Definition int.hpp:71
static ExecStatus post(Home home, ViewArray< View > &x, Val s, int q, int l, int u)
Post propagator for.
Definition int.hpp:133
virtual Actor * copy(Space &home)
Perform copying during cloning.
Definition int.hpp:145
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition int.hpp:167
static ExecStatus check(ViewArray< View > &x, Val s, int q, int l, int u)
Check for consistency.
Definition int.hpp:109
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition int.hpp:99
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition int.hpp:151
Sequence(Space &home, Sequence &p)
Constructor for cloning p.
Definition int.hpp:60
Class for advising the propagator.
Definition view.hpp:44
void update(Space &home, ViewValSupportArray< View, Val, iss > &x)
Cloning.
Definition view.hpp:461
Propagation cost.
Definition core.hpp:486
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition core.hpp:4778
@ HI
Expensive.
Definition core.hpp:514
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
View arrays.
Definition array.hpp:253
ExecStatus ES_FIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed
Definition core.hpp:3880
ExecStatus ES_NOFIX_DISPOSE(Council< A > &c, A &a)
Advisor a must be disposed and its propagator must be run
Definition core.hpp:3887
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4074
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
bool excludes(const View &x, int s)
Test whether all values of view x are excluded from s.
Definition set-op.hpp:89
bool includes(const View &x, int s)
Test whether all values of view x are included in s.
Definition set-op.hpp:72
bool undecided(const View &x, int s)
Test whether no decision on inclusion or exclusion of values of view x in s can be made.
Definition set-op.hpp:106
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187