LRU Cache Implementation

examples.rb

# Create the LRU cache
cache = LRUCache.new(max_size: 3)

# adding a key value pair adds the vaue to the highest priority position
cache.add(:a, 'a')
cache.add(:b, 'b')
cache.add(:c, 'c')
cache.to_a # => ["c", "b", "a"]
cache.size # => 3

# accessing a key value pair moves that value to the highest priority position
cache.get(:b)
cache.to_a # => ["b", "c", "a"]

# adding beyond cache size removes the key value pair in the lowest priority position
cache.add(:d, 'd')
cache.to_a # => ["d", "c", "b"]
cache.size # => 3

# removing a key value pair reduces the size of the cache
cache.remove(:b)
cache.to_a # => ["d", "c"]
cache.size # => 2

linked_list.rb

class ListNode < Node

  protected :remove # prevent removal from external sources

  def initialize
    @next = @prev = self
  end

  def head
    @next unless @next == self
  end

  def tail
    @prev unless @prev == self
  end

  def add_to_head(node)
    node.insert_after(self)
  end

  def add_to_tail(node)
    node.insert_after(self.prev)
  end

  def each(&block)
    # http://blog.arkency.com/2014/01/ruby-to-enum-for-enumerator/
    return enum_for(:each) unless block_given?

    node = @next
    while node != self
      yield node
      node = node.next
    end
  end

  def to_a
    each.collect {|node| node.value }
  end

end

lru_cache.rb

class LRUCache

  def initialize(max_size:)
    @list = ListNode.new
    @map = {}.with_indifferent_access
    @max_size = max_size
  end

  def add(key, value)
    if (node = @map[key])
      @list.add_to_head(node)
    else
      if @map.size >= @max_size
        node = @list.tail
        node.remove
        @map.delete(node.key)
      end
      @map[key] = @list.add_to_head(LRUCacheNode.new(key, value))
    end
  end

  def get(key)
    if (node = @map[key])
      @list.add_to_head(node)
      node
    end
  end

  def remove(key)
    if (node = @map.delete(key))
      node.remove
      node
    end
  end

  def size
    @map.size
  end

  def to_a
    @list.to_a
  end
end

node_types.rb

class Node
  protected
  attr_accessor :next, :prev

  public
  attr_reader :value, :next, :prev

  def initialize(value)
    @value = value
  end

  def inspect
    "#<Node @value=#{value.inspect}>"
  end

  def remove
    @prev.next = @next if @prev
    @next.prev = @prev if @next
    @next = @prev = nil
  end

  def move_after(node)
    remove

    @next = node.next
    @next.prev = self if @next
    @prev = node
    node.next = self
  end
end

# The LRUCacheNode includes a key that indentifies the node for use within an LRUCache.
class LRUCacheNode < Node

  attr_reader :key

  def initialize(key, value)
    super(value)
    @key = key
  end
end