##
# A least recently used cache

class Borges::LRUCache

  ##
  # The default capacity of the LRUCache.

  DEFAULT_CAPACITY = 20

  ##
  # The number of items the LRUCache can hold.

  attr_accessor :capacity

  ##
  # Create a new LRUCache that can accomodate up to +capacity+
  # objects.

  def initialize(capacity = DEFAULT_CAPACITY)
    @capacity = capacity
    @table = {}
    @age_array = []
  end

  ##
  # Returns the number of items stored in the LRUCache.

  def size
    return @table.size
  end

  ##
  # Stores +object+ in the cache, returning a key that can be
  # used to retrive it.

  def store(object)
    key = next_key
    self[key] = object
    return key
  end

  ##
  # Fetches +key+ from the LRUCache.

  def fetch(key)
    return self[key]
  end

  private

  ##
  # Creates a new key for storing cache entries.

  def next_key
    key = nil
    while @table.key?(key = Borges::ExternalID.create) do end
    return key
  end

  ##
  # Sets cache entry +key+ to +val+, bumping an item out of the
  # cache if it is bigger than @capacity.

  def []=(key,val)
    @table[key] = val
    @age_array << key
    if @age_array.length > capacity then
      @table.delete @age_array[0]
      @age_array.delete_at 0
    end
    return val
  end

  ##
  # Retrieves cache item +key+, and sets it as the most recently
  # accessed item.

  def [](key)
    val = @table[key]
    @age_array.delete key
    @age_array << key if val
    return val
  end

end # class Borges::LRUCache