Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- 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
Add Comment
Please, Sign In to add comment