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

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

    00001 //==============================================================================
    00002 // Copyright (c) 2001           Model-based Embedded and Robotic Systems Group
    00003 // All Rights Reserved          Massachusetts Institute of Technology
    00004 //
    00005 // This software is provided as is. Model-based Embedded and Robotic Systems
    00006 // (MERS) group does not assume any responsibility.
    00007 //==============================================================================
    00008 //# CHECKED MJP 08-07-2002
    00009
    00010 #ifdef _MSC_VER
    00011 #pragma warning( disable : 4786 )
    00012 #endif
    00013
    00014 #include <cassert>
    00015 #include "BFIGAssignment.h"
    00016
    00017 // MSVC does not support template methods, but we can use a work-around.
    00018 #ifdef _MSC_VER
    00019 #include "ListManipulator.h"
    00020 using Mers::Generators::BFIG::ListManipulator;
    00021 template ListManipulator<BFIGAssignment const *>;
    00022 #else
    00023 typedef bool (*assignment_comp_func)(BFIGAssignment const *, BFIGAssignment const *);
    00024 #endif
    00025
    00026 #include "BFIGConflict.h"
    00027
    00028 using namespace std;
    00029
    00030 static bool
    00031 assignment_cost_less(BFIGAssignment const * a1, BFIGAssignment const * a2)
    00032 {
    00033         return ( a1->getCost() < a2->getCost() );
    00034 }
    00035
    00036 static bool
    00037 assignment_less(BFIGAssignment const * a1, BFIGAssignment const * a2)
    00038 {
    00039         return ( (*a1) < (*a2) );
    00040 }
    00041
    00042         //------------------------------------
    00043         //      CONSTRUCTOR
    00044         //------------------------------------
    00045 /*#
    00046 BFIGConflict::BFIGConflict(list<BFIGAssignment const *> inconsistentAssignments_pList,
    00047                    list<BFIGAssignment const *> primeImplicants_pList)
    00048 {
    00049         inconsistentAssignments = inconsistentAssignments_pList;
    00050         primeImplicants = primeImplicants_pList;
    00051 }
    00052 */
    00053
    00054 BFIGConflict::BFIGConflict(list<BFIGAssignment const *> inconsistentAssignments_pList)
    00055 : primeImplicants()
    00056 {
    00057         inconsistentAssignments = inconsistentAssignments_pList;
    00058         // sort the assignments for comparison
    00059         #ifdef _WIN32
    00060         #ifndef __CYGWIN__
    00061         {
    00062                 ListManipulator<BFIGAssignment const *> lm;
    00063                 lm.sort(inconsistentAssignments, assignment_less);
    00064         }
    00065         #else
    00066         inconsistentAssignments.sort<assignment_comp_func>(assignment_less);
    00067         #endif
    00068         #else
    00069         inconsistentAssignments.sort<assignment_comp_func>(assignment_less);
    00070         #endif
    00071
    00072         createPrimeImplicants();
    00073 }
    00074
    00075 /*#
    00076 BFIGConflict::BFIGConflict()
    00077 {
    00078         //cout << "warning: default Conflict constructor called." << endln;
    00079 }
    00080 */
    00081
    00082         //------------------------------------
    00083         //      PUBLIC FUNCTION METHODS
    00084         //------------------------------------
    00085
    00086 list<BFIGAssignment const *>
    00087 BFIGConflict::getInconsistentAssignments() const
    00088 {
    00089         return inconsistentAssignments;
    00090 }
    00091
    00092 list<BFIGAssignment const *>
    00093 BFIGConflict::getPrimeImplicants() const
    00094 {
    00095         return primeImplicants;
    00096 }
    00097
    00098
    00099 int
    00100 BFIGConflict::getLength() const
    00101 {
    00102         return inconsistentAssignments.size();
    00103 }
    00104
    00105 bool
    00106 BFIGConflict::isEmpty() const
    00107 {
    00108         return (getLength() == 0);
    00109 }
    00110
    00111
    00112 void
    00113 BFIGConflict::createPrimeImplicants()
    00114         //******************************
    00115         //      This function will take the list of inconsistentAssignments and create a list of
    00116         //      assignments that are not in this list.  This list represents the set of assignments
    00117         //      that will entail the conflict.  Choosing only one of these assignments will then resolve
    00118         //      the conflict.
    00119         //******************************
    00120 {
    00121         list<BFIGAssignment const *>::const_iterator inconsistentAssignmentsIter;
    00122         list<BFIGAssignment const *> tempAssignment_pList;
    00123         list<BFIGAssignment const *>::iterator tempAssignmentIter;
    00124
    00125         for (inconsistentAssignmentsIter = inconsistentAssignments.begin();
    00126              inconsistentAssignmentsIter != inconsistentAssignments.end();
    00127              inconsistentAssignmentsIter++)
    00128         {
    00129                 tempAssignment_pList = (*inconsistentAssignmentsIter)->alternateAssignments();
    00130
    00131                 for (tempAssignmentIter = tempAssignment_pList.begin();
    00132                      tempAssignmentIter != tempAssignment_pList.end();
    00133                      tempAssignmentIter++)
    00134                 {
    00135                         primeImplicants.push_back(*tempAssignmentIter);
    00136                 }
    00137         }
    00138
    00139 #ifdef _WIN32
    00140 #ifndef __CYGWIN__
    00141         ListManipulator<BFIGAssignment const *> lm;
    00142         lm.sort(primeImplicants, assignment_cost_less);
    00143 #else
    00144         primeImplicants.sort<assignment_comp_func>(assignment_cost_less);
    00145 #endif
    00146 #else
    00147         primeImplicants.sort<assignment_comp_func>(assignment_cost_less);
    00148 #endif
    00149 }
    00150
    00151
    00152 /*#
    00153 void
    00154 BFIGConflict::recordConflict()
    00155         // **************************
    00156         //      This function will take each assignment in the primeImplicants of a conflict
    00157         //      and set the field in its assignment to note that the assignment entails this
    00158         //      conflict.
    00159         // ***************************
    00160 {
    00161         list<BFIGAssignment const *>::const_iterator primeImplIter;
    00162
    00163         //      Iterate through the assignments in primeImplicants, and set their entailedConflicts
    00164         //      field to point to this conflict.
    00165         for (primeImplIter = primeImplicants.begin(); primeImplIter != primeImplicants.end();
    00166                  primeImplIter++)
    00167                  {
    00169                  }
    00170 }
    00171 */
    00172
    00173
    00174 /*#
    00175 void
    00176 BFIGConflict::trySupportingConflict(Implicant const * currentImplNode)
    00177         // **************************************
    00178         //      This function checks if the assignments in its primeImplicants list are in the
    00179         //      current Implicant of BFIG.  It does this by comparing the assignments in
    00180         //      the primeImplicants list to the ones in currentImplicant's assignments.
    00181         //      If they are equal, then it adds the assignment as a support for the conflict.
    00182         //
    00183         //      Question:  If a conflict can be supported by multiple assignments, this is not
    00184         //              considered.  This type of check would be expensive, which is why it may not
    00185         //              have been in the original Lisp implementation. ???
    00186 {
    00187         list<BFIGAssignment const *>::const_iterator
    00188                 primeImplIter = primeImplicants.begin();
    00189         list<BFIGAssignment const *>::const_iterator
    00190                 ImplNodeAssignmentIter = currentImplNode->getAssignments().begin();
    00191         bool isSupported = false;
    00192
    00193         while (primeImplIter != primeImplicants.end() && !isSupported)
    00194         {
    00195                 while (ImplNodeAssignmentIter != currentImplNode->getAssignments().end() &&
    00196                        !isSupported)
    00197                 {
    00198                         if ((*primeImplIter) == (*ImplNodeAssignmentIter))
    00199                         {
    00200                                 isSupported = true;
    00201                                 currentEntailedAssignment = (*primeImplIter);
    00202                         }
    00203                         else currentEntailedAssignment = NULL;
    00204                 }
    00205         }
    00206 }
    00207 */
    00208
    00209
    00210 bool
    00211 BFIGConflict::supportedBy(Implicant const * implicant) const
    00212 {
    00213         list<BFIGAssignment const *> assignments = implicant->getAssignments();
    00214         list<BFIGAssignment const *>::const_iterator assignmentsIter;
    00215         for (assignmentsIter = assignments.begin(); assignmentsIter != assignments.end();
    00216                  assignmentsIter++)
    00217         {
    00218                 list<BFIGAssignment const *>::const_iterator conflictAssignmentsIter;
    00219                 for (conflictAssignmentsIter = inconsistentAssignments.begin();
    00220                      conflictAssignmentsIter != inconsistentAssignments.end();
    00221                          conflictAssignmentsIter++)
    00222                 {
    00223                         if (! (*assignmentsIter)->compatible(*conflictAssignmentsIter) )
    00224                         {
    00225                                 return true;
    00226                         }
    00227                 }
    00228         }
    00229         return false;
    00230 }
    00231
    00232
    00233 bool
    00234 BFIGConflict::supportedBy(BFIGAssignment const * a) const
    00235 {
    00236         list<BFIGAssignment const *>::const_iterator conflictAssignmentsIter;
    00237         for (conflictAssignmentsIter = inconsistentAssignments.begin();
    00238              conflictAssignmentsIter != inconsistentAssignments.end();
    00239                  conflictAssignmentsIter++)
    00240         {
    00241                 if (! a->compatible(*conflictAssignmentsIter) )
    00242                 {
    00243                         return true;
    00244                 }
    00245         }
    00246         return false;
    00247 }
    00248
    00249
    00250 bool
    00251 BFIGConflict::operator==(BFIGConflict const & c)  const
    00252 {
    00253         // Assumes constraints are in minimal form:
    00254         if (getLength() != c.getLength())
    00255                 return false;
    00256
    00257         // Could also fail if they are not minimal:
    00258         list<BFIGAssignment const *>::const_iterator c1Iter;
    00259         list<BFIGAssignment const *>::const_iterator c2Iter;
    00260         for (c1Iter = inconsistentAssignments.begin(), c2Iter = c.inconsistentAssignments.begin();
    00261              c1Iter != inconsistentAssignments.end(); c1Iter++, c2Iter++)
    00262         {
    00263                 if (!( (*c1Iter) == (*c2Iter) ))
    00264                         return false;
    00265         }
    00266
    00267         return true;
    00268 }
    00269
    00270
    00271 bool
    00272 BFIGConflict::operator<(BFIGConflict const & c)  const
    00273 {
    00274         if (getLength() < c.getLength())
    00275                 return true;
    00276         if (getLength() > c.getLength())
    00277                 return false;
    00278
    00279         list<BFIGAssignment const *>::const_iterator c1Iter;
    00280         list<BFIGAssignment const *>::const_iterator c2Iter;
    00281         for (c1Iter = inconsistentAssignments.begin(), c2Iter = c.inconsistentAssignments.begin();
    00282              c1Iter != inconsistentAssignments.end(); c1Iter++, c2Iter++)
    00283         {
    00284                 if ((*c1Iter) == (*c2Iter))
    00285                         continue;
    00286                 if ((*(*c1Iter)) < (*(*c2Iter)))
    00287                         return true;
    00288                 return false;
    00289         }
    00290
    00291         return false;
    00292 }
    00293
    00294
    00295 String
    00296 BFIGConflict::toString() const
    00297 {
    00298         list<BFIGAssignment const *>::const_iterator conflictIter;
    00299         list<BFIGAssignment const *> conflictInconsistent = inconsistentAssignments;
    00300
    00301         String res = "";
    00302         res += " ( " ;
    00303         for (conflictIter = conflictInconsistent.begin();
    00304                  conflictIter != conflictInconsistent.end(); conflictIter++)
    00305         {
    00306                 res += (*conflictIter)->toString();
    00307         }
    00308         res += " )" ;
    00309         // res += "\n" ;
    00310         return res;
    00311 }
    00312
    00313 ostream&
    00314 operator<<(ostream& os, BFIGConflict const & c)
    00315 {
    00316         list<BFIGAssignment const *>::const_iterator conflictIter;
    00317         list<BFIGAssignment const *> conflictInconsistent = c.inconsistentAssignments;
    00318
    00319         os << "(" ;
    00320         for (conflictIter = conflictInconsistent.begin();
    00321                  conflictIter != conflictInconsistent.end(); conflictIter++)
    00322         {
    00323                 os << *(*conflictIter) << " ";
    00324         }
    00325         os << ")" ;
    00326         return os;
    00327 }
    00328
    00329         //------------------------------------
    00330         //      PRIVATE FUNCTION METHODS
    00331         //------------------------------------
    00332
    00333