package nxm.sys.lib;

import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.WeakHashMap;
import java.util.concurrent.ConcurrentHashMap;

import nxm.sys.inc.InternalUseOnly;

/** A size-constrained cache. Available cache types based on how they choose which element to
    discard on a cache overflow:
    <pre>
      LRU  - A typical cache where the "Least Recently Used" item is discarded. this is <b>not thread-safe</b>.
      SLRU - A synchronized (thread-safe) version of the LRU cache.
      AUTO - A version that limit cache size using internal algorithm (automatic)
              that should perform the best in most cases but is <b>not thread-safe</b>. (Since NeXtMidas 3.5.0).
      SAUTO - A synchronized (thread-safe) version that limit cache size using internal algorithm (automatic)
              that should perform the best in most cases. (Default cache type) (Since NeXtMidas 3.5.0).
    </pre>
    Note that unlike most other caches this one can be set up to automatically discard stale entries
    (this is done by setting <code>maxAge</code> to a non-zero value). A typical use of this feature
    is one where the underlying data may change over time but it would be acceptable to use the old
    data for a pre-determined time span. The NeXtMidas Map Server uses this feature with a maximum
    age of one hour to ensure that clients will be receiving updated information within the next
    hour. While immediately updated data is ideal, the high cost of recomputing forces a compromise
    in this situation. <br>
    <br>
    Typical usage is as follows:
    <pre>
      private Cache cache = new Cache(16);

      public Object computeValue(String key) {
        Object value = cache.get(key);

        if (value == null) {
          value = ...
          cache.put(key, value); // Update the cache
        }

        return value;
      }
    </pre>
    <h2><a href="#VictimCache">Victim Cache</a></h2>
    Since NeXtMidas 2.5.0, {@link Cache} has been extended to make use of a "victim cache." When the
    normal cache is full (e.g. the LRU cache) and needs to discard an entry it places it in the
    victim cache. The victim cache holds the "recently killed" entries that fell out of the normal
    cache. A {@link #get(String)} first looks in the cache for the given key, if it is not there it
    looks in the victim cache. If the key is found in the victim cache, it is pulled back into the
    normal cache and then again available for use.<br>
    <br>
    The victim cache has no set size, rather it is implemented using weak references (see
    {@link WeakHashMap}) to keep references to objects until they get garbage collected. The
    Java VM guarantees that all objects held only by a weak reference will be garbage collected
    before an {@link OutOfMemoryError} is thrown. In effect, the victim cache holds on to items
    for as long as there is memory available to do so (note that <code>-server</code> mode and
    <code>-client</code> mode for the Java VM use different algorithms when determining this, see
    <a href="http://weblogs.java.net/blog/enicholas/archive/2006/05/understanding_w.html">
    http://weblogs.java.net/blog/enicholas/archive/2006/05/understanding_w.html</a> for more
    discussion on the use of weak references). <br>
    <br>
    The victim cache improves performance (i.e. more things cached) without using any "extra"
    memory. However, this requires turning control over to the garbage collector and allowing
    it to remove items from the victim cache as needed.

    @author  J. Czechowski IV
    @since   NeXtMidas 2.1.1
 */
public final class Cache {
  /** The types of caches available. */
  public static final String cacheTypeList = "LRU,SLRU,_RESERVED_SLOT3_,AUTO,SAUTO";

  /** A non thread-safe Least Recently Used (LRU) cache. */
  public static final int LRU = 1;
  /** A thread-safe / synchronized LRU cache. */
  public static final int SLRU = 2;
  /** A thread-safe / synchronized LRU cache. */
  static final int OLD_SLRU_CONST_VALUE = 3; // reserved for binary backwards compatibility with classes files built with NeXtMidas 3.4.x and prior, remove this in 3.9+
  /** A non thread-safe limited size cache using (automatic) internal algorithm which should perform the best in most cases. Since NeXtMidas 3.5.0. */
  public static final int AUTO = 4;
  /** a thread-safe limited size cache using (automatic) internal algorithm which should perform the best in most cases. Since NeXtMidas 3.5.0. */
  public static final int SAUTO = 5;

  /** Minimum cache size (value={@value}). */
  public static final int MIN_SIZE = 1;

  /** Age limit constant indicating there is no age limit (i.e. no time limit). */
  public static final double NO_AGE_LIMIT = 0.0;

  private CacheType cache       = null;     // The actual cache implementation.
  private Map<String,TimeStampedValue> vCache  = null; // The "victim" cache.
  private int       maxSize     = MIN_SIZE; // Maximum number of entries.
  private double    maxAge      = 0.0;      // Max age of an entry in the cache (0.0=Infinite).
  private long      statsPut    = 0L;       // Stats: Cache puts.
  private long      statsGet    = 0L;       // Stats: Cache gets.
  private long      statsRemove = 0L;       // Stats: Cache removes.
  private long      statsClear  = 0L;       // Stats: Cache clears.
  private long      statsHits   = 0L;       // Stats: Cache hits.
  private long      statsVHits  = 0L;       // Stats: Cache hits (victim cache).
  private long      statsExp    = 0L;       // Stats: Cache entries dropped due to expiration.
  private long      statsFull   = 0L;       // Stats: Cache entries dropped due overflow.

  /** Creates a new instance of the default type ({@link #SAUTO} with no time limit.
      @param maxSize The max number of entries (should be larger than 16).
   */
  public Cache(int maxSize) {
//  this("LRU", maxSize, 0.0);  // prior to 3.0.4, 3.2.3, 3.4.1, and 3.5.0
//  this("SLRU", maxSize, 0.0); // 3.0.4, 3.2.3, and 3.4.1 defaults to "SLRU" for BUG 2794
    this(SAUTO, maxSize, NO_AGE_LIMIT); // since 3.5.0 default to SAUTO for BUG 2794
  }

  /** Creates a new instance with no time limit.
      @param type    The cache type (see {@link #cacheTypeList}).
      @param maxSize The max number of entries (should be larger than 16).
   */
  public Cache(String type, int maxSize) {
    this(type, maxSize, NO_AGE_LIMIT);
  }

  /** Creates a new instance with no time limit.
      @param type    The cache type (see {@link #cacheTypeList}).
      @param maxSize The max number of entries (should be larger than 16).
      @since NeXtMidas 3.5.0
   */
  public Cache(int type, int maxSize) {
    this(type, maxSize, NO_AGE_LIMIT);
  }

  /** Creates a new instance.
      @param type    The cache type (see {@link #cacheTypeList}).
      @param maxSize The max number of entries (should be larger than 16).
      @param maxAge  The maximum lifespan of an entry in the cache, in seconds (0.0=infinite).
   */
  public Cache(String type, int maxSize, double maxAge) {
    this(Parser.find(cacheTypeList, type, -1), maxSize, maxAge);
  }

  /** Creates a new instance.
      @param type    The cache type (see {@link #cacheTypeList}).
      @param maxSize The max number of entries (should be larger than 16).
      @param maxAge  The maximum lifespan of an entry in the cache, in seconds (0.0=infinite).
   */
  public Cache(int type, int maxSize, double maxAge) {
    this(type,maxSize,maxAge,null);
  }

  /** DO NOT USE THIS CONSTRUCTOR. This constructor is being used on an experimental basis by
      <code>LayerMap</code> and may be removed before the next release.
      @param type the cache type.
      @param size the max cache size.
      @param age  the max cache age.
      @param vc   the victim cache.
   */
  @InternalUseOnly
  public Cache(int type, int size, double age, WeakHashMap<String,TimeStampedValue> vc) {
    // this.vCache = (vc != null)? vc : new WeakHashMap<String,TimeStampedValue>(); // prior to 3.5.0
    if (vc == null) {
      vc = new WeakHashMap<>();
    }
    if (type == LRU || type == AUTO) { // for non thread-safe cache types
      this.vCache = vc;                //   use non thread-safe victim cache for best performance
    } else {                           // for thread-safe cache types, use thread-safe wrapper over victim cache
      this.vCache = Collections.synchronizedMap(vc); // Since 3.5.0: to be thread-safe for BUG 2794
    }

    switch (type) {
      case LRU:  cache = new LRU();  break;
      case SLRU: cache = new SLRU(); break;
      case OLD_SLRU_CONST_VALUE: cache = new SLRU(); break; // <-- temporary slot for backward compatibility with class files built with NeXtMidas prior to 3.5.0, remove in 3.7.0
      case AUTO:  cache = new HashMapCache();           break; // since 3.5.0
      case SAUTO: cache = new ConcurrentHashMapCache(); break; // since 3.5.0
      default:   throw new MidasException("Cache: Invalid cache type '"+type+"'.");
    }
    setMaxSize(size);
    setMaxAge(age);
  }

  /** Gets the cache type as an int.
      @return The cache type (see {@link #cacheTypeList}).
      @see #getCacheTypeName()
   */
  public int getCacheType () { return cache.cacheType(); }

  /** Gets the cache type as a string.
      @return The cache type (see {@link #cacheTypeList}).
      @see #getCacheType()
   */
  public String getCacheTypeName () { return Parser.get(cacheTypeList, getCacheType()); }

  /** Gets an element from the cache. Calling this method DOES NOT count as a "use" of the cached
      value (will not update time/frequency of use) but it may trigger a removal if the requested
      element is expired.
      <br>
      Note that a <code>get(k)</code> immediately following a successful <code>peek(k)</code> is
      NOT guaranteed to be successful. For example:
      <pre>
        Cache cache;
        ...
        if (cache.peek(k) != null) {
          Object obj = cache.get(k); // This may return null
          ...;
        }
      </pre>
      The <code>get(k)</code> in the above example may return <code>null</code> even if (1)
      <code>peek(k)</code> was non-null and (2) no other thread has access to <code>cache</code>.
      Below are a few reasons why this may take place:
      <pre>
        (1) The value may have expired between the peek(k) and the get(k)
        (2) The peek(k) may have found something in the <a href="#VictimCache">Victim Cache</a>
            that was subsequently removed by the garbage collector.
      </pre>
      @param key The key to look up.
      @return The matching object or null if not found.
   */
  public Object peek (String key) {
    return getFromVCache(key,true);
  }

  /** Gets an element from the cache. This is similar to {@link #peek(String)}, except that it has
      an option to disable checking the victim cache. This method is rarely used (other than testing)
      since the {@link #peek(String)} method is faster and more likely to find a match.
      @param key The key to look up.
      @param vc  Include the "victim cache" when looking?
      @return The matching object or null if not found.
      @since NeXtMidas 2.5.0
   */
  public Object peek (String key, boolean vc) {
    return (vc)? getFromVCache(key,true) : getFromCache(key,true);
  }

  /** Gets an element from the cache. Calling this method counts as a cache-access.
      @param key The key to look up.
      @return The matching object or null if not found.
   */
  public Object get (String key) {
    Object val = getFromCache(key,false);
    return (val != null)? val : getFromVCache(key,false);
  }

  /** Gets an element from the cache. Calling this method counts as a cache-access.This is similar
      to {@link #get(String)}, except that it has an option to disable checking the victim cache.
      This method is rarely used (other than testing) since the {@link #get(String)} method is
      faster and more likely to find a match.
      @param key The key to look up.
      @param vc  Include the "victim cache" when looking?
      @return The matching object or null if not found.
      @since NeXtMidas 2.5.0
   */
  public Object get (String key, boolean vc) {
    Object val = getFromCache(key,false);
    return ((val != null) || !vc)? val : getFromVCache(key,false);
  }

  /** Gets an element from the cache and victim cache. Calling this method counts as a cache-access.
      This returns the object removed for similarity to the {@link Map} interface. The return value
      of this method is rarely useful (hence there is no <code>remove(String,boolean)</code> method).
      @param key The key to remove.
      @return The object removed from the cache or null if not found in the cache or victim cache.
   */
  public Object remove (String key) {
    Object val = getFromCache(key,true);
    if (val == null) {
      val = getFromVCache(key,true);
    } else {
      statsRemove++;
    }
    cache.cacheRemove(key);
    vCache.remove(key);
    return val;
  }

  /** Clears the cache. */
  public void clear() {
    vCache.clear();
    cache.cacheClear();
    statsClear++;
  }

  /** Puts an element into the cache.
      @param key The key to insert.
      @param val The value to insert.
   */
  public void put(String key, Object val) {
    TimeStampedValue tsv = new TimeStampedValue(val);
    vCache.put(key, tsv);
    cache.cachePut(key, tsv);
    statsPut++;
  }

  /** Returns a description of the object useful for debugging. */
  public String toString() {
    return "Cache: " + getStats();
  }

  /** Returns statistics about the performance of this cache.
      WARNING: The entries in this table are subject to change without notice!!!

      @return a {@link Table} of statistics about the performance of this cache.
   */
  @InternalUseOnly
  public Table getStats() {
    Table tbl = new Table();

    tbl.put("TYPE",                    getCacheTypeName());
    tbl.put("MAX_SIZE",                getMaxSize());
    tbl.put("MAX_AGE",                 getMaxAge());
    tbl.put("TOTAL_PUTS",              statsPut);
    tbl.put("TOTAL_GETS",              statsGet);
    tbl.put("TOTAL_REMOVES",           statsRemove);
    tbl.put("TOTAL_CLEARS",            statsClear);
    tbl.put("TOTAL_HITS",              statsHits);
    tbl.put("TOTAL_CAPACITY_DROPS",    statsFull);
    tbl.put("TOTAL_EXPIRATION_DROPS",  statsExp);
    tbl.put("TOTAL_VICTIM_CACHE_HITS", statsVHits);

    return tbl;
  }

  /** Sets the maximum number of elements in the lookup table.
      @param size The max number of entries (should be larger than {@link #MIN_SIZE}).
      @since NeXtMidas 2.5.0
   */
  public synchronized void setMaxSize (int size) {
    if (size < MIN_SIZE) {
      Shell.getSharedMidasContext().warning("Cache size of "+size+" is too small using "+MIN_SIZE+".");
      size = MIN_SIZE;
    }
    if (maxSize != size) {
      maxSize = size;
      cache.cacheCleanup();
    }
  }

  /** Gets the maximum number of elements in the cache table.
      @return The maximum size of the normal cache (does not include the victim cache).
   */
  public int getMaxSize () { return maxSize; }

  /** Sets the maximum age of an element in the lookup table.
      @param age The maximum lifespan of an entry in the cache (in seconds) or {@link #NO_AGE_LIMIT}
                 to disable age checking.
      @since NeXtMidas 2.5.0
   */
  public synchronized void setMaxAge (double age) {
    if (age < 0.0) {
      Shell.getSharedMidasContext().warning("Invalid maxAge of "+age+" for cache using NO_AGE_LIMIT.");
      age = NO_AGE_LIMIT;
    }
    if (maxAge != age) {
      maxAge = age;
      cache.cacheCleanup();
    }
  }

  /** Gets the maximum age of an element in the lookup table.
      @return The maximum lifespan of an entry in the cache (in seconds) or {@link #NO_AGE_LIMIT}
              if age checking is disabled.
   */
  public double getMaxAge () { return maxAge; }

  /** Gets a value from the cache. */
  private Object getFromCache (String key, boolean peek) {
    TimeStampedValue tsv = (peek)? cache.cachePeek(key) : cache.cacheGet(key);
    Object           val = null;

    if (!peek) statsGet++;

    if (tsv != null) {
      if (!peek) statsHits++;
      if (tsv.isExpired()) {
        cache.cacheRemove(key);
        statsExp++;
      } else {
        val = tsv.getValue();
      }
    }
    return val;
  }

  /** Gets a value from the victim cache. */
  private Object getFromVCache (String key, boolean peek) {
    TimeStampedValue tsv = vCache.get(key);
    Object           val = null;

    if (tsv != null) {
      if (tsv.isExpired()) {
        vCache.remove(key);
      } else {
        val = tsv.getValue();
        if (!peek) {
          cache.cachePut(key,tsv);
          statsVHits++;
        }
      }
    }
    return val;
  }

  /** Get actual size of internal map / structure.
      @return actual size of internal map
      @since NeXtMidas 3.5.0
   */
  @InternalUseOnly("since created")
  public synchronized int size () { // public since 3.6.0
    return cache.size();
  }

  //////////////////////////////////////////////////////////////////////////////////////////////////
  // Nested classes
  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A time stamped cache value. */
  @InternalUseOnly
  public class TimeStampedValue {
    private final Object value;     // The value.
    private final double time;      // The time stamp.

    /** Constructor of TimeStampValue that uses current time
     *
     *  @param value value
     */
    public TimeStampedValue(Object value) {
      this(value, Time.current());
    }

    /** Constructor of TimeStampValue
     *
     *  @param value value
     *  @param time  time as double
     */
    public TimeStampedValue(Object value, double time) {
      this.value = value;
      this.time  = time;
    }
    /** Gets the value. */
    private Object getValue() { return value; }
    /** Gets the time stamp. */
    private double getTime() { return time; }
    /** Gets the time stamp. */
    private boolean isExpired() { return (maxAge <= 0.0)? false: ((time+maxAge) < Time.current()); }
  }

  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A generic cache interface. */
  private interface CacheType {
    /** Gets the cache type. */
    public int cacheType();
    /** Gets an element from the cache. Calling this method DOES NOT count as a cache-access. */
    public TimeStampedValue cachePeek(String key);
    /** Gets an element from the cache. Calling this method counts as a cache-access. */
    public TimeStampedValue cacheGet(String key);
    /** Puts an element into the cache. */
    public void cachePut(String key, TimeStampedValue val);
    /** Removes an element from the cache returning it. */
    public TimeStampedValue cacheRemove(String key);
    /** Clears the cache. */
    public void cacheClear();
    /** Cleans up the cache by deleting expired entries and discarding any "extra" entries. */
    public void cacheCleanup();
    /** get size of internal cache structure. Since NeXtMidas 3.5.0. */
    @InternalUseOnly
    int size();
  }

  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A non thread-safe LRU cache, based the Sun documentation for {@link LinkedHashMap}. */
  @InternalUseOnly
  private class LRU extends LinkedHashMap<String,TimeStampedValue> implements CacheType {
    /** NOTE: this should be changed if the structure/fields of this class changes. */
    private static final long serialVersionUID = 2012012200311L; // for Serializable interface

    /** Creates a new instance */
    public LRU() {
      // since 3.5.0: +1 on initial capacity AND use load factor of 1.0 to prevent resizing of Map,
      //              since we are limited this Map to maxSize (see removeEldestEntry method) for Bug 2794
      super(Math.max(maxSize,16) + 1, 1.0f, true);
    }

    public int              cacheType ()             { return LRU;                           }
    public TimeStampedValue cacheGet (String key)    { return get(key);    }
    public TimeStampedValue cacheRemove (String key) { return remove(key); }
    public String           toString ()              { return "LRU";                         }
    public void             cacheClear ()            { clear();                              }

    public void cachePut (String key, TimeStampedValue val) {
      put(key, val);
    }

    public TimeStampedValue cachePeek (String key) {
      // JC4: Can not use get(key) since it would modify cache.
      TimeStampedValue val = null;

      if (containsKey(key)) {
        Iterator<Entry<String, TimeStampedValue>> iter = entrySet().iterator();

        while (iter.hasNext() && (val == null)) {
          Map.Entry<String, TimeStampedValue> entry = iter.next();
          if (entry.getKey().equals(key)) {
            val = entry.getValue();
          }
        }
      }
      return val;
    }

    public void cacheCleanup() {
      Iterator<Entry<String, TimeStampedValue>> iter;

      if ((maxAge != NO_AGE_LIMIT) || (size() > maxSize)) {
        // Remove expired entries
        iter = entrySet().iterator();
        while (iter.hasNext()) {
          TimeStampedValue tsv = iter.next().getValue();

          if (tsv.isExpired()) {
            remove(tsv);
            statsExp++;
          }
        }

        // Remove extra entries
        int toRemove = size() - maxSize;

        if (toRemove > 0) {
          iter = entrySet().iterator();
          while (iter.hasNext() && (toRemove > 0)) {
            remove(iter.next());
            statsRemove++;
            toRemove--;
          }
        }
      }
    }

    /** overriding this method to limit the size of this LinkedHashMap to maxSize. */
    protected boolean removeEldestEntry(Map.Entry<String,TimeStampedValue> eldest) {
      boolean remove = false;

      if (maxAge == NO_AGE_LIMIT) {
        remove = (size() > maxSize); // No expiration, just remove if full.
      } else {
        if (eldest.getValue().isExpired()) { // Always remove if expired
          remove = true;
        } else if (size() <= maxSize) {                          // Not full, just return false
          remove = false;
        } else {                                                 // Remove any expired entries first
          remove = true; // Default to true.

          Iterator<Entry<String, TimeStampedValue>> iter = entrySet().iterator();
          while (iter.hasNext()) {
            TimeStampedValue tsv = iter.next().getValue();

            if (tsv.isExpired()) {
              remove(tsv);
              statsExp++;
              remove = false; // If modified this method MUST return false (see LinkedHashMap)
            }
          }
        }
      }

      if (remove) { statsFull++; }

      return remove;
    }
  } // end class LRU Cache

  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A thread-safe / synchronized version of the LRU cache. */
  @InternalUseOnly
  private class SLRU extends LRU {
    /** NOTE: this should be changed if the structure/fields of this class changes. */
    private static final long serialVersionUID = 2012012300311L; // for Serializable interface

    public int cacheType() { return SLRU; }
    public String toString() { return "SLRU"; }

    public synchronized void cachePut(String key, TimeStampedValue val) { super.cachePut(key, val); }
    public synchronized void cacheClear() { super.cacheClear(); }
    public synchronized void cacheCleanup() { super.cacheCleanup(); }
    public synchronized TimeStampedValue cacheGet(String key)    { return super.cacheGet(key);    }
    public synchronized TimeStampedValue cacheRemove(String key) { return super.cacheRemove(key); }
    public synchronized TimeStampedValue cachePeek(String key)   { return super.cachePeek(key);   }
    protected synchronized boolean removeEldestEntry(Map.Entry<String,TimeStampedValue> eldest) {
      return super.removeEldestEntry(eldest);
    }
  } // end class SLRU Cache

  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A non thread-safe cache that performs well in most single threaded scenarios.
      This uses a HashMap which generally performs better than LRU in most single-threaded scenarios.
      This implementation DOES NOT look at the TimeStampedValue for limiting size of this cache in cachePut(..)
      for best performance.
      @author Neon Ngo
      @since NeXtMidas 3.5.0
   */
  @InternalUseOnly
  private class HashMapCache extends HashMap<String,TimeStampedValue> implements CacheType {
    /** NOTE: this should be changed if the structure/fields of this class changes. */
    private static final long serialVersionUID = 2013100700350L; // for Serializable interface

    public HashMapCache () {
      // +1 on initial capacity AND use load factor of 1.0 to prevent resizing of Map,
      // since we are limiting this Map to maxSize
      super(Math.max(maxSize,16) + 1, 1.0f);
    }
    public int              cacheType ()             { return AUTO;        }
    public String           toString ()              { return "AUTO";     }
    public TimeStampedValue cacheGet (String key)    { return get(key);    }
    public TimeStampedValue cacheRemove (String key) { return remove(key); }
    public TimeStampedValue cachePeek (String key)   { return get(key);    }
    public void             cacheClear ()            { clear();            }

    public void cachePut (String key, TimeStampedValue val) {
      put(key, val);

      if (size() > maxSize) { // limit size, remove first key/value in Map that is not the current key
        Iterator<String> keyIter = keySet().iterator();
        for (int ii=0; ii<5 && keyIter.hasNext(); ii++) { // loop up to 4 times
          String aKey = keyIter.next();
          if (!aKey.equals(key)) { // remove first non-matching key
            keyIter.remove();
            statsRemove++;
            break;
          }
        } // end while loop
      }
    }

    public void cacheCleanup() {
      Iterator<Entry<String, TimeStampedValue>> iter;

      if ((maxAge != NO_AGE_LIMIT) || (size() > maxSize)) {
        // Remove expired entries
        for (Entry<String, TimeStampedValue> entry : entrySet()) {
          TimeStampedValue tsv = entry.getValue();
          if (tsv.isExpired()) {
            remove(tsv);
          }
        }

        // Remove extra entries
        int toRemove = size() - maxSize;

        if (toRemove > 0) {
          iter = entrySet().iterator();
          while (iter.hasNext() && (toRemove > 0)) {
            iter.remove();
            statsRemove++;
            toRemove--;
          }
        }
      }

    }
  } // end class HashMapCache

  //////////////////////////////////////////////////////////////////////////////////////////////////
  /** A thread-safe cache that performs well in most multi-threaded scenarios.
      This uses a ConcurrentHashMap which generally performs better than SLRU in most multi-threaded scenarios.
      This implementation DOES NOT look at the TimeStampedValue for limiting size of this cache in cachePut(..) for best performance.
      @author Neon Ngo
      @since NeXtMidas 3.5.0
   */
  @InternalUseOnly
  private class ConcurrentHashMapCache extends ConcurrentHashMap<String,TimeStampedValue> implements CacheType {
    /** NOTE: this should be changed if the structure/fields of this class changes. */
    private static final long serialVersionUID = 2013100700350L; // for Serializable interface

    public ConcurrentHashMapCache () {
      // +1 on initial capacity AND use load factor of 1.0 to prevent resizing of Map,
      // since we are limiting this Map to maxSize
      super(Math.max(maxSize,16) + 1, 1.0f);
    }
    public int              cacheType ()             { return SAUTO;       }
    public String           toString ()              { return "SAUTO";     }
    public TimeStampedValue cacheGet (String key)    { return get(key);    }
    public TimeStampedValue cacheRemove (String key) { return remove(key); }
    public TimeStampedValue cachePeek (String key)   { return get(key);    }
    public void             cacheClear ()            { clear();            }

    public void cachePut (String key, TimeStampedValue val) {
      put(key, val);

      if (size() > maxSize) { // limit size, remove first key/value in Map that is not the current key
        // NOTE: when building against JDK 8: keySet() returns ConcurrentHashMap.KeySetView (Java 1.8 API)
        // which causes java.lang.NoSuchMethodError Cache$ConcurrentHashMapCache.keySet()Ljava/util/concurrent/ConcurrentHashMap$KeySetView;
        // when running under Java 6 or Java 7, even when java class targets lower version
        // hence, as of nxm360 we are using entrySet() instead (although, if a future Java 8 or Java 9
        //   changes entrySet() to return a Java 8+ API, then we still have the same issue...)
        Set<java.util.Map.Entry<String, TimeStampedValue>> set = entrySet();
        Iterator<java.util.Map.Entry<String, TimeStampedValue>> iter = set.iterator();
        for (int ii=0; ii<5 && iter.hasNext(); ii++) { // loop up to 4 times
          java.util.Map.Entry<String, TimeStampedValue> entry = iter.next();
          String aKey = entry.getKey();
          if (!aKey.equals(key)) { // remove first non-matching key
            iter.remove();
            statsRemove++;
            break;
          }
        } // end while loop
      }
    }

    public void cacheCleanup() {
      Iterator<Entry<String, TimeStampedValue>> iter;

      if ((maxAge != NO_AGE_LIMIT) || (size() > maxSize)) {
        // Remove expired entries
        for (Entry<String, TimeStampedValue> entry : entrySet()) {
          TimeStampedValue tsv = entry.getValue();
          if (tsv.isExpired()) {
            remove(tsv);
          }
        }

        // Remove extra entries
        int toRemove = size() - maxSize;

        if (toRemove > 0) {
          iter = entrySet().iterator();
          while (iter.hasNext() && (toRemove > 0)) {
            iter.remove();
            statsRemove++;
            toRemove--;
          }
        }
      }
    }
  } // end class ConcurrentHashMapCache

}
