Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
opt.hpp
Go to the documentation of this file.
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, 2011
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
34namespace Gecode { namespace Int { namespace NoOverlap {
35
36 template<class Box>
38 OptProp<Box>::OptProp(Home home, Box* b, int n, int m0)
39 : Base<Box>(home,b,n), m(m0) {
40 for (int i=0; i<m; i++)
41 b[n+i].subscribe(home, *this);
42 }
43
44 template<class Box>
46 OptProp<Box>::post(Home home, Box* b, int n) {
47 // Partition into mandatory and optional boxes
48 if (n > 1) {
49 int p = Base<Box>::partition(b, 0, n);
50 (void) new (home) OptProp<Box>(home,b,p,n-p);
51 }
52 return ES_OK;
53 }
54
55 template<class Box>
56 forceinline size_t
58 for (int i=0; i<m; i++)
59 b[n+i].cancel(home, *this);
60 (void) Base<Box>::dispose(home);
61 return sizeof(*this);
62 }
63
64
65 template<class Box>
68 : Base<Box>(home, p, p.n + p.m), m(p.m) {}
69
70 template<class Box>
71 Actor*
73 return new (home) OptProp<Box>(home,*this);
74 }
75
76 template<class Box>
79 Region r;
80
81 if (BoolView::me(med) == ME_BOOL_VAL) {
82 // Eliminate excluded boxes
83 for (int i=m; i--; )
84 if (b[n+i].excluded()) {
85 b[n+i].cancel(home,*this);
86 b[n+i] = b[n+(--m)];
87 }
88 // Reconsider optional boxes
89 if (m > 0) {
90 int p = Base<Box>::partition(b+n, 0, m);
91 n += p; m -= p;
92 }
93 }
94
95 // Number of disjoint boxes
96 int* db = r.alloc<int>(n);
97 for (int i=0; i<n; i++)
98 db[i] = n-1;
99
100 // Number of boxes to be eliminated
101 int e = 0;
102 for (int i=0; i<n; i++) {
103 assert(b[i].mandatory());
104 for (int j=0; j<i; j++)
105 if (b[i].nooverlap(b[j])) {
106 assert(db[i] > 0); assert(db[j] > 0);
107 if (--db[i] == 0) e++;
108 if (--db[j] == 0) e++;
109 continue;
110 } else {
111 GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
112 }
113 }
114
115 if (m == 0) {
116 if (e == n)
117 return home.ES_SUBSUMED(*this);
118 int i = n-1;
119 while (e > 0) {
120 // Eliminate boxes that do not overlap
121 while (db[i] > 0)
122 i--;
123 b[i].cancel(home, *this);
124 b[i] = b[--n]; b[n] = b[n+m];
125 e--; i--;
126 }
127 if (n < 2)
128 return home.ES_SUBSUMED(*this);
129 }
130
131 // Check whether some optional boxes must be excluded
132 for (int i=m; i--; ) {
133 if (b[n+i].optional()) {
134 for (int j=n; j--; )
135 if (b[n+i].overlap(b[j])) {
136 GECODE_ES_CHECK(b[n+i].exclude(home));
137 b[n+i].cancel(home,*this);
138 b[n+i] = b[n+(--m)];
139 break;
140 }
141 } else {
142 // This might be the case if the same Boolean view occurs
143 // several times and has already been excluded
144 assert(b[n+i].excluded());
145 b[n+i].cancel(home,*this);
146 b[n+i] = b[n+(--m)];
147 }
148 }
149
150 return ES_NOFIX;
151 }
152
153}}}
154
155// STATISTICS: int-prop
156
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
bool overlap(const FloatVal &x, const FloatVal &y)
Test whether x and y overlap.
Definition val.hpp:498
Home class for posting propagators
Definition core.hpp:856
Base class for no-overlap propagator.
int n
Number of mandatory boxes: b[0] ... b[n-1].
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition base.hpp:46
No-overlap propagator for optional boxes.
virtual size_t dispose(Space &home)
Destructor.
Definition opt.hpp:57
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition opt.hpp:46
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition opt.hpp:78
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition opt.hpp:38
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition opt.hpp:72
int m
Number of optional boxes: b[n] ... b[n+m-1].
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
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
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel ipl=IPL_DEF)
Post propagator for rectangle packing.
bool optional(const BoolVarArgs &m)
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:116
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_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
#define forceinline
Definition config.hpp:187