- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

# /home/coin/SVN-release/Ipopt-3.2.1/Ipopt/src/Common/IpCachedResults.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2004, 2006 International Business Machines and others.
    00002 // All Rights Reserved.
    00003 // This code is published under the Common Public License.
    00004 //
    00005 // $Id: IpCachedResults.hpp 759 2006-07-07 03:07:08Z andreasw $
    00006 //
    00007 // Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
    00008
    00009 #ifndef __IPCACHEDRESULTS_HPP__
    00010 #define __IPCACHEDRESULTS_HPP__
    00011
    00012 #include "IpTaggedObject.hpp"
    00013 #include "IpObserver.hpp"
    00014 #include "IpDebug.hpp"
    00015 #include <algorithm>
    00016 #include <vector>
    00017 #include <list>
    00018
    00019 namespace Ipopt
    00020 {
    00021
    00022   // Forward Declarations
    00023
    00024   template <class T>
    00025   class DependentResult;
    00026
    00027   //  AW: I'm taking this out, since this is by far the most used
    00028   //  class.  We should keep it as simple as possible.
    00029   //   /** Cache Priority Enum */
    00030   //   enum CachePriority
    00031   //   {
    00032   //     CP_Lowest,
    00033   //     CP_Standard,
    00034   //     CP_Trial,
    00035   //     CP_Iterate
    00036   //   };
    00037
    00063   template <class T>
    00064   class CachedResults
    00065   {
    00066   public:
    00067 #ifdef IP_DEBUG_CACHE
    00068
    00069     static const Index dbg_verbosity;
    00070 #endif
    00071
    00078     CachedResults(Int max_cache_size);
    00079
    00081     virtual ~CachedResults();
    00083
    00089     void AddCachedResult(const T& result,
    00090                          const std::vector<const TaggedObject*>& dependents,
    00091                          const std::vector<Number>& scalar_dependents);
    00092
    00097     bool GetCachedResult(T& retResult,
    00098                          const std::vector<const TaggedObject*>& dependents,
    00099                          const std::vector<Number>& scalar_dependents) const;
    00100
    00104     void AddCachedResult(const T& result,
    00105                          const std::vector<const TaggedObject*>& dependents);
    00106
    00110     bool GetCachedResult(T& retResult,
    00111                          const std::vector<const TaggedObject*>& dependents) const;
    00113
    00121     void AddCachedResult1Dep(const T& result,
    00122                              const TaggedObject* dependent1);
    00123
    00127     bool GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1);
    00128
    00132     void AddCachedResult2Dep(const T& result,
    00133                              const TaggedObject* dependent1,
    00134                              const TaggedObject* dependent2);
    00135
    00139     bool GetCachedResult2Dep(T& retResult,
    00140                              const TaggedObject* dependent1,
    00141                              const TaggedObject* dependent2);
    00142
    00146     void AddCachedResult3Dep(const T& result,
    00147                              const TaggedObject* dependent1,
    00148                              const TaggedObject* dependent2,
    00149                              const TaggedObject* dependent3);
    00150
    00154     bool GetCachedResult3Dep(T& retResult,
    00155                              const TaggedObject* dependent1,
    00156                              const TaggedObject* dependent2,
    00157                              const TaggedObject* dependent3);
    00158
    00161     bool GetCachedResult1Dep(T& retResult, const TaggedObject& dependent1)
    00162     {
    00163       return GetCachedResult1Dep(retResult, &dependent1);
    00164     }
    00165     bool GetCachedResult2Dep(T& retResult,
    00166                              const TaggedObject& dependent1,
    00167                              const TaggedObject& dependent2)
    00168     {
    00169       return GetCachedResult2Dep(retResult, &dependent1, &dependent2);
    00170     }
    00171     bool GetCachedResult3Dep(T& retResult,
    00172                              const TaggedObject& dependent1,
    00173                              const TaggedObject& dependent2,
    00174                              const TaggedObject& dependent3)
    00175     {
    00176       return GetCachedResult3Dep(retResult, &dependent1, &dependent2, &dependent3);
    00177     }
    00178     void AddCachedResult1Dep(const T& result,
    00179                              const TaggedObject& dependent1)
    00180     {
    00181       AddCachedResult1Dep(result, &dependent1);
    00182     }
    00183     void AddCachedResult2Dep(const T& result,
    00184                              const TaggedObject& dependent1,
    00185                              const TaggedObject& dependent2)
    00186     {
    00187       AddCachedResult2Dep(result, &dependent1, &dependent2);
    00188     }
    00189     void AddCachedResult3Dep(const T& result,
    00190                              const TaggedObject& dependent1,
    00191                              const TaggedObject& dependent2,
    00192                              const TaggedObject& dependent3)
    00193     {
    00194       AddCachedResult3Dep(result, &dependent1, &dependent2, &dependent3);
    00195     }
    00197
    00201     bool InvalidateResult(const std::vector<const TaggedObject*>& dependents,
    00202                           const std::vector<Number>& scalar_dependents);
    00203
    00204   private:
    00214     CachedResults();
    00215
    00217     CachedResults(const CachedResults&);
    00218
    00220     void operator=(const CachedResults&);
    00222
    00224     Int max_cache_size_;
    00225
    00227     mutable std::list<DependentResult<T>*>* cached_results_;
    00228
    00233     void CleanupInvalidatedResults() const;
    00234
    00236     void DebugPrintCachedResults() const;
    00237   };
    00238
    00244   template <class T>
    00245   class DependentResult : public Observer
    00246   {
    00247   public:
    00248
    00249 #ifdef IP_DEBUG_CACHE
    00250
    00251     static const Index dbg_verbosity;
    00252 #endif
    00253
    00257     DependentResult(const T& result, const std::vector<const TaggedObject*>& dependents,
    00258                     const std::vector<Number>& scalar_dependents);
    00259
    00261     ~DependentResult();
    00263
    00267     bool IsStale() const;
    00268
    00270     void Invalidate();
    00271
    00273     const T& GetResult() const;
    00275
    00280     bool DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00281                              const std::vector<Number>& scalar_dependents) const;
    00282
    00284     void DebugPrint() const;
    00285
    00286   protected:
    00294     virtual void RecieveNotification(NotifyType notify_type, const Subject* subject);
    00295
    00296   private:
    00297
    00307     DependentResult();
    00308
    00310     DependentResult(const DependentResult&);
    00311
    00313     void operator=(const DependentResult&);
    00315
    00319     bool stale_;
    00321     const T result_;
    00323     std::vector<TaggedObject::Tag> dependent_tags_;
    00325     std::vector<Number> scalar_dependents_;
    00326   };
    00327
    00328 #ifdef IP_DEBUG_CACHE
    00329
    00330   template <class T>
    00331   const Index CachedResults<T>::dbg_verbosity = 0;
    00332
    00333   template <class T>
    00334   const Index DependentResult<T>::dbg_verbosity = 0;
    00335 #endif
    00336
    00337   template <class T>
    00338   DependentResult<T>::DependentResult(
    00339     const T& result,
    00340     const std::vector<const TaggedObject*>& dependents,
    00341     const std::vector<Number>& scalar_dependents)
    00342       :
    00343       stale_(false),
    00344       result_(result),
    00345       dependent_tags_(dependents.size()),
    00346       scalar_dependents_(scalar_dependents)
    00347   {
    00348 #ifdef IP_DEBUG_CACHE
    00349     DBG_START_METH("DependentResult<T>::DependentResult()", dbg_verbosity);
    00350 #endif
    00351
    00352     for (Index i=0; i<(Index)dependents.size(); i++) {
    00353       if (dependents[i]) {
    00354         // Call the RequestAttach method of the Observer base class.
    00355         // This will add this dependent result in the Observer list
    00356         // for the Subject dependents[i].  As a consequence, the
    00357         // RecieveNotification method of this DependentResult will be
    00358         // called with notify_type=NT_Changed, whenever the
    00359         // TaggedResult dependents[i] is changed (i.e. its HasChanged
    00360         // method is called).
    00361         RequestAttach(NT_Changed, dependents[i]);
    00362         dependent_tags_[i] = dependents[i]->GetTag();
    00363       }
    00364       else {
    00365         dependent_tags_[i] = 0;
    00366       }
    00367     }
    00368   }
    00369
    00370   template <class T>
    00371   DependentResult<T>::~DependentResult()
    00372   {
    00373 #ifdef IP_DEBUG_CACHE
    00374     DBG_START_METH("DependentResult<T>::~DependentResult()", dbg_verbosity);
    00375 #endif
    00376     //DBG_ASSERT(stale_ == true);
    00377     // Nothing to be done here, destructor
    00378     // of T should sufficiently remove
    00379     // any memory, etc.
    00380   }
    00381
    00382   template <class T>
    00383   bool DependentResult<T>::IsStale() const
    00384   {
    00385     return stale_;
    00386   }
    00387
    00388   template <class T>
    00389   void DependentResult<T>::Invalidate()
    00390   {
    00391     stale_ = true;
    00392   }
    00393
    00394   template <class T>
    00395   void DependentResult<T>::RecieveNotification(NotifyType notify_type, const Subject* subject)
    00396   {
    00397 #ifdef IP_DEBUG_CACHE
    00398     DBG_START_METH("DependentResult<T>::RecieveNotification", dbg_verbosity);
    00399 #endif
    00400
    00401     if (notify_type == NT_Changed || notify_type==NT_BeingDestroyed) {
    00402       stale_ = true;
    00403       // technically, I could unregister the notifications here, but they
    00404       // aren't really hurting anything
    00405     }
    00406   }
    00407
    00408   template <class T>
    00409   bool DependentResult<T>::DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00410       const std::vector<Number>& scalar_dependents) const
    00411   {
    00412 #ifdef IP_DEBUG_CACHE
    00413     DBG_START_METH("DependentResult<T>::DependentsIdentical", dbg_verbosity);
    00414 #endif
    00415
    00416     DBG_ASSERT(stale_ == false);
    00417     DBG_ASSERT(dependents.size() == dependent_tags_.size());
    00418
    00419     bool retVal = true;
    00420
    00421     if (dependents.size() != dependent_tags_.size()
    00422         || scalar_dependents.size() != scalar_dependents_.size()) {
    00423       retVal = false;
    00424     }
    00425     else {
    00426       for (Index i=0; i<(Index)dependents.size(); i++) {
    00427         if ( (dependents[i] && dependents[i]->GetTag() != dependent_tags_[i])
    00428              || (!dependents[i] && dependent_tags_[i] != 0) ) {
    00429           retVal = false;
    00430           break;
    00431         }
    00432       }
    00433       if (retVal) {
    00434         for (Index i=0; i<(Index)scalar_dependents.size(); i++) {
    00435           if (scalar_dependents[i] != scalar_dependents_[i]) {
    00436             retVal = false;
    00437             break;
    00438           }
    00439         }
    00440       }
    00441     }
    00442
    00443     return retVal;
    00444   }
    00445
    00446   template <class T>
    00447   const T& DependentResult<T>::GetResult() const
    00448   {
    00449 #ifdef IP_DEBUG_CACHE
    00450     DBG_START_METH("DependentResult<T>::GetResult()", dbg_verbosity);
    00451 #endif
    00452
    00453     DBG_ASSERT(stale_ == false);
    00454     return result_;
    00455   }
    00456
    00457   template <class T>
    00458   void DependentResult<T>::DebugPrint() const
    00459   {
    00460 #ifdef IP_DEBUG_CACHE
    00461     DBG_START_METH("DependentResult<T>::DebugPrint", dbg_verbosity);
    00462 #endif
    00463
    00464   }
    00465
    00466   template <class T>
    00467   CachedResults<T>::CachedResults(Int max_cache_size)
    00468       :
    00469       max_cache_size_(max_cache_size),
    00470       cached_results_(NULL)
    00471   {
    00472 #ifdef IP_DEBUG_CACHE
    00473     DBG_START_METH("CachedResults<T>::CachedResults", dbg_verbosity);
    00474 #endif
    00475
    00476   }
    00477
    00478   template <class T>
    00479   CachedResults<T>::~CachedResults()
    00480   {
    00481 #ifdef IP_DEBUG_CACHE
    00482     DBG_START_METH("CachedResults<T>::!CachedResults()", dbg_verbosity);
    00483 #endif
    00484
    00485     if (cached_results_) {
    00486       for (typename std::list< DependentResult<T>* >::iterator iter = cached_results_->
    00487            begin();
    00488            iter != cached_results_->end();
    00489            iter++) {
    00490         delete *iter;
    00491       }
    00492       delete cached_results_;
    00493     }
    00494     /*
    00495     while (!cached_results_.empty()) {
    00496       DependentResult<T>* result = cached_results_.back();
    00497       cached_results_.pop_back();
    00498       delete result;
    00499     }
    00500     */
    00501   }
    00502
    00503   template <class T>
    00504   void CachedResults<T>::AddCachedResult(const T& result,
    00505                                          const std::vector<const TaggedObject*>& dependents,
    00506                                          const std::vector<Number>& scalar_dependents)
    00507   {
    00508 #ifdef IP_DEBUG_CACHE
    00509     DBG_START_METH("CachedResults<T>::AddCachedResult", dbg_verbosity);
    00510 #endif
    00511
    00512     CleanupInvalidatedResults();
    00513
    00514     // insert the new one here
    00515     DependentResult<T>* newResult = new DependentResult<T>(result, dependents, scalar_dependents);
    00516     if (!cached_results_) {
    00517       cached_results_ = new std::list<DependentResult<T>*>;
    00518     }
    00519     cached_results_->push_front(newResult);
    00520
    00521     // keep the list small enough
    00522     if (max_cache_size_ >= 0) { // if negative, allow infinite cache
    00523       // non-negative - limit size of list to max_cache_size
    00524       DBG_ASSERT((Int)cached_results_->size()<=max_cache_size_+1);
    00525       if ((Int)cached_results_->size() > max_cache_size_) {
    00526         delete cached_results_->back();
    00527         cached_results_->pop_back();
    00528       }
    00529     }
    00530
    00531 #ifdef IP_DEBUG_CACHE
    00532     DBG_EXEC(2, DebugPrintCachedResults());
    00533 #endif
    00534
    00535   }
    00536
    00537   template <class T>
    00538   void CachedResults<T>::AddCachedResult(const T& result,
    00539                                          const std::vector<const TaggedObject*>& dependents)
    00540   {
    00541     std::vector<Number> scalar_dependents;
    00542     AddCachedResult(result, dependents, scalar_dependents);
    00543   }
    00544
    00545   template <class T>
    00546   bool CachedResults<T>::GetCachedResult(T& retResult, const std::vector<const TaggedObject*>& dependents,
    00547                                          const std::vector<Number>& scalar_dependents) const
    00548   {
    00549 #ifdef IP_DEBUG_CACHE
    00550     DBG_START_METH("CachedResults<T>::GetCachedResult", dbg_verbosity);
    00551 #endif
    00552
    00553     if (!cached_results_)
    00554       return false;
    00555
    00556     CleanupInvalidatedResults();
    00557
    00558     bool retValue = false;
    00559     typename std::list< DependentResult<T>* >::const_iterator iter;
    00560     for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00561       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00562         retResult = (*iter)->GetResult();
    00563         retValue = true;
    00564         break;
    00565       }
    00566     }
    00567
    00568 #ifdef IP_DEBUG_CACHE
    00569     DBG_EXEC(2, DebugPrintCachedResults());
    00570 #endif
    00571
    00572     return retValue;
    00573   }
    00574
    00575   template <class T>
    00576   bool CachedResults<T>::GetCachedResult(
    00577     T& retResult, const std::vector<const TaggedObject*>& dependents) const
    00578   {
    00579     std::vector<Number> scalar_dependents;
    00580     return GetCachedResult(retResult, dependents, scalar_dependents);
    00581   }
    00582
    00583   template <class T>
    00584   void CachedResults<T>::AddCachedResult1Dep(const T& result,
    00585       const TaggedObject* dependent1)
    00586   {
    00587 #ifdef IP_DEBUG_CACHE
    00588     DBG_START_METH("CachedResults<T>::AddCachedResult1Dep", dbg_verbosity);
    00589 #endif
    00590
    00591     std::vector<const TaggedObject*> dependents(1);
    00592     dependents[0] = dependent1;
    00593
    00594     AddCachedResult(result, dependents);
    00595   }
    00596
    00597   template <class T>
    00598   bool CachedResults<T>::GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1)
    00599   {
    00600 #ifdef IP_DEBUG_CACHE
    00601     DBG_START_METH("CachedResults<T>::GetCachedResult1Dep", dbg_verbosity);
    00602 #endif
    00603
    00604     std::vector<const TaggedObject*> dependents(1);
    00605     dependents[0] = dependent1;
    00606
    00607     return GetCachedResult(retResult, dependents);
    00608   }
    00609
    00610   template <class T>
    00611   void CachedResults<T>::AddCachedResult2Dep(const T& result, const TaggedObject* dependent1,
    00612       const TaggedObject* dependent2)
    00613
    00614   {
    00615 #ifdef IP_DEBUG_CACHE
    00616     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00617 #endif
    00618
    00619     std::vector<const TaggedObject*> dependents(2);
    00620     dependents[0] = dependent1;
    00621     dependents[1] = dependent2;
    00622
    00623     AddCachedResult(result, dependents);
    00624   }
    00625
    00626   template <class T>
    00627   bool CachedResults<T>::GetCachedResult2Dep(T& retResult, const TaggedObject* dependent1, const TaggedObject* dependent2)
    00628   {
    00629 #ifdef IP_DEBUG_CACHE
    00630     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00631 #endif
    00632
    00633     std::vector<const TaggedObject*> dependents(2);
    00634     dependents[0] = dependent1;
    00635     dependents[1] = dependent2;
    00636
    00637     return GetCachedResult(retResult, dependents);
    00638   }
    00639
    00640   template <class T>
    00641   void CachedResults<T>::AddCachedResult3Dep(const T& result, const TaggedObject* dependent1,
    00642       const TaggedObject* dependent2,
    00643       const TaggedObject* dependent3)
    00644
    00645   {
    00646 #ifdef IP_DEBUG_CACHE
    00647     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00648 #endif
    00649
    00650     std::vector<const TaggedObject*> dependents(3);
    00651     dependents[0] = dependent1;
    00652     dependents[1] = dependent2;
    00653     dependents[2] = dependent3;
    00654
    00655     AddCachedResult(result, dependents);
    00656   }
    00657
    00658   template <class T>
    00659   bool CachedResults<T>::GetCachedResult3Dep(T& retResult, const TaggedObject* dependent1,
    00660       const TaggedObject* dependent2,
    00661       const TaggedObject* dependent3)
    00662   {
    00663 #ifdef IP_DEBUG_CACHE
    00664     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00665 #endif
    00666
    00667     std::vector<const TaggedObject*> dependents(3);
    00668     dependents[0] = dependent1;
    00669     dependents[1] = dependent2;
    00670     dependents[2] = dependent3;
    00671
    00672     return GetCachedResult(retResult, dependents);
    00673   }
    00674
    00675   template <class T>
    00676   bool CachedResults<T>::InvalidateResult(const std::vector<const TaggedObject*>& dependents,
    00677                                           const std::vector<Number>& scalar_dependents)
    00678   {
    00679     if (!cached_results_)
    00680       return false;
    00681
    00682     CleanupInvalidatedResults();
    00683
    00684     bool retValue = false;
    00685     typename std::list< DependentResult<T>* >::const_iterator iter;
    00686     for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00687       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00688         (*iter)->Invalidate();
    00689         retValue = true;
    00690         break;
    00691       }
    00692     }
    00693
    00694     return retValue;
    00695   }
    00696
    00697   template <class T>
    00698   void CachedResults<T>::CleanupInvalidatedResults() const
    00699   {
    00700 #ifdef IP_DEBUG_CACHE
    00701     DBG_START_METH("CachedResults<T>::CleanupInvalidatedResults", dbg_verbosity);
    00702 #endif
    00703
    00704     if (!cached_results_)
    00705       return;
    00706
    00707     typename std::list< DependentResult<T>* >::iterator iter;
    00708     iter = cached_results_->begin();
    00709     while (iter != cached_results_->end()) {
    00710       if ((*iter)->IsStale()) {
    00711         typename std::list< DependentResult<T>* >::iterator
    00712         iter_to_remove = iter;
    00713         iter++;
    00714         DependentResult<T>* result_to_delete = (*iter_to_remove);
    00715         cached_results_->erase(iter_to_remove);
    00716         delete result_to_delete;
    00717       }
    00718       else {
    00719         iter++;
    00720       }
    00721     }
    00722   }
    00723
    00724   template <class T>
    00725   void CachedResults<T>::DebugPrintCachedResults() const
    00726   {
    00727 #ifdef IP_DEBUG_CACHE
    00728     DBG_START_METH("CachedResults<T>::DebugPrintCachedResults", dbg_verbosity);
    00729     if (DBG_VERBOSITY()>=2 ) {
    00730       if (!chached_results_) {
    00731         DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
    00732       }
    00733       else {
    00734         typename std::list< DependentResult<T>* >::const_iterator iter;
    00735         DBG_PRINT((2,"Current set of cached results:\n"));
    00736         for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00737           DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
    00738         }
    00739       }
    00740     }
    00741 #endif
    00742
    00743   }
    00744
    00745 } // namespace Ipopt
    00746
    00747 #endif