* Adds a new Cacheable object to the cache. The key must be unique.
     *
     * @param key a unique key for the object being put into cache.
     * @param object the Cacheable object to put into cache.
     */
    public synchronized void add(long key, Cacheable object) {
        // Delete an old entry if it exists.
        remove(key);

        int objectSize = object.getSize();
        // If the object is bigger than the entire cache, simply don't add it.
        if (objectSize > maxObjectSize) {
            return;
        }
        size += objectSize;
        LongCacheObject cacheObject = new LongCacheObject(object, objectSize);
        cachedObjectsHash.put(key, cacheObject);
        // Make an entry into the cache order list.
        LongLinkedListNode lastAccessedNode = lastAccessedList.addFirst(key);
        // Store the cache order list entry so that we can get back to it
        // during later lookups.
        cacheObject.lastAccessedListNode = lastAccessedNode;
        // Add the object to the age list
        LongLinkedListNode ageNode = ageList.addFirst(key);
        // We make an explicit call to currentTimeMillis() so that total accuracy
        // of lifetime calculations is better than one second.
        ageNode.timestamp = System.currentTimeMillis();
        cacheObject.ageListNode = ageNode;

        // If cache is too full, remove least used cache entries until it is
        // not too full.
        if (size >= maxSize) {
            cullCache();
        }
    }

    /**
     * Gets an object from cache. This method will return null under two
     * conditions:<ul>
     *    <li>The object referenced by the key was never added to cache.
     *    <li>The object referenced by the key has expired from cache.</ul>
     *
     * @param key the unique key of the object to get.
     * @return the Cacheable object corresponding to unique key.
     */
    public synchronized Cacheable get(long key) {
        // First, clear all entries that have been in cache longer than the
        // maximum defined age.
        deleteExpiredEntries();

        LongCacheObject cacheObject = (LongCacheObject)cachedObjectsHash.get(key);
        if (cacheObject == null) {
            // The object didn't exist in cache, so increment cache misses.
            cacheMisses++;
            return null;
        }

        // The object exists in cache, so increment cache hits.
        cacheHits++;

        // Remove the object from it's current place in the cache order list,
        // and re-insert it at the front of the list.
        cacheObject.lastAccessedListNode.remove();
        lastAccessedList.addFirst(cacheObject.lastAccessedListNode);

        return cacheObject.object;
    }

    /**
     * Removes an object from cache.
     *
     * @param key the unique key of the object to remove.
     */
    public synchronized void remove(long key) {
        LongCacheObject cacheObject = (LongCacheObject)cachedObjectsHash.get(key);
        // If the object is not in cache, stop trying to remove it.
        if (cacheObject == null) {
            return;
        }
        // remove from the hash map
        cachedObjectsHash.removeKey(key);
        // remove from the cache order list
        cacheObject.lastAccessedListNode.remove();
        cacheObject.ageListNode.remove();
        // remove references to linked list nodes
        cacheObject.ageListNode = null;
        cacheObject.lastAccessedListNode = null;
        // removed the object, so subtract its size from the total.
        size -= cacheObject.size;
    }

    /**
     * Clears the cache of all objects. The size of the cache is reset to 0.
     */
    public synchronized void clear() {
        long [] keys = cachedObjectsHash.keys();
        for (int i=0; i<keys.length; i++) {
            remove(keys[i]);
        }

        // Now, reset all containers.
        cachedObjectsHash.clear();
        // cachedObjectsHash = new HashMap(103);
        lastAccessedList.clear();
        lastAccessedList = new LongLinkedList();
        ageList.clear();
        ageList = new LongLinkedList();

        size = 0;
        cacheHits = 0;
        cacheMisses = 0;
    }

    /**
     * Returns an array of the keys contained in the cache.
     *
     * @return an array of the keys present in the cache.
     */
    public long [] keys() {
        return cachedObjectsHash.keys();
    }

    /**
     * Returns an array of the values contained in the cache.
     *
     * @return a array of the cache entries.
     */
    public Object [] values() {
        Object [] cacheObjects = cachedObjectsHash.values();
        Object [] values = new Object[cacheObjects.length];
        for (int i=0; i<cacheObjects.length; i++) {
            values[i] = ((LongCacheObject)cacheObjects[i]).object;
        }
        return values;
    }

    /**
     * Returns the number of cache hits. A cache hit occurs every
     * time the get method is called and the cache contains the requested
     * object.<p>
     *
     * Keeping track of cache hits and misses lets one measure how efficient
     * the cache is; the higher the percentage of hits, the more efficient.
     *
     * @return the number of cache hits.
     */
    public long getCacheHits() {
        return cacheHits;
    }

    /**
     * Returns the number of cache misses. A cache miss occurs every
     * time the get method is called and the cache does not contain the
     * requested object.<p>
     *
     * Keeping track of cache hits and misses lets one measure how efficient
     * the cache is; the higher the percentage of hits, the more efficient.
     *
     * @return the number of cache hits.
     */
    public long getCacheMisses() {
        return cacheMisses;
    }

    /**
     * Clears all entries out of cache where the entries are older than the
     * maximum defined age.
     */
    private final void deleteExpiredEntries() {
        // Check if expiration is turned on.
        if (maxLifetime <= 0) {
            return;
        }

        // Remove all old entries. To do this, we remove objects from the end
        // of the linked list until they are no longer too old. We get to avoid
        // any hash lookups or looking at any more objects than is strictly
        // neccessary.
        LongLinkedListNode node = ageList.getLast();
        // If there are no entries in the age list, return.
        if (node == null) {
            return;
        }

        // Determine the expireTime, which is the moment in time that elements
        // should expire from cache. Then, we can do an easy to check to see
        // if the expire time is greater than the expire time.
        long expireTime = currentTime - maxLifetime;

        while(expireTime > node.timestamp) {
            // Remove the object
            remove(node.key);

            // Get the next node.
            node = ageList.getLast();
            // If there are no more entries in the age list, return.
            if (node == null) {
                return;
            }
        }
    }

    /**
     * Removes objects from cache if the cache is too full. "Too full" is
     * defined as within 3% of the maximum cache size. Whenever the cache is
     * is too big, the least frequently used elements are deleted until the
     * cache is at least 10% empty.
     */
    private final void cullCache() {
        // First, delete any old entries to see how much memory that frees.
        deleteExpiredEntries();
        final int desiredSize = maxObjectSize;
        while (size > desiredSize) {
            // Get the key and invoke the remove method on it.
            remove(lastAccessedList.getLast().key);
        }
    }
}