class Hashery::LRUHash

# File lib/hashery/lru_hash.rb, line 30
def initialize(max_size, default_value=nil, &block)
  @max_size     = normalize_max(max_size)
  @default      = default_value
  @default_proc = block

  @h = {}
  @head = Node.new
  @tail = front(Node.new)
end

# File lib/hashery/lru_hash.rb, line 114
def [](key)
  fetch(key) do |k|
    @default_proc ? @default_proc[self, k] : default
  end
end

# File lib/hashery/lru_hash.rb, line 165
def assoc(key)
  n = @h[key]

  if n
    front(n)
    [n.key, n.value]
  end
end

# File lib/hashery/lru_hash.rb, line 253
def clear
  until empty?
    delete_oldest
  end

  self
end

# File lib/hashery/lru_hash.rb, line 224
def delete(key)
  n = @h[key] and remove_node(n).value
end

# File lib/hashery/lru_hash.rb, line 231
def delete_if
  each_node do |n|
    remove_node n if yield n.key, n.value
  end
end

# File lib/hashery/lru_hash.rb, line 61
def each_key
  if block_given?
    each_node do |n|
      yield n.key
    end
  else
    enum_for :each_key
  end
end

# File lib/hashery/lru_hash.rb, line 43
def each_pair
  if block_given?
    each_node do |n|
      yield [n.key, n.value]
    end
  else
    enum_for :each_pair
  end
end

# File lib/hashery/lru_hash.rb, line 74
def each_value
  if block_given?
    each_node do |n|
      yield n.value
    end
  else
    enum_for :each_value
  end
end

# File lib/hashery/lru_hash.rb, line 94
def empty?
  @head.succ.equal? @tail
end

# File lib/hashery/lru_hash.rb, line 101
def fetch(key, &b)
  n = @h[key]

  if n
    front(n).value
  else
    (b || FETCH)[key]
  end
end

# File lib/hashery/lru_hash.rb, line 137
def has_key?(key)
  @h.has_key? key
end

# File lib/hashery/lru_hash.rb, line 148
def has_value?(value)
  each_pair do |k, v|
    return true if value.eql? v
  end

  false
end

# File lib/hashery/lru_hash.rb, line 190
def key(value)
  pair = rassoc(value) and pair.first
end

# File lib/hashery/lru_hash.rb, line 123
def keys
  @h.keys
end

# File lib/hashery/lru_hash.rb, line 240
def max_size=(limit)
  limit = normalize_max(limit)

  while size > limit
    delete_oldest
  end

  @max_size = limit
end

# File lib/hashery/lru_hash.rb, line 177
def rassoc(value)
  each_node do |n|
    if value.eql? n.value
      front(n)
      return [n.key, n.value]
    end
  end
  nil
end

# File lib/hashery/lru_hash.rb, line 87
def size
  @h.size
end

# File lib/hashery/lru_hash.rb, line 197
def store(key, value)
  # same optimization as in Hash
  key = key.dup.freeze if String === key && !key.frozen?

  n = @h[key]

  unless n
    if size == max_size
      # reuse node to optimize memory usage
      n = delete_oldest
      n.key = key
      n.value = value
    else
      n = Node.new key, value
    end

    @h[key] = n
  end

  front(n).value = value
end

# File lib/hashery/lru_hash.rb, line 264
def to_s
  s = nil
  each_pair {|k, v| (s ? (s << ', ') : s = '{') << k.to_s << '=>' << v.to_s}
  s ? (s << '}') : '{}'
end

# File lib/hashery/lru_hash.rb, line 130
def values
  @h.map {|k,n| n.value}
end

# File lib/hashery/lru_hash.rb, line 158
def values_at(*key_list)
  key_list.map {|k| self[k]}
end

# File lib/hashery/lru_hash.rb, line 314
def delete_oldest
  n = @tail.pred
  raise "Cannot delete from empty hash" if @head.equal? n
  remove_node n
end

# File lib/hashery/lru_hash.rb, line 277
def each_node
  n = @head.succ

  until n.equal? @tail
    succ = n.succ
    yield n
    n = succ
  end

  self
end

# File lib/hashery/lru_hash.rb, line 294
def front(node)
  node.insert_after(@head)
end

# File lib/hashery/lru_hash.rb, line 327
def normalize_max(n)
  n = n.to_i
  raise ArgumentError, 'Invalid max_size: %p' % n unless Integer === n && n > 0
  n
end

# File lib/hashery/lru_hash.rb, line 304
def remove_node(node)
  n = @h.delete(node.key)
  n.unlink
  release_proc and release_proc[n.key, n.value]
  n
end