- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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

Go to the documentation of this file.

    00001 // Copyright (C) 2004, 2007 International Business Machines and others.
    00002 // All Rights Reserved.
    00003 // This code is published under the Common Public License.
    00004 //
    00005 // $Id: IpCachedResults.hpp 949 2007-03-27 00:41:26Z 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 <algorithm>
    00015 #include <vector>
    00016 #include <list>
    00017
    00018 namespace Ipopt
    00019       //#define IP_DEBUG_CACHE
    00020 #if COIN_IPOPT_CHECKLEVEL > 2
    00021 # define IP_DEBUG_CACHE
    00022 #endif
    00023 #ifdef IP_DEBUG_CACHE
    00024 # include "IpDebug.hpp"
    00025 #endif
    00026 {
    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
    00263     static const Index dbg_verbosity;
    00264 #endif
    00265
    00269     DependentResult(const T& result, const std::vector<const TaggedObject*>& dependents,
    00270                     const std::vector<Number>& scalar_dependents);
    00271
    00273     ~DependentResult();
    00275
    00279     bool IsStale() const;
    00280
    00282     void Invalidate();
    00283
    00285     const T& GetResult() const;
    00287
    00292     bool DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00293                              const std::vector<Number>& scalar_dependents) const;
    00294
    00296     void DebugPrint() const;
    00297
    00298   protected:
    00306     virtual void RecieveNotification(NotifyType notify_type, const Subject* subject);
    00307
    00308   private:
    00309
    00319     DependentResult();
    00320
    00322     DependentResult(const DependentResult&);
    00323
    00325     void operator=(const DependentResult&);
    00327
    00331     bool stale_;
    00333     const T result_;
    00335     std::vector<TaggedObject::Tag> dependent_tags_;
    00337     std::vector<Number> scalar_dependents_;
    00338   };
    00339
    00340 #ifdef IP_DEBUG_CACHE
    00341
    00342   template <class T>
    00343   const Index CachedResults<T>::dbg_verbosity = 0;
    00344
    00345   template <class T>
    00346   const Index DependentResult<T>::dbg_verbosity = 0;
    00347 #endif
    00348
    00349   template <class T>
    00350   DependentResult<T>::DependentResult(
    00351     const T& result,
    00352     const std::vector<const TaggedObject*>& dependents,
    00353     const std::vector<Number>& scalar_dependents)
    00354       :
    00355       stale_(false),
    00356       result_(result),
    00357       dependent_tags_(dependents.size()),
    00358       scalar_dependents_(scalar_dependents)
    00359   {
    00360 #ifdef IP_DEBUG_CACHE
    00361     DBG_START_METH("DependentResult<T>::DependentResult()", dbg_verbosity);
    00362 #endif
    00363
    00364     for (Index i=0; i<(Index)dependents.size(); i++) {
    00365       if (dependents[i]) {
    00366         // Call the RequestAttach method of the Observer base class.
    00367         // This will add this dependent result in the Observer list
    00368         // for the Subject dependents[i].  As a consequence, the
    00369         // RecieveNotification method of this DependentResult will be
    00370         // called with notify_type=NT_Changed, whenever the
    00371         // TaggedResult dependents[i] is changed (i.e. its HasChanged
    00372         // method is called).
    00373         RequestAttach(NT_Changed, dependents[i]);
    00374         dependent_tags_[i] = dependents[i]->GetTag();
    00375       }
    00376       else {
    00377         dependent_tags_[i] = 0;
    00378       }
    00379     }
    00380   }
    00381
    00382   template <class T>
    00383   DependentResult<T>::~DependentResult()
    00384   {
    00385 #ifdef IP_DEBUG_CACHE
    00386     DBG_START_METH("DependentResult<T>::~DependentResult()", dbg_verbosity);
    00387     //DBG_ASSERT(stale_ == true);
    00388 #endif
    00389     // Nothing to be done here, destructor
    00390     // of T should sufficiently remove
    00391     // any memory, etc.
    00392   }
    00393
    00394   template <class T>
    00395   bool DependentResult<T>::IsStale() const
    00396   {
    00397     return stale_;
    00398   }
    00399
    00400   template <class T>
    00401   void DependentResult<T>::Invalidate()
    00402   {
    00403     stale_ = true;
    00404   }
    00405
    00406   template <class T>
    00407   void DependentResult<T>::RecieveNotification(NotifyType notify_type, const Subject* subject)
    00408   {
    00409 #ifdef IP_DEBUG_CACHE
    00410     DBG_START_METH("DependentResult<T>::RecieveNotification", dbg_verbosity);
    00411 #endif
    00412
    00413     if (notify_type == NT_Changed || notify_type==NT_BeingDestroyed) {
    00414       stale_ = true;
    00415       // technically, I could unregister the notifications here, but they
    00416       // aren't really hurting anything
    00417     }
    00418   }
    00419
    00420   template <class T>
    00421   bool DependentResult<T>::DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
    00422       const std::vector<Number>& scalar_dependents) const
    00423   {
    00424 #ifdef IP_DEBUG_CACHE
    00425     DBG_START_METH("DependentResult<T>::DependentsIdentical", dbg_verbosity);
    00426     DBG_ASSERT(stale_ == false);
    00427     DBG_ASSERT(dependents.size() == dependent_tags_.size());
    00428 #endif
    00429
    00430     bool retVal = true;
    00431
    00432     if (dependents.size() != dependent_tags_.size()
    00433         || scalar_dependents.size() != scalar_dependents_.size()) {
    00434       retVal = false;
    00435     }
    00436     else {
    00437       for (Index i=0; i<(Index)dependents.size(); i++) {
    00438         if ( (dependents[i] && dependents[i]->GetTag() != dependent_tags_[i])
    00439              || (!dependents[i] && dependent_tags_[i] != 0) ) {
    00440           retVal = false;
    00441           break;
    00442         }
    00443       }
    00444       if (retVal) {
    00445         for (Index i=0; i<(Index)scalar_dependents.size(); i++) {
    00446           if (scalar_dependents[i] != scalar_dependents_[i]) {
    00447             retVal = false;
    00448             break;
    00449           }
    00450         }
    00451       }
    00452     }
    00453
    00454     return retVal;
    00455   }
    00456
    00457   template <class T>
    00458   const T& DependentResult<T>::GetResult() const
    00459   {
    00460 #ifdef IP_DEBUG_CACHE
    00461     DBG_START_METH("DependentResult<T>::GetResult()", dbg_verbosity);
    00462     DBG_ASSERT(stale_ == false);
    00463 #endif
    00464
    00465     return result_;
    00466   }
    00467
    00468   template <class T>
    00469   void DependentResult<T>::DebugPrint() const
    00470   {
    00471 #ifdef IP_DEBUG_CACHE
    00472     DBG_START_METH("DependentResult<T>::DebugPrint", dbg_verbosity);
    00473 #endif
    00474
    00475   }
    00476
    00477   template <class T>
    00478   CachedResults<T>::CachedResults(Int max_cache_size)
    00479       :
    00480       max_cache_size_(max_cache_size),
    00481       cached_results_(NULL)
    00482   {
    00483 #ifdef IP_DEBUG_CACHE
    00484     DBG_START_METH("CachedResults<T>::CachedResults", dbg_verbosity);
    00485 #endif
    00486
    00487   }
    00488
    00489   template <class T>
    00490   CachedResults<T>::~CachedResults()
    00491   {
    00492 #ifdef IP_DEBUG_CACHE
    00493     DBG_START_METH("CachedResults<T>::!CachedResults()", dbg_verbosity);
    00494 #endif
    00495
    00496     if (cached_results_) {
    00497       for (typename std::list< DependentResult<T>* >::iterator iter = cached_results_->
    00498            begin();
    00499            iter != cached_results_->end();
    00500            iter++) {
    00501         delete *iter;
    00502       }
    00503       delete cached_results_;
    00504     }
    00505     /*
    00506     while (!cached_results_.empty()) {
    00507       DependentResult<T>* result = cached_results_.back();
    00508       cached_results_.pop_back();
    00509       delete result;
    00510     }
    00511     */
    00512   }
    00513
    00514   template <class T>
    00515   void CachedResults<T>::AddCachedResult(const T& result,
    00516                                          const std::vector<const TaggedObject*>& dependents,
    00517                                          const std::vector<Number>& scalar_dependents)
    00518   {
    00519 #ifdef IP_DEBUG_CACHE
    00520     DBG_START_METH("CachedResults<T>::AddCachedResult", dbg_verbosity);
    00521 #endif
    00522
    00523     CleanupInvalidatedResults();
    00524
    00525     // insert the new one here
    00526     DependentResult<T>* newResult = new DependentResult<T>(result, dependents, scalar_dependents);
    00527     if (!cached_results_) {
    00528       cached_results_ = new std::list<DependentResult<T>*>;
    00529     }
    00530     cached_results_->push_front(newResult);
    00531
    00532     // keep the list small enough
    00533     if (max_cache_size_ >= 0) { // if negative, allow infinite cache
    00534       // non-negative - limit size of list to max_cache_size
    00535       DBG_ASSERT((Int)cached_results_->size()<=max_cache_size_+1);
    00536       if ((Int)cached_results_->size() > max_cache_size_) {
    00537         delete cached_results_->back();
    00538         cached_results_->pop_back();
    00539       }
    00540     }
    00541
    00542 #ifdef IP_DEBUG_CACHE
    00543     DBG_EXEC(2, DebugPrintCachedResults());
    00544 #endif
    00545
    00546   }
    00547
    00548   template <class T>
    00549   void CachedResults<T>::AddCachedResult(const T& result,
    00550                                          const std::vector<const TaggedObject*>& dependents)
    00551   {
    00552     std::vector<Number> scalar_dependents;
    00553     AddCachedResult(result, dependents, scalar_dependents);
    00554   }
    00555
    00556   template <class T>
    00557   bool CachedResults<T>::GetCachedResult(T& retResult, const std::vector<const TaggedObject*>& dependents,
    00558                                          const std::vector<Number>& scalar_dependents) const
    00559   {
    00560 #ifdef IP_DEBUG_CACHE
    00561     DBG_START_METH("CachedResults<T>::GetCachedResult", dbg_verbosity);
    00562 #endif
    00563
    00564     if (!cached_results_)
    00565       return false;
    00566
    00567     CleanupInvalidatedResults();
    00568
    00569     bool retValue = false;
    00570     typename std::list< DependentResult<T>* >::const_iterator iter;
    00571     for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00572       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00573         retResult = (*iter)->GetResult();
    00574         retValue = true;
    00575         break;
    00576       }
    00577     }
    00578
    00579 #ifdef IP_DEBUG_CACHE
    00580     DBG_EXEC(2, DebugPrintCachedResults());
    00581 #endif
    00582
    00583     return retValue;
    00584   }
    00585
    00586   template <class T>
    00587   bool CachedResults<T>::GetCachedResult(
    00588     T& retResult, const std::vector<const TaggedObject*>& dependents) const
    00589   {
    00590     std::vector<Number> scalar_dependents;
    00591     return GetCachedResult(retResult, dependents, scalar_dependents);
    00592   }
    00593
    00594   template <class T>
    00595   void CachedResults<T>::AddCachedResult1Dep(const T& result,
    00596       const TaggedObject* dependent1)
    00597   {
    00598 #ifdef IP_DEBUG_CACHE
    00599     DBG_START_METH("CachedResults<T>::AddCachedResult1Dep", dbg_verbosity);
    00600 #endif
    00601
    00602     std::vector<const TaggedObject*> dependents(1);
    00603     dependents[0] = dependent1;
    00604
    00605     AddCachedResult(result, dependents);
    00606   }
    00607
    00608   template <class T>
    00609   bool CachedResults<T>::GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1)
    00610   {
    00611 #ifdef IP_DEBUG_CACHE
    00612     DBG_START_METH("CachedResults<T>::GetCachedResult1Dep", dbg_verbosity);
    00613 #endif
    00614
    00615     std::vector<const TaggedObject*> dependents(1);
    00616     dependents[0] = dependent1;
    00617
    00618     return GetCachedResult(retResult, dependents);
    00619   }
    00620
    00621   template <class T>
    00622   void CachedResults<T>::AddCachedResult2Dep(const T& result, const TaggedObject* dependent1,
    00623       const TaggedObject* dependent2)
    00624
    00625   {
    00626 #ifdef IP_DEBUG_CACHE
    00627     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00628 #endif
    00629
    00630     std::vector<const TaggedObject*> dependents(2);
    00631     dependents[0] = dependent1;
    00632     dependents[1] = dependent2;
    00633
    00634     AddCachedResult(result, dependents);
    00635   }
    00636
    00637   template <class T>
    00638   bool CachedResults<T>::GetCachedResult2Dep(T& retResult, const TaggedObject* dependent1, const TaggedObject* dependent2)
    00639   {
    00640 #ifdef IP_DEBUG_CACHE
    00641     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00642 #endif
    00643
    00644     std::vector<const TaggedObject*> dependents(2);
    00645     dependents[0] = dependent1;
    00646     dependents[1] = dependent2;
    00647
    00648     return GetCachedResult(retResult, dependents);
    00649   }
    00650
    00651   template <class T>
    00652   void CachedResults<T>::AddCachedResult3Dep(const T& result, const TaggedObject* dependent1,
    00653       const TaggedObject* dependent2,
    00654       const TaggedObject* dependent3)
    00655
    00656   {
    00657 #ifdef IP_DEBUG_CACHE
    00658     DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
    00659 #endif
    00660
    00661     std::vector<const TaggedObject*> dependents(3);
    00662     dependents[0] = dependent1;
    00663     dependents[1] = dependent2;
    00664     dependents[2] = dependent3;
    00665
    00666     AddCachedResult(result, dependents);
    00667   }
    00668
    00669   template <class T>
    00670   bool CachedResults<T>::GetCachedResult3Dep(T& retResult, const TaggedObject* dependent1,
    00671       const TaggedObject* dependent2,
    00672       const TaggedObject* dependent3)
    00673   {
    00674 #ifdef IP_DEBUG_CACHE
    00675     DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
    00676 #endif
    00677
    00678     std::vector<const TaggedObject*> dependents(3);
    00679     dependents[0] = dependent1;
    00680     dependents[1] = dependent2;
    00681     dependents[2] = dependent3;
    00682
    00683     return GetCachedResult(retResult, dependents);
    00684   }
    00685
    00686   template <class T>
    00687   bool CachedResults<T>::InvalidateResult(const std::vector<const TaggedObject*>& dependents,
    00688                                           const std::vector<Number>& scalar_dependents)
    00689   {
    00690     if (!cached_results_)
    00691       return false;
    00692
    00693     CleanupInvalidatedResults();
    00694
    00695     bool retValue = false;
    00696     typename std::list< DependentResult<T>* >::const_iterator iter;
    00697     for (iter = cached_results_->begin(); iter != cached_results_->end();
    00698          iter++) {
    00699       if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
    00700         (*iter)->Invalidate();
    00701         retValue = true;
    00702         break;
    00703       }
    00704     }
    00705
    00706     return retValue;
    00707   }
    00708
    00709   template <class T>
    00710   void CachedResults<T>::Clear()
    00711   {
    00712     if (!cached_results_)
    00713       return;
    00714
    00715     typename std::list< DependentResult<T>* >::const_iterator iter;
    00716     for (iter = cached_results_->begin(); iter != cached_results_->end();
    00717          iter++) {
    00718       (*iter)->Invalidate();
    00719     }
    00720
    00721     CleanupInvalidatedResults();
    00722   }
    00723
    00724   template <class T>
    00725   void CachedResults<T>::Clear(Int max_cache_size)
    00726   {
    00727     Clear();
    00728     max_cache_size_ = max_cache_size;
    00729   }
    00730
    00731   template <class T>
    00732   void CachedResults<T>::CleanupInvalidatedResults() const
    00733   {
    00734 #ifdef IP_DEBUG_CACHE
    00735     DBG_START_METH("CachedResults<T>::CleanupInvalidatedResults", dbg_verbosity);
    00736 #endif
    00737
    00738     if (!cached_results_)
    00739       return;
    00740
    00741     typename std::list< DependentResult<T>* >::iterator iter;
    00742     iter = cached_results_->begin();
    00743     while (iter != cached_results_->end()) {
    00744       if ((*iter)->IsStale()) {
    00745         typename std::list< DependentResult<T>* >::iterator
    00746         iter_to_remove = iter;
    00747         iter++;
    00748         DependentResult<T>* result_to_delete = (*iter_to_remove);
    00749         cached_results_->erase(iter_to_remove);
    00750         delete result_to_delete;
    00751       }
    00752       else {
    00753         iter++;
    00754       }
    00755     }
    00756   }
    00757
    00758   template <class T>
    00759   void CachedResults<T>::DebugPrintCachedResults() const
    00760   {
    00761 #ifdef IP_DEBUG_CACHE
    00762     DBG_START_METH("CachedResults<T>::DebugPrintCachedResults", dbg_verbosity);
    00763     if (DBG_VERBOSITY()>=2 ) {
    00764       if (!chached_results_) {
    00765         DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
    00766       }
    00767       else {
    00768         typename std::list< DependentResult<T>* >::const_iterator iter;
    00769         DBG_PRINT((2,"Current set of cached results:\n"));
    00770         for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
    00771           DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
    00772         }
    00773       }
    00774     }
    00775 #endif
    00776
    00777   }
    00778
    00779 } // namespace Ipopt
    00780
    00781 #endif