IpCachedResults.hpp
Go to the documentation of this file.
1 // Copyright (C) 2004, 2011 International Business Machines and others.
2 // All Rights Reserved.
3 // This code is published under the Eclipse Public License.
4 //
5 // $Id: IpCachedResults.hpp 2019 2011-06-15 16:32:30Z andreasw $
6 //
7 // Authors: Carl Laird, Andreas Waechter IBM 2004-08-13
8 
9 #ifndef __IPCACHEDRESULTS_HPP__
10 #define __IPCACHEDRESULTS_HPP__
11 
12 #include "IpTaggedObject.hpp"
13 #include "IpObserver.hpp"
14 #include <algorithm>
15 #include <vector>
16 #include <list>
17 
18 namespace Ipopt
19  //#define IP_DEBUG_CACHE
21 # define IP_DEBUG_CACHE
22 #endif
23 #ifdef IP_DEBUG_CACHE
24 # include "IpDebug.hpp"
25 #endif
26 {
27 
28  // Forward Declarations
29 
30  template <class T>
31  class DependentResult;
32 
33  // AW: I'm taking this out, since this is by far the most used
34  // class. We should keep it as simple as possible.
35  // /** Cache Priority Enum */
36  // enum CachePriority
37  // {
38  // CP_Lowest,
39  // CP_Standard,
40  // CP_Trial,
41  // CP_Iterate
42  // };
43 
69  template <class T>
71  {
72  public:
73 #ifdef IP_DEBUG_CACHE
74 
75  static const Index dbg_verbosity;
76 #endif
77 
84  CachedResults(Int max_cache_size);
85 
87  virtual ~CachedResults();
89 
95  void AddCachedResult(const T& result,
96  const std::vector<const TaggedObject*>& dependents,
97  const std::vector<Number>& scalar_dependents);
98 
103  bool GetCachedResult(T& retResult,
104  const std::vector<const TaggedObject*>& dependents,
105  const std::vector<Number>& scalar_dependents) const;
106 
110  void AddCachedResult(const T& result,
111  const std::vector<const TaggedObject*>& dependents);
112 
116  bool GetCachedResult(T& retResult,
117  const std::vector<const TaggedObject*>& dependents) const;
119 
127  void AddCachedResult1Dep(const T& result,
128  const TaggedObject* dependent1);
129 
133  bool GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1);
134 
138  void AddCachedResult2Dep(const T& result,
139  const TaggedObject* dependent1,
140  const TaggedObject* dependent2);
141 
145  bool GetCachedResult2Dep(T& retResult,
146  const TaggedObject* dependent1,
147  const TaggedObject* dependent2);
148 
152  void AddCachedResult3Dep(const T& result,
153  const TaggedObject* dependent1,
154  const TaggedObject* dependent2,
155  const TaggedObject* dependent3);
156 
160  bool GetCachedResult3Dep(T& retResult,
161  const TaggedObject* dependent1,
162  const TaggedObject* dependent2,
163  const TaggedObject* dependent3);
164 
167  bool GetCachedResult1Dep(T& retResult, const TaggedObject& dependent1)
168  {
169  return GetCachedResult1Dep(retResult, &dependent1);
170  }
171  bool GetCachedResult2Dep(T& retResult,
172  const TaggedObject& dependent1,
173  const TaggedObject& dependent2)
174  {
175  return GetCachedResult2Dep(retResult, &dependent1, &dependent2);
176  }
177  bool GetCachedResult3Dep(T& retResult,
178  const TaggedObject& dependent1,
179  const TaggedObject& dependent2,
180  const TaggedObject& dependent3)
181  {
182  return GetCachedResult3Dep(retResult, &dependent1, &dependent2, &dependent3);
183  }
184  void AddCachedResult1Dep(const T& result,
185  const TaggedObject& dependent1)
186  {
187  AddCachedResult1Dep(result, &dependent1);
188  }
189  void AddCachedResult2Dep(const T& result,
190  const TaggedObject& dependent1,
191  const TaggedObject& dependent2)
192  {
193  AddCachedResult2Dep(result, &dependent1, &dependent2);
194  }
195  void AddCachedResult3Dep(const T& result,
196  const TaggedObject& dependent1,
197  const TaggedObject& dependent2,
198  const TaggedObject& dependent3)
199  {
200  AddCachedResult3Dep(result, &dependent1, &dependent2, &dependent3);
201  }
203 
207  bool InvalidateResult(const std::vector<const TaggedObject*>& dependents,
208  const std::vector<Number>& scalar_dependents);
209 
211  void Clear();
212 
214  void Clear(Int max_cache_size);
215 
216  private:
226  CachedResults();
227 
230 
232  void operator=(const CachedResults&);
234 
237 
239  mutable std::list<DependentResult<T>*>* cached_results_;
240 
245  void CleanupInvalidatedResults() const;
246 
248  void DebugPrintCachedResults() const;
249  };
250 
256  template <class T>
257  class DependentResult : public Observer
258  {
259  public:
260 
261 #ifdef IP_DEBUG_CACHE
262 
263  static const Index dbg_verbosity;
264 #endif
265 
269  DependentResult(const T& result, const std::vector<const TaggedObject*>& dependents,
270  const std::vector<Number>& scalar_dependents);
271 
275 
279  bool IsStale() const;
280 
282  void Invalidate();
283 
285  const T& GetResult() const;
287 
292  bool DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
293  const std::vector<Number>& scalar_dependents) const;
294 
296  void DebugPrint() const;
297 
298  protected:
306  virtual void RecieveNotification(NotifyType notify_type, const Subject* subject);
307 
308  private:
309 
319  DependentResult();
320 
323 
325  void operator=(const DependentResult&);
327 
331  bool stale_;
333  const T result_;
335  std::vector<TaggedObject::Tag> dependent_tags_;
337  std::vector<Number> scalar_dependents_;
338  };
339 
340 #ifdef IP_DEBUG_CACHE
341 
342  template <class T>
344 
345  template <class T>
347 #endif
348 
349  template <class T>
351  const T& result,
352  const std::vector<const TaggedObject*>& dependents,
353  const std::vector<Number>& scalar_dependents)
354  :
355  stale_(false),
356  result_(result),
357  dependent_tags_(dependents.size()),
358  scalar_dependents_(scalar_dependents)
359  {
360 #ifdef IP_DEBUG_CACHE
361  DBG_START_METH("DependentResult<T>::DependentResult()", dbg_verbosity);
362 #endif
363 
364  for (Index i=0; i<(Index)dependents.size(); i++) {
365  if (dependents[i]) {
366  // Call the RequestAttach method of the Observer base class.
367  // This will add this dependent result in the Observer list
368  // for the Subject dependents[i]. As a consequence, the
369  // RecieveNotification method of this DependentResult will be
370  // called with notify_type=NT_Changed, whenever the
371  // TaggedResult dependents[i] is changed (i.e. its HasChanged
372  // method is called).
373  RequestAttach(NT_Changed, dependents[i]);
374  dependent_tags_[i] = dependents[i]->GetTag();
375  }
376  else {
377  dependent_tags_[i] = 0;
378  }
379  }
380  }
381 
382  template <class T>
384  {
385 #ifdef IP_DEBUG_CACHE
386  DBG_START_METH("DependentResult<T>::~DependentResult()", dbg_verbosity);
387  //DBG_ASSERT(stale_ == true);
388 #endif
389  // Nothing to be done here, destructor
390  // of T should sufficiently remove
391  // any memory, etc.
392  }
393 
394  template <class T>
396  {
397  return stale_;
398  }
399 
400  template <class T>
402  {
403  stale_ = true;
404  }
405 
406  template <class T>
408  {
409 #ifdef IP_DEBUG_CACHE
410  DBG_START_METH("DependentResult<T>::RecieveNotification", dbg_verbosity);
411 #endif
412 
413  if (notify_type == NT_Changed || notify_type==NT_BeingDestroyed) {
414  stale_ = true;
415  // technically, I could unregister the notifications here, but they
416  // aren't really hurting anything
417  }
418  }
419 
420  template <class T>
421  bool DependentResult<T>::DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
422  const std::vector<Number>& scalar_dependents) const
423  {
424 #ifdef IP_DEBUG_CACHE
425  DBG_START_METH("DependentResult<T>::DependentsIdentical", dbg_verbosity);
426  DBG_ASSERT(stale_ == false);
427  DBG_ASSERT(dependents.size() == dependent_tags_.size());
428 #endif
429 
430  bool retVal = true;
431 
432  if (dependents.size() != dependent_tags_.size()
433  || scalar_dependents.size() != scalar_dependents_.size()) {
434  retVal = false;
435  }
436  else {
437  for (Index i=0; i<(Index)dependents.size(); i++) {
438  if ( (dependents[i] && dependents[i]->GetTag() != dependent_tags_[i])
439  || (!dependents[i] && dependent_tags_[i] != 0) ) {
440  retVal = false;
441  break;
442  }
443  }
444  if (retVal) {
445  for (Index i=0; i<(Index)scalar_dependents.size(); i++) {
446  if (scalar_dependents[i] != scalar_dependents_[i]) {
447  retVal = false;
448  break;
449  }
450  }
451  }
452  }
453 
454  return retVal;
455  }
456 
457  template <class T>
459  {
460 #ifdef IP_DEBUG_CACHE
461  DBG_START_METH("DependentResult<T>::GetResult()", dbg_verbosity);
462  DBG_ASSERT(stale_ == false);
463 #endif
464 
465  return result_;
466  }
467 
468  template <class T>
470  {
471 #ifdef IP_DEBUG_CACHE
472  DBG_START_METH("DependentResult<T>::DebugPrint", dbg_verbosity);
473 #endif
474 
475  }
476 
477  template <class T>
479  :
480  max_cache_size_(max_cache_size),
481  cached_results_(NULL)
482  {
483 #ifdef IP_DEBUG_CACHE
484  DBG_START_METH("CachedResults<T>::CachedResults", dbg_verbosity);
485 #endif
486 
487  }
488 
489  template <class T>
491  {
492 #ifdef IP_DEBUG_CACHE
493  DBG_START_METH("CachedResults<T>::!CachedResults()", dbg_verbosity);
494 #endif
495 
496  if (cached_results_) {
497  for (typename std::list< DependentResult<T>* >::iterator iter = cached_results_->
498  begin();
499  iter != cached_results_->end();
500  iter++) {
501  delete *iter;
502  }
503  delete cached_results_;
504  }
505  /*
506  while (!cached_results_.empty()) {
507  DependentResult<T>* result = cached_results_.back();
508  cached_results_.pop_back();
509  delete result;
510  }
511  */
512  }
513 
514  template <class T>
515  void CachedResults<T>::AddCachedResult(const T& result,
516  const std::vector<const TaggedObject*>& dependents,
517  const std::vector<Number>& scalar_dependents)
518  {
519 #ifdef IP_DEBUG_CACHE
520  DBG_START_METH("CachedResults<T>::AddCachedResult", dbg_verbosity);
521 #endif
522 
523  CleanupInvalidatedResults();
524 
525  // insert the new one here
526  DependentResult<T>* newResult = new DependentResult<T>(result, dependents, scalar_dependents);
527  if (!cached_results_) {
528  cached_results_ = new std::list<DependentResult<T>*>;
529  }
530  cached_results_->push_front(newResult);
531 
532  // keep the list small enough
533  if (max_cache_size_ >= 0) { // if negative, allow infinite cache
534  // non-negative - limit size of list to max_cache_size
535  DBG_ASSERT((Int)cached_results_->size()<=max_cache_size_+1);
536  if ((Int)cached_results_->size() > max_cache_size_) {
537  delete cached_results_->back();
538  cached_results_->pop_back();
539  }
540  }
541 
542 #ifdef IP_DEBUG_CACHE
543  DBG_EXEC(2, DebugPrintCachedResults());
544 #endif
545 
546  }
547 
548  template <class T>
549  void CachedResults<T>::AddCachedResult(const T& result,
550  const std::vector<const TaggedObject*>& dependents)
551  {
552  std::vector<Number> scalar_dependents;
553  AddCachedResult(result, dependents, scalar_dependents);
554  }
555 
556  template <class T>
557  bool CachedResults<T>::GetCachedResult(T& retResult, const std::vector<const TaggedObject*>& dependents,
558  const std::vector<Number>& scalar_dependents) const
559  {
560 #ifdef IP_DEBUG_CACHE
561  DBG_START_METH("CachedResults<T>::GetCachedResult", dbg_verbosity);
562 #endif
563 
564  if (!cached_results_)
565  return false;
566 
567  CleanupInvalidatedResults();
568 
569  bool retValue = false;
570  typename std::list< DependentResult<T>* >::const_iterator iter;
571  for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
572  if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
573  retResult = (*iter)->GetResult();
574  retValue = true;
575  break;
576  }
577  }
578 
579 #ifdef IP_DEBUG_CACHE
580  DBG_EXEC(2, DebugPrintCachedResults());
581 #endif
582 
583  return retValue;
584  }
585 
586  template <class T>
588  T& retResult, const std::vector<const TaggedObject*>& dependents) const
589  {
590  std::vector<Number> scalar_dependents;
591  return GetCachedResult(retResult, dependents, scalar_dependents);
592  }
593 
594  template <class T>
596  const TaggedObject* dependent1)
597  {
598 #ifdef IP_DEBUG_CACHE
599  DBG_START_METH("CachedResults<T>::AddCachedResult1Dep", dbg_verbosity);
600 #endif
601 
602  std::vector<const TaggedObject*> dependents(1);
603  dependents[0] = dependent1;
604 
605  AddCachedResult(result, dependents);
606  }
607 
608  template <class T>
609  bool CachedResults<T>::GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1)
610  {
611 #ifdef IP_DEBUG_CACHE
612  DBG_START_METH("CachedResults<T>::GetCachedResult1Dep", dbg_verbosity);
613 #endif
614 
615  std::vector<const TaggedObject*> dependents(1);
616  dependents[0] = dependent1;
617 
618  return GetCachedResult(retResult, dependents);
619  }
620 
621  template <class T>
622  void CachedResults<T>::AddCachedResult2Dep(const T& result, const TaggedObject* dependent1,
623  const TaggedObject* dependent2)
624 
625  {
626 #ifdef IP_DEBUG_CACHE
627  DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
628 #endif
629 
630  std::vector<const TaggedObject*> dependents(2);
631  dependents[0] = dependent1;
632  dependents[1] = dependent2;
633 
634  AddCachedResult(result, dependents);
635  }
636 
637  template <class T>
638  bool CachedResults<T>::GetCachedResult2Dep(T& retResult, const TaggedObject* dependent1, const TaggedObject* dependent2)
639  {
640 #ifdef IP_DEBUG_CACHE
641  DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
642 #endif
643 
644  std::vector<const TaggedObject*> dependents(2);
645  dependents[0] = dependent1;
646  dependents[1] = dependent2;
647 
648  return GetCachedResult(retResult, dependents);
649  }
650 
651  template <class T>
652  void CachedResults<T>::AddCachedResult3Dep(const T& result, const TaggedObject* dependent1,
653  const TaggedObject* dependent2,
654  const TaggedObject* dependent3)
655 
656  {
657 #ifdef IP_DEBUG_CACHE
658  DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
659 #endif
660 
661  std::vector<const TaggedObject*> dependents(3);
662  dependents[0] = dependent1;
663  dependents[1] = dependent2;
664  dependents[2] = dependent3;
665 
666  AddCachedResult(result, dependents);
667  }
668 
669  template <class T>
670  bool CachedResults<T>::GetCachedResult3Dep(T& retResult, const TaggedObject* dependent1,
671  const TaggedObject* dependent2,
672  const TaggedObject* dependent3)
673  {
674 #ifdef IP_DEBUG_CACHE
675  DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
676 #endif
677 
678  std::vector<const TaggedObject*> dependents(3);
679  dependents[0] = dependent1;
680  dependents[1] = dependent2;
681  dependents[2] = dependent3;
682 
683  return GetCachedResult(retResult, dependents);
684  }
685 
686  template <class T>
687  bool CachedResults<T>::InvalidateResult(const std::vector<const TaggedObject*>& dependents,
688  const std::vector<Number>& scalar_dependents)
689  {
690  if (!cached_results_)
691  return false;
692 
693  CleanupInvalidatedResults();
694 
695  bool retValue = false;
696  typename std::list< DependentResult<T>* >::const_iterator iter;
697  for (iter = cached_results_->begin(); iter != cached_results_->end();
698  iter++) {
699  if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
700  (*iter)->Invalidate();
701  retValue = true;
702  break;
703  }
704  }
705 
706  return retValue;
707  }
708 
709  template <class T>
711  {
712  if (!cached_results_)
713  return;
714 
715  typename std::list< DependentResult<T>* >::const_iterator iter;
716  for (iter = cached_results_->begin(); iter != cached_results_->end();
717  iter++) {
718  (*iter)->Invalidate();
719  }
720 
721  CleanupInvalidatedResults();
722  }
723 
724  template <class T>
725  void CachedResults<T>::Clear(Int max_cache_size)
726  {
727  Clear();
728  max_cache_size_ = max_cache_size;
729  }
730 
731  template <class T>
733  {
734 #ifdef IP_DEBUG_CACHE
735  DBG_START_METH("CachedResults<T>::CleanupInvalidatedResults", dbg_verbosity);
736 #endif
737 
738  if (!cached_results_)
739  return;
740 
741  typename std::list< DependentResult<T>* >::iterator iter;
742  iter = cached_results_->begin();
743  while (iter != cached_results_->end()) {
744  if ((*iter)->IsStale()) {
745  typename std::list< DependentResult<T>* >::iterator
746  iter_to_remove = iter;
747  iter++;
748  DependentResult<T>* result_to_delete = (*iter_to_remove);
749  cached_results_->erase(iter_to_remove);
750  delete result_to_delete;
751  }
752  else {
753  iter++;
754  }
755  }
756  }
757 
758  template <class T>
760  {
761 #ifdef IP_DEBUG_CACHE
762  DBG_START_METH("CachedResults<T>::DebugPrintCachedResults", dbg_verbosity);
763  if (DBG_VERBOSITY()>=2 ) {
764  if (!cached_results_) {
765  DBG_PRINT((2,"Currentlt no cached results:\n"));
766  }
767  else {
768  typename std::list< DependentResult<T>* >::const_iterator iter;
769  DBG_PRINT((2,"Current set of cached results:\n"));
770  for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
771  DBG_PRINT((2," DependentResult:0x%x\n", (*iter)));
772  }
773  }
774  }
775 #endif
776 
777  }
778 
779 } // namespace Ipopt
780 
781 #endif