/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.facet.taxonomy;

import java.util.LinkedHashMap;
import java.util.Map;

LRUHashMap is an extension of Java's HashMap, which has a bounded size();
When it reaches that size, each time a new element is added, the least
recently used (LRU) entry is removed.
 Java makes it very easy to implement LRUHashMap - all its functionality is already available from LinkedHashMap, and we just need to configure that properly. 

Note that like HashMap, LRUHashMap is unsynchronized, and the user MUST
synchronize the access to it if used from several threads. Moreover, while
with HashMap this is only a concern if one of the threads is modifies the
map, with LURHashMap every read is a modification (because the LRU order
needs to be remembered) so proper synchronization is always necessary.

With the usual synchronization mechanisms available to the user, this
unfortunately means that LRUHashMap will probably perform sub-optimally under
heavy contention: while one thread uses the hash table (reads or writes), any
other thread will be blocked from using it - or even just starting to use it
(e.g., calculating the hash function). A more efficient approach would be not
to use LinkedHashMap at all, but rather to use a non-locking (as much as
possible) thread-safe solution, something along the lines of
java.util.concurrent.ConcurrentHashMap (though that particular class does not
support the additional LRU semantics, which will need to be added separately
using a concurrent linked list or additional storage of timestamps (in an
array or inside the entry objects), or whatever).
@lucene.experimental
/**
 * LRUHashMap is an extension of Java's HashMap, which has a bounded size();
 * When it reaches that size, each time a new element is added, the least
 * recently used (LRU) entry is removed.
 * <p>
 * Java makes it very easy to implement LRUHashMap - all its functionality is
 * already available from {@link java.util.LinkedHashMap}, and we just need to
 * configure that properly.
 * <p>
 * Note that like HashMap, LRUHashMap is unsynchronized, and the user MUST
 * synchronize the access to it if used from several threads. Moreover, while
 * with HashMap this is only a concern if one of the threads is modifies the
 * map, with LURHashMap every read is a modification (because the LRU order
 * needs to be remembered) so proper synchronization is always necessary.
 * <p>
 * With the usual synchronization mechanisms available to the user, this
 * unfortunately means that LRUHashMap will probably perform sub-optimally under
 * heavy contention: while one thread uses the hash table (reads or writes), any
 * other thread will be blocked from using it - or even just starting to use it
 * (e.g., calculating the hash function). A more efficient approach would be not
 * to use LinkedHashMap at all, but rather to use a non-locking (as much as
 * possible) thread-safe solution, something along the lines of
 * java.util.concurrent.ConcurrentHashMap (though that particular class does not
 * support the additional LRU semantics, which will need to be added separately
 * using a concurrent linked list or additional storage of timestamps (in an
 * array or inside the entry objects), or whatever).
 * 
 * @lucene.experimental
 */
public class LRUHashMap<K,V> extends LinkedHashMap<K,V> {

  private int maxSize;

  
Create a new hash map with a bounded size and with least recently
used entries removed.
Params:
maxSize – 
    the maximum size (in number of entries) to which the map can grow
    before the least recently used entries start being removed.
 Setting maxSize to a very large value, like Integer.MAX_VALUE is allowed, but is less efficient than using HashMap because our class needs to keep track of the use order (via an additional doubly-linked list) which is not used when the map's size is always below the maximum size./**
   * Create a new hash map with a bounded size and with least recently
   * used entries removed.
   * @param maxSize
   *     the maximum size (in number of entries) to which the map can grow
   *     before the least recently used entries start being removed.<BR>
   *      Setting maxSize to a very large value, like
   *      {@link Integer#MAX_VALUE} is allowed, but is less efficient than
   *      using {@link java.util.HashMap} because our class needs
   *      to keep track of the use order (via an additional doubly-linked
   *      list) which is not used when the map's size is always below the
   *      maximum size. 
   */
  public LRUHashMap(int maxSize) {
    super(16, 0.75f, true);
    this.maxSize = maxSize;
  }

  
Return the max size
/**
   * Return the max size
   */
  public int getMaxSize() {
    return maxSize;
  }

  
setMaxSize() allows changing the map's maximal number of elements
which was defined at construction time.

Note that if the map is already larger than maxSize, the current 
implementation does not shrink it (by removing the oldest elements);
Rather, the map remains in its current size as new elements are
added, and will only start shrinking (until settling again on the
give maxSize) if existing elements are explicitly deleted.  
/**
   * setMaxSize() allows changing the map's maximal number of elements
   * which was defined at construction time.
   * <P>
   * Note that if the map is already larger than maxSize, the current 
   * implementation does not shrink it (by removing the oldest elements);
   * Rather, the map remains in its current size as new elements are
   * added, and will only start shrinking (until settling again on the
   * give maxSize) if existing elements are explicitly deleted.  
   */
  public void setMaxSize(int maxSize) {
    this.maxSize = maxSize;
  }

  // We override LinkedHashMap's removeEldestEntry() method. This method
  // is called every time a new entry is added, and if we return true
  // here, the eldest element will be deleted automatically. In our case,
  // we return true if the size of the map grew beyond our limit - ignoring
  // what is that eldest element that we'll be deleting.
  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > maxSize;
  }

  @SuppressWarnings("unchecked")
  @Override
  public LRUHashMap<K,V> clone() {
    return (LRUHashMap<K,V>) super.clone();
  }
  
}