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 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Joseph Scott <joseph.scott@it.uu.se>
9 *
10 * Copyright:
11 * Christian Schulte, 2009
12 * Guido Tack, 2010
13 * Joseph Scott, 2011
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <algorithm>
41
42namespace Gecode { namespace Int { namespace Cumulative {
43
44 /// Sort by capacity
45 template<class TaskView, bool inc>
46 class StoCap {
47 public:
48 /// Sort order
49 bool operator ()(const TaskView& t1, const TaskView& t2) const {
50 return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
51 }
52 };
53
54 /// Sort by prec array
55 class PrecOrder {
56 public:
57 int* prec;
58 /// Constructor
59 PrecOrder(int* prec0) : prec(prec0) {}
60 /// Sort order
61 bool operator ()(int i, int j) const {
62 return prec[i] > prec[j];
63 }
64 };
65
66 template<class TaskView>
67 forceinline ExecStatus
68 edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
69 sort<TaskView,STO_LCT,false>(t);
70
71 Region r;
72
73 ///////////////////////
74 // Detection
75
76 int* prec = r.alloc<int>(t.size());
77 for (int i=0; i<t.size(); i++)
78 prec[i] = t[i].ect();
79
80 OmegaLambdaTree<TaskView> ol(r,c,t);
81
82 for (int j=0; j<t.size(); j++) {
83 while (!ol.lempty() &&
84 (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
85 int i = ol.responsible();
86 prec[i] = std::max(prec[i], t[j].lct());
87 ol.lremove(i);
88 }
89 ol.shift(j);
90 }
91
92 ///////////////////////
93 // Propagation
94
95 // Compute array of unique capacities and a mapping
96 // from the task array to the corresponding entry in
97 // the capacity array
98
99 int* cap = r.alloc<int>(t.size());
100 for (int i=0; i<t.size(); i++)
101 cap[i] = i;
102 SortMap<TaskView,StoCap,true> o(t);
103 Support::quicksort(cap, t.size(), o);
104
105 int* capacities = r.alloc<int>(t.size());
106 int* capInv = r.alloc<int>(t.size());
107 for (int i=t.size(); i--;) {
108 capacities[cap[i]] = t[i].c();
109 capInv[cap[i]] = i;
110 }
111
112 int n_c = 0;
113 for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
114 if (capacities[i] != cur_c)
115 capacities[n_c++] = cur_c = capacities[i];
116 cap[capInv[i]] = n_c-1;
117 }
118 r.free<int>(capInv, t.size());
119
120 // Compute update values for each capacity and LCut
121
122 int* update = r.alloc<int>(t.size()*n_c);
123 for (int i=0; i<t.size()*n_c; i++)
124 update[i] = -Limits::infinity;
125
126 ExtOmegaTree<TaskView> eo(r,c,ol);
127 for (int i=0; i<n_c; i++) {
128 eo.init(capacities[i]);
129 int u = -Limits::infinity;
130 for (int j=t.size(); j--;) {
131 long long int lctj =
132 static_cast<long long int>(c-capacities[i])*t[j].lct();
133 long long int eml = plus(eo.env(j), -lctj);
134 long long int diff_l;
135 if (eml == -Limits::llinfinity)
136 diff_l = -Limits::llinfinity;
137 else
138 diff_l = ceil_div_xx(eml,
139 static_cast<long long int>(capacities[i]));
140 int diff = (diff_l <= -Limits::infinity) ?
141 -Limits::infinity : static_cast<int>(diff_l);
142 u = std::max(u,diff);
143 update[i*t.size()+j] = u;
144 }
145 }
146
147 // Update est by iterating in parallel over the prec array
148 // and the task array, both sorted by lct
149
150 int* precMap = r.alloc<int>(t.size());
151 for (int i=0; i<t.size(); i++)
152 precMap[i] = i;
153 PrecOrder po(prec);
154 Support::quicksort(precMap, t.size(), po);
155
156 int curJ = 0;
157 for (int i=0; i<t.size(); i++) {
158 // discard any curJ with lct > prec[i]:
159 while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
160 curJ++;
161 if (curJ >= t.size())
162 break;
163 // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
164 int locJ = curJ;
165 do {
166 if (t[locJ].lct() != t[precMap[i]].lct()) {
167 GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
168 break;
169 }
170 } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
171 }
172
173 return ES_OK;
174 }
175
176 template<class Task>
177 ExecStatus
178 edgefinding(Space& home, int c, TaskArray<Task>& t) {
179 TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
180 GECODE_ES_CHECK(edgefinding(home,c,f));
181 TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
182 GECODE_ES_CHECK(edgefinding(home,c,b));
183 return ES_OK;
184 }
185
186}}}
187
188// STATISTICS: int-prop