Generated on Tue Oct 22 2013 00:49:03 for Gecode by doxygen 1.8.4
tree.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  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2013-03-11 06:26:07 +0100 (Mon, 11 Mar 2013) $ by $Author: tack $
13  * $Revision: 13487 $
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 #include <cmath>
42 
43 namespace Gecode { namespace Int { namespace Cumulative {
44 
45  /*
46  * Omega tree
47  */
48 
49  forceinline void
51  e = 0; env = -Limits::llinfinity;
52  }
53 
54  forceinline void
56  e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
57  }
58 
59  template<class TaskView>
62  : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
63  for (int i=tasks.size(); i--; ) {
64  leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
65  }
66  init();
67  }
68 
69  template<class TaskView>
70  forceinline void
72  leaf(i).e = tasks[i].e();
73  leaf(i).env =
74  static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
75  update(i);
76  }
77 
78  template<class TaskView>
79  forceinline void
81  leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
82  update(i);
83  }
84 
85  template<class TaskView>
86  forceinline long long int
88  return root().env;
89  }
90 
91  /*
92  * Extended Omega tree
93  */
94 
95  forceinline void
97  OmegaNode::init(l,r);
99  }
100 
101  forceinline void
103  OmegaNode::update(l,r);
104  cenv = std::max(plus(l.cenv,r.e), r.cenv);
105  }
106 
107  template<class TaskView> void
109  ci = ci0;
110  for (int i=tasks.size(); i--; ) {
111  leaf(i).e = 0;
112  leaf(i).env = leaf(i).cenv = -Limits::llinfinity;
113  }
114  init();
115  }
116 
117  template<class TaskView> template<class Node>
119  const TaskTree<TaskView,Node>& t)
120  : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
121 
122  template<class TaskView>
123  forceinline long long int
125  // Enter task i
126  leaf(i).e = tasks[i].e();
127  leaf(i).env =
128  static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
129  leaf(i).cenv =
130  static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e();
132 
133  // Perform computation of node for task with minest
134  int met = 0;
135  {
136  long long int e = 0;
137  while (!n_leaf(met)) {
138  if (plus(node[n_right(met)].cenv,e) >
139  static_cast<long long int>(c-ci) * tasks[i].lct()) {
140  met = n_right(met);
141  } else {
142  e += node[n_right(met)].e; met = n_left(met);
143  }
144  }
145  }
146 
147  /*
148  * The following idea to compute the cut in one go is taken from:
149  * Joseph Scott, Filtering Algorithms for Discrete Resources,
150  * Master Thesis, Uppsala University, 2010 (in preparation).
151  */
152 
153  // Now perform split from leaf met upwards
154  long long int a_e = node[met].e;
155  long long int a_env = node[met].env;
156  long long int b_e = 0;
157 
158  while (!n_root(met)) {
159  if (left(met)) {
160  b_e += node[n_right(n_parent(met))].e;
161  } else {
162  a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
163  a_e += node[n_left(n_parent(met))].e;
164  }
165  met = n_parent(met);
166  }
167 
168  return plus(a_env,b_e);
169  }
170 
171 
172 
173  /*
174  * Omega lambda tree
175  */
176 
177  forceinline void
179  OmegaNode::init(l,r);
180  le = 0; lenv = -Limits::llinfinity;
181  resLe = undef; resLenv = undef;
182  }
183 
184  forceinline void
186  OmegaNode::update(l,r);
187  if (l.le + r.e > l.e + r.le) {
188  le = l.le + r.e;
189  resLe = l.resLe;
190  } else {
191  le = l.e + r.le;
192  resLe = r.resLe;
193  }
194  if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) {
195  lenv = r.lenv; resLenv = r.resLenv;
196  } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) {
197  assert(plus(l.env,r.le) > r.lenv);
198  lenv = plus(l.env,r.le); resLenv = r.resLe;
199  } else {
200  assert((plus(l.lenv,r.e) > r.lenv) &&
201  (plus(l.lenv,r.e) > plus(l.env,r.le)));
202  lenv = plus(l.lenv,r.e); resLenv = l.resLenv;
203  }
204  }
205 
206 
207  template<class TaskView>
209  const TaskViewArray<TaskView>& t)
210  : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) {
211  // Enter all tasks into tree (omega = all tasks, lambda = empty)
212  for (int i=tasks.size(); i--; ) {
213  leaf(i).e = tasks[i].e();
214  leaf(i).le = 0;
215  leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
216  leaf(i).lenv = -Limits::llinfinity;
217  leaf(i).resLe = OmegaLambdaNode::undef;
218  leaf(i).resLenv = OmegaLambdaNode::undef;
219  }
220  update();
221  }
222 
223  template<class TaskView>
224  forceinline void
226  // i is in omega
227  assert(leaf(i).env > -Limits::llinfinity);
228  leaf(i).le = leaf(i).e;
229  leaf(i).e = 0;
230  leaf(i).lenv = leaf(i).env;
231  leaf(i).env = -Limits::llinfinity;
232  leaf(i).resLe = i;
233  leaf(i).resLenv = i;
234  update(i);
235  }
236 
237  template<class TaskView>
238  forceinline void
240  // i not in omega but in lambda
241  assert(leaf(i).env == -Limits::llinfinity);
242  assert(leaf(i).lenv > -Limits::llinfinity);
243  leaf(i).le = 0;
244  leaf(i).lenv = -Limits::llinfinity;
245  leaf(i).resLe = OmegaLambdaNode::undef;
246  leaf(i).resLenv = OmegaLambdaNode::undef;
247  update(i);
248  }
249 
250  template<class TaskView>
251  forceinline bool
253  return root().resLenv < 0;
254  }
255 
256  template<class TaskView>
257  forceinline int
259  return root().resLenv;
260  }
261 
262  template<class TaskView>
263  forceinline long long int
265  return root().env;
266  }
267 
268  template<class TaskView>
269  forceinline long long int
271  return root().lenv;
272  }
273 
274 }}}
275 
276 // STATISTICS: int-prop