Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
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
long long int env(void) const
Return energy envelope of all tasks.
Definition: tree.hpp:87
long long int env(void) const
Return energy envelope of all tasks.
Definition: tree.hpp:264
long long int cenv
Energy envelope for subtree.
Definition: cumulative.hh:589
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
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
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
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Node for an omega lambda tree.
Definition: cumulative.hh:629
long long int env
Energy envelope for subtree.
Definition: cumulative.hh:556
int responsible(void) const
Return responsible task.
Definition: tree.hpp:258
Handle to region.
Definition: region.hpp:61
Gecode::FloatVal c(-8, 8)
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:50
Gecode::IntArgs i(4, 1, 2, 3, 4)
OmegaTree(Region &r, int c, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t and capacity c.
Definition: tree.hpp:60
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:55
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:126
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int resLe
Node which is responsible for le.
Definition: cumulative.hh:638
void init(void)
Initialize tree after leaves have been initialized.
bool lempty(void) const
Whether has responsible task.
Definition: tree.hpp:252
int resLenv
Node which is responsible for lenv.
Definition: cumulative.hh:640
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
ExtOmegaTree(Region &r, int c, const TaskTree< TaskView, Node > &t)
Initialize tree for tasks t and capacity c.
Definition: tree.hpp:118
long long int le
Energy for subtree.
Definition: cumulative.hh:634
void init(const ExtOmegaNode &l, const ExtOmegaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:96
void insert(int i)
Insert task with index i.
Definition: tree.hpp:71
static const int undef
Undefined task.
Definition: cumulative.hh:632
Node for an extended omega tree.
Definition: cumulative.hh:586
#define forceinline
Definition: config.hpp:132
OmegaNode & leaf(int i)
Return leaf for task i.
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:208
void remove(int i)
Remove task with index i.
Definition: tree.hpp:80
Gecode toplevel namespace
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
const long long int llinfinity
Infinity for long long integers.
Definition: int.hh:123
Node for an omega tree.
Definition: cumulative.hh:551
void update(const ExtOmegaNode &l, const ExtOmegaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:102
Task trees for task views with node type Node.
Definition: task.hh:365
long long int e
Energy for subtree.
Definition: cumulative.hh:554
long long int lenv
Energy envelope for subtree.
Definition: cumulative.hh:636
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:178
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:185
void lremove(int i)
Remove task with index i from lambda.
Definition: tree.hpp:239