Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
edge-finding.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  * 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  * Last modified:
16  * $Date: 2013-03-11 06:26:07 +0100 (Mon, 11 Mar 2013) $ by $Author: tack $
17  * $Revision: 13487 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <algorithm>
45 
46 namespace Gecode { namespace Int { namespace Cumulative {
47 
49  template<class TaskView, bool inc>
50  class StoCap {
51  public:
53  bool operator ()(const TaskView& t1, const TaskView& t2) const {
54  return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
55  }
56  };
57 
59  class PrecOrder {
60  public:
61  int* prec;
63  PrecOrder(int* prec0) : prec(prec0) {}
65  bool operator ()(int i, int j) const {
66  return prec[i] > prec[j];
67  }
68  };
69 
70  template<class TaskView>
73  sort<TaskView,STO_LCT,false>(t);
74 
75  Region r(home);
76 
78  // Detection
79 
80  int* prec = r.alloc<int>(t.size());
81  for (int i=t.size(); i--; )
82  prec[i] = t[i].ect();
83 
84  OmegaLambdaTree<TaskView> ol(r,c,t);
85 
86  for (int j=0; j<t.size(); j++) {
87  while (!ol.lempty() &&
88  (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
89  int i = ol.responsible();
90  prec[i] = std::max(prec[i], t[j].lct());
91  ol.lremove(i);
92  }
93  ol.shift(j);
94  }
95 
97  // Propagation
98 
99  // Compute array of unique capacities and a mapping
100  // from the task array to the corresponding entry in
101  // the capacity array
102 
103  int* cap = r.alloc<int>(t.size());
104  for (int i=t.size(); i--;)
105  cap[i] = i;
107  Support::quicksort(cap, t.size(), o);
108 
109  int* capacities = r.alloc<int>(t.size());
110  int* capInv = r.alloc<int>(t.size());
111  for (int i=t.size(); i--;) {
112  capacities[cap[i]] = t[i].c();
113  capInv[cap[i]] = i;
114  }
115 
116  int n_c = 0;
117  for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
118  if (capacities[i] != cur_c)
119  capacities[n_c++] = cur_c = capacities[i];
120  cap[capInv[i]] = n_c-1;
121  }
122  r.free<int>(capInv, t.size());
123 
124  // Compute update values for each capacity and LCut
125 
126  int* update = r.alloc<int>(t.size()*n_c);
127  for (int i=t.size()*n_c; i--;)
128  update[i] = -Int::Limits::infinity;
129 
130  ExtOmegaTree<TaskView> eo(r,c,ol);
131  for (int i=0; i<n_c; i++) {
132  eo.init(capacities[i]);
133  int u = -Int::Limits::infinity;
134  for (int j=t.size(); j--;) {
135  long long int lctj =
136  static_cast<long long int>(c-capacities[i])*t[j].lct();
137  long long int eml = plus(eo.env(j), -lctj);
138  long long int diff_l;
139  if (eml == -Limits::llinfinity)
140  diff_l = -Limits::llinfinity;
141  else
142  diff_l = ceil_div_xx(eml,
143  static_cast<long long int>(capacities[i]));
144  int diff = (diff_l <= -Limits::infinity) ?
145  -Limits::infinity : static_cast<int>(diff_l);
146  u = std::max(u,diff);
147  update[i*t.size()+j] = u;
148  }
149  }
150 
151  // Update est by iterating in parallel over the prec array
152  // and the task array, both sorted by lct
153 
154  int* precMap = r.alloc<int>(t.size());
155  for (int i=t.size(); i--;)
156  precMap[i] = i;
157  PrecOrder po(prec);
158  Support::quicksort(precMap, t.size(), po);
159 
160  int curJ = 0;
161  for (int i=0; i<t.size(); i++) {
162  // discard any curJ with lct > prec[i]:
163  while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
164  curJ++;
165  if (curJ >= t.size())
166  break;
167  // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
168  int locJ = curJ;
169  do {
170  if (t[locJ].lct() != t[precMap[i]].lct()) {
171  GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
172  break;
173  }
174  } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
175  }
176 
177  return ES_OK;
178  }
179 
180  template<class Task>
181  ExecStatus
184  GECODE_ES_CHECK(edgefinding(home,c,f));
186  GECODE_ES_CHECK(edgefinding(home,c,b));
187  return ES_OK;
188  }
189 
190 }}}
191 
192 // STATISTICS: int-prop
long long int env(int i)
Compute update for task with index i.
Definition: tree.hpp:124
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:233
Omega-lambda trees for computing ect of task sets.
Definition: cumulative.hh:649
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void shift(int i)
Shift task with index i from omega to lambda.
Definition: tree.hpp:225
PrecOrder(int *prec0)
Constructor.
Omega trees for computing ect of task sets.
Definition: cumulative.hh:598
Task array.
Definition: task.hh:167
int responsible(void) const
Return responsible task.
Definition: tree.hpp:258
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1362
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
Gecode::FloatVal c(-8, 8)
bool operator()(int i, int j) const
Sort order.
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
Sorting maps rather than tasks.
Definition: sort.hpp:76
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
bool lempty(void) const
Whether has responsible task.
Definition: tree.hpp:252
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:43
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition: tree.hpp:270
void init(int ci)
Initialize tasks for current capacity ci.
Definition: tree.hpp:108
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:86
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:139
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
union Gecode::@518::NNF::@57 u
Union depending on nodetype t.
const int infinity
Infinity for integers.
Definition: int.hh:117
ExecStatus
Definition: core.hpp:523
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
const long long int llinfinity
Infinity for long long integers.
Definition: int.hh:123
ExecStatus edgefinding(Space &home, int c, TaskViewArray< TaskView > &t)
void lremove(int i)
Remove task with index i from lambda.
Definition: tree.hpp:239