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, 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