Ipopt
trunk
|
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