- Main Page
- Classes
- Files

- File List
- File Members

# src/Common/IpCachedResults.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2004, 2011 International Business Machines and others.
    00002 // All Rights Reserved.
    00003 // This code is published under the Eclipse Public License.
    00004 //
    00005 // $Id: IpCachedResults.hpp 2476 2014-04-08 09:41:07Z stefan $
    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 <algorithm>
    00015 #include <vector>
    00016 #include <list>
    00017
    00018 namespace Ipopt
    00019 {
    00020
    00021 #if COIN_IPOPT_CHECKLEVEL > 2
    00022 # define IP_DEBUG_CACHE
    00023 #endif
    00024 #ifdef IP_DEBUG_CACHE
    00025 # include "IpDebug.hpp"
    00026 #endif
    00027
    00028   // Forward Declarations
    00029
    00030   template <class T>
    00031   class DependentResult;
    00032
    00033   //  AW: I'm taking this out, since this is by far the most used
    00034   //  class.  We should keep it as simple as possible.
    00035   //   /** Cache Priority Enum */
    00036   //   enum CachePriority
    00037   //   {
    00038   //     CP_Lowest,
    00039   //     CP_Standard,
    00040   //     CP_Trial,
    00041   //     CP_Iterate
    00042   //   };
    00043
    00069   template <class T>
    00070   class CachedResults
    00071   {
    00072   public:
    00073 #ifdef IP_DEBUG_CACHE
    00074
    00075     static const Index dbg_verbosity;
    00076 #endif
    00077
    00084     CachedResults(Int max_cache_size);
    00085
    00087     virtual ~CachedResults();
    00089
    00095     void AddCachedResult(const T& result,
    00096                          const std::vector<const TaggedObject*>& dependents,
    00097                          const std::vector<Number>& scalar_dependents);
    00098
    00103     bool GetCachedResult(T& retResult,
    00104                          const std::vector<const TaggedObject*>& dependents,
    00105                          const std::vector<Number>& scalar_dependents) const;
    00106
    00110     void AddCachedResult(const T& result,
    00111                          const std::vector<const TaggedObject*>& dependents);
    00112
    00116     bool GetCachedResult(T& retResult,
    00117                          const std::vector<const TaggedObject*>& dependents) const;
    00119
    00127     void AddCachedResult1Dep(const T& result,
    00128                              const TaggedObject* dependent1);
    00129
    00133     bool GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1);
    00134
    00138     void AddCachedResult2Dep(const T& result,
    00139                              const TaggedObject* dependent1,
    00140                              const TaggedObject* dependent2);
    00141
    00145     bool GetCachedResult2Dep(T& retResult,
    00146                              const TaggedObject* dependent1,
    00147                              const TaggedObject* dependent2);
    00148
    00152     void AddCachedResult3Dep(const T& result,
    00153                              const TaggedObject* dependent1,
    00154                              const TaggedObject* dependent2,
    00155                              const TaggedObject* dependent3);
    00156
    00160     bool GetCachedResult3Dep(T& retResult,
    00161                              const TaggedObject* dependent1,
    00162                              const TaggedObject* dependent2,
    00163                              const TaggedObject* dependent3);
    00164
    00167     bool GetCachedResult1Dep(T& retResult, const TaggedObject& dependent1)
    00168     {
    00169       return GetCachedResult1Dep(retResult, &dependent1);
    00170     }
    00171     bool GetCachedResult2Dep(T& retResult,
    00172                              const TaggedObject& dependent1,
    00173                              const TaggedObject& dependent2)
    00174     {
    00175       return GetCachedResult2Dep(retResult, &dependent1, &dependent2);
    00176     }
    00177     bool GetCachedResult3Dep(T& retResult,
    00178                              const TaggedObject& dependent1,
    00179                              const TaggedObject& dependent2,
    00180                              const TaggedObject& dependent3)
    00181     {
    00182       return GetCachedResult3Dep(retResult, &dependent1, &dependent2, &dependent3);
    00183     }
    00184     void AddCachedResult1Dep(const T& result,
    00185                              const TaggedObject& dependent1)
    00186     {
    00187       AddCachedResult1Dep(result, &dependent1);
    00188     }
    00189     void AddCachedResult2Dep(const T& result,
    00190                              const TaggedObject& dependent1,
    00191                              const TaggedObject& dependent2)
    00192     {
    00193       AddCachedResult2Dep(result, &dependent1, &dependent2);
    00194     }
    00195     void AddCachedResult3Dep(const T& result,
    00196                              const TaggedObject& dependent1,
    00197                              const TaggedObject& dependent2,
    00198                              const TaggedObject& dependent3)
    00199     {
    00200       AddCachedResult3Dep(result, &dependent1, &dependent2, &dependent3);
    00201     }
    00203
    00207     bool InvalidateResult(const std::vector<const TaggedObject*>& dependents,
    00208                           const std::vector<Number>& scalar_dependents);
    00209
    00211     void Clear();
    00212
    00214     void Clear(Int max_cache_size);
    00215
    00216   private:
    00226     CachedResults();
    00227
    00229     CachedResults(const CachedResults&);
    00230
    00232     void operator=(const CachedResults&);
    00234
    00236     Int max_cache_size_;
    00237
    00239     mutable std::list<DependentResult<T>*>* cached_results_;
    00240
    00245     void CleanupInvalidatedResults() const;
    00246
    00248     void DebugPrintCachedResults() const;
    00249   };
    00250
    00256   template <class T>
    00257   class DependentResult : public Observer
    00258   {
    00259   public:
    00260
    00261 #ifdef IP_DEBUG_CACHE
    00262     static const Index dbg_verbosity;
    00263 #endif
    00264
    00268     DependentResult(const T& result, const std::vector<const TaggedObject*>& dependents,
    00269                     const std::vector<Number>& scalar_dependents);
    00270
    00272     ~DependentResult();
    00274
    00278     bool IsStale() const;
    00279
    00281     void Invalidate();
    00282
    00284     const T& GetResult() const;
    00286
    00291     bool DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00292                              const std::vector<Number>& scalar_dependents) const;
    00293
    00295     void DebugPrint() const;
    00296
    00297   protected:
    00305     virtual void RecieveNotification(NotifyType notify_type, const Subject* subject);
    00306
    00307   private:
    00308
    00318     DependentResult();
    00319
    00321     DependentResult(const DependentResult&);
    00322
    00324     void operator=(const DependentResult&);
    00326
    00330     bool stale_;
    00332     const T result_;
    00334     std::vector<TaggedObject::Tag> dependent_tags_;
    00336     std::vector<Number> scalar_dependents_;
    00337   };
    00338
    00339 #ifdef IP_DEBUG_CACHE
    00340   template <class T>
    00341   const Index CachedResults<T>::dbg_verbosity = 0;
    00342
    00343   template <class T>
    00344   const Index DependentResult<T>::dbg_verbosity = 0;
    00345 #endif
    00346
    00347   template <class T>
    00348   DependentResult<T>::DependentResult(
    00349     const T& result,
    00350     const std::vector<const TaggedObject*>& dependents,
    00351     const std::vector<Number>& scalar_dependents)
    00352       :
    00353       stale_(false),
    00354       result_(result),
    00355       dependent_tags_(dependents.size()),
    00356       scalar_dependents_(scalar_dependents)
    00357   {
    00358 #ifdef IP_DEBUG_CACHE
    00359     DBG_START_METH("DependentResult<T>::DependentResult()", dbg_verbosity);
    00360 #endif
    00361
    00362     for (Index i=0; i<(Index)dependents.size(); i++) {
    00363       if (dependents[i]) {
    00364         // Call the RequestAttach method of the Observer base class.
    00365         // This will add this dependent result in the Observer list
    00366         // for the Subject dependents[i].  As a consequence, the
    00367         // RecieveNotification method of this DependentResult will be
    00368         // called with notify_type=NT_Changed, whenever the
    00369         // TaggedResult dependents[i] is changed (i.e. its HasChanged
    00370         // method is called).
    00371         RequestAttach(NT_Changed, dependents[i]);
    00372         dependent_tags_[i] = dependents[i]->GetTag();
    00373       }
    00374       else {
    00375         dependent_tags_[i] = 0;
    00376       }
    00377     }
    00378   }
    00379
    00380   template <class T>
    00381   DependentResult<T>::~DependentResult()
    00382   {
    00383 #ifdef IP_DEBUG_CACHE
    00384     DBG_START_METH("DependentResult<T>::~DependentResult()", dbg_verbosity);
    00385     //DBG_ASSERT(stale_ == true);
    00386 #endif
    00387     // Nothing to be done here, destructor
    00388     // of T should sufficiently remove
    00389     // any memory, etc.
    00390   }
    00391
    00392   template <class T>
    00393   bool DependentResult<T>::IsStale() const
    00394   {
    00395     return stale_;
    00396   }
    00397
    00398   template <class T>
    00399   void DependentResult<T>::Invalidate()
    00400   {
    00401     stale_ = true;
    00402   }
    00403
    00404   template <class T>
    00405   void DependentResult<T>::RecieveNotification(NotifyType notify_type, const Subject* subject)
    00406   {
    00407 #ifdef IP_DEBUG_CACHE
    00408     DBG_START_METH("DependentResult<T>::RecieveNotification", dbg_verbosity);
    00409 #endif
    00410
    00411     if (notify_type == NT_Changed || notify_type==NT_BeingDestroyed) {
    00412       stale_ = true;
    00413       // technically, I could unregister the notifications here, but they
    00414       // aren't really hurting anything
    00415     }
    00416   }
    00417
    00418   template <class T>
    00419   bool DependentResult<T>::DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00420       const std::vector<Number>& scalar_dependents) const
    00421   {
    00422 #ifdef IP_DEBUG_CACHE
    00423     DBG_START_METH("DependentResult<T>::DependentsIdentical", dbg_verbosity);
    00424     DBG_ASSERT(stale_ == false);
    00425     DBG_ASSERT(dependents.size() == dependent_tags_.size());
    00426 #endif
    00427
    00428     bool retVal = true;
    00429
    00430     if (dependents.size() != dependent_tags_.size()
    00431         || scalar_dependents.size() != scalar_dependents_.size()) {
    00432       retVal = false;
    00433     }
    00434     else {
    00435       for (Index i=0; i<(Index)dependents.size(); i++) {
    00436         if ( (dependents[i] && dependents[i]->GetTag() != dependent_tags_[i])
    00437              || (!dependents[i] && dependent_tags_[i] != 0) ) {
    00438           retVal = false;
    00439           break;
    00440         }
    00441       }
    00442       if (retVal) {
    00443         for (Index i=0; i<(Index)scalar_dependents.size(); i++) {
    00444           if (scalar_dependents[i] != scalar_dependents_[i]) {
    00445             retVal = false;
    00446             break;
    00447           }
    00448         }
    00449       }
    00450     }
    00451
    00452     return retVal;
    00453   }
    00454
    00455   template <class T>
    00456   const T& DependentResult<T>::GetResult() const
    00457   {
    00458 #ifdef IP_DEBUG_CACHE
    00459     DBG_START_METH("DependentResult<T>::GetResult()", dbg_verbosity);
    00460     DBG_ASSERT(stale_ == false);
    00461 #endif
    00462
    00463     return result_;
    00464   }
    00465
    00466   template <class T>
    00467   void DependentResult<T>::DebugPrint() const
    00468   {
    00469 #ifdef IP_DEBUG_CACHE
    00470     DBG_START_METH("DependentResult<T>::DebugPrint", dbg_verbosity);
    00471 #endif
    00472
    00473   }
    00474
    00475   template <class T>
    00476   CachedResults<T>::CachedResults(Int max_cache_size)
    00477       :
    00478       max_cache_size_(max_cache_size),
    00479       cached_results_(NULL)
    00480   {
    00481 #ifdef IP_DEBUG_CACHE
    00482     DBG_START_METH("CachedResults<T>::CachedResults", dbg_verbosity);
    00483 #endif
    00484
    00485   }
    00486
    00487   template <class T>
    00488   CachedResults<T>::~CachedResults()
    00489   {
    00490 #ifdef IP_DEBUG_CACHE
    00491     DBG_START_METH("CachedResults<T>::!CachedResults()", dbg_verbosity);
    00492 #endif
    00493
    00494     if (cached_results_) {
    00495       for (typename std::list< DependentResult<T>* >::iterator iter = cached_results_->
    00496            begin();
    00497            iter != cached_results_->end();
    00498            iter++) {
    00499         delete *iter;
    00500       }
    00501       delete cached_results_;
    00502     }
    00503     /*
    00504     while (!cached_results_.empty()) {
    00505       DependentResult<T>* result = cached_results_.back();
    00506       cached_results_.pop_back();
    00507       delete result;
    00508     }
    00509     */
    00510   }
    00511
    00512   template <class T>
    00513   void CachedResults<T>::AddCachedResult(const T& result,
    00514                                          const std::vector<const TaggedObject*>& dependents,
    00515                                          const std::vector<Number>& scalar_dependents)
    00516   {
    00517 #ifdef IP_DEBUG_CACHE
    00518     DBG_START_METH("CachedResults<T>::AddCachedResult", dbg_verbosity);
    00519 #endif
    00520
    00521     CleanupInvalidatedResults();
    00522
    00523     // insert the new one here
    00524     DependentResult<T>* newResult = new DependentResult<T>(result, dependents, scalar_dependents);
    00525     if (!cached_results_) {
    00526       cached_results_ = new std::list<DependentResult<T>*>;
    00527     }
    00528     cached_results_->push_front(newResult);
    00529
    00530     // keep the list small enough
    00531     if (max_cache_size_ >= 0) { // if negative, allow infinite cache
    00532       // non-negative - limit size of list to max_cache_size
    00533       DBG_ASSERT((Int)cached_results_->size()<=max_cache_size_+1);
    00534       if ((Int)cached_results_->size() > max_cache_size_) {
    00535         delete cached_results_->back();
    00536         cached_results_->pop_back();
    00537       }
    00538     }
    00539
    00540 #ifdef IP_DEBUG_CACHE
    00541     DBG_EXEC(2, DebugPrintCachedResults());
    00542 #endif
    00543
    00544   }
    00545
    00546   template <class T>
    00547   void CachedResults<T>::AddCachedResult(const T& result,
    00548                                          const std::vector<const TaggedObject*>& dependents)
    00549   {
    00550     std::vector<Number> scalar_dependents;
    00551     AddCachedResult(result, dependents, scalar_dependents);
    00552   }
    00553
    00554   template <class T>
    00555   bool CachedResults<T>::GetCachedResult(T& retResult, const std::vector<const TaggedObject*>& dependents,
    00556                                          const std::vector<Number>& scalar_dependents) const
    00557   {
    00558 #ifdef IP_DEBUG_CACHE
    00559     DBG_START_METH("CachedResults<T>::GetCachedResult", dbg_verbosity);
    00560 #endif
    00561
    00562     if (!cached_results_)
    00563       return false;
    00564
    00565     CleanupInvalidatedResults();
    00566
    00567     bool retValue = false;
    00568     typename std::list< DependentResult<T>* >::const_iterator iter;
    00569     for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00570       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00571         retResult = (*iter)->GetResult();
    00572         retValue = true;
    00573         break;
    00574       }
    00575     }
    00576
    00577 #ifdef IP_DEBUG_CACHE
    00578     DBG_EXEC(2, DebugPrintCachedResults());
    00579 #endif
    00580
    00581     return retValue;
    00582   }
    00583
    00584   template <class T>
    00585   bool CachedResults<T>::GetCachedResult(
    00586     T& retResult, const std::vector<const TaggedObject*>& dependents) const
    00587   {
    00588     std::vector<Number> scalar_dependents;
    00589     return GetCachedResult(retResult, dependents, scalar_dependents);
    00590   }
    00591
    00592   template <class T>
    00593   void CachedResults<T>::AddCachedResult1Dep(const T& result,
    00594       const TaggedObject* dependent1)
    00595   {
    00596 #ifdef IP_DEBUG_CACHE
    00597     DBG_START_METH("CachedResults<T>::AddCachedResult1Dep", dbg_verbosity);
    00598 #endif
    00599
    00600     std::vector<const TaggedObject*> dependents(1);
    00601     dependents[0] = dependent1;
    00602
    00603     AddCachedResult(result, dependents);
    00604   }
    00605
    00606   template <class T>
    00607   bool CachedResults<T>::GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1)
    00608   {
    00609 #ifdef IP_DEBUG_CACHE
    00610     DBG_START_METH("CachedResults<T>::GetCachedResult1Dep", dbg_verbosity);
    00611 #endif
    00612
    00613     std::vector<const TaggedObject*> dependents(1);
    00614     dependents[0] = dependent1;
    00615
    00616     return GetCachedResult(retResult, dependents);
    00617   }
    00618
    00619   template <class T>
    00620   void CachedResults<T>::AddCachedResult2Dep(const T& result, const TaggedObject* dependent1,
    00621       const TaggedObject* dependent2)
    00622
    00623   {
    00624 #ifdef IP_DEBUG_CACHE
    00625     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00626 #endif
    00627
    00628     std::vector<const TaggedObject*> dependents(2);
    00629     dependents[0] = dependent1;
    00630     dependents[1] = dependent2;
    00631
    00632     AddCachedResult(result, dependents);
    00633   }
    00634
    00635   template <class T>
    00636   bool CachedResults<T>::GetCachedResult2Dep(T& retResult, const TaggedObject* dependent1, const TaggedObject* dependent2)
    00637   {
    00638 #ifdef IP_DEBUG_CACHE
    00639     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00640 #endif
    00641
    00642     std::vector<const TaggedObject*> dependents(2);
    00643     dependents[0] = dependent1;
    00644     dependents[1] = dependent2;
    00645
    00646     return GetCachedResult(retResult, dependents);
    00647   }
    00648
    00649   template <class T>
    00650   void CachedResults<T>::AddCachedResult3Dep(const T& result, const TaggedObject* dependent1,
    00651       const TaggedObject* dependent2,
    00652       const TaggedObject* dependent3)
    00653
    00654   {
    00655 #ifdef IP_DEBUG_CACHE
    00656     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00657 #endif
    00658
    00659     std::vector<const TaggedObject*> dependents(3);
    00660     dependents[0] = dependent1;
    00661     dependents[1] = dependent2;
    00662     dependents[2] = dependent3;
    00663
    00664     AddCachedResult(result, dependents);
    00665   }
    00666
    00667   template <class T>
    00668   bool CachedResults<T>::GetCachedResult3Dep(T& retResult, const TaggedObject* dependent1,
    00669       const TaggedObject* dependent2,
    00670       const TaggedObject* dependent3)
    00671   {
    00672 #ifdef IP_DEBUG_CACHE
    00673     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00674 #endif
    00675
    00676     std::vector<const TaggedObject*> dependents(3);
    00677     dependents[0] = dependent1;
    00678     dependents[1] = dependent2;
    00679     dependents[2] = dependent3;
    00680
    00681     return GetCachedResult(retResult, dependents);
    00682   }
    00683
    00684   template <class T>
    00685   bool CachedResults<T>::InvalidateResult(const std::vector<const TaggedObject*>& dependents,
    00686                                           const std::vector<Number>& scalar_dependents)
    00687   {
    00688     if (!cached_results_)
    00689       return false;
    00690
    00691     CleanupInvalidatedResults();
    00692
    00693     bool retValue = false;
    00694     typename std::list< DependentResult<T>* >::const_iterator iter;
    00695     for (iter = cached_results_->begin(); iter != cached_results_->end();
    00696          iter++) {
    00697       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00698         (*iter)->Invalidate();
    00699         retValue = true;
    00700         break;
    00701       }
    00702     }
    00703
    00704     return retValue;
    00705   }
    00706
    00707   template <class T>
    00708   void CachedResults<T>::Clear()
    00709   {
    00710     if (!cached_results_)
    00711       return;
    00712
    00713     typename std::list< DependentResult<T>* >::const_iterator iter;
    00714     for (iter = cached_results_->begin(); iter != cached_results_->end();
    00715          iter++) {
    00716       (*iter)->Invalidate();
    00717     }
    00718
    00719     CleanupInvalidatedResults();
    00720   }
    00721
    00722   template <class T>
    00723   void CachedResults<T>::Clear(Int max_cache_size)
    00724   {
    00725     Clear();
    00726     max_cache_size_ = max_cache_size;
    00727   }
    00728
    00729   template <class T>
    00730   void CachedResults<T>::CleanupInvalidatedResults() const
    00731   {
    00732 #ifdef IP_DEBUG_CACHE
    00733     DBG_START_METH("CachedResults<T>::CleanupInvalidatedResults", dbg_verbosity);
    00734 #endif
    00735
    00736     if (!cached_results_)
    00737       return;
    00738
    00739     typename std::list< DependentResult<T>* >::iterator iter;
    00740     iter = cached_results_->begin();
    00741     while (iter != cached_results_->end()) {
    00742       if ((*iter)->IsStale()) {
    00743         typename std::list< DependentResult<T>* >::iterator
    00744         iter_to_remove = iter;
    00745         iter++;
    00746         DependentResult<T>* result_to_delete = (*iter_to_remove);
    00747         cached_results_->erase(iter_to_remove);
    00748         delete result_to_delete;
    00749       }
    00750       else {
    00751         iter++;
    00752       }
    00753     }
    00754   }
    00755
    00756   template <class T>
    00757   void CachedResults<T>::DebugPrintCachedResults() const
    00758   {
    00759 #ifdef IP_DEBUG_CACHE
    00760     DBG_START_METH("CachedResults<T>::DebugPrintCachedResults", dbg_verbosity);
    00761     if (DBG_VERBOSITY()>=2 ) {
    00762       if (!cached_results_) {
    00763         DBG_PRINT((2,"Currentlt no cached results:\n"));
    00764       }
    00765       else {
    00766         typename std::list< DependentResult<T>* >::const_iterator iter;
    00767         DBG_PRINT((2,"Current set of cached results:\n"));
    00768         for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00769           DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
    00770         }
    00771       }
    00772     }
    00773 #endif
    00774
    00775   }
    00776
    00777 } // namespace Ipopt
    00778
    00779 #endif

All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Defines