Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
man.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 ManProp<Box>::ManProp(Home home, Box* b, int n)
39 : Base<Box>(home, b, n) {}
40
41 template<class Box>
42 inline ExecStatus
43 ManProp<Box>::post(Home home, Box* b, int n) {
44 if (n > 1)
45 (void) new (home) ManProp<Box>(home,b,n);
46 return ES_OK;
47 }
48
49 template<class Box>
50 forceinline size_t
52 (void) Base<Box>::dispose(home);
53 return sizeof(*this);
54 }
55
56
57 template<class Box>
60 : Base<Box>(home, p, p.n) {}
61
62 template<class Box>
63 Actor*
65 return new (home) ManProp<Box>(home,*this);
66 }
67
68 template<class Box>
71 Region r;
72
73 // Number of disjoint boxes
74 int* db = r.alloc<int>(n);
75 for (int i=0; i<n; i++)
76 db[i] = n-1;
77
78 // Number of boxes to be eliminated
79 int e = 0;
80
81 for (int i=0; i<n; i++)
82 for (int j=0; j<i; j++)
83 if (b[i].nooverlap(b[j])) {
84 assert(db[i] > 0); assert(db[j] > 0);
85 if (--db[i] == 0) e++;
86 if (--db[j] == 0) e++;
87 continue;
88 } else {
89 GECODE_ES_CHECK(b[i].nooverlap(home,b[j]));
90 }
91
92 if (e == n)
93 return home.ES_SUBSUMED(*this);
94
95 {
96 int i = n-1;
97 while (e > 0) {
98 // Eliminate boxes that do not overlap
99 while (db[i] > 0)
100 i--;
101 b[i].cancel(home, *this);
102 b[i] = b[--n];
103 e--; i--;
104 }
105 if (n < 2)
106 return home.ES_SUBSUMED(*this);
107 }
108
109 return ES_NOFIX;
110 }
111
112}}}
113
114// STATISTICS: int-prop
115
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
Home class for posting propagators
Definition core.hpp:856
Base class for no-overlap propagator.
No-overlap propagator for mandatory boxes.
ManProp(Home home, Box *b, int n)
Constructor for posting.
Definition man.hpp:38
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition man.hpp:70
virtual size_t dispose(Space &home)
Destructor.
Definition man.hpp:51
static ExecStatus post(Home home, Box *b, int n)
Post propagator for boxes b.
Definition man.hpp:43
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition man.hpp:64
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
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.
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