package org.apache.commons.jcs3.utils.struct;
   
   /*
    * 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.
   */
  
  import java.util.AbstractMap;
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Map;
  import java.util.Set;
  import java.util.concurrent.ConcurrentHashMap;
  import java.util.concurrent.locks.Lock;
  import java.util.concurrent.locks.ReentrantLock;
  import java.util.stream.Collectors;
  
  import org.apache.commons.jcs3.engine.control.group.GroupAttrName;
  import org.apache.commons.jcs3.engine.stats.StatElement;
  import org.apache.commons.jcs3.engine.stats.Stats;
  import org.apache.commons.jcs3.engine.stats.behavior.IStatElement;
  import org.apache.commons.jcs3.engine.stats.behavior.IStats;
  import org.apache.commons.jcs3.log.Log;
  import org.apache.commons.jcs3.log.LogManager;
  
  /**
   * This is a simple LRUMap. It implements most of the map methods. It is not recommended that you
   * use any but put, get, remove, and clear.
   * <p>
   * Children can implement the processRemovedLRU method if they want to handle the removal of the
   * least recently used item.
   * </p>
   * <p>
   * This class was abstracted out of the LRU Memory cache. Put, remove, and get should be thread
   * safe. It uses a hashtable and our own double linked list.
   * </p>
   * <p>
   * Locking is done on the instance.
   * </p>
   */
  public abstract class AbstractLRUMap<K, V>
      implements Map<K, V>
  {
      /** The logger */
      private static final Log log = LogManager.getLog( AbstractLRUMap.class );
  
      /** double linked list for lru */
      private final DoubleLinkedList<LRUElementDescriptor<K, V>> list;
  
      /** Map where items are stored by key. */
      private final Map<K, LRUElementDescriptor<K, V>> map;
  
      /** lock to keep map and list synchronous */
      private final Lock lock = new ReentrantLock();
  
      /** stats */
      private long hitCnt;
  
      /** stats */
      private long missCnt;
  
      /** stats */
      private long putCnt;
  
      /**
       * This creates an unbounded version. Setting the max objects will result in spooling on
       * subsequent puts.
       */
      public AbstractLRUMap()
      {
          list = new DoubleLinkedList<>();
  
          // normal hashtable is faster for
          // sequential keys.
          map = new ConcurrentHashMap<>();
      }
  
  
      /**
       * This simply returns the number of elements in the map.
       * <p>
       * @see java.util.Map#size()
       */
      @Override
      public int size()
     {
         return map.size();
     }
 
     /**
      * This removes all the items. It clears the map and the double linked list.
      * <p>
      * @see java.util.Map#clear()
      */
     @Override
     public void clear()
     {
         lock.lock();
         try
         {
             map.clear();
             list.removeAll();
         }
         finally
         {
             lock.unlock();
         }
     }
 
     /**
      * Returns true if the map is empty.
      * <p>
      * @see java.util.Map#isEmpty()
      */
     @Override
     public boolean isEmpty()
     {
         return map.isEmpty();
     }
 
     /**
      * Returns true if the map contains an element for the supplied key.
      * <p>
      * @see java.util.Map#containsKey(Object)
      */
     @Override
     public boolean containsKey( final Object key )
     {
         return map.containsKey( key );
     }
 
     /**
      * This is an expensive operation that determines if the object supplied is mapped to any key.
      * <p>
      * @see java.util.Map#containsValue(Object)
      */
     @Override
     public boolean containsValue( final Object value )
     {
         return map.containsValue( value );
     }
 
     /**
      * @return map.values();
      */
     @Override
     public Collection<V> values()
     {
         return map.values().stream()
                 .map(LRUElementDescriptor::getPayload)
                 .collect(Collectors.toList());
     }
 
     /**
      * @param source
      */
     @Override
     public void putAll( final Map<? extends K, ? extends V> source )
     {
         if ( source != null )
         {
             source.forEach(this::put);
         }
     }
 
     /**
      * @param key
      * @return Object
      */
     @Override
     public V get( final Object key )
     {
         final V retVal;
 
         log.debug( "getting item  for key {0}", key );
 
         final LRUElementDescriptor<K, V> me = map.get( key );
 
         if ( me == null )
         {
             missCnt++;
             retVal = null;
         }
         else
         {
             hitCnt++;
             retVal = me.getPayload();
             list.makeFirst( me );
         }
 
         if ( me == null )
         {
             log.debug( "LRUMap miss for {0}", key );
         }
         else
         {
             log.debug( "LRUMap hit for {0}", key );
         }
 
         // verifyCache();
         return retVal;
     }
 
     /**
      * This gets an element out of the map without adjusting it's position in the LRU. In other
      * words, this does not count as being used. If the element is the last item in the list, it
      * will still be the last time in the list.
      * <p>
      * @param key
      * @return Object
      */
     public V getQuiet( final Object key )
     {
         V ce = null;
         final LRUElementDescriptor<K, V> me = map.get( key );
 
         if ( me != null )
         {
             ce = me.getPayload();
         }
 
         if ( me == null )
         {
             log.debug( "LRUMap quiet miss for {0}", key );
         }
         else
         {
             log.debug( "LRUMap quiet hit for {0}", key );
         }
 
         return ce;
     }
 
     /**
      * @param key
      * @return Object removed
      */
     @Override
     public V remove( final Object key )
     {
         log.debug( "removing item for key: {0}", key );
 
         // remove single item.
         lock.lock();
         try
         {
             final LRUElementDescriptor<K, V> me = map.remove(key);
 
             if (me != null)
             {
                 list.remove(me);
                 return me.getPayload();
             }
         }
         finally
         {
             lock.unlock();
         }
 
         return null;
     }
 
     /**
      * @param key
      * @param value
      * @return Object
      */
     @Override
     public V put(final K key, final V value)
     {
         putCnt++;
 
         LRUElementDescriptor<K, V> old = null;
         final LRUElementDescriptor<K, V> me = new LRUElementDescriptor<>(key, value);
 
         lock.lock();
         try
         {
             list.addFirst( me );
             old = map.put(key, me);
 
             // If the node was the same as an existing node, remove it.
             if ( old != null && key.equals(old.getKey()))
             {
                 list.remove( old );
             }
         }
         finally
         {
             lock.unlock();
         }
 
         // If the element limit is reached, we need to spool
         if (shouldRemove())
         {
             log.debug( "In memory limit reached, removing least recently used." );
 
             // The spool will put them in a disk event queue, so there is no
             // need to pre-queue the queuing. This would be a bit wasteful
             // and wouldn't save much time in this synchronous call.
             while (shouldRemove())
             {
                 lock.lock();
                 try
                 {
                     final LRUElementDescriptor<K, V> last = list.getLast();
                     if (last == null) {
                         verifyCache();
                         throw new Error("update: last is null!");
                     }
                     processRemovedLRU(last.getKey(), last.getPayload());
                     if (map.remove(last.getKey()) == null)
                     {
                         log.warn("update: remove failed for key: {0}",
                                 last::getKey);
                         verifyCache();
                     }
                     list.removeLast();
                 }
                 finally
                 {
                     lock.unlock();
                 }
             }
 
             log.debug( "update: After spool map size: {0}", map::size);
             if ( map.size() != list.size() )
             {
                 log.error("update: After spool, size mismatch: map.size() = {0}, "
                         + "linked list size = {1}",
                         map::size, list::size);
             }
         }
 
         if ( old != null )
         {
             return old.getPayload();
         }
         return null;
     }
 
     protected abstract boolean shouldRemove();
 
     /**
      * Dump the cache entries from first to list for debugging.
      */
     @SuppressWarnings("unchecked") // No generics for public fields
     public void dumpCacheEntries()
     {
         if (log.isTraceEnabled())
         {
             log.trace("dumpingCacheEntries");
             for (LRUElementDescriptor<K, V> me = list.getFirst(); me != null; me = (LRUElementDescriptor<K, V>) me.next)
             {
                 log.trace("dumpCacheEntries> key={0}, val={1}", me.getKey(), me.getPayload());
             }
         }
     }
 
     /**
      * Dump the cache map for debugging.
      */
     public void dumpMap()
     {
         if (log.isTraceEnabled())
         {
             log.trace("dumpingMap");
             map.forEach((key, value) -> log.trace("dumpMap> key={0}, val={1}", key, value.getPayload()));
         }
     }
 
     /**
      * Checks to see if all the items that should be in the cache are. Checks consistency between
      * List and map.
      */
     @SuppressWarnings("unchecked") // No generics for public fields
     protected void verifyCache()
     {
         if ( !log.isTraceEnabled() )
         {
             return;
         }
 
         log.trace( "verifycache: mapContains {0} elements, linked list "
                 + "contains {1} elements", map.size(), list.size() );
         log.trace( "verifycache: checking linked list by key" );
         for (LRUElementDescriptor<K, V> li = list.getFirst(); li != null; li = (LRUElementDescriptor<K, V>) li.next )
         {
             final K key = li.getKey();
             if ( !map.containsKey( key ) )
             {
                 log.error( "verifycache: map does not contain key : {0}", li.getKey() );
                 log.error( "li.hashCode={0}", li.getKey().hashCode() );
                 log.error( "key class={0}", key.getClass() );
                 log.error( "key hashCode={0}", key.hashCode() );
                 log.error( "key toString={0}", key.toString() );
                 if ( key instanceof GroupAttrName )
                 {
                     final GroupAttrName<?> name = (GroupAttrName<?>) key;
                     log.error( "GroupID hashCode={0}", name.groupId.hashCode() );
                     log.error( "GroupID.class={0}", name.groupId.getClass() );
                     log.error( "AttrName hashCode={0}", name.attrName.hashCode() );
                     log.error( "AttrName.class={0}", name.attrName.getClass() );
                 }
                 dumpMap();
             }
             else if ( map.get( li.getKey() ) == null )
             {
                 log.error( "verifycache: linked list retrieval returned null for key: {0}",
                         li.getKey() );
             }
         }
 
         log.trace( "verifycache: checking linked list by value " );
         for (LRUElementDescriptor<K, V> li3 = list.getFirst(); li3 != null; li3 = (LRUElementDescriptor<K, V>) li3.next )
         {
             if (!map.containsValue(li3))
             {
                 log.error( "verifycache: map does not contain value : {0}", li3 );
                 dumpMap();
             }
         }
 
         log.trace( "verifycache: checking via keysets!" );
         map.keySet().stream()
             .filter(key -> {
                 for (LRUElementDescriptor<K, V> li2 = list.getFirst(); li2 != null; li2 = (LRUElementDescriptor<K, V>) li2.next )
                 {
                     if ( key.equals( li2.getKey() ) )
                     {
                         return true;
                     }
                 }
 
                 log.error( "verifycache: key not found in list : {0}", key );
                 dumpCacheEntries();
                 if ( map.containsKey( key ) )
                 {
                     log.error( "verifycache: map contains key" );
                 }
                 else
                 {
                     log.error( "verifycache: map does NOT contain key, what the HECK!" );
                 }
 
                 return false;
             })
             .findFirst();
     }
 
     /**
      * This is called when an item is removed from the LRU. We just log some information.
      * <p>
      * Children can implement this method for special behavior.
      * @param key
      * @param value
      */
     protected void processRemovedLRU(final K key, final V value )
     {
         log.debug( "Removing key: [{0}] from LRUMap store, value = [{1}]", key, value );
         log.debug( "LRUMap store size: \"{0}\".", this.size() );
     }
 
     /**
      * @return IStats
      */
     public IStats getStatistics()
     {
         final IStats stats = new Stats();
         stats.setTypeName( "LRUMap" );
 
         final ArrayList<IStatElement<?>> elems = new ArrayList<>();
 
         elems.add(new StatElement<>( "List Size", Integer.valueOf(list.size()) ) );
         elems.add(new StatElement<>( "Map Size", Integer.valueOf(map.size()) ) );
         elems.add(new StatElement<>( "Put Count", Long.valueOf(putCnt) ) );
         elems.add(new StatElement<>( "Hit Count", Long.valueOf(hitCnt) ) );
         elems.add(new StatElement<>( "Miss Count", Long.valueOf(missCnt) ) );
 
         stats.setStatElements( elems );
 
         return stats;
     }
 
     /**
      * This returns a set of entries. Our LRUMapEntry is used since the value stored in the
      * underlying map is a node in the double linked list. We wouldn't want to return this to the
      * client, so we construct a new entry with the payload of the node.
      * <p>
      * TODO we should return out own set wrapper, so we can avoid the extra object creation if it
      * isn't necessary.
      * <p>
      * @see java.util.Map#entrySet()
      */
     @Override
     public Set<Map.Entry<K, V>> entrySet()
     {
         lock.lock();
         try
         {
             return map.entrySet().stream()
                     .map(entry -> new AbstractMap.SimpleEntry<>(
                             entry.getKey(), entry.getValue().getPayload()))
                     .collect(Collectors.toSet());
         }
         finally
         {
             lock.unlock();
         }
     }
 
     /**
      * @return map.keySet();
      */
     @Override
     public Set<K> keySet()
     {
         return map.values().stream()
                 .map(LRUElementDescriptor::getKey)
                 .collect(Collectors.toSet());
     }
 }