package Torello.Java.Additional;

import java.util.*;

import java.util.function.BiConsumer;

/**
 * A great class, heavily used by the Java Doc Upgrader Tool, that extends Java's
 * <CODE>TreeMap</CODE> class to eliminate "Least Recently Used" elements from the 
 * Map, <I>effectively creating an <CODE>'in-memory cache'</CODE> for the tool.</I>
 * 
 * <EMBED CLASS='external-html' DATA-FILE-ID=LRUTREEMAP>
 * 
 * @param <K> This is the type for the map {@code 'key'}.  It should be thought of as
 * identical to the {@code java.util.TreeMap} type-parameter {@code 'K'}
 * 
 * @param <V> This is the type used by the map for {@code 'value'}.  It should be thought of as
 * identical to the {@code java.util.TreeMap} type-parameter {@code 'V'}
 */
public class LRUTreeMap<K, V> extends TreeMap<K, V>
{
    /** <EMBED CLASS='external-html' DATA-FILE-ID=SVUID> */
    protected static final long serialVersionUID = 1;

    // ********************************************************************************************
    // ********************************************************************************************
    // INHERITED FROM: java.util.TreeMap - THESE WORK JUST-FINE, NO @Override NEEDED
    // ********************************************************************************************
    // ********************************************************************************************


    // public int size()

    // public Comparator<? super K> comparator()

    // public Set<K> keySet();

    // public NavigableSet<K> navigableKeySet()

    // public NavigableSet<K> descendingKeySet()

    // public Collection<V> values()

    // public Set<Map.Entry<K,V>> entrySet()

    // public NavigableMap<K,V> descendingMap()

    // public NavigableMap<K,V> subMap
    //   (K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

    // public NavigableMap<K,V> headMap(K toKey, boolean inclusive)

    // public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)

    // public SortedMap<K,V> subMap(K fromKey, K toKey)

    // public SortedMap<K,V> headMap(K toKey)

    // public SortedMap<K,V> tailMap(K fromKey)

    // public void replaceAll(BiFunction<? super K,? super V,? extends V> function)
    

    // ********************************************************************************************
    // ********************************************************************************************
    // LRUTreeMaps "Helper Class" - Keeps Track of each Tree-Node's "Place In Line"
    // ********************************************************************************************
    // ********************************************************************************************


    // This just keeps track of which Key-Value Pairs are the Least-Recently-Used (and of course)
    // The Most-Recently-Used
    private final class LRUTreeMaps
    {
        // Each TreeMap has TWO INTERNAL "Place In Line" TreeMap's
        // 
        // NOTE-ABOUT-EFFICIENCY: This class was developed for use with the EmbedTag's of the
        // "Java Doc Upgrader" package.  These two additional TreeMap's do not create additional
        // keys, just references to keys.  Furthermore, even if a "Reference to Key" was a real
        // memory-hog (which it isn't, a 'refernce' is just a 'long'), the Key's themselves are
        // all 8-character String's
        //
        // The values in this map are 1,000 - 2,000 node long html-page vectors.  These can be
        // quite memory-intensive.  Holding more than 500 of them might slow Java down to an
        // "unusable state".  In any case, only the "Keys" are saved multiple times (not the
        // web-pages, and furthermore, only a **REFERENCE** to the keys are saved multiple times)

        // A TreeMap that can be queried using the "Key" (the same "Key") that the real OUTER
        // "Real" TreeMap is using.  This is just a "Mirror"   We need this because the OUTER
        // tree map is pruned when it grows larger than MAX_NUM_ELEMENTS.
        private final TreeMap<K, Integer> keyToPlaceInLine = new TreeMap<>();
        private final TreeMap<Integer, K> placeInLineToKey = new TreeMap<>();

        // The "Place In Line" is just the value in this counterLRU.  This counter is incremented
        // every single time that it is assigned to a key-value pair.
        private int counterLRU = 0;

        final void added(K key)
        {
            Integer possiblyNullPreviousPlaceInLine = keyToPlaceInLine.put(key, counterLRU);
            placeInLineToKey.put(counterLRU, key);
            counterLRU++;

            if (possiblyNullPreviousPlaceInLine != null)
                placeInLineToKey.remove(possiblyNullPreviousPlaceInLine);

            // NOTE: .size() is an OUTER TREE-MAP METHOD-REFERENCE
            else if (size() > MAX_NUM_ELEMENTS)
            {
                // This is difficult to read.
                //
                // 1) 'pollFirstEntry' removes *AND* returns the key/place-in-line combo from the
                //    first of the two Queue-Information TreeMap's
                // 2) Therefore: 'beingRemoved' has the 'key' (saved as the value), and the
                //    'place-in-line' saved as the key.  This needs to be removed from the second
                //    of the two Queue-Information TreeMap's

                Map.Entry<Integer, K>   beingRemoved    = placeInLineToKey.pollFirstEntry();
                K                       keyBeingRemoved = beingRemoved.getValue();

                // 'placeInLineToKey' has had this 'key' removed, *NOW* (here) the
                // 'keyToPlaceInLine' will be purged of this key.

                keyToPlaceInLine.remove(keyBeingRemoved);

                // Make a call to the **OUTER-CLASS*, We just eliminated the "Place In Line"
                // Queue-TreeMap's (of which there are TWO).  The last thing is to remove the
                // key-value from the actual (Main) TreeMap - the one the user has.
                //
                // THIS MEAS: if we call the usual (outer-class) 'remove' method, it would remove
                //            the key from the main TreeMap - AND THEN try to remove the
                //            'place-in-line' information AGAIN!  (What was just done in the
                //            previous lines)
                //
                // INSTEAD:   a method "removeINTERNAL" is being built.

                // System.out.println("Removig [" + keyBeingRemoved + "] from LRUTreeMap");

                removeINTERNAL(keyBeingRemoved);
            }
        }

        final void removed(K key)
        { placeInLineToKey.remove(keyToPlaceInLine.remove(key)); }

        final void changed(K key)
        {
            // System.out.println("Changed: " + key);
            Integer previousPlaceInLine = keyToPlaceInLine.put(key, counterLRU);

            placeInLineToKey.remove(previousPlaceInLine);
            placeInLineToKey.put(counterLRU, key);

            counterLRU++;
        }

        final void clear()
        {
            placeInLineToKey.clear();
            keyToPlaceInLine.clear();
        }

        final int trimToFit()
        {
            int numExtra = size() - MAX_NUM_ELEMENTS;
    
            if (numExtra <= 0) return 0;

            // If you read it - 'descendingMap' is sort-of *LINKED* to the map from which it
            // originated.  When you remove something from the descending map, you also remove
            // from the original map from which it was created.

            NavigableMap<Integer, K> entriesToRemove = placeInLineToKey.descendingMap();

            while (numExtra-- > 0)
                keyToPlaceInLine.remove(entriesToRemove.pollFirstEntry().getValue());

            // This is how many elements were removed
            return numExtra;
        }
    }


    // ********************************************************************************************
    // ********************************************************************************************
    // LRUTreeMap: This class extends "TreeMap" - **AND** These are the methods being added
    // ********************************************************************************************
    // ********************************************************************************************


    // This one is only used above, once.
    private void removeINTERNAL(Object key) { super.remove(key); }

    /**
     * Keeps a record of the <I>'Ordering of Use'</I> for the elements in {@code 'this'} map.  The
     * values stored here are set by a counter that increases with each use.
     */
    protected LRUTreeMaps mapLRU = new LRUTreeMaps();

    /**
     * This is, literally, the maximum number of Key-Value pairs allowed into this instance of
     * {@code LRUTreeMap}.  When an insert or {@code 'put'} operation is made after the tree has
     * reached this maximum size, it will remove the oldest element in the tree, first, before
     * inserting the new addition(s)j.
     */
    protected int MAX_NUM_ELEMENTS;

    /**
     * This merely retrieves the value stored in {@link #MAX_NUM_ELEMENTS}.
     * 
     * @return The maximum number of elements allowed in this tree before it begins discarding
     * Key-Value Pairs.
     */
    public int getMaxNumElements() { return this.MAX_NUM_ELEMENTS; }

    /**
     * Sets a new value for the maximum number of elements allowed into this tree.  If this number
     * is smaller than the current size of the tree, then the oldest elements will be removed until
     * the tree has a {@code size()} smaller than the value of {@code 'maxNumElements'}
     * 
     * @param maxNumElements This is thee new maximum allowable size for this {@code LRUTreeMap}
     * instance.
     * 
     * @return The number of elements that had to be removed from this tree in order to adhere to
     * this new size-specifier.  {@code '0'} is returned if no elements were removed.
     * 
     * @throws IllegalArgumentException The value provided to {@code 'maxNumElements'} must be
     * at least {@code '3'}, or this exception throws.
     */
    public int setMaxNumElements(int maxNumElements)
    {
        CHECK_MAX_NUM_ELEMENTS(maxNumElements);

        this.MAX_NUM_ELEMENTS = maxNumElements;

        // No elements need to be removed from the tree.
        if (this.size() <= maxNumElements) return 0;

        // Returns how many elements were removed.
        return mapLRU.trimToFit();
    }

    private void CHECK_NEW_MAP_SIZE(int mapSize)
    {
        if (mapSize > this.MAX_NUM_ELEMENTS) throw new IllegalArgumentException(
            "The size of the 'map' provided is [" + mapSize + "], unfortunately this is " +
            "greater than 'maxNumElements' [" + this.MAX_NUM_ELEMENTS + ']'
        );
    }

    private void CHECK_MAX_NUM_ELEMENTS(int maxNumElements)
    {
        if (maxNumElements < 3) throw new IllegalArgumentException(
            "The value provided to 'maxNumElements' [" + maxNumElements + "] must be greater " +
            "than 2"
        );
    }
    

    // ********************************************************************************************
    // ********************************************************************************************
    // The Usual TreeMap Constructors - Copied from JDK 'java.util.TreeMap'
    // ********************************************************************************************
    // ********************************************************************************************


    /**
     * Constructs a new, empty tree map, using the <I>natural ordering</I> of its keys. All keys
     * inserted into the map must implement the interface {@code 'Comparable'}. Furthermore, all
     * such keys must be mutually comparable: {@code k1.compareTo(k2)}, and must not throw a
     * {@code ClassCastException} for any keys k1 and k2 in the map. If the user attempts to put
     * a key into the map that violates this constraint (for example, the user attempts to put a
     * string key into a map whose keys are integers), the {@code put(Object key, Object value)}
     * call will throw a {@code ClassCastException}.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param maxNumElements The maximum allowable number of elements that may be inserted into
     * {@code 'this'} tree before older elements are discarded.
     */
    public LRUTreeMap(int maxNumElements)
    {
        super();

        CHECK_MAX_NUM_ELEMENTS(maxNumElements);

        this.MAX_NUM_ELEMENTS = maxNumElements;
    }

    /**
     * Constructs a new, empty tree map, ordered according to the given comparator. All keys
     * inserted into the map must be mutually comparable by the given comparator:
     * {@code comparator.compare(k1, k2)}, must not throw a {@code ClassCastException} for any keys
     * k1 and k2 in the map. If the user attempts to put a key into the map that violates this
     * constraint, the {@code put(Object key, Object value)}
     * call will throw a {@code ClassCastException}.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param comparator the {@code java.util.Comparator} that will be used to order {@code 'this'}
     * map. If null, the <I>natural ordering</I> of the keys will be used.
     * 
     * @param maxNumElements The maximum allowable number of elements that may be inserted into
     * {@code 'this'} tree before older elements are discarded.
     */
    public LRUTreeMap(Comparator<? super K> comparator, int maxNumElements)
    {
        super(comparator);

        CHECK_MAX_NUM_ELEMENTS(maxNumElements);

        this.MAX_NUM_ELEMENTS = maxNumElements;
    }

    /**
     * Constructs a new tree map containing the same mappings as the given map, ordered according
     * to the <I>natural ordering</I> of its keys. All keys inserted into the new map must
     * implement the interface {@code 'Comparable'}. Furthermore, all such keys must be mutually
     * comparable: {@code k1.compareTo(k2)} must not throw a {@code ClassCastException} for any
     * keys k1 and k2 in the map. This method runs in <B>{@code n * log(n)}</B> time.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param m the map whose mappings are to be placed in {@code 'this'} map
     * 
     * @param maxNumElements The maximum allowable number of elements that may be inserted into
     * {@code 'this'} tree before older elements are discarded.
     * 
     * @throws ClassCastException if the keys in {@code m} are not Comparable, or are not mutually
     * comparable
     * 
     * @throws NullPointerException if the specified map is null
     */
    public LRUTreeMap(Map<? extends K,? extends V> m, int maxNumElements)
    {
        super(m);

        // Brief Check to make sure that 'maxNumElements' is at least 3 (and non-negative)
        CHECK_MAX_NUM_ELEMENTS(maxNumElements);

        this.MAX_NUM_ELEMENTS = maxNumElements;

        // Throws if map.size() is greater than MAX_NUM_ELEMENTS
        CHECK_NEW_MAP_SIZE(m.size());

        for (K key : m.keySet()) mapLRU.added(key);
    }

    /**
     * Constructs a new tree map containing the same mappings and using the same ordering as the
     * specified sorted map. This method runs in linear time.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param m the sorted map whose mappings are to be placed in {@code 'this'} map, and whose
     * {@code Comparator} is to be used to sort {@code 'this'} map
     * 
     * @param maxNumElements The maximum allowable number of elements that may be inserted into
     * {@code 'this'} tree before older elements are discarded.
     * 
     * @throws NullPointerException if the specified map is null
     */
    public LRUTreeMap(SortedMap<K,? extends V> m, int maxNumElements)
    {
        super(m);

        // Brief Check to make sure that 'maxNumElements' is at least 3 (and non-negative)
        CHECK_MAX_NUM_ELEMENTS(maxNumElements);

        this.MAX_NUM_ELEMENTS = maxNumElements;

        // Throws if map.size() is greater than MAX_NUM_ELEMENTS
        CHECK_NEW_MAP_SIZE(m.size());

        for (K key : m.keySet()) mapLRU.added(key);
    }


    // ********************************************************************************************
    // ********************************************************************************************
    // The Usual TreeMap Methods - Copied from JDK 'java.util.TreeMap'
    // ********************************************************************************************
    // ********************************************************************************************


    /**
     * Returns {@code TRUE} if {@code 'this'} map contains a mapping for the specified
     * {@code 'key'}.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key key whose presence in {@code 'this'} map is to be tested
     * 
     * @return {@code TRUE} if {@code 'this'} map contains a mapping for the specified {@code 'key'}
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    @SuppressWarnings("unchecked") // If the map contains "key", it must have been of type "K"
    public boolean containsKey(Object key)
    {
        boolean ret = super.containsKey(key);

        // Change the time-stamp-counter for 'key' (if it was present)
        // It is now the 'Most Recently Used'

        if (ret) this.mapLRU.changed((K) key);

        return ret;
    }

    /**
     * Returns {@code TRUE} if {@code 'this'} map maps one or more keys to the specified
     * {@code 'value'}. More formally, returns {@code TRUE} if and only if {@code 'this'} map
     * contains at least one mapping to a value v such that {@code (value==null ? v==null :
     * value.equals(v))}.
     * 
     * <BR /><BR />This operation will probably require time linear in the map size for most
     * implementations.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param value value whose presence in {@code 'this'} map is to be tested
     * 
     * @return {@code TRUE} if a mapping to value exists; {@code FALSE} otherwise
     */
    public boolean containsValue(Object value)
    {
        for (Map.Entry<K, V> entry : this.entrySet())
            if (value.equals(entry.getValue()))
            {
                // Change the time-stamp-counter for 'entry.key'
                // These are all now the 'Most Recently Used' keys
                //
                // NOTE: The counter-value assigned to each key is in order consistent with the
                //       the order of the entries returned by the iterator.

                this.mapLRU.changed(entry.getKey());
                return true;
            }

        return false;
    }

    /**
     * Returns the value to which the specified {@code 'key'} is mapped, or null if {@code 'this'}
     * map contains no mapping for the {@code 'key'}.  More formally, if {@code 'this'} map
     * contains a mapping from a key {@code k} to a value {@code v} such that {@code 'key'}
     * compares equal to {@code k} according to the map's ordering, then this method returns
     * {@code v}; otherwise it returns null. (There can be at most one such mapping.)
     *
     * <BR /><BR />A return value of null does not necessarily indicate that the map contains no
     * mapping for the {@code 'key'}; it's also possible that the map explicitly maps the
     * {@code 'key'} to null. The {@code 'containsKey'} operation may be used to distinguish these
     * two cases.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     *
     * @param key the key whose associated value is to be returned
     * 
     * @return the value to which the specified {@code 'key'} is mapped, or null if
     * {@code 'this'} map contains no mapping for the {@code 'key'}
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    @SuppressWarnings("unchecked") // If the map contains "key", it must have been of type "K"
    public V get(Object key)
    {
        V ret = super.get(key);

        // Change the time-stamp-counter for 'key' (if it was present)
        // It is now the 'Most Recently Used'

        if (ret != null) mapLRU.changed((K) key);

        return ret;
    }

    /**
     * Returns the first (lowest) key currently in {@code 'this'} map.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return the first (lowest) key currently in {@code 'this'} map
     * 
     * @throws NoSuchElementException if {@code 'this'} map is empty
     */
    public K firstKey()
    {
        K ret = super.firstKey();

        // Change the time-stamp-counter for 'first-key' (if present) before returning it.
        // It is now the 'Most Recently Used'

        if (ret != null) mapLRU.changed(ret);

        return ret;
    }

    /**
     * Returns the last (highest) key currently in {@code 'this'} map.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return the last (highest) key currently in {@code 'this'} map
     * 
     * @throws NoSuchElementException if {@code 'this'} map is empty
     */
    public K lastKey()
    {
        K ret = super.lastKey();

        // Change the time-stamp-counter for 'last-key' (if present) before returning it.
        // It is now the 'Most Recently Used'

        if (ret != null) mapLRU.changed(ret);

        return ret;    
    }

    /**
     * Copies all of the mappings from the specified {@code 'map'} to {@code 'this'} map. These
     * mappings replace any mappings that {@code 'this'} map had for any of the keys currently in
     * the specified {@code 'map'}.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated.
     * 
     * @param map mappings to be stored in {@code 'this'} map
     * 
     * @throws ClassCastException if the class of a key or value in the specified map prevents it
     * from being stored in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified map is null or the specified map contains a
     * null key and {@code 'this'} map does not permit null keys
     */
    public void putAll(Map<? extends K,? extends V> map)
    {
        // Throws if map.size() is greater than MAX_NUM_ELEMENTS
        CHECK_NEW_MAP_SIZE(map.size());

        super.putAll(map);

        // Add all of the entries in 'map' into the (Internal) LRU-Counter class
        for (K key : map.keySet()) this.mapLRU.added(key);

        if (this.size() > this.MAX_NUM_ELEMENTS) mapLRU.trimToFit();
    }

    /**
     * Associates the specified {@code value} with the specified {@code key} in {@code 'this'} map.
     * If the map previously contained a mapping for the {@code 'key'}, the old value is replaced.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated.
     *
     * @param key key with which the specified {@code 'value'} is to be associated
     * 
     * @param value value to be associated with the specified {@code 'key'}
     * 
     * @return the previous value associated with {@code 'key'}, or null if there was no mapping
     * for {@code 'key'}. (A null return can also indicate that the map previously associated
     * null with key.)
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public V put(K key, V value)
    {
        V ret = super.put(key, value);

        // Add this 'key' into the (Internal) LRU-Counter class
        this.mapLRU.added(key);

        return ret;
    }

    /**
     * Removes the mapping for this {@code 'key'} from {@code 'this' TreeMap} if present.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key key for which mapping should be removed
     * 
     * @return the previous value associated with {@code 'key'}, or null if there was no mapping
     * for {@code 'key'}. (A null return can also indicate that the map previously associated null
     * with {@code 'key'}.)
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    @SuppressWarnings("unchecked") // If the map contained "key", that key must have been type "K"
    public V remove(Object key)
    {
        V ret = super.remove(key);

        // Remove this 'key' from the (Internal) LRU-Counter class, if it was present.
        if (ret != null) this.mapLRU.removed((K) key);

        return ret;
    }

    /**
     * Removes all of the mappings from {@code 'this'} map. The map will be empty after this call
     * returns.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated.
     */
    public void clear()
    { super.clear(); this.mapLRU.clear(); }

    /**
     * Returns a shallow copy of this {@code LRUTreeMap} instance. (The keys and values themselves
     * are not cloned.)
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @return a shallow copy of {@code 'this'} map
     */
    public Object clone()
    { return new LRUTreeMap<K, V>(this, this.MAX_NUM_ELEMENTS); }

    /**
     * Returns a key-value mapping associated with the least key in {@code 'this'} map, or null if
     * the map is empty.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return an entry with the least key, or null if {@code 'this'} map is empty
     */
    public Map.Entry<K,V> firstEntry()
    {
        Map.Entry<K, V> ret = super.firstEntry();

        // Change the time-stamp-counter for 'first-key' before returning it.
        // It is now the 'Most Recently Used'
        //
        // NOTE: The (internal) mapLRU only needs to watch the 'key', not the 'key-value' pair.

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Returns a key-value mapping associated with the greatest key in {@code 'this'} map, or
     * null if the map is empty.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return an entry with the greatest key, or null if {@code 'this'} map is empty
     */
    public Map.Entry<K,V> lastEntry()
    {
        Map.Entry<K, V> ret = super.lastEntry();

        // Change the time-stamp-counter for 'last-key' before returning it.
        // It is now the 'Most Recently Used'
        //
        // NOTE: The (internal) mapLRU only needs to watch the 'key', not the 'key-value' pair.

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Removes and returns a key-value mapping associated with the least key in {@code 'this'} map,
     * or null if the map is empty.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return the removed first entry of {@code 'this'} map, or null if {@code 'this'} map is
     * empty
     */
    public Map.Entry<K,V> pollFirstEntry()
    {
        Map.Entry<K, V> ret = super.pollFirstEntry();

        // If there was a 'first key', it was just removed from the TreeMap
        // Make sure to remove it from the (internal) LRU-Counter class

        if (ret != null) this.mapLRU.removed(ret.getKey());

        return ret;
    }

    /**
     * Removes and returns a key-value mapping associated with the greatest key in this
     * map, or null if the map is empty.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @return the removed last entry of {@code 'this'} map, or null if {@code 'this'} map is empty
     */
    public Map.Entry<K,V> pollLastEntry()
    {
        Map.Entry<K, V> ret = super.pollLastEntry();

        // If there was a 'last key', it was just removed from the TreeMap
        // Make sure to remove it from the (internal) LRU-Counter class

        if (ret != null) this.mapLRU.removed(ret.getKey());

        return ret;
    }

    /**
     * Returns a key-value mapping associated with the greatest key strictly less than the
     * given {@code 'key'}, or null if there is no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return an entry with the greatest key less than {@code 'key'}, or null if there is no such
     * key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in the map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public Map.Entry<K,V> lowerEntry(K key)
    {
        Map.Entry<K, V> ret = super.lowerEntry(key);

        // Change the time-stamp-counter for the lower-entry 'key' (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Returns the greatest key strictly less than the given {@code 'key'}, or null if there is no
     * such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return the greatest key less than {@code 'key'}, or null if there is no such key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public K lowerKey(K key)
    {
        K ret = super.lowerKey(key);

        // Change the time-stamp-counter for the lower-key (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret);

        return ret;    
    }

    /**
     * Returns a key-value mapping associated with the greatest key less than or equal to the
     * given {@code 'key'}, or null if there is no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return an entry with the greatest key less than or equal to {@code 'key'}, or null if there
     * is no such key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public Map.Entry<K,V> floorEntry(K key)
    {
        Map.Entry<K, V> ret = super.floorEntry(key);

        // Change the time-stamp-counter for the 'key' of the floor-entry (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Returns the greatest key less than or equal to the given {@code 'key'}, or null if there is
     * no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return the greatest key less than or equal to {@code 'key'}, or null if there is no such
     * key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in the map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public K floorKey(K key)
    {
        K ret = super.floorKey(key);

        // Change the time-stamp-counter for the floor-key (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret);

        return ret;
    }

    /**
     * Returns a key-value mapping associated with the least key greater than or equal to
     * the given {@code 'key'}, or null if there is no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return an entry with the least key greater than or equal to {@code 'key'}, or null if
     * there is no such key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in the map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public Map.Entry<K,V> ceilingEntry(K key)
    {
        Map.Entry<K, V> ret = super.ceilingEntry(key);

        // Change the time-stamp-counter for the 'key' of the ceiling-entry (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Returns the least key greater than or equal to the given {@code 'key'}, or null if there is
     * no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return the least key greater than or equal to {@code 'key'}, or null if there is no such
     * key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in the map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public K ceilingKey(K key)
    {
        K ret = super.ceilingKey(key);

        // Change the time-stamp-counter for the ceiling-key (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret);

        return ret;
    }

    /**
     * Returns a key-value mapping associated with the least key strictly greater than the
     * given {@code 'key'}, or null if there is no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return an entry with the least key greater than key, or null if there is no such key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in the map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public Map.Entry<K,V> higherEntry(K key)
    {
        Map.Entry<K, V> ret = super.higherEntry(key);

        // Change the time-stamp-counter for the 'key' of the higher-entry (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret.getKey());

        return ret;
    }

    /**
     * Returns the least key strictly greater than the given {@code 'key'}, or null if
     * there is no such key.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key the key
     * 
     * @return the least key greater than {@code 'key'}, or null if there is no such key
     * 
     * @throws ClassCastException if the specified {@code 'key'} cannot be compared with the keys
     * currently in {@code 'this'} map
     * 
     * @throws NullPointerException if the specified {@code 'key'} is null and {@code 'this'} map
     * uses <I>natural ordering</I>, or its {@code Comparator} does not permit null keys
     */
    public K higherKey(K key)
    {
        K ret = super.higherKey(key);

        // Change the time-stamp-counter for the higher-key (if there is one)
        // before returning it.   It is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(ret);

        return ret;
    }

    /**
     * Replaces the entry for the specified {@code 'key'} only if currently mapped to the specified
     * {@code 'value'}.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key key with which the specified {@code 'value'} is associated
     * @param oldValue value expected to be associated with the specified {@code 'key'}
     * @param newValue value to be associated with the specified {@code 'key'}
     * 
     * @return {@code TRUE} if the value was replaced
     */
    public boolean replace(K key, V oldValue, V newValue)
    {
        boolean ret = super.replace(key, oldValue, newValue);

        // Change the time-stamp-counter for 'key' - if-and-only-if it was present and it mapped
        // to 'oldValue'
        // If both of these conditions were met, then it is now the 'Most Recently Used'

        if (ret) this.mapLRU.changed(key);

        return ret;
    }

    /**
     * Replaces the entry for the specified {@code 'key'} only if it is currently mapped to some
     * value.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * <BR /><B STYLE='color:red'>UPDATES:</B> After invoking the {@code 'super'} of this
     * <I>overridden method</I>, the internal LRU-Counter is updated, if necessary.
     * 
     * @param key key with which the specified {@code 'value'} is associated
     * @param value value to be associated with the specified {@code 'key'}
     *
     * @return the previous value associated with the specified {@code 'key'}, or null if there was
     * no mapping for the {@code 'key'}. (A null return can also indicate that the map previously
     * associated null with the key, if the implementation supports null values.)
     */
    public V replace(K key, V value)
    {
        V ret = super.replace(key, value);

        // Change the time-stamp-counter for 'key' - if-and-only-if it was present and mapped
        // to any value.
        // If it was, then it is now the 'Most Recently Used'

        if (ret != null) this.mapLRU.changed(key);

        if (this.size() > this.MAX_NUM_ELEMENTS) this.mapLRU.trimToFit();

        return ret;
    }

    /**
     * Performs the given action for each entry in {@code 'this'} map until all entries have been
     * processed or the action throws an exception. Unless otherwise specified by the implementing
     * class, actions are performed in the order of entry set iteration (if an iteration order is
     * specified.) Exceptions thrown by the action are relayed to the caller.
     * 
     * <BR /><BR /><SPAN CLASS=CopiedJDK>Description copied from class:
     * {@code java.util.TreeMap<K, V>}, <B>JDK 1.8</B></SPAN>
     * 
     * @param action The action to be performed for each entry
     */
    public void forEach(BiConsumer<? super K,? super V> action)
    {
        super.forEach(action);

        // No need to touch the (internal) LRU-Counter class.  All keys are being visited
        // at the same time.

        if (this.size() > this.MAX_NUM_ELEMENTS) this.mapLRU.trimToFit();
    }
}