Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
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 
34 namespace 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 
Box * b
Boxes.
Definition: no-overlap.hh:237
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition: set-op.hpp:137
bool optional(const BoolVarArgs &m)
Definition: no-overlap.cpp:41
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3563
int m
Number of optional boxes: b[n] ... b[n+m-1].
Definition: no-overlap.hh:299
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: opt.hpp:78
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:116
Gecode toplevel namespace
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition: opt.hpp:46
virtual size_t dispose(Space &home)
Destructor.
Definition: opt.hpp:57
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: opt.hpp:72
Home class for posting propagators
Definition: core.hpp:856
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: view.hpp:552
Handle to region.
Definition: region.hpp:55
static int partition(Box *b, int i, int n)
Partition n boxes b starting at position i.
Definition: base.hpp:46
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
OptProp(Home home, Box *b, int n, int m)
Constructor for posting.
Definition: opt.hpp:38
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
No-overlap propagator for optional boxes.
Definition: no-overlap.hh:294
void cancel(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:81
bool overlap(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:498
Base class for no-overlap propagator.
Definition: no-overlap.hh:234
#define forceinline
Definition: config.hpp:192
void nooverlap(Home home, const IntVarArgs &x, const IntArgs &w, const IntVarArgs &y, const IntArgs &h, IntPropLevel)
Post propagator for rectangle packing.
Definition: no-overlap.cpp:51
int n
Number of mandatory boxes: b[0] ... b[n-1].
Definition: no-overlap.hh:239
void subscribe(Space &home, Propagator &p, IntSet &y)
Definition: rel.hpp:71
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475
Gecode::IntArgs i({1, 2, 3, 4})
@ ES_OK
Execution is okay.
Definition: core.hpp:476
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
ExecStatus
Definition: core.hpp:472