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 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 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 64 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* 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 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 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 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 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 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 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 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 219 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 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 249 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 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 277 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 289 Constraint::SetPenaltyPos(double value) 290 { 291 fPenaltyPos = value; 292 293 if (fLS != NULL) 294 fLS->UpdatePenalties(this); 295 } 296 297 298 const char* 299 Constraint::Label() 300 { 301 return fLabel.String(); 302 } 303 304 305 void 306 Constraint::SetLabel(const char* label) 307 { 308 fLabel = label; 309 } 310 311 312 bool 313 Constraint::IsValid() 314 { 315 return fLS != NULL; 316 } 317 318 319 void 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 333 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 362 Constraint::PrintToStream() 363 { 364 BString string = ToString(); 365 printf("%s\n", string.String()); 366 } 367 368 369 /** 370 * Constructor. 371 */ 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 */ 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