探しても探してもわいてくるバグ。今回のバグはかなり難しい！と自負できます。 これはもう、設計段階でどれだけ例外的な場合を考えることができるかにかかっています。 完璧なアルゴリズムに則ってさっさと組んでしまいたいです。

さて、そんなわけでこのブログの読者様にもぜひ挑戦してみて欲しいです。 ちなみに本来のコードを改造して、ちょっとだけ解きやすくなっています。 クラス名が適当なのは無視ということで...。

class Entry {
    private String id;
    private double value;
    public static Comparator<Entry> ID_ASCEND_COMP;

    // getter, setter は定義済みとします。
}

class Application {

    // 問題のメソッド
    public List<Entry> merge(List<Entry> list1, List<Entry> list2 ){
        Collections.sort(list1, Entry.ID_ASCEND_COMP);
        Collections.sort(list2, Entry.ID_ASCEND_COMP);

        Iterator<Entry> it1 = list1.iterator();
        Iterator<Entry> it2 = list2.iterator();
        Entry e1 = null;
        Entry e2 = null;
        List<Entry> merged = new ArrayList<Entry>();

        while(it1.hasNext() && it2.hasNext()){
            if(e1==null)  e1 = it1.next();
            if(e2==null)  e2 = it2.next();

            int key = Entry.ID_ASCEND_COMP.compare(e1,e2);

            if(key<0){
                merged.add(e1);
                e1 = null;
            } else if(key==0) {
                e1.setValue(e1.getValue()+e2.getValue());
                merge.add(e1);
                e1 = null;
                e2 = null;
            } else {
                merged.add(e2);
                e2 = null
            }
        }
        if(e1!=null)  merged.add(e1);
        if(e2!=null)  merged.add(e2);

        while(it1.hasNext())  merged.add(it1.next());
        while(it2.hasNext())  merged.add(it2.next());

        return merged;
    }
}

で、このメソッドが何をしているかというと、引数に与えられた2つのコレクションを1つにまとめるということをしています。ただし、IDが重複しているインスタンスがあれば、片方のインスタンスに value を加算してそれを追加するというメソッドです。ちなみに、list1とlist2がnullの場合は考えなくても構いません。（NullPointerExceptionが発生して終了するだけなんで。）また、ID_ASCEND_COMPは、Entryのidをソーとキーとして昇順に並び替えるComparatorです。*1

では正解です。

単純な場合ではこんな引数が与えられるとおかしなことになります。

class Main {
    public static void main(String[] args){
        List<Entry> list1 = new ArrayList<Entry>();
        List<Entry> list2 = new ArrayList<Entry>();

        list1.add(new Entry("0003", 0.5));

        list2.add(new Entry("0001", 0.4));
        list2.add(new Entry("0003", 0.5));

        List<Entry> merged = new Application().merge(list1, list2);
        for(Entry e: merge){
            // 正しくは2回しか呼ばれないはずだが、バグのため3回呼ばれる
            System.out.println(e);
        }
    }
}

これを回避する単純な方法は、追加したIDを記録しておいて、毎回チェックを行うことでしょう。他にいい方法がありますかね?？

--
(2007/1/27 追記)

今思ったら、片方のリストの要素を、IDをキー・要素を値としたMapに格納しておいて、総当りで追加してもよさそうな気がしてきました。マージし終わったあとに、Mapの値のCollectionだけ取ってきてソートしなおしたらいいだけだしorz

  • *1:ちなみに、降順でも問題なく動きます。