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