第二回チキチキ 日本ペアプログラミングの会java-ja支部会（仮）に参加してきました。会場を提供してくださった株式会社ドワンゴ様、本当にありがとうございました。
TDD(test-driven development)での開発ってどんな感じ？というセッションをまずt_wada氏がやって、
踏まえたうえでペアプログラミングで実践して体感するという流れ。
ペアプロの相手を探すフェーズがさながら合コンかお見合いパーティといった風情。私は@yamashiro氏とペアを組みました。
@yamashiro氏はTDD慣れしているんだけど、僕のLet'sノートのキーボードと相性が悪かったのが残念。僕らのペアプロ姿はUst中継で放映されていましたよ。
セッション内容は@monjudoh氏がリアルタイムにblogに上げた奴とかたくさんあるので割愛。
成果物
テーマはプライオリティキューを作ろう、というもの。ぶっちゃけてしまえば、Java5からあるPriorityQueue
を自作しましょうというネタです。
作業のステップは以下のような感じ。記憶を元に書いているので怪しいです。実際にはもっと細かいステップもいろいろあります。Ust中継を見ていた人はわかったんじゃないかな。
- まず単なるキューを実装する方針にしよう
- ひとつのオブジェクトを入れて出すところまでをまず作る
- まずはテストを書いてJUnit(※自動テスト用ツール)を実行してバーをレッド(※自動テストが失敗した状態)にしないといけない
- キューに入れるテストコードをまず書く
- コンパイルエラーになるのでCtrl+1 (※エディタはEclipse3.4)を使って実装をCtrl+1で補完
- とりあえずJUnitのテストが通過してグリーンになる（pushは値を返さないので空実装でも関係ない）
- キューから取り出す部分のテストコードをまず書く
- コンパイルが通るように実装コードを補完して、JUnitを実行して失敗、バーが赤くなる
- Object型フィールド変数を作って格納してget()で返すという簡単な作り
- JUnitを実行して成功、バーがグリーンになる
- 次に複数個の入れれるようにしてちゃんとキューにしよう
- テストケースを書き足して、２個入れて２個出すようにする
- バーがレッドになる
- フィールドをList型に変更
- get()の実装は return this.data.remove(0); でいいよね(List#remove(int)を利用)
- バーがグリーンになる
- ジェネリクス対応させちゃいたいんでここで入れちゃおう
- コンストラクタに型変数を渡すようにテストコードを修正。コンパイルエラー
- コンストラクタに型変数を追加
- あー。このへんのリファクタリングで自動でやれないんだよなー。(2009年6月現在)
- 手動で実装を載せるしかない
- さて、プライオリティを渡せるようにしますか。コンストラクタで渡すでいいよね
- Comparatorを渡すようにして順序付けを外から指定できるのがいいよね
- コンストラクタにComparatorを渡して比較をするテストケースを書く
- コンパイルエラーになるので実装をCtrl+1で補完
- バーがレッド。さて、グリーンにするにはどうしようか？
- ちょっと小さい手ごろなステップが思い浮かばないので一気に実装しちゃう
- ThreeSetを使って実装しちゃえば速いんじゃない？
- 実装できた。テストを実行すると…あれ、レッド？
- あー。同じ値を入れたらTreeSetだとひとつにまとめられちゃうからか
- ダメだ、TreeSet方式は却下
- ちゃんとダメなケースをはじけたわけだからTDDがうまく機能したね
- Listにケツから突っ込んで、比較しながら手前に向かって追い越しをやる方法でどうだろう？
- push()時点でキューの中の状態を正しい状態に保つ感じ
- まずはTreeSet方式を差し戻す。Subversion使っておけばよかった orz (現地の環境がトラブル多そうだったので避けたのが敗因)
- ただのListにしよう
- 後ろから順に比較しないといけないから逆順にループしないと
- Collections#reverse()を使う？
- 挿入するときにループカウンタ必要になるから拡張for文つかうのはあきらめよう
- compare()の結果ってどっちが大きいときに正だっけ？ｗ
- 出来上がり。なんか拡張するテーマ決めよう
- SQLのorder by みたいな感じで複数のキーを優先度設定できるようなのどう？
- よしそれで行こう…って時間切れか！
ソースコード
ソースをそのままで張ろうかとも思ったんだけど、コメントないなー orz 普段はjavadocとかコメントがりがり書く派なんだけど、なんかすっかり忘れてました。
上で時間切れになった後、「各自の荷物片付けてー」とか言われている最中に実装をやっちゃったので、実装完了版にコメントを追記したソースを載せます。
package queue;
import static org.junit.Assert.*;
import java.awt.Point;
import java.util.Comparator;
import org.junit.Test;
public class PriorityQueueTest
{
@Test
public void testname() throws Exception {
PriorityQueue<String> queue = new PriorityQueue<String>();
String expectedObj1 = new String();
String expectedObj2 = new String();
queue.push(expectedObj1);
queue.push(expectedObj2);
assertEquals(expectedObj1, queue.get());
assertEquals(expectedObj2, queue.get());
}
@Test
public void プライオリティを設定できる() throws Exception {
PriorityQueue<String> queue = new PriorityQueue<String>(new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}});
String expectedObj1 = new String("b");
String expectedObj2 = new String("a");
queue.push(expectedObj1);
queue.push(expectedObj2);
assertEquals(expectedObj2, queue.get());
assertEquals(expectedObj1, queue.get());
}
@Test
public void 複数の優先度を設定できる() throws Exception {
PriorityQueue<Point> queue = new PriorityQueue<Point>(
new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o2.x - o1.x;
}},
new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o2.y - o2.y;
}});
Point p1 = new Point(1,4);
Point p2 = new Point(1,3);
queue.push(p1);
queue.push(p2);
assertEquals(p1, queue.get());
assertEquals(p2, queue.get());
Point p3 = new Point(2,2);
queue.push(p1);
queue.push(p3);
assertEquals(p1, queue.get());
assertEquals(p3, queue.get());
}
}
package queue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
/**
* 2009.06.06 第二回チキチキ 日本ペアプログラミングの会java-ja支部会（仮）
* TDDでプライオリティキューの実装をした成れの果て。
* TDDで作ったものは複数優先度がやりかけだったので、お片づけ時間中にnagiseが完成させ、
* blog掲載時に読む人を考慮してnagiseが解説のコメントを足したもの。
*
* @author yamashiro, nagise
*
* @param <T> 格納するデータ型
*/
public class PriorityQueue<T> {
List<T> data = new ArrayList<T>();
List<Comparator<T>> comparators;
/** 自然順序付けによるプライオリティのキューを作成する */
public PriorityQueue() {
this.comparators = new ArrayList<Comparator<T>>();
this.comparators.add(new Comparator<T>() {
@SuppressWarnings("unchecked")
@Override
public int compare(T o1, T o2) {
Comparable c1 = (Comparable) o1;
return c1.compareTo(o2);
}
});
}
/**
* 指定したComparatorをプライオリティ判定に用いるキューを作成する
* @param comparator プライオリティ判定に用いるキュー
*/
public PriorityQueue(Comparator<T> comparator) {
this.comparators = new ArrayList<Comparator<T>>();
this.comparators.add(comparator);
}
/**
* 複数優先度を持つキューを作成する
* @param comparators 第一優先度判定用Comparator、第二優先度判定用Comparatorといった形で並べる
*/
public PriorityQueue(Comparator<T> ... comparators) {
this.comparators = new ArrayList<Comparator<T>>();
for (Comparator<T> c : comparators) {
this.comparators.add(c);
}
}
public T get() {
Iterator<T> iterator = data.iterator();
if (iterator.hasNext()) {
T next = iterator.next();
this.data.remove(next);
return next;
}
return null;
}
public void push(T obj) {
// 挿入時に末尾から前に向かって順に優先度判定をして、しかるべき位置に挿入する
int i = this.data.size();
// 第一優先度からループして、等しい値が現れたら次の優先度で比較
comparatorLoop: for (Comparator<T> c : this.comparators) {
// 末尾から前に向かって湯鮮度判定するから逆ループ
for (;i > 0; i--) {
T target = this.data.get(i -1);
// 現在の優先度が等しければ、次の優先度での比較に移行
if (c.compare(obj, target) == 0) {
continue comparatorLoop;
}
// 優先度を超えそうな境目を見つけたら、そこが安住の地
if (c.compare(obj, target) <= 0) {
break comparatorLoop;
}
}
}
this.data.add(i, obj);
}
}