this repo has no description
dekker.one
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>
37 forceinline
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>
45 ExecStatus
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
57 OptProp<Box>::dispose(Space& home) {
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>
66 forceinline
67 OptProp<Box>::OptProp(Space& home, OptProp<Box>& p)
68 : Base<Box>(home, p, p.n + p.m), m(p.m) {}
69
70 template<class Box>
71 Actor*
72 OptProp<Box>::copy(Space& home) {
73 return new (home) OptProp<Box>(home,*this);
74 }
75
76 template<class Box>
77 ExecStatus
78 OptProp<Box>::propagate(Space& home, const ModEventDelta& med) {
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