Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
seq-u.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Guido Tack, 2004
12 * Christian Schulte, 2004
13 * Gabor Szokoli, 2004
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
41
42namespace Gecode { namespace Set { namespace Sequence {
43
44 /*
45 * "Sequenced union" propagator
46 *
47 */
48
49 Actor*
50 SeqU::copy(Space& home) {
51 return new (home) SeqU(home,*this);
52 }
53
55 SeqU::propagateSeqUnion(Space& home,
56 bool& modified, ViewArray<SetView>& x,
57 SetView& y) {
58 Region r;
59 GlbRanges<SetView>* XLBs = r.alloc<GlbRanges<SetView> >(x.size());
60 for (int i=x.size(); i--; ) {
61 GlbRanges<SetView> lb(x[i]);
62 XLBs[i]=lb;
63 }
65 GECODE_ME_CHECK_MODIFIED(modified, y.includeI(home,u));
66
67 GLBndSet before(home);
68 for (int i=0; i<x.size(); i++) {
69 LubRanges<SetView> xiub(x[i]);
70 before.includeI(home, xiub);
71 BndSetRanges beforeR(before);
74 if (diff()) {
75 GECODE_ME_CHECK_MODIFIED(modified, x[i].exclude(home, diff.min(),
77 }
78 }
79 before.dispose(home);
80
81 GLBndSet after(home);
82 for (int i=x.size(); i--; ) {
83 LubRanges<SetView> xiub(x[i]);
84 after.includeI(home, xiub);
85 BndSetRanges afterR(after);
88 if (diff()) {
89 int max = diff.max();
90 for (; diff(); ++diff)
91 max = diff.max();
92 GECODE_ME_CHECK_MODIFIED(modified, x[i].exclude(home,
94 max));
95 }
96 }
97 after.dispose(home);
98
99 return ES_FIX;
100 }
101
102 //Enforces sequentiality and ensures y contains union of Xi lower bounds.
104 SeqU::propagate(Space& home, const ModEventDelta& med) {
105 ModEvent me0 = SetView::me(med);
106 bool ubevent = Rel::testSetEventUB(me0);
107 bool anybevent = Rel::testSetEventAnyB(me0);
108 bool cardevent = Rel::testSetEventCard(me0);
109
110 bool modified = false;
111 bool assigned=false;
112 bool oldModified = false;
113
114 do {
115 oldModified = modified;
116 modified = false;
117
118 if (oldModified || modified || anybevent || cardevent)
119 GECODE_ES_CHECK(propagateSeq(home,modified,assigned,x));
120 if (oldModified || modified || anybevent)
121 GECODE_ES_CHECK(propagateSeqUnion(home,modified,x,y));
122 if (oldModified || modified || ubevent)
124 if (oldModified || modified || ubevent)
126 if (oldModified || modified || anybevent)
128 if (oldModified || modified || cardevent || ubevent)
130
131 } while (modified);
132
133 for (int i=x.size(); i--;)
134 if (!x[i].assigned())
135 return ES_FIX;
136 return home.ES_SUBSUMED(*this);
137 }
138
139}}}
140
141// STATISTICS: set-prop
union Gecode::@603::NNF::@65 u
Union depending on nodetype t.
Range iterator for computing set difference.
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
Range iterator for appending arbitrarily many iterators.
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Handle to region.
Definition region.hpp:55
Range iterator for integer sets.
Definition var-imp.hpp:185
void dispose(Space &home)
Free memory used by this set.
Growing sets of integers.
Definition var-imp.hpp:205
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Range iterator for the greatest lower bound.
Definition var-imp.hpp:359
Range iterator for the least upper bound.
Definition var-imp.hpp:317
SeqU(Space &home, SeqU &p)
Constructor for cloning p.
Definition seq-u.hpp:52
ExecStatus propagateSeqUnion(Space &home, bool &modified, ViewArray< SetView > &x, SetView &y)
Definition seq-u.cpp:55
Set view for set variables
Definition view.hpp:56
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition set.hpp:151
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
View arrays.
Definition array.hpp:253
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
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
#define GECODE_ME_CHECK_MODIFIED(modified, me)
Check whether me is failed or modified, and forward failure.
Definition macros.hpp:64
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
const int max
Largest allowed integer in integer set.
Definition set.hh:97
ExecStatus partitionNCard(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:308
ExecStatus unionNXiUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &)
Definition common.hpp:294
ExecStatus partitionNXiLB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:513
ExecStatus partitionNYUB(Space &home, bool &modified, ViewArray< View0 > &x, View1 &y, GLBndSet &unionOfDets)
Definition common.hpp:587
bool testSetEventCard(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:95
bool testSetEventUB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:87
bool testSetEventAnyB(ModEvent me0, ModEvent me1, ModEvent me2)
Definition common.hpp:91
ExecStatus propagateSeq(Space &home, bool &modified, bool &assigned, ViewArray< SetView > &x)
Definition common.hpp:43
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62