TDDBC@Sapporo の ruby チームの実装/テストです

LRUCache.rb

# -*- coding: utf-8 -*-
require 'rspec'

class LRUCache
  attr_reader :order, :capacity

  def initialize(capacity)
    @capacity = capacity
    @order = []
    @hash = {}
  end
  def put key, value
    @hash[key] = value
    touch key
    truncate!
  end
  def get key
    @hash[key]
  end
  def get! key
    touch key
    get key
  end
  def touch key
    @order.delete key
    @order.unshift key
  end
  def truncate!
    while @order.size > @capacity
      @hash.delete(@order.pop)
    end
  end
  def resize! size
    @capacity = size
    truncate!
  end
end

describe LRUCache do
  describe 'with capacty 3' do
    before do
      @cache = LRUCache.new(3)
    end
    context 'resizing capacity' do
      context 'resizing to smaller' do
        it 'should decrease capacity' do
          @cache.resize! 2
          @cache.capacity.should == 2
        end
        it 'should truncate old elements of cache' do
          @cache.put('key1', 'value1')
          @cache.put('key2', 'value2')
          @cache.put('key3', 'value3')
          @cache.resize! 2
          @cache.get('key1').should be_nil
          @cache.get('key2').should == 'value2'
          @cache.get('key3').should == 'value3'
        end
      end
      context 'resizing to 0' do
        it 'should be empty' do
          @cache.put('key1', 'value1')
          @cache.put('key2', 'value2')
          @cache.put('key3', 'value3')
          @cache.resize! 0
          @cache.get('key1').should be_nil
          @cache.get('key2').should be_nil
          @cache.get('key3').should be_nil
        end
      end
    end
    context 'same key inserted twice' do
      before do
        @cache.put('key1', 'value1')
        @cache.put('key1', 'value1-2')
      end
      it "updates key1's value" do
        @cache.get('key1').should == 'value1-2'
      end
    end
    context 'put a key, and put another key many times' do
      before do
        @cache.put('key1', 'value1')
        3.times {
          @cache.put('key2', 'value2')
        }
      end
      it "should keeps key1" do
        @cache.get('key1').should == 'value1'
      end
    end
    context 'two pairs inserted' do
      before do
        @cache.put('key1', 'value1')
        @cache.put('key2', 'value2')
      end
      it 'contains two pairs' do
        @cache.get('key1').should == 'value1'
        @cache.get('key2').should == 'value2'
      end
      it 'preserves the order inserted' do
        @cache.order.should == ['key2', 'key1']
      end
    end
  end
  describe 'with capcity 2' do
    before do
      @cache = LRUCache.new(2)
    end
    context 'doing get! while putting values' do
      before do
        @cache.put('key1', 'value1')
        @cache.put('key2', 'value2')
        @cache.get!('key1')
        @cache.put('key3', 'value3')
      end
      it 'should change key order' do
        @cache.get('key1').should == 'value1'
        @cache.get('key2').should be_nil
        @cache.get('key3').should == 'value3'
      end
    end
  end

  describe 'with capcity 1' do
    before do
      @cache = LRUCache.new(1)
    end
    context 'same key inserted twice' do
      before do
        @cache.put('key1', 'value1')
        @cache.put('key1', 'value1-2')
      end
      it "updates key1's value" do
        @cache.get('key1').should == 'value1-2'
      end
    end
    it '要素を 2 つ追加して，1つめが取れないこと' do
      @cache.put('key1', 'value1')
      @cache.put('key2', 'value2')
      @cache.get('key1').should be_nil
      @cache.get('key2').should == 'value2'
    end
    it '要素を 3 つ追加して，3つめ以外が取れないこと' do
      @cache.put('key1', 'value1')
      @cache.put('key2', 'value2')
      @cache.put('key3', 'value3')
      @cache.get('key1').should be_nil
      @cache.get('key2').should be_nil
      @cache.get('key3').should == 'value3'
    end
  end

  it "with capacity 0"
  it "with capacity -1"
  it "with capacity given by not integer"
end