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