/*
 * This software is distributed under following license based on modified BSD
 * style license.
 * ----------------------------------------------------------------------
 * 
 * Copyright 2009 The Nimbus2 Project. All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer. 
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE NIMBUS PROJECT ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
 * NO EVENT SHALL THE NIMBUS PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * The views and conclusions contained in the software and documentation are
 * those of the authors and should not be interpreted as representing official
 * policies, either expressed or implied, of the Nimbus2 Project.
 */
package jp.ossc.nimbus.service.cache;

import java.util.*;
import java.io.*;

import jp.ossc.nimbus.core.ServiceBase;

/**
 * Least Frequency Used あふれアルゴリズムサービス。<p>
 * 以下に、LFUであふれ対象となるキャッシュオブジェクトを決定するあふれアルゴリズムサービスのサービス定義例を示す。<br>
 * <pre>
 * &lt;?xml version="1.0" encoding="Shift_JIS"?&gt;
 * 
 * &lt;nimbus&gt;
 *     
 *     &lt;manager name="Sample"&gt;
 *         
 *         &lt;service name="LFUOverflowAlgorithm"
 *                  code="jp.ossc.nimbus.service.cache.LFUOverflowAlgorithmService"/&gt;
 *         
 *     &lt;/manager&gt;
 *     
 * &lt;/nimbus&gt;
 * </pre>
 *
 * @author M.Takata
 */
public class LFUOverflowAlgorithmService<E> extends ServiceBase
 implements OverflowAlgorithm<E>, CacheRemoveListener<E>, CacheAccessListener<E>,
            java.io.Serializable, LFUOverflowAlgorithmServiceMBean{
    
    private static final long serialVersionUID = -8742917099381213489L;

    private Map<CachedReference<E>, CounterCachedReference<E>> referenceMap;
    private List<CounterCachedReference<E>> referenceList;
    private boolean cachedRatioCompare = false;
    private long ratioUnitTime = 1000;
    
    // LFUOverflowAlgorithmServiceMBeanのJavaDoc
    @Override
    public int size(){
        return referenceList == null ? 0 : referenceList.size();
    }
    
    // LFUOverflowAlgorithmServiceMBeanのJavaDoc
    @Override
    public int getMaximumReferenceCount(){
        if(referenceMap == null){
            return 0;
        }
        synchronized(referenceMap){
            if(referenceMap.size() == 0){
                return 0;
            }
            Collections.sort(referenceList);
            CounterCachedReference<E> couterRef
                 = referenceList.get(referenceList.size() - 1);
            return couterRef.getCount();
        }
    }
    
    // LFUOverflowAlgorithmServiceMBeanのJavaDoc
    @Override
    public int getMinimumReferenceCount(){
        if(referenceMap == null){
            return 0;
        }
        synchronized(referenceMap){
            if(referenceMap.size() == 0){
                return 0;
            }
            Collections.sort(referenceList);
            CounterCachedReference<E> couterRef
                 = referenceList.get(0);
            return couterRef.getCount();
        }
    }
    
    // LFUOverflowAlgorithmServiceMBeanのJavaDoc
    @Override
    public String displayReferenceCounts(){
        if(referenceMap == null){
            return "";
        }
        synchronized(referenceMap){
            if(referenceMap.size() == 0){
                return "";
            }
            final StringWriter sw = new StringWriter();
            final PrintWriter pw = new PrintWriter(sw);
            Collections.sort(referenceList);
            CounterCachedReference<E> couterRef
                 = referenceList.get(referenceList.size() - 1);
            final double unitCount = couterRef.getCount() / 100.0d;
            final Iterator<CounterCachedReference<E>> itr = referenceList.iterator();
            while(itr.hasNext()){
                couterRef = itr.next();
                CachedReference<?> ref = couterRef.getCachedReference();
                final int count = couterRef.getCount();
                final int point = (int)(count / unitCount);
                for(int i = 0; i < point; i++){
                    pw.print('*');
                }
                pw.print('　');
                pw.print(Integer.toString(count));
                if(ref instanceof KeyCachedReference<?,?>){
                    pw.print('　');
                    pw.print(((KeyCachedReference<?,?>)ref).getKey());
                }
                pw.println("<br>");
            }
            return sw.toString();
        }
    }
    
    @Override
    public boolean isCachedRatioCompare() {
        return cachedRatioCompare;
    }
    
    @Override
    public void setCachedRatioCompare(boolean cachedRatioCompare) {
        this.cachedRatioCompare = cachedRatioCompare;
    }

    @Override
    public void setRatioUnitTime(long ratioUnitTime) {
        this.ratioUnitTime = ratioUnitTime;
    }
    
    /**
     * サービスの生成処理を行う。<p>
     * インスタンス変数の初期化を行う。
     *
     * @exception Exception サービスの生成処理に失敗した場合
     */
    @Override
    public void createService() throws Exception{
        referenceMap = Collections.synchronizedMap(new HashMap<CachedReference<E>, CounterCachedReference<E>>());
        referenceList = Collections.synchronizedList(new ArrayList<CounterCachedReference<E>>());
    }
    
    /**
     * サービスの破棄処理を行う。<p>
     * インスタンス変数の開放を行う。
     *
     * @exception Exception サービスの破棄処理に失敗した場合
     */
    @Override
    public void destroyService() throws Exception{
        reset();
        referenceMap = null;
        referenceList = null;
    }
    
    /**
     * キャッシュ参照を追加する。<p>
     * 引数で渡されたキャッシュ参照を保持する。同時に、{@link CachedReference#addCacheAccessListener(CacheAccessListener)}で、{@link CacheAccessListener}として自分自身を登録する。また、{@link CachedReference#addCacheRemoveListener(CacheRemoveListener)}で、{@link CacheRemoveListener}として自分自身を登録する。<br>
     *
     * @param ref キャッシュ参照
     */
    @Override
    public void add(CachedReference<E> ref){
        if(referenceMap == null || ref == null){
            return;
        }
        synchronized(referenceMap){
            if(!referenceMap.containsKey(ref)){
                CounterCachedReference<E> counterRef
                     = new CounterCachedReference<E>(ref, cachedRatioCompare, ratioUnitTime);
                referenceMap.put(ref, counterRef);
                referenceList.add(counterRef);
                ref.addCacheAccessListener(this);
                ref.addCacheRemoveListener(this);
            }
        }
    }
    
    /**
     * キャッシュ参照を削除する。<p>
     * 引数で渡されたキャッシュ参照を内部で保持している場合は、破棄する。同時に、{@link CachedReference#removeCacheAccessListener(CacheAccessListener)}で、{@link CacheAccessListener}として自分自身を登録解除する。また、{@link CachedReference#removeCacheRemoveListener(CacheRemoveListener)}で、{@link CacheRemoveListener}として自分自身を登録解除する。<br>
     *
     * @param ref キャッシュ参照
     */
    @Override
    public void remove(CachedReference<E> ref){
        if(referenceMap == null || ref == null){
            return;
        }
        synchronized(referenceMap){
            if(referenceMap.containsKey(ref)){
                CounterCachedReference<E> counterRef
                     = referenceMap.remove(ref);
                referenceList.remove(counterRef);
                ref.removeCacheAccessListener(this);
                ref.removeCacheRemoveListener(this);
            }
        }
    }
    
    /**
     * 最も参照頻度が低いキャッシュ参照をあふれさせる。<p>
     * {@link #add(CachedReference)}で渡されたキャッシュ参照の中から、最も参照頻度が低いキャッシュ参照を、あふれキャッシュ参照として返す。<br>
     *
     * @return 最も参照頻度が低いキャッシュ参照
     */
    @Override
    public CachedReference<E> overflow(){
        if(referenceMap == null){
            return null;
        }
        synchronized(referenceMap){
            if(referenceMap.size() != 0){
                Collections.sort(referenceList);
                CounterCachedReference<E> couterRef
                     = referenceList.get(0);
                referenceList.remove(couterRef);
                referenceMap.remove(couterRef.getCachedReference());
                return couterRef.getCachedReference();
            }
            return null;
        }
    }
    
    /**
     * 最も参照頻度が低いキャッシュ参照をあふれさせる。<p>
     * {@link #add(CachedReference)}で渡されたキャッシュ参照の中から、最も参照頻度が低いキャッシュ参照を、あふれキャッシュ参照として返す。<br>
     *
     * @param size あふれ数
     * @return 最も参照頻度が低いキャッシュ参照
     */
    @SuppressWarnings("unchecked")
    public CachedReference<E>[] overflow(int size){
        if(referenceMap == null || referenceMap.size() == 0){
            return null;
        }
        synchronized(referenceMap){
            if(referenceMap.size() != 0){
                final CachedReference<E>[] result = new CachedReference[Math.min(referenceMap.size(), size)];
                Collections.sort(referenceList);
                for(int i = 0; i < result.length; i++){
                    CounterCachedReference<E> couterRef
                         = referenceList.remove(0);
                    referenceMap.remove(couterRef.getCachedReference());
                    result[i] = couterRef.getCachedReference();
                }
                return result;
            }
            return null;
        }
    }
    
    /**
     * あふれアルゴリズムを実行するために保持している情報を初期化する。<p>
     * {@link #add(CachedReference)}で渡されたキャッシュ参照を全て破棄する。<br>
     */
    @Override
    public void reset(){
        if(referenceMap != null){
            referenceMap.clear();
            referenceList.clear();
        }
    }
    
    /**
     * キャッシュから削除されたキャッシュ参照の通知を受ける。<p>
     * {@link #remove(CachedReference)}を呼び出す。<br>
     *
     * @param ref キャッシュから削除されたキャッシュ参照
     */
    @Override
    public void removed(CachedReference<E> ref){
        remove(ref);
    }
    
    /**
     * 参照されたキャッシュ参照の通知を受ける。<p>
     * 内部で保持しているキャッシュ参照のリストに含まれる場合は、参照回数を増加させる。<br>
     *
     * @param ref 参照されたキャッシュ参照
     */
    @Override
    public void accessed(CachedReference<E> ref){
        if(referenceMap == null){
            return;
        }
        synchronized(referenceMap){
            if(referenceMap != null && referenceMap.containsKey(ref)){
                CounterCachedReference<E> counterRef
                     = referenceMap.get(ref);
                if(!counterRef.increment()){
                    for(CounterCachedReference<E> cref : referenceMap.values()){
                        cref.offset();
                    }
                    counterRef.increment();
                }
            }
        }
    }
    
    private static class CounterCachedReference<E>
     implements java.io.Serializable, Comparable<CounterCachedReference<E>>{
        
        private static final long serialVersionUID = -5670267780842863519L;
        
        private CachedReference<E> reference;
        private int count = 1;
        private long lastAccessTime;
        private boolean cachedRatioCompare = false;
        private long ratioUnitTime;
        
        public CounterCachedReference(CachedReference<E> ref, boolean cachedRatioCompare, long ratioUnitTime){
            reference = ref;
            lastAccessTime = System.currentTimeMillis();
            this.cachedRatioCompare = cachedRatioCompare;
            this.ratioUnitTime = ratioUnitTime;
        }
        public CachedReference<E> getCachedReference(){
            return reference;
        }
        public void offset(){
            count/=1000;
        }
        public boolean increment(){
            if(count == Integer.MAX_VALUE){
                return false;
            }
            count++;
            lastAccessTime = System.currentTimeMillis();
            return true;
        }
        public int getCount(){
            return count;
        }
        public long getLastAccessTime(){
            return lastAccessTime;
        }

        @Override
        public int compareTo(CounterCachedReference<E> arg0) {
            if(arg0 == null){
                return 1;
            }
            if(arg0 == this){
                return 0;
            }
            CounterCachedReference<E> comp = arg0;
            
            if(cachedRatioCompare){
                long currentTime = System.currentTimeMillis();
                long currentDiffTime = currentTime - getLastAccessTime();
                long compDifftime = currentTime - comp.getLastAccessTime();
                
                // キャッシュ時刻との差が無い場合
                if(currentDiffTime <= 0){
                    // 両方キャッシュ時刻との差が無い場合、カウントで比較
                    if(compDifftime <= 0){
                        if(getCount() == comp.getCount()){
                            if(reference.equals(comp.getCachedReference())){
                                return 0;
                            }else{
                                return hashCode() > comp.hashCode() ? -1 : 1;
                            }
                        }else if(getCount() > comp.getCount()){
                            return 1;
                        }else{
                            return -1;
                        }
                    }
                    // カウントが存在する場合は正
                    else if(getCount() > 0){
                            return 1;
                    }
                    else{
                        return 1;
                    }
                }
                // 両方キャッシュ時刻との差が存在する場合は、割合で比較
                else{
                    double ratio = getRatio(this, currentDiffTime);
                    double compRatio = getRatio(comp, compDifftime);
                    
                    if(ratio == compRatio){
                        if(reference.equals(comp.getCachedReference())){
                            return 0;
                        }else{
                            return hashCode() > comp.hashCode() ? -1 : 1;
                        }
                    }else if(ratio > compRatio){
                        return 1;
                    }else{
                        return -1;
                    }
                }
            }else{
                
                if(comp.getCount() == getCount()){
                    if(reference.equals(comp.getCachedReference())){
                        return 0;
                    }else{
                        return hashCode() > comp.hashCode() ? -1 : 1;
                    }
                }else if(comp.getCount() > getCount()){
                    return -1;
                }else{
                    return 1;
                }
            }
        }
        
        private double getRatio(CounterCachedReference<E> target, long diffTime){
            
            return (double)target.getCount() / Math.max(1.0, ((double)diffTime / (double)ratioUnitTime));
        }
     }
}
