// package

/*
 * @(#)WorkingSetCache.java	
 *
 * Copyright (c) 2000, Pat Farrell.  All rights reserved.
 *  This code is free for anyone to use, provided this copyright and       
 *  statement are left attached.                                           
 *                                                                         
 */

import java.util.*;
/**
 * A working set cache. Will manage a cache of any objects that can
 * be put into a java.util.Map store. Use it exactly as you would
 * a normal Map.
 * <p>
 * The constructor allows specification of
 * sweep cycle time, altho a reasonable default is automatically provided.
 * Based on the working set model by Peter J. Denning
 * See numerous citations including "The working set model for program behavior"
 * Communications of the ACM, May 1968
 * <p>
 * This class is automatic and self contained. 
 * There is nothing to do but declare this and use it. 
 * It is multi-threaded, but you don't have to worry about that.
 */
public class WorkingSetCache  implements Runnable {
    /** the sweep thread */
    Thread myThread = null;
    /** interval (in milliseconds) for the sweep thread to nap */
    protected long mySweepInterval;
    /** number of entries in the cache as of the last sweep cycle, which is only approximatly the number in the cache */
    protected long currentActiveCount = 0;

    /** number of sweep cycles we have done */
    protected long numSweeps = 0;
    /** number of values found (hits) */
    protected long numHits = 0;
    /** number of misses */
    protected long numMiss = 0;
    /** count of terribly slow searches performed */
    protected long numSlowSearches = 0;
    /** our internal data map */
    protected Map theCache = null;
     
/**
 * default constructor, pick a decent time for the flush cycle
 */
    public WorkingSetCache() {
        this(10);   // ten minutes seems like a good default
    }


/**
 * standard constructor, accept time (in minutes!) for aging cycle
 *
 * @param minutes a long containing the time to sleep between cycles
 */
    public WorkingSetCache( long minutes) {
        theCache = Collections.synchronizedMap(new HashMap());
        if ( minutes < 0 || minutes > 24*60 )
        {
            String temp = "WSC called with sweeptime of " + minutes + " minutes, is the scale wrong? postive value required, 1 day max";
            System.out.println(temp);
            System.exit(-1);
        }
        mySweepInterval = minutes*1000*60;
        if (mySweepInterval > 0) {
            myThread = new Thread(this);
            myThread.start();
        }
    }
/**
 * sweep thru the cache, deleting any unmarked items and clearing all marks
 */
    private void deleteUnused() {
        currentActiveCount = 0;
        synchronized(theCache) { 
            Set keySet = (Set)theCache.keySet();
            Object [] keys = new Object[keySet.size()];
            int k=0;
            for (Iterator it=keySet.iterator(); it.hasNext();) {
                keys[k++] = it.next();
            }
            
            int whichEntry = 0;
            try {
                for (int i=0; i<keys.length; i++)
                {
                    Object key = keys[i];

                    WorkingSetObject wso = (WorkingSetObject) theCache.get(key);
                    if (wso == null) continue;
                    if ( wso.usedThisCycle )
                    {
                        currentActiveCount++;
                        wso.usedThisCycle = false;
                    }
                    else
                        remove(key);
                    whichEntry++;                        
                }
            } catch (java.util.ConcurrentModificationException cme ) {
                System.err.println("WSetCache concurrent for " + whichEntry + " out of " + keySet.size());
                cme.printStackTrace();
            }
        }
    }
/**
 * basic cache sweeper thread.
 * Note: envoking programs do <i>not</i> need to explicitly call this.
 */
    public void run() {
        while (true) {
            try {
                Thread.currentThread().sleep(mySweepInterval);
                numSweeps++;
                deleteUnused();
            } catch (Exception e) {
                System.err.println("WSC run catch");
                e.printStackTrace();
            }
        }
    }


    /**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this cache. Neither the key nor the
     * value can be <code>null</code>.
     * <p>
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @param      key     the cache key.
     * @param      value   the value.
     * @return     the previous value of the specified key in this cache,
     *             or <code>null</code> if it did not have one.
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>.
     * @see     java.lang.Object#equals(java.lang.Object)
     * @see     java.util.Hashtable#get(java.lang.Object)
     */
    public Object put(Object key, Object value) {
        WorkingSetObject wso = new WorkingSetObject( value );
        Object o = theCache.put(key, wso);
        return value;
    }
    /**
     * Removes the key (and its corresponding value) from this
     * cache. This method does nothing (but accounting) if the key is not in the cache.
     *
     * @param   key   the key that needs to be removed.
     * @return  the value to which the key had been mapped in this cache,
     *          or <code>null</code> if the key did not have a mapping.
     */
    public Object remove(Object key) {
        WorkingSetObject wso = (WorkingSetObject) theCache.remove(key);
        if (wso == null )
        {
            numMiss++;
            return null;
        }
        else
        {
            numHits++;
        }
        return  wso.obj;
    }
    /**
     * Returns the value to which the specified key is mapped in this cache.
     *
     * @param   key   a key in the cache.
     * @return  the value to which the key is mapped in this cache;
     *          <code>null</code> if the key is not mapped to any value in
     *          this cache.
     * @see     java.util.Hashtable#put(java.lang.Object, java.lang.Object)
     */
    public Object get(Object key) {
        WorkingSetObject wso = (WorkingSetObject) theCache.get(key);
        if (wso == null )
        {
            numMiss++;
            return null;
        }
        else
        {
            numHits++;
            wso.usedThisCycle = true;
        }
        return wso.obj;
    }
/**
 * Returns <tt>true</tt> if this map contains a mapping for the specified
 * key.
 * 
 * @return <tt>true</tt> if this map contains a mapping for the specified key.
 * @param key key whose presence in this Map is to be tested.
 */
public boolean containsKey(Object key) { return theCache.containsKey(key);}
	    
/**
 * slow but occasionally useful routine to slog thru the elements
 * looking for a value. Note that this locks the whole table
 * for the long time it takes. 
 * @return <tt>true</tt> if this cache contains a mapping for the specified value.
 */
public boolean contains(Object value)
{
    numSlowSearches++;
    synchronized (theCache) {
        Collection wsoColl = theCache.values();
        for (Iterator it = wsoColl.iterator(); it.hasNext(); ) {
            WorkingSetObject wso =  (WorkingSetObject) it.next();
            if ( wso.obj.equals(value))
                return true;
        }
    }
    return false;
}
/**
 * slow but occasionally useful routine to slog thru the elements
 * looking for a value, returning its key. Note that this locks the whole table
 * for the long time it takes. And it marks all visited elements of the cache
 * as in use -- since it sweeps thru them all until it either finds a match
 * or covers the whole table.
 *
 * @param value the object to look for
 * @return Object the (first) key to the object
 */
public Object getKeyForValue(Object value)
{
    numSlowSearches++;
    synchronized(theCache) {
        Collection wsoColl = theCache.keySet();
        for (Iterator it = wsoColl.iterator(); it.hasNext(); ) {
            Object key = it.next();
            Object obj = get(key);
            if ( obj.equals(value))
                return key;
        }
    }
    return null;
}

    /**
     * Returns a set view of the keys contained in this map.  The set is
     * backed by the map, so changes to the map are reflected in the set, and
     * vice-versa.  The set supports element removal, which removes the
     * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
     * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
     * <tt>addAll</tt> operations.
     *
     * @return a set view of the keys contained in this map.
     */
    public Set keySet() {
        return theCache.keySet();
    }
/** 
 * return a set of the values of the cache.
 * And it marks all visited elements of the cache
 * as in use -- since it sweeps thru them all until it either finds a match
 * or covers the whole table.
 */
public HashSet getValues() {
    numSlowSearches++;
    HashSet rval = new HashSet();
    synchronized(theCache) {
        Collection wsoColl = theCache.values();
        for (Iterator it = wsoColl.iterator(); it.hasNext(); ) {
            WorkingSetObject wso = (WorkingSetObject) it.next();
            rval.add(wso.obj);
        }
    }
    return rval;
}
/**
 * handy getter for the current approximate size. Only approx. because
 * this is only updated during the sweep cycle
 */
public  long getCurrentActiveCount() { return  currentActiveCount;};
/**
 * handy getter for the number of full content searches done.
 * use this to make sure we are NOT doing this often.
 */
public  long getNumberSlowSearches() { return  numSlowSearches;};
/**
 * return number of entries in the cache
 */
public  int size() { return theCache.size();} 

/**
 * Removes all entries in this cache.
 */
    public void clear() {
        theCache.clear();
    }

/**
 * returns a hashtable of handy-dandy statistics useful for calculating  and reporting
 * things like ratio of hits to misses, so the sweep cycle can be adjusted.
 */
public  HashMap getStatistics()
{
    HashMap rval = new HashMap(10);
    rval.put("interval", new Long(mySweepInterval));
    rval.put("sweeps", new Long(numSweeps));
    rval.put("hits", new Long(numHits));
    rval.put("misses", new Long(numMiss));
    rval.put("size", new Long(theCache.size()));
    rval.put("slowsrch", new Long (numSlowSearches ));
    rval.put("approxActiveCount", new Long(currentActiveCount));
    return rval;
}
/**
 * write out a quick dump of the cache contents and status
 */
public  void quickDump()
{
    System.out.println("quick dump");
    synchronized(theCache) {
        Collection wsoColl = theCache.values();
        for (Iterator it = wsoColl.iterator(); it.hasNext(); ) {
            WorkingSetObject wso =  (WorkingSetObject) it.next();
            System.out.println(( wso.obj == null ) ? "null" :  wso.obj.toString() + " used: " + wso.usedThisCycle);
        }
    }
    System.out.println("stats: " + getStatistics().toString() +"\n");
}
/**
 * standard testing driver
 */
public static void main(String argss[]) {
    WorkingSetCache wsc = new WorkingSetCache();
    wsc.put("key1", "value1");
    wsc.put("key3", "value3");
    wsc.put("key2", "value2");
    System.out.println("Contains test for " + "value3" + " = " + ((wsc.contains("value3")) ? "yes" : "no") );
    Object key = wsc.getKeyForValue("value2");
    System.out.println("Contains key for " + "value2" + " = " + key );
    wsc.quickDump();
    System.exit(0);
}

} // end WorkingSetCache


/**
 * local class that contains the real object and the inUse flag
 */
class WorkingSetObject {
    boolean usedThisCycle;
    Object obj;
    WorkingSetObject(Object rhs) {
        usedThisCycle = true;
        obj = rhs;
    }
}