Ipopt  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
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$
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 Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines