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 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
51 ManProp<Box>::dispose(Space& home) {
52 (void) Base<Box>::dispose(home);
53 return sizeof(*this);
54 }
55
56
57 template<class Box>
58 forceinline
59 ManProp<Box>::ManProp(Space& home, ManProp<Box>& p)
60 : Base<Box>(home, p, p.n) {}
61
62 template<class Box>
63 Actor*
64 ManProp<Box>::copy(Space& home) {
65 return new (home) ManProp<Box>(home,*this);
66 }
67
68 template<class Box>
69 ExecStatus
70 ManProp<Box>::propagate(Space& home, const ModEventDelta&) {
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