/*
 * @(#)HashCache.java
 *
 * Copyright (C) 2003 Matt Albrecht
 * groboclown@users.sourceforge.net
 * http://groboutils.sourceforge.net
 *
 *  Permission is hereby granted, free of charge, to any person obtaining a
 *  copy of this software and associated documentation files (the "Software"),
 *  to deal in the Software without restriction, including without limitation
 *  the rights to use, copy, modify, merge, publish, distribute, sublicense,
 *  and/or sell copies of the Software, and to permit persons to whom the 
 *  Software is furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be included in 
 *  all copies or substantial portions of the Software. 
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL 
 *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 *  DEALINGS IN THE SOFTWARE.
 */

package net.sourceforge.groboutils.util.datastruct.v1;


import java.util.Hashtable;
import java.util.Enumeration;


/**
 * Stores objects that are created via a unique key in a limited-sized
 * cache.  The objects are retrieved and created through the key.  If the
 * object with a requested key exists in the cache, then it is returned
 * and the object is marked as the latest accessed object.  If a request
 * is made for an object whose key is not in the cache, then the object
 * is created, put into the cache, and returned.  If the cache is full
 * when a new object is created, then the oldest item in the cache is
 * removed.
 * <P>
 * This class is NOT thread safe.  All thread safety issues will need to
 * be covered by the calling class.
 * <P>
 * Future versions should use the ObjectCache to cache the node instances.
 *
 * @author     Matt Albrecht <a href="mailto:groboclown@users.sourceforge.net">groboclown@users.sourceforge.net</a>
 * @since      May 23, 2003
 * @version    $Date: 2003/05/23 22:37:57 $
 */
public class HashCache
{
    /**
     * An interface which needs to be implemented and given to the
     * cache in order to create new instances.  It also allows for
     * created objects to be cleaned up.
     */
    public static interface ObjectManager
    {
        /**
         * Called when a new object needs to be created.
         *
         * @param key the key associated with the created object.
         * @return the newly created object
         */
        public Object createObject( Object key );
        
        
        /**
         * Called when the given object is being removed from the cache.
         *
         * @param key the key associated with the object.
         * @param obj the object being cleaned up.
         */
        public void cleanUpObject( Object key, Object obj );
    }
    
    
    /**
     * An inner class used for maintaining the chain of ownership.
     * Uses a doubly-linked list, so that each node can remove itself.
     */
    private static class Node
    {
        public Object key;
        public Object value;
        
        public Node next;
        public Node prev;
        
        public Node( Object key, Object value )
        {
            this.key = key;
            this.value = value;
        }
        
        
        /* used with the printChain method below
        public String toString()
        {
            return "node ["+this.value+"]";
        }
        */
    }
    
    
    /**
     * We also need to keep the object created.
     */
    private ObjectManager mgr;
    
    /**
     * Maximum size of the cache.
     */
    private int maxSize;
    
    
    /**
     * The head of our list of cached elements.
     */
    private Node head;
    
    
    /**
     * The tail of our list of cached elements.
     */
    private Node tail;
    
    
    /**
     * Our quick-reference to the list elements.
     */
    private Hashtable keyToNode = new Hashtable();
    
    
    /**
     * For metrics.
     */
    private int overflowCount = 0;
    
    
    //-----------------------------------------------------
    // Constructors
    
    
    /**
     * Create a new HashCache.
     *
     * @param om the manager for creating and cleaning up the objects.  This
     *      cannot be null.
     * @param maxSize the maximum size of the cache.  This must be &gt; 1
     *      (this is for performance reasons).
     */
    public HashCache( ObjectManager om, int maxSize )
    {
        if (om == null)
        {
            throw new IllegalArgumentException("no null args");
        }
        if (maxSize <= 1)
        {
            throw new IllegalArgumentException("size must be > 1");
        }
        
        this.mgr = om;
        this.maxSize = maxSize;
    }
    

    
    //-----------------------------------------------------
    // Public methods
    
    
    /**
     * Retrieves an item from the cache with the given key.  If the
     * object doesn't exist, then it is created, added to the cache,
     * and returned.  If it does exist, the cached version is returned
     * and marked as the most recently found.  If it was created,
     * and the cache is full, then the oldest retrieved object is
     * removed and cleaned up.
     */
    public Object get( Object key )
    {
        Node n = (Node)this.keyToNode.get( key );
        if (n == null)
        {
            // must include the equals, because we're going to add
            // another element to the list.  An "if" statement would
            // take roughly the same amount of time, but is less safe.
            while (getSize() >= getMaxSize())
            {
                Node last = removeTail();
                this.keyToNode.remove( last.key );
                cleanup( last );
                ++this.overflowCount;
            }
            n = createObject( key );
            this.keyToNode.put( key, n );
        }
        freshenNode( n );
        return n.value;
    }
    
    
    /**
     * Retrieves the current number of elements in the cache.
     *
     * @return the current size of the cache.
     */
    public int getSize()
    {
        //System.out.println("size = "+this.keyToNode.size());
        return this.keyToNode.size();
    }
    
    
    /**
     * Retrieves the maximum cache size.
     *
     * @return the maximum cache size.
     */
    public int getMaxSize()
    {
        //System.out.println("maxsize = "+this.maxSize);
        return this.maxSize;
    }
    
    
    /**
     * Retrieves the metric that corresponds to the number of objects
     * that were removed from the cache.
     *
     * @return the overflow count.
     */
    public int getOverflowCount()
    {
        return this.overflowCount;
    }
    
    
    /**
     * Resets the overflow count metric.
     */
    public void resetOverflowCount()
    {
        this.overflowCount = 0;
    }
    
    
    /**
     * Cleans out the data structure, calling the clean-up on all items.
     * The manager and max size will not be changed, nor will the overflow
     * count.
     */
    public void clear()
    {
        this.head = null;
        this.tail = null;
        Enumeration enum = this.keyToNode.keys();
        while (enum.hasMoreElements())
        {
            Object key = enum.nextElement();
            Node n = (Node)this.keyToNode.remove( key );
            cleanup( n );
        }
    }
    
    
    
    //-----------------------------------------------------
    // Protected methods
    
    
    /**
     * Generates an Object for the cache, but does not add it to the
     * hashtable or lists.
     */
    private Node createObject( Object key )
    {
        Object o = this.mgr.createObject( key );
        Node n = new Node( key, o );
        return n;
    }
    
    
    /**
     * Call the cleanup on the given node.
     */
    private void cleanup( Node n )
    {
        this.mgr.cleanUpObject( n.key, n.value );
    }
    
    
    /**
     * Removes the tail node.  If the list is empty or has 1 element, then an
     * IllegalStateException is thrown.
     *
     * @return the last node in the list.
     */
    private Node removeTail()
    {
        /*
        // temp test code
        if (this.tail == null)
        {
            throw new IllegalStateException("list is empty");
        }
        */
        
        Node n = this.tail;
        this.tail = n.prev;
        n.prev = null;
        tail.next = null;
        
        /*
        // temp test code
        if (this.tail == null)
        {
            throw new IllegalStateException("invalid tail setup: size < 1");
        }
        if (n.next != null)
        {
            throw new IllegalStateException("next of old tail node "+n+" is not null, but "+n.next);
        }
        */
        
        return n;
    }
    
    
    /**
     * Move the given node to the top of the list.  This works even if the
     * given node is not in the list.
     */
    private void freshenNode( Node n )
    {
        /*
        // temp test code
        if (n == null)
        {
            throw new IllegalArgumentException("no null args");
        }
        */
        
        if (n == this.head)
        {
            // we're done!
            return;
        }
        
        if (this.head == null)
        {
            // n's next and prev better be null!
            this.head = n;
            this.tail = n;
            
            /*
            // temp test code
            if (n.next != null || n.prev != null)
            {
                throw new IllegalStateException("new head&tail node "+n+" next is "+n.next+", prev is "+n.prev);
            }
            */
        }
        else
        {
            // setup tail, and next and prev of n's next and prev
            if (n.prev != null)
            {
                n.prev.next = n.next;
            }
            
            if (n.next != null)
            {
                n.next.prev = n.prev;
            }
            else
            if (this.tail == n)
            {
                this.tail = n.prev;
                
                // n.prev better not be null!  that should have been trapped
                // above.
                /*
                // temp test code
                if (n.prev == null)
                {
                    throw new IllegalStateException("new tail's previous is null!");
                }
                */
            }
            
            n.prev = null;
            
            // the head is going to be not null, due to the if block above
            this.head.prev = n;
            n.next = this.head;
            
            this.head = n;
        }
    }
    
    
    /* Integrety check.  Uncomment when doing testing.
    protected void printChain()
    {
        if (this.head == null)
        {
            System.out.println("[Empty chain]");
            return;
        }
        Hashtable seen = new Hashtable();
        
        System.out.println("Chain:");
        Node n = this.head;
        while (n != null)
        {
            seen.put( n, new Object() );
            System.out.println("    "+n);
            Node n2 = n.next;
            if (n2 != null && n2.prev != n)
            {
                throw new IllegalStateException("Bad back chain! next = "+n2+
                    ", but its prev = "+n2.prev);
            }
            else
            if (n2 == null && n != this.tail)
            {
                throw new IllegalStateException("Broken Chain!  next is null but tail isn't this node (it's "+this.tail+")");
            }
            else
            if (n2 != null && seen.contains( n2 ))
            {
                throw new IllegalStateException("node "+n2+" in the list twice.");
            }
            if (n2 != null && n == this.tail)
            {
                throw new IllegalStateException("Tail in a loop!");
            }
            n = n2;
        }
        System.out.println("[End chain]");
    }
    */
}