package org.apache.commons.jcs.engine.memory.arc;

/*
 * 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 org.apache.commons.jcs.engine.CacheElement;
import org.apache.commons.jcs.engine.behavior.ICacheElement;
import org.apache.commons.jcs.engine.control.CompositeCache;
import org.apache.commons.jcs.engine.memory.AbstractMemoryCache;
import org.apache.commons.jcs.engine.memory.util.MemoryElementDescriptor;
import org.apache.commons.jcs.engine.stats.StatElement;
import org.apache.commons.jcs.engine.stats.Stats;
import org.apache.commons.jcs.engine.stats.behavior.IStatElement;
import org.apache.commons.jcs.engine.stats.behavior.IStats;
import org.apache.commons.jcs.utils.struct.DoubleLinkedList;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import java.io.IOException;
import java.util.ArrayList;

/**
 * This is a rough implmentation of an adaptive replacement cache. ARC is a
 * hybrid LFU / LRU that adapts to user behavior.
 * <p>
 * See the ARC method for more detail on how the algorithm works.
 * <p>
 * @see http://www.almaden.ibm.com/StorageSystems/autonomic_storage/ARC/index.shtml
 * @see http://www.almaden.ibm.com/cs/people/dmodha/ARC.pdf
 */
public class ARCMemoryCache
    extends AbstractMemoryCache
{
    private static final long serialVersionUID = 1L;

    private static final Log log = LogFactory.getLog( ARCMemoryCache.class );

    // private int[] loc = new int[0];

    // maximum size
    private int maxSize = 0;

    private DoubleLinkedList T1 = new DoubleLinkedList();

    private DoubleLinkedList T2 = new DoubleLinkedList();

    private DoubleLinkedList B1 = new DoubleLinkedList();

    private DoubleLinkedList B2 = new DoubleLinkedList();

    /** id of list T1 */
    protected static final int _T1_ = 1;

    /** id of list T2 */
    protected static final int _T2_ = 2;

    /** id of list B1 */
    protected static final int _B1_ = 3;

    /** id of list B2 */
    protected static final int _B2_ = 4;

    // ideal size of T1
    private int target_T1 = 0;

    private ConcurrentHashMap map = new ConcurrentHashMap();

    private int cnt = 0;

    private int hitCnt = 0;

    private int missCnt = 0;

    private int putCnt = 0;

    /**
     * Default constructor.
     */
    public ARCMemoryCache()
    {
        if ( log.isInfoEnabled() )
        {
            log.info( "Loading Arc" );
        }
    }

    /**
     * Get an Array of the keys for all elements in the memory cache
     * @return Object[]
     */
    public Object[] getKeyArray()
    {
        // need to lock to map here?
        synchronized ( map )
        {
            return map.keySet().toArray();
        }
    }

    public ICacheElement<K, V> getQuiet( K key )
        throws IOException
    {
        return get( key );
    }

    /**
     * For post reflection creation initialization
     * <p>
     * @param hub
     */
    public synchronized void initialize( CompositeCache hub )
    {
        super.initialize( hub );
        maxSize = this.cattr.getMaxObjects(); // / 2;
        target_T1 = maxSize / 2;
        log.info( "initialized LRUMemoryCache for " + cacheName );
    }

    /**
     * Looks for the item in the lists.
     */
    public ICacheElement<K, V> get( K key )
        throws IOException
    {
        CacheElement ce = new CacheElement( cacheName, key, null );

        ICacheElement<K, V> ice = null;
        try
        {
            ice = ARC( ce, true );
        }
        catch ( Exception e )
        {
            log.error( e );
        }
        return ice;
    }

    /**
     * Adds an element to the cache.
     */
    public void update( ICacheElement<K, V> ce )
    {
        try
        {
            ARC( ce, false );
        }
        catch ( Exception e )
        {
            log.error( e );
        }
    }

    /**
     * This is the primary method for the ARC. It handles both puts and gets.
     * <p>
     * The ARC has 4 linked lists: T1, T2, B1, and B2. The 'T' lists are tops
     * and the 'B' lists are bottoms. Bottom lists do not hold object, only
     * keys.
     * <p>
     * The T1 list is an LRU (Least Recently Used) list. The T2 list is a near
     * LFU (Least Frequently Used) list.
     * <p>
     * After items are removed from T1 and T2, their keys are stored in B1 and
     * B2. The number of keys in B1 and B2 is restricted to the number of max
     * items.
     * <p>
     * When there is a put or a get for an item whose key exists on one of the
     * bottom lists, the maximum number of items in T1 is adjusted. If the item
     * was found on B2 (the bottom LFU list) the maximum allowed in T1 (the top
     * LRU list) is reduced. If the item is found in B1 list (the bottom LRU)
     * the maximum allowed in T1 is increased.
     * <p>
     * The maximum allowed in T1 will not exceed the maxSize. The maximum in T1
     * and T2 combined will not exceed the maxSize. The maximum number of
     * elements and keys allowed in all 4 lists will not exceed twice the
     * maximum size.
     * <p>
     * All the elements are stored in a map. The lists keep track of when the
     * element was last used, or when it was deleted and from where. We first
     * look for the item in the map, if we find it, we go looking for it in the
     * lists.
     * <p>
     * @param ce
     *            ICacheElement
     * @param isGet
     *            boolean
     * @return ICacheElement
     */
    public ICacheElement<K, V> ARC( ICacheElement<K, V> ce, boolean isGet )
    {
        cnt++;
        logStatsOccassionally( ce, isGet );
        if ( !isGet )
        {
            putCnt++;
        }

        ElementDescriptor temp = (ElementDescriptor) map.get( ce.getKey() );
        boolean isHit = true;

        if ( temp != null )
        {
            if ( isGet )
            {
                hitCnt++;
            }

            // determine where the element lives.
            switch ( temp.listNum )
            {
                case _T1_:
                    handleFoundInT1( temp );
                    break;

                case _T2_:
                    handleFoundInT2( temp );
                    break;

                case _B1_:
                    temp = handleFoundInB1( ce, isGet, temp );
                    break;

                case _B2_:
                    temp = handleFoundInB2( ce, isGet, temp );
                    break;
            }
        }
        else
        {
            /* Element is not in cache */
            isHit = false;
            if ( isGet )
            {
                missCnt++;
            }
            if ( log.isDebugEnabled() )
            {
                log.debug( "Element is not in cache" );
            }
        }

        // ////////////////////////////////////////////////////////////////////////////
        // Do some size Checks if this is a put
        if ( !isGet && !isHit )
        {
            if ( T1.size() + B1.size() >= maxSize )
            {
                /* B1 + T1 full? */
                if ( T1.size() < maxSize )
                {
                    /* Still room in T1? */
                    temp = (ElementDescriptor) B1.removeLast();
                    if ( temp != null )
                    {
                        map.remove( temp.key );
                    }
                    /* yes: take page off B1 */
                    // temp->pointer = replace(); /* find new place to put page
                    // */
                    replace( temp );
                }
                else
                {
                    /* no: B1 must be empty */
                    temp = (ElementDescriptor) T1.removeLast(); /*
                                                                 * take page //
                                                                 * off // T1
                                                                 */
                    map.remove( temp.ce.getKey() );
                    // if (temp->dirty) destage(temp); /* if dirty, evict before
                    // overwrite */
                    replace( temp );
                }
            }
            else
            {
                /* B1 + T1 have less than the maxSize elements */
                if ( T1.size() + T2.size() + B1.size() + B2.size() >= maxSize )
                {
                    /* cache full? */
                    /* Yes, cache full: */
                    if ( T1.size() + T2.size() + B1.size() + B2.size() >= 2 * maxSize )
                    {
                        /* cache is full: */
                        /* x find and reuse B2�s LRU */
                        temp = (ElementDescriptor) B2.removeLast();
                        if ( temp != null )
                        {
                            map.remove( temp.key );
                        }
                    }
                    else
                    {
                        /* cache directory not full, easy case */
                        // nop
                    }
                    replace( temp );
                }
                else
                {
                    /* cache not full, easy case */
                    // nop
                }
            }
        }

        if ( !isGet && !isHit )
        {
            temp = new ElementDescriptor( ce );
            temp.ce = ce;
            temp.listNum = _T1_;
            T1.addFirst( temp );
            // seen once recently, put on T1
            this.map.put( temp.ce.getKey(), temp );
        }
        // end if put

        if ( temp == null )
        {
            return null;
        }
        return temp.ce;
    }

    /**
     * Move to T2 if the item was found in T1.
     * <p>
     * @param temp
     */
    protected void handleFoundInT1( ElementDescriptor temp )
    {
        if ( log.isDebugEnabled() )
        {
            log.debug( "T1" );
        }
        if ( log.isDebugEnabled() )
        {
            log.debug( "T1 to T2, before remove = " + T1.size() );
        }
        boolean stat1 = T1.remove( temp );
        // need to implement our
        // own list
        if ( log.isDebugEnabled() )
        {
            log.debug( "T1 to T2, after remove = " + T1.size() + " stat = " + stat1 );
        }

        temp.listNum = _T2_;
        T2.addFirst( temp );
    }

    /**
     * If it was found in T2, we move it to the top of the T2 list.
     * <p>
     * @param temp
     */
    protected void handleFoundInT2( ElementDescriptor temp )
    {
        if ( log.isDebugEnabled() )
        {
            log.debug( "T2" );
        }

        temp.listNum = _T2_;
        T2.makeFirst( temp );
    }

    /**
     * B1 hit: favor recency
     * <p>
     * @param ce
     * @param isGet
     * @param temp
     * @return
     */
    protected ElementDescriptor handleFoundInB1( ICacheElement<K, V> ce, boolean isGet, ElementDescriptor temp )
    {
        // B1 hit: favor recency

        // adapt the target size
        target_T1 = Math.min( target_T1 + Math.max( B2.size() / B1.size(), 1 ), maxSize );
        if ( log.isDebugEnabled() )
        {
            log.debug( "B1, targetT1 = " + target_T1 );
        }

        if ( !isGet )
        {
            if ( log.isDebugEnabled() )
            {
                log.debug( "B1 before remove = " + B1.size() );
            }
            boolean stat3 = B1.remove( temp ); // need to implement
            // our own list
            if ( log.isDebugEnabled() )
            {
                log.debug( "B1 after remove = " + B1.size() + " stat = " + stat3 );
            }
            replace( temp );
            temp.listNum = _T2_;
            temp.ce = ce;
            // seen twice recently, put on T2
            T2.addFirst( temp );
        }
        else
        {
            // if this is just a get, then adjust the cache
            // it is essentially a miss.
            temp = null;
            hitCnt--;
            missCnt++;
        }
        return temp;
    }

    /**
     * B2 hit: favor frequency
     * <p>
     * @param ce
     * @param isGet
     * @param temp
     * @return
     */
    protected ElementDescriptor handleFoundInB2( ICacheElement<K, V> ce, boolean isGet, ElementDescriptor temp )
    {
        // adapt the target size
        target_T1 = Math.max( target_T1 - Math.max( B1.size() / B2.size(), 1 ), 0 );
        if ( log.isDebugEnabled() )
        {
            log.debug( "B2, targetT1 = " + target_T1 );
        }

        if ( !isGet )
        {
            if ( log.isDebugEnabled() )
            {
                log.debug( "B2 before remove = " + B2.size() );
            }
            boolean stat4 = B2.remove( temp ); // need to implement
            // our own list
            if ( log.isDebugEnabled() )
            {
                log.debug( "B2 after remove = " + B2.size() + " stat = " + stat4 );
            }

            replace( temp );
            temp.listNum = _T2_;
            temp.ce = ce;
            // seen twice recently, put on T2
            T2.addFirst( temp );

            replace( temp );
        }
        else
        {
            // if this is just a get, then adjust the cache
            // it is essentially a miss.
            temp = null;
            hitCnt--;
            missCnt++;
        }
        return temp;
    }

    /**
     * Prints the stats every 10000 or so operations.
     * <p>
     * @param ce
     * @param isGet
     */
    protected void logStatsOccassionally( ICacheElement<K, V> ce, boolean isGet )
    {
        if ( cnt % 10000 == 0 )
        // if ( true )
        {
            if ( log.isInfoEnabled() )
            {
                StringBuilder buf = new StringBuilder();
                buf.append( "\n ce.key() = " ).append( ce.getKey() );
                buf.append( "\n isGet = " ).append( isGet );
                buf.append( getStats() );
                log.info( buf.toString() );
            }
        }
    }

    /**
     * This method doesn't so much replace as remove. It pushes the least
     * recently used in t1 or t2 to a dummy holder. The holder keeps a dummy
     * object that stores the key so that subsequent gets and puts can help
     * train the cache. Items are spooled if there is a disk cache at this
     * point.
     * <p>
     * @param orig
     *            ElementDescriptor
     */
    public void replace( ElementDescriptor orig )
    {
        try
        {
            ElementDescriptor temp;
            if ( T1.size() >= Math.max( 1, target_T1 ) )
            {
                // T1�s size exceeds target?
                // yes: T1 is too big
                temp = (ElementDescriptor) T1.getLast();
                if ( orig == null || !orig.key.equals( temp.key ) )
                {
                    if ( log.isDebugEnabled() )
                    {
                        log.debug( "replace -- T1 to B1" );
                        log.debug( getStats() );
                    }
                    temp = (ElementDescriptor) T1.removeLast(); // grab LRU from
                    // T1
                    // nullify object, temp is now just a dummy container to
                    // help adjust the lru size
                    try
                    {
                        this.waterfal( temp.ce );
                    }
                    catch ( Exception e )
                    {
                        log.error( e );
                    }
                    temp.ce = null;
                    temp.listNum = _B1_; // note that fact
                    B1.addFirst( temp ); // put it on B1
                    // T1Length�; B1Length++; // bookkeep
                }
                else
                {
                    if ( log.isDebugEnabled() )
                    {
                        log.debug( "orig == temp, t1" );
                    }
                }
            }
            else
            // if t2 is greater than or equal to what is left in c after the
            // target
            if ( ( T2.size() + T1.size() ) > maxSize )
            {

                // no: T1 is not too big
                temp = (ElementDescriptor) T2.getLast();
                if ( orig == null || !orig.key.equals( temp.key ) )
                {
                    if ( log.isDebugEnabled() )
                    {
                        log.debug( "replace -- T2 to B2" );
                        log.debug( getStats() );
                    }

                    temp = (ElementDescriptor) T2.removeLast(); // grab LRU page
                    // of T2
                    // nullify object, temp is now just a dummy container to
                    // help
                    // adjust the lru size
                    try
                    {
                        this.waterfal( temp.ce );
                    }
                    catch ( Exception e )
                    {
                        log.error( e );
                    }
                    temp.ce = null;
                    temp.listNum = _B2_; // note that fact
                    B2.addFirst( temp ); // put it on B2
                    // T2Length�; B2Length++; // bookkeep
                }
                else
                {
                    if ( log.isDebugEnabled() )
                    {
                        log.debug( "orig == temp, t2" );
                    }
                }
            }
        }
        catch ( Exception e )
        {
            log.error( e );
        }
    }

    /**
     * remove the element if it is in any of the lists.
     * @param key
     *            Serializable
     * @return boolean
     */
    public boolean remove( K key )
    {
        ElementDescriptor temp = (ElementDescriptor) map.remove( key );
        if ( temp != null )
        {
            int loc = temp.listNum;
            if ( loc == _T1_ )
            {
                T1.remove( temp );
            }
            else if ( loc == _T2_ )
            {
                T2.remove( temp );
            }
            else if ( loc == _B1_ )
            {
                B1.remove( temp );
            }
            else if ( loc == _B2_ )
            {
                B2.remove( temp );
            }
        }
        return true;
    }

    /**
     * Remove all of the elements from both the Map and the linked list
     * implementation. Overrides base class.
     */
    public synchronized void removeAll()
        throws IOException
    {
        map.clear();
        T1.removeAll();
        T2.removeAll();
        B1.removeAll();
        B2.removeAll();
    }

    // ///////////////////////////////////////////////////////////////////////
    /**
     * @return
     */
    public String getStats()
    {
        return getStatistics().toString();
    }

    /*
     * (non-Javadoc)
     * @see org.apache.commons.jcs.engine.memory.MemoryCache#getStatistics()
     */
    public IStats getStatistics()
    {
        IStats stats = new Stats();
        stats.setTypeName( "LRU Memory Cache" );

        ArrayList elems = new ArrayList();

        IStatElement se = null;

        se = new StatElement();
        se.setName( "T1 Size" );
        se.setData( "" + T1.size() );
        elems.add( se );

        se = new StatElement();
        se.setName( "T2 Size" );
        se.setData( "" + T2.size() );
        elems.add( se );

        se = new StatElement();
        se.setName( "B1 Size" );
        se.setData( "" + B1.size() );
        elems.add( se );

        se = new StatElement();
        se.setName( "B2 Size" );
        se.setData( "" + B2.size() );
        elems.add( se );

        se = new StatElement();
        se.setName( "Target T1 Size" );
        se.setData( "" + target_T1 );
        elems.add( se );

        se = new StatElement();
        se.setName( "Map Size" );
        se.setData( "" + map.size() );
        elems.add( se );

        se = new StatElement();
        se.setName( "Put Count" );
        se.setData( "" + putCnt );
        elems.add( se );

        se = new StatElement();
        se.setName( "Hit Count" );
        se.setData( "" + hitCnt );
        elems.add( se );

        se = new StatElement();
        se.setName( "Miss Count" );
        se.setData( "" + missCnt );
        elems.add( se );

        // get an array and put them in the Stats object
        IStatElement[] ses = (IStatElement[]) elems.toArray( new StatElement[0] );
        stats.setStatElements( ses );

        // int rate = ((hitCnt + missCnt) * 100) / (hitCnt * 100) * 100;
        // buf.append("\n Hit Rate = " + rate + " %" );

        return stats;
    }

    // ///////////////////////////////////////////////
    /**
     * @author Aaron Smuts
     */
    public class ElementDescriptor
        extends MemoryElementDescriptor
    {
        private static final long serialVersionUID = -6271920830449238031L;

        /** Where this is located */
        public int listNum;

        /** Its key */
        public K key;

        /**
         * Constructs a usable object
         * @param ce
         */
        public ElementDescriptor( ICacheElement<K, V> ce )
        {
            super( ce );
            key = ce.getKey();
        }
    }

    /**
     * This is currently not implemented. It should remove items from t2. If
     * there are none in t2, it should move them to t2 and then remove them.
     * <p>
     * (non-Javadoc)
     * @see org.apache.commons.jcs.engine.memory.MemoryCache#freeElements(int)
     */
    public int freeElements( int numberToFree )
        throws IOException
    {
        // TODO Auto-generated method stub
        return 0;
    }

    /**
     * At the start this will be 1/2 the max.
     * <p>
     * @return Returns the target_T1.
     */
    protected int getTarget_T1()
    {
        return target_T1;
    }

    /**
     * Returns the size of the list.
     * @param listNumber
     * @return -1 if the list is unknown.
     */
    protected int getListSize( int listNumber )
    {
        switch ( listNumber )
        {
            case _T1_:
                return T1.size();

            case _T2_:
                return T2.size();

            case _B1_:
                return B1.size();

            case _B2_:
                return B2.size();
        }
        return -1;
    }

}