TDD Boot Campのコード

というわけで、晒します。

前半は@katzchang・@kozy4324のペア。後半は@katzchang・@yugoriのペア。

Eclipseは独自に履歴を持っているので、2パターンを引っ張り出してきました。クラス宣言部にカーソルを当てて右クリックからLocal History。たぶん20セーブくらいしか保持してないけど、たまに助かることもあります。

仕様変更直後くらい

ということで、仕様変更直後くらいのセーブから。大体の時間で取っているので、REDな組み合わせかも知れません。
基本的には、テストコードは下に順に追加していっています。上にある項目から順に、プロダクトコードを作り込んでいったってことです。
第一の仕様変更（キャッシュサイズを変更できるようにする）まで対応済、第二の仕様変更（一定時間が経過したデータはキャッシュから消える）に対応しようとしたら、既存機能にバグの疑いがあり、バグを出現させるテストコードを書いてREDであることを確認、改修してGREENになった直後です（たぶん）。
このときは第二の仕様変更のテストコードは途中まで書いていたけど、とりあえずコメントアウト。@Igunoreでもいいかもしれないけど、コンパイルエラーとか拾われたら面倒なのでコメント化してます。
その他、仕様変更の未対応のものは"// TODO"タグでメモ。あと、ミルズさんに「このーputputってすごい長いよね」と指摘されたので、これもTODOタグを付けています。

テストコード

package tddbc;

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

import org.hamcrest.core.IsNull;
import org.junit.Before;
import org.junit.Test;

public class LRUCacheTest {

    LRUCache<String, String> target;
    
    @Before
    public void setup() throws Exception {
        target = new LRUCache<String, String>(3);
    }
    
    @Test
    public void putしたものがgetできる() throws Exception {
        target.put("a", "A");
        assertThat(target.get("a"), is("A"));
    }
    
    @Test
    public void sizeがとれる() throws Exception {
        assertThat(target.size(), is(0));
        target.put("a", "A");
        assertThat(target.size(), is(1));
        target.put("b", "B");
        assertThat(target.size(), is(2));
    }
    
    @Test
    public void リストが更新される() throws Exception {
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        assertThat(target.get("a"), is("A"));
        assertThat(target.get("b"), is("B"));
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), nullValue());
        target.put("d", "D");
        assertThat(target.get("a"), nullValue());
        assertThat(target.get("b"), is("B"));
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), is("D"));
    }

    @Test
    public void 上限値を設定できる() throws Exception {
        target = new LRUCache<String, String>(1);
        target.put("a", "A");
        target.put("b", "B");
        assertThat(target.size(), is(1));
    }

    @Test(expected=IllegalArgumentException.class)
    public void 上限値は0はだめ() throws Exception {
        target = new LRUCache<String, String>(0);
    }

    @Test
    public void 上限値は1はおk() throws Exception {
        target = new LRUCache<String, String>(1);
    }
    
    @Test(timeout=3000)
    public void _1万回の操作が3秒以内に終わること() throws Exception {
        LRUCache<Integer, String> target = new LRUCache<Integer, String>(1);
        for (int i = 0; i < 10000; i++) {
            target.put(i, "A");
        }
    }
    
    @Test
    public void 古いものが消すリストの先頭に来ること() throws Exception {
        target.put("a", "A"); // a
        target.put("b", "B"); // a,b
        target.put("c", "C"); // a,b,c
        assertThat(target.oldest(), is("a"));
        target.get("a"); // b,c,a
        assertThat(target.oldest(), is("b"));
        target.put("b", "B"); // c,a,b
        assertThat(target.oldest(), is("c"));
    }
    
    @Test
    public void とちゅうでgetしてputしたら次のヤツが消えるか() throws Exception {
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        target.get("a");
        target.put("d", "D");
        assertThat(target.get("b"), nullValue());
    }
    
    @Test
    public void 一つも使われていない場合は最初に追加したものから消える() throws Exception {
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        target.put("d", "D");
        assertThat(target.get("a"), IsNull.nullValue());
    }
    
    @Test
    public void getされたら使われたと見なす() throws Exception {
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        target.get("a");
        target.put("d", "D");
        assertThat(target.get("b"), nullValue());
    }
    
    //TODO 一定時間でキャッシュは消える。
    //TODO スレッドセーフ
    
    @Test
    public void キャッシュサイズをふやせる() throws Exception {
        target.setCacheSize(1);
        target.put("a", "A");
        target.put("b", "B");
        assertThat(target.size(), is(1));
        target.setCacheSize(2);
        target.put("c", "C");
        assertThat(target.size(), is(2));
    }
    
    @Test
    public void キャッシュサイズを減らせる() throws Exception {
        target.setCacheSize(4);
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        target.put("d", "D");
        target.setCacheSize(2);
        assertThat(target.get("a"), nullValue());
        assertThat(target.get("b"), nullValue());
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), is("D"));
    }
    
    @Test
    public void historyが消えてないかも() throws Exception {
        target.setCacheSize(3);
        target.put("a", "A");
        target.put("b", "B");
        target.put("c", "C");
        
        target.put("d", "D"); //should remove key a
        
        target.put("e", "E"); //should remove key b
        assertThat(target.get("b"), nullValue());
        
    }
    
    //TODO putputputって書くのがめんどくさい。
    
//    @Test
//    public void 更新時刻を持っていること() throws Exception {
//        long start = System.currentTimeMillis();
//        target.put("a", "A");
//        long end = System.currentTimeMillis();
//        assertTrue(start <= target.updateTimeOf("a"));
//        assertTrue(target.updateTimeOf("a") <= end);
//    }
    
//    @Test
//    public void キャッシュ保持期間が指定できる() throws Exception {
//        target.setAlive(1000);
//        target.put("a", "A");
//        Thread.sleep(1010);
//        assertThat(target.get("a"), nullValue());
//    }
}

プロダクトコード

package tddbc;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LRUCache<K, V> {
    final Map<K, V> cache;
    int limit;
    final List<K> history;
    final List<Long> historyTime;
    long alive;
    
    public LRUCache(int limit) {
        if(limit < 1) throw new IllegalArgumentException();
        this.history = new ArrayList<K>(limit);
        this.historyTime = new ArrayList<Long>(limit);
        this.cache = new HashMap<K, V>(limit);
        this.limit = limit;
    }

    public LRUCache() {
        this(10);
    }

    public void put(K key, V value) {
        if (limit <= cache.size()) {
            cache.remove(history.remove(0));
        }
        cache.put(key, value);
        updateOldest(key);
    }
    
    void removeHistoryAt() {
        
    }
    
    private void updateOldest(K key) {
        history.remove(key);
        history.add(key);
    }

    public V get(K key) {
        if(history.contains(key)) {
            updateOldest(key);
        }
        return cache.get(key);
    }

    public Integer size() {
        return cache.size();
    }

    K oldest() {
        return this.history.get(0);
    }

    public void setCacheSize(int i) {
        while(history.size()>i){
            cache.remove(history.remove(0));
        }
        limit=i;
    }
    
    public void setAlive(long alive) {
        this.alive = alive;
    }
    
    long updateTimeOf(String string) {
        // TODO Auto-generated method stub
        return 0;
    }

}

最終的に

第二の仕様変更に対応。あと、テストのためのtarget.putが連続して長いよねという指摘に対応しようとして、途中までしか直してません。
プロダクトコード側もだいぶぐちゃぐちゃになってきたので、クラスを分割しようとしたところであと10分なので、とりあえずここまでです。

テストコード

package tddbc;

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

import org.hamcrest.core.IsNull;
import org.junit.Before;
import org.junit.Test;

public class LRUCacheTest {

    LRUCache<String, String> target;
    
    @Before
    public void setup() throws Exception {
        target = new LRUCache<String, String>(3);
    }
    
    private void fillTarget(String...keys) {
        for (String key : keys) target.put(key, key.toUpperCase());
    }
    
    @Test
    public void putしたものがgetできる() throws Exception {
        fillTarget("a");
        assertThat(target.get("a"), is("A"));
    }
    
    @Test
    public void sizeがとれる() throws Exception {
        assertThat(target.size(), is(0));
        fillTarget("a");
        assertThat(target.size(), is(1));
        fillTarget("b");
        assertThat(target.size(), is(2));
    }
    
    @Test
    public void リストが更新される() throws Exception {
        fillTarget("a", "b", "c");
        assertThat(target.get("a"), is("A"));
        assertThat(target.get("b"), is("B"));
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), nullValue());
        fillTarget("d");
        assertThat(target.get("a"), nullValue());
        assertThat(target.get("b"), is("B"));
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), is("D"));
    }

    @Test
    public void 上限値を設定できる() throws Exception {
        target = new LRUCache<String, String>(1);
        fillTarget("a", "b");
        assertThat(target.size(), is(1));
    }

    @Test(expected=IllegalArgumentException.class)
    public void 上限値は0はだめ() throws Exception {
        target = new LRUCache<String, String>(0);
    }

    @Test
    public void 上限値は1はおk() throws Exception {
        target = new LRUCache<String, String>(1);
    }
    
    @Test(timeout=3000)
    public void _1万回の操作が3秒以内に終わること() throws Exception {
        LRUCache<Integer, String> target = new LRUCache<Integer, String>(1);
        for (int i = 0; i < 10000; i++) {
            target.put(i, "A");
        }
    }
    
    @Test
    public void 古いものが消すリストの先頭に来ること() throws Exception {
        fillTarget("a", "b", "c");
        assertThat(target.oldest(), is("a"));
        target.get("a"); // b,c,a
        assertThat(target.oldest(), is("b"));
        fillTarget("b");
        assertThat(target.oldest(), is("c"));
    }
    
    @Test
    public void とちゅうでgetしてputしたら次のヤツが消えるか() throws Exception {
        fillTarget("a", "b", "c");
        target.get("a");
        fillTarget("d");
        assertThat(target.get("b"), nullValue());
    }
    
    @Test
    public void 一つも使われていない場合は最初に追加したものから消える() throws Exception {
        fillTarget("a", "b", "c", "d");
        assertThat(target.get("a"), IsNull.nullValue());
    }
    
    @Test
    public void getされたら使われたと見なす() throws Exception {
        fillTarget("a", "b", "c");
        target.get("a");
        fillTarget("d");
        assertThat(target.get("b"), nullValue());
    }
    
    //TODO スレッドセーフ
    
    @Test
    public void キャッシュサイズをふやせる() throws Exception {
        target.setCacheSize(1);
        fillTarget("a", "b");
        assertThat(target.size(), is(1));
        target.setCacheSize(2);
        fillTarget("a");
        assertThat(target.size(), is(2));
    }
    
    @Test
    public void キャッシュサイズを減らせる() throws Exception {
        target.setCacheSize(4);
        fillTarget("a", "b", "c", "d");
        target.setCacheSize(2);
        assertThat(target.get("a"), nullValue());
        assertThat(target.get("b"), nullValue());
        assertThat(target.get("c"), is("C"));
        assertThat(target.get("d"), is("D"));
    }
    
    @Test
    public void historyが消えてないかも() throws Exception {
        target.setCacheSize(3);
        fillTarget("a", "b", "c", "d");
        fillTarget("d"); //should remove key a
        
        fillTarget("e"); //should remove key b
        assertThat(target.get("b"), nullValue());
        
    }
    
    @Test
    public void 更新時刻を持っていること() throws Exception {
        {
            long start = System.currentTimeMillis();
            target.put("a", "A");
            long end = System.currentTimeMillis();
            assertTrue(start <= target.updateTimeOf("a"));
            assertTrue(target.updateTimeOf("a") <= end);
        }
        {
            long start = System.currentTimeMillis();
            target.put("a", "A");
            long end = System.currentTimeMillis();
            assertTrue(start <= target.updateTimeOf("a"));
            assertTrue(target.updateTimeOf("a") <= end);
        }
        {
            assertTrue(target.updateTimeOf("b") == 0);
            long start = System.currentTimeMillis();
            target.put("b", "B");
            long end = System.currentTimeMillis();
            assertTrue(start <= target.updateTimeOf("b"));
            assertTrue(target.updateTimeOf("b") <= end);
        }

    }
    
    @Test
    public void キャッシュ保持期間が指定できる() throws Exception {
        target.setAlive(1000);
        target.put("a", "A");
        target.put("b", "B");
        Thread.sleep(1010);
        target.put("c", "C");
        assertThat(target.get("a"), nullValue());
        assertThat(target.get("b"), nullValue());
        assertThat(target.get("c"), notNullValue());
    }
    
    
}

プロダクトコード

package tddbc;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LRUCache<K, V> {
    final Map<K, V> cache;
    int limit;
    final List<K> history;
    final List<Long> historyTime;
    long alive;
    
    public LRUCache(int limit) {
        if(limit < 1) throw new IllegalArgumentException();
        this.history = new ArrayList<K>(limit);
        this.historyTime = new ArrayList<Long>(limit);
        this.cache = new HashMap<K, V>(limit);
        this.limit = limit;
        this.alive = 0;
    }
    
    public LRUCache() {
        this(10);
    }
    
    public LRUCache<K, V> put(K key, V value) {
        if (limit <= cache.size()) removeCache(0);
        cache.put(key, value);
        updateOldest(key);
        return this;
    }
    
    void removeCache(int i) {
        cache.remove(removeHistoryAt(i));
    }

    K removeHistoryAt(int i) {
        historyTime.remove(i);
        return history.remove(i);
    }
    
    private void updateOldest(K key) {
        if (history.contains(key)) removeHistoryAt(history.indexOf(key));
        history.add(key);
        historyTime.add(System.currentTimeMillis());
    }

    public V get(K key) {
        if (alive > 0) clearDeadCache();
        if (history.contains(key)) updateOldest(key);
        return cache.get(key);
    }
    

    void clearDeadCache() {
        long now = System.currentTimeMillis();
        for (int i = 0; i< historyTime.size(); i++) {
            long dead = historyTime.get(i) + alive;
            if(dead < now) removeCache(i);
        }
    }
    
    public Integer size() {
        return cache.size();
    }

    K oldest() {
        return this.history.get(0);
    }

    public void setCacheSize(int i) {
        while(history.size()>i) removeCache(0);
        limit = i;
    }
    
    public void setAlive(long alive) {
        this.alive = alive;
    }
    
    long updateTimeOf(K key) {
        if (history.contains(key)) return historyTime.get(history.indexOf(key));
        return 0;
    }
}