Last active
March 19, 2019 17:38
-
-
Save Slike9/e0e50dea4c565bd50441bcea1d7e34d5 to your computer and use it in GitHub Desktop.
lru.rb
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
| # frozen_string_literal: true | |
| class DoubleLinkedList | |
| include Enumerable | |
| def initialize | |
| @head_guard = { prev: nil } | |
| @tail_guard = { prev: @head_guard, next: nil } | |
| @head_guard[:next] = @tail_guard | |
| end | |
| def append_node(node) | |
| node[:next] = @tail_guard | |
| node[:prev] = @tail_guard[:prev] | |
| @tail_guard[:prev][:next] = node | |
| @tail_guard[:prev] = node | |
| end | |
| def delete_node(node) | |
| node[:prev][:next] = node[:next] | |
| node[:next][:prev] = node[:prev] | |
| end | |
| def head | |
| @head_guard[:next] if @head_guard[:next] != @tail_guard | |
| end | |
| def move_node_to_tail(node) | |
| delete_node(node) | |
| append_node(node) | |
| end | |
| def each | |
| node = @head_guard[:next] | |
| while node != @tail_guard | |
| yield node | |
| node = node[:next] | |
| end | |
| end | |
| end | |
| class LRU | |
| def initialize(limit) | |
| @limit = 5 | |
| @entry_hash = {} | |
| @entries = DoubleLinkedList.new | |
| end | |
| # if LRU_LIMIT_VALUES cached already, the least-recently inserted/read k,v should be evicted | |
| # and key,value passed here should be "farthest" from eviction | |
| def insert(key, value) | |
| entry = @entry_hash[key] | |
| if entry | |
| update_entry(entry, value) | |
| else | |
| add_entry(key, value) | |
| end | |
| end | |
| # The value read should now be the one "farthest" from eviction | |
| def read(key) | |
| entry = @entry_hash[key] | |
| return unless entry | |
| renew_entry(entry) | |
| entry[:value] | |
| end | |
| def size | |
| @entry_hash.size | |
| end | |
| def inspect | |
| @entries.map { |entry| entry.values_at(:key, :value) }.to_h.inspect | |
| end | |
| private | |
| def update_entry(entry, value) | |
| renew_entry(entry) | |
| entry[:value] = value | |
| end | |
| def add_entry(key, value) | |
| delete_oldest_entry if size == @limit | |
| entry = @entries.append_node(key: key, value: value) | |
| @entry_hash[key] = entry | |
| end | |
| def renew_entry(entry) | |
| @entries.move_node_to_tail(entry) | |
| end | |
| def delete_oldest_entry | |
| oldest_entry = @entries.head | |
| @entries.delete_node(oldest_entry) | |
| @entry_hash.delete(oldest_entry[:key]) | |
| end | |
| end | |
| require 'minitest/autorun' | |
| class LRUTest < Minitest::Test | |
| def setup | |
| @cache = LRU.new(5) | |
| end | |
| def test_empty_cache | |
| assert_nil @cache.read(:a) | |
| end | |
| def test_insert | |
| @cache.insert(:a, 10) | |
| assert_equal 10, @cache.read(:a) | |
| end | |
| def test_replaces_oldest_entry | |
| 5.times do |key| | |
| @cache.insert(key, key) | |
| end | |
| @cache.insert(5, 5) | |
| assert_nil @cache.read(0) | |
| (1..5).each do |key| | |
| assert_equal key, @cache.read(key) | |
| end | |
| end | |
| def test_reading_renews_the_entry | |
| 5.times do |key| | |
| @cache.insert(key, key) | |
| end | |
| @cache.read(0) | |
| @cache.insert(5, 5) | |
| assert_nil @cache.read(1) | |
| ([0] + (2..5).to_a).each do |key| | |
| assert_equal key, @cache.read(key) | |
| end | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment