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
28Constraint::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
40Constraint::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 */
63int32
64Constraint::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 */
81SummandList*
82Constraint::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 */
94bool
95Constraint::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
139bool
140Constraint::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
148bool
149Constraint::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
159bool
160Constraint::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
172bool
173Constraint::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 */
192OperatorType
193Constraint::Op()
194{
195	return fOp;
196}
197
198
199/**
200 * Sets the operator used for this constraint.
201 *
202 * @param value	operator
203 */
204void
205Constraint::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 */
218double
219Constraint::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 */
230void
231Constraint::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 */
248double
249Constraint::PenaltyNeg() const
250{
251	return fPenaltyNeg;
252}
253
254
255/**
256 * The penalty coefficient for negative deviations from the soft constraint's exact solution,&nbsp;
257 * i.e. if the left side is too large.
258 *
259 * @param value	coefficient of negative penalty <code>double</code>
260 */
261void
262Constraint::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 */
276double
277Constraint::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 */
288void
289Constraint::SetPenaltyPos(double value)
290{
291	fPenaltyPos = value;
292
293	if (fLS != NULL)
294		fLS->UpdatePenalties(this);
295}
296
297
298const char*
299Constraint::Label()
300{
301	return fLabel.String();
302}
303
304
305void
306Constraint::SetLabel(const char* label)
307{
308	fLabel = label;
309}
310
311
312bool
313Constraint::IsValid()
314{
315	return fLS != NULL;
316}
317
318
319void
320Constraint::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
332BString
333Constraint::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
361void
362Constraint::PrintToStream()
363{
364	BString string = ToString();
365	printf("%s\n", string.String());
366}
367
368
369/**
370 * Constructor.
371 */
372Constraint::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 */
390Constraint::~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