Generated on Mon Jul 27 2020 00:00:00 for Gecode by doxygen 1.8.18
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  * This file is part of Gecode, the generic constraint
12  * development environment:
13  * http://www.gecode.org
14  *
15  * Permission is hereby granted, free of charge, to any person obtaining
16  * a copy of this software and associated documentation files (the
17  * "Software"), to deal in the Software without restriction, including
18  * without limitation the rights to use, copy, modify, merge, publish,
19  * distribute, sublicense, and/or sell copies of the Software, and to
20  * permit persons to whom the Software is furnished to do so, subject to
21  * the following conditions:
22  *
23  * The above copyright notice and this permission notice shall be
24  * included in all copies or substantial portions of the Software.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33  *
34  */
35 
36 #include <algorithm>
37 #include <cmath>
38 
39 namespace Gecode { namespace Int { namespace Cumulative {
40 
41  /*
42  * Omega tree
43  */
44 
45  forceinline void
47  e = 0; env = -Limits::llinfinity;
48  }
49 
50  forceinline void
52  e = l.e + r.e; env = std::max(plus(l.env,r.e), r.env);
53  }
54 
55  template<class TaskView>
58  : TaskTree<TaskView,OmegaNode>(r,t), c(c0) {
59  for (int i=0; i<tasks.size(); i++) {
60  leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
61  }
62  init();
63  }
64 
65  template<class TaskView>
66  forceinline void
68  leaf(i).e = tasks[i].e();
69  leaf(i).env =
70  static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
71  update(i);
72  }
73 
74  template<class TaskView>
75  forceinline void
77  leaf(i).e = 0; leaf(i).env = -Limits::llinfinity;
78  update(i);
79  }
80 
81  template<class TaskView>
82  forceinline long long int
84  return root().env;
85  }
86 
87  /*
88  * Extended Omega tree
89  */
90 
91  forceinline void
95  }
96 
97  forceinline void
100  cenv = std::max(plus(l.cenv,r.e), r.cenv);
101  }
102 
103  template<class TaskView> void
105  ci = ci0;
106  for (int i=0; i<tasks.size(); i++) {
107  leaf(i).e = 0;
108  leaf(i).env = leaf(i).cenv = -Limits::llinfinity;
109  }
110  init();
111  }
112 
113  template<class TaskView> template<class Node>
115  const TaskTree<TaskView,Node>& t)
116  : TaskTree<TaskView,ExtOmegaNode>(r,t), c(c0) {}
117 
118  template<class TaskView>
119  forceinline long long int
121  // Enter task i
122  leaf(i).e = tasks[i].e();
123  leaf(i).env =
124  static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
125  leaf(i).cenv =
126  static_cast<long long int>(c-ci)*tasks[i].est()+tasks[i].e();
128 
129  // Perform computation of node for task with minest
130  int met = 0;
131  {
132  long long int e = 0;
133  while (!n_leaf(met)) {
134  if (plus(node[n_right(met)].cenv,e) >
135  static_cast<long long int>(c-ci) * tasks[i].lct()) {
136  met = n_right(met);
137  } else {
138  e += node[n_right(met)].e; met = n_left(met);
139  }
140  }
141  }
142 
143  /*
144  * The following idea to compute the cut in one go is taken from:
145  * Joseph Scott, Filtering Algorithms for Discrete Resources,
146  * Master Thesis, Uppsala University, 2010 (in preparation).
147  */
148 
149  // Now perform split from leaf met upwards
150  long long int a_e = node[met].e;
151  long long int a_env = node[met].env;
152  long long int b_e = 0;
153 
154  while (!n_root(met)) {
155  if (left(met)) {
156  b_e += node[n_right(n_parent(met))].e;
157  } else {
158  a_env = std::max(a_env, plus(node[n_left(n_parent(met))].env,a_e));
159  a_e += node[n_left(n_parent(met))].e;
160  }
161  met = n_parent(met);
162  }
163 
164  return plus(a_env,b_e);
165  }
166 
167 
168 
169  /*
170  * Omega lambda tree
171  */
172 
173  forceinline void
176  le = 0; lenv = -Limits::llinfinity;
177  resLe = undef; resLenv = undef;
178  }
179 
180  forceinline void
183  if (l.le + r.e > l.e + r.le) {
184  le = l.le + r.e;
185  resLe = l.resLe;
186  } else {
187  le = l.e + r.le;
188  resLe = r.resLe;
189  }
190  if ((r.lenv >= plus(l.env,r.le)) && (r.lenv >= plus(l.lenv,r.e))) {
191  lenv = r.lenv; resLenv = r.resLenv;
192  } else if (plus(l.env,r.le) >= plus(l.lenv,r.e)) {
193  assert(plus(l.env,r.le) > r.lenv);
194  lenv = plus(l.env,r.le); resLenv = r.resLe;
195  } else {
196  assert((plus(l.lenv,r.e) > r.lenv) &&
197  (plus(l.lenv,r.e) > plus(l.env,r.le)));
198  lenv = plus(l.lenv,r.e); resLenv = l.resLenv;
199  }
200  }
201 
202 
203  template<class TaskView>
205  const TaskViewArray<TaskView>& t)
206  : TaskTree<TaskView,OmegaLambdaNode>(r,t), c(c0) {
207  // Enter all tasks into tree (omega = all tasks, lambda = empty)
208  for (int i=0; i<tasks.size(); i++) {
209  leaf(i).e = tasks[i].e();
210  leaf(i).le = 0;
211  leaf(i).env = static_cast<long long int>(c)*tasks[i].est()+tasks[i].e();
212  leaf(i).lenv = -Limits::llinfinity;
213  leaf(i).resLe = OmegaLambdaNode::undef;
214  leaf(i).resLenv = OmegaLambdaNode::undef;
215  }
216  update();
217  }
218 
219  template<class TaskView>
220  forceinline void
222  // i is in omega
223  assert(leaf(i).env > -Limits::llinfinity);
224  leaf(i).le = leaf(i).e;
225  leaf(i).e = 0;
226  leaf(i).lenv = leaf(i).env;
227  leaf(i).env = -Limits::llinfinity;
228  leaf(i).resLe = i;
229  leaf(i).resLenv = i;
230  update(i);
231  }
232 
233  template<class TaskView>
234  forceinline void
236  // i not in omega but in lambda
237  assert(leaf(i).env == -Limits::llinfinity);
238  assert(leaf(i).lenv > -Limits::llinfinity);
239  leaf(i).le = 0;
240  leaf(i).lenv = -Limits::llinfinity;
241  leaf(i).resLe = OmegaLambdaNode::undef;
242  leaf(i).resLenv = OmegaLambdaNode::undef;
243  update(i);
244  }
245 
246  template<class TaskView>
247  forceinline bool
249  return root().resLenv < 0;
250  }
251 
252  template<class TaskView>
253  forceinline int
255  return root().resLenv;
256  }
257 
258  template<class TaskView>
259  forceinline long long int
261  return root().env;
262  }
263 
264  template<class TaskView>
265  forceinline long long int
267  return root().lenv;
268  }
269 
270 }}}
271 
272 // STATISTICS: int-prop
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:46
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition: tree.hpp:266
OmegaNode & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:103
long long int le
Energy for subtree.
Definition: cumulative.hh:630
void init(const ExtOmegaNode &l, const ExtOmegaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:92
static const int undef
Undefined task.
Definition: cumulative.hh:628
void remove(int i)
Remove task with index i.
Definition: tree.hpp:76
int responsible(void) const
Return responsible task.
Definition: tree.hpp:254
long long int e
Energy for subtree.
Definition: cumulative.hh:550
const long long int llinfinity
Infinity for long long integers.
Definition: int.hh:126
NodeType t
Type of node.
Definition: bool-expr.cpp:230
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition: tree.hpp:39
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:51
OmegaTree(Region &r, int c, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t and capacity c.
Definition: tree.hpp:56
long long int env(void) const
Return energy envelope of all tasks.
Definition: tree.hpp:260
OmegaLambdaTree(Region &r, int c, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t and capcity c with all tasks included in omega.
Definition: tree.hpp:204
Gecode toplevel namespace
void update(const ExtOmegaNode &l, const ExtOmegaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:98
long long int lenv
Energy envelope for subtree.
Definition: cumulative.hh:632
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
Int ci(step1)
void insert(int i)
Insert task with index i.
Definition: tree.hpp:67
Handle to region.
Definition: region.hpp:55
Task trees for task views with node type Node.
Definition: task.hh:365
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:174
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:181
void lremove(int i)
Remove task with index i from lambda.
Definition: tree.hpp:235
bool lempty(void) const
Whether has responsible task.
Definition: tree.hpp:248
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:115
int c
Capacity.
Definition: cumulative.hh:653
void shift(int i)
Shift task with index i from omega to lambda.
Definition: tree.hpp:221
Node for an omega lambda tree.
Definition: cumulative.hh:625
ExtOmegaTree(Region &r, int c, const TaskTree< TaskView, Node > &t)
Initialize tree for tasks t and capacity c.
Definition: tree.hpp:114
long long int env
Energy envelope for subtree.
Definition: cumulative.hh:552
Node for an extended omega tree.
Definition: cumulative.hh:582
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:122
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
long long int env(void) const
Return energy envelope of all tasks.
Definition: tree.hpp:83
Node for an omega tree.
Definition: cumulative.hh:547
long long int cenv
Energy envelope for subtree.
Definition: cumulative.hh:585
#define forceinline
Definition: config.hpp:185
Task view array.
Definition: task.hh:233
Gecode::FloatVal c(-8, 8)
int resLe
Node which is responsible for le.
Definition: cumulative.hh:634
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
Gecode::IntArgs i({1, 2, 3, 4})
int resLenv
Node which is responsible for lenv.
Definition: cumulative.hh:636
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
long long int env(int i)
Compute update for task with index i.
Definition: tree.hpp:120