lru_cache.rb

class LRUCache
  MAX_SIZE = 3

  def initialize
    @cache = {}
    @max_size = MAX_SIZE
    @lru_list = List.new
  end

  def get(key)
    if has_key?(key)
      @lru_list.lift(key)
    end

    @cache[key]
  end

  def has_key?(key)
    @cache.has_key?(key)
  end

  def put(key, value)
    if size >= MAX_SIZE
      @cache.delete lru_key

      @lru_list.pop
    end

    @lru_list.push key
    @cache[key] = value

    value
  end

  def size
    @cache.keys.count
  end

  private

  def lru_key
    @lru_list.last
  end
end

class List
  def initialize
    @head = nil
    @last = nil
    @hash = {}
  end

  def push(value)
    node = ListNode.new(value)
    @hash[value] = node

    if @head
      node.next = @head
      @head.prev = node

      @head = node
    else
      @head = @last = node
    end

    node
  end

  def lift(value)
    node = @hash[value]

    if node
      prev = node.prev
      n = node.next

      if node == @last
        @last = prev
      end

      if prev
        prev.next = n
      end

      if n
        n.prev = prev
      end

      node.prev = nil
      node.next = @head

      @head = node
    end

    node
  end

  def pop
    removed = @last
    @hash.delete removed

    if removed
      @last = removed.prev

      if @last
        @last.next = nil
      end
    end

    removed
  end

  def last
    @last.value
  end
end

class ListNode
  attr_reader :value, :prev, :next
  attr_writer :prev, :next

  def initialize(value)
    @value = value
  end
end

describe LRUCache do
  describe "#put" do
    it "evicts LRU items (writes only)" do
      subject.put :a, "a"
      subject.put :b, "b"
      subject.put :c, "c"
      expect(subject.size).to eq 3
      expect(subject.has_key?(:a)).to eq true
      expect(subject.has_key?(:b)).to eq true
      expect(subject.has_key?(:c)).to eq true

      subject.put :d, "d"
      expect(subject.size).to eq 3
      expect(subject.has_key?(:a)).to eq false
      expect(subject.has_key?(:b)).to eq true
      expect(subject.has_key?(:c)).to eq true
      expect(subject.has_key?(:d)).to eq true
    end

    it "evicts LRU items (with reads)" do
      subject.put :a, "a"
      subject.put :b, "b"
      subject.put :c, "c"

      subject.get :a

      subject.put :d, "d"

      expect(subject.size).to eq 3
      expect(subject.has_key?(:a)).to eq true
      expect(subject.has_key?(:b)).to eq false
      expect(subject.has_key?(:c)).to eq true
      expect(subject.has_key?(:d)).to eq true
    end
  end
end