Generated on Wed Jan 24 2018 21:22:26 for Gecode by doxygen 1.8.13
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  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * Last modified:
10  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <algorithm>
39 
40 namespace Gecode { namespace Int { namespace Unary {
41 
42  /*
43  * Omega tree
44  */
45 
46  forceinline void
48  p = 0; ect = -Limits::infinity;
49  }
50 
51  forceinline void
53  p = l.p + r.p;
54  ect = std::max(plus(l.ect,r.p), r.ect);
55  }
56 
57  template<class TaskView>
60  : TaskTree<TaskView,OmegaNode>(r,t) {
61  for (int i=tasks.size(); i--; ) {
62  leaf(i).p = 0; leaf(i).ect = -Limits::infinity;
63  }
64  init();
65  }
66 
67  template<class TaskView>
68  forceinline void
70  leaf(i).p = tasks[i].pmin();
71  leaf(i).ect = tasks[i].est()+tasks[i].pmin();
72  update(i);
73  }
74 
75  template<class TaskView>
76  forceinline void
78  leaf(i).p = 0; leaf(i).ect = -Limits::infinity;
79  update(i);
80  }
81 
82  template<class TaskView>
83  forceinline int
85  return root().ect;
86  }
87 
88  template<class TaskView>
89  forceinline int
91  // Check whether task i is in?
92  OmegaTree<TaskView>& o = const_cast<OmegaTree<TaskView>&>(*this);
93  if (o.leaf(i).ect != -Limits::infinity) {
94  o.remove(i);
95  int ect = o.root().ect;
96  o.insert(i);
97  return ect;
98  } else {
99  return root().ect;
100  }
101  }
102 
103 
104 
105  /*
106  * Omega lambda tree
107  */
108 
109  forceinline void
111  OmegaNode::init(l,r);
112  lp = p; lect = ect; resEct = undef; resLp = undef;
113  }
114 
115  forceinline void
117  OmegaNode::update(l,r);
118  if (l.lp + r.p > l.p + r.lp) {
119  resLp = l.resLp;
120  lp = l.lp + r.p;
121  } else {
122  resLp = r.resLp;
123  lp = l.p + r.lp;
124  }
125  if ((r.lect >= plus(l.ect,r.lp)) && (r.lect >= plus(l.lect,r.p))) {
126  lect = r.lect; resEct = r.resEct;
127  } else if (plus(l.ect,r.lp) >= plus(l.lect,r.p)) {
128  assert(plus(l.ect,r.lp) > r.lect);
129  lect = plus(l.ect,r.lp); resEct = r.resLp;
130  } else {
131  assert((plus(l.lect,r.p) > r.lect) &&
132  (plus(l.lect,r.p) > plus(l.ect,r.lp)));
133  lect = plus(l.lect,r.p); resEct = l.resEct;
134  }
135  }
136 
137 
138  template<class TaskView>
141  const TaskViewArray<TaskView>& t,
142  bool inc)
143  : TaskTree<TaskView,OmegaLambdaNode>(r,t) {
144  if (inc) {
145  // Enter all tasks into tree (omega = all tasks, lambda = empty)
146  for (int i=tasks.size(); i--; ) {
147  leaf(i).p = leaf(i).lp = tasks[i].pmin();
148  leaf(i).ect = leaf(i).lect = tasks[i].est()+tasks[i].pmin();
149  leaf(i).resEct = OmegaLambdaNode::undef;
150  leaf(i).resLp = OmegaLambdaNode::undef;
151  }
152  update();
153  } else {
154  // Enter no tasks into tree (omega = empty, lambda = empty)
155  for (int i=tasks.size(); i--; ) {
156  leaf(i).p = leaf(i).lp = 0;
157  leaf(i).ect = leaf(i).lect = -Limits::infinity;
158  leaf(i).resEct = OmegaLambdaNode::undef;
159  leaf(i).resLp = OmegaLambdaNode::undef;
160  }
161  init();
162  }
163  }
164 
165  template<class TaskView>
166  forceinline void
168  // That means that i is in omega
169  assert(leaf(i).ect > -Limits::infinity);
170  leaf(i).p = 0;
171  leaf(i).ect = -Limits::infinity;
172  leaf(i).resEct = i;
173  leaf(i).resLp = i;
174  update(i);
175  }
176 
177  template<class TaskView>
178  forceinline void
180  leaf(i).p = tasks[i].pmin();
181  leaf(i).ect = tasks[i].est()+tasks[i].pmin();
182  update(i);
183  }
184 
185  template<class TaskView>
186  forceinline void
188  leaf(i).lp = tasks[i].pmin();
189  leaf(i).lect = tasks[i].est()+tasks[i].pmin();
190  leaf(i).resEct = i;
191  leaf(i).resLp = i;
192  update(i);
193  }
194 
195  template<class TaskView>
196  forceinline void
198  leaf(i).lp = 0;
199  leaf(i).lect = -Limits::infinity;
200  leaf(i).resEct = OmegaLambdaNode::undef;
201  leaf(i).resLp = OmegaLambdaNode::undef;
202  update(i);
203  }
204 
205  template<class TaskView>
206  forceinline bool
208  return root().resEct < 0;
209  }
210 
211  template<class TaskView>
212  forceinline int
214  return root().resEct;
215  }
216 
217  template<class TaskView>
218  forceinline int
220  return root().ect;
221  }
222 
223  template<class TaskView>
224  forceinline int
226  return root().lect;
227  }
228 
229 }}}
230 
231 // STATISTICS: int-prop
int resEct
Node which is responsible for lect.
Definition: unary.hh:708
Node for an omega tree.
Definition: unary.hh:664
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:237
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:110
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
int lp
Processing times for subtree.
Definition: unary.hh:704
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:52
int lect(void) const
Return earliest completion time of all tasks excluding lambda tasks.
Definition: tree.hpp:225
void linsert(int i)
Insert task with index i to lambda.
Definition: tree.hpp:187
Handle to region.
Definition: region.hpp:61
int ect
Earliest completion time for subtree.
Definition: unary.hh:669
void insert(int i)
Insert task with index i.
Definition: tree.hpp:69
int lect
Earliest completion times for subtree.
Definition: unary.hh:706
void oinsert(int i)
Insert task with index i to omega.
Definition: tree.hpp:179
bool lempty(void) const
Whether has responsible task.
Definition: tree.hpp:207
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Omega trees for computing ect of task sets.
Definition: unary.hh:678
Gecode::IntArgs i(4, 1, 2, 3, 4)
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition: tree.hpp:116
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:126
void remove(int i)
Remove task with index i.
Definition: tree.hpp:77
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:119
int ect(void) const
Return earliest completion time of all tasks.
Definition: tree.hpp:219
Node for an omega lambda tree.
Definition: unary.hh:699
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:43
int responsible(void) const
Return responsible task.
Definition: tree.hpp:213
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
int resLp
Node which is responsible for lp.
Definition: unary.hh:710
OmegaLambdaTree(Region &r, const TaskViewArray< TaskView > &t, bool inc=true)
Initialize tree for tasks t with all tasks included, if inc is true.
Definition: tree.hpp:140
int ect(void) const
Return earliest completion time of all tasks.
Definition: tree.hpp:84
const int infinity
Infinity for integers.
Definition: int.hh:120
OmegaTree(Region &r, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t.
Definition: tree.hpp:59
const OmegaNode & root(void) const
Return root node.
Definition: tree.hpp:113
#define forceinline
Definition: config.hpp:173
void lremove(int i)
Remove task with index i from lambda.
Definition: tree.hpp:197
OmegaNode & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:107
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition: tree.hpp:47
void shift(int i)
Shift task with index i from omega to lambda.
Definition: tree.hpp:167
Gecode toplevel namespace
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:373
static const int undef
Undefined task.
Definition: unary.hh:702
Task trees for task views with node type Node.
Definition: task.hh:369
int p
Processing time for subtree.
Definition: unary.hh:667