LRUCache、一定時間経つと消えるところまで。

仕様変更その2まで対応。

• Clockオブジェクトを導入
  • 記事にしやすいよう、モッククラスをテストないに記述してるけど、分けた方がいい。
  • でも、Clock.SYSTEM_CLOCKは、interface Clock内に定義すべき。通常使うだろう、デフォルトオブジェクトがわかりやすいはず。
• 容量変更のメソッド（fixCache()）と時間でクリアのメソッド(deleteDeadCache())を分けた。
  • 理由は、put/getメソッド内でのcache.putとcache.getとの前後関係を同じようにするため。
  • この一歩手前までは、fixCache()内に2行記述していた。そうすると、get時はget前に、put時はput後にfixCache()を呼ぶ必要があった。
  • これで、重複が出来た。が、どうやって取り除こうか。
• 生存時間と容量も、KeyHolderに移動。
  • これで、外側のオブジェクトはほぼMapの機能しか残っていない。

んー、でも、この方向でただしいのか？
できれば、KeyHolderとLRUCacheの相互参照状態を解消したい…。

テストコード

package tddbc;

import static org.junit.Assert.*;
import static org.hamcrest.core.Is.*;
import static org.hamcrest.core.IsNull.*;

import org.junit.*;

// TODO スレッドセーフ

public class LRUCacheTest {
    LRUCache<String, String> target;
    MockClock clock;
    
    class MockClock implements Clock {
        long currentTime = 0;
        @Override
        public long currentTime() {
            return this.currentTime;
        }
        
        void set(long currentTime) {
            this.currentTime = currentTime;
        }
    }

    @Before
    public void setup() {
        target = new LRUCache<String, String>();
        clock = new MockClock();
        target.setClock(clock);
    }
    
    void fillTarget(Integer...is) {
        for (Integer i : is) target.put(i.toString(), i.toString());
    }
    
    @Test
    public void putしたものをgetできる() throws Exception {
        target.put("key", "value");
        assertThat(target.get("key"), is("value"));
    }
    
    @Test
    public void 容量が取得できる() throws Exception {
        fillTarget(1,2,3,4);
        assertThat(target.size(), is(4));
    }
    
    @Test
    public void 限界容量まで格納できる() throws Exception {
        target.changeCapacityTo(3);
        fillTarget(1,2,3);
        assertThat(target.size(), is(3));
        fillTarget(4);
        assertThat(target.size(), is(3));
    }
    
    @Test
    public void 存在しないキーにはnullを返す() throws Exception {
        assertThat(target.get("存在しないキー"), nullValue());
    }
    
    @Test
    public void 限界容量を超えると一番古いものから削除される() throws Exception {
        target.changeCapacityTo(3);
        fillTarget(1,2,3,4);
        assertThat(target.get("1"), nullValue());
        fillTarget(5);
        assertThat(target.get("2"), nullValue());
    }
    
    @Test
    public void あとで容量を増やせる() throws Exception {
        target.changeCapacityTo(3);
        fillTarget(1,2,3,4);
        target.changeCapacityTo(5);
        fillTarget(5,6);
        assertThat(target.size(), is(5));
    }
    
    @Test
    public void あとで容量を減らせる() throws Exception {
        target.changeCapacityTo(5);
        fillTarget(1,2,3,4,5);
        target.changeCapacityTo(1);
        assertThat(target.size(), is(1));
    }
    
    @Test(expected=IllegalArgumentException.class)
    public void 容量0は指定できない() throws Exception {
        target.changeCapacityTo(0);
    }

    @Test
    public void あとで容量を減らしたら古いキーから削除される() throws Exception {
        target.changeCapacityTo(5);
        fillTarget(1,2,3,4,5);
        target.changeCapacityTo(3);
        assertThat(target.get("1"), nullValue());
        assertThat(target.get("2"), nullValue());
    }
    
    
    @Test
    public void putした時刻が記録される() throws Exception {
        clock.set(1);
        fillTarget(1);
        clock.set(2);
        assertThat(target.keyHolder.d.get(0), is(1L));
    }
    
    @Test
    public void getした時刻が記録される() throws Exception {
        clock.set(1);
        fillTarget(1);
        clock.set(2);
        target.get("1");
        clock.set(3);
        assertThat(target.keyHolder.d.get(0), is(2L));
    }
    
    @Test
    public void 一定時間経過すると削除対象になる() throws Exception {
        fillTarget(1);
        clock.set(3600000);
        assertThat(target.keyHolder.dead(), is(false));
        clock.set(3600001);
        assertThat(target.keyHolder.dead(), is(true));
    }
    
    @Test
    public void 一定時間経過すると削除される() throws Exception {
        fillTarget(1);
        clock.set(3600001);
        assertThat(target.get("1"), nullValue());
    }
}

Clockオブジェクト

package tddbc;

public interface Clock {
    public long currentTime();
    
    public static final Clock SYSTEM_CLOCK = new Clock() {
        @Override
        public long currentTime() {
            return System.currentTimeMillis();
        }
    };
}

プロダクトコード

package tddbc;

import java.util.*;

public class LRUCache<K, V> {
    final HashMap<K, V> cache = new HashMap<K, V>();
    final KeyHolder keyHolder = new KeyHolder();
    
    class KeyHolder {
        final ArrayList<K> l = new ArrayList<K>();
        final ArrayList<Long> d = new ArrayList<Long>();
        int capacity = 1000;
        long survivalTime = 3600000;
        Clock clock = Clock.SYSTEM_CLOCK;
        
        void touch(K key) {
            if(this.l.contains(key)) {
                this.d.remove(this.l.indexOf(key));
                this.l.remove(key);
            }
            this.l.add(key);
            this.d.add(clock.currentTime());
        }
        
        void fixCache() {
            while (capacity < size()) kill();
        }
        
        void deleteDeadCache() {
            while (0 < size() && dead()) kill();
        }
        
        void kill() {
            this.d.remove(0);
            cache.remove(this.l.remove(0));
        }
        
        boolean dead() {
            return this.d.get(0) + survivalTime < clock.currentTime();
        }
        
        void capa(int capacity) {
            if (capacity < 1) throw new IllegalArgumentException("Capacity must be positive integer...");
            this.capacity = capacity;
            this.fixCache();
        }

    }
    
    public void setSurvivalTime(long survivalTime) {
        keyHolder.survivalTime = survivalTime;
    }

    public void changeCapacityTo(int capacity) {
        this.keyHolder.capa(capacity);
    }
    
    public void setClock(Clock clock) {
        keyHolder.clock = clock;
    }
    
    public void put(K key, V value) {
        try {
            this.keyHolder.deleteDeadCache();
            this.keyHolder.touch(key);
            this.cache.put(key, value);
        } finally {
            this.keyHolder.fixCache();
        }
    }
    
    public V get(K key) {
        try {
            this.keyHolder.deleteDeadCache();
            this.keyHolder.touch(key);
            return this.cache.get(key);
        } finally {
            this.keyHolder.fixCache();
        }
    }
    
    public int size() {
        return this.cache.size();
    }    
}