CollectionImprovements: Cache.d

/++
    author: Darryl Bleau

    Generic LRU Cache. 

    Makes a cache that has an upper limit, and the items least used will be removed. Putting an item doesn't gurantee that it will be in there later.

    Example
    ---
        auto myCache = new Cache!(char[], char[])(3);
        myCache["one"] = "1";
        myCache["two"] = "2";
        myCache["three"] = "3";
        Stdout(myCache["one"], myCache["two"], myCache["three"]).newline;
    ---
++/

module tetra.util.Cache;

import tetra.util.container.Hash;
import tetra.util.container.List;

/++
    Cache class...
++/
public class Cache(K,V)
{
    private struct cacheReference
    {
        K key;
        V value;    
    }   
    
    private Hash!(K,Item!(cacheReference)) chash;
    private List!(cacheReference) mru;
    private int _size;
    /++ Property containing the maximum number of items that this cache will hold. ++/
    int size()  { return this._size; }
    void size(int size) { this._size = size; }
    
    /++
        Add an item to the cache

        Params:
            key = the key to the item
            value = the value to the item
    ++/
    final void add(K key, V value)
    {
        Item!(cacheReference) item = chash[key];
        if (item !is null)
            item.data.value = value;
        else
        {
            if (mru.length == _size)
            {
                Item!(cacheReference) lastItem = mru.lastItem;
                mru.remove(lastItem);
                chash.remove(lastItem.data.key);
            }
            cacheReference newReference;
            newReference.key = key;
            newReference.value = value;
            Item!(cacheReference) newItem = new Item!(cacheReference)(newReference);
            chash[key] = newItem;
            mru.first = newItem; // Idea: perhaps newly added items should be added to the middle of the mru?
        }
    }
    /++
        Operator to allow blah[key] = value
    ++/
    final void opIndexAssign(V value, K key) { this.add(key, value); }

    /++
        The number of items currently in the cache
    ++/
    final int length()
    {
        return mru.length;  
    }
    
    /++
        remove an item from the cache based on the key

        Params:
            key = the key of the item to remove.
    ++/
    final void remove(K key)
    {
        Item!(cacheReference) item = chash[key];
        if (item !is null)
        {
            mru.remove(item);
            chash.remove(key);
        }
    }
    
    /++
        Operator that allows foreach. Returns the key
    ++/
    int opApply(int delegate(inout K key) dg)
    {
        int result;
        foreach(cacheReference cr; mru)
        {
            if ((result = dg(cr.key)) != 0)
                break;
        }
        return result;
    }
    /++
        Operator that allows reverse foreach, returns the key
    ++/
    int opApplyReverse(int delegate(inout K key) dg)
    {
        int result;
        foreach_reverse(cacheReference cr; mru)
        {
            if ((result = dg(cr.key)) != 0)
                break;
        }
        return result;
    }
    /++
        Operator that allows foreach, returns key and value
    ++/
    int opApply(int delegate(inout K key, inout V value) dg)
    {
        int result;
        foreach(cacheReference cr; mru)
        {
            if ((result = dg(cr.key, cr.value)) != 0)
                break;
        }
        return result;
    }   
    /++
        Operator that allows reverse foreach, returns key and value
    ++/
    int opApplyReverse(int delegate(inout K key, inout V value) dg)
    {
        int result;
        foreach_reverse(cacheReference cr; mru)
        {
            if ((result = dg(cr.key, cr.value)) != 0)
                break;
        }
        return result;
    }
    
    /++
        Returns a float representing how full the cache is.
    ++/
    float load()
    {
        return cast(float)(cast(float)this.length / cast(float)this.size);  
    }
    
    /++
        Operator to allow access of values via index: auto val = myCache["blah"];
    ++/
    final V opIndex(K key)
    {
        V rtn;
        Item!(cacheReference) item = cast(Item!(cacheReference))cast(void*)chash[key];
        if (item !is null)
        {
            mru.remove(item);
            mru.first = item;
            rtn = item.data.value;
        }
        return rtn;
    }
    
    /++
        Operator to check if the key exists in the cache: if ("blah" in myCache") {}
    ++/
    final bool opIn_r(K key)
    {
        return (key in chash);
    }
    
    /++
        Create a new cache

        Params:
            size = the initial size of the cache
    ++/
    this(int size)
    {
        if (size > 0)
        {
            chash = new Hash!(K,Item!(cacheReference));
            mru = new List!(cacheReference);
            _size = size;
        }
        else
            throw new Exception("Cache size must be greater than zero.");
    }
}

version(Test)
{
    import tetra.util.Test;
    import tango.io.Stdout;
    unittest
    {
        Test.Status basicFunctionality(inout char[][] messages)
        {
            auto myCache = new Cache!(char[], char[])(3);
            myCache["one"] = "1";
            myCache["two"] = "2";
            myCache["three"] = "3";
            myCache["one"];
            myCache["two"];
            myCache.remove("two");
            myCache["four"] = "4";
            myCache["five"] = "5";
            if (myCache["one"] == "1" && myCache["two"] == null && myCache["three"] == null && myCache["four"] == "4" && myCache["five"] == "5" && myCache.length == 3 && myCache.size == 3)            
            {
                bool a, b, c;
                foreach(char[] key, char[] value; myCache)
                {
                    if (key == "one" && value == "1")
                        a = true;
                    else if (key == "four" && value == "4")
                        b = true;
                    else if (key == "five" && value == "5")
                        c = true;
                    else
                        break;
                }
                if (a && b && c)
                {
                    if (myCache.load == 1.00)
                        return Test.Status.Success;
                }
            }
            return Test.Status.Failure;
        }

        auto t = new Test("tetra.util.Cache");
        t["Basic functionality"] = &basicFunctionality;
        t.run();
    }
}