class LRUCache

Attributes

hash[R]
linked_list[R]
max_size[RW]
size[RW]

Public Class Methods

new(max_size) click to toggle source
# File lib/data_structures/lru_cache.rb, line 4
def initialize(max_size)
  @max_size = max_size
  @size = 0
  @hash = {}
  @linked_list = LinkedList.new
end

Public Instance Methods

add_after_key(ref_key, key, val) click to toggle source
# File lib/data_structures/lru_cache.rb, line 73
def add_after_key(ref_key, key, val)
  node = @linked_list.add_after_key(ref_key, key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:first)
  else
    @size += 1
  end

  node
end
add_before_key(ref_key, key, val) click to toggle source
# File lib/data_structures/lru_cache.rb, line 86
def add_before_key(ref_key, key, val)
  node = @linked_list.add_before_key(ref_key, key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:last)
  else
    @size += 1
  end

  node
end
append(key, val) click to toggle source
# File lib/data_structures/lru_cache.rb, line 47
def append(key, val)
  node = @linked_list.append(key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:first)
  else
    @size += 1
  end

  node
end
empty?() click to toggle source
# File lib/data_structures/lru_cache.rb, line 23
def empty?
  @size == 0
end
find(key) click to toggle source
# File lib/data_structures/lru_cache.rb, line 39
def find(key)
  @hash[key]
end
first() click to toggle source
# File lib/data_structures/lru_cache.rb, line 31
def first
  @linked_list.first
end
include?(key) click to toggle source
# File lib/data_structures/lru_cache.rb, line 43
def include?(key)
  @hash.has_key?(key)
end
inspect() click to toggle source
# File lib/data_structures/lru_cache.rb, line 19
def inspect
  @linked_list.inspect
end
last() click to toggle source
# File lib/data_structures/lru_cache.rb, line 35
def last
  @linked_list.last
end
length() click to toggle source
# File lib/data_structures/lru_cache.rb, line 27
def length
  @size
end
prepend(key, val) click to toggle source
# File lib/data_structures/lru_cache.rb, line 60
def prepend(key, val)
  node = @linked_list.prepend(key, val)
  @hash[key] = node

  if @size == @max_size
    remove_node(:last)
  else
    @size += 1
  end

  node
end
remove(key) click to toggle source
# File lib/data_structures/lru_cache.rb, line 99
def remove(key)
  node = self.find(key)
  return nil if node.nil?

  @linked_list.remove(key)
  @hash.delete(key)
  @size -= 1

  node
end
to_a() click to toggle source
# File lib/data_structures/lru_cache.rb, line 11
def to_a
  @linked_list.to_a
end
to_s() click to toggle source
# File lib/data_structures/lru_cache.rb, line 15
def to_s
  @linked_list.to_s
end

Private Instance Methods

remove_node(position) click to toggle source
# File lib/data_structures/lru_cache.rb, line 112
def remove_node(position)
  node_key = @linked_list.send(position).send(:key)
  @linked_list.remove(node_key)
  @hash.delete(node_key)
end