IpCachedResults.hpp

Go to the documentation of this file.

// Copyright (C) 2004, 2006 International Business Machines and others.
// All Rights Reserved.
// This code is published under the Common Public License.
//
// $Id: IpCachedResults.hpp 759 2006-07-07 03:07:08Z andreasw $
//
// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13

#ifndef __IPCACHEDRESULTS_HPP__
#define __IPCACHEDRESULTS_HPP__

#include "IpTaggedObject.hpp"
#include "IpObserver.hpp"
#include "IpDebug.hpp"
#include <algorithm>
#include <vector>
#include <list>

namespace Ipopt
{

  // Forward Declarations

  template <class T>
  class DependentResult;

  //  AW: I'm taking this out, since this is by far the most used
  //  class.  We should keep it as simple as possible.
  //   /** Cache Priority Enum */
  //   enum CachePriority
  //   {
  //     CP_Lowest,
  //     CP_Standard,
  //     CP_Trial,
  //     CP_Iterate
  //   };

  template <class T>
  class CachedResults
  {
  public:
#ifdef IP_DEBUG_CACHE

    static const Index dbg_verbosity;
#endif

    CachedResults(Int max_cache_size);

    virtual ~CachedResults();

    void AddCachedResult(const T& result,
                         const std::vector<const TaggedObject*>& dependents,
                         const std::vector<Number>& scalar_dependents);

    bool GetCachedResult(T& retResult,
                         const std::vector<const TaggedObject*>& dependents,
                         const std::vector<Number>& scalar_dependents) const;

    void AddCachedResult(const T& result,
                         const std::vector<const TaggedObject*>& dependents);

    bool GetCachedResult(T& retResult,
                         const std::vector<const TaggedObject*>& dependents) const;

    void AddCachedResult1Dep(const T& result,
                             const TaggedObject* dependent1);

    bool GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1);

    void AddCachedResult2Dep(const T& result,
                             const TaggedObject* dependent1,
                             const TaggedObject* dependent2);

    bool GetCachedResult2Dep(T& retResult,
                             const TaggedObject* dependent1,
                             const TaggedObject* dependent2);

    void AddCachedResult3Dep(const T& result,
                             const TaggedObject* dependent1,
                             const TaggedObject* dependent2,
                             const TaggedObject* dependent3);

    bool GetCachedResult3Dep(T& retResult,
                             const TaggedObject* dependent1,
                             const TaggedObject* dependent2,
                             const TaggedObject* dependent3);

    bool GetCachedResult1Dep(T& retResult, const TaggedObject& dependent1)
    {
      return GetCachedResult1Dep(retResult, &dependent1);
    }
    bool GetCachedResult2Dep(T& retResult,
                             const TaggedObject& dependent1,
                             const TaggedObject& dependent2)
    {
      return GetCachedResult2Dep(retResult, &dependent1, &dependent2);
    }
    bool GetCachedResult3Dep(T& retResult,
                             const TaggedObject& dependent1,
                             const TaggedObject& dependent2,
                             const TaggedObject& dependent3)
    {
      return GetCachedResult3Dep(retResult, &dependent1, &dependent2, &dependent3);
    }
    void AddCachedResult1Dep(const T& result,
                             const TaggedObject& dependent1)
    {
      AddCachedResult1Dep(result, &dependent1);
    }
    void AddCachedResult2Dep(const T& result,
                             const TaggedObject& dependent1,
                             const TaggedObject& dependent2)
    {
      AddCachedResult2Dep(result, &dependent1, &dependent2);
    }
    void AddCachedResult3Dep(const T& result,
                             const TaggedObject& dependent1,
                             const TaggedObject& dependent2,
                             const TaggedObject& dependent3)
    {
      AddCachedResult3Dep(result, &dependent1, &dependent2, &dependent3);
    }

    bool InvalidateResult(const std::vector<const TaggedObject*>& dependents,
                          const std::vector<Number>& scalar_dependents);

  private:
    CachedResults();

    CachedResults(const CachedResults&);

    void operator=(const CachedResults&);

    Int max_cache_size_;

    mutable std::list<DependentResult<T>*>* cached_results_;

    void CleanupInvalidatedResults() const;

    void DebugPrintCachedResults() const;
  };

  template <class T>
  class DependentResult : public Observer
  {
  public:

#ifdef IP_DEBUG_CACHE

    static const Index dbg_verbosity;
#endif

    DependentResult(const T& result, const std::vector<const TaggedObject*>& dependents,
                    const std::vector<Number>& scalar_dependents);

    ~DependentResult();

    bool IsStale() const;

    void Invalidate();

    const T& GetResult() const;

    bool DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
                             const std::vector<Number>& scalar_dependents) const;

    void DebugPrint() const;

  protected:
    virtual void RecieveNotification(NotifyType notify_type, const Subject* subject);

  private:

    DependentResult();

    DependentResult(const DependentResult&);

    void operator=(const DependentResult&);

    bool stale_;
    const T result_;
    std::vector<TaggedObject::Tag> dependent_tags_;
    std::vector<Number> scalar_dependents_;
  };

#ifdef IP_DEBUG_CACHE

  template <class T>
  const Index CachedResults<T>::dbg_verbosity = 0;

  template <class T>
  const Index DependentResult<T>::dbg_verbosity = 0;
#endif

  template <class T>
  DependentResult<T>::DependentResult(
    const T& result,
    const std::vector<const TaggedObject*>& dependents,
    const std::vector<Number>& scalar_dependents)
      :
      stale_(false),
      result_(result),
      dependent_tags_(dependents.size()),
      scalar_dependents_(scalar_dependents)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::DependentResult()", dbg_verbosity);
#endif

    for (Index i=0; i<(Index)dependents.size(); i++) {
      if (dependents[i]) {
        // Call the RequestAttach method of the Observer base class.
        // This will add this dependent result in the Observer list
        // for the Subject dependents[i].  As a consequence, the
        // RecieveNotification method of this DependentResult will be
        // called with notify_type=NT_Changed, whenever the
        // TaggedResult dependents[i] is changed (i.e. its HasChanged
        // method is called).
        RequestAttach(NT_Changed, dependents[i]);
        dependent_tags_[i] = dependents[i]->GetTag();
      }
      else {
        dependent_tags_[i] = 0;
      }
    }
  }

  template <class T>
  DependentResult<T>::~DependentResult()
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::~DependentResult()", dbg_verbosity);
#endif
    //DBG_ASSERT(stale_ == true);
    // Nothing to be done here, destructor
    // of T should sufficiently remove
    // any memory, etc.
  }

  template <class T>
  bool DependentResult<T>::IsStale() const
  {
    return stale_;
  }

  template <class T>
  void DependentResult<T>::Invalidate()
  {
    stale_ = true;
  }

  template <class T>
  void DependentResult<T>::RecieveNotification(NotifyType notify_type, const Subject* subject)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::RecieveNotification", dbg_verbosity);
#endif

    if (notify_type == NT_Changed || notify_type==NT_BeingDestroyed) {
      stale_ = true;
      // technically, I could unregister the notifications here, but they
      // aren't really hurting anything
    }
  }

  template <class T>
  bool DependentResult<T>::DependentsIdentical(const std::vector<const TaggedObject*>& dependents,
      const std::vector<Number>& scalar_dependents) const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::DependentsIdentical", dbg_verbosity);
#endif

    DBG_ASSERT(stale_ == false);
    DBG_ASSERT(dependents.size() == dependent_tags_.size());

    bool retVal = true;

    if (dependents.size() != dependent_tags_.size()
        || scalar_dependents.size() != scalar_dependents_.size()) {
      retVal = false;
    }
    else {
      for (Index i=0; i<(Index)dependents.size(); i++) {
        if ( (dependents[i] && dependents[i]->GetTag() != dependent_tags_[i])
             || (!dependents[i] && dependent_tags_[i] != 0) ) {
          retVal = false;
          break;
        }
      }
      if (retVal) {
        for (Index i=0; i<(Index)scalar_dependents.size(); i++) {
          if (scalar_dependents[i] != scalar_dependents_[i]) {
            retVal = false;
            break;
          }
        }
      }
    }

    return retVal;
  }

  template <class T>
  const T& DependentResult<T>::GetResult() const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::GetResult()", dbg_verbosity);
#endif

    DBG_ASSERT(stale_ == false);
    return result_;
  }

  template <class T>
  void DependentResult<T>::DebugPrint() const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("DependentResult<T>::DebugPrint", dbg_verbosity);
#endif

  }

  template <class T>
  CachedResults<T>::CachedResults(Int max_cache_size)
      :
      max_cache_size_(max_cache_size),
      cached_results_(NULL)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::CachedResults", dbg_verbosity);
#endif

  }

  template <class T>
  CachedResults<T>::~CachedResults()
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::!CachedResults()", dbg_verbosity);
#endif

    if (cached_results_) {
      for (typename std::list< DependentResult<T>* >::iterator iter = cached_results_->
           begin();
           iter != cached_results_->end();
           iter++) {
        delete *iter;
      }
      delete cached_results_;
    }
    /*
    while (!cached_results_.empty()) {
      DependentResult<T>* result = cached_results_.back();
      cached_results_.pop_back();
      delete result;
    }
    */
  }

  template <class T>
  void CachedResults<T>::AddCachedResult(const T& result,
                                         const std::vector<const TaggedObject*>& dependents,
                                         const std::vector<Number>& scalar_dependents)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::AddCachedResult", dbg_verbosity);
#endif

    CleanupInvalidatedResults();

    // insert the new one here
    DependentResult<T>* newResult = new DependentResult<T>(result, dependents, scalar_dependents);
    if (!cached_results_) {
      cached_results_ = new std::list<DependentResult<T>*>;
    }
    cached_results_->push_front(newResult);

    // keep the list small enough
    if (max_cache_size_ >= 0) { // if negative, allow infinite cache
      // non-negative - limit size of list to max_cache_size
      DBG_ASSERT((Int)cached_results_->size()<=max_cache_size_+1);
      if ((Int)cached_results_->size() > max_cache_size_) {
        delete cached_results_->back();
        cached_results_->pop_back();
      }
    }

#ifdef IP_DEBUG_CACHE
    DBG_EXEC(2, DebugPrintCachedResults());
#endif

  }

  template <class T>
  void CachedResults<T>::AddCachedResult(const T& result,
                                         const std::vector<const TaggedObject*>& dependents)
  {
    std::vector<Number> scalar_dependents;
    AddCachedResult(result, dependents, scalar_dependents);
  }

  template <class T>
  bool CachedResults<T>::GetCachedResult(T& retResult, const std::vector<const TaggedObject*>& dependents,
                                         const std::vector<Number>& scalar_dependents) const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::GetCachedResult", dbg_verbosity);
#endif

    if (!cached_results_)
      return false;

    CleanupInvalidatedResults();

    bool retValue = false;
    typename std::list< DependentResult<T>* >::const_iterator iter;
    for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
      if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
        retResult = (*iter)->GetResult();
        retValue = true;
        break;
      }
    }

#ifdef IP_DEBUG_CACHE
    DBG_EXEC(2, DebugPrintCachedResults());
#endif

    return retValue;
  }

  template <class T>
  bool CachedResults<T>::GetCachedResult(
    T& retResult, const std::vector<const TaggedObject*>& dependents) const
  {
    std::vector<Number> scalar_dependents;
    return GetCachedResult(retResult, dependents, scalar_dependents);
  }

  template <class T>
  void CachedResults<T>::AddCachedResult1Dep(const T& result,
      const TaggedObject* dependent1)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::AddCachedResult1Dep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(1);
    dependents[0] = dependent1;

    AddCachedResult(result, dependents);
  }

  template <class T>
  bool CachedResults<T>::GetCachedResult1Dep(T& retResult, const TaggedObject* dependent1)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::GetCachedResult1Dep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(1);
    dependents[0] = dependent1;

    return GetCachedResult(retResult, dependents);
  }

  template <class T>
  void CachedResults<T>::AddCachedResult2Dep(const T& result, const TaggedObject* dependent1,
      const TaggedObject* dependent2)

  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(2);
    dependents[0] = dependent1;
    dependents[1] = dependent2;

    AddCachedResult(result, dependents);
  }

  template <class T>
  bool CachedResults<T>::GetCachedResult2Dep(T& retResult, const TaggedObject* dependent1, const TaggedObject* dependent2)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(2);
    dependents[0] = dependent1;
    dependents[1] = dependent2;

    return GetCachedResult(retResult, dependents);
  }

  template <class T>
  void CachedResults<T>::AddCachedResult3Dep(const T& result, const TaggedObject* dependent1,
      const TaggedObject* dependent2,
      const TaggedObject* dependent3)

  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::AddCachedResult2dDep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(3);
    dependents[0] = dependent1;
    dependents[1] = dependent2;
    dependents[2] = dependent3;

    AddCachedResult(result, dependents);
  }

  template <class T>
  bool CachedResults<T>::GetCachedResult3Dep(T& retResult, const TaggedObject* dependent1,
      const TaggedObject* dependent2,
      const TaggedObject* dependent3)
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::GetCachedResult2Dep", dbg_verbosity);
#endif

    std::vector<const TaggedObject*> dependents(3);
    dependents[0] = dependent1;
    dependents[1] = dependent2;
    dependents[2] = dependent3;

    return GetCachedResult(retResult, dependents);
  }

  template <class T>
  bool CachedResults<T>::InvalidateResult(const std::vector<const TaggedObject*>& dependents,
                                          const std::vector<Number>& scalar_dependents)
  {
    if (!cached_results_)
      return false;

    CleanupInvalidatedResults();

    bool retValue = false;
    typename std::list< DependentResult<T>* >::const_iterator iter;
    for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
      if ((*iter)->DependentsIdentical(dependents, scalar_dependents)) {
        (*iter)->Invalidate();
        retValue = true;
        break;
      }
    }

    return retValue;
  }

  template <class T>
  void CachedResults<T>::CleanupInvalidatedResults() const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::CleanupInvalidatedResults", dbg_verbosity);
#endif

    if (!cached_results_)
      return;

    typename std::list< DependentResult<T>* >::iterator iter;
    iter = cached_results_->begin();
    while (iter != cached_results_->end()) {
      if ((*iter)->IsStale()) {
        typename std::list< DependentResult<T>* >::iterator
        iter_to_remove = iter;
        iter++;
        DependentResult<T>* result_to_delete = (*iter_to_remove);
        cached_results_->erase(iter_to_remove);
        delete result_to_delete;
      }
      else {
        iter++;
      }
    }
  }

  template <class T>
  void CachedResults<T>::DebugPrintCachedResults() const
  {
#ifdef IP_DEBUG_CACHE
    DBG_START_METH("CachedResults<T>::DebugPrintCachedResults", dbg_verbosity);
    if (DBG_VERBOSITY()>=2 ) {
      if (!chached_results_) {
        DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
      }
      else {
        typename std::list< DependentResult<T>* >::const_iterator iter;
        DBG_PRINT((2,"Current set of cached results:\n"));
        for (iter = cached_results_->begin(); iter != cached_results_->end(); iter++) {
          DBG_PRINT((2,"  DependentResult:0x%x\n", (*iter)));
        }
      }
    }
#endif

  }

} // namespace Ipopt

#endif