1 /*
2 * Copyright 2007-2008, Christof Lutteroth, lutteroth@cs.auckland.ac.nz
3 * Copyright 2007-2008, James Kim, jkim202@ec.auckland.ac.nz
4 * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de>
5 * Distributed under the terms of the MIT License.
6 */
7
8
9 #include "Constraint.h"
10
11 #include <new>
12 #include <stdio.h>
13
14 #include "LinearSpec.h"
15 #include "Variable.h"
16
17
18 // Toggle debug output
19 //#define DEBUG_CONSTRAINT
20
21 #ifdef DEBUG_CONSTRAINT
22 # define STRACE(x) debug_printf x
23 #else
24 # define STRACE(x) ;
25 #endif
26
27
Constraint()28 Constraint::Constraint()
29 :
30 fLS(NULL),
31 fLeftSide(new SummandList),
32 fOp(kEQ),
33 fRightSide(0),
34 fPenaltyNeg(-1),
35 fPenaltyPos(-1)
36 {
37 }
38
39
Constraint(Constraint * constraint)40 Constraint::Constraint(Constraint* constraint)
41 :
42 fLS(NULL),
43 fLeftSide(new SummandList),
44 fOp(constraint->Op()),
45 fRightSide(constraint->RightSide()),
46 fPenaltyNeg(constraint->PenaltyNeg()),
47 fPenaltyPos(constraint->PenaltyPos()),
48 fLabel(constraint->Label())
49 {
50 SummandList* orgSummands = constraint->LeftSide();
51 for (int32 i = 0; i < orgSummands->CountItems(); i++) {
52 Summand* summand = orgSummands->ItemAt(i);
53 fLeftSide->AddItem(new Summand(summand));
54 }
55 }
56
57
58 /**
59 * Gets the index of the constraint.
60 *
61 * @return the index of the constraint
62 */
63 int32
Index() const64 Constraint::Index() const
65 {
66 if (fLS == NULL)
67 return -1;
68 int32 i = fLS->Constraints().IndexOf(this);
69 if (i == -1)
70 STRACE(("Constraint not part of fLS->Constraints()."));
71
72 return i;
73 }
74
75
76 /**
77 * Gets the left side of the constraint.
78 *
79 * @return pointer to a BList containing the summands on the left side of the constraint
80 */
81 SummandList*
LeftSide()82 Constraint::LeftSide()
83 {
84 return fLeftSide;
85 }
86
87
88 /**
89 * Sets the summands on the left side of the constraint.
90 * The old summands are NOT deleted.
91 *
92 * @param summands a BList containing the Summand objects that make up the new left side
93 */
94 bool
SetLeftSide(SummandList * summands,bool deleteOldSummands)95 Constraint::SetLeftSide(SummandList* summands, bool deleteOldSummands)
96 {
97 if (summands == NULL)
98 debugger("Invalid summands");
99
100 // check left side
101 for (int32 i = 0; i < summands->CountItems(); i++) {
102 Summand* summand = summands->ItemAt(i);
103 for (int32 a = i + 1; a < summands->CountItems(); a++) {
104 Summand* nextSummand = summands->ItemAt(a);
105 if (summand->Var() == nextSummand->Var()) {
106 summand->SetCoeff(summand->Coeff() + nextSummand->Coeff());
107 summands->RemoveItem(nextSummand);
108 delete nextSummand;
109 a--;
110 }
111 }
112 }
113
114 if (fLS == NULL) {
115 if (deleteOldSummands)
116 delete fLeftSide;
117 fLeftSide = summands;
118 return true;
119 }
120
121 // notify the solver
122 SummandList oldSummands;
123 if (fLeftSide != NULL)
124 oldSummands = *fLeftSide;
125 if (deleteOldSummands)
126 delete fLeftSide;
127 fLeftSide = summands;
128 if (fLS != NULL)
129 fLS->UpdateLeftSide(this, &oldSummands);
130
131 if (deleteOldSummands) {
132 for (int32 i = 0; i < oldSummands.CountItems(); i++)
133 delete oldSummands.ItemAt(i);
134 }
135 return true;
136 }
137
138
139 bool
SetLeftSide(double coeff1,Variable * var1)140 Constraint::SetLeftSide(double coeff1, Variable* var1)
141 {
142 SummandList* list = new SummandList;
143 list->AddItem(new(std::nothrow) Summand(coeff1, var1));
144 return SetLeftSide(list, true);
145 }
146
147
148 bool
SetLeftSide(double coeff1,Variable * var1,double coeff2,Variable * var2)149 Constraint::SetLeftSide(double coeff1, Variable* var1,
150 double coeff2, Variable* var2)
151 {
152 SummandList* list = new SummandList;
153 list->AddItem(new(std::nothrow) Summand(coeff1, var1));
154 list->AddItem(new(std::nothrow) Summand(coeff2, var2));
155 return SetLeftSide(list, true);
156 }
157
158
159 bool
SetLeftSide(double coeff1,Variable * var1,double coeff2,Variable * var2,double coeff3,Variable * var3)160 Constraint::SetLeftSide(double coeff1, Variable* var1,
161 double coeff2, Variable* var2,
162 double coeff3, Variable* var3)
163 {
164 SummandList* list = new SummandList;
165 list->AddItem(new(std::nothrow) Summand(coeff1, var1));
166 list->AddItem(new(std::nothrow) Summand(coeff2, var2));
167 list->AddItem(new(std::nothrow) Summand(coeff3, var3));
168 return SetLeftSide(list, true);
169 }
170
171
172 bool
SetLeftSide(double coeff1,Variable * var1,double coeff2,Variable * var2,double coeff3,Variable * var3,double coeff4,Variable * var4)173 Constraint::SetLeftSide(double coeff1, Variable* var1,
174 double coeff2, Variable* var2,
175 double coeff3, Variable* var3,
176 double coeff4, Variable* var4)
177 {
178 SummandList* list = new SummandList;
179 list->AddItem(new(std::nothrow) Summand(coeff1, var1));
180 list->AddItem(new(std::nothrow) Summand(coeff2, var2));
181 list->AddItem(new(std::nothrow) Summand(coeff3, var3));
182 list->AddItem(new(std::nothrow) Summand(coeff4, var4));
183 return SetLeftSide(list, true);
184 }
185
186
187 /**
188 * Gets the operator used for this constraint.
189 *
190 * @return the operator used for this constraint
191 */
192 OperatorType
Op()193 Constraint::Op()
194 {
195 return fOp;
196 }
197
198
199 /**
200 * Sets the operator used for this constraint.
201 *
202 * @param value operator
203 */
204 void
SetOp(OperatorType value)205 Constraint::SetOp(OperatorType value)
206 {
207 fOp = value;
208 if (fLS != NULL)
209 fLS->UpdateOperator(this);
210 }
211
212
213 /**
214 * Gets the constant value that is on the right side of the operator.
215 *
216 * @return the constant value that is on the right side of the operator
217 */
218 double
RightSide() const219 Constraint::RightSide() const
220 {
221 return fRightSide;
222 }
223
224
225 /**
226 * Sets the constant value that is on the right side of the operator.
227 *
228 * @param value constant value that is on the right side of the operator
229 */
230 void
SetRightSide(double value)231 Constraint::SetRightSide(double value)
232 {
233 if (fRightSide == value)
234 return;
235
236 fRightSide = value;
237
238 if (fLS != NULL)
239 fLS->UpdateRightSide(this);
240 }
241
242
243 /**
244 * Gets the penalty coefficient for negative deviations.
245 *
246 * @return the penalty coefficient
247 */
248 double
PenaltyNeg() const249 Constraint::PenaltyNeg() const
250 {
251 return fPenaltyNeg;
252 }
253
254
255 /**
256 * The penalty coefficient for negative deviations from the soft constraint's exact solution,
257 * i.e. if the left side is too large.
258 *
259 * @param value coefficient of negative penalty <code>double</code>
260 */
261 void
SetPenaltyNeg(double value)262 Constraint::SetPenaltyNeg(double value)
263 {
264 fPenaltyNeg = value;
265
266 if (fLS != NULL)
267 fLS->UpdatePenalties(this);
268 }
269
270
271 /**
272 * Gets the penalty coefficient for positive deviations.
273 *
274 * @return the penalty coefficient
275 */
276 double
PenaltyPos() const277 Constraint::PenaltyPos() const
278 {
279 return fPenaltyPos;
280 }
281
282
283 /**
284 * The penalty coefficient for negative deviations from the soft constraint's
285 * exact solution, i.e. if the left side is too small.
286 * @param value coefficient of positive penalty <code>double</code>
287 */
288 void
SetPenaltyPos(double value)289 Constraint::SetPenaltyPos(double value)
290 {
291 fPenaltyPos = value;
292
293 if (fLS != NULL)
294 fLS->UpdatePenalties(this);
295 }
296
297
298 const char*
Label()299 Constraint::Label()
300 {
301 return fLabel.String();
302 }
303
304
305 void
SetLabel(const char * label)306 Constraint::SetLabel(const char* label)
307 {
308 fLabel = label;
309 }
310
311
312 bool
IsValid()313 Constraint::IsValid()
314 {
315 return fLS != NULL;
316 }
317
318
319 void
Invalidate()320 Constraint::Invalidate()
321 {
322 STRACE(("Constraint::Invalidate() on %d\n", this));
323
324 if (fLS == NULL)
325 return;
326
327 fLS->RemoveConstraint(this, false);
328 fLS = NULL;
329 }
330
331
332 BString
ToString() const333 Constraint::ToString() const
334 {
335 BString string;
336 string << "Constraint ";
337 string << fLabel;
338 string << "(" << (addr_t)this << "): ";
339
340 for (int i = 0; i < fLeftSide->CountItems(); i++) {
341 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i));
342 if (i != 0 && s->Coeff() >= 0)
343 string << " + ";
344 string << (float)s->Coeff() << "*";
345 string << "x";
346 string << s->Var()->Index();
347 string << " ";
348 }
349 string << ((fOp == kEQ) ? "== "
350 : (fOp == kGE) ? ">= "
351 : (fOp == kLE) ? "<= "
352 : "?? ");
353 string << (float)fRightSide;
354 string << " PenaltyPos=" << (float)PenaltyPos();
355 string << " PenaltyNeg=" << (float)PenaltyNeg();
356
357 return string;
358 }
359
360
361 void
PrintToStream()362 Constraint::PrintToStream()
363 {
364 BString string = ToString();
365 printf("%s\n", string.String());
366 }
367
368
369 /**
370 * Constructor.
371 */
Constraint(LinearSpec * ls,SummandList * summands,OperatorType op,double rightSide,double penaltyNeg,double penaltyPos)372 Constraint::Constraint(LinearSpec* ls, SummandList* summands, OperatorType op,
373 double rightSide, double penaltyNeg, double penaltyPos)
374 :
375 fLS(ls),
376 fLeftSide(NULL),
377 fOp(op),
378 fRightSide(rightSide),
379 fPenaltyNeg(penaltyNeg),
380 fPenaltyPos(penaltyPos)
381 {
382 SetLeftSide(summands, false);
383 }
384
385
386 /**
387 * Destructor.
388 * Removes the constraint from its specification and deletes all the summands.
389 */
~Constraint()390 Constraint::~Constraint()
391 {
392 Invalidate();
393
394 for (int32 i = 0; i < fLeftSide->CountItems(); i++)
395 delete fLeftSide->ItemAt(i);
396 delete fLeftSide;
397 fLeftSide = NULL;
398 }
399
400