package com.randomnoun.common;
   
   /* (c) 2013 randomnoun. All Rights Reserved. This work is licensed under a
    * BSD Simplified License. (http://www.randomnoun.com/bsd-simplified.html)
    */
   
   import java.util.*;
   
   import org.apache.log4j.Logger;
  
  /**
   * Most-recently used cache class. 
   * 
   * <p>You probably want to use something in the guava Collections library these days instead.
   * 
   * <p>This class can be used to implement serverside data caches. The constructor
   * takes three parameters: maximum size, expiry time (in milliseconds) and a 
   * 'RetrievalCallback' object (defined as an interface in this class). 
   * 
   * <p>As items are put into this object, they are timestamped; if a key is applied
   * to retrieve an object that has 'expired', then this object will return null
   * (if no callback has been supplied), or will execute the callback to refresh
   * the value. A callback can (optionally) be supplied with every get() invocation
   * so that this object knows precisely how to generate the requested object. (This
   * works since it is usually computationally cheaper to generate the Callback object
   * than to generate the result of the callback, which generally needs to fetch
   * information from a database).
   * 
   * <p>There are two possible expiry mechanisms: either an item is expired from the
   * time it is entered into the cache, or expired from the time it is last retrieved
   * from the cache. The former makes sense for 'dynamic' data that may change over time
   * (e.g. rowcounts); the latter makes sense for 'static' data that is just used to
   * cache large objects that don't need to be in memory at all times 
   * (e.g. message definitions). By default this object will operate as per 'static'
   * rules; the other method can be selected by calling the setDynamicCaching() after
   * construction.
   *
   * <p><b>Implementation notes</b>
   *    
   * <p>It may be possible to extend this class to use WeakReferences, so that it can
   * shrink in size as memory constraints within the VM become increased. This is 
   * unlikely to be useful in practice, however, since this is probably an indication
   * of a memory leak or over-utilised server. It may make more sense to just reduce the
   * maximum size in these cases. Performance tuning would be required to know 
   * for sure.
   * 
   * <p>Also note that if an object exceeds it's expiryTime, it is *not* automatically
   * removed from the cache. This would involve having an additional Timer thread
   * running through these objects and scanning for expired objects, which is unlikely
   * to be useful in practice. An additional method could be implemented to trigger these
   * cleanups if this becomes necessary.
   * 
   * @author knoxg
   * 
   *
   */
  
  // this probably isn't as efficient as it could be (it contains a mruList AND a 
  // HashMap of expiryTimes, which I'm sure is overkill. To do this properly
  // would involve extending Map.Entry to include a timestamp value, however,
  // which would require a fair amount of re-engineering. (would need to subclass 
  // Map.Entry, and use "this.putAll()" to insert subclasses into this instance. 
  // you'd still need a way of keeping a sorted list of timestamped entries anyway,
  // now that I think about it (to choose the next expiry candidate), so this may not 
  // be so bad after all. 
  public class MRUCache<K, V>
      extends HashMap<K, V>
  {
      
      /** Generated serialVersionUID */
      private static final long serialVersionUID = -6826049000932880050L;
  
  	/** Logger instance for this class */
      public static Logger logger = Logger.getLogger(MRUCache.class);
      
      /** The callback interface. Caches should provide one of these classes to 
       * perform any time-consuming tasks required to generate values in this cache.
       * If the time taken to generate a value isn't time-consuming, then perhaps
       * you shouldn't be using a cache to store them.
       */
      public static interface RetrievalCallback<K, V> {
          
          /** Dynamically generates the value of an entity in a cache
           * 
           * @param key The key used to reference the cached object
           * 
           * @return The newly generated (or updated) cached object
           */ 
          public V get(K key);
      }
      
      /** If set to true, expires data from the time it was <i>entered</i> into the cache,
       * rather than the time if was <i>fetched</i> from the cache. Suitable when we 
       * wish to apply a strict expiry time for dynamically-updating data, e.g.
       * rowcounts.
       */
      private boolean dynamicCaching = false;
  
      /** An ordered list of the objects in this cache. Objects at position 0 on the list
      *  have been the most recently accessed (i.e. objects will be expired from the
      * end of this list). */
     private LinkedList<K> mruList;
 
     /** The maximum number of elements that this cache can hold. If &lt;= 0, then the
      * size of the map is unlimited. */
     private int cacheSize;
 
     /** A callback which can be used to populate entries in the cache that are unknown,
      *  or have expired. */
     private RetrievalCallback<K, V> callbackInstance;
 
     /** A Map whose keys are elements in this cache, and who's entries are the last time
      *  that entry was 'touched' (i.e. added to or retrieved from the cache) */
     private Map<K, Long> lastUpdatedTimes;
 
     /** The amount of time an entry can remain valid, measured from when the element
      *  is first added to the cache. If expiryTime is set to &lt;= 0, then items never expire. */
     private int expiryTime;
 
     /**
      * Creates a new MRUCache object.
      *
      * @param cacheSize  The maximum number of elements that this cache can hold. A value &lt;=0 means 
      *    that the size of this map is not limited.
      * @param expiryTime The amount of time (in ms) an entry can remain valid, measured from when the element
      *    is first added to the cache (or last retrieved if {@link #setDynamicCaching()} is 
      *    in effect. A value &lt;=0 means that items do not have an
      *    expiry period.
      * @param callback   A callback which can be used to populate entries in the cache that are unknown,
      *    or have expired. This parameter can be set to null <b>if and only if</b> the
      *    two-parameter {@link #get(Object, RetrievalCallback)} method is used to retrieve
      *    elements from the map.
      */
     public MRUCache(int cacheSize, int expiryTime, RetrievalCallback<K, V> callback)
     {
         mruList = new LinkedList<>();
         lastUpdatedTimes = new HashMap<>();
         this.cacheSize = cacheSize;
         this.callbackInstance = callback;
         this.expiryTime = expiryTime;
     }
 
     /**
      * Retrieve an element from the cache. If a callback was defined in the cache
      * constructor, then this will be used to refresh
      * values in the cache if they are missing, or have expired.
      *
      * @param key key whose associated value is to be returned
      *
      * @return the value to which this map maps the specified key, or
      *   null if the map contains no mapping for this key.
      */
     @SuppressWarnings("unchecked")
 	@Override
     public synchronized V get(Object key)
     {
         return get((K) key, callbackInstance);
     }
 
     /**
      * Retrieves an element from the cache. The supplied callback will be used to
      * refresh the value in the cache if it is missing, or has expired. If the
      * requested element is missing and the callback is set to null, then
      * null is returned.
      *
      * @param key key whose associated value is to be returned
      * @param callback a callback used to populate the cache if necessary
      *
      * @return the value to which this map maps the specified key, or
      *   null if the map contains no mapping for this key.
      */
     public synchronized V get(K key, RetrievalCallback<K, V> callback)
     {
         long now = System.currentTimeMillis();
 
         if (!this.containsKey(key))
         {
             if (callback == null) {
                 return null;
             } else {
                 // cache is missing key; retrieve from callback and update access times
                 synchronized (this) {
                     if (cacheSize > 0 && mruList.size() >= cacheSize) {
                         this.remove(mruList.getLast());
                         mruList.removeLast();
                     }
 
                     super.put(key, callback.get(key));
                     lastUpdatedTimes.put(key, Long.valueOf(now));
                     mruList.addFirst(key);
                 }
             }
             
         } else {
             
             // cache contains key
             if (expiryTime > 0) {
                 
                 // expire this element if it's old
                 Long lastUpdatedTime = (Long) lastUpdatedTimes.get(key);
                 if (lastUpdatedTime==null) {
                 	logger.warn("MRUCache contains key '" + key + "' with no lastUpdatedTime set");
                 }
                 if (lastUpdatedTime == null || (lastUpdatedTime.longValue() + expiryTime < now)) {
                     synchronized (this) {
                         if (callback == null) {
                             // no callback, we just remove it
                             super.remove(key);
                             lastUpdatedTimes.remove(key);
                             mruList.remove(key);
 
                             return null;
                         } else {
                             super.put((K) key, callback.get((K) key));
                             lastUpdatedTimes.put(key, Long.valueOf(now));
                         }
                     }
                 }
             }
 
             // we have an element and it has been retrieved, move it to the
             // top of the mruList. (we may not necessarily want to do this;
             // this should be a constructor preference). There are pros & cons 
             // to this approach:
             // pros: if we just got an element, we probably don't want it expiring out
             //   of the cache
             // cons: this moves 'stale' objects to the top of the mruList
             //   stack; this means that when we remove elements from mruList
             //   to fit in more elements, we may be expiring older elements.
             // this should probably be a decision made by the developer, rather than
             // this code, but I'd like to keep the interface simple.
             if (!dynamicCaching) {
                 synchronized (this) {
                     mruList.remove(key);
                     mruList.addFirst(key);
                 }
             }
         }
 
         return super.get(key);
     }
 
     /**
      * Returns the object if it is in the cache and has not expired.
      * This method will return null if the the key is not in cache, or
      * if it is in the cache but has expired.
      *
      * @param key key whose associated value is to be returned
      *
      * @return the value to which this map maps the specified key, or
      *   null if the map contains no mapping for this key.
      */
     public synchronized Object getNoCallback(Object key) {
         if (!this.containsKey(key)) {
             return null;
         }
 
         if (expiryTime > 0) {
             if (((Long)lastUpdatedTimes.get(key)).longValue() + expiryTime < 
               System.currentTimeMillis()) 
             {
                 return null;
             }
         }
 
         return super.get(key);
     }
 
     /**
      * Add an element into the cache.
      *
      * @param key  key with which the specified value is to be associated.
      * @param value value to be associated with the specified key.
      * 
      * @return the previous value of this map entry, if one exists, otherwise null
      */
     @Override
     public synchronized V put(K key, V value) {
     	
         synchronized (this) {
 			V lastValue = super.put(key, value);
             lastUpdatedTimes.put(key, Long.valueOf(System.currentTimeMillis()));
             return lastValue;
         }
     }
     
     /** Enforces dynamic caching rules. When called, data will be expired from the time it 
      * is <i>entered</i> into the cache, rather than the time if is <i>fetched</i> from 
      * the cache. Suitable when we wish to apply a strict expiry time for 
      * dynamically-updating data, e.g. rowcounts.
      */
     public void setDynamicCaching() {
         dynamicCaching = true;
     }
 }