Created
March 4, 2018 00:06
-
-
Save godspeedyoo/5d40d3e79f4e1d1fd4dabfed36d9c8cc to your computer and use it in GitHub Desktop.
LRU cache in ruby with doubly linked list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class LRU | |
attr_reader :max, :head, :tail, :data | |
def initialize(max = 5) | |
@max = max | |
@data = {} | |
end | |
def set(key, value) | |
evict if data.size == max | |
node = Node.new(value) | |
if head | |
head.prev_node = node | |
node.next_node = head | |
# head should now become tail when growing from size 1 to 2 | |
if head.next_node.nil? | |
@tail = head | |
end | |
end | |
@head = node | |
data[key] = node | |
end | |
def get(key) | |
node = data[key] | |
return node if node == head | |
return node if node.nil? | |
if tail == node | |
# set new tail | |
node.prev_node.next_node = nil | |
@tail = node.prev_node | |
else | |
node.prev_node.next_node = node.next_node | |
node.next_node.prev_node = node.prev_node | |
end | |
node.prev_node = nil | |
node.next_node = head | |
@head = node | |
node | |
end | |
private | |
def evict | |
if tail | |
remove_key_of(tail) | |
tail = tail.prev_node if tail | |
tail.next_node = nil | |
else | |
remove_key_of(tail) | |
@head = nil | |
end | |
end | |
def remove_key_of(node) | |
data.delete(data.key(node)) | |
end | |
class Node | |
attr_accessor :value, :prev_node, :next_node | |
def initialize(value) | |
@value = value | |
end | |
end | |
end | |
lru = LRU.new(1) | |
lru.set('google', 'http://www.google.com') | |
### SET | |
# when there is no data, sets value as head | |
puts "1: #{lru.head.value == 'http://www.google.com'}" | |
# when data is full, sets new value as head | |
lru.set('reddit', 'http://www.reddit.com') | |
puts "2: #{lru.head.value == 'http://www.reddit.com'}" | |
# when data is not full and head already exists, sets tail correctly | |
lru = LRU.new(2) | |
lru.set('google', 'http://www.google.com') | |
lru.set('reddit', 'http://www.reddit.com') | |
puts "3: #{lru.tail.value == 'http://www.google.com'}" | |
### GET | |
# gets the correct value | |
puts "4: #{lru.get('reddit').value == 'http://www.reddit.com'}" | |
puts "5: #{lru.get('google').value == 'http://www.google.com'}" | |
# when getting a key that is not head, sets that as new head | |
puts "6: #{lru.head.value == 'http://www.google.com'}" | |
lru.get('google') # access google, head should become google | |
puts "7: #{lru.head.value == 'http://www.google.com'}" | |
# returns nil if not found in cache | |
puts "8: #{lru.get('invalid') == nil}" | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment