cpp/src/util/lru_cache_using_std.h

/******************************************************************************/
/*  Copyright (c) 2010-2011, Tim Day <timday@timday.com>                      */
/*                                                                            */
/*  Permission to use, copy, modify, and/or distribute this software for any  */
/*  purpose with or without fee is hereby granted, provided that the above    */
/*  copyright notice and this permission notice appear in all copies.         */
/*                                                                            */
/*  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES  */
/*  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF          */
/*  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR   */
/*  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES    */
/*  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN     */
/*  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF   */
/*  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.            */
/******************************************************************************/

// The original source code is from:
// https://bitbucket.org/timday/lru_cache/src/497822a492a8/include/lru_cache_using_std.h

#ifndef I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_
#define I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_

#include <cassert>
#include <cstddef>
#include <list>
#include <map>
#include <utility>

// Class providing fixed-size (by number of records)
// LRU-replacement cache of a function with signature
// V f(K).
// The default comparator/hash/allocator will be used.
template <
  typename K,
  typename V
  > class lru_cache_using_std
{
public:

  typedef K key_type;
  typedef V value_type;

  // Key access history, most recent at back
  typedef std::list<key_type> key_tracker_type;

  // Key to value and key history iterator
  typedef std::map<
    key_type,
    std::pair<
      value_type,
      typename key_tracker_type::iterator
      >
  > key_to_value_type;

  // Constuctor specifies the cached function and
  // the maximum number of records to be stored
  lru_cache_using_std(
    value_type (*f)(const key_type&),
    size_t c
  )
    :_fn(f)
    ,_capacity(c)
  {
    assert(_capacity!=0);
  }

  // Obtain value of the cached function for k
  value_type operator()(const key_type& k) {

    // Attempt to find existing record
    const typename key_to_value_type::iterator it
      =_key_to_value.find(k);

    if (it==_key_to_value.end()) {

      // We don't have it:

      // Evaluate function and create new record
      const value_type v=_fn(k);
      insert(k,v);

      // Return the freshly computed value
      return v;

    } else {

      // We do have it:

      // Update access record by moving
      // accessed key to back of list
      _key_tracker.splice(
	_key_tracker.end(),
	_key_tracker,
	(*it).second.second
      );

      // Return the retrieved value
      return (*it).second.first;
    }
  }

  // Obtain the cached keys, most recently used element
  // at head, least recently used at tail.
  // This method is provided purely to support testing.
  template <typename IT> void get_keys(IT dst) const {
    typename key_tracker_type::const_reverse_iterator src
	=_key_tracker.rbegin();
    while (src!=_key_tracker.rend()) {
      *dst++ = *src++;
    }
  }

private:

  // Record a fresh key-value pair in the cache
  void insert(const key_type& k,const value_type& v) {

    // Method is only called on cache misses
    assert(_key_to_value.find(k)==_key_to_value.end());

    // Make space if necessary
    if (_key_to_value.size()==_capacity)
      evict();

    // Record k as most-recently-used key
    typename key_tracker_type::iterator it
      =_key_tracker.insert(_key_tracker.end(),k);

    // Create the key-value entry,
    // linked to the usage record.
    _key_to_value.insert(
      std::make_pair(
	k,
	std::make_pair(v,it)
      )
    );
    // No need to check return,
    // given previous assert.
  }

  // Purge the least-recently-used element in the cache
  void evict() {

    // Assert method is never called when cache is empty
    assert(!_key_tracker.empty());

    // Identify least recently used key
    const typename key_to_value_type::iterator it
      =_key_to_value.find(_key_tracker.front());
    assert(it!=_key_to_value.end());

    // Erase both elements to completely purge record
    _key_to_value.erase(it);
    _key_tracker.pop_front();
  }

  // The function to be cached
  value_type (*_fn)(const key_type&);

  // Maximum number of key-value pairs to be retained
  const size_t _capacity;

  // Key access history
  key_tracker_type _key_tracker;

  // Key-to-value lookup
  key_to_value_type _key_to_value;
};

#endif  // I18N_ADDRESSINPUT_UTIL_LRU_CACHE_USING_STD_H_