- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Generators/BFIG/BFIGConstraint.cpp

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00009 // Organization:        Model-based Embedded and Robotic Systems Group
    00010 //                                      Massachusetts Institute of Technology
    00011 //
    00013 //# CHECKED MJP 08-07-2002
    00014
    00015 #include "BFIGConstraint.h"
    00016
    00017 #include <cassert>
    00018 #include <iostream>
    00019 #include <vector>
    00020
    00021 #include "BFIGAssignment.h"
    00022 #include "BFIGImplicant.h"
    00023 #include "BFIGConstraintUnit.h"
    00024
    00026
    00027 using namespace Mers::Generators::BFIG;
    00028 using std::list;
    00029 using std::vector;
    00030 using std::ostream;
    00031
    00033
    00034 #ifdef _MSC_VER
    00035 #include "ListManipulator.h"
    00036 using Mers::Generators::BFIG::ListManipulator;
    00037 template ListManipulator<BFIGAssignment const *>;
    00038 #else
    00039 typedef bool (*assignment_comp_func)(BFIGAssignment const *, BFIGAssignment const *);
    00040 #endif
    00041
    00043
    00044 static bool
    00045 assignment_cost_less(BFIGAssignment const * a1, BFIGAssignment const * a2)
    00046 {
    00047         return ( a1->getCost() < a2->getCost() );
    00048 }
    00049
    00051
    00052 bool BFIGConstraint::terse = false;
    00053
    00055
    00056 BFIGConstraint::BFIGConstraint(bool noEssentialConflict_)
    00057 : constraintUnits(), essentialConflict(!noEssentialConflict_),
    00058   primeImplicants(), primed(false)
    00059 {
    00060 }
    00061
    00062
    00063 BFIGConstraint::BFIGConstraint(BFIGAssignment const * a, bool positive)
    00064 : constraintUnits(), essentialConflict(false),
    00065   primeImplicants(), primed(false)
    00066 {
    00067         assert(a);
    00068         addUnit(a, positive);
    00069 }
    00070
    00071
    00072 BFIGConstraint::BFIGConstraint(BFIGConstraintUnit const & cu)
    00073 : constraintUnits(), essentialConflict(false),
    00074   primeImplicants(), primed(false)
    00075 {
    00076         addUnit(cu);
    00077 }
    00078
    00079
    00080 /*#
    00081 //BFIGConstraint::BFIGConstraint(BFIGConstraint const & c)
    00082 //: constraintUnits(c.constraintUnits), essentialConflict(c.essentialConflict),
    00083 //  primeImplicants(c.primeImplicants), primed(c.primed)
    00084 //{
    00085 //}
    00086 */
    00087
    00088
    00089 BFIGConstraint::BFIGConstraint(BFIGConstraint const & c)
    00090 : constraintUnits(), essentialConflict(c.essentialConflict),
    00091   primeImplicants(), primed(c.primed)
    00092 {
    00093         list<BFIGConstraintUnit>::const_iterator cIter;
    00094         for (cIter = c.constraintUnits.begin(); cIter != c.constraintUnits.end(); cIter++)
    00095         {
    00096                 constraintUnits.push_back(*cIter);
    00097         }
    00098         if (primed)
    00099         {
    00100                 list<BFIGAssignment const *>::const_iterator aIter;
    00101                 for (aIter = c.primeImplicants.begin(); aIter != c.primeImplicants.end(); aIter++)
    00102                 {
    00103                         primeImplicants.push_back((*aIter));
    00104                 }
    00105         }
    00106 }
    00107
    00108
    00109 // Conflict constructor
    00110 BFIGConstraint::BFIGConstraint(vector<BFIGAssignment const *> const & inconsistentAssignments)
    00111 : constraintUnits(), essentialConflict(false),
    00112   primeImplicants(), primed(false)
    00113 {
    00114         vector<BFIGAssignment const *>::const_iterator aIter;
    00115         for (aIter = inconsistentAssignments.begin();
    00116              aIter != inconsistentAssignments.end(); aIter++)
    00117         {
    00118                 assert((*aIter));
    00119                 addUnit((*aIter), false);
    00120         }
    00121 }
    00122
    00123
    00124
    00125
    00126 BFIGConstraint::~BFIGConstraint()
    00127 {
    00128 }
    00129
    00130
    00131 BFIGConstraint
    00132 BFIGConstraint::withoutEnd()  const
    00133 {
    00134         BFIGConstraint c(*this);
    00135         if (!c.empty())
    00136                 c.constraintUnits.pop_back();
    00137         c.primed = false;
    00138         return c;
    00139 }
    00140
    00141
    00142 void
    00143 BFIGConstraint::addUnit(BFIGConstraintUnit const & unit)
    00144 {
    00145         constraintUnits.push_back(unit);
    00146         if (primed)
    00147                 addPrimeImplicants(unit);
    00148 }
    00149
    00150
    00151 void
    00152 BFIGConstraint::addUnit(BFIGAssignment const * a, bool parity)
    00153 {
    00154         addUnit(BFIGConstraintUnit(a, parity));
    00155 }
    00156
    00157
    00158 bool
    00159 BFIGConstraint::isEmpty()  const
    00160 {
    00161         return empty();
    00162 }
    00163
    00164 bool
    00165 BFIGConstraint::empty()  const
    00166 {
    00167         return (!essentialConflict) && constraintUnits.empty();
    00168 }
    00169
    00170
    00171 unsigned int
    00172 BFIGConstraint::getSize()  const
    00173 {
    00174         return size();
    00175 }
    00176
    00177 unsigned int
    00178 BFIGConstraint::size()  const
    00179 {
    00180         return constraintUnits.size();
    00181 }
    00182
    00183
    00184 unsigned int
    00185 BFIGConstraint::primeImplicantSize()  const
    00186 {
    00187         if (!primed)
    00188                 ((BFIGConstraint *)this)->makePrimeImplicants();
    00189         return primeImplicants.size();
    00190 }
    00191
    00192
    00193 vector<BFIGAssignment const *>
    00194 BFIGConstraint::getAssignments()  const
    00195 {
    00196         vector<BFIGAssignment const *> res;
    00197         list<BFIGConstraintUnit>::const_iterator cIter;
    00198         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00199         {
    00200                 assert((*cIter).getAssignment());
    00201                 res.push_back((*cIter).getAssignment());
    00202         }
    00203         return res;
    00204 }
    00205
    00206
    00207 list<BFIGConstraintUnit>
    00208 BFIGConstraint::getConstraintUnits()  const
    00209 {
    00210         return constraintUnits;
    00211 }
    00212
    00213 /*
    00214 bool
    00215 BFIGConstraint::isSatisfiedCurrent(bool conjunctive)  const
    00216 {
    00217         if (essentialConflict)
    00218                 return false;
    00219         if (empty())
    00220                 return true;
    00221         list<BFIGConstraintUnit>::const_iterator cIter;
    00222         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00223         {
    00224                 if (!(*cIter).isSatisfiedCurrent())
    00225                 {
    00226                         if (conjunctive)
    00227                                 return false;
    00228                 } else
    00229                 {
    00230                         if (!conjunctive)
    00231                                 return true;
    00232                 }
    00233
    00234         }
    00235         if (conjunctive)
    00236                 return true;
    00237         else
    00238                 return false;
    00239 }
    00240
    00241
    00242 bool
    00243 BFIGConstraint::maybeSatisfiedCurrent(bool conjunctive)  const
    00244 {
    00245         if (essentialConflict)
    00246                 return false;
    00247         if (empty())
    00248                 return true;
    00249         list<BFIGConstraintUnit>::const_iterator cIter;
    00250         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00251         {
    00252                 if (!(*cIter).maybeSatisfiedCurrent())
    00253                 {
    00254                         if (conjunctive)
    00255                                 return false;
    00256                 } else
    00257                 {
    00258                         if (!conjunctive)
    00259                                 return true;
    00260                 }
    00261
    00262         }
    00263         if (conjunctive)
    00264                 return true;
    00265         else
    00266                 return false;
    00267 }
    00268 */
    00269
    00270 vector<BFIGConstraint>
    00271 BFIGConstraint::negated()  const
    00272 {
    00273         vector<BFIGConstraint> res;
    00274         if (essentialConflict)  // should be empty constraint, then...
    00275                 return res;
    00276         list<BFIGConstraintUnit>::const_iterator cIter;
    00277         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00278         {
    00279                 res.push_back(BFIGConstraint((*cIter).negated()));
    00280         }
    00281         return res;
    00282 }
    00283
    00284
    00285 bool
    00286 BFIGConstraint::contains(BFIGAssignment const * a)  const
    00287 {
    00288         list<BFIGConstraintUnit>::const_iterator cIter;
    00289         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00290         {
    00291                 if ((*cIter).getAssignment() == a)
    00292                         return true;
    00293         }
    00294         return false;
    00295 }
    00296
    00297
    00298 bool
    00299 BFIGConstraint::reduce(BFIGConstraintUnit const & cu)
    00300 {
    00301         bool reduced = false;
    00302         list<BFIGConstraintUnit>::iterator cIter;
    00303         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); )
    00304         {
    00305                 if ((*cIter).getAssignment() == cu.getAssignment())
    00306                 {
    00307                         if ((*cIter).getParity() == cu.getParity())  // satisfies it
    00308                         {
    00309                                 constraintUnits.clear();
    00310                                 primed = false;
    00311                                 return true;
    00312                         } else
    00313                         {
    00314                                 cIter = constraintUnits.erase(cIter);
    00315                                 reduced = true;
    00316                         }
    00317                 } else
    00318                 {
    00319                         cIter++;
    00320                 }
    00321         }
    00322         if (reduced)
    00323                 primed = false;
    00324         if (constraintUnits.empty())  // oops! violated...
    00325         {
    00326                 essentialConflict = true;
    00327         }
    00328         return reduced;
    00329 }
    00330
    00331 /*
    00332 void
    00333 BFIGConstraint::sort()
    00334 {
    00335         constraintUnits.sort();
    00336 }
    00337 */
    00338
    00339
    00340 void
    00341 BFIGConstraint::clear()
    00342 {
    00343         constraintUnits.clear();
    00344         primed = false;
    00345 }
    00346
    00347
    00348 bool
    00349 BFIGConstraint::isEssentialConflict()  const
    00350 {
    00351         return essentialConflict;
    00352 }
    00353
    00354
    00355 bool
    00356 BFIGConstraint::supportedBy(BFIGImplicant const * implicant) const
    00357 {
    00358         vector<BFIGAssignment const *> assigns = implicant->getAssignments();
    00359         vector<BFIGAssignment const *>::const_iterator aIter;
    00360         for (aIter = assigns.begin(); aIter != assigns.end(); aIter++)
    00361         {
    00362                 assert(*aIter);
    00363                 if (supportedBy((*aIter)))
    00364                 {
    00365                         return true;
    00366                 }
    00367         }
    00368         return false;
    00369 }
    00370
    00371
    00372 bool
    00373 BFIGConstraint::supportedBy(BFIGAssignment const * a) const
    00374 {
    00375         assert(a);
    00376         BFIGVariable const * v = a->getVariable();
    00377         list<BFIGConstraintUnit>::const_iterator cIter;
    00378         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00379         {
    00380                 assert((*cIter).getAssignment());
    00381                 if ((*cIter).getAssignment()->getVariable() == v)
    00382                 {
    00383                         if ((*cIter).getParity())
    00384                         {
    00385                                 if ((*cIter).getAssignment() == a)
    00386                                         return true;
    00387                         } else
    00388                         {
    00389                                 if ((*cIter).getAssignment() != a)
    00390                                         return true;
    00391                         }
    00392                 }
    00393         }
    00394         return false;
    00395 }
    00396
    00397
    00398 list<BFIGAssignment const *>
    00399 BFIGConstraint::getPrimeImplicants()  const
    00400 {
    00401         if (!primed)
    00402         {
    00403                 ((BFIGConstraint *)this)->makePrimeImplicants();
    00404         }
    00405         return primeImplicants;
    00406 }
    00407
    00408
    00409 void
    00410 BFIGConstraint::makePrimeImplicants()
    00411 {
    00412         primeImplicants.clear();
    00413         list<BFIGConstraintUnit>::const_iterator cIter;
    00414         for (cIter = constraintUnits.begin(); cIter != constraintUnits.end(); cIter++)
    00415         {
    00416                 if ((*cIter).getParity())
    00417                 {
    00418                         primeImplicants.push_back((*cIter).getAssignment());
    00419                 } else
    00420                 {
    00421                         list<BFIGAssignment const *> newAssigns =
    00422                                 (*cIter).getAssignment()->alternateAssignments();
    00423                         primeImplicants.merge(newAssigns);
    00424                 }
    00425         }
    00426         // remove duplicates...
    00427 #ifdef _MSC_VER
    00428         ListManipulator<BFIGAssignment const *> lm;
    00429         lm.sort(primeImplicants, assignment_cost_less);
    00430 #else
    00431         primeImplicants.sort<assignment_comp_func>(assignment_cost_less);
    00432 #endif
    00433         primeImplicants.unique();
    00434
    00435         primed = true;
    00436 }
    00437
    00438
    00439
    00440 void
    00441 BFIGConstraint::addPrimeImplicants(BFIGConstraintUnit const & cu)
    00442 {
    00443         if (cu.getParity())
    00444         {
    00445                 primeImplicants.push_back(cu.getAssignment());
    00446         } else
    00447         {
    00448                 list<BFIGAssignment const *> newAssigns =
    00449                         cu.getAssignment()->alternateAssignments();
    00450                 primeImplicants.merge(newAssigns);
    00451         }
    00452         // remove duplicates...
    00453 #ifdef _MSC_VER
    00454         ListManipulator<BFIGAssignment const *> lm;
    00455         lm.sort(primeImplicants, assignment_cost_less);
    00456 #else
    00457         primeImplicants.sort<assignment_comp_func>(assignment_cost_less);
    00458 #endif
    00459         primeImplicants.unique();
    00460 }
    00461
    00463
    00464 bool
    00465 BFIGConstraint::operator==(BFIGConstraint const & c)  const
    00466 {
    00467         // Assumes constraints are in minimal form:
    00468         if (constraintUnits.size() != c.constraintUnits.size())
    00469                 return false;
    00470
    00471         // Could also fail if they are not minimal:
    00472         list<BFIGConstraintUnit> c1 = c.constraintUnits;
    00473         c1.sort();
    00474         list<BFIGConstraintUnit> c2 = constraintUnits;
    00475         c2.sort();
    00476         list<BFIGConstraintUnit>::const_iterator cu1Iter;
    00477         list<BFIGConstraintUnit>::const_iterator cu2Iter;
    00478         for (cu1Iter = c1.begin(), cu2Iter = c2.begin();
    00479              cu1Iter != c1.end(); cu1Iter++, cu2Iter++)
    00480         {
    00481                 if (!( (*cu1Iter) == (*cu2Iter) ))
    00482                         return false;
    00483         }
    00484
    00485         return true;
    00486 }
    00487
    00488
    00489 bool
    00490 BFIGConstraint::operator<(BFIGConstraint const & c)  const
    00491 {
    00492         if (size() < c.size())
    00493                 return true;
    00494         if (size() > c.size())
    00495                 return false;
    00496
    00497         list<BFIGConstraintUnit> c1 = constraintUnits;
    00498         c1.sort();
    00499         list<BFIGConstraintUnit> c2 = c.constraintUnits;
    00500         c2.sort();
    00501         list<BFIGConstraintUnit>::const_iterator c1Iter;
    00502         list<BFIGConstraintUnit>::const_iterator c2Iter;
    00503         for (c1Iter = c1.begin(), c2Iter = c2.begin();
    00504              c1Iter != c1.end(); c1Iter++, c2Iter++)
    00505         {
    00506                 if ((*c1Iter) == (*c2Iter))
    00507                         continue;
    00508                 if ((*c1Iter) < (*c2Iter))
    00509                         return true;
    00510                 return false;
    00511         }
    00512
    00513         return false;
    00514 }
    00515
    00516 namespace Mers {
    00517         namespace Generators {
    00518                 namespace BFIG {
    00519
    00520                         ostream&
    00521                         operator<<(ostream& os, BFIGConstraint const & c)
    00522                         {
    00523                                 //if (!c.terse)
    00524                                 os << "(";
    00525                                 if (c.constraintUnits.size() != 0)
    00526                                 {
    00527                                         list<BFIGConstraintUnit>::const_iterator cIter;
    00528                                         cIter = c.constraintUnits.begin();
    00529                                         if (c.terse)
    00530                                                 os << (*cIter).getDescription();
    00531                                         else
    00532                                                 os << (*cIter);
    00533                                         for (cIter++; cIter != c.constraintUnits.end(); cIter++)
    00534                                         {
    00535                                                 if (c.terse)
    00536                                                         os << " ";
    00537                                                 else
    00538                                                         os << " OR ";
    00539                                                 if (c.terse)
    00540                                                         os << (*cIter).getDescription();
    00541                                                 else
    00542                                                         os << (*cIter);
    00543                                         }
    00544                                 }
    00545                                 if (c.isEssentialConflict())
    00546                                         os << "X";
    00547                                 //if (!c.terse)
    00548                                 os << ")";
    00549                                 return os;
    00550                         }
    00551                 }
    00552         }
    00553 }
    00554