lru_cache.rb

class LRUCache
  def initialize(max_size)
    @max_size = max_size
  end

  def put(name, value)
    queue << name unless queue.include?(name)
    data[name] = value
    data[queue.shift] = nil if queue.size > @max_size
  end

  def get(name)
    queue << queue.delete(name) if queue.include?(name)
    data[name]
  end

  def size
    queue.size
  end
  
  private
  def queue
    @queue ||= []
  end

  def data
    @data ||= {}
  end
end

lru_cache_spec.rb

require File.join(File.dirname(__FILE__), %w[ .. lib lru_cache ])

describe LRUCache, '.new' do
  it 'の引数で最大サイズが決まる' do
    cache = LRUCache.new(2)
    cache.instance_variable_get(:@max_size).should == 2
  end
end

describe LRUCache, '#put' do
  subject { LRUCache.new(2) }
  
  it 'で値を格納できてgetできる' do
    subject.put('a', '1')
    subject.get('a').should == '1'
  end

  it 'nilもOK' do
    subject.put(nil, '1')
    subject.get(nil).should == '1'
  end

  it 'で値を格納できてgetできる' do
    subject.put('a', '1')
    subject.put('b', '1')
    subject.put('a', '2')
    
    subject.get('a').should == '2'
  end
end

describe LRUCache, '#get' do
  subject { LRUCache.new(2).tap {|c| c.instance_eval { @data = { 'a' => 'b' } } } }

  it 'でそもそもaという値をもったものからgetできる' do
    subject.get('a').should == 'b'
  end

  it 'なのにbをgetしようとしたらないのでnilがかえる' do
    subject.get('b').should == nil
  end
  
end

describe LRUCache, '#size' do
  subject { LRUCache.new(2) }

  it '初期状態はサイズが0' do
    subject.size.should == 0
  end

  it '2つ格納したらサイズは2' do
    subject.put('a','1111')
    subject.put('b','2222')
    
    subject.size.should == 2
  end

  it '3つ格納してもサイズは2' do
    subject.put('a','1111')
    subject.put('b','2222')
    subject.put('c','3333')
    
    subject.size.should == 2
  end
  it '同じ物を格納してもサイズは2' do
    subject.put('a','1111')
    subject.put('b','2222')
    subject.put('b','3333')
    
    subject.size.should == 2
  end
 it 'nilを格納してもサイズは2' do
    subject.put('a','1111')
    subject.put('b','2222')
    subject.put(nil,'3333')
    
    subject.size.should == 2
  end

=begin
  it 'なのにbをgetしようとしたらないのでnilがかえってかつサイズも増えてない' do
    subject.get('b').should == nil
    
  end
=end
end


describe LRUCache, '#get' do
  describe 'たくさんputされたら昔のやつから消える' do
    subject { LRUCache.new(2) }
    it 'で3つ格納したら最初の値が消える' do
      subject.put('a','1111')
      subject.put('b','2222')
      subject.put('c','3333')
      subject.get('a').should == nil      
    end
    it 'で4つ格納したら二つ目の値も消える' do
      subject.put('a','1111')
      subject.put('b','2222')
      subject.put('c','3333')
      subject.put('d','4444')
      subject.get('a').should == nil
      subject.get('b').should == nil      
    end
  end

  describe 'たくさんputされたら使われてないやつから消える' do
    subject { LRUCache.new(2) }
    it 'で2つ格納したらあとにaをゲットしたあともう一つ入れたらaは消えずbが消える' do
      subject.put('a','1111')
      subject.put('b','2222')
      subject.get('a')
      
      subject.put('c','3333')
      subject.get('a').should == '1111'
      subject.get('b').should == nil      
    end

    it 'で4つ格納したら二つ目の値も消える' do
      subject.put('a','1111')
      subject.put('b','2222')
      subject.get('a')
      
      subject.put('c','3333')
      subject.put('d','4444')

      subject.get('a').should == nil
      subject.get('c').should == '3333'
    end

  end
end