00001
00002
00003
00004
00005
00006
00007
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 #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
00029
00030 template <class T>
00031 class DependentResult;
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
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
00367
00368
00369
00370
00371
00372
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
00388 #endif
00389
00390
00391
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
00416
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
00507
00508
00509
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
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
00533 if (max_cache_size_ >= 0) {
00534
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 }
00780
00781 #endif