レンジスキャンのアレ

Scan.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.NavigableSet;
import java.util.Queue;
import java.util.SortedSet;
import java.util.TreeSet;

public class Scan {

    public static void main(String[] args) {
        kind();
        property();
        inequality();
        like();
        custom();
        scanAndMerge();
        zigzagScan();
    }

    // SELECT * FROM Foo
    private static void kind() {
        TreeSet<String> index = new TreeSet<String>();
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "Key(1)"),
            encode("Foo", "Key(2)"),
            encode("Bar", "Key(3)"),
            encode("Hoge", "Key(4)"),
            encode("Foo", "Key(5)"),
        }));

        // KindがFooであるものを探して表示
        String hogeFrom = encode("Foo");
        String hogeTo = next(hogeFrom);
        SortedSet<String> hogeFound = index.subSet(hogeFrom, hogeTo);
        print("Foo", hogeFound);
    }

    // SELECT * FROM Hoge WHERE name = "foo"
    // SELECT * FROM Hoge WHERE age = 18
    private static void property() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{name=hoge, age=18} : Key(1)
        // Hoge{name=foo, age=18}  : Key(2)
        // Hoge{name=bar, age=20}  : Key(3)
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "age", "18", "Key(1)"),
            encode("Hoge", "age", "18", "Key(2)"),
            encode("Hoge", "age", "20", "Key(3)"),
            encode("Hoge", "name", "hoge", "Key(1)"),
            encode("Hoge", "name", "foo", "Key(2)"),
            encode("Hoge", "name", "bar", "Key(3)"),
        }));

        // name=fooの人をさがす
        String nameFrom = encode("Hoge", "name", "foo");
        String nameTo = next(nameFrom);
        SortedSet<String> nameFound = index.subSet(nameFrom, nameTo);
        print("Hoge name foo", nameFound);

        // age=18の人を探す
        String ageFrom = encode("Hoge", "age", "18");
        String ageTo = next(ageFrom);
        SortedSet<String> ageFound = index.subSet(ageFrom, ageTo);
        print("Hoge age 18", ageFound);
    }

    // SELECT * FROM Hoge WHERE 18 < age AND age <= 20
    private static void inequality() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{age=17} : Key(1)
        // Hoge{age=18} : Key(2)
        // Hoge{age=19} : Key(3)
        // Hoge{age=20} : Key(4)
        // Hoge{age=20} : Key(5)
        // Hoge{age=21} : Key(6)
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "age", "17", "Key(1)"),
            encode("Hoge", "age", "18", "Key(2)"),
            encode("Hoge", "age", "19", "Key(3)"),
            encode("Hoge", "age", "20", "Key(4)"),
            encode("Hoge", "age", "20", "Key(5)"),
            encode("Hoge", "age", "21", "Key(6)"),
        }));
        // age=18のキー
        String ageFrom = encode("Hoge", "age", "18");
        // age=20のキー
        String ageTo = encode("Hoge", "age", "20");

        // このままだと 18 <= age < 20 なので、ageFrom, ageToを１つ加算
        ageFrom = next(ageFrom);
        ageTo = next(ageTo);
        SortedSet<String> nameFound = index.subSet(ageFrom, ageTo);
        print("Hoge name (18, 20]", nameFound);
    }

    // SELECT * FROM Hoge WHERE name LIKE "f.*"
    private static void like() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{name="hoge"} : Key(1)
        // Hoge{name="foo"} : Key(2)
        // Hoge{name="bar"} : Key(3)
        // Hoge{name="fuga"} : Key(4)
        // Hoge{name="g"} : Key(5)
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "name", "hoge", "Key(1)"),
            encode("Hoge", "name", "foo", "Key(2)"),
            encode("Hoge", "name", "bar", "Key(3)"),
            encode("Hoge", "name", "fuga", "Key(4)"),
            encode("Hoge", "name", "g", "Key(5)"),
        }));
        // Hoge name まで指定後に、前方一致させる "f" を指定
        String likeFrom = encode("Hoge", "name") + "f";
        // 末尾の文字を+1して終わりのキーを作成
        String likeTo = next(likeFrom);

        SortedSet<String> likeFound = index.subSet(likeFrom, likeTo);
        print("Hoge name f*", likeFound);
    }

    // SELECT * FROM Hoge WHERE 20 <= age AND age < 50 AND name = "foo"
    private static void custom() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{name=hoge, age=18} : Key(1)
        // Hoge{name=foo, age=38}  : Key(2)
        // Hoge{name=bar, age=20}  : Key(3)
        // Hoge{name=hoge, age=18} : Key(4)
        // Hoge{name=foo, age=16}  : Key(5)
        // Hoge{name=bar, age=45}  : Key(6)
        // Hoge{name=hoge, age=30} : Key(7)
        // Hoge{name=foo, age=25}  : Key(8)
        // Hoge{name=bar, age=18}  : Key(9)
        // Hoge{name=foo, age=99}  : Key(A)

        // Custom Index の構造と同様に、 IndexID, Property Value... にする
        // 今回は IndexID = IDX_100, プロパティは等号、不等号比較の順なので name, age
        // http://code.google.com/intl/en/appengine/articles/storage_breakdown.html
        index.addAll(Arrays.asList(new String[] {
            encode("IDX_100", "hoge", "18", "Key(1)"),
            encode("IDX_100", "foo" , "38", "Key(2)"),
            encode("IDX_100", "bar" , "20", "Key(3)"),
            encode("IDX_100", "hoge", "18", "Key(4)"),
            encode("IDX_100", "foo" , "16", "Key(5)"),
            encode("IDX_100", "bar" , "45", "Key(6)"),
            encode("IDX_100", "hoge", "30", "Key(7)"),
            encode("IDX_100", "foo" , "25", "Key(8)"),
            encode("IDX_100", "bar" , "18", "Key(9)"),
            encode("IDX_100", "foo" , "99", "Key(A)"),
        }));
        // name=foo, age=20 のキー
        String from = encode("IDX_100", "foo", "20");

        // name=foo, age=50 のキー
        String to = encode("IDX_100", "foo", "50");

        SortedSet<String> found = index.subSet(from, to);
        print("IDX_100 foo [20, 50)", found);
    }

    // SELECT * FROM Hoge WHERE name = "foo" AND age = 18
    private static void scanAndMerge() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{name=hoge, age=18} : Key(1)
        // Hoge{name=foo, age=18}  : Key(2)
        // Hoge{name=foo, age=20}  : Key(3)
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "age", "18", "Key(1)"),
            encode("Hoge", "age", "18", "Key(2)"),
            encode("Hoge", "age", "20", "Key(3)"),
            encode("Hoge", "name", "hoge", "Key(1)"),
            encode("Hoge", "name", "foo", "Key(2)"),
            encode("Hoge", "name", "foo", "Key(3)"),
        }));

        // name=fooの人をさがす
        String nameFrom = encode("Hoge", "name", "foo");
        String nameTo = next(nameFrom);
        SortedSet<String> nameFound = index.subSet(nameFrom, nameTo);
        print("Hoge name foo", nameFound);

        // age=18の人を探す
        String ageFrom = encode("Hoge", "age", "18");
        String ageTo = next(ageFrom);
        SortedSet<String> ageFound = index.subSet(ageFrom, ageTo);
        print("Hoge age 18", ageFound);

        // プログラム短縮のためQueueを使ってマージする(コピーが発生するため遅い)
        Queue<String> nameQueue = new LinkedList<String>(nameFound);
        Queue<String> ageQueue = new LinkedList<String>(ageFound);
        List<String> merged = new ArrayList<String>();

        // いずれかのキューが空になったらAND条件を満たせない
        while (!nameQueue.isEmpty() && !ageQueue.isEmpty()) {
            // キューの先頭にあるエントリからキーを抽出
            String nameKey = extractLast(nameQueue.element());
            String ageKey = extractLast(ageQueue.element());

            // それぞれのエントリはキー順に並んでいるため、大小比較してみる
            int cmp = nameKey.compareTo(ageKey);
            if (cmp == 0) {
                // 同じならマッチ, 結果としてキーを保持しておく
                merged.add(nameKey);
                nameQueue.remove();
                ageQueue.remove();
            }
            else if (cmp < 0) {
                // nameで比較したキーが小さいので、一つ進める
                nameQueue.remove();
            }
            else {
                // ageで比較したキーが小さいので、一つ進める
                ageQueue.remove();
            }
        }

        System.out.println("==== merged: " + merged);
    }

    // SELECT * FROM Hoge WHERE name = "foo" AND age = 18
    private static void zigzagScan() {
        TreeSet<String> index = new TreeSet<String>();
        // Hoge{name=hoge, age=18} : Key(1)
        // Hoge{name=foo, age=18}  : Key(2)
        // Hoge{name=foo, age=20}  : Key(3)
        index.addAll(Arrays.asList(new String[] {
            encode("Hoge", "age", "18", "Key(1)"),
            encode("Hoge", "age", "18", "Key(2)"),
            encode("Hoge", "age", "20", "Key(3)"),
            encode("Hoge", "name", "hoge", "Key(1)"),
            encode("Hoge", "name", "foo", "Key(2)"),
            encode("Hoge", "name", "foo", "Key(3)"),
            encode("Hoge", "age", "18", "Key(4)"),
            encode("Hoge", "age", "18", "Key(5)"),
            encode("Hoge", "age", "20", "Key(6)"),
            encode("Hoge", "name", "hoge", "Key(4)"),
            encode("Hoge", "name", "foo", "Key(5)"),
            encode("Hoge", "name", "foo", "Key(6)"),
        }));

        // name < foo+ の人、age < 18+ の人を別々に抜き出しておく
        // 今回はトリッキーな検索を行うため、変数名を一般的にする
        String aPrefix = encode("Hoge", "name", "foo");
        String bPrefix = encode("Hoge", "age", "18");
        NavigableSet<String> aIndex = index.headSet(next(aPrefix), false);
        NavigableSet<String> bIndex = index.headSet(next(bPrefix), false);

        List<String> results = new ArrayList<String>();

        // まず、a*から最初のエントリを取り出す
        // これは、name=fooでかつキーが一番小さいもの
        String aNext = aIndex.ceiling(aPrefix);
        while (aNext != null) {
            // 現在のaの情報から、キーだけを取り出す
            String aKey = extractLast(aNext);

            // bIndexの中から、「本来の検索条件+aIndexの現在のキー」以上の
            // エントリを探し出す
            // 本来の検索条件はキーを除いた部分のプレフィックスであるため、
            // bIndex の該当部分は末尾のキーだけで整列されている。
            // ここに、プレフィックスを固定しつつ末尾にキーを追加すれば、
            // aKey 以上のキーを持つ bIndex 内のエントリを探すことができ
            // aKey 未満のキーを持つエントリをスキップできる
            String bNext = bIndex.ceiling(append(bPrefix, aKey));
            if (bNext == null) {
                break;
            }

            // aKeyとbKeyが一致したら、name=fooかつage=18
            String bKey = extractLast(bNext);
            if (aKey.equals(bKey)) {
                results.add(aKey);
                // bの次のエントリへ
                bNext = bIndex.higher(bNext);
                if (bNext == null) {
                    break;
                }
                bKey = extractLast(bNext);
            }

            // この時点で、aKey < bKey が保証される
            assert aKey.compareTo(bKey) < 0;

            // bで見つけたキーを元に、aの次のエントリを計算
            aNext = append(aPrefix, bKey);

            // ジグザグに動くので、aとbを入れ替えて繰り返す
            NavigableSet<String> tIndex = aIndex;
            aIndex = bIndex;
            bIndex = tIndex;
            String tPrefix = aPrefix;
            aPrefix = bPrefix;
            bPrefix = tPrefix;
        }

        System.out.println("==== merged: " + results);
    }

    // それぞれの文字列の末尾にNULL文字を加えて順番に連結
    private static String encode(String...segments) {
        // エンコード対象は2つ以上の文字列
        assert segments.length >= 1;

        StringBuilder buf = new StringBuilder();
        for (String s : segments) {
            // 文字列のあとに、区切り文字のNULLを追加
            buf.append(s).append((char) 0);
        }
        return buf.toString();
    }

    // エンコードされた文字列と同じ長さで、1つ分だけ大きな文字列
    private static String next(String encoded) {
        assert encoded.isEmpty() == false;

        // 最後の文字を1文字すすめる(今回は桁上がりを無視)
        char[] content = encoded.toCharArray();
        content[content.length - 1]++;
        return String.valueOf(content);
    }

    // エンコードされた文字列の一覧を表示
    private static void print(String title, Iterable<String> encoded) {
        System.out.println("==== " + title);
        for (String s : encoded) {
            // 区切り文字で分割して表示
            String[] split = s.split("\u0000");
            System.out.println(Arrays.toString(split));
        }
    }

    // エンコードされた文字列の中から、最後のセグメントを取り出す
    private static String extractLast(String encoded) {
        assert encoded.isEmpty() == false;

        // エンコードされているので末尾はNULL文字
        int len = encoded.length();
        assert encoded.charAt(len - 1) == 0;

        // 最後のセグメントの先頭にある区切り文字を探す
        int lastStart = encoded.lastIndexOf(0, len - 2);

        // エンコード前のセグメントを抽出
        return encoded.substring(lastStart + 1, len - 1);
    }

    // エンコードされた文字列の末尾に情報を追加する
    private static String append(String encoded, String s) {
        StringBuilder buf = new StringBuilder();
        buf.append(encoded);
        buf.append(s);
        buf.append((char) 0);
        return buf.toString();
    }
}