#ifndef _utl_Cache_h_
#define _utl_Cache_h_

#include <boost/smart_ptr.hpp>


namespace utl {

  template<typename AResult, class Functor, typename AArgument>
  class Cache {
  public:
    Cache() : fMaxSize(0), fSize(0), fRoot(NULL) { }

    Cache(const Functor* const functorPtr, const unsigned int maxSize)
      : fFunctorPtr(functorPtr), fMaxSize(maxSize), fSize(0), fRoot(NULL)
    { }

    Cache(const Cache& other)
      : fFunctorPtr(other.fFunctorPtr), fMaxSize(other.fMaxSize),
        fSize(0), fRoot(NULL)
    { }

    Cache&
    operator=(const Cache& other)
    {
      if (this != &other) {
        Reset();
        fFunctorPtr = other.fFunctorPtr;
        fMaxSize = other.fMaxSize;
      }
      return *this;
    }

    ~Cache() { Reset(); }

    void
    Reset()
    {
      fSize = 0;
      Node* curr = fRoot;
      while (curr != NULL) {
        Node* node = curr;
        curr = curr->next;
        delete node;
      }
      fRoot = NULL;
    }

    AResult
    operator()(const AArgument& arg)
    {
      if (fRoot == NULL) {
        fRoot = new Node;
        fRoot->arg = arg;
        fRoot->res = (*fFunctorPtr.get())(arg);
        fRoot->next = NULL;
        ++fSize;
        return fRoot->res;
      }

      if (fRoot->arg == arg)
        return fRoot->res;

      Node* prev = NULL;
      Node* curr = fRoot;
      while (curr->next != NULL) {
        prev = curr;
        curr = curr->next;
        if (curr->arg == arg) {
          // move curr to front
          prev->next = curr->next;
          curr->next = fRoot;
          fRoot = curr;
          return curr->res;
        }
      }

      // cache miss, curr is last valid element
      if (fSize < fMaxSize) {
        // cache is not full: push to front
        Node* node = new Node;
        node->next = fRoot;
        node->arg = arg;
        node->res = (*fFunctorPtr.get())(arg);
        fRoot = node;
        ++fSize;
      } else {
        // cache is full: recycle last element
        prev->next = NULL;
        curr->next = fRoot;
        curr->arg = arg;
        curr->res = (*fFunctorPtr.get())(arg);
        fRoot = curr;
      }

      return fRoot->res;
    }

  protected:
    struct Node {
      AArgument arg;
      AResult res;
      Node* next;
    };

    boost::shared_ptr<const Functor> fFunctorPtr;
    unsigned int fMaxSize;
    unsigned int fSize;
    Node* fRoot;
  };

} // ns utl

#endif