Least Recently Used Algorithm in Ruby

gist.ruby

Node = Struct.new(:value, :prev_node, :next_node)

class LRU
  attr_accessor :head, :tail, :num_items, :max_items

  def initialize(max_items)
    @max_items = max_items
    @head, @tail = nil
    @table = {}
    @num_items = 0
  end

  def set(key, value)
    @num_items += 1
    @head = @head.next_node if @num_items > @max_items
    new_node = Node.new value, @tail, nil

    @tail.nil? ? @head = new_node : @tail.next_node = new_node
    @tail = new_node
    @table[key] = new_node
  end

  def get(key)
    res = @table[key]
    return res if res.next_node.nil?

    if !res.prev_node.nil?
      res.prev_node.next_node = res.next_node
      res.next_node.prev_node = res.prev_node
    else
      @head = res.next_node
      @head.prev_node = nil
    end

    @tail.next_node = res
    res.prev_node = @tail
    res.next_node = nil
    @tail = res
  end
end