this repo has no description
dekker.one
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
36namespace Gecode { namespace Int { namespace Unary {
37
38 /*
39 * Omega tree
40 */
41
42 forceinline void
43 OmegaNode::init(const OmegaNode&, const OmegaNode&) {
44 p = 0; ect = -Limits::infinity;
45 }
46
47 forceinline void
48 OmegaNode::update(const OmegaNode& l, const OmegaNode& r) {
49 p = l.p + r.p;
50 ect = std::max(plus(l.ect,r.p), r.ect);
51 }
52
53 template<class TaskView>
54 forceinline
55 OmegaTree<TaskView>::OmegaTree(Region& r, const TaskViewArray<TaskView>& t)
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
65 OmegaTree<TaskView>::insert(int i) {
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
73 OmegaTree<TaskView>::remove(int i) {
74 leaf(i).p = 0; leaf(i).ect = -Limits::infinity;
75 update(i);
76 }
77
78 template<class TaskView>
79 forceinline int
80 OmegaTree<TaskView>::ect(void) const {
81 return root().ect;
82 }
83
84 template<class TaskView>
85 forceinline int
86 OmegaTree<TaskView>::ect(int i) const {
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
106 OmegaLambdaNode::init(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
107 OmegaNode::init(l,r);
108 lp = p; lect = ect; resEct = undef; resLp = undef;
109 }
110
111 forceinline void
112 OmegaLambdaNode::update(const OmegaLambdaNode& l, const OmegaLambdaNode& r) {
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>
135 forceinline
136 OmegaLambdaTree<TaskView>::OmegaLambdaTree(Region& r,
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
163 OmegaLambdaTree<TaskView>::shift(int i) {
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
175 OmegaLambdaTree<TaskView>::oinsert(int i) {
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
183 OmegaLambdaTree<TaskView>::linsert(int i) {
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
193 OmegaLambdaTree<TaskView>::lremove(int i) {
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
203 OmegaLambdaTree<TaskView>::lempty(void) const {
204 return root().resEct < 0;
205 }
206
207 template<class TaskView>
208 forceinline int
209 OmegaLambdaTree<TaskView>::responsible(void) const {
210 return root().resEct;
211 }
212
213 template<class TaskView>
214 forceinline int
215 OmegaLambdaTree<TaskView>::ect(void) const {
216 return root().ect;
217 }
218
219 template<class TaskView>
220 forceinline int
221 OmegaLambdaTree<TaskView>::lect(void) const {
222 return root().lect;
223 }
224
225}}}
226
227// STATISTICS: int-prop