Groonga - fulltext search engine.

[Groonga-commit] groonga/grnxx at ce6e495 [master] Add an initial implementation of dummy12.

susumu.yata null+****@clear*****
Thu Feb 27 18:42:27 JST 2014

• Previous message: [Groonga-commit] droonga/droonga.org at 207ec0a [gh-pages] ja: Translate
• Next message: [Groonga-commit] droonga/droonga.org at ed23a73 [gh-pages] Add more basic descriptions about the Droonga itself.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

susumu.yata	2014-02-27 18:42:27 +0900 (Thu, 27 Feb 2014)

  New Revision: ce6e495664789192eb4533aa45e5abab4d989a51
  https://github.com/groonga/grnxx/commit/ce6e495664789192eb4533aa45e5abab4d989a51

  Message:
    Add an initial implementation of dummy12.

  Added files:
    lib/grnxx/calc.cpp
    lib/grnxx/calc.hpp
    lib/grnxx/calc_impl.cpp
    lib/grnxx/calc_impl.hpp
    lib/grnxx/column.cpp
    lib/grnxx/column.hpp
    lib/grnxx/column_impl.cpp
    lib/grnxx/column_impl.hpp
    lib/grnxx/database.cpp
    lib/grnxx/database.hpp
    lib/grnxx/datum.cpp
    lib/grnxx/datum.hpp
    lib/grnxx/index.cpp
    lib/grnxx/index.hpp
    lib/grnxx/sorter.cpp
    lib/grnxx/sorter.hpp
    lib/grnxx/sorter_impl.cpp
    lib/grnxx/sorter_impl.hpp
    lib/grnxx/string.cpp
    lib/grnxx/string.hpp
    lib/grnxx/table.cpp
    lib/grnxx/table.hpp
    lib/grnxx/timer.cpp
    lib/grnxx/timer.hpp
    lib/grnxx/types.cpp
    lib/grnxx/types.hpp
  Modified files:
    lib/grnxx/Makefile.am
    lib/grnxx/library.cpp
    lib/grnxx/library.hpp
    src/grnxx.cpp
    test/test_grnxx.cpp

  Modified: lib/grnxx/Makefile.am (+27 -1)
===================================================================
--- lib/grnxx/Makefile.am    2014-02-24 16:02:00 +0900 (df693e0)
+++ lib/grnxx/Makefile.am    2014-02-27 18:42:27 +0900 (2f77bb5)
@@ -9,11 +9,37 @@ lib_LTLIBRARIES = libgrnxx.la
 libgrnxx_la_LDFLAGS = @AM_LTLDFLAGS@
 
 libgrnxx_la_SOURCES =			\
-	library.cpp
+	calc.cpp			\
+	calc_impl.cpp			\
+	column.cpp			\
+	column_impl.cpp			\
+	database.cpp			\
+	datum.cpp			\
+	index.cpp			\
+	library.cpp			\
+	sorter.cpp			\
+	sorter_impl.cpp			\
+	string.cpp			\
+	table.cpp			\
+	timer.cpp			\
+	types.cpp
 
 libgrnxx_includedir = ${includedir}/grnxx
 libgrnxx_include_HEADERS =		\
+	calc.hpp			\
+	calc_impl.hpp			\
+	column.hpp			\
+	column_impl.hpp			\
+	database.hpp			\
+	datum.hpp			\
+	index.hpp			\
 	library.hpp			\
+	sorter.hpp			\
+	sorter_impl.hpp			\
+	string.hpp			\
+	table.hpp			\
+	types.hpp			\
+	timer.hpp			\
 	version.h
 
 EXTRA_DIST = version.sh

  Added: lib/grnxx/calc.cpp (+16 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/calc.cpp    2014-02-27 18:42:27 +0900 (b55c497)
@@ -0,0 +1,16 @@
+#include "grnxx/calc.hpp"
+
+#include "grnxx/calc_impl.hpp"
+
+namespace grnxx {
+
+// 演算器を作成する．
+Calc *CalcHelper::create(const Table *table, const String &query) {
+  std::unique_ptr<CalcImpl> calc(new CalcImpl);
+  if (!calc->parse(table, query)) {
+    return nullptr;
+  }
+  return calc.release();
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/calc.hpp (+30 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/calc.hpp    2014-02-27 18:42:27 +0900 (563e1b5)
@@ -0,0 +1,30 @@
+#ifndef GRNXX_CALC_HPP
+#define GRNXX_CALC_HPP
+
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+class Calc {
+ public:
+  // 演算器を初期化する．
+  Calc() {}
+  // 演算器を破棄する．
+  virtual ~Calc() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  virtual Int64 filter(RowID *row_ids, Int64 num_row_ids) = 0;
+
+  // 条件がひとつでもあれば true を返し，そうでなければ false を返す．
+  virtual bool empty() const = 0;
+};
+
+class CalcHelper {
+ public:
+  // 演算器を作成する．
+  static Calc *create(const Table *table, const String &query);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_CALC_HPP

  Added: lib/grnxx/calc_impl.cpp (+1639 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/calc_impl.cpp    2014-02-27 18:42:27 +0900 (3d27589)
@@ -0,0 +1,1639 @@
+#include "grnxx/calc_impl.hpp"
+
+#include "grnxx/column_impl.hpp"
+#include "grnxx/table.hpp"
+
+namespace grnxx {
+namespace {
+
+// 定数と対応するノード．
+template <typename T>
+class ConstantNode : public CalcNode {
+ public:
+  // 指定された定数と対応するノードとして初期化する．
+  explicit ConstantNode(T value)
+      : CalcNode(CONSTANT_NODE, TypeTraits<T>::data_type()),
+        value_(value) {}
+  // ノードを破棄する．
+  ~ConstantNode() {}
+
+  // 指定された値を返す．
+  T get(Int64 i, RowID row_id) const {
+    return value_;
+  }
+
+ private:
+  T value_;
+};
+
+// 真偽値と対応するノード．
+template <>
+class ConstantNode<Boolean> : public CalcNode {
+ public:
+  // 指定された定数と対応するノードとして初期化する．
+  explicit ConstantNode(Boolean value)
+      : CalcNode(CONSTANT_NODE, TypeTraits<Boolean>::data_type()),
+        value_(value) {}
+  // ノードを破棄する．
+  ~ConstantNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids) {
+    // 真のときは何もせず，偽のときはクリアする．
+    return value_ ? num_row_ids : 0;
+  }
+
+  // 指定された値を返す．
+  Boolean get(Int64 i, RowID row_id) const {
+    return value_;
+  }
+
+ private:
+  Boolean value_;
+};
+
+// 文字列の定数と対応するノード．
+template <>
+class ConstantNode<String> : public CalcNode {
+ public:
+  // 指定された定数と対応するノードとして初期化する．
+  explicit ConstantNode(const String &value)
+      : CalcNode(CONSTANT_NODE, TypeTraits<String>::data_type()),
+        value_(),
+        buf_() {
+    buf_.assign(reinterpret_cast<const char *>(value.data()), value.size());
+    value_ = buf_;
+  }
+  // ノードを破棄する．
+  ~ConstantNode() {}
+
+  // 指定された値を返す．
+  String get(Int64 i, RowID row_id) const {
+    return value_;
+  }
+
+ private:
+  String value_;
+  std::string buf_;
+};
+
+// カラムと対応するノード．
+template <typename T>
+class ColumnNode : public CalcNode {
+ public:
+  // 指定されたカラムに対応するノードとして初期化する．
+  explicit ColumnNode(Column *column)
+      : CalcNode(COLUMN_NODE, TypeTraits<T>::data_type()),
+        column_(static_cast<ColumnImpl<T> *>(column)) {}
+  // ノードを破棄する．
+  ~ColumnNode() {}
+
+  // 指定された値を返す．
+  T get(Int64 i, RowID row_id) const {
+    return column_->get(row_id);
+  }
+
+ private:
+  ColumnImpl<T> *column_;
+};
+
+// 真偽値のカラムと対応するノード．
+template <>
+class ColumnNode<Boolean> : public CalcNode {
+ public:
+  // 指定されたカラムに対応するノードとして初期化する．
+  explicit ColumnNode(Column *column)
+      : CalcNode(COLUMN_NODE, TypeTraits<Boolean>::data_type()),
+        column_(static_cast<ColumnImpl<Boolean> *>(column)) {}
+  // ノードを破棄する．
+  ~ColumnNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 指定された値を返す．
+  Boolean get(Int64 i, RowID row_id) const {
+    return column_->get(row_id);
+  }
+
+ private:
+  ColumnImpl<Boolean> *column_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+Int64 ColumnNode<Boolean>::filter(RowID *row_ids, Int64 num_row_ids) {
+  // 真になる行だけを残す．
+  Int64 count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    RowID row_id = row_ids[i];
+    if (column_->get(row_id)) {
+      row_ids[count++] = row_id;
+    }
+  }
+  return count;
+}
+
+// 演算子と対応するノード．
+template <typename T>
+class OperatorNode : public CalcNode {
+ public:
+  // 指定された定数と対応するノードとして初期化する．
+  OperatorNode()
+      : CalcNode(OPERATOR_NODE, TypeTraits<T>::data_type()),
+        data_() {}
+  // ノードを破棄する．
+  virtual ~OperatorNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  virtual Int64 filter(RowID *row_ids, Int64 num_row_ids) {
+    // すべて破棄する．
+    return 0;
+  }
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  virtual void fill(const RowID *row_ids, Int64 num_row_ids) {
+    // 致命的なエラーを回避するために領域を確保する．
+    data_.resize(num_row_ids);
+  }
+
+  // 指定された値を返す．
+  T get(Int64 i, RowID row_id) const {
+    return data_[i];
+  }
+
+ protected:
+  std::vector<T> data_;
+};
+
+// LOGICAL_NOT と対応するノード．
+template <typename T>
+class LogicalNotNode : public OperatorNode<Boolean> {
+ public:
+  // 指定されたノードに対する LOGICAL_NOT と対応するノードとして初期化する．
+  explicit LogicalNotNode(CalcNode *operand)
+      : OperatorNode<Boolean>(),
+        operand_(static_cast<T *>(operand)) {}
+  // ノードを破棄する．
+  ~LogicalNotNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ private:
+  T *operand_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+template <typename T>
+Int64 LogicalNotNode<T>::filter(RowID *row_ids, Int64 num_row_ids) {
+  // 真になる行だけを残す．
+  operand_->fill(row_ids, num_row_ids);
+  Int64 count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    RowID row_id = row_ids[i];
+    if (!operand_->get(i, row_id)) {
+      row_ids[count++] = row_id;
+    }
+  }
+  return count;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+template <typename T>
+void LogicalNotNode<T>::fill(const RowID *row_ids, Int64 num_row_ids) {
+  operand_->fill(row_ids, num_row_ids);
+  data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    data_[i] = !operand_->get(i, row_ids[i]);
+  }
+}
+
+// 比較演算子の実装．
+template <typename T> using EqualOperator = std::equal_to<T>;
+template <typename T> using NotEqualOperator = std::not_equal_to<T>;
+template <typename T> using LessOperator = std::less<T>;
+template <typename T> using LessEqualOperator = std::less_equal<T>;
+template <typename T> using GreaterOperator = std::greater<T>;
+template <typename T> using GreaterEqualOperator = std::greater_equal<T>;
+
+// 比較演算子と対応するノード．
+template <typename T, typename U, typename V>
+class ComparerNode : public OperatorNode<Boolean> {
+ public:
+  // 指定されたノードに対する比較演算子と対応するノードとして初期化する．
+  explicit ComparerNode(CalcNode *lhs, CalcNode *rhs)
+      : OperatorNode<Boolean>(),
+        comparer_(),
+        lhs_(static_cast<U *>(lhs)),
+        rhs_(static_cast<V *>(rhs)) {}
+  // ノードを破棄する．
+  ~ComparerNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ private:
+  T comparer_;
+  U *lhs_;
+  V *rhs_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+template <typename T, typename U, typename V>
+Int64 ComparerNode<T, U, V>::filter(RowID *row_ids, Int64 num_row_ids) {
+  // 真になる行だけを残す．
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  Int64 count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    RowID row_id = row_ids[i];
+    if (comparer_(lhs_->get(i, row_ids[i]), rhs_->get(i, row_ids[i]))) {
+      row_ids[count++] = row_id;
+    }
+  }
+  return count;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+template <typename T, typename U, typename V>
+void ComparerNode<T, U, V>::fill(const RowID *row_ids, Int64 num_row_ids) {
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    data_[i] = comparer_(lhs_->get(i, row_ids[i]), rhs_->get(i, row_ids[i]));
+  }
+}
+
+// LOGICAL_AND と対応するノード．
+template <typename T, typename U>
+class LogicalAndNode : public OperatorNode<Boolean> {
+ public:
+  // 指定されたノードに対する LOGICAL_AND と対応するノードとして初期化する．
+  explicit LogicalAndNode(CalcNode *lhs, CalcNode *rhs)
+      : OperatorNode<Boolean>(),
+        lhs_(static_cast<T *>(lhs)),
+        rhs_(static_cast<U *>(rhs)) {}
+  // ノードを破棄する．
+  ~LogicalAndNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ private:
+  T *lhs_;
+  U *rhs_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+template <typename T, typename U>
+Int64 LogicalAndNode<T, U>::filter(RowID *row_ids, Int64 num_row_ids) {
+  num_row_ids = lhs_->filter(row_ids, num_row_ids);
+  num_row_ids = rhs_->filter(row_ids, num_row_ids);
+  return num_row_ids;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+template <typename T, typename U>
+void LogicalAndNode<T, U>::fill(const RowID *row_ids, Int64 num_row_ids) {
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    data_[i] = lhs_->get(i, row_ids[i]) && rhs_->get(i, row_ids[i]);
+  }
+}
+
+// LOGICAL_OR と対応するノード．
+template <typename T, typename U>
+class LogicalOrNode : public OperatorNode<Boolean> {
+ public:
+  // 指定されたノードに対する LOGICAL_OR と対応するノードとして初期化する．
+  explicit LogicalOrNode(CalcNode *lhs, CalcNode *rhs)
+      : OperatorNode<Boolean>(),
+        lhs_(static_cast<T *>(lhs)),
+        rhs_(static_cast<U *>(rhs)),
+        local_row_ids_() {}
+  // ノードを破棄する．
+  ~LogicalOrNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ private:
+  T *lhs_;
+  U *rhs_;
+  std::vector<RowID> local_row_ids_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+template <typename T, typename U>
+Int64 LogicalOrNode<T, U>::filter(RowID *row_ids, Int64 num_row_ids) {
+  // 入力のコピーを作成する．
+  // 番兵を追加しても大丈夫なように，サイズは num_row_ids + 2 としている．
+  local_row_ids_.resize(num_row_ids + 2);
+  RowID *left_row_ids = &*local_row_ids_.begin();
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    local_row_ids_[i] = row_ids[i];
+  }
+
+  // 入力のコピーを左のフィルタにかける．
+  Int64 num_left_row_ids = lhs_->filter(left_row_ids, num_row_ids);
+  if (num_left_row_ids == 0) {
+    // すべて偽なので，入力を丸ごと右のフィルタにかける．
+    return rhs_->filter(row_ids, num_row_ids);
+  } else if (num_left_row_ids == num_row_ids) {
+    // すべて真なので，何もしなくてよい．
+    return num_row_ids;
+  }
+
+  // 番兵を配置する．
+  left_row_ids[num_left_row_ids] = 0;
+
+  // 左のフィルタにかけて残らなかった行 ID を列挙する．
+  RowID *right_row_ids = left_row_ids + num_left_row_ids + 1;
+  Int64 left_count = 0;
+  Int64 right_count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    if (row_ids[i] == left_row_ids[left_count]) {
+      ++left_count;
+    } else {
+      right_row_ids[right_count] = row_ids[i];
+      ++right_count;
+    }
+  }
+
+  // 右のフィルタにかける．
+  Int64 num_right_row_ids = rhs_->filter(right_row_ids, right_count);
+  if (num_right_row_ids == 0) {
+    // すべて偽なので，左のをそのまま返せばよい．
+    for (Int64 i = 0; i < num_left_row_ids; ++i) {
+      row_ids[i] = left_row_ids[i];
+    }
+    return num_left_row_ids;
+  } else if (num_right_row_ids == right_count) {
+    // すべて真なので，何もしなくてよい．
+    return num_row_ids;
+  }
+
+  // 番兵を配置する．
+  right_row_ids[num_right_row_ids] = 0;
+
+  // 左右の結果をマージする（どちらかに含まれている行 ID を取り出す）．
+  left_count = 0;
+  right_count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    if (row_ids[i] == left_row_ids[left_count]) {
+      row_ids[left_count + right_count] = row_ids[i];
+      ++left_count;
+    } else if (row_ids[i] == right_row_ids[right_count]) {
+      row_ids[left_count + right_count] = row_ids[i];
+      ++right_count;
+    }
+  }
+  return left_count + right_count;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+template <typename T, typename U>
+void LogicalOrNode<T, U>::fill(const RowID *row_ids, Int64 num_row_ids) {
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    data_[i] = lhs_->get(i, row_ids[i]) || rhs_->get(i, row_ids[i]);
+  }
+}
+
+// FIXME: 以下，同じような演算子を定義するのはマクロで簡略化できるし，
+//        そうした方が誤りを減らせそうである．
+
+// FIXME: オーバーフロー時の例外には専用の型を用意すべきである．
+
+// 無効な型．
+struct InvalidResult {};
+
+// 算術加算．
+//Int64 plus_with_overflow_check(Int64 lhs, Int64 rhs) {
+//  Int64 result = lhs + rhs;
+//  lhs ^= result;
+//  rhs ^= result;
+//  if ((lhs & rhs) >> 63) {
+//    throw "overflow or underflow!";
+//  }
+//  return result;
+//}
+#ifdef __clang__
+Int64 plus_with_overflow_check(Int64 lhs, Int64 rhs) {
+  UInt8 overflow_flag = 0;
+  __asm__ ("add %2, %0; seto %1;"
+           : "+r" (lhs), "=r" (overflow_flag) : "r" (rhs));
+  if (overflow_flag) {
+    throw "overflow or underflow!";
+  }
+  return lhs;
+}
+#else  // __clang__
+Int64 plus_with_overflow_check(Int64 lhs, Int64 rhs) {
+  __asm__ volatile ("add %1, %0;"
+                    : "+r" (lhs) : "r" (rhs));
+  __asm__ goto ("jo %l0;"
+                : : : : PLUS_WITH_OVERFLOW_CHECK_LABEL);
+  return lhs;
+
+ PLUS_WITH_OVERFLOW_CHECK_LABEL:
+  throw "overflow or underflow!";
+}
+#endif  // __clang__
+template <typename T, typename U> struct PlusOperator {
+  using Result = InvalidResult;
+  using Lhs = T;
+  using Rhs = U;
+};
+template <> struct PlusOperator<Int64, Int64> {
+  using Result = Int64;
+  using Lhs = Int64;
+  using Rhs = Int64;
+  Result operator()(Int64 lhs, Int64 rhs) const {
+    return plus_with_overflow_check(lhs, rhs);
+  }
+};
+template <> struct PlusOperator<Float, Float> {
+  using Result = Float;
+  using Lhs = Float;
+  using Rhs = Float;
+  Result operator()(Float lhs, Float rhs) const { return lhs + rhs; }
+};
+
+// 算術減算．
+//Int64 minus_with_overflow_check(Int64 lhs, Int64 rhs) {
+//  Int64 result = lhs - rhs;
+//  rhs ^= lhs;
+//  lhs ^= result;
+//  if ((lhs & rhs) >> 63) {
+//    throw "overflow or underflow!";
+//  }
+//  return result;
+//}
+#ifdef __clang__
+Int64 minus_with_overflow_check(Int64 lhs, Int64 rhs) {
+  UInt8 overflow_flag = 0;
+  __asm__ ("sub %2, %0; seto %1;"
+           : "+r" (lhs), "=r" (overflow_flag) : "r" (rhs));
+  if (overflow_flag) {
+    throw "overflow or underflow!";
+  }
+  return lhs;
+}
+#else  // __clang__
+Int64 minus_with_overflow_check(Int64 lhs, Int64 rhs) {
+  __asm__ volatile ("sub %1, %0;"
+                    : "+r" (lhs) : "r" (rhs));
+  __asm__ goto ("jo %l0;"
+                : : : : MINUS_WITH_OVERFLOW_CHECK_LABEL);
+  return lhs;
+
+ MINUS_WITH_OVERFLOW_CHECK_LABEL:
+  throw "overflow or underflow!";
+}
+#endif  // __clang__
+template <typename T, typename U> struct MinusOperator {
+  using Result = InvalidResult;
+  using Lhs = T;
+  using Rhs = U;
+};
+template <> struct MinusOperator<Int64, Int64> {
+  using Result = Int64;
+  using Lhs = Int64;
+  using Rhs = Int64;
+  Result operator()(Int64 lhs, Int64 rhs) const {
+    return minus_with_overflow_check(lhs, rhs);
+  }
+};
+template <> struct MinusOperator<Float, Float> {
+  using Result = Float;
+  using Lhs = Float;
+  using Rhs = Float;
+  Result operator()(Float lhs, Float rhs) const { return lhs - rhs; }
+};
+
+// 算術乗算．
+//Int64 multiplies_with_overflow_check(Int64 lhs, Int64 rhs) {
+//  if (lhs == 0) {
+//    return 0;
+//  }
+//  Int64 result = lhs * rhs;
+//  if ((result / rhs) != lhs) {
+//    throw "overflow or underflow";
+//  }
+//  return result;
+//}
+#ifdef __clang__
+Int64 multiplies_with_overflow_check(Int64 lhs, Int64 rhs) {
+  UInt8 overflow_flag = 0;
+  __asm__ ("imul %2, %0; seto %1;"
+           : "+r" (lhs), "=r" (overflow_flag) : "r" (rhs));
+  if (overflow_flag) {
+    throw "overflow or underflow!";
+  }
+  return lhs;
+}
+#else  // __clang__
+Int64 multiplies_with_overflow_check(Int64 lhs, Int64 rhs) {
+  __asm__ volatile ("imul %1, %0;"
+                    : "+r" (lhs) : "r" (rhs));
+  __asm__ goto ("jo %l0;"
+                : : : : MULTIPLIES_WITH_OVERFLOW_CHECK_LABEL);
+  return lhs;
+
+ MULTIPLIES_WITH_OVERFLOW_CHECK_LABEL:
+  throw "overflow or underflow!";
+}
+#endif  // __clang__
+template <typename T, typename U> struct MultipliesOperator {
+  using Result = InvalidResult;
+  using Lhs = T;
+  using Rhs = U;
+};
+template <> struct MultipliesOperator<Int64, Int64> {
+  using Result = Int64;
+  using Lhs = Int64;
+  using Rhs = Int64;
+  Result operator()(Int64 lhs, Int64 rhs) const {
+    return multiplies_with_overflow_check(lhs, rhs);
+  }
+};
+template <> struct MultipliesOperator<Float, Float> {
+  using Result = Float;
+  using Lhs = Float;
+  using Rhs = Float;
+  Result operator()(Float lhs, Float rhs) const { return lhs * rhs; }
+};
+
+// 算術除算．
+Int64 divides_with_overflow_check(Int64 lhs, Int64 rhs) {
+  if (rhs == 0) {
+    throw "division by zero";
+  }
+  if ((lhs == INT64_MIN) && (rhs == -1)) {
+    throw "overflow or underflow";
+  }
+  return lhs / rhs;
+}
+template <typename T, typename U> struct DividesOperator {
+  using Result = InvalidResult;
+  using Lhs = T;
+  using Rhs = U;
+};
+template <> struct DividesOperator<Int64, Int64> {
+  using Result = Int64;
+  using Lhs = Int64;
+  using Rhs = Int32;
+  Result operator()(Int64 lhs, Int64 rhs) const {
+    return divides_with_overflow_check(lhs, rhs);
+  }
+};
+template <> struct DividesOperator<Float, Float> {
+  using Result = Float;
+  using Lhs = Float;
+  using Rhs = Float;
+  Result operator()(Float lhs, Float rhs) const { return lhs / rhs; }
+};
+
+// 算術剰余算．
+Int64 modulus_with_overflow_check(Int64 lhs, Int64 rhs) {
+  if (rhs == 0) {
+    throw "division by zero";
+  }
+  if ((lhs == INT64_MIN) && (rhs == -1)) {
+    throw "overflow or underflow";
+  }
+  return lhs % rhs;
+}
+template <typename T, typename U> struct ModulusOperator {
+  using Result = InvalidResult;
+  using Lhs = T;
+  using Rhs = U;
+};
+template <> struct ModulusOperator<Int64, Int64> {
+  using Result = Int64;
+  using Lhs = Int64;
+  using Rhs = Int64;
+  Result operator()(Int64 lhs, Int64 rhs) const {
+    return modulus_with_overflow_check(lhs, rhs);
+  }
+};
+
+// 四則演算と対応するノード．
+template <typename T, typename U, typename V>
+class ArithmeticNode : public OperatorNode<typename T::Result> {
+ public:
+  using Result = typename T::Result;
+
+  // 指定されたノードに対する四則演算と対応するノードとして初期化する．
+  explicit ArithmeticNode(CalcNode *lhs, CalcNode *rhs)
+      : OperatorNode<Result>(),
+        operator_(),
+        lhs_(static_cast<U *>(lhs)),
+        rhs_(static_cast<V *>(rhs)) {}
+  // ノードを破棄する．
+  ~ArithmeticNode() {}
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ private:
+  T operator_;
+  U *lhs_;
+  V *rhs_;
+};
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+template <typename T, typename U, typename V>
+Int64 ArithmeticNode<T, U, V>::filter(RowID *row_ids, Int64 num_row_ids) {
+  // 真になる行だけを残す．
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  Int64 count = 0;
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    RowID row_id = row_ids[i];
+    if (operator_(lhs_->get(i, row_ids[i]), rhs_->get(i, row_ids[i]))) {
+      row_ids[count++] = row_id;
+    }
+  }
+  return count;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+template <typename T, typename U, typename V>
+void ArithmeticNode<T, U, V>::fill(const RowID *row_ids, Int64 num_row_ids) {
+  lhs_->fill(row_ids, num_row_ids);
+  rhs_->fill(row_ids, num_row_ids);
+  this->data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    this->data_[i] = operator_(lhs_->get(i, row_ids[i]),
+                               rhs_->get(i, row_ids[i]));
+  }
+}
+
+// 四則演算と対応するノードの作成を補助する．
+template <typename T, typename U = typename T::Result>
+class ArithmeticNodeHelper {
+ public:
+  template <typename V, typename W>
+  static CalcNode *create(CalcNode *lhs, CalcNode *rhs) {
+    return new ArithmeticNode<T, V, W>(lhs, rhs);
+  }
+
+  static CalcNode *create(typename T::Lhs lhs, typename T::Rhs rhs) {
+    return new ConstantNode<typename T::Result>(T()(lhs, rhs));
+  }
+};
+template <typename T>
+class ArithmeticNodeHelper<T, InvalidResult> {
+ public:
+  template <typename V, typename W>
+  static CalcNode *create(CalcNode *lhs, CalcNode *rhs) {
+    return nullptr;
+  }
+
+  static CalcNode *create(typename T::Lhs lhs, typename T::Rhs rhs) {
+    return nullptr;
+  }
+};
+
+}  // namespace
+
+// 指定された種類のノードとして初期化する．
+CalcNode::CalcNode(CalcNodeType type, DataType data_type)
+    : type_(type),
+      data_type_(data_type) {}
+
+// ノードを破棄する．
+CalcNode::~CalcNode() {}
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+Int64 CalcNode::filter(RowID *row_ids, Int64 num_row_ids) {
+  // すべて破棄する．
+  return 0;
+}
+
+// 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+void CalcNode::fill(const RowID *row_ids, Int64 num_row_ids) {
+  // 何もしない
+}
+
+// 二項演算子の優先度を返す．
+int CalcToken::get_binary_operator_priority(BinaryOperatorType operator_type) {
+  switch (operator_type) {
+    case EQUAL_OPERATOR: {
+      return 6;
+    }
+    case NOT_EQUAL_OPERATOR: {
+      return 6;
+    }
+    case LESS_OPERATOR: {
+      return 7;
+    }
+    case LESS_EQUAL_OPERATOR: {
+      return 7;
+    }
+    case GREATER_OPERATOR: {
+      return 7;
+    }
+    case GREATER_EQUAL_OPERATOR: {
+      return 7;
+    }
+    case LOGICAL_AND_OPERATOR: {
+      return 2;
+    }
+    case LOGICAL_OR_OPERATOR: {
+      return 1;
+    }
+    case PLUS_OPERATOR: {
+      return 8;
+    }
+    case MINUS_OPERATOR: {
+      return 8;
+    }
+    case MULTIPLIES_OPERATOR: {
+      return 9;
+    }
+    case DIVIDES_OPERATOR: {
+      return 9;
+    }
+    case MODULUS_OPERATOR: {
+      return 9;
+    }
+  }
+  return 0;
+}
+
+CalcImpl::CalcImpl()
+    : Calc(),
+      table_(nullptr),
+      nodes_() {}
+
+CalcImpl::~CalcImpl() {}
+
+// 指定された文字列に対応する演算器を作成する．
+bool CalcImpl::parse(const Table *table, const String &query) try {
+  if (!table) {
+    return false;
+  }
+  table_ = table;
+  nodes_.clear();
+
+  // 指定された文字列をトークンに分割する．
+  // 先頭と末尾に括弧を配置することで例外をなくす．
+  std::vector<CalcToken> tokens;
+  tokens.push_back(CalcToken(LEFT_BRACKET));
+  if (!tokenize_query(query, &tokens)) {
+    return false;
+  }
+  tokens.push_back(CalcToken(RIGHT_BRACKET));
+
+  // トークンがひとつもないときは何もしない．
+  if (tokens.size() == 2) {
+    return true;
+  }
+
+  // スタックを使って木を構築する．
+  std::vector<CalcToken> stack;
+  for (const auto &token : tokens) {
+    if (!push_token(token, &stack)) {
+      return false;
+    }
+  }
+
+  // 最終的にはトークンがひとつだけ残らなければならない．
+  if (stack.size() != 1) {
+    return false;
+  }
+  return true;
+} catch (const char *) {
+  // ゼロによる除算もしくはオーバーフローによる例外．
+  return false;
+}
+
+// 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+Int64 CalcImpl::filter(RowID *row_ids, Int64 num_row_ids) {
+  if (nodes_.empty()) {
+    return num_row_ids;
+  }
+  try {
+    return nodes_.back()->filter(row_ids, num_row_ids);
+  } catch (const char *) {
+    // ゼロによる除算もしくはオーバーフローによる例外．
+    return 0;
+  }
+}
+
+// 演算が何も指定されていなければ true を返し，そうでなければ false を返す．
+bool CalcImpl::empty() const {
+  return nodes_.empty();
+}
+
+// クエリをトークンに分割する．
+bool CalcImpl::tokenize_query(const String &query,
+                              std::vector<CalcToken> *tokens) {
+  String left = query;
+  while (!left.empty()) {
+    // 先頭の空白は無視する．
+    auto delim_pos = left.find_first_not_of(" \t\r\n");
+    if (delim_pos == left.npos) {
+      break;
+    }
+    left = left.except_prefix(delim_pos);
+    switch (left[0]) {
+      case '!': {
+        if (left[1] == '=') {
+          tokens->push_back(CalcToken(NOT_EQUAL_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          tokens->push_back(CalcToken(LOGICAL_NOT_OPERATOR));
+          left = left.except_prefix(1);
+        }
+        break;
+      }
+      case '=': {
+        if (left[1] == '=') {
+          tokens->push_back(CalcToken(EQUAL_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          return false;
+        }
+        break;
+      }
+      case '<': {
+        if (left[1] == '=') {
+          tokens->push_back(CalcToken(LESS_EQUAL_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          tokens->push_back(CalcToken(LESS_OPERATOR));
+          left = left.except_prefix(1);
+        }
+        break;
+      }
+      case '>': {
+        if (left[1] == '=') {
+          tokens->push_back(CalcToken(GREATER_EQUAL_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          tokens->push_back(CalcToken(GREATER_OPERATOR));
+          left = left.except_prefix(1);
+        }
+        break;
+      }
+      case '&': {
+        if (left[1] == '&') {
+          tokens->push_back(CalcToken(LOGICAL_AND_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          return false;
+        }
+        break;
+      }
+      case '|': {
+        if (left[1] == '|') {
+          tokens->push_back(CalcToken(LOGICAL_OR_OPERATOR));
+          left = left.except_prefix(2);
+        } else {
+          return false;
+        }
+        break;
+      }
+      case '+': {
+        tokens->push_back(CalcToken(PLUS_OPERATOR));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '-': {
+        tokens->push_back(CalcToken(MINUS_OPERATOR));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '*': {
+        tokens->push_back(CalcToken(MULTIPLIES_OPERATOR));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '/': {
+        tokens->push_back(CalcToken(DIVIDES_OPERATOR));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '%': {
+        tokens->push_back(CalcToken(MODULUS_OPERATOR));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '(': {
+        tokens->push_back(CalcToken(LEFT_BRACKET));
+        left = left.except_prefix(1);
+        break;
+      }
+      case ')': {
+        tokens->push_back(CalcToken(RIGHT_BRACKET));
+        left = left.except_prefix(1);
+        break;
+      }
+      case '"': {
+        auto end = left.find_first_of('"', 1);
+        if (end == left.npos) {
+          // 文字列の終端がないときは失敗する．
+          return false;
+        }
+        // 文字列の定数に対応するノードを作成する．
+        String value = left.extract(1, end - 1);
+        auto node = create_string_node(value);
+        if (!node) {
+          return false;
+        }
+        tokens->push_back(CalcToken(node));
+        left = left.except_prefix(end + 1);
+        break;
+      }
+      default: {
+        auto end = left.find_first_of(" \t\r\n!=<>&|+-*/%()");
+        if (end == left.npos) {
+          end = left.size();
+        }
+        // カラムもしくは Boolean, Int64, Float の定数に対応するノードを作成する．
+        String token = left.prefix(end);
+        auto node = create_column_node(token);
+        if (!node) {
+          if (token == "TRUE") {
+            node = create_boolean_node(true);
+          } else if (token == "FALSE") {
+            node = create_boolean_node(false);
+          } else if (token.find_first_of('.') != token.npos) {
+            node = create_float_node(static_cast<Float>(std::stod(
+                std::string(reinterpret_cast<const char *>(token.data()),
+                            token.size()))));
+          } else {
+            node = create_int64_node(static_cast<Int64>(std::stol(
+                std::string(reinterpret_cast<const char *>(token.data()),
+                            token.size()))));
+          }
+          if (!node) {
+            return false;
+          }
+        }
+        tokens->push_back(CalcToken(node));
+        left = left.except_prefix(end);
+        break;
+      }
+    }
+  }
+  return true;
+}
+
+// トークンをひとつずつ解釈する．
+bool CalcImpl::push_token(const CalcToken &token,
+                          std::vector<CalcToken> *stack) {
+  switch (token.type()) {
+    case BRACKET_TOKEN: {
+      if (token.bracket_type() == LEFT_BRACKET) {
+        // 開き括弧の直前にノードがあるのはおかしい．
+        if (!stack->empty() && (stack->back().type() == NODE_TOKEN)) {
+          return false;
+        }
+        stack->push_back(token);
+      } else {
+        // 閉じ括弧の直前にはノードが必要であり，それより前に開き括弧が必要である．
+        if ((stack->size() < 2) || (stack->back().type() != NODE_TOKEN)) {
+          return false;
+        }
+        // 括弧内にある演算子をすべて解決する．
+        // 単項演算子は既に片付いているはずなので，二項演算子のみに注意すればよい．
+        while (stack->size() >= 3) {
+          CalcToken operator_token = (*stack)[stack->size() - 2];
+          if (operator_token.type() != BINARY_OPERATOR_TOKEN) {
+            break;
+          }
+          CalcToken lhs_token = (*stack)[stack->size() - 3];
+          CalcToken rhs_token = (*stack)[stack->size() - 1];
+          stack->resize(stack->size() - 3);
+
+          // 演算に対応するノードに置き換える．
+          auto node = create_binary_operator_node(
+              operator_token.binary_operator_type(),
+              lhs_token.node(), rhs_token.node());
+          if (!node) {
+            return false;
+          }
+          if (!push_token(CalcToken(node), stack)) {
+            return false;
+          }
+        }
+        // 括弧を取り除き，中身だけを残す．
+        if ((stack->size() < 2) ||
+            ((*stack)[stack->size() - 2].type() != BRACKET_TOKEN) ||
+            ((*stack)[stack->size() - 2].bracket_type() != LEFT_BRACKET)) {
+          return false;
+        }
+        (*stack)[stack->size() - 2] = stack->back();
+        stack->pop_back();
+        break;
+      }
+      break;
+    }
+    case NODE_TOKEN: {
+      if (stack->empty()) {
+        // 最初のトークンであれば追加する．
+        stack->push_back(token);
+        break;
+      }
+      // ノードが連続するのはおかしい．
+      if (stack->back().type() == NODE_TOKEN) {
+        return false;
+      }
+      // 直前が単項演算子でなければ末尾に追加する．
+      if (stack->back().type() != UNARY_OPERATOR_TOKEN) {
+        stack->push_back(token);
+        break;
+      }
+      // 直前の単項演算子を適用した結果に置き換える．
+      auto node = create_unary_operator_node(
+          LOGICAL_NOT_OPERATOR, stack->back().node());
+      if (!node) {
+        return false;
+      }
+      stack->pop_back();
+      // FIXME: 単項演算子が大量に連続していると，再帰呼び出しが深くなりすぎて
+      //        スタックオーバーフローになる．
+      if (!push_token(CalcToken(node), stack)) {
+        return false;
+      }
+      break;
+    }
+    case UNARY_OPERATOR_TOKEN: {
+      // 単項演算子の直前にオペランドがあるのはおかしい．
+      if (!stack->empty() && (stack->back().type() == NODE_TOKEN)) {
+        return false;
+      }
+      stack->push_back(token);
+      break;
+    }
+    case BINARY_OPERATOR_TOKEN: {
+      // 二項演算子の直前にはノードがなければならない．
+      if (stack->empty() || (stack->back().type() != NODE_TOKEN)) {
+        return false;
+      }
+      // 前方に優先度の高い二項演算子があるときは，それらを先に適用する．
+      while (stack->size() >= 3) {
+        CalcToken operator_token = (*stack)[stack->size() - 2];
+        if ((operator_token.type() != BINARY_OPERATOR_TOKEN) ||
+            (operator_token.priority() < token.priority())) {
+          break;
+        }
+        CalcToken lhs_token = (*stack)[stack->size() - 3];
+        CalcToken rhs_token = (*stack)[stack->size() - 1];
+        stack->resize(stack->size() - 3);
+        auto node = create_binary_operator_node(
+            operator_token.binary_operator_type(),
+            lhs_token.node(), rhs_token.node());
+        if (!node) {
+          return false;
+        }
+        if (!push_token(CalcToken(node), stack)) {
+          return false;
+        }
+      }
+      stack->push_back(token);
+      break;
+    }
+  }
+  return true;
+}
+
+// 指定された名前のカラムと対応するノードを作成する．
+CalcNode *CalcImpl::create_column_node(const String &column_name) {
+  auto column = table_->get_column_by_name(column_name);
+  if (!column) {
+    return nullptr;
+  }
+  std::unique_ptr<CalcNode> node;
+  switch (column->data_type()) {
+    case BOOLEAN: {
+      node.reset(new ColumnNode<Boolean>(column));
+      break;
+    }
+    case INTEGER: {
+      node.reset(new ColumnNode<Int64>(column));
+      break;
+    }
+    case FLOAT: {
+      node.reset(new ColumnNode<Float>(column));
+      break;
+    }
+    case STRING: {
+      node.reset(new ColumnNode<String>(column));
+      break;
+    }
+  }
+  if (!node) {
+    return nullptr;
+  }
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された Boolean の定数と対応するノードを作成する．
+CalcNode *CalcImpl::create_boolean_node(Boolean value) {
+  std::unique_ptr<CalcNode> node(new ConstantNode<Boolean>(value));
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された Int64 の定数と対応するノードを作成する．
+CalcNode *CalcImpl::create_int64_node(Int64 value) {
+  std::unique_ptr<CalcNode> node(new ConstantNode<Int64>(value));
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された Float の定数と対応するノードを作成する．
+CalcNode *CalcImpl::create_float_node(Float value) {
+  std::unique_ptr<CalcNode> node(new ConstantNode<Float>(value));
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された String の定数と対応するノードを作成する．
+CalcNode *CalcImpl::create_string_node(const String &value) {
+  std::unique_ptr<CalcNode> node(new ConstantNode<String>(value));
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された単項演算子と対応するノードを作成する．
+CalcNode *CalcImpl::create_unary_operator_node(
+    UnaryOperatorType unary_operator_type, CalcNode *operand) {
+  std::unique_ptr<CalcNode> node;
+  switch (unary_operator_type) {
+    case LOGICAL_NOT_OPERATOR: {
+      node.reset(create_logical_not_operator_node(operand));
+      break;
+    }
+  }
+  if (!node) {
+    return nullptr;
+  }
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// LOGICAL_NOT と対応するノードを作成する．
+CalcNode *CalcImpl::create_logical_not_operator_node(CalcNode *operand) {
+  if (operand->data_type() != BOOLEAN) {
+    return nullptr;
+  }
+  switch (operand->type()) {
+    case CONSTANT_NODE: {
+      auto value = static_cast<ConstantNode<Boolean> *>(operand)->get(0, 0);
+      return new ConstantNode<Boolean>(value);
+    }
+    case COLUMN_NODE: {
+      return new LogicalNotNode<ColumnNode<Boolean>>(operand);
+    }
+    case OPERATOR_NODE: {
+      return new LogicalNotNode<OperatorNode<Boolean>>(operand);
+    }
+  }
+  return nullptr;
+}
+
+// 指定された二項演算子と対応するノードを作成する．
+CalcNode *CalcImpl::create_binary_operator_node(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  std::unique_ptr<CalcNode> node;
+  switch (binary_operator_type) {
+    case EQUAL_OPERATOR:
+    case NOT_EQUAL_OPERATOR:
+    case LESS_OPERATOR:
+    case LESS_EQUAL_OPERATOR:
+    case GREATER_OPERATOR:
+    case GREATER_EQUAL_OPERATOR: {
+      node.reset(create_comparer_node(binary_operator_type, lhs, rhs));
+      break;
+    }
+    case LOGICAL_AND_OPERATOR: {
+      node.reset(create_logical_and_node(lhs, rhs));
+      break;
+    }
+    case LOGICAL_OR_OPERATOR: {
+      node.reset(create_logical_or_node(lhs, rhs));
+      break;
+    }
+    case PLUS_OPERATOR:
+    case MINUS_OPERATOR:
+    case MULTIPLIES_OPERATOR:
+    case DIVIDES_OPERATOR:
+    case MODULUS_OPERATOR: {
+      node.reset(create_arithmetic_node(binary_operator_type, lhs, rhs));
+      break;
+    }
+  }
+  if (!node) {
+    return nullptr;
+  }
+  nodes_.push_back(std::move(node));
+  return nodes_.back().get();
+}
+
+// 指定された比較演算子と対応するノードを作成する．
+CalcNode *CalcImpl::create_comparer_node(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  // 同じ型同士と整数同士のみを許す．
+  switch (lhs->data_type()) {
+    case BOOLEAN: {
+      if (rhs->data_type() != BOOLEAN) {
+        return nullptr;
+      }
+      return create_comparer_node_2<Boolean, Boolean, Boolean>(
+          binary_operator_type, lhs, rhs);
+    }
+    case INTEGER: {
+      if (rhs->data_type() != INTEGER) {
+        return nullptr;
+      }
+      return create_comparer_node_2<Int64, Int64, Int64>(
+          binary_operator_type, lhs, rhs);
+    }
+    case FLOAT: {
+      if (rhs->data_type() != FLOAT) {
+        return nullptr;
+      }
+      return create_comparer_node_2<Float, Float, Float>(
+          binary_operator_type, lhs, rhs);
+    }
+    case STRING: {
+      if (rhs->data_type() != STRING) {
+        return nullptr;
+      }
+      return create_comparer_node_2<String, String, String>(
+          binary_operator_type, lhs, rhs);
+    }
+  }
+}
+
+// 指定された比較演算子と対応するノードを作成する．
+// T = 比較に用いる型， U = lhs のデータ型， V = rhs のデータ型．
+template <typename T, typename U, typename V>
+CalcNode *CalcImpl::create_comparer_node_2(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  switch (binary_operator_type) {
+    case EQUAL_OPERATOR: {
+      return create_comparer_node_3<EqualOperator<T>, U, V>(lhs, rhs);
+    }
+    case NOT_EQUAL_OPERATOR: {
+      return create_comparer_node_3<NotEqualOperator<T>, U, V>(lhs, rhs);
+    }
+    case LESS_OPERATOR: {
+      return create_comparer_node_3<LessOperator<T>, U, V>(lhs, rhs);
+    }
+    case LESS_EQUAL_OPERATOR: {
+      return create_comparer_node_3<LessEqualOperator<T>, U, V>(lhs, rhs);
+    }
+    case GREATER_OPERATOR: {
+      return create_comparer_node_3<GreaterOperator<T>, U, V>(lhs, rhs);
+    }
+    case GREATER_EQUAL_OPERATOR: {
+      return create_comparer_node_3<GreaterEqualOperator<T>, U, V>(lhs, rhs);
+    }
+    default: {
+      return nullptr;
+    }
+  }
+}
+
+// 指定された比較演算子と対応するノードを作成する．
+// T = 比較演算子， U = lhs のデータ型， V = rhs のデータ型．
+template <typename T, typename U, typename V>
+CalcNode *CalcImpl::create_comparer_node_3(
+    CalcNode *lhs, CalcNode *rhs) {
+  switch (lhs->type()) {
+    case CONSTANT_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          auto lhs_value = static_cast<ConstantNode<U> *>(lhs)->get(0, 0);
+          auto rhs_value = static_cast<ConstantNode<V> *>(rhs)->get(0, 0);
+          return new ConstantNode<Boolean>(T()(lhs_value, rhs_value));
+        }
+        case COLUMN_NODE: {
+          return new ComparerNode<T, ConstantNode<U>, ColumnNode<V>>(
+              lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new ComparerNode<T, ConstantNode<U>, OperatorNode<V>>(
+              lhs, rhs);
+        }
+      }
+      break;
+    }
+    case COLUMN_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new ComparerNode<T, ColumnNode<U>, ConstantNode<V>>(
+              lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new ComparerNode<T, ColumnNode<U>, ColumnNode<V>>(
+              lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new ComparerNode<T, ColumnNode<U>, OperatorNode<V>>(
+              lhs, rhs);
+        }
+      }
+      break;
+    }
+    case OPERATOR_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new ComparerNode<T, OperatorNode<U>, ConstantNode<V>>(
+              lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new ComparerNode<T, OperatorNode<U>, ColumnNode<V>>(
+              lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new ComparerNode<T, OperatorNode<U>, OperatorNode<V>>(
+              lhs, rhs);
+        }
+      }
+    }
+  }
+  return nullptr;
+}
+
+// LOGICAL_AND と対応するノードを作成する．
+CalcNode *CalcImpl::create_logical_and_node(CalcNode *lhs, CalcNode *rhs) {
+  if ((lhs->data_type() != BOOLEAN) || (rhs->data_type() != BOOLEAN)) {
+    return nullptr;
+  }
+  using ConstantNodeB = ConstantNode<Boolean>;
+  using ColumnNodeB = ColumnNode<Boolean>;
+  using OperatorNodeB = OperatorNode<Boolean>;
+  switch (lhs->type()) {
+    case CONSTANT_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          auto lhs_value = static_cast<ConstantNodeB *>(lhs)->get(0, 0);
+          auto rhs_value = static_cast<ConstantNodeB *>(rhs)->get(0, 0);
+          return new ConstantNode<Boolean>(lhs_value && rhs_value);
+        }
+        case COLUMN_NODE: {
+          return new LogicalAndNode<ConstantNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalAndNode<ConstantNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case COLUMN_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new LogicalAndNode<ColumnNodeB, ConstantNodeB>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new LogicalAndNode<ColumnNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalAndNode<ColumnNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case OPERATOR_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new LogicalAndNode<OperatorNodeB, ConstantNodeB>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new LogicalAndNode<OperatorNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalAndNode<OperatorNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+    }
+  }
+  return nullptr;
+}
+
+// LOGICAL_OR と対応するノードを作成する．
+CalcNode *CalcImpl::create_logical_or_node(CalcNode *lhs, CalcNode *rhs) {
+  if ((lhs->data_type() != BOOLEAN) || (rhs->data_type() != BOOLEAN)) {
+    return nullptr;
+  }
+  using ConstantNodeB = ConstantNode<Boolean>;
+  using ColumnNodeB = ColumnNode<Boolean>;
+  using OperatorNodeB = OperatorNode<Boolean>;
+  switch (lhs->type()) {
+    case CONSTANT_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          auto lhs_value = static_cast<ConstantNodeB *>(lhs)->get(0, 0);
+          auto rhs_value = static_cast<ConstantNodeB *>(rhs)->get(0, 0);
+          return new ConstantNode<Boolean>(lhs_value || rhs_value);
+        }
+        case COLUMN_NODE: {
+          return new LogicalOrNode<ConstantNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalOrNode<ConstantNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case COLUMN_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new LogicalOrNode<ColumnNodeB, ConstantNodeB>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new LogicalOrNode<ColumnNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalOrNode<ColumnNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case OPERATOR_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return new LogicalOrNode<OperatorNodeB, ConstantNodeB>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return new LogicalOrNode<OperatorNodeB, ColumnNodeB>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return new LogicalOrNode<OperatorNodeB, OperatorNodeB>(lhs, rhs);
+        }
+      }
+    }
+  }
+  return nullptr;
+}
+
+// 指定された算術演算子と対応するノードを作成する．
+CalcNode *CalcImpl::create_arithmetic_node(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  // 整数同士およびに浮動小数点数同士のみを許す．
+  switch (lhs->data_type()) {
+    case BOOLEAN: {
+      return create_arithmetic_node_2<Boolean>(binary_operator_type, lhs, rhs);
+    }
+    case INTEGER: {
+      return create_arithmetic_node_2<Int64>(binary_operator_type, lhs, rhs);
+    }
+    case FLOAT: {
+      return create_arithmetic_node_2<Float>(binary_operator_type, lhs, rhs);
+    }
+    case STRING: {
+      return create_arithmetic_node_2<String>(binary_operator_type, lhs, rhs);
+    }
+  }
+  return nullptr;
+}
+
+// 指定された算術演算子と対応するノードを作成する．
+// T: lhs のデータ型．
+template <typename T>
+CalcNode *CalcImpl::create_arithmetic_node_2(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  // 整数同士およびに浮動小数点数同士のみを許す．
+  switch (rhs->data_type()) {
+    case BOOLEAN: {
+      return create_arithmetic_node_3<T, Boolean>(
+          binary_operator_type, lhs, rhs);
+    }
+    case INTEGER: {
+      return create_arithmetic_node_3<T, Int64>(
+          binary_operator_type, lhs, rhs);
+    }
+    case FLOAT: {
+      return create_arithmetic_node_3<T, Float>(
+          binary_operator_type, lhs, rhs);
+    }
+    case STRING: {
+      return create_arithmetic_node_3<T, String>(
+          binary_operator_type, lhs, rhs);
+    }
+  }
+  return nullptr;
+}
+
+// 指定された算術演算子と対応するノードを作成する．
+// T: lhs のデータ型， U: rhs のデータ型．
+template <typename T, typename U>
+CalcNode *CalcImpl::create_arithmetic_node_3(
+    BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs) {
+  switch (binary_operator_type) {
+    case PLUS_OPERATOR: {
+      return create_arithmetic_node_4<PlusOperator<T, U>>(lhs, rhs);
+    }
+    case MINUS_OPERATOR: {
+      return create_arithmetic_node_4<MinusOperator<T, U>>(lhs, rhs);
+    }
+    case MULTIPLIES_OPERATOR: {
+      return create_arithmetic_node_4<MultipliesOperator<T, U>>(lhs, rhs);
+    }
+    case DIVIDES_OPERATOR: {
+      return create_arithmetic_node_4<DividesOperator<T, U>>(lhs, rhs);
+    }
+    case MODULUS_OPERATOR: {
+      return create_arithmetic_node_4<ModulusOperator<T, U>>(lhs, rhs);
+    }
+    default: {
+      return nullptr;
+    }
+  }
+}
+
+// 指定された算術演算子と対応するノードを作成する．
+// T: 算術演算子．
+template <typename T>
+CalcNode *CalcImpl::create_arithmetic_node_4(CalcNode *lhs, CalcNode *rhs) {
+  using Result = typename T::Result;
+  using Lhs = typename T::Lhs;
+  using Rhs = typename T::Rhs;
+  switch (lhs->type()) {
+    case CONSTANT_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          auto lhs_value = static_cast<ConstantNode<Lhs> *>(lhs)->get(0, 0);
+          auto rhs_value = static_cast<ConstantNode<Rhs> *>(rhs)->get(0, 0);
+          return ArithmeticNodeHelper<T>::template create(
+              lhs_value, rhs_value);
+        }
+        case COLUMN_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              ConstantNode<Lhs>, ColumnNode<Rhs>>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              ConstantNode<Lhs>, OperatorNode<Rhs>>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case COLUMN_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              ColumnNode<Lhs>, ConstantNode<Rhs>>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              ColumnNode<Lhs>, ColumnNode<Rhs>>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              ColumnNode<Lhs>, OperatorNode<Rhs>>(lhs, rhs);
+        }
+      }
+      break;
+    }
+    case OPERATOR_NODE: {
+      switch (rhs->type()) {
+        case CONSTANT_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              OperatorNode<Lhs>, ConstantNode<Rhs>>(lhs, rhs);
+        }
+        case COLUMN_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              OperatorNode<Lhs>, ColumnNode<Rhs>>(lhs, rhs);
+        }
+        case OPERATOR_NODE: {
+          return ArithmeticNodeHelper<T>::template create<
+              OperatorNode<Lhs>, OperatorNode<Rhs>>(lhs, rhs);
+        }
+      }
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/calc_impl.hpp (+233 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/calc_impl.hpp    2014-02-27 18:42:27 +0900 (e71e929)
@@ -0,0 +1,233 @@
+#ifndef GRNXX_CALC_IMPL_HPP
+#define GRNXX_CALC_IMPL_HPP
+
+#include "grnxx/calc.hpp"
+
+namespace grnxx {
+
+// 単項演算子の種類．
+enum UnaryOperatorType {
+  LOGICAL_NOT_OPERATOR
+};
+
+// 二項演算子の種類．
+enum BinaryOperatorType {
+  EQUAL_OPERATOR,
+  NOT_EQUAL_OPERATOR,
+  LESS_OPERATOR,
+  LESS_EQUAL_OPERATOR,
+  GREATER_OPERATOR,
+  GREATER_EQUAL_OPERATOR,
+  LOGICAL_AND_OPERATOR,
+  LOGICAL_OR_OPERATOR,
+  PLUS_OPERATOR,
+  MINUS_OPERATOR,
+  MULTIPLIES_OPERATOR,
+  DIVIDES_OPERATOR,
+  MODULUS_OPERATOR
+};
+
+// 演算器を構成するノードの種類．
+enum CalcNodeType {
+  CONSTANT_NODE,
+  COLUMN_NODE,
+  OPERATOR_NODE
+};
+
+// 演算器を構成するノード．
+class CalcNode {
+ public:
+  // 指定された種類のノードとして初期化する．
+  CalcNode(CalcNodeType type, DataType data_type);
+  // ノードを破棄する．
+  virtual ~CalcNode();
+
+  // ノードの種類を返す．
+  CalcNodeType type() const {
+    return type_;
+  }
+  // データ型を返す．
+  DataType data_type() const {
+    return data_type_;
+  }
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  virtual Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 与えられた行の一覧について演算をおこない，その結果を取得できる状態にする．
+  virtual void fill(const RowID *row_ids, Int64 num_row_ids);
+
+ protected:
+  CalcNodeType type_;
+  DataType data_type_;
+};
+
+// 括弧の種類．
+enum CalcBracketType {
+  LEFT_BRACKET,
+  RIGHT_BRACKET
+};
+
+// クエリを構成するトークンの種類．
+enum CalcTokenType {
+  BRACKET_TOKEN,
+  NODE_TOKEN,
+  UNARY_OPERATOR_TOKEN,
+  BINARY_OPERATOR_TOKEN
+};
+
+// クエリを構成するトークン．
+class CalcToken {
+ public:
+  // std::vector<CalcToken>::resize() を使えるようにする．
+  CalcToken()
+      : type_(NODE_TOKEN),
+        node_(nullptr),
+        priority_(0) {}
+  // 括弧に対応するトークンを作成する．
+  explicit CalcToken(CalcBracketType bracket_type)
+      : type_(BRACKET_TOKEN),
+        bracket_type_(bracket_type),
+        priority_(0) {}
+  // ノードに対応するトークンを作成する．
+  explicit CalcToken(CalcNode *node)
+      : type_(NODE_TOKEN),
+        node_(node),
+        priority_(0) {}
+  // 単項演算子に対応するトークンを作成する．
+  explicit CalcToken(UnaryOperatorType unary_operator_type)
+      : type_(UNARY_OPERATOR_TOKEN),
+        unary_operator_type_(unary_operator_type),
+        priority_(0) {}
+  // 二項演算子に対応するトークンを作成する．
+  explicit CalcToken(BinaryOperatorType binary_operator_type)
+      : type_(BINARY_OPERATOR_TOKEN),
+        binary_operator_type_(binary_operator_type),
+        priority_(get_binary_operator_priority(binary_operator_type)) {}
+
+  // トークンの種類を返す．
+  CalcTokenType type() const {
+    return type_;
+  }
+  // 対応する括弧の種類を返す．
+  CalcBracketType bracket_type() const {
+    return bracket_type_;
+  }
+  // 対応するノードを返す．
+  CalcNode *node() const {
+    return node_;
+  }
+  // 対応する単項演算子の種類を返す．
+  UnaryOperatorType unary_operator_type() const {
+    return unary_operator_type_;
+  }
+  // 対応する二項演算子の種類を返す．
+  BinaryOperatorType binary_operator_type() const {
+    return binary_operator_type_;
+  }
+  // 対応する二項演算子の優先度を返す．
+  int priority() const {
+    return priority_;
+  }
+
+ private:
+  CalcTokenType type_;
+  union {
+    CalcBracketType bracket_type_;
+    CalcNode *node_;
+    UnaryOperatorType unary_operator_type_;
+    BinaryOperatorType binary_operator_type_;
+  };
+  int priority_;
+
+  // 二項演算子の優先度を返す．
+  static int get_binary_operator_priority(BinaryOperatorType operator_type);
+};
+
+class CalcImpl : public Calc {
+ public:
+  CalcImpl();
+  ~CalcImpl();
+
+  // 指定された文字列に対応する演算器を作成する．
+  bool parse(const Table *table, const String &query);
+
+  // 行の一覧を受け取り，演算結果が真になる行のみを残して，残った行の数を返す．
+  Int64 filter(RowID *row_ids, Int64 num_row_ids);
+
+  // 演算が何も指定されていなければ true を返し，そうでなければ false を返す．
+  bool empty() const;
+
+ private:
+  const Table *table_;
+  std::vector<std::unique_ptr<CalcNode>> nodes_;
+
+  // クエリをトークンに分割する．
+  bool tokenize_query(const String &query, std::vector<CalcToken> *tokens);
+  // トークンをひとつずつ解釈する．
+  bool push_token(const CalcToken &token, std::vector<CalcToken> *stack);
+
+  // 指定された名前のカラムと対応するノードを作成する．
+  CalcNode *create_column_node(const String &column_name);
+
+  // 指定された Boolean の定数と対応するノードを作成する．
+  CalcNode *create_boolean_node(Boolean value);
+  // 指定された Int64 の定数と対応するノードを作成する．
+  CalcNode *create_int64_node(Int64 value);
+  // 指定された Float の定数と対応するノードを作成する．
+  CalcNode *create_float_node(Float value);
+  // 指定された String の定数と対応するノードを作成する．
+  CalcNode *create_string_node(const String &value);
+
+  // 指定された単項演算子と対応するノードを作成する．
+  CalcNode *create_unary_operator_node(UnaryOperatorType unary_operator_type,
+                                       CalcNode *operand);
+
+  // LOGICAL_NOT と対応するノードを作成する．
+  CalcNode *create_logical_not_operator_node(CalcNode *operand);
+
+  // 指定された二項演算子と対応するノードを作成する．
+  CalcNode *create_binary_operator_node(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+
+  // 指定された比較演算子と対応するノードを作成する．
+  CalcNode *create_comparer_node(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+  // 指定された比較演算子と対応するノードを作成する．
+  // T = 比較に用いる型， U = lhs のデータ型， V = rhs のデータ型．
+  template <typename T, typename U, typename V>
+  CalcNode *create_comparer_node_2(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+  // 指定された比較演算子と対応するノードを作成する．
+  // T = 比較演算子， U = lhs のデータ型， V = rhs のデータ型．
+  template <typename T, typename U, typename V>
+  CalcNode *create_comparer_node_3(CalcNode *lhs, CalcNode *rhs);
+
+  // LOGICAL_AND と対応するノードを作成する．
+  CalcNode *create_logical_and_node(CalcNode *lhs, CalcNode *rhs);
+
+  // LOGICAL_OR と対応するノードを作成する．
+  CalcNode *create_logical_or_node(CalcNode *lhs, CalcNode *rhs);
+
+  // 指定された算術演算子と対応するノードを作成する．
+  CalcNode *create_arithmetic_node(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+  // 指定された算術演算子と対応するノードを作成する．
+  // T: lhs のデータ型．
+  template <typename T>
+  CalcNode *create_arithmetic_node_2(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+  // 指定された算術演算子と対応するノードを作成する．
+  // T: lhs のデータ型， U: rhs のデータ型．
+  template <typename T, typename U>
+  CalcNode *create_arithmetic_node_3(
+      BinaryOperatorType binary_operator_type, CalcNode *lhs, CalcNode *rhs);
+  // 指定された算術演算子と対応するノードを作成する．
+  // T: 算術演算子．
+  template <typename T>
+  CalcNode *create_arithmetic_node_4(CalcNode *lhs, CalcNode *rhs);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_CALC_IMPL_HPP

  Added: lib/grnxx/column.cpp (+100 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/column.cpp    2014-02-27 18:42:27 +0900 (a64ff4d)
@@ -0,0 +1,100 @@
+#include "grnxx/column.hpp"
+
+#include "grnxx/column_impl.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+
+// カラムを初期化する．
+Column::Column(Table *table, ColumnID id, const String &name,
+               DataType data_type)
+    : table_(table),
+      id_(id),
+      name_(reinterpret_cast<const char *>(name.data()), name.size()),
+      data_type_(data_type) {}
+
+// カラムを破棄する．
+Column::~Column() {}
+
+// FIXME: 指定された ID の値を返す．
+Datum Column::generic_get(RowID row_id) const {
+  switch (data_type()) {
+    case BOOLEAN: {
+      return static_cast<const ColumnImpl<Boolean> *>(this)->get(row_id);
+    }
+    case INTEGER: {
+      return static_cast<const ColumnImpl<Int64> *>(this)->get(row_id);
+    }
+    case FLOAT: {
+      return static_cast<const ColumnImpl<Float> *>(this)->get(row_id);
+    }
+    case STRING: {
+      return static_cast<const ColumnImpl<String> *>(this)->get(row_id);
+    }
+  }
+  return false;
+}
+
+// FIXME: 指定された ID の値を設定する．
+void Column::generic_set(RowID row_id, const Datum &datum) {
+  switch (data_type()) {
+    case BOOLEAN: {
+      static_cast<ColumnImpl<Boolean> *>(this)->set(
+          row_id, static_cast<Boolean>(datum));
+      break;
+    }
+    case INTEGER: {
+      static_cast<ColumnImpl<Int64> *>(this)->set(
+          row_id, static_cast<Int64>(datum));
+      break;
+    }
+    case FLOAT: {
+      static_cast<ColumnImpl<Float> *>(this)->set(
+          row_id, static_cast<Float>(datum));
+      break;
+    }
+    case STRING: {
+      static_cast<ColumnImpl<String> *>(this)->set(
+          row_id, static_cast<std::string>(datum));
+      break;
+    }
+  }
+}
+
+// ストリームに書き出す．
+std::ostream &Column::write_to(std::ostream &stream) const {
+  stream << "{ id = " << id_
+         << ", name = \"" << name_ << '"'
+         << ", data_type = " << data_type_
+         << " }";
+  return stream;
+}
+
+std::ostream &operator<<(std::ostream &stream, const Column &column) {
+  return column.write_to(stream);
+}
+
+// 指定されたカラムを作成して返す．
+Column *ColumnHelper::create(Table *table,
+                             ColumnID column_id,
+                             const String &column_name,
+                             DataType data_type) {
+  switch (data_type) {
+    case BOOLEAN: {
+      return new ColumnImpl<Boolean>(table, column_id, column_name);
+    }
+    case INTEGER: {
+      return new ColumnImpl<Int64>(table, column_id, column_name);
+    }
+    case FLOAT: {
+      return new ColumnImpl<Float>(table, column_id, column_name);
+    }
+    case STRING: {
+      return new ColumnImpl<String>(table, column_id, column_name);
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/column.hpp (+68 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/column.hpp    2014-02-27 18:42:27 +0900 (66a0355)
@@ -0,0 +1,68 @@
+#ifndef GRNXX_COLUMN_HPP
+#define GRNXX_COLUMN_HPP
+
+#include "grnxx/datum.hpp"
+
+namespace grnxx {
+
+class Column {
+ public:
+  // カラムを初期化する．
+  Column(Table *table, ColumnID id, const String &name, DataType data_type);
+  // カラムを破棄する．
+  virtual ~Column();
+
+  // 所属するテーブルを返す．
+  Table *table() const {
+    return table_;
+  }
+  // カラム ID を返す．
+  ColumnID id() const {
+    return id_;
+  }
+  // カラム名を返す．
+  String name() const {
+    return name_;
+  }
+  // データ型を返す．
+  DataType data_type() const {
+    return data_type_;
+  }
+
+  // 指定された索引との関連付けをおこなう．
+  virtual bool register_index(Index *index) = 0;
+  // 指定された索引との関連を削除する．
+  virtual bool unregister_index(Index *index) = 0;
+
+  // 指定された行 ID が使えるようにサイズを変更する．
+  virtual void resize(RowID max_row_id) = 0;
+
+  // FIXME: 指定された ID の値を返す．
+  virtual Datum generic_get(RowID row_id) const;
+  // FIXME: 指定された ID の値を設定する．
+  virtual void generic_set(RowID row_id, const Datum &datum);
+
+  // ストリームに書き出す．
+  virtual std::ostream &write_to(std::ostream &stream) const;
+
+ protected:
+  Table *table_;
+  ColumnID id_;
+  std::string name_;
+  DataType data_type_;
+};
+
+std::ostream &operator<<(std::ostream &stream, const Column &column);
+
+class ColumnHelper {
+ public:
+  // 指定されたカラムを作成して返す．
+  static Column *create(Table *table,
+                        ColumnID column_id,
+                        const String &column_name,
+                        DataType data_type);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_COLUMN_HPP

  Added: lib/grnxx/column_impl.cpp (+120 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/column_impl.cpp    2014-02-27 18:42:27 +0900 (8e96392)
@@ -0,0 +1,120 @@
+#include "grnxx/column_impl.hpp"
+
+#include "grnxx/index.hpp"
+
+namespace grnxx {
+
+// カラムを初期化する．
+template <typename T>
+ColumnImpl<T>::ColumnImpl(Table *table, ColumnID id, const String &name)
+    : Column(table, id, name, TypeTraits<T>::data_type()),
+      data_(MIN_ROW_ID, 0),
+      indexes_() {}
+
+// カラムを破棄する．
+template <typename T>
+ColumnImpl<T>::~ColumnImpl() {}
+
+// 指定された索引との関連付けをおこなう．
+template <typename T>
+bool ColumnImpl<T>::register_index(Index *index) {
+  auto it = std::find(indexes_.begin(), indexes_.end(), index);
+  if (it != indexes_.end()) {
+    return false;
+  }
+  indexes_.push_back(index);
+  return true;
+}
+
+// 指定された索引との関連を削除する．
+template <typename T>
+bool ColumnImpl<T>::unregister_index(Index *index) {
+  auto it = std::find(indexes_.begin(), indexes_.end(), index);
+  if (it == indexes_.end()) {
+    return false;
+  }
+  indexes_.erase(it);
+  return true;
+}
+
+// 指定された行 ID が使えるようにサイズを変更する．
+template <typename T>
+void ColumnImpl<T>::resize(RowID max_row_id) {
+  data_.resize(max_row_id + 1, 0);
+}
+
+// 指定された ID の値を更新する．
+template <typename T>
+void ColumnImpl<T>::set(RowID row_id, T value) {
+  data_[row_id] = value;
+  for (auto index : indexes_) {
+    index->insert(row_id);
+  }
+}
+
+template class ColumnImpl<Boolean>;
+template class ColumnImpl<Int64>;
+template class ColumnImpl<Float>;
+
+// カラムを初期化する．
+ColumnImpl<String>::ColumnImpl(Table *table, ColumnID id, const String &name)
+    : Column(table, id, name, TypeTraits<String>::data_type()),
+      headers_(MIN_ROW_ID, 0),
+      bodies_(),
+      indexes_() {}
+
+// カラムを破棄する．
+ColumnImpl<String>::~ColumnImpl() {}
+
+// 指定された索引との関連付けをおこなう．
+bool ColumnImpl<String>::register_index(Index *index) {
+  auto it = std::find(indexes_.begin(), indexes_.end(), index);
+  if (it != indexes_.end()) {
+    return false;
+  }
+  indexes_.push_back(index);
+  return true;
+}
+
+// 指定された索引との関連を削除する．
+bool ColumnImpl<String>::unregister_index(Index *index) {
+  auto it = std::find(indexes_.begin(), indexes_.end(), index);
+  if (it == indexes_.end()) {
+    return false;
+  }
+  indexes_.erase(it);
+  return true;
+}
+
+// 指定された行 ID が使えるようにサイズを変更する．
+void ColumnImpl<String>::resize(RowID max_row_id) {
+  headers_.resize(max_row_id + 1, 0);
+}
+
+// 指定された ID の値を更新する．
+void ColumnImpl<String>::set(RowID row_id, const String &value) {
+  if (value.empty()) {
+    headers_[row_id] = 0;
+    return;
+  }
+  Int64 offset = bodies_.size();
+  if (value.size() < 0xFFFF) {
+    bodies_.resize(offset + value.size());
+    std::memcpy(&bodies_[offset], value.data(), value.size());
+    headers_[row_id] = (offset << 16) | value.size();
+  } else {
+    // 長い文字列については offset の位置にサイズを保存する．
+    if ((offset % sizeof(Int64)) != 0) {
+      offset += sizeof(Int64) - (offset % sizeof(Int64));
+    }
+    bodies_.resize(offset + sizeof(Int64) + value.size());
+    *reinterpret_cast<Int64 *>(&bodies_[offset]) = value.size();
+    std::memcpy(&bodies_[offset + sizeof(Int64)], value.data(), value.size());
+    headers_[row_id] = (offset << 16) | 0xFFFF;
+  }
+  for (auto index : indexes_) {
+    index->insert(row_id);
+  }
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/column_impl.hpp (+86 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/column_impl.hpp    2014-02-27 18:42:27 +0900 (89ed32e)
@@ -0,0 +1,86 @@
+#ifndef GRNXX_COLUMN_IMPL_HPP
+#define GRNXX_COLUMN_IMPL_HPP
+
+#include "grnxx/column.hpp"
+
+namespace grnxx {
+
+template <typename T>
+class ColumnImpl : public Column {
+ public:
+  // カラムを初期化する．
+  ColumnImpl(Table *table, ColumnID id, const String &name);
+  // カラムを破棄する．
+  ~ColumnImpl();
+
+  // コピーと代入を禁止する．
+  ColumnImpl(const ColumnImpl &) = delete;
+  ColumnImpl &operator=(const ColumnImpl &) = delete;
+
+  // 指定された索引との関連付けをおこなう．
+  bool register_index(Index *index);
+  // 指定された索引との関連を削除する．
+  bool unregister_index(Index *index);
+
+  // 指定された行 ID が使えるようにサイズを変更する．
+  void resize(RowID max_row_id);
+
+  // 指定された ID の値を返す．
+  T get(RowID row_id) const {
+    return data_[row_id];
+  }
+  // 指定された ID の値を更新する．
+  void set(RowID row_id, T value);
+
+ private:
+  std::vector<T> data_;
+  std::vector<Index *> indexes_;
+};
+
+template <>
+class ColumnImpl<String> : public Column {
+ public:
+  // カラムを初期化する．
+  ColumnImpl(Table *table, ColumnID id, const String &name);
+  // カラムを破棄する．
+  ~ColumnImpl();
+
+  // コピーと代入を禁止する．
+  ColumnImpl(const ColumnImpl &) = delete;
+  ColumnImpl &operator=(const ColumnImpl &) = delete;
+
+  // 指定された索引との関連付けをおこなう．
+  bool register_index(Index *index);
+  // 指定された索引との関連を削除する．
+  bool unregister_index(Index *index);
+
+  // 指定された行 ID が使えるようにサイズを変更する．
+  void resize(RowID max_row_id);
+
+  // 指定された ID の値を返す．
+  String get(RowID row_id) const {
+    Int64 size = headers_[row_id] & 0xFFFF;
+    if (size == 0) {
+      return String("", 0);
+    }
+    Int64 offset = headers_[row_id] >> 16;
+    if (size < 0xFFFF) {
+      return String(&bodies_[offset], size);
+    } else {
+      // 長い文字列については offset の位置にサイズが保存してある．
+      size = *reinterpret_cast<const Int64 *>(&bodies_[offset]);
+      return String(&bodies_[offset + sizeof(Int64)], size);
+    }
+  }
+  // 指定された ID の値を更新する．
+  void set(RowID row_id, const String &value);
+
+ private:
+  std::vector<UInt64> headers_;
+  std::vector<char> bodies_;
+  std::vector<Index *> indexes_;
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_COLUMN_IMPL_HPP

  Added: lib/grnxx/database.cpp (+90 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/database.cpp    2014-02-27 18:42:27 +0900 (2461032)
@@ -0,0 +1,90 @@
+#include "grnxx/database.hpp"
+
+#include "grnxx/table.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+
+// データベースを初期化する．
+Database::Database()
+    : tables_(MIN_TABLE_ID),
+      tables_map_() {}
+
+// データベースを破棄する．
+Database::~Database() {}
+
+// 指定された名前のテーブルを作成して返す．
+// 失敗すると nullptr を返す．
+Table *Database::create_table(const String &table_name) {
+  auto it = tables_map_.find(table_name);
+  if (it != tables_map_.end()) {
+    return nullptr;
+  }
+  TableID table_id = min_table_id();
+  for ( ; table_id <= max_table_id(); ++table_id) {
+    if (!tables_[table_id]) {
+      break;
+    }
+  }
+  if (table_id > max_table_id()) {
+    tables_.resize(table_id + 1);
+  }
+  std::unique_ptr<Table> new_table(new Table(this, table_id, table_name));
+  tables_map_.insert(it, std::make_pair(new_table->name(), table_id));
+  tables_[table_id] = std::move(new_table);
+  return tables_[table_id].get();
+}
+
+// 指定された名前のテーブルを破棄する．
+// 成功すれば true を返し，失敗すれば false を返す．
+bool Database::drop_table(const String &table_name) {
+  auto it = tables_map_.find(table_name);
+  if (it == tables_map_.end()) {
+    return false;
+  }
+  tables_[it->second].reset();
+  tables_map_.erase(it);
+  return true;
+}
+
+// 指定された名前のテーブルを返す．
+// なければ nullptr を返す．
+Table *Database::get_table_by_name(const String &table_name) const {
+  auto it = tables_map_.find(table_name);
+  if (it == tables_map_.end()) {
+    return nullptr;
+  }
+  return tables_[it->second].get();
+}
+
+// テーブルの一覧を tables の末尾に追加し，テーブルの数を返す．
+Int64 Database::get_tables(std::vector<Table *> *tables) const {
+  std::size_t old_size = tables->size();
+  for (auto &table : tables_) {
+    if (table) {
+      tables->push_back(table.get());
+    }
+  }
+  return tables->size() - old_size;
+}
+
+// ストリームに書き出す．
+std::ostream &Database::write_to(std::ostream &stream) const {
+  std::vector<Table *> tables;
+  if (get_tables(&tables) == 0) {
+    return stream << "{}";
+  }
+  stream << "{ " << *tables[0];
+  for (std::size_t i = 1; i < tables.size(); ++i) {
+    stream << ", " << *tables[i];
+  }
+  stream << " }";
+  return stream;
+}
+
+std::ostream &operator<<(std::ostream &stream, const Database &database) {
+  return database.write_to(stream);
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/database.hpp (+62 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/database.hpp    2014-02-27 18:42:27 +0900 (3962c1a)
@@ -0,0 +1,62 @@
+#ifndef GRNXX_DATABASE_HPP
+#define GRNXX_DATABASE_HPP
+
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+class Database {
+ public:
+  // データベースを初期化する．
+  Database();
+  // データベースを破棄する．
+  ~Database();
+
+  // コピーと代入を禁止する．
+  Database(const Database &) = delete;
+  Database &operator=(const Database &) = delete;
+
+  // 指定された名前のテーブルを作成して返す．
+  // 失敗すると nullptr を返す．
+  Table *create_table(const String &table_name);
+  // 指定された名前のテーブルを破棄する．
+  // 成功すれば true を返し，失敗すれば false を返す．
+  bool drop_table(const String &table_name);
+
+  // テーブル ID の最小値を返す．
+  TableID min_table_id() const {
+    return MIN_TABLE_ID;
+  }
+  // テーブル ID の最大値を返す．
+  TableID max_table_id() const {
+    return tables_.size() - 1;
+  }
+
+  // 指定された ID のテーブルを返す．
+  // なければ nullptr を返す．
+  Table *get_table_by_id(TableID table_id) const {
+    if (table_id > max_table_id()) {
+      return nullptr;
+    }
+    return tables_[table_id].get();
+  }
+  // 指定された名前のテーブルを返す．
+  // なければ nullptr を返す．
+  Table *get_table_by_name(const String &table_name) const;
+
+  // テーブルの一覧を tables の末尾に追加し，テーブルの数を返す．
+  Int64 get_tables(std::vector<Table *> *tables) const;
+
+  // ストリームに書き出す．
+  std::ostream &write_to(std::ostream &stream) const;
+
+ private:
+  std::vector<std::unique_ptr<Table>> tables_;
+  std::map<String, TableID> tables_map_;
+};
+
+std::ostream &operator<<(std::ostream &stream, const Database &database);
+
+}  // namespace grnxx
+
+#endif  // GRNXX_DATABASE_HPP

  Added: lib/grnxx/datum.cpp (+37 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/datum.cpp    2014-02-27 18:42:27 +0900 (cb09357)
@@ -0,0 +1,37 @@
+#include "grnxx/datum.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+
+std::ostream &Datum::write_to(std::ostream &stream) const {
+  switch (type_) {
+    case BOOLEAN: {
+      return stream << (boolean_ ? "TRUE" : "FALSE");
+    }
+    case INTEGER: {
+      return stream << integer_;
+    }
+    case FLOAT: {
+      if (std::isnan(float_)) {
+        return stream << "NAN";
+      } else if (std::isinf(float_)) {
+        return stream << (std::signbit(float_) ? "-INF" : "INF");
+      } else {
+        return stream << float_;
+      }
+    }
+    case STRING: {
+      return stream << '"' << string_ << '"';
+    }
+    default: {
+      return stream << "N/A";
+    }
+  }
+}
+
+std::ostream &operator<<(std::ostream &stream, const Datum &datum) {
+  return datum.write_to(stream);
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/datum.hpp (+244 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/datum.hpp    2014-02-27 18:42:27 +0900 (a68ff0a)
@@ -0,0 +1,244 @@
+#ifndef GRNXX_DATUM_HPP
+#define GRNXX_DATUM_HPP
+
+#include "grnxx/string.hpp"
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+// 汎用データ型．
+class Datum {
+ public:
+  // FALSE として初期化する．
+  Datum() : type_(BOOLEAN), boolean_(false) {}
+  // 真偽値として初期化する．
+  Datum(Boolean value) : type_(BOOLEAN), boolean_(value) {}
+  // 整数として初期化する．
+  Datum(Int64 value) : type_(INTEGER), integer_(value) {}
+  // 浮動小数点数として初期化する．
+  Datum(Float value) : type_(FLOAT), float_(value) {}
+  // バイト列・文字列として初期化する．
+  Datum(const char *value) : type_(STRING), string_(value) {}
+  Datum(const String &value)
+      : type_(STRING),
+        string_(reinterpret_cast<const char *>(value.data()), value.size()) {}
+  Datum(const std::string &value) : type_(STRING), string_(value) {}
+  // 破棄する．
+  ~Datum() {
+    if (type_ == STRING) {
+      string_.~basic_string();
+    }
+  }
+
+  // string_ はコピーするとコストが大きくなるので注意．
+  Datum(const Datum &datum) : type_(BOOLEAN), boolean_(false) {
+    switch (datum.type_) {
+      case BOOLEAN: {
+        boolean_ = datum.boolean_;
+        type_ = datum.type_;
+        break;
+      }
+      case INTEGER: {
+        integer_ = datum.integer_;
+        type_ = datum.type_;
+        break;
+      }
+      case FLOAT: {
+        float_ = datum.float_;
+        type_ = datum.type_;
+        break;
+      }
+      case STRING: {
+        new (&string_) std::string(datum.string_);
+        type_ = datum.type_;
+        break;
+      }
+      default: {
+        break;
+      }
+    }
+  }
+  // string_ はムーブの方がコストを抑えられるはず．
+  Datum(Datum &&datum) : type_(BOOLEAN), boolean_(false) {
+    switch (datum.type_) {
+      case BOOLEAN: {
+        boolean_ = std::move(datum.boolean_);
+        type_ = std::move(datum.type_);
+        break;
+      }
+      case INTEGER: {
+        integer_ = std::move(datum.integer_);
+        type_ = std::move(datum.type_);
+        break;
+      }
+      case FLOAT: {
+        float_ = std::move(datum.float_);
+        type_ = std::move(datum.type_);
+        break;
+      }
+      case STRING: {
+        new (&string_) std::string(std::move(datum.string_));
+        type_ = std::move(datum.type_);
+        break;
+      }
+      default: {
+        break;
+      }
+    }
+  }
+
+  // データ型を返す．
+  DataType type() const {
+    return type_;
+  }
+
+  // データを代入する．
+  Datum &operator=(Boolean rhs) {
+    if (type_ == STRING) {
+      string_.~basic_string();
+    }
+    type_ = BOOLEAN;
+    boolean_ = rhs;
+    return *this;
+  }
+  Datum &operator=(Int64 rhs) {
+    if (type_ == STRING) {
+      string_.~basic_string();
+    }
+    type_ = INTEGER;
+    integer_ = static_cast<Int64>(rhs);
+    return *this;
+  }
+  Datum &operator=(Float rhs) {
+    if (type_ == STRING) {
+      string_.~basic_string();
+    }
+    type_ = FLOAT;
+    float_ = static_cast<Float>(rhs);
+    return *this;
+  }
+  Datum &operator=(const char *rhs) {
+    if (type_ != STRING) {
+      new (&string_) std::string(rhs);
+      type_ = STRING;
+    } else {
+      string_ = rhs;
+    }
+    return *this;
+  }
+  Datum &operator=(const String &rhs) {
+    if (type_ != STRING) {
+      new (&string_) std::string(reinterpret_cast<const char *>(rhs.data()),
+                                 rhs.size());
+      type_ = STRING;
+    } else {
+      string_.assign(reinterpret_cast<const char *>(rhs.data()), rhs.size());
+    }
+    return *this;
+  }
+  Datum &operator=(const std::string &rhs) {
+    if (type_ != STRING) {
+      new (&string_) std::string(rhs);
+      type_ = STRING;
+    } else {
+      string_ = rhs;
+    }
+    return *this;
+  }
+
+  // 型変換．
+  explicit operator Boolean() const {
+    switch (type_) {
+      case BOOLEAN: {
+        return boolean_;
+      }
+      case INTEGER: {
+        return static_cast<Boolean>(integer_);
+      }
+      case FLOAT: {
+        return static_cast<Boolean>(float_);
+      }
+      case STRING: {
+        return string_ == "TRUE";
+      }
+      default: {
+        return false;
+      }
+    }
+  }
+  explicit operator Int64() const {
+    switch (type_) {
+      case BOOLEAN: {
+        return static_cast<Int64>(boolean_);
+      }
+      case INTEGER: {
+        return integer_;
+      }
+      case FLOAT: {
+        return static_cast<Int64>(float_);
+      }
+      case STRING: {
+        return static_cast<Int64>(std::stol(string_));
+      }
+      default: {
+        return 0;
+      }
+    }
+  }
+  explicit operator Float() const {
+    switch (type_) {
+      case BOOLEAN: {
+        return static_cast<Float>(boolean_);
+      }
+      case INTEGER: {
+        return static_cast<Float>(integer_);
+      }
+      case FLOAT: {
+        return float_;
+      }
+      case STRING: {
+        return static_cast<Float>(std::stod(string_));
+      }
+      default: {
+        return 0.0;
+      }
+    }
+  }
+  explicit operator std::string() const {
+    switch (type_) {
+      case BOOLEAN: {
+        return boolean_ ? "TRUE" : "FALSE";
+      }
+      case INTEGER: {
+        return std::to_string(integer_);
+      }
+      case FLOAT: {
+        return std::to_string(float_);
+      }
+      case STRING: {
+        return string_;
+      }
+      default: {
+        return "";
+      }
+    }
+  }
+
+  // ストリームに書き出す．
+  std::ostream &write_to(std::ostream &stream) const;
+
+ private:
+  DataType type_;
+  union {
+    Boolean boolean_;
+    Int64 integer_;
+    Float float_;
+    std::string string_;
+  };
+};
+
+std::ostream &operator<<(std::ostream &stream, const Datum &datum);
+
+}  // namespace grnxx
+
+#endif  // GRNXX_DATUM_HPP

  Added: lib/grnxx/index.cpp (+577 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/index.cpp    2014-02-27 18:42:27 +0900 (32b2ff0)
@@ -0,0 +1,577 @@
+#include "grnxx/index.hpp"
+
+#include "grnxx/column_impl.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+namespace {
+
+template <typename T>
+class TreeMapIndex : public Index {
+ public:
+  using RowIDSet = std::set<RowID>;
+  using Map = std::map<T, RowIDSet>;
+
+  // 索引を初期化する．
+  TreeMapIndex(IndexID index_id,
+               const String &index_name,
+               Column *column);
+
+  // 指定されたデータを登録する．
+  void insert(RowID row_id);
+  // 指定されたデータを削除する．
+  void remove(RowID row_id);
+
+  // 行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_all(bool reverse_order);
+  // 指定された値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_equal(const Datum &datum, bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_less(const Datum &datum, bool less_equal,
+                         bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_greater(const Datum &datum, bool greater_equal,
+                            bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_between(const Datum &begin, const Datum &end,
+                            bool greater_equal, bool less_equal,
+                            bool reverse_order);
+
+  class Cursor : public RowIDCursor {
+   public:
+    Cursor(typename Map::iterator begin, typename Map::iterator end);
+
+    // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+    // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+    Int64 get_next(Int64 limit, std::vector<RowID> *row_ids);
+
+   private:
+    typename Map::iterator map_it_;
+    typename Map::iterator map_end_;
+    typename RowIDSet::iterator set_it_;
+    typename RowIDSet::iterator set_end_;
+  };
+
+  class ReverseCursor : public RowIDCursor {
+   public:
+    ReverseCursor(typename Map::iterator begin, typename Map::iterator end);
+
+    // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+    // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+    Int64 get_next(Int64 limit, std::vector<RowID> *row_ids);
+
+   private:
+    typename Map::reverse_iterator map_it_;
+    typename Map::reverse_iterator map_end_;
+    typename RowIDSet::iterator set_it_;
+    typename RowIDSet::iterator set_end_;
+  };
+
+  RowIDCursor *create_cursor(typename Map::iterator begin,
+                             typename Map::iterator end, bool reverse_order);
+
+ private:
+  Map map_;
+  ColumnImpl<T> *column_;
+};
+
+// 索引を初期化する．
+template <typename T>
+TreeMapIndex<T>::TreeMapIndex(IndexID index_id,
+                              const String &index_name,
+                              Column *column)
+    : Index(index_id, index_name, column, TREE_MAP),
+      map_(),
+      column_(static_cast<ColumnImpl<T> *>(column)) {}
+
+// 指定されたデータを登録する．
+template <typename T>
+void TreeMapIndex<T>::insert(RowID row_id) {
+  map_[column_->get(row_id)].insert(row_id);
+}
+
+// 指定されたデータを削除する．
+template <typename T>
+void TreeMapIndex<T>::remove(RowID row_id) {
+  auto map_it = map_.find(column_->get(row_id));
+  if (map_it == map_.end()) {
+    return;
+  }
+  auto &set = map_it->second;
+  auto set_it = set.find(row_id);
+  if (set_it == set.end()) {
+    return;
+  }
+  set.erase(set_it);
+  if (set.empty()) {
+    map_.erase(map_it);
+  }
+}
+
+// 行の一覧を取得できるカーソルを作成して返す．
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::find_all(bool reverse_order) {
+  return create_cursor(map_.begin(), map_.end(), reverse_order);
+}
+
+// 指定された値が格納された行の一覧を取得できるカーソルを作成して返す．
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::find_equal(const Datum &datum,
+                                         bool reverse_order) {
+  auto range = map_.equal_range(static_cast<T>(datum));
+  return create_cursor(range.first, range.second, reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::find_less(const Datum &datum,
+                                        bool less_equal,
+                                        bool reverse_order) {
+  typename Map::iterator map_end;
+  if (less_equal) {
+    map_end = map_.upper_bound(static_cast<T>(datum));
+  } else {
+    map_end = map_.lower_bound(static_cast<T>(datum));
+  }
+  return create_cursor(map_.begin(), map_end, reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::find_greater(const Datum &datum,
+                                           bool greater_equal,
+                                           bool reverse_order) {
+  typename Map::iterator map_begin;
+  if (greater_equal) {
+    map_begin = map_.lower_bound(static_cast<T>(datum));
+  } else {
+    map_begin = map_.upper_bound(static_cast<T>(datum));
+  }
+  return create_cursor(map_begin, map_.end(), reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::find_between(const Datum &begin,
+                                           const Datum &end,
+                                           bool greater_equal,
+                                           bool less_equal,
+                                           bool reverse_order) {
+  T begin_key = static_cast<T>(begin);
+  T end_key = static_cast<T>(end);
+  typename Map::iterator map_begin;
+  if (greater_equal) {
+    map_begin = map_.lower_bound(begin_key);
+  } else {
+    map_begin = map_.upper_bound(begin_key);
+  }
+  typename Map::iterator map_end;
+  if (less_equal) {
+    map_end = map_.upper_bound(end_key);
+  } else {
+    map_end = map_.lower_bound(end_key);
+  }
+  return create_cursor(map_begin, map_end, reverse_order);
+}
+
+template <typename T>
+TreeMapIndex<T>::Cursor::Cursor(typename Map::iterator begin,
+                                typename Map::iterator end)
+    : RowIDCursor(),
+      map_it_(begin),
+      map_end_(end),
+      set_it_(),
+      set_end_() {
+  if (begin != end) {
+    set_it_ = begin->second.begin();
+    set_end_ = begin->second.end();
+  }
+}
+
+// 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+// 取得できる行 ID が尽きたときは limit より小さい値を返す．
+template <typename T>
+Int64 TreeMapIndex<T>::Cursor::get_next(Int64 limit,
+                                        std::vector<RowID> *row_ids) {
+  if (map_it_ == map_end_) {
+    return 0;
+  }
+  Int64 count = 0;
+  while (count < limit) {
+    if (set_it_ == set_end_) {
+      ++map_it_;
+      if (map_it_ == map_end_) {
+        return count;
+      }
+      set_it_ = map_it_->second.begin();
+      set_end_ = map_it_->second.end();
+    }
+    if (row_ids) {
+      row_ids->push_back(*set_it_);
+    }
+    ++set_it_;
+    ++count;
+  }
+  return count;
+}
+
+template <typename T>
+TreeMapIndex<T>::ReverseCursor::ReverseCursor(typename Map::iterator begin,
+                                              typename Map::iterator end)
+    : RowIDCursor(),
+      map_it_(end),
+      map_end_(begin),
+      set_it_(),
+      set_end_() {
+  if (map_it_ != map_end_) {
+    set_it_ = map_it_->second.begin();
+    set_end_ = map_it_->second.end();
+  }
+}
+
+// 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+// 取得できる行 ID が尽きたときは limit より小さい値を返す．
+template <typename T>
+Int64 TreeMapIndex<T>::ReverseCursor::get_next(Int64 limit,
+                                               std::vector<RowID> *row_ids) {
+  if (map_it_ == map_end_) {
+    return 0;
+  }
+  Int64 count = 0;
+  while (count < limit) {
+    if (set_it_ == set_end_) {
+      ++map_it_;
+      if (map_it_ == map_end_) {
+        return count;
+      }
+      set_it_ = map_it_->second.begin();
+      set_end_ = map_it_->second.end();
+    }
+    if (row_ids) {
+      row_ids->push_back(*set_it_);
+    }
+    ++set_it_;
+    ++count;
+  }
+  return count;
+}
+
+template <typename T>
+RowIDCursor *TreeMapIndex<T>::create_cursor(typename Map::iterator begin,
+                                            typename Map::iterator end,
+                                            bool reverse_order) {
+  if (reverse_order) {
+    return new ReverseCursor(begin, end);
+  } else {
+    return new Cursor(begin, end);
+  }
+}
+
+// String では更新時に本体のアドレスが移動してしまい，
+// std::map では対応できないので， std::string を使っている．
+template <>
+class TreeMapIndex<String> : public Index {
+ public:
+  using RowIDSet = std::set<RowID>;
+  using Map = std::map<std::string, RowIDSet>;
+
+  // 索引を初期化する．
+  TreeMapIndex(IndexID index_id,
+               const String &index_name,
+               Column *column);
+
+  // 指定されたデータを登録する．
+  void insert(RowID row_id);
+  // 指定されたデータを削除する．
+  void remove(RowID row_id);
+
+
+  // 行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_all(bool reverse_order);
+  // 指定された値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_equal(const Datum &datum, bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_less(const Datum &datum, bool less_equal,
+                         bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_greater(const Datum &datum, bool greater_equal,
+                            bool reverse_order);
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  RowIDCursor *find_between(const Datum &begin, const Datum &end,
+                            bool greater_equal, bool less_equal,
+                            bool reverse_order);
+
+  class Cursor : public RowIDCursor {
+   public:
+    Cursor(Map::iterator begin, Map::iterator end);
+
+    // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+    // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+    Int64 get_next(Int64 limit, std::vector<RowID> *row_ids);
+
+   private:
+    Map::iterator map_it_;
+    Map::iterator map_end_;
+    RowIDSet::iterator set_it_;
+    RowIDSet::iterator set_end_;
+  };
+
+  class ReverseCursor : public RowIDCursor {
+   public:
+    ReverseCursor(Map::iterator begin, Map::iterator end);
+
+    // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+    // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+    Int64 get_next(Int64 limit, std::vector<RowID> *row_ids);
+
+   private:
+    Map::reverse_iterator map_it_;
+    Map::reverse_iterator map_end_;
+    RowIDSet::iterator set_it_;
+    RowIDSet::iterator set_end_;
+  };
+
+  RowIDCursor *create_cursor(typename Map::iterator begin,
+                             typename Map::iterator end, bool reverse_order);
+
+ private:
+  Map map_;
+  ColumnImpl<String> *column_;
+};
+
+// 索引を初期化する．
+TreeMapIndex<String>::TreeMapIndex(IndexID index_id,
+                                   const String &index_name,
+                                   Column *column)
+    : Index(index_id, index_name, column, TREE_MAP),
+      map_(),
+      column_(static_cast<ColumnImpl<String> *>(column)) {}
+
+// 指定されたデータを登録する．
+void TreeMapIndex<String>::insert(RowID row_id) {
+  String datum = column_->get(row_id);
+  std::string key(reinterpret_cast<const char *>(datum.data()), datum.size());
+  map_[key].insert(row_id);
+}
+
+// 指定されたデータを削除する．
+void TreeMapIndex<String>::remove(RowID row_id) {
+  String datum = column_->get(row_id);
+  std::string key(reinterpret_cast<const char *>(datum.data()), datum.size());
+  auto map_it = map_.find(key);
+  if (map_it == map_.end()) {
+    return;
+  }
+  auto &set = map_it->second;
+  auto set_it = set.find(row_id);
+  if (set_it == set.end()) {
+    return;
+  }
+  set.erase(set_it);
+  if (set.empty()) {
+    map_.erase(map_it);
+  }
+}
+
+// 行の一覧を取得できるカーソルを作成して返す．
+RowIDCursor *TreeMapIndex<String>::find_all(bool reverse_order) {
+  return create_cursor(map_.begin(), map_.end(), reverse_order);
+}
+
+// 指定された値が格納された行の一覧を取得できるカーソルを作成して返す．
+RowIDCursor *TreeMapIndex<String>::find_equal(const Datum &datum,
+                                              bool reverse_order) {
+  auto range = map_.equal_range(static_cast<std::string>(datum));
+  return create_cursor(range.first, range.second, reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+RowIDCursor *TreeMapIndex<String>::find_less(const Datum &datum,
+                                             bool less_equal,
+                                             bool reverse_order) {
+  typename Map::iterator map_end;
+  if (less_equal) {
+    map_end = map_.upper_bound(static_cast<std::string>(datum));
+  } else {
+    map_end = map_.lower_bound(static_cast<std::string>(datum));
+  }
+  return create_cursor(map_.begin(), map_end, reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+RowIDCursor *TreeMapIndex<String>::find_greater(const Datum &datum,
+                                                bool greater_equal,
+                                                bool reverse_order) {
+  typename Map::iterator map_begin;
+  if (greater_equal) {
+    map_begin = map_.lower_bound(static_cast<std::string>(datum));
+  } else {
+    map_begin = map_.upper_bound(static_cast<std::string>(datum));
+  }
+  return create_cursor(map_begin, map_.end(), reverse_order);
+}
+
+// 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+RowIDCursor *TreeMapIndex<String>::find_between(const Datum &begin,
+                                                const Datum &end,
+                                                bool greater_equal,
+                                                bool less_equal,
+                                                bool reverse_order) {
+  std::string begin_key = static_cast<std::string>(begin);
+  std::string end_key = static_cast<std::string>(end);
+  Map::iterator map_begin;
+  if (greater_equal) {
+    map_begin = map_.lower_bound(begin_key);
+  } else {
+    map_begin = map_.upper_bound(begin_key);
+  }
+  Map::iterator map_end;
+  if (less_equal) {
+    map_end = map_.upper_bound(end_key);
+  } else {
+    map_end = map_.lower_bound(end_key);
+  }
+  return create_cursor(map_begin, map_end, reverse_order);
+}
+
+TreeMapIndex<String>::Cursor::Cursor(Map::iterator begin, Map::iterator end)
+    : RowIDCursor(),
+      map_it_(begin),
+      map_end_(end),
+      set_it_(),
+      set_end_() {
+  if (begin != end) {
+    set_it_ = begin->second.begin();
+    set_end_ = begin->second.end();
+  }
+}
+
+// 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+// 取得できる行 ID が尽きたときは limit より小さい値を返す．
+Int64 TreeMapIndex<String>::Cursor::get_next(Int64 limit,
+                                             std::vector<RowID> *row_ids) {
+  if (map_it_ == map_end_) {
+    return 0;
+  }
+  Int64 count = 0;
+  while (count < limit) {
+    if (set_it_ == set_end_) {
+      ++map_it_;
+      if (map_it_ == map_end_) {
+        return count;
+      }
+      set_it_ = map_it_->second.begin();
+      set_end_ = map_it_->second.end();
+    }
+    if (row_ids) {
+      row_ids->push_back(*set_it_);
+    }
+    ++set_it_;
+    ++count;
+  }
+  return count;
+}
+
+TreeMapIndex<String>::ReverseCursor::ReverseCursor(Map::iterator begin,
+                                                   Map::iterator end)
+    : RowIDCursor(),
+      map_it_(end),
+      map_end_(begin),
+      set_it_(),
+      set_end_() {
+  if (map_it_ != map_end_) {
+    set_it_ = map_it_->second.begin();
+    set_end_ = map_it_->second.end();
+  }
+}
+
+// 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+// 取得できる行 ID が尽きたときは limit より小さい値を返す．
+Int64 TreeMapIndex<String>::ReverseCursor::get_next(
+    Int64 limit, std::vector<RowID> *row_ids) {
+  if (map_it_ == map_end_) {
+    return 0;
+  }
+  Int64 count = 0;
+  while (count < limit) {
+    if (set_it_ == set_end_) {
+      ++map_it_;
+      if (map_it_ == map_end_) {
+        return count;
+      }
+      set_it_ = map_it_->second.begin();
+      set_end_ = map_it_->second.end();
+    }
+    if (row_ids) {
+      row_ids->push_back(*set_it_);
+    }
+    ++set_it_;
+    ++count;
+  }
+  return count;
+}
+
+RowIDCursor *TreeMapIndex<String>::create_cursor(typename Map::iterator begin,
+                                                 typename Map::iterator end,
+                                                 bool reverse_order) {
+  if (reverse_order) {
+    return new ReverseCursor(begin, end);
+  } else {
+    return new Cursor(begin, end);
+  }
+}
+
+class TreeMapIndexHelper {
+ public:
+  static Index *create(IndexID index_id,
+                       const String &index_name,
+                       Column *column);
+};
+
+Index *TreeMapIndexHelper::create(IndexID index_id,
+                                  const String &index_name,
+                                  Column *column) {
+  switch (column->data_type()) {
+    case BOOLEAN: {
+      return new TreeMapIndex<Boolean>(index_id, index_name, column);
+    }
+    case INTEGER: {
+      return new TreeMapIndex<Int64>(index_id, index_name, column);
+    }
+    case FLOAT: {
+      return new TreeMapIndex<Float>(index_id, index_name, column);
+    }
+    case STRING: {
+      return new TreeMapIndex<String>(index_id, index_name, column);
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace
+
+// 索引を初期化する．
+Index::Index(IndexID id, const String &name, Column *column, IndexType type)
+    : id_(id),
+      name_(reinterpret_cast<const char *>(name.data()), name.size()),
+      column_(column),
+      type_(type) {}
+
+// 索引を破棄する．
+Index::~Index() {}
+
+// 指定された ID, 名前，対処カラム，種類の索引を作成して返す．
+Index *IndexHelper::create(IndexID index_id,
+                           const String &index_name,
+                           Column *column,
+                           IndexType index_type) {
+  switch (index_type) {
+    case TREE_MAP: {
+      return TreeMapIndexHelper::create(index_id, index_name, column);
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/index.hpp (+75 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/index.hpp    2014-02-27 18:42:27 +0900 (5f36e61)
@@ -0,0 +1,75 @@
+#ifndef GRNXX_INDEX_HPP
+#define GRNXX_INDEX_HPP
+
+#include "grnxx/datum.hpp"
+
+namespace grnxx {
+
+class Index {
+ public:
+  // 索引を初期化する．
+  Index(IndexID id, const String &name, Column *column, IndexType type);
+  // 索引を破棄する．
+  virtual ~Index();
+
+  // 索引の ID を返す．
+  IndexID id() const {
+    return id_;
+  }
+  // 索引の名前を返す．
+  String name() const {
+    return name_;
+  }
+  // 対象カラムを返す．
+  Column *column() const {
+    return column_;
+  }
+  // 索引の種類を返す．
+  IndexType type() const {
+    return type_;
+  }
+
+  // 指定されたデータを登録する．
+  virtual void insert(RowID row_id) = 0;
+  // 指定されたデータを削除する．
+  virtual void remove(RowID row_id) = 0;
+
+  // 行の一覧を取得できるカーソルを作成して返す．
+  virtual RowIDCursor *find_all(bool reverse_order = false) = 0;
+  // 指定された値が格納された行の一覧を取得できるカーソルを作成して返す．
+  virtual RowIDCursor *find_equal(const Datum &datum,
+                                  bool reverse_order = false) = 0;
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  virtual RowIDCursor *find_less(const Datum &datum,
+                                 bool less_equal = false,
+                                 bool reverse_order = false) = 0;
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  virtual RowIDCursor *find_greater(const Datum &datum,
+                                    bool greater_equal = false,
+                                    bool reverse_order = false) = 0;
+  // 指定された範囲の値が格納された行の一覧を取得できるカーソルを作成して返す．
+  virtual RowIDCursor *find_between(const Datum &begin, const Datum &end,
+                                    bool greater_equal = false,
+                                    bool less_equal = false,
+                                    bool reverse_order = false) = 0;
+
+ protected:
+  IndexID id_;
+  std::string name_;
+  Column *column_;
+  IndexType type_;
+};
+
+class IndexHelper {
+ public:
+  // 指定された ID, 名前，対処カラム，種類の索引を作成して返す．
+  static Index *create(IndexID index_id,
+                       const String &index_name,
+                       Column *column,
+                       IndexType index_type);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_INDEX_HPP
+

  Modified: lib/grnxx/library.cpp (+2 -0)
===================================================================
--- lib/grnxx/library.cpp    2014-02-24 16:02:00 +0900 (dbadac7)
+++ lib/grnxx/library.cpp    2014-02-27 18:42:27 +0900 (57dcc6b)
@@ -5,10 +5,12 @@
 
 namespace grnxx {
 
+// ライブラリの名前を返す．
 const char *Library::name() {
   return PACKAGE;
 }
 
+// ライブラリのバージョンを返す．
 const char *Library::version() {
   return GRNXX_VERSION;
 }

  Modified: lib/grnxx/library.hpp (+4 -0)
===================================================================
--- lib/grnxx/library.hpp    2014-02-24 16:02:00 +0900 (2219b37)
+++ lib/grnxx/library.hpp    2014-02-27 18:42:27 +0900 (1530383)
@@ -3,9 +3,13 @@
 
 namespace grnxx {
 
+// ライブラリ．
 class Library {
  public:
+  // ライブラリの名前を返す．
   static const char *name();
+
+  // ライブラリのバージョンを返す．
   static const char *version();
 };
 

  Added: lib/grnxx/sorter.cpp (+16 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/sorter.cpp    2014-02-27 18:42:27 +0900 (4e9f0a1)
@@ -0,0 +1,16 @@
+#include "grnxx/sorter.hpp"
+
+#include "grnxx/sorter_impl.hpp"
+
+namespace grnxx {
+
+// 演算器を作成する．
+Sorter *SorterHelper::create(const Table *table, const String &query) {
+  std::unique_ptr<SorterImpl> sorter(new SorterImpl);
+  if (!sorter->parse(table, query)) {
+    return nullptr;
+  }
+  return sorter.release();
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/sorter.hpp (+29 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/sorter.hpp    2014-02-27 18:42:27 +0900 (392719a)
@@ -0,0 +1,29 @@
+#ifndef GRNXX_SORTER_HPP
+#define GRNXX_SORTER_HPP
+
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+class Sorter {
+ public:
+  // 整列器を初期化する．
+  Sorter() {}
+  // 整列器を破棄する．
+  virtual ~Sorter() {}
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [offset, offset + limit) の範囲に限定される．
+  virtual void sort(RowID *row_ids, Int64 num_row_ids,
+                    Int64 offset = 0, Int64 limit = INT64_MAX) = 0;
+};
+
+class SorterHelper {
+ public:
+  // 演算器を作成する．
+  static Sorter *create(const Table *table, const String &query);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_SORTER_HPP

  Added: lib/grnxx/sorter_impl.cpp (+481 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/sorter_impl.cpp    2014-02-27 18:42:27 +0900 (4fe59a7)
@@ -0,0 +1,481 @@
+#include "grnxx/sorter_impl.hpp"
+
+#include "grnxx/column_impl.hpp"
+#include "grnxx/table.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+namespace {
+
+// 整列順序．
+enum SortOrder {
+  ASCENDING,
+  DESCENDING
+};
+
+template <typename T>
+class GenericSorterNode : public SorterNode {
+ public:
+  // ノードを初期化する．
+  GenericSorterNode(Column *column, SortOrder sort_order)
+      : column_(static_cast<ColumnImpl<T> *>(column)),
+        sort_order_(sort_order),
+        data_() {}
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+  void sort(RowID *row_ids, Int64 num_row_ids,
+            Int64 begin, Int64 end);
+
+ private:
+  ColumnImpl<T> *column_;
+  SortOrder sort_order_;
+  std::vector<T> data_;
+
+  // 第一引数の優先度が第二引数より高ければ true を返す．
+  struct AscendingPriorTo {
+    bool operator()(const T &lhs, const T &rhs) const {
+      return lhs < rhs;
+    }
+  };
+  struct DescendingPriorTo {
+    bool operator()(const T &lhs, const T &rhs) const {
+      return rhs < lhs;
+    }
+  };
+
+  // 三分岐のクイックソートをおこなう．
+  template <typename U>
+  void quick_sort(RowID *row_ids, T *values, Int64 size,
+                  Int64 begin, Int64 end, U prior_to);
+  // 挿入ソートをおこなう．
+  template <typename U>
+  void insertion_sort(RowID *row_ids, T *values, Int64 size, U prior_to);
+
+  // 枢軸となる要素を見つけ，その要素を先頭に移動する．
+  template <typename U>
+  void move_pivot_first(RowID *row_ids, T *values, Int64 size, U prior_to);
+};
+
+// 与えられた行の一覧を整列する．
+// 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+template <typename T>
+void GenericSorterNode<T>::sort(RowID *row_ids, Int64 num_row_ids,
+                                Int64 begin, Int64 end) {
+  // 整列に使うデータを取ってくる．
+  data_.resize(num_row_ids);
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    data_[i] = column_->get(row_ids[i]);
+  }
+  if (sort_order_ == ASCENDING) {
+    quick_sort(row_ids, &*data_.begin(), num_row_ids,
+               begin, end, AscendingPriorTo());
+  } else {
+    quick_sort(row_ids, &*data_.begin(), num_row_ids,
+               begin, end, DescendingPriorTo());
+  }
+}
+
+// 三分岐のクイックソートをおこなう．
+template <typename T>
+template <typename U>
+void GenericSorterNode<T>::quick_sort(RowID *row_ids, T *values, Int64 size,
+                                      Int64 begin, Int64 end, U prior_to) {
+  while (size >= 16) {
+    move_pivot_first(row_ids, values, size, prior_to);
+    const auto &pivot = values[0];
+    Int64 left = 1;
+    Int64 right = size;
+    Int64 pivot_left = 1;
+    Int64 pivot_right = size;
+    for ( ; ; ) {
+      // 枢軸を基準として左右へと分ける．
+      // 枢軸と等しい要素は左右端へと移動する．
+      while (left < right) {
+        if (prior_to(pivot, values[left])) {
+          break;
+        } else if (pivot == values[left]) {
+          std::swap(values[left], values[pivot_left]);
+          std::swap(row_ids[left], row_ids[pivot_left]);
+          ++pivot_left;
+        }
+        ++left;
+      }
+      while (left < right) {
+        --right;
+        if (prior_to(values[right], pivot)) {
+          break;
+        } else if (values[right] == pivot) {
+          --pivot_right;
+          std::swap(values[right], values[pivot_right]);
+          std::swap(row_ids[right], row_ids[pivot_right]);
+        }
+      }
+      if (left >= right) {
+        break;
+      }
+      std::swap(values[left], values[right]);
+      std::swap(row_ids[left], row_ids[right]);
+      ++left;
+    }
+
+    // 左端の値を境界の左に移動する．
+    while (pivot_left > 0) {
+      --pivot_left;
+      --left;
+      std::swap(values[pivot_left], values[left]);
+      std::swap(row_ids[pivot_left], row_ids[left]);
+    }
+    // 右端の値を境界の右に移動する．
+    while (pivot_right < size) {
+      std::swap(values[pivot_right], values[right]);
+      std::swap(row_ids[pivot_right], row_ids[right]);
+      ++pivot_right;
+      ++right;
+    }
+
+    // 枢軸と同値の範囲 [left, right) には次の検索条件を適用する．
+    if (next()) {
+      if (((right - left) >= 2) && (begin < right) && (end > left)) {
+        Int64 next_begin = (begin < left) ? 0 : (begin - left);
+        Int64 next_end = ((end > right) ? right : end) - left;
+        next()->sort(row_ids + left, right - left, next_begin, next_end);
+      }
+    }
+
+    // 再帰呼び出しの深さを抑えるため，左側 [0, left) と右側 [right, size) の
+    // 小さい方を再帰呼び出しで処理し，大きい方を次のループで処理する．
+    if (left < (size - right)) {
+      if ((begin < left) && (left >= 2)) {
+        Int64 next_end = (end < left) ? end : left;
+        quick_sort(row_ids, values, left, begin, next_end, prior_to);
+      }
+      if (end <= right) {
+        return;
+      }
+      row_ids += right;
+      values += right;
+      size -= right;
+      begin -= right;
+      if (begin < 0) {
+        begin = 0;
+      }
+      end -= right;
+    } else {
+      if ((end > right) && ((size - right) >= 2)) {
+        Int64 next_begin = (begin < right) ? 0 : (begin - right);
+        Int64 next_end = end - right;
+        quick_sort(row_ids + right, values + right, size - right,
+                   next_begin, next_end, prior_to);
+      }
+      if (begin >= left) {
+        return;
+      }
+      size = left;
+      if (end > left) {
+        end = left;
+      }
+    }
+  }
+
+  if (size >= 2) {
+    insertion_sort(row_ids, values, size, prior_to);
+  }
+}
+
+// 挿入ソートをおこなう．
+template <typename T>
+template <typename U>
+void GenericSorterNode<T>::insertion_sort(RowID *row_ids, T *values,
+                                          Int64 size, U prior_to) {
+  // まずは挿入ソートをおこなう．
+  for (Int64 i = 1; i < size; ++i) {
+    for (Int64 j = i; j > 0; --j) {
+      if (prior_to(values[j], values[j - 1])) {
+        std::swap(row_ids[j], row_ids[j - 1]);
+        std::swap(values[j], values[j - 1]);
+      } else {
+        break;
+      }
+    }
+  }
+
+  // 同値の範囲には次の検索条件を適用する．
+  if (next()) {
+    Int64 begin = 0;
+    for (Int64 i = 1; i < size; ++i) {
+      if (values[i] != values[begin]) {
+        if ((i - begin) >= 2) {
+          next()->sort(row_ids + begin, i - begin, 0, i - begin);
+        }
+        begin = i;
+      }
+    }
+    if ((size - begin) >= 2) {
+      next()->sort(row_ids + begin, size - begin, 0, size - begin);
+    }
+  }
+}
+
+// 枢軸となる要素を見つけ，その要素を先頭に移動する．
+template <typename T>
+template <typename U>
+void GenericSorterNode<T>::move_pivot_first(RowID *row_ids, T *values,
+                                            Int64 size, U prior_to) {
+  RowID first = 1;
+  RowID middle = size / 2;
+  RowID last = size - 2;
+  if (prior_to(values[first], values[middle])) {
+    // first < middle.
+    if (prior_to(values[middle], values[last])) {
+      // first < middle < last.
+      std::swap(values[0], values[middle]);
+      std::swap(row_ids[0], row_ids[middle]);
+    } else if (prior_to(values[first], values[last])) {
+      // first < last < middle.
+      std::swap(values[0], values[last]);
+      std::swap(row_ids[0], row_ids[last]);
+    } else {
+      // last < first < middle.
+      std::swap(values[0], values[first]);
+      std::swap(row_ids[0], row_ids[first]);
+    }
+  } else if (prior_to(values[last], values[middle])) {
+    // last < middle < first.
+    std::swap(values[0], values[middle]);
+    std::swap(row_ids[0], row_ids[middle]);
+  } else if (prior_to(values[last], values[first])) {
+    // middle < last < first.
+    std::swap(values[0], values[last]);
+    std::swap(row_ids[0], row_ids[last]);
+  } else {
+    // middle < first < last.
+    std::swap(values[0], values[first]);
+    std::swap(row_ids[0], row_ids[first]);
+  }
+}
+
+class BooleanSorterNode : public SorterNode {
+ public:
+  // ノードを初期化する．
+  BooleanSorterNode(Column *column, SortOrder sort_order)
+      : SorterNode(),
+        column_(static_cast<ColumnImpl<Boolean> *>(column)),
+        sort_order_(sort_order) {}
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+  void sort(RowID *row_ids, Int64 num_row_ids,
+            Int64 begin, Int64 end);
+
+ private:
+  ColumnImpl<Boolean> *column_;
+  SortOrder sort_order_;
+
+  // 昇順のときは TRUE を後ろに移動する．
+  struct AscendingIsPrior {
+    bool operator()(Boolean value) const {
+      return !value;
+    }
+  };
+  // 降順のときは FALSE を後ろに移動する．
+  struct DescendingIsPrior {
+    bool operator()(Boolean value) const {
+      return value;
+    }
+  };
+
+  // 行 ID の一覧を全域ソートする．
+  template <typename T>
+  void entire_sort(RowID *row_ids, Int64 num_row_ids,
+                   Int64 begin, Int64 end, T is_prior);
+};
+
+// 与えられた行の一覧を整列する．
+// 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+void BooleanSorterNode::sort(RowID *row_ids, Int64 num_row_ids,
+                             Int64 begin, Int64 end) {
+  if (sort_order_ == ASCENDING) {
+    entire_sort(row_ids, num_row_ids, begin, end, AscendingIsPrior());
+  } else {
+    entire_sort(row_ids, num_row_ids, begin, end, DescendingIsPrior());
+  }
+}
+
+// 行 ID の一覧を全域ソートする．
+template <typename T>
+void BooleanSorterNode::entire_sort(RowID *row_ids, Int64 num_row_ids,
+                                    Int64 begin, Int64 end, T is_prior) {
+  // 優先する値を左に，そうでない値を右に移動する．
+  Int64 left = 0;
+  Int64 right = num_row_ids;
+  while (left < right) {
+    auto value = column_->get(row_ids[left]);
+    if (is_prior(value)) {
+      ++left;
+    } else {
+      --right;
+      std::swap(row_ids[left], row_ids[right]);
+    }
+  }
+  // この時点で left, right は等しく，左右の境界になっている．
+  if (next()) {
+    // 左右に 2 つ以上の行があり，整列範囲と重なっていれば，次の整列条件を適用する．
+    if ((left >= 2) && (begin < left)) {
+      next()->sort(row_ids, left, begin, (end < left) ? end : left);
+    }
+    if (((num_row_ids - left) >= 2) && (end > left)) {
+      if (begin < left) {
+        begin = 0;
+      } else {
+        begin -= left;
+      }
+      end -= left;
+      next()->sort(row_ids + left, num_row_ids - left, begin, end);
+    }
+  }
+}
+
+// 行 ID の大小関係にしたがって整列する．
+class RowIDSorterNode : public SorterNode {
+ public:
+  // ノードを初期化する．
+  explicit RowIDSorterNode(SortOrder sort_order) : sort_order_(sort_order) {}
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+  void sort(RowID *row_ids, Int64 num_row_ids,
+            Int64 begin, Int64 end);
+
+ private:
+  SortOrder sort_order_;
+};
+
+// 与えられた行の一覧を整列する．
+// 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+void RowIDSorterNode::sort(RowID *row_ids, Int64 num_row_ids,
+                           Int64 begin, Int64 end) {
+  // 整列対象が多くて整列範囲が狭いときは部分ソートを使い，それ以外のときは全域を整列する．
+  // FIXME: 適当に設定したので，将来的には最適な設定を求めるべきである．
+  // FIXME: 行 ID に重複がないという前提になっているため，次の整列条件があっても関係ない．
+  if ((num_row_ids >= 1000) && (end < 100)) {
+    if (sort_order_ == ASCENDING) {
+      std::partial_sort(row_ids, row_ids + end,
+                        row_ids + num_row_ids, std::less<RowID>());
+    } else {
+      std::partial_sort(row_ids, row_ids + end,
+                        row_ids + num_row_ids, std::greater<RowID>());
+    }
+  } else {
+    if (sort_order_ == ASCENDING) {
+      std::sort(row_ids, row_ids + num_row_ids, std::less<RowID>());
+    } else {
+      std::sort(row_ids, row_ids + num_row_ids, std::greater<RowID>());
+    }
+  }
+}
+
+}  // namespace
+
+// 整列器を初期化する．
+SorterImpl::SorterImpl()
+    : Sorter(),
+      table_(nullptr),
+      nodes_() {}
+
+// 整列器を破棄する．
+SorterImpl::~SorterImpl() {}
+
+// 指定された文字列に対応する整列器を作成する．
+// 文字列には，コンマ区切りでカラムを指定することができる．
+// カラム名の先頭に '-' を付けると降順になる．
+bool SorterImpl::parse(const Table *table, String query) {
+  table_ = table;
+  nodes_.clear();
+  while (!query.empty()) {
+    Int64 delim_pos = query.find_first_of(',');
+    String column_name;
+    if (delim_pos == query.npos) {
+      column_name = query;
+      query = "";
+    } else {
+      column_name = query.prefix(delim_pos);
+      query = query.except_prefix(delim_pos + 1);
+    }
+    if (!append_column(column_name)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+// 与えられた行の一覧を整列する．
+// 整列の結果が保証されるのは [offset, offset + limit) の範囲に限定される．
+void SorterImpl::sort(RowID *row_ids, Int64 num_row_ids,
+                      Int64 offset, Int64 limit) {
+  // 整列条件が存在しなければ何もしない．
+  if (nodes_.empty()) {
+    return;
+  }
+  // 整列対象が存在しなければ何もしない．
+  if ((num_row_ids <= 1) || (offset >= num_row_ids) || (limit <= 0)) {
+    return;
+  }
+  // 整列範囲を補正する．
+  if (offset < 0) {
+    offset = 0;
+  }
+  if (limit > (num_row_ids - offset)) {
+    limit = num_row_ids - offset;
+  }
+  nodes_.front()->sort(row_ids, num_row_ids, offset, offset + limit);
+}
+
+// 指定された名前のカラムを整列条件に加える．
+// 先頭に '-' を付けると降順になる．
+// 成功すれば true を返し，失敗すれば false を返す．
+bool SorterImpl::append_column(String column_name) {
+  Column *column = nullptr;
+  SortOrder sort_order = ASCENDING;
+  if (column_name.starts_with("-")) {
+    column_name = column_name.except_prefix(1);
+    sort_order = DESCENDING;
+  }
+  if (column_name != "_id") {
+    column = table_->get_column_by_name(column_name);
+    if (!column) {
+      return false;
+    }
+  }
+  std::unique_ptr<SorterNode> node;
+  if (column) {
+    switch (column->data_type()) {
+      case BOOLEAN: {
+        node.reset(new BooleanSorterNode(column, sort_order));
+        break;
+      }
+      case INTEGER: {
+        node.reset(new GenericSorterNode<Int64>(column, sort_order));
+        break;
+      }
+      case FLOAT: {
+        node.reset(new GenericSorterNode<Float>(column, sort_order));
+        break;
+      }
+      case STRING: {
+        node.reset(new GenericSorterNode<String>(column, sort_order));
+        break;
+      }
+    }
+  } else {
+    node.reset(new RowIDSorterNode(sort_order));
+  }
+  if (!nodes_.empty()) {
+    nodes_.back()->set_next(node.get());
+  }
+  nodes_.push_back(std::move(node));
+  return true;
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/sorter_impl.hpp (+66 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/sorter_impl.hpp    2014-02-27 18:42:27 +0900 (aa8ca3a)
@@ -0,0 +1,66 @@
+#ifndef GRNXX_SORTER_IMPL_HPP
+#define GRNXX_SORTER_IMPL_HPP
+
+#include "grnxx/sorter.hpp"
+#include "grnxx/string.hpp"
+
+namespace grnxx {
+
+// 整列器を構成するノード．
+// 整列条件のひとつと対応する．
+class SorterNode {
+ public:
+  // ノードを初期化する．
+  SorterNode() : next_(nullptr) {}
+  // ノードを破棄する．
+  virtual ~SorterNode() {}
+
+  // 次のノードを返す．
+  SorterNode *next() {
+    return next_;
+  }
+  // 次のノードを設定する．
+  void set_next(SorterNode *next) {
+    next_ = next;
+  }
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [begin, end) の範囲に限定される．
+  virtual void sort(RowID *row_ids, Int64 num_row_ids,
+                    Int64 begin, Int64 end) = 0;
+
+ private:
+  SorterNode *next_;
+};
+
+// 整列器．
+class SorterImpl : public Sorter {
+ public:
+  // 整列器を初期化する．
+  SorterImpl();
+  // 整列器を破棄する．
+  ~SorterImpl();
+
+  // 指定された文字列に対応する整列器を作成する．
+  // 文字列には，コンマ区切りでカラムを指定することができる．
+  // カラム名の先頭に '-' を付けると降順になる．
+  bool parse(const Table *table, String query);
+
+  // 与えられた行の一覧を整列する．
+  // 整列の結果が保証されるのは [offset, offset + limit) の範囲に限定される．
+  void sort(RowID *row_ids, Int64 num_row_ids,
+            Int64 offset = 0, Int64 limit = -1);
+
+ protected:
+  const Table *table_;
+  std::vector<std::unique_ptr<SorterNode>> nodes_;
+
+  // 指定された名前のカラムを整列条件に加える．
+  // 先頭に '-' を付けると降順になる．
+  // 成功すれば true を返し，失敗すれば false を返す．
+  bool append_column(String column_name);
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_SORTER_IMPL_HPP

  Added: lib/grnxx/string.cpp (+12 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/string.cpp    2014-02-27 18:42:27 +0900 (d916ba3)
@@ -0,0 +1,12 @@
+#include "grnxx/string.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+
+std::ostream &operator<<(std::ostream &stream, const String &string) {
+  stream.write(reinterpret_cast<const char *>(string.data()), string.size());
+  return stream;
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/string.hpp (+181 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/string.hpp    2014-02-27 18:42:27 +0900 (2fc9597)
@@ -0,0 +1,181 @@
+#ifndef GRNXX_STRING_HPP
+#define GRNXX_STRING_HPP
+
+#include "grnxx/types.hpp"
+
+namespace grnxx {
+
+// 文字列．
+class String {
+ public:
+  // 明示的な初期化はしない．
+  String() = default;
+  // 空文字列として初期化する．
+  String(std::nullptr_t) : data_(nullptr), size_(0) {}
+  // NULL 文字を終端とする文字列を参照するように初期化する．
+  String(const char *str)
+      : data_(reinterpret_cast<const UInt8 *>(str)),
+        size_(std::strlen(str)) {}
+  // 文字列を参照するように初期化する．
+  String(const std::string &str)
+      : data_(reinterpret_cast<const UInt8 *>(str.data())),
+        size_(str.size()) {}
+  // 指定されたバイト列を参照するように初期化する．
+  String(const void *data, Int64 size)
+      : data_(static_cast<const UInt8 *>(data)),
+        size_(size) {}
+
+  // 先頭の n bytes に対するオブジェクトを作成する．
+  String prefix(Int64 n) const {
+    return String(data_, n);
+  }
+  // 末尾の n bytes に対するオブジェクトを作成する．
+  String suffix(Int64 n) const {
+    return String(data_ + size_ - n, n);
+  }
+
+  // 先頭の n bytes を取り除いた部分列に対するオブジェクトを作成する．
+  String except_prefix(Int64 n) const {
+    return String(data_ + n, size_ - n);
+  }
+  // 末尾の n bytes を取り除いた部分列に対するオブジェクトを作成する．
+  String except_suffix(Int64 n) const {
+    return String(data_, size_ - n);
+  }
+
+  // 先頭の n bytes を飛ばした後，残りの先頭 m bytes に対するオブジェクトを作成する．
+  String extract(Int64 n, Int64 m) const {
+    return String(data_ + n, m);
+  }
+  // 先頭の n bytes と末尾の n bytes を取り除いた部分列に対するオブジェクトを作成する．
+  String trim(Int64 n, Int64 m) const {
+    return String(data_ + n, size_ - n - m);
+  }
+
+  // 文字列同士を比較する．
+  bool operator==(const String &rhs) const {
+    return (size_ == rhs.size_) &&
+           (std::memcmp(data_, rhs.data_, size_) == 0);
+  }
+  bool operator!=(const String &rhs) const {
+    return !(*this == rhs);
+  }
+  bool operator<(const String &rhs) const {
+    const Int64 min_size = (size_ < rhs.size_) ? size_ : rhs.size_;
+    int result = std::memcmp(data_, rhs.data_, min_size);
+    return (result < 0) || ((result == 0) && (size_ < rhs.size_));
+  }
+  bool operator>(const String &rhs) const {
+    return rhs < *this;
+  }
+  bool operator<=(const String &rhs) const {
+    return !(*this > rhs);
+  }
+  bool operator>=(const String &rhs) const {
+    return !(*this < rhs);
+  }
+
+  // 指定された文字列と比較して，小さければ負の値を返し，等しければ 0 を返し，
+  // 大きければ正の値を返す．
+  int compare(const String &bytes) const {
+    const Int64 min_size = (size_ < bytes.size_) ? size_ : bytes.size_;
+    int result = std::memcmp(data_, bytes.data_, min_size);
+    if (result != 0) {
+      return result;
+    }
+    return (size_ < bytes.size_) ? -1 : (size_ > bytes.size_);
+  }
+
+  // 指定された文字列で始まっていれば true を返し，そうでなければ false を返す．
+  bool starts_with(const String &bytes) const {
+    return (size_ >= bytes.size_) && (prefix(bytes.size_) == bytes);
+  }
+  // 指定された文字列で終わっていれば true を返し，そうでなければ false を返す．
+  bool ends_with(const String &bytes) const {
+    return (size_ >= bytes.size_) && (suffix(bytes.size_) == bytes);
+  }
+
+  // 指定された文字が最初に出現する位置を返す．
+  // 先頭の offset bytes は無視する．
+  // 出現しないときは npos を返す．
+  Int64 find_first_of(UInt8 byte, Int64 offset = 0) const {
+    for (Int64 i = offset; i < size_; ++i) {
+      if (data_[i] == byte) {
+        return i;
+      }
+    }
+    return npos;
+  }
+  // 指定された文字列に含まれる文字が最初に出現する位置を返す．
+  // 先頭の offset bytes は無視する．
+  // 出現しないときは npos を返す．
+  Int64 find_first_of(const String &str, Int64 offset = 0) const {
+    for (Int64 i = offset; i < size_; ++i) {
+      if (str.find_first_of(data_[i]) != npos) {
+        return i;
+      }
+    }
+    return npos;
+  }
+  // 指定された文字が最後に出現する位置を返す．
+  // 先頭の offset bytes は無視する．
+  // 出現しないときは npos を返す．
+  Int64 find_last_of(UInt8 byte, Int64 offset = 0) const {
+    for (Int64 i = size_; i > offset; ) {
+      if (data_[--i] == byte) {
+        return i;
+      }
+    }
+    return npos;
+  }
+
+  // 指定された文字列に含まれない文字が最初に出現する位置を返す．
+  // 出現しないときは npos を返す．
+  Int64 find_first_not_of(const String &str, Int64 offset = 0) const {
+    for (Int64 i = offset; i < size_; ++i) {
+      if (str.find_first_of(data_[i]) == npos) {
+        return i;
+      }
+    }
+    return npos;
+  }
+  // 指定された文字列に含まれない文字が最後に出現する位置を返す．
+  // 出現しないときは npos を返す．
+  Int64 find_last_not_of(const String &str, Int64 offset = 0) const {
+    for (Int64 i = size_; i > offset; ) {
+      if (str.find_first_of(data_[--i]) == npos) {
+        return i;
+      }
+    }
+    return npos;
+  }
+
+  // 文字（バイト）を返す．
+  UInt8 operator[](Int64 i) const {
+    return data_[i];
+  }
+  // 開始アドレスを返す．
+  const UInt8 *data() const {
+    return data_;
+  }
+  // 長さをバイト単位で返す．
+  Int64 size() const {
+    return size_;
+  }
+  // 長さが 0 であれば true を返し，そうでなければ false を返す．
+  bool empty() const {
+    return size_ == 0;
+  }
+
+  static constexpr Int64 npos = -1;
+
+ private:
+  const UInt8 *data_;
+  Int64 size_;
+};
+
+std::ostream &operator<<(std::ostream &stream, const String &string);
+
+}  // namespace grnxx
+
+#endif  // GRNXX_STRING_HPP

  Added: lib/grnxx/table.cpp (+498 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/table.cpp    2014-02-27 18:42:27 +0900 (ee7a5e7)
@@ -0,0 +1,498 @@
+#include "grnxx/table.hpp"
+
+#include "grnxx/calc.hpp"
+#include "grnxx/column_impl.hpp"
+#include "grnxx/index.hpp"
+#include "grnxx/sorter.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+namespace {
+
+// カンマ区切りの文字列をばらす．
+std::vector<String> split_column_names(
+    const String &comma_separated_column_names) {
+  std::vector<String> column_names;
+  if (comma_separated_column_names.empty()) {
+    return column_names;
+  }
+  Int64 begin = 0;
+  while (begin < comma_separated_column_names.size()) {
+    auto end = comma_separated_column_names.find_first_of(',', begin);
+    if (end == comma_separated_column_names.npos) {
+      end = comma_separated_column_names.size();
+    }
+    column_names.push_back(
+        comma_separated_column_names.extract(begin, end - begin));
+    begin = end + 1;
+  }
+  return column_names;
+}
+
+// FIXME: これのためだけに column_impl.hpp を #include している状態なので，
+//        ColumnImpl に持たせるべきなのかもしれない．
+// 基準となるカラムの値が変化する位置を求める．
+template <typename T>
+void find_boundaries(const RowID *row_ids, Int64 num_row_ids,
+                     const Column *column,
+                     const std::vector<Int64> &boundaries,
+                     std::vector<Int64> *new_boundaries) {
+  // あらかじめ十分なサイズの仮想領域を確保することで，拡張にかかるコストをなくす．
+  new_boundaries->reserve(num_row_ids);
+  auto data = static_cast<const ColumnImpl<T> *>(column);
+  Int64 begin = 0;
+  for (auto end : boundaries) {
+    for (auto i = begin + 1; i < end; ++i) {
+      if (data->get(row_ids[i - 1]) != data->get(row_ids[i])) {
+        new_boundaries->push_back(i);
+      }
+    }
+    new_boundaries->push_back(end);
+    begin = end;
+  }
+}
+
+}  // namespace
+
+// テーブルを初期化する．
+Table::Table(Database *database, TableID id, const String &name)
+    : database_(database),
+      id_(id),
+      name_(reinterpret_cast<const char *>(name.data()), name.size()),
+      max_row_id_(MIN_ROW_ID - 1),
+      columns_(MIN_COLUMN_ID),
+      columns_map_(),
+      indexes_(MIN_INDEX_ID),
+      indexes_map_() {}
+
+// テーブルを破棄する．
+Table::~Table() {}
+
+// 指定された名前とデータ型のカラムを作成して返す．
+// 失敗すると nullptr を返す．
+Column *Table::create_column(const String &column_name, DataType data_type) {
+  auto it = columns_map_.find(column_name);
+  if (it != columns_map_.end()) {
+    return nullptr;
+  }
+  ColumnID column_id = min_column_id();
+  for ( ; column_id <= max_column_id(); ++column_id) {
+    if (!columns_[column_id]) {
+      break;
+    }
+  }
+  if (column_id > max_column_id()) {
+    columns_.resize(column_id + 1);
+  }
+  std::unique_ptr<Column> new_column(
+      ColumnHelper::create(this, column_id, column_name, data_type));
+  new_column->resize(max_row_id());
+  columns_map_.insert(it, std::make_pair(new_column->name(), column_id));
+  columns_[column_id] = std::move(new_column);
+  return columns_[column_id].get();
+}
+
+// 指定された名前のカラムを破棄する．
+// 成功すれば true を返し，失敗すれば false を返す．
+bool Table::drop_column(const String &column_name) {
+  auto it = columns_map_.find(column_name);
+  if (it == columns_map_.end()) {
+    return false;
+  }
+  auto &column = columns_[it->second];
+  for (auto &index : indexes_) {
+    if (index) {
+      if (index->column() == column.get()) {
+        drop_index(index->name());
+      }
+    }
+  }
+  column.reset();
+  columns_map_.erase(it);
+  return true;
+}
+
+// 指定された 名前 のカラムを返す．
+// なければ nullptr を返す．
+Column *Table::get_column_by_name(const String &column_name) const {
+  auto it = columns_map_.find(column_name);
+  if (it == columns_map_.end()) {
+    return nullptr;
+  }
+  return columns_[it->second].get();
+}
+
+// カラムの一覧を columns の末尾に追加し，カラムの数を返す．
+Int64 Table::get_columns(std::vector<Column *> *columns) const {
+  std::size_t old_size = columns->size();
+  for (auto &column : columns_) {
+    if (column) {
+      columns->push_back(column.get());
+    }
+  }
+  return columns->size() - old_size;
+}
+
+// 指定された名前，対象カラム，種類の索引を作成して返す．
+// 失敗すると nullptr を返す．
+Index *Table::create_index(const String &index_name, const String &column_name,
+                           IndexType index_type) {
+  Column *column = get_column_by_name(column_name);
+  if (!column) {
+    return nullptr;
+  }
+  auto it = indexes_map_.find(index_name);
+  if (it != indexes_map_.end()) {
+    return nullptr;
+  }
+  IndexID index_id = min_index_id();
+  for ( ; index_id <= max_index_id(); ++index_id) {
+    if (!indexes_[index_id]) {
+      break;
+    }
+  }
+  if (index_id > max_index_id()) {
+    indexes_.resize(index_id + 1);
+  }
+  std::unique_ptr<Index> new_index(
+      IndexHelper::create(index_id, index_name, column, index_type));
+  if (!column->register_index(new_index.get())) {
+    return nullptr;
+  }
+  for (RowID row_id = min_row_id(); row_id <= max_row_id(); ++row_id) {
+    new_index->insert(row_id);
+  }
+  indexes_map_.insert(it, std::make_pair(new_index->name(), index_id));
+  indexes_[index_id] = std::move(new_index);
+  return indexes_[index_id].get();
+}
+
+// 指定された名前の索引を破棄する．
+// 成功すれば true を返し，失敗すれば false を返す．
+bool Table::drop_index(const String &index_name) {
+  auto it = indexes_map_.find(index_name);
+  if (it == indexes_map_.end()) {
+    return false;
+  }
+  auto &index = indexes_[it->second];
+  if (!index->column()->unregister_index(index.get())) {
+    return false;
+  }
+  index.reset();
+  indexes_map_.erase(it);
+  return true;
+}
+
+// 指定された名前の索引を返す．
+// なければ nullptr を返す．
+Index *Table::get_index_by_name(const String &index_name) const {
+  auto it = indexes_map_.find(index_name);
+  if (it == indexes_map_.end()) {
+    return nullptr;
+  }
+  return indexes_[it->second].get();
+}
+
+// 索引の一覧を indexes の末尾に追加し，索引の数を返す．
+Int64 Table::get_indexes(std::vector<Index *> *indexes) const {
+  std::size_t old_size = indexes->size();
+  for (auto &index : indexes_) {
+    if (index) {
+      indexes->push_back(index.get());
+    }
+  }
+  return indexes->size() - old_size;
+}
+
+// 行を追加して，その行 ID を返す．
+RowID Table::insert_row() {
+  RowID row_id = max_row_id() + 1;
+  for (auto &column : columns_) {
+    if (column) {
+      column->resize(row_id);
+    }
+  }
+  max_row_id_ = row_id;
+  return row_id;
+}
+
+// 指定されたテーブルの範囲内にある行 ID を取得するようにカーソルを初期化する．
+Table::Cursor::Cursor(RowID range_min, RowID range_max)
+    : RowIDCursor(),
+      row_id_(range_min),
+      max_row_id_(range_max) {}
+
+// 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+// 取得できる行 ID が尽きたときは limit より小さい値を返す．
+Int64 Table::Cursor::get_next(Int64 limit, std::vector<RowID> *row_ids) {
+  if (row_ids) {
+    Int64 count = 0;
+    while ((count < limit) && (row_id_ <= max_row_id_)) {
+      row_ids->push_back(row_id_);
+      ++row_id_;
+      ++count;
+    }
+    return count;
+  } else {
+    Int64 count;
+    if (limit > (max_row_id_ - row_id_ + 1)) {
+      count = max_row_id_ - row_id_ + 1;
+    } else {
+      count = limit;
+    }
+    row_id_ += count;
+    return count;
+  }
+}
+
+// 指定された範囲の行 ID を取得するカーソルを作成して返す．
+// 範囲が省略された，もしくは 0 を指定されたときは，
+// 行 ID の最小値・最大値を範囲として使用する．
+Table::Cursor *Table::create_cursor(RowID range_min, RowID range_max) const {
+  if (range_min < min_row_id()) {
+    range_min = min_row_id();
+  }
+  if (range_max > max_row_id()) {
+    range_max = max_row_id();
+  }
+  return new Cursor(range_min, range_max);
+}
+
+// 演算器を作成する．
+Calc *Table::create_calc(const String &query) const {
+  return CalcHelper::create(this, query);
+}
+
+// 整列器を作成する．
+Sorter *Table::create_sorter(const String &query) const {
+  return SorterHelper::create(this, query);
+}
+
+// 整列済みの行一覧を受け取り，グループの境界を求める．
+bool Table::group_by(const RowID *row_ids, Int64 num_row_ids,
+                     const String &comma_separated_column_names,
+                     std::vector<Int64> *boundaries) {
+  boundaries->clear();
+  if (num_row_ids == 0) {
+    return true;
+  }
+  boundaries->push_back(num_row_ids);
+  auto column_names = split_column_names(comma_separated_column_names);
+  for (const String &column_name : column_names) {
+    // 一カラムずつ走査する．
+    auto column = get_column_by_name(column_name);
+    if (!column) {
+      return false;
+    }
+    std::vector<Int64> new_boundaries;
+    switch (column->data_type()) {
+      case BOOLEAN: {
+        find_boundaries<Boolean>(row_ids, num_row_ids, column,
+                                 *boundaries, &new_boundaries);
+        break;
+      }
+      case INTEGER: {
+        find_boundaries<Int64>(row_ids, num_row_ids, column,
+                               *boundaries, &new_boundaries);
+        break;
+      }
+      case FLOAT: {
+        find_boundaries<Float>(row_ids, num_row_ids, column,
+                               *boundaries, &new_boundaries);
+        break;
+      }
+      case STRING: {
+        find_boundaries<String>(row_ids, num_row_ids, column,
+                                *boundaries, &new_boundaries);
+        break;
+      }
+      default: {
+        return false;
+      }
+    }
+    boundaries->swap(new_boundaries);
+  }
+  return true;
+}
+
+// ストリームに書き出す．
+std::ostream &Table::write_to(std::ostream &stream) const {
+  stream << "{ id = " << id_
+         << ", name = \"" << name_ << '"'
+         << ", columns = ";
+  std::vector<Column *> columns;
+  if (get_columns(&columns) == 0) {
+    stream << "{}";
+  } else {
+    stream << "{ " << *columns[0];
+    for (std::size_t i = 1; i < columns.size(); ++i) {
+      stream << ", " << *columns[i];
+    }
+    stream << " }";
+  }
+  stream << " }";
+  return stream;
+}
+
+// 行の一覧を文字列化する．
+std::ostream &Table::write_to(std::ostream &stream,
+                              const RowID *row_ids, Int64 num_row_ids,
+                              const String &comma_separated_column_names) {
+  std::vector<String> column_names;
+  std::vector<Column *> columns;
+  if (comma_separated_column_names.empty() ||
+      (comma_separated_column_names == "*")) {
+    // 指定なし，およびに "*" のときはすべてのカラムに展開する．
+    get_columns(&columns);
+    column_names.push_back("_id");
+    for (auto column : columns) {
+      column_names.push_back(column->name());
+    }
+    columns.insert(columns.begin(), nullptr);
+  } else {
+    column_names = split_column_names(comma_separated_column_names);
+    for (const String &column_name : column_names) {
+      auto column = get_column_by_name(column_name);
+      if (!column) {
+        // "_id"という名前が指定されて，しかも該当するカラムが存在しないときは行IDを使う．
+        if (column_name != "_id") {
+//          std::cerr << "unknown column: \"" << column_name << "\"";
+          return stream;
+        }
+      }
+      columns.push_back(column);
+    }
+  }
+  stream << "{ column_names = {";
+  for (std::size_t i = 0; i < column_names.size(); ++i) {
+    if (i == 0) {
+      stream << ' ';
+    }
+    stream << '"' << column_names[i] << '"';
+    if (i != (column_names.size() - 1)) {
+      stream << ',';
+    }
+    stream << ' ';
+  }
+  stream << "}, rows = {";
+
+  for (Int64 i = 0; i < num_row_ids; ++i) {
+    if (i == 0) {
+      stream << ' ';
+    }
+    stream << '{';
+    for (std::size_t j = 0; j < columns.size(); ++j) {
+      if (j == 0) {
+        stream << ' ';
+      }
+      if (columns[j]) {
+        stream << columns[j]->generic_get(row_ids[i]);
+      } else {
+        stream << row_ids[i];
+      }
+      if (j != (columns.size() - 1)) {
+        stream << ',';
+      }
+      stream << ' ';
+    }
+    stream << '}';
+    if (i != (num_row_ids - 1)) {
+      stream << ',';
+    }
+    stream << ' ';
+  }
+  stream << "} }";
+  return stream;
+}
+
+// 行の一覧をグループ毎に文字列化する．
+std::ostream &Table::write_to(std::ostream &stream,
+                              const RowID *row_ids, Int64 num_row_ids,
+                              const std::vector<Int64> &boundaries,
+                              const String &comma_separated_column_names) {
+  std::vector<String> column_names;
+  std::vector<Column *> columns;
+  if (comma_separated_column_names.empty() ||
+      (comma_separated_column_names == "*")) {
+    // 指定なし，およびに "*" のときはすべてのカラムに展開する．
+    get_columns(&columns);
+    column_names.push_back("_id");
+    for (auto column : columns) {
+      column_names.push_back(column->name());
+    }
+    columns.insert(columns.begin(), nullptr);
+  } else {
+    column_names = split_column_names(comma_separated_column_names);
+    for (const String &column_name : column_names) {
+      auto column = get_column_by_name(column_name);
+      if (!column) {
+        // "_id"という名前が指定されて，しかも該当するカラムが存在しないときは行IDを使う．
+        if (column_name != "_id") {
+//          std::cerr << "unknown column: \"" << column_name << "\"";
+          return stream;
+        }
+      }
+      columns.push_back(column);
+    }
+  }
+  stream << "{ column_names = {";
+  for (std::size_t i = 0; i < column_names.size(); ++i) {
+    if (i == 0) {
+      stream << ' ';
+    }
+    stream << '"' << column_names[i] << '"';
+    if (i != (column_names.size() - 1)) {
+      stream << ',';
+    }
+    stream << ' ';
+  }
+  stream << "}, groups = {";
+
+  Int64 begin = 0;
+  for (auto end : boundaries) {
+    if (end == boundaries.front()) {
+      stream << ' ';
+    }
+    stream << '{';
+    for (Int64 i = begin; i < end; ++i) {
+      if (i == begin) {
+        stream << ' ';
+      }
+      stream << '{';
+      for (std::size_t j = 0; j < columns.size(); ++j) {
+        if (j == 0) {
+          stream << ' ';
+        }
+        if (columns[j]) {
+          stream << columns[j]->generic_get(row_ids[i]);
+        } else {
+          stream << row_ids[i];
+        }
+        if (j != (columns.size() - 1)) {
+          stream << ',';
+        }
+        stream << ' ';
+      }
+      stream << '}';
+      if (i != (end - 1)) {
+        stream << ',';
+      }
+      stream << ' ';
+    }
+    stream << '}';
+    if (end != boundaries.back()) {
+      stream << ',';
+    }
+    stream << ' ';
+    begin = end;
+  }
+  stream << "} }";
+  return stream;
+}
+
+std::ostream &operator<<(std::ostream &stream, const Table &table) {
+  return table.write_to(stream);
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/table.hpp (+165 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/table.hpp    2014-02-27 18:42:27 +0900 (e7124c7)
@@ -0,0 +1,165 @@
+#ifndef GRNXX_TABLE_HPP
+#define GRNXX_TABLE_HPP
+
+#include "grnxx/datum.hpp"
+
+namespace grnxx {
+
+class Table {
+ public:
+  // テーブルを初期化する．
+  Table(Database *database, TableID id, const String &name);
+  // テーブルを破棄する．
+  ~Table();
+
+  // コピーと代入を禁止する．
+  Table(const Table &) = delete;
+  Table &operator=(const Table &) = delete;
+
+  // 所属するデータベースを返す．
+  Database *database() const {
+    return database_;
+  }
+  // テーブル ID を返す．
+  TableID id() const {
+    return id_;
+  }
+  // テーブル名を返す．
+  String name() const {
+    return name_;
+  }
+
+  // 指定された名前とデータ型のカラムを作成して返す．
+  // 失敗すると nullptr を返す．
+  Column *create_column(const String &column_name, DataType data_type);
+  // 指定された名前のカラムを破棄する．
+  // 成功すれば true を返し，失敗すれば false を返す．
+  bool drop_column(const String &column_name);
+
+  // カラム ID の最小値を返す．
+  ColumnID min_column_id() const {
+    return MIN_COLUMN_ID;
+  }
+  // カラム ID の最大値を返す．
+  ColumnID max_column_id() const {
+    return columns_.size() - 1;
+  }
+
+  // 指定された ID のカラムを返す．
+  // なければ nullptr を返す．
+  Column *get_column_by_id(ColumnID column_id) const {
+    if (column_id > max_column_id()) {
+      return nullptr;
+    }
+    return columns_[column_id].get();
+  }
+  // 指定された名前のカラムを返す．
+  // なければ nullptr を返す．
+  Column *get_column_by_name(const String &column_name) const;
+
+  // カラムの一覧を columns の末尾に追加し，カラムの数を返す．
+  Int64 get_columns(std::vector<Column *> *columns) const;
+
+  // 指定された名前，対象カラム，種類の索引を作成して返す．
+  // 失敗すると nullptr を返す．
+  Index *create_index(const String &index_name, const String &column_name,
+                      IndexType index_type);
+  // 指定された名前の索引を破棄する．
+  // 成功すれば true を返し，失敗すれば false を返す．
+  bool drop_index(const String &index_name);
+
+  // 索引 ID の最小値を返す．
+  IndexID min_index_id() const {
+    return MIN_INDEX_ID;
+  }
+  // 索引 ID の最大値を返す．
+  IndexID max_index_id() const {
+    return indexes_.size() - 1;
+  }
+  // 指定された ID の索引を返す．
+  // なければ nullptr を返す．
+  Index *get_index_by_id(IndexID index_id) const {
+    if (index_id > max_index_id()) {
+      return nullptr;
+    }
+    return indexes_[index_id].get();
+  }
+  // 指定された名前の索引を返す．
+  // なければ nullptr を返す．
+  Index *get_index_by_name(const String &index_name) const;
+
+  // 索引の一覧を indexes の末尾に追加し，索引の数を返す．
+  Int64 get_indexes(std::vector<Index *> *indexes) const;
+
+  // 行を追加して，その行 ID を返す．
+  RowID insert_row();
+
+  // 行 ID の最小値を返す．
+  RowID min_row_id() const {
+    return MIN_ROW_ID;
+  }
+  // 行 ID の最大値を返す．
+  RowID max_row_id() const {
+    return max_row_id_;
+  }
+
+  // 行 ID を取得するカーソル．
+  class Cursor : public RowIDCursor {
+   public:
+    // 指定されたテーブルの範囲内にある行 ID を取得するようにカーソルを初期化する．
+    Cursor(RowID range_min, RowID range_max);
+
+    // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+    // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+    Int64 get_next(Int64 limit, std::vector<RowID> *row_ids);
+
+   private:
+    RowID row_id_;
+    RowID max_row_id_;
+  };
+
+  // 指定された範囲の行 ID を取得するカーソルを作成して返す．
+  // 範囲が省略された，もしくは 0 を指定されたときは，
+  // 行 ID の最小値・最大値を範囲として使用する．
+  Cursor *create_cursor(RowID range_min = MIN_ROW_ID,
+                        RowID range_max = INT64_MAX) const;
+
+  // 演算器を作成する．
+  Calc *create_calc(const String &query) const;
+  // 整列器を作成する．
+  Sorter *create_sorter(const String &query) const;
+
+  // 整列済みの行一覧を受け取り，グループの境界を求める．
+  bool group_by(const RowID *row_ids, Int64 num_row_ids,
+                const String &comma_separated_column_names,
+                std::vector<Int64> *boundaries);
+
+  // ストリームに書き出す．
+  std::ostream &write_to(std::ostream &stream) const;
+
+  // 行の一覧を文字列化する．
+  std::ostream &write_to(std::ostream &stream,
+                         const RowID *row_ids, Int64 num_row_ids,
+                         const String &comma_separated_column_names);
+  // 行の一覧をグループ毎に文字列化する．
+  std::ostream &write_to(std::ostream &stream,
+                         const RowID *row_ids, Int64 num_row_ids,
+                         const std::vector<Int64> &boundaries,
+                         const String &comma_separated_column_names);
+
+ private:
+  Database *database_;
+  TableID id_;
+  std::string name_;
+  RowID max_row_id_;
+  std::vector<std::unique_ptr<Column>> columns_;
+  std::map<String, ColumnID> columns_map_;
+  std::vector<std::unique_ptr<Index>> indexes_;
+  std::map<String, IndexID> indexes_map_;
+};
+
+std::ostream &operator<<(std::ostream &stream, const Table &table);
+
+}  // namespace grnxx
+
+#endif  // GRNXX_TABLE_HPP

  Added: lib/grnxx/timer.cpp (+32 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/timer.cpp    2014-02-27 18:42:27 +0900 (a4194bf)
@@ -0,0 +1,32 @@
+#include "grnxx/timer.hpp"
+
+#include <time.h>
+
+namespace grnxx {
+namespace {
+
+// 現在の時刻を秒単位で返す．
+double get_current_time() {
+  // CLOCK_MONOTONIC_RAW は使える環境が限られるため，
+  // とりあえずは CLOCK_MONOTONIC を使うことにする．
+  struct timespec current_time;
+  ::clock_gettime(CLOCK_MONOTONIC, &current_time);
+  return current_time.tv_sec + (current_time.tv_nsec * 0.000000001);
+}
+
+}  // namespace
+
+// タイマを初期化する．
+Timer::Timer() : start_time_(get_current_time()) {}
+
+// タイマが初期化されてからの経過時間を秒単位で返す．
+double Timer::elapsed() const {
+  return get_current_time() - start_time_;
+}
+
+// タイマを初期化する．
+void Timer::reset() {
+  start_time_ = get_current_time();
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/timer.hpp (+24 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/timer.hpp    2014-02-27 18:42:27 +0900 (4927889)
@@ -0,0 +1,24 @@
+#ifndef GRNXX_TIMER_HPP
+#define GRNXX_TIMER_HPP
+
+namespace grnxx {
+
+// FIXME: 将来的にはマイクロ秒単位を標準にする．
+class Timer {
+ public:
+  // タイマを初期化する．
+  Timer();
+
+  // タイマが初期化されてからの経過時間を秒単位で返す．
+  double elapsed() const;
+
+  // タイマを初期化する．
+  void reset();
+
+ private:
+  double start_time_;
+};
+
+}  // namespace grnxx
+
+#endif  // GRNXX_TIMER_HPP

  Added: lib/grnxx/types.cpp (+34 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/types.cpp    2014-02-27 18:42:27 +0900 (915186b)
@@ -0,0 +1,34 @@
+#include "grnxx/types.hpp"
+
+#include <ostream>
+
+namespace grnxx {
+
+std::ostream &operator<<(std::ostream &stream, DataType data_type) {
+  switch (data_type) {
+    case BOOLEAN: {
+      return stream << "BOOLEAN";
+    }
+    case INTEGER: {
+      return stream << "INTEGER";
+    }
+    case FLOAT: {
+      return stream << "FLOAT";
+    }
+    case STRING: {
+      return stream << "STRING";
+    }
+  }
+  return stream << "N/A";
+}
+
+std::ostream &operator<<(std::ostream &stream, IndexType index_type) {
+  switch (index_type) {
+    case TREE_MAP: {
+      return stream << "TREE_MAP";
+    }
+  }
+  return stream << "N/A";
+}
+
+}  // namespace grnxx

  Added: lib/grnxx/types.hpp (+111 -0) 100644
===================================================================
--- /dev/null
+++ lib/grnxx/types.hpp    2014-02-27 18:42:27 +0900 (3fd02d1)
@@ -0,0 +1,111 @@
+#ifndef GRNXX_TYPES_HPP
+#define GRNXX_TYPES_HPP
+
+#include <algorithm>
+#include <cstdint>
+#include <cstring>
+#include <functional>
+#include <iosfwd>
+#include <map>
+#include <memory>
+#include <set>
+#include <string>
+#include <vector>
+
+namespace grnxx {
+
+// 真偽値．
+using Boolean = bool;
+
+// 符号付き整数．
+using Int8    = std::int8_t;
+using Int16   = std::int16_t;
+using Int32   = std::int32_t;
+using Int64   = std::int64_t;
+
+// 符号なし整数．
+using UInt8   = std::uint8_t;
+using UInt16  = std::uint16_t;
+using UInt32  = std::uint32_t;
+using UInt64  = std::uint64_t;
+
+// 浮動小数点数．
+using Float   = double;
+
+// 文字列．
+class String;
+
+// 前方宣言．
+class Database;
+class Table;
+class Column;
+class Index;
+class Calc;
+class Sorter;
+
+// 各種 ID．
+using TableID  = Int64;
+using ColumnID = Int64;
+using IndexID  = Int64;
+using RowID    = Int64;
+
+// 各種 ID の最小値．
+constexpr TableID  MIN_TABLE_ID  = 1;
+constexpr ColumnID MIN_COLUMN_ID = 1;
+constexpr IndexID  MIN_INDEX_ID  = 1;
+constexpr RowID    MIN_ROW_ID    = 1;
+
+// 行 ID を取得するカーソルのインタフェース．
+class RowIDCursor {
+ public:
+  // カーソルを初期化する．
+  explicit RowIDCursor() {}
+  // カーソルを破棄する．
+  virtual ~RowIDCursor() {}
+
+  // 行 ID を最大 limit 個取得して row_ids の末尾に追加し，取得した行 ID の数を返す．
+  // 取得できる行 ID が尽きたときは limit より小さい値を返す．
+  virtual Int64 get_next(Int64 limit, std::vector<RowID> *row_ids) = 0;
+};
+
+// データ型の種類．
+enum DataType {
+  BOOLEAN,  // 真偽値．
+  INTEGER,  // 整数．
+  FLOAT,    // 浮動小数点数．
+  STRING    // 文字列．
+};
+
+// データ型の情報．
+template <typename T> struct TypeTraits;
+template <> struct TypeTraits<Boolean> {
+  static DataType data_type() {
+    return BOOLEAN;
+  }
+};
+template <> struct TypeTraits<Int64> {
+  static DataType data_type() {
+    return INTEGER;
+  }
+};
+template <> struct TypeTraits<Float> {
+  static DataType data_type() {
+    return FLOAT;
+  }
+};
+template <> struct TypeTraits<String> {
+  static DataType data_type() {
+    return STRING;
+  }
+};
+
+// 索引の種類．
+enum IndexType {
+  TREE_MAP
+};
+
+std::ostream &operator<<(std::ostream &stream, IndexType index_type);
+
+}  // namespace grnxx
+
+#endif  // GRNXX_TYPES_HPP

  Modified: src/grnxx.cpp (+914 -10)
===================================================================
--- src/grnxx.cpp    2014-02-24 16:02:00 +0900 (05efe1c)
+++ src/grnxx.cpp    2014-02-27 18:42:27 +0900 (b9ca125)
@@ -1,48 +1,952 @@
 #include <getopt.h>
+#include <unistd.h>
 
+#include <cctype>
 #include <iostream>
+#include <sstream>
 
+#include "grnxx/calc.hpp"
+#include "grnxx/column.hpp"
+#include "grnxx/database.hpp"
+#include "grnxx/index.hpp"
 #include "grnxx/library.hpp"
+#include "grnxx/sorter.hpp"
+#include "grnxx/table.hpp"
+#include "grnxx/timer.hpp"
 
 namespace {
 
+bool verbose_mode = false;
+
+// 入力された行をコマンドと引数に切り分ける．
+bool extract_command(const std::string &line,
+                     grnxx::String *command, grnxx::String *params) {
+  // 先頭の空白をスキップする．
+  std::size_t begin = line.find_first_not_of(" \t\n");
+  if ((begin == line.npos) || (line[begin] == '#')) {
+    // 空行および'#'で始まる行（コメント）は無視する．
+    return false;
+  }
+  // 次の空白までをコマンドとして抜き出す．
+  std::size_t end = line.find_first_of(" \t\n", begin);
+  if (end == line.npos) {
+    end = line.size();
+  }
+  *command = grnxx::String(line.data() + begin, end - begin);
+  // コマンドの後ろにある空白をスキップする．
+  begin = line.find_first_not_of(" \t\n", end);
+  if (begin == line.npos) {
+    begin = line.size();
+  }
+  end = line.find_last_not_of(" \t\n");
+  if (end == line.npos) {
+    end = line.size();
+  }
+  *params = grnxx::String(line.data() + begin, end - begin + 1);
+  return true;
+}
+
+// table_create コマンド．
+bool run_table_create(grnxx::Database *database,
+                      const grnxx::String &params) {
+  auto delim_pos = params.find_first_of(" \t\n");
+  if (delim_pos == params.npos) {
+    delim_pos = params.size();
+  }
+  grnxx::String table_name = params.prefix(delim_pos);
+  if (!database->create_table(table_name)) {
+    std::cerr << "Error: grnxx::Database::create_table() failed: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// table_remove コマンド．
+bool run_table_remove(grnxx::Database *database,
+                      const grnxx::String &params) {
+  auto delim_pos = params.find_first_of(" \t\n");
+  if (delim_pos == params.npos) {
+    delim_pos = params.size();
+  }
+  grnxx::String table_name = params.prefix(delim_pos);
+  if (!database->drop_table(table_name)) {
+    std::cerr << "Error: grnxx::Database::drop_table() failed: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// table_list コマンド．
+bool run_table_list(grnxx::Database *database,
+                    const grnxx::String &params) {
+  std::vector<grnxx::Table *> tables;
+  database->get_tables(&tables);
+  for (auto table : tables) {
+    std::cout << "id = " << table->id()
+              << ", name = " << table->name() << '\n';
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// column_create コマンド．
+bool run_column_create(grnxx::Database *database,
+                       const grnxx::String &params) {
+  auto end = params.find_first_of(" \t\n");
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String table_name = params.prefix(end);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  auto begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String column_name = params.extract(begin, end - begin);
+  begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    end = params.size();
+  }
+  grnxx::String data_type_name = params.extract(begin, end - begin);
+  grnxx::DataType data_type;
+  if (data_type_name == "BOOLEAN") {
+    data_type = grnxx::BOOLEAN;
+  } else if ((data_type_name == "INT8") ||
+             (data_type_name == "INT16") ||
+             (data_type_name == "INT32") ||
+             (data_type_name == "INT64")) {
+    data_type = grnxx::INTEGER;
+  } else if (data_type_name == "FLOAT") {
+    data_type = grnxx::FLOAT;
+  } else if (data_type_name == "STRING") {
+    data_type = grnxx::STRING;
+  } else {
+    std::cerr << "Error: Unknown data type: "
+              << "data_type = " << data_type_name << std::endl;
+    return false;
+  }
+  if (!table->create_column(column_name, data_type)) {
+    std::cerr << "Error: grnxx::Table::create_column() failed: "
+              << "table_name = \"" << table_name << '"'
+              << ", column_name = \"" << column_name << '"'
+              << ", data_type = " << data_type << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// column_remove コマンド．
+bool run_column_remove(grnxx::Database *database,
+                       const grnxx::String &params) {
+  auto end = params.find_first_of(" \t\n");
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String table_name = params.prefix(end);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  auto begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    end = params.size();
+  }
+  grnxx::String column_name = params.extract(begin, end - begin);
+  if (!table->drop_column(column_name)) {
+    std::cerr << "Error: grnxx::Table::drop_column() failed: "
+              << "table_name = " << table_name
+              << ", column_name = " << column_name << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// column_list コマンド．
+bool run_column_list(grnxx::Database *database,
+                     const grnxx::String &params) {
+  auto delim_pos = params.find_first_of(" \t\n");
+  if (delim_pos == params.npos) {
+    delim_pos = params.size();
+  }
+  grnxx::String table_name = params.prefix(delim_pos);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: table_name = "
+              << table_name << std::endl;
+    return false;
+  }
+  std::vector<grnxx::Column *> columns;
+  table->get_columns(&columns);
+  for (auto column : columns) {
+    std::cout << "id = " << column->id()
+              << ", name = \"" << column->name() << '"'
+              << ", type = " << column->data_type() << '\n';
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// index_create コマンド．
+bool run_index_create(grnxx::Database *database,
+                       const grnxx::String &params) {
+  auto end = params.find_first_of(" \t\n");
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String table_name = params.prefix(end);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  auto begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String index_name = params.extract(begin, end - begin);
+  begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    end = params.size();
+  }
+  grnxx::String column_name = params.extract(begin, end - begin);
+  if (end == params.size()) {
+    begin = end;
+  } else {
+    begin = params.find_first_not_of(" \t\n", end);
+    end = params.find_first_of(" \t\n", begin);
+    if (end == params.npos) {
+      end = params.size();
+    }
+  }
+  grnxx::String index_type_name = params.extract(begin, end - begin);
+  grnxx::IndexType index_type = grnxx::TREE_MAP;
+  if (index_type_name.empty()) {
+    index_type = grnxx::TREE_MAP;
+  } else if (index_type_name == "TREE_MAP") {
+    index_type = grnxx::TREE_MAP;
+  } else {
+    std::cerr << "Error: Unknown index type: "
+              << "index_type = " << index_type_name << std::endl;
+    return false;
+  }
+  if (!table->create_index(index_name, column_name, index_type)) {
+    std::cerr << "Error: grnxx::Table::create_index() failed: "
+              << "table_name = " << table_name
+              << ", index_name = " << index_name
+              << ", column_name = " << column_name
+              << ", index_type = " << index_type << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// index_remove コマンド．
+bool run_index_remove(grnxx::Database *database,
+                      const grnxx::String &params) {
+  auto end = params.find_first_of(" \t\n");
+  if (end == params.npos) {
+    std::cerr << "Error: too few arguments" << std::endl;
+    return false;
+  }
+  grnxx::String table_name = params.prefix(end);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: "
+              << "table_name = " << table_name << std::endl;
+    return false;
+  }
+  auto begin = params.find_first_not_of(" \t\n", end);
+  end = params.find_first_of(" \t\n", begin);
+  if (end == params.npos) {
+    end = params.size();
+  }
+  grnxx::String index_name = params.extract(begin, end - begin);
+  if (!table->drop_index(index_name)) {
+    std::cerr << "Error: grnxx::Table::drop_index() failed: "
+              << "table_name = " << table_name
+              << ", index_name = " << index_name << std::endl;
+    return false;
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// index_list コマンド．
+bool run_index_list(grnxx::Database *database,
+                    const grnxx::String &params) {
+  auto delim_pos = params.find_first_of(" \t\n");
+  if (delim_pos == params.npos) {
+    delim_pos = params.size();
+  }
+  grnxx::String table_name = params.prefix(delim_pos);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: table_name = "
+              << table_name << std::endl;
+    return false;
+  }
+  std::vector<grnxx::Index *> indexes;
+  table->get_indexes(&indexes);
+  for (auto index : indexes) {
+    std::cout << "id = " << index->id()
+              << ", name = \"" << index->name() << '"'
+              << ", column = \"" << index->column()->name() << '"'
+              << ", type = " << index->type() << '\n';
+  }
+  std::cout << "OK\n";
+  return true;
+}
+
+// load コマンド．
+bool run_load(grnxx::Database *database,
+              const grnxx::String &params) {
+  auto end = params.find_first_of(" \t\n");
+  if (end == params.npos) {
+    end = params.size();
+  }
+  grnxx::String table_name = params.prefix(end);
+  auto table = database->get_table_by_name(table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: table_name = "
+              << table_name << std::endl;
+    return false;
+  }
+  auto begin = params.find_first_not_of(" \t\n", end);
+  if (begin == params.npos) {
+    // 入力がひとつもない．
+    std::cout << "OK: 0 rows\n";
+    return true;
+  }
+  grnxx::Int64 count = 0;
+  grnxx::Datum datum;
+  do {
+    ++count;
+    grnxx::RowID row_id = table->insert_row();
+    if (!row_id) {
+      std::cerr << "Error: Table::add_row() failed" << std::endl;
+      return false;
+    }
+    for (grnxx::ColumnID column_id = table->min_column_id();
+         column_id <= table->max_column_id(); ++column_id) {
+      auto column = table->get_column_by_id(column_id);
+      if (!column) {
+        continue;
+      }
+      if (params[begin] == '"') {
+        // 文字列．
+        end = params.find_first_of('"', ++begin);
+        if (end == params.npos) {
+          end = params.size();
+        }
+        datum = params.extract(begin, end - begin);
+        if (end != params.size()) {
+          ++end;
+        }
+      } else {
+        // そのほか．
+        end = params.find_first_of(" \t\n", begin);
+        if (end == params.npos) {
+          end = params.size();
+        }
+        datum = params.extract(begin, end - begin);
+      }
+      column->generic_set(table->max_row_id(), datum);
+      begin = params.find_first_not_of(" \t\n", end);
+      if (begin == params.npos) {
+        break;
+      }
+    }
+  } while (begin != params.npos);
+  std::cout << "OK: " << count << " rows\n";
+  return true;
+}
+
+struct SelectQuery {
+  grnxx::String table_name;
+  grnxx::String output_column_names;
+  grnxx::String index_query;
+  grnxx::String calc_query;
+  grnxx::Int64 offset;
+  grnxx::Int64 limit;
+  grnxx::String column_names_for_sort_by;
+  grnxx::String column_names_for_group_by;
+};
+
+bool parse_select_params(grnxx::String params, SelectQuery *query) {
+  // テーブルの名前を切り出す．
+  auto boundary = params.find_first_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  query->table_name = params.prefix(boundary);
+  params = params.except_prefix(boundary);
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // 出力カラム名を切り出す．
+  boundary = params.find_first_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  query->output_column_names = params.prefix(boundary);
+  params = params.except_prefix(boundary);
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // 索引を使うクエリを切り出す．
+  query->index_query = "";
+  if (!params.empty() && (params[0] == '`')) {
+    boundary = params.find_first_of('`', 1);
+    if (boundary == params.npos) {
+      std::cerr << "Error: closing back quote does not exist" << std::endl;
+      return false;
+    }
+    query->index_query = params.extract(1, boundary - 1);
+    params = params.except_prefix(boundary + 1);
+  }
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // フィルタのクエリを切り出す．
+  query->calc_query = "";
+  if (!params.empty() && (params[0] == '\'')) {
+    boundary = params.find_first_of('\'', 1);
+    if (boundary == params.npos) {
+      std::cerr << "Error: closing single quote does not exist" << std::endl;
+      return false;
+    }
+    query->calc_query = params.extract(1, boundary - 1);
+    params = params.except_prefix(boundary + 1);
+  }
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // オフセットを切り出す．
+  query->offset = 0;
+  if (!params.empty() && std::isdigit(params[0])) {
+    boundary = params.find_first_of(" \t\n");
+    if (boundary == params.npos) {
+      boundary = params.size();
+    }
+    query->offset = std::strtol(reinterpret_cast<const char *>(params.data()),
+                                nullptr, 10);
+    params = params.except_prefix(boundary);
+  }
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // 上限数を切り出す．
+  query->limit = INT64_MAX;
+  if (!params.empty() && std::isdigit(params[0])) {
+    boundary = params.find_first_of(" \t\n");
+    if (boundary == params.npos) {
+      boundary = params.size();
+    }
+    query->limit = std::strtol(reinterpret_cast<const char *>(params.data()),
+                               nullptr, 10);
+    params = params.except_prefix(boundary);
+  }
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // 整列条件を切り出す．
+  boundary = params.find_first_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  query->column_names_for_sort_by = params.prefix(boundary);
+  params = params.except_prefix(boundary);
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  // グループ化の条件を切り出す．
+  boundary = params.find_first_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  query->column_names_for_group_by = params.prefix(boundary);
+  params = params.except_prefix(boundary);
+  boundary = params.find_first_not_of(" \t\n");
+  if (boundary == params.npos) {
+    boundary = params.size();
+  }
+  params = params.except_prefix(boundary);
+
+  if (verbose_mode) {
+    std::cout << "table_name = " << query->table_name << '\n'
+              << "output = " << query->output_column_names << '\n'
+              << "index_query = " << query->index_query << '\n'
+              << "calc_query = " << query->calc_query << '\n'
+              << "offset = " << query->offset << '\n'
+              << "limit = " << query->limit << '\n'
+              << "sort_by = " << query->column_names_for_sort_by << '\n'
+              << "group_by = " << query->column_names_for_group_by << '\n';
+  }
+
+  return true;
+}
+
+grnxx::RowIDCursor *create_index_cursor(grnxx::Table *table,
+                                        grnxx::String query) {
+  // 索引の名前を切り出す．
+  auto boundary = query.find_first_of(" \t\n");
+  if (boundary == query.npos) {
+    boundary = query.size();
+  }
+  grnxx::String index_name = query.prefix(boundary);
+  bool reverse_order = false;
+  if (index_name.starts_with("-")) {
+    index_name = index_name.except_prefix(1);
+    reverse_order = true;
+  }
+  grnxx::Index *index = table->get_index_by_name(index_name);
+  if (!index) {
+    std::cerr << "Error: index not found: index_name = "
+              << index_name << std::endl;
+    return nullptr;
+  }
+  query = query.except_prefix(boundary);
+  boundary = query.find_first_not_of(" \t\n");
+  if (boundary == query.npos) {
+    boundary = query.size();
+  }
+  query = query.except_prefix(boundary);
+
+  // 特に指示がなければすべての行を取得できるカーソルを作成する．
+  if (query.empty()) {
+    return index->find_all(reverse_order);
+  }
+
+  // 指定された範囲に対応するカーソルを作成する．
+  if (!query.empty() && ((query[0] == '[') || (query[0] == '('))) {
+    // 角括弧なら「以上」と「以下」で，丸括弧なら「より大きい」と「より小さい」になる．
+    grnxx::UInt8 last_byte = query[query.size() - 1];
+    if ((last_byte != ']') && (last_byte != ')')) {
+      std::cerr << "Error: closing bracket not found" << std::endl;
+      return nullptr;
+    }
+    bool greater_equal = (query[0] == '[');
+    bool less_equal = (last_byte == ']');
+    query = query.trim(1, 1);
+
+    // 括弧内両端の空白を取り除く．
+    boundary = query.find_first_not_of(" \t\n");
+    if (boundary == query.npos) {
+      std::cerr << "Error: empty brackets" << std::endl;
+      return nullptr;
+    }
+    query = query.except_prefix(boundary);
+    query = query.prefix(query.find_last_not_of(" \t\n") + 1);
+
+    // 一つ目の値を切り出す．
+    bool has_begin = false;
+    grnxx::Datum begin;
+    if (query[0] == '"') {
+      boundary = query.find_first_of('"', 1);
+      if (boundary == query.npos) {
+        std::cerr << "Error: closing double quote not found" << std::endl;
+        return nullptr;
+      }
+      has_begin = true;
+      begin = query.extract(1, boundary - 1);
+      query = query.except_prefix(boundary + 1);
+    } else {
+      boundary = query.find_first_of(" \t\n,");
+      if (boundary == query.npos) {
+        std::cerr << "Error: delimiter not found" << std::endl;
+        return nullptr;
+      } else if (boundary != 0) {
+        has_begin = true;
+        begin = query.prefix(boundary);
+        query = query.except_prefix(boundary);
+      }
+    }
+
+    // 空白，区切り文字，空白の順でスキップする．
+    boundary = query.find_first_not_of(" \t\n");
+    if (boundary == query.npos) {
+      std::cerr << "Error: delimiter not found" << std::endl;
+      return nullptr;
+    }
+    query = query.except_prefix(boundary);
+    if (query[0] != ',') {
+      std::cerr << "Error: delimiter not found" << std::endl;
+      return nullptr;
+    }
+    query = query.except_prefix(1);
+    boundary = query.find_first_not_of(" \t\n");
+    if (boundary == query.npos) {
+      boundary = query.size();
+    }
+    query = query.except_prefix(boundary);
+
+    // 二つ目の値を切り出す．
+    bool has_end = false;
+    grnxx::Datum end;
+    if (query[0] == '"') {
+      boundary = query.find_first_of('"', 1);
+      if (boundary == query.npos) {
+        std::cerr << "Error: closing double quote not found" << std::endl;
+        return nullptr;
+      }
+      has_end = true;
+      end = query.extract(1, boundary - 1);
+      query = query.except_prefix(boundary + 1);
+    } else {
+      boundary = query.find_first_of(" \t\n");
+      if (boundary == query.npos) {
+        boundary = query.size();
+      }
+      if (boundary != 0) {
+        has_end = true;
+        end = query.prefix(boundary);
+        query = query.except_prefix(boundary);
+      }
+    }
+
+    if (!query.empty()) {
+      std::cerr << "Error: invalid format" << std::endl;
+      return nullptr;
+    }
+
+    if (verbose_mode) {
+      std::cout << "index_name = " << index_name << '\n'
+                << "begin = " << (has_begin ? begin : "N/A") << '\n'
+                << "end = " << (has_end ? end : "N/A") << '\n'
+                << "greater_equal = " << greater_equal << '\n'
+                << "less_equal = " << less_equal << '\n';
+    }
+
+    if (has_begin) {
+      if (has_end) {
+        return index->find_between(begin, end, greater_equal, less_equal,
+                                   reverse_order);
+      } else {
+        return index->find_greater(begin, greater_equal, reverse_order);
+      }
+    } else if (has_end) {
+        return index->find_less(end, less_equal, reverse_order);
+    } else {
+      return index->find_all(reverse_order);
+    }
+    return nullptr;
+  }
+
+  // 指定された値に対応するカーソルを作成する．
+  grnxx::Datum datum;
+  if (query[0] == '"') {
+    boundary = query.find_first_of('"', 1);
+    if (boundary == query.npos) {
+      std::cerr << "Error: closing double quote not found" << std::endl;
+      return nullptr;
+    }
+    datum = query.extract(1, boundary - 1);
+    query = query.except_prefix(boundary + 1);
+  } else {
+    datum = query;
+  }
+
+  if (verbose_mode) {
+    std::cout << "index_name = " << index_name << '\n'
+              << "datum = " << datum << '\n';
+  }
+
+  return index->find_equal(datum);
+}
+
+// select コマンド．
+bool run_select(grnxx::Database *database, const grnxx::String &params,
+                std::ostream &stream) {
+  // 引数を解釈する．
+  SelectQuery query;
+  if (!parse_select_params(params, &query)) {
+    return false;
+  }
+
+  // 指定されたテーブルを探す．
+  grnxx::Table *table = database->get_table_by_name(query.table_name);
+  if (!table) {
+    std::cerr << "Error: table not found: table_name = "
+              << query.table_name << std::endl;
+    return false;
+  }
+
+  // 行 ID の一覧を取得するためのカーソルを用意する．
+  std::unique_ptr<grnxx::RowIDCursor> cursor;
+  if (query.index_query.empty()) {
+    // テーブル由来のカーソルを使う．
+    cursor.reset(table->create_cursor());
+    if (!cursor) {
+      std::cerr << "Error: Table::create_cursor failed" << std::endl;
+      return false;
+    }
+  } else {
+    // 索引由来のカーソルを使う．
+    cursor.reset(create_index_cursor(table, query.index_query));
+    if (!cursor) {
+      return false;
+    }
+  }
+
+  // 絞り込みに用いるフィルタを用意する．
+  std::unique_ptr<grnxx::Calc> calc(table->create_calc(query.calc_query));
+  if (!calc) {
+    std::cerr << "Error: Table::create_calc() failed: query = "
+              << query.calc_query << std::endl;
+    return false;
+  }
+
+  // 検索をおこなう．
+  constexpr grnxx::Int64 BLOCK_SIZE = 1024;
+  grnxx::Int64 num_filtered_rows = 0;
+  std::vector<grnxx::RowID> row_ids;
+  if (query.column_names_for_sort_by.empty()) {
+    // 整列条件がなければ offset, limit を考慮する．
+    if (calc->empty()) {
+      // 検索条件がなければ，先頭の offset 件をスキップした後，
+      // limit 件を取り出して終了する．
+      cursor->get_next(query.offset, nullptr);
+      cursor->get_next(query.limit, &row_ids);
+    } else {
+      // 検索条件があればブロック単位でフィルタにかける．
+      grnxx::Int64 num_rows = 0;
+      grnxx::Int64 offset_left = query.offset;
+      grnxx::Int64 num_new_rows;
+      while ((num_new_rows = cursor->get_next(BLOCK_SIZE, &row_ids)) != 0) {
+        num_filtered_rows += num_new_rows;
+        num_new_rows = calc->filter(&row_ids[num_rows], num_new_rows);
+        if (offset_left != 0) {
+          if (num_new_rows > offset_left) {
+            for (grnxx::Int64 i = 0; i < (num_new_rows - offset_left); ++i) {
+              row_ids[i] = row_ids[offset_left + i];
+            }
+            num_new_rows -= offset_left;
+            offset_left = 0;
+          } else {
+            offset_left -= num_new_rows;
+            num_new_rows = 0;
+          }
+        }
+        num_rows += num_new_rows;
+        if (num_rows >= query.limit) {
+          row_ids.resize(query.limit);
+          break;
+        }
+        row_ids.resize(num_rows);
+      }
+    }
+  } else {
+    // 整列条件が指定されているときは，後で offset, limit を適用する．
+    grnxx::Int64 num_rows = 0;
+    grnxx::Int64 num_new_rows;
+    while ((num_new_rows = cursor->get_next(BLOCK_SIZE, &row_ids)) != 0) {
+      num_filtered_rows += num_new_rows;
+      num_new_rows = calc->filter(&row_ids[num_rows], num_new_rows);
+      num_rows += num_new_rows;
+      row_ids.resize(num_rows);
+    }
+  }
+
+  if (verbose_mode) {
+    std::cout << "num_filtered_rows = " << num_filtered_rows << '\n';
+  }
+
+  // 整列をおこなう．
+  if (!query.column_names_for_sort_by.empty()) {
+    std::unique_ptr<grnxx::Sorter> sorter(
+        table->create_sorter(query.column_names_for_sort_by));
+    if (!sorter) {
+      std::cerr << "Error: Table::create_sorter() failed: query = "
+                << query.column_names_for_sort_by << std::endl;
+      return false;
+    }
+    sorter->sort(&*row_ids.begin(), row_ids.size(), query.offset, query.limit);
+    if (query.offset >= row_ids.size()) {
+      // 先頭の offset 個を取り除くと空になる．
+      row_ids.clear();
+    } else if (query.offset > 0) {
+      // 先頭の offset 個を取り除く．
+      grnxx::Int64 num_rows = row_ids.size() - query.offset;
+      if (num_rows > query.limit) {
+        num_rows = query.limit;
+      }
+      for (grnxx::Int64 i = 0; i < num_rows; ++i) {
+        row_ids[i] = row_ids[query.offset + i];
+      }
+      row_ids.resize(num_rows);
+    } else if (query.limit < row_ids.size()) {
+      // 先頭の limit 個までを残す．
+      row_ids.resize(query.limit);
+    }
+  }
+
+  // グループ化をおこなう．
+  std::vector<grnxx::Int64> boundaries;
+  if (!query.column_names_for_group_by.empty()) {
+    if (!table->group_by(&*row_ids.begin(), row_ids.size(),
+                         query.column_names_for_group_by, &boundaries)) {
+      std::cerr << "Error: Table::group_by() failed: column_names = "
+                << query.column_names_for_group_by << std::endl;
+      return false;
+    }
+  }
+
+  // 結果を出力する．
+  table->write_to(stream << "result = ", &*row_ids.begin(), row_ids.size(),
+                  query.output_column_names) << '\n';
+  if (!boundaries.empty()) {
+    table->write_to(stream, &*row_ids.begin(), row_ids.size(),
+                    boundaries, query.output_column_names) << '\n';
+  }
+  std::cout << "OK: " << row_ids.size() << " rows\n";
+
+  return false;
+}
+
+// 対話モード．
+void run_terminal() {
+  grnxx::Database database;
+  std::string line;
+  grnxx::String command;
+  grnxx::String params;
+  while (std::getline(std::cin, line)) {
+    if (extract_command(line, &command, &params)) {
+      if (verbose_mode) {
+        std::cout << "command = " << command
+                  << ", params = " << params << '\n';
+      }
+      if (command == "table_create") {
+        run_table_create(&database, params);
+      } else if (command == "table_remove") {
+        run_table_remove(&database, params);
+      } else if (command == "table_list") {
+        run_table_list(&database, params);
+      } else if (command == "column_create") {
+        run_column_create(&database, params);
+      } else if (command == "column_remove") {
+        run_column_remove(&database, params);
+      } else if (command == "column_list") {
+        run_column_list(&database, params);
+      } else if (command == "index_create") {
+        run_index_create(&database, params);
+      } else if (command == "index_remove") {
+        run_index_remove(&database, params);
+      } else if (command == "index_list") {
+        run_index_list(&database, params);
+      } else if (command == "load") {
+        run_load(&database, params);
+      } else if (command == "select") {
+        grnxx::Timer timer;
+        run_select(&database, params, std::cout);
+        std::cerr << "select: " << timer.elapsed()
+                  << " [s] elapsed" << std::endl;
+      } else if (command == "count") {
+        grnxx::Timer timer;
+        std::stringstream stream;
+        run_select(&database, params, stream);
+        std::cerr << "count: " << timer.elapsed()
+                  << " [s] elapsed" << std::endl;
+      } else if (command == "quit") {
+        break;
+      } else {
+        std::cerr << "Error: unknown command: "
+                  << "command= " << command << std::endl;
+      }
+    }
+  }
+}
+
 void print_version() {
   std::cout << grnxx::Library::name() << ' '
             << grnxx::Library::version() << std::endl;
 }
 
-void print_usage() {
-  std::cout << "Usage: grnxx [options...]\n\n"
+void print_usage(int argc, char *argv[]) {
+  std::cout << "Usage: " << argv[0] << " [OPTION]...\n\n"
                "Options:\n"
-               "  -h, --help:     show this help\n"
-               "  -v, --version:  show grnxx version"
-            << std::endl;
+               "  -v, --verbose:  enable verbose mode\n"
+               "  -h, --help:     print this help\n"
+               "  -V, --version:  print grnxx version\n"
+            << std::flush;
 }
 
 }  // namespace
 
 int main(int argc, char *argv[]) {
   const struct option long_options[] = {
+    { "verbose", 0, nullptr, 'v' },
     { "help", 0, nullptr, 'h' },
-    { "version", 0, nullptr, 'v' },
+    { "version", 0, nullptr, 'V' },
     { nullptr, 0, nullptr, 0 }
   };
   int value;
-  while ((value = ::getopt_long(argc, argv, "hv",
+  while ((value = ::getopt_long(argc, argv, "vhV",
                                 long_options, nullptr)) != -1) {
     switch (value) {
+      case 'v': {
+        verbose_mode = true;
+        break;
+      }
       case 'h': {
-        print_usage();
+        print_usage(argc, argv);
         return 0;
       }
-      case 'v': {
+      case 'V': {
         print_version();
         return 0;
       }
       default: {
-        break;
+        print_usage(argc, argv);
+        return 1;
       }
     }
   }
+  run_terminal();
   return 0;
 }

  Modified: test/test_grnxx.cpp (+955 -0)
===================================================================
--- test/test_grnxx.cpp    2014-02-24 16:02:00 +0900 (f807017)
+++ test/test_grnxx.cpp    2014-02-27 18:42:27 +0900 (83c2bb9)
@@ -18,7 +18,962 @@
 #include <cassert>
 
 #include "grnxx/library.hpp"
+#include <cassert>
+#include <iostream>
+#include <random>
+#include <vector>
+
+#include "grnxx/calc.hpp"
+#include "grnxx/column.hpp"
+#include "grnxx/column_impl.hpp"
+#include "grnxx/database.hpp"
+#include "grnxx/index.hpp"
+#include "grnxx/sorter.hpp"
+#include "grnxx/table.hpp"
+
+namespace {
+
+void test_database() {
+  grnxx::Database database;
+
+  assert(database.min_table_id() == grnxx::MIN_TABLE_ID);
+  assert(database.max_table_id() == (grnxx::MIN_TABLE_ID - 1));
+
+  grnxx::Table *table = database.create_table("Table_1");
+  assert(table);
+
+  grnxx::TableID table_id = table->id();
+  assert(table_id == grnxx::MIN_TABLE_ID);
+  grnxx::String table_name = table->name();
+  assert(table_name == "Table_1");
+
+  table = database.get_table_by_id(table_id);
+  assert(table->id() == table_id);
+  assert(table->name() == table_name);
+
+  table = database.get_table_by_name(table_name);
+  assert(table->id() == table_id);
+  assert(table->name() == table_name);
+
+  assert(!database.create_table("Table_1"));
+
+  assert(database.create_table("Table_2"));
+  assert(database.create_table("Table_3"));
+  assert(database.drop_table("Table_2"));
+
+  std::vector<grnxx::Table *> tables;
+  assert(database.get_tables(&tables) == 2);
+
+  assert(tables[0]->name() == "Table_1");
+  assert(tables[1]->name() == "Table_3");
+
+  assert(database.min_table_id() == tables[0]->id());
+  assert(database.max_table_id() == tables[1]->id());
+}
+
+void test_table() {
+  grnxx::Database database;
+
+  grnxx::Table *table = database.create_table("Table");
+  assert(table);
+
+  assert(table->min_column_id() == grnxx::MIN_COLUMN_ID);
+  assert(table->max_column_id() == (grnxx::MIN_COLUMN_ID - 1));
+
+  grnxx::Column *column = table->create_column("Column_1", grnxx::INTEGER);
+  assert(column);
+
+  grnxx::ColumnID column_id = column->id();
+  assert(column_id == grnxx::MIN_COLUMN_ID);
+  grnxx::String column_name = column->name();
+  assert(column_name == "Column_1");
+
+  column = table->get_column_by_id(column_id);
+  assert(column->id() == column_id);
+  assert(column->name() == column_name);
+
+  column = table->get_column_by_name(column_name);
+  assert(column->id() == column_id);
+  assert(column->name() == column_name);
+
+  grnxx::Index *index =
+      table->create_index("Index_1", "Column_1", grnxx::TREE_MAP);
+  assert(index);
+
+  grnxx::IndexID index_id = index->id();
+  assert(index_id == grnxx::MIN_INDEX_ID);
+  grnxx::String index_name = index->name();
+  assert(index_name == "Index_1");
+
+  index = table->get_index_by_id(index_id);
+  assert(index->id() == index_id);
+  assert(index->name() == index_name);
+
+  index = table->get_index_by_name(index_name);
+  assert(index->id() == index_id);
+  assert(index->name() == index_name);
+
+  assert(!table->create_index("Index_1", "Column_1", grnxx::TREE_MAP));
+
+  assert(table->create_column("Column_2", grnxx::FLOAT));
+  assert(table->create_column("Column_3", grnxx::STRING));
+  assert(table->create_index("Index_2", "Column_2", grnxx::TREE_MAP));
+  assert(table->create_index("Index_3", "Column_3", grnxx::TREE_MAP));
+  assert(table->drop_column("Column_2"));
+  assert(table->drop_index("Index_3"));
+
+  std::vector<grnxx::Column *> columns;
+  assert(table->get_columns(&columns) == 2);
+
+  assert(columns[0]->name() == "Column_1");
+  assert(columns[1]->name() == "Column_3");
+
+  assert(table->min_column_id() == columns[0]->id());
+  assert(table->max_column_id() == columns[1]->id());
+
+  std::vector<grnxx::Index *> indexes;
+  assert(table->get_indexes(&indexes) == 1);
+
+  assert(indexes[0]->name() == "Index_1");
+
+  for (grnxx::Int64 i = 0; i < 100; ++i) {
+    assert(table->insert_row() == (grnxx::MIN_ROW_ID + i));
+    assert(table->min_row_id() == grnxx::MIN_ROW_ID);
+    assert(table->max_row_id() == (grnxx::MIN_ROW_ID + i));
+  }
+
+  std::unique_ptr<grnxx::RowIDCursor> cursor(table->create_cursor());
+  assert(cursor);
+
+  std::vector<grnxx::RowID> row_ids;
+  assert(cursor->get_next(10, &row_ids) == 10);
+  assert(cursor->get_next(100, &row_ids) == 90);
+  for (grnxx::Int64 i = 0; i < 100; ++i) {
+    assert(row_ids[i] == (grnxx::MIN_ROW_ID + i));
+  }
+}
+
+void test_column() {
+  grnxx::Database database;
+
+  grnxx::Table *table = database.create_table("Table");
+  assert(table);
+
+  auto boolean_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Boolean> *>(
+      table->create_column("Boolean", grnxx::BOOLEAN));
+  assert(boolean_column);
+  assert(boolean_column->name() == "Boolean");
+  assert(boolean_column->data_type() == grnxx::BOOLEAN);
+
+  auto integer_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Int64> *>(
+      table->create_column("Integer", grnxx::INTEGER));
+  assert(integer_column);
+  assert(integer_column->name() == "Integer");
+  assert(integer_column->data_type() == grnxx::INTEGER);
+
+  auto float_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Float> *>(
+      table->create_column("Float", grnxx::FLOAT));
+  assert(float_column);
+  assert(float_column->name() == "Float");
+  assert(float_column->data_type() == grnxx::FLOAT);
+
+  auto string_column = dynamic_cast<grnxx::ColumnImpl<grnxx::String> *>(
+      table->create_column("String", grnxx::STRING));
+  assert(string_column);
+  assert(string_column->name() == "String");
+  assert(string_column->data_type() == grnxx::STRING);
+
+  for (grnxx::Int64 row_id = grnxx::MIN_ROW_ID; row_id <= 1000; ++row_id) {
+    assert(table->insert_row() == row_id);
+    boolean_column->set(row_id, row_id & 1);
+    integer_column->set(row_id, row_id);
+    float_column->set(row_id, 1.0 / row_id);
+    std::string str = std::to_string(row_id);
+    string_column->set(row_id, str);
+  }
+
+  for (grnxx::Int64 row_id = table->min_row_id();
+       row_id <= table->max_row_id(); ++row_id) {
+    assert(boolean_column->get(row_id) == grnxx::Boolean(row_id & 1));
+    assert(integer_column->get(row_id) == grnxx::Int64(row_id));
+    assert(float_column->get(row_id) == grnxx::Float(1.0 / row_id));
+    std::string str = std::to_string(row_id);
+    assert(string_column->get(row_id) == str);
+  }
+
+  std::vector<grnxx::RowID> row_ids = { 1, 5, 10, 50, 100, 500 };
+  table->write_to(std::cout, &*row_ids.begin(), row_ids.size(),
+                  "_id,Integer,Float,String") << std::endl;
+  table->write_to(std::cout, &*row_ids.begin(), row_ids.size(),
+                  "*") << std::endl;
+
+  std::vector<grnxx::Int64> boundaries = { 2, 4, 6 };
+  table->write_to(std::cout, &*row_ids.begin(), row_ids.size(), boundaries,
+                  "*") << std::endl;
+}
+
+void test_calc() {
+  grnxx::Database database;
+
+  grnxx::Table *table = database.create_table("Table");
+  assert(table);
+
+  auto boolean_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Boolean> *>(
+      table->create_column("Boolean", grnxx::BOOLEAN));
+  assert(boolean_column);
+  auto integer_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Int64> *>(
+      table->create_column("Integer", grnxx::INTEGER));
+  assert(integer_column);
+  auto float_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Float> *>(
+      table->create_column("Float", grnxx::FLOAT));
+  assert(float_column);
+  auto string_column = dynamic_cast<grnxx::ColumnImpl<grnxx::String> *>(
+      table->create_column("String", grnxx::STRING));
+  assert(string_column);
+
+  std::mt19937_64 random;
+  std::vector<grnxx::Boolean> boolean_data;
+  std::vector<grnxx::Int64> integer_data;
+  std::vector<grnxx::Float> float_data;
+  std::vector<std::string> string_data;
+  for (grnxx::Int64 i = 0; i < 1000; ++i) {
+    boolean_data.push_back(random() & 1);
+    integer_data.push_back(random() % 100);
+    float_data.push_back(1.0 * random() / random.max());
+    std::string str(1 + (random() % 10), 'A');
+    for (std::size_t i = 0; i < str.size(); ++i) {
+      str[i] += random() % 26;
+    }
+    string_data.push_back(str);
+  }
+
+  for (grnxx::Int64 i = 0; i < 1000; ++i) {
+    grnxx::RowID row_id = table->insert_row();
+    boolean_column->set(row_id, boolean_data[i]);
+    integer_column->set(row_id, integer_data[i]);
+    float_column->set(row_id, float_data[i]);
+    string_column->set(row_id, string_data[i]);
+  }
+
+  std::vector<grnxx::RowID> all_row_ids;
+  std::unique_ptr<grnxx::RowIDCursor> cursor(table->create_cursor());
+  assert(cursor->get_next(INT64_MAX, &all_row_ids) == 1000);
+
+  // 何もしない．
+  {
+    std::unique_ptr<grnxx::Calc> calc(table->create_calc(""));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids == 1000);
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      assert(row_ids[i] == row_id);
+    }
+  }
+
+  // Boolean で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(table->create_calc("Boolean"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if (boolean_data[i]) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // Integer の範囲で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(table->create_calc("Integer < 50"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if (integer_data[i] < 50) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // Boolean と Integer と Float の範囲で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Boolean && Integer < 50 && Float < 0.5"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if (boolean_data[i] && (integer_data[i] < 50) && (float_data[i] < 0.5)) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // Boolean と Integer と String の範囲で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("(Boolean && Integer >= 50) || (String <= \"A\")"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((boolean_data[i] && (integer_data[i] >= 50)) ||
+          (string_data[i] <= "A")) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // Integer の演算結果で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("(Integer * 2) > 100"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((integer_data[i] * 2) > 100) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // Float の演算結果で絞り込む．
+  {
+    std::unique_ptr<grnxx::Calc> calc(table->create_calc("(Float + 1.0) < 1.5"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((float_data[i] + 1.0) < 1.5) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // ゼロによる除算を起こす．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Integer / Integer != 0"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids == 0);
+  }
+
+  // オーバーフローを起こす．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("9223372036854775807 + 9223372036854775807 != 0"));
+    assert(!calc);
+  }
+
+  // || の左がすべて真になる．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Integer <= 100 || Float < 0.5"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids != 0);
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((integer_data[i] <= 100) || (float_data[i] < 0.5)) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // || の左がすべて偽になる．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Integer < 0 || Float < 0.5"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids != 0);
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((integer_data[i] < 0) || (float_data[i] < 0.5)) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // || の右がすべて真になる．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Integer < 50 || Float >= 0.0"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids != 0);
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((integer_data[i] < 50) || (float_data[i] >= 0.0)) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+
+  // || の右がすべて偽になる．
+  {
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("Integer < 50 || Float < 0.0"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    assert(num_row_ids != 0);
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = grnxx::MIN_ROW_ID + i;
+      if ((integer_data[i] < 50) || (float_data[i] < 0.0)) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+}
+
+void test_sorter() {
+  grnxx::Database database;
+
+  grnxx::Table *table = database.create_table("Table");
+  assert(table);
+
+  auto boolean_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Boolean> *>(
+      table->create_column("Boolean", grnxx::BOOLEAN));
+  assert(boolean_column);
+  auto integer_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Int64> *>(
+      table->create_column("Integer", grnxx::INTEGER));
+  assert(integer_column);
+  auto float_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Float> *>(
+      table->create_column("Float", grnxx::FLOAT));
+  assert(float_column);
+  auto string_column = dynamic_cast<grnxx::ColumnImpl<grnxx::String> *>(
+      table->create_column("String", grnxx::STRING));
+  assert(string_column);
+
+  std::mt19937_64 random;
+  for (grnxx::Int64 i = 0; i < 1000; ++i) {
+    grnxx::RowID row_id = table->insert_row();
+    boolean_column->set(row_id, random() & 1);
+    integer_column->set(row_id, random() % 100);
+    float_column->set(row_id, 1.0 * random() / random.max());
+    std::string str(1 + (random() % 10), 'A');
+    for (std::size_t i = 0; i < str.size(); ++i) {
+      str[i] += random() % 26;
+    }
+    string_column->set(row_id, str);
+  }
+
+  std::vector<grnxx::RowID> all_row_ids;
+  std::unique_ptr<grnxx::RowIDCursor> cursor(table->create_cursor());
+  assert(cursor->get_next(INT64_MAX, &all_row_ids) == 1000);
+
+  // Boolean を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("Boolean"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(boolean_column->get(row_ids[i - 1]) <=
+             boolean_column->get(row_ids[i]));
+    }
+  }
+
+  // Integer を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("Integer"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(integer_column->get(row_ids[i - 1]) <=
+             integer_column->get(row_ids[i]));
+    }
+  }
+
+  // Float を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("Float"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(float_column->get(row_ids[i - 1]) <=
+             float_column->get(row_ids[i]));
+    }
+  }
+
+  // String を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("String"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(string_column->get(row_ids[i - 1]) <=
+             string_column->get(row_ids[i]));
+    }
+  }
+
+  // Boolean を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("-Boolean"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(boolean_column->get(row_ids[i - 1]) >=
+             boolean_column->get(row_ids[i]));
+    }
+  }
+
+  // Integer を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("-Integer"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(integer_column->get(row_ids[i - 1]) >=
+             integer_column->get(row_ids[i]));
+    }
+  }
+
+  // Float を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("-Float"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(float_column->get(row_ids[i - 1]) >=
+             float_column->get(row_ids[i]));
+    }
+  }
+
+  // String を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("-String"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(string_column->get(row_ids[i - 1]) >=
+             string_column->get(row_ids[i]));
+    }
+  }
+
+  // Integer を基準に整列して 100 件目まで取得する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("Integer"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size(), 0, 100);
+    for (grnxx::Int64 i = 1; i < 100; ++i) {
+      assert(integer_column->get(row_ids[i - 1]) <=
+             integer_column->get(row_ids[i]));
+    }
+  }
+
+  // Integer を基準に整列して，先頭の 100 件をスキップしてから 200 件目まで取得する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(table->create_sorter("Integer"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size(), 100, 200);
+    for (grnxx::Int64 i = 101; i < 300; ++i) {
+      assert(integer_column->get(row_ids[i - 1]) <=
+             integer_column->get(row_ids[i]));
+    }
+  }
+
+  // Boolean, Integer, Float を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(
+        table->create_sorter("Boolean,Integer,-Float"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(boolean_column->get(row_ids[i - 1]) <=
+             boolean_column->get(row_ids[i]));
+      if (boolean_column->get(row_ids[i - 1]) ==
+          boolean_column->get(row_ids[i])) {
+        assert(integer_column->get(row_ids[i - 1]) <=
+               integer_column->get(row_ids[i]));
+        if (integer_column->get(row_ids[i - 1]) ==
+            integer_column->get(row_ids[i])) {
+          assert(float_column->get(row_ids[i - 1]) >=
+                 float_column->get(row_ids[i]));
+        }
+      }
+    }
+  }
+
+  // Boolean, Integer, String を基準に整列して 500 件目までを取得する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(
+        table->create_sorter("Boolean,Integer,-String"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size(), 0, 500);
+    for (grnxx::Int64 i = 1; i < 500; ++i) {
+      assert(boolean_column->get(row_ids[i - 1]) <=
+             boolean_column->get(row_ids[i]));
+      if (boolean_column->get(row_ids[i - 1]) ==
+          boolean_column->get(row_ids[i])) {
+        assert(integer_column->get(row_ids[i - 1]) <=
+               integer_column->get(row_ids[i]));
+        if (integer_column->get(row_ids[i - 1]) ==
+            integer_column->get(row_ids[i])) {
+          assert(string_column->get(row_ids[i - 1]) >=
+                 string_column->get(row_ids[i]));
+        }
+      }
+    }
+  }
+
+  // Boolean, Integer, _id を基準に整列する．
+  {
+    std::vector<grnxx::RowID> row_ids(all_row_ids);
+    std::unique_ptr<grnxx::Sorter> sorter(
+        table->create_sorter("Boolean,-Integer,-_id"));
+    assert(sorter);
+    sorter->sort(&*row_ids.begin(), row_ids.size());
+    for (grnxx::Int64 i = 1; i < 1000; ++i) {
+      assert(boolean_column->get(row_ids[i - 1]) <=
+             boolean_column->get(row_ids[i]));
+      if (boolean_column->get(row_ids[i - 1]) ==
+          boolean_column->get(row_ids[i])) {
+        assert(integer_column->get(row_ids[i - 1]) >=
+               integer_column->get(row_ids[i]));
+        if (integer_column->get(row_ids[i - 1]) ==
+            integer_column->get(row_ids[i])) {
+          assert(row_ids[i - 1] > row_ids[i]);
+        }
+      }
+    }
+  }
+}
+
+void test_index() {
+  grnxx::Database database;
+
+  grnxx::Table *table = database.create_table("Table");
+  assert(table);
+
+  auto boolean_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Boolean> *>(
+      table->create_column("Boolean", grnxx::BOOLEAN));
+  assert(boolean_column);
+  auto integer_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Int64> *>(
+      table->create_column("Integer", grnxx::INTEGER));
+  assert(integer_column);
+  auto float_column = dynamic_cast<grnxx::ColumnImpl<grnxx::Float> *>(
+      table->create_column("Float", grnxx::FLOAT));
+  assert(float_column);
+  auto string_column = dynamic_cast<grnxx::ColumnImpl<grnxx::String> *>(
+      table->create_column("String", grnxx::STRING));
+  assert(string_column);
+
+  auto integer_index =
+      table->create_index("Integer", "Integer", grnxx::TREE_MAP);
+  assert(integer_index);
+  auto float_index =
+      table->create_index("Float", "Float", grnxx::TREE_MAP);
+  assert(float_index);
+  auto string_index =
+      table->create_index("String", "String", grnxx::TREE_MAP);
+  assert(string_index);
+
+  std::mt19937_64 random;
+  for (grnxx::Int64 i = 0; i < 1000; ++i) {
+    grnxx::RowID row_id = table->insert_row();
+    boolean_column->set(row_id, random() & 1);
+    integer_column->set(row_id, random() % 100);
+    float_column->set(row_id, 1.0 * random() / random.max());
+    std::string str(1 + (random() % 10), 'A');
+    for (std::size_t i = 0; i < str.size(); ++i) {
+      str[i] += random() % 26;
+    }
+    string_column->set(row_id, str);
+  }
+
+  // Integer 昇順に全件．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(integer_index->find_all());
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) == 1000);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value >= 0);
+    assert(value < 100);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value >= 0);
+      assert(value < 100);
+      assert(value >= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 昇順に 30 より大きく 70 より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        integer_index->find_between(grnxx::Int64(30), grnxx::Int64(70),
+                                    false, false));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value > 30);
+    assert(value < 70);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value > 30);
+      assert(value < 70);
+      assert(value >= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 昇順に 30 以上 70 以下の範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        integer_index->find_between(grnxx::Int64(30), grnxx::Int64(70),
+                                    true, true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value >= 30);
+    assert(value <= 70);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value >= 30);
+      assert(value <= 70);
+      assert(value >= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Float 昇順に 0.3 より大きく 0.7 より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        float_index->find_between(0.3, 0.7));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = float_column->get(row_ids[0]);
+    assert(value > 0.3);
+    assert(value < 0.7);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = float_column->get(row_ids[i]);
+      assert(value > 0.3);
+      assert(value < 0.7);
+      assert(value >= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // String 昇順に "G" より大きく "P" より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        string_index->find_between("G", "P"));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = string_column->get(row_ids[0]);
+    assert(value > "G");
+    assert(value < "P");
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = string_column->get(row_ids[i]);
+      assert(value > "G");
+      assert(value < "P");
+      assert(value >= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 降順に全件．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(integer_index->find_all(true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) == 1000);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value >= 0);
+    assert(value < 100);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value >= 0);
+      assert(value < 100);
+      assert(value <= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 降順に 30 より大きく 70 より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        integer_index->find_between(grnxx::Int64(30), grnxx::Int64(70),
+                                    false, false, true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value > 30);
+    assert(value < 70);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value > 30);
+      assert(value < 70);
+      assert(value <= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 降順に 30 以上 70 以下の範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        integer_index->find_between(grnxx::Int64(30), grnxx::Int64(70),
+                                    true, true, true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = integer_column->get(row_ids[0]);
+    assert(value >= 30);
+    assert(value <= 70);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = integer_column->get(row_ids[i]);
+      assert(value >= 30);
+      assert(value <= 70);
+      assert(value <= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Float 降順に 0.3 より大きく 0.7 より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        float_index->find_between(0.3, 0.7, false, false, true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = float_column->get(row_ids[0]);
+    assert(value > 0.3);
+    assert(value < 0.7);
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = float_column->get(row_ids[i]);
+      assert(value > 0.3);
+      assert(value < 0.7);
+      assert(value <= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // String 降順に "G" より大きく "P" より小さい範囲．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(
+        string_index->find_between("G", "P", false, false, true));
+    assert(cursor);
+    std::vector<grnxx::RowID> row_ids;
+    assert(cursor->get_next(INT64_MAX, &row_ids) > 100);
+    auto value = string_column->get(row_ids[0]);
+    assert(value > "G");
+    assert(value < "P");
+    for (std::size_t i = 1; i < row_ids.size(); ++i) {
+      auto prev_value = value;
+      value = string_column->get(row_ids[i]);
+      assert(value > "G");
+      assert(value < "P");
+      assert(value <= prev_value);
+      prev_value = value;
+    }
+  }
+
+  // Integer 昇順で論理和が使えることを確認する．
+  {
+    std::unique_ptr<grnxx::RowIDCursor> cursor(integer_index->find_all());
+    assert(cursor);
+    std::vector<grnxx::RowID> ordered_row_ids;
+    assert(cursor->get_next(INT64_MAX, &ordered_row_ids) == 1000);
+    std::unique_ptr<grnxx::Calc> calc(
+        table->create_calc("(Boolean && Integer >= 50) || (String <= \"O\")"));
+    assert(calc);
+    std::vector<grnxx::RowID> row_ids(ordered_row_ids);
+    grnxx::Int64 num_row_ids = calc->filter(&*row_ids.begin(), row_ids.size());
+    grnxx::Int64 count = 0;
+    for (grnxx::Int64 i = 0; i < 1000; ++i) {
+      grnxx::RowID row_id = ordered_row_ids[i];
+      if ((boolean_column->get(row_id) &&
+           (integer_column->get(row_id) >= 50)) ||
+          (string_column->get(row_id) <= "O")) {
+        assert(row_ids[count] == row_id);
+        assert(++count <= num_row_ids);
+      }
+    }
+    assert(count == num_row_ids);
+  }
+}
+
+}  // namespace
 
 int main() {
+  test_database();
+  test_table();
+  test_column();
+  test_calc();
+  test_sorter();
+  test_index();
   return 0;
 }

• Previous message: [Groonga-commit] droonga/droonga.org at 207ec0a [gh-pages] ja: Translate
• Next message: [Groonga-commit] droonga/droonga.org at ed23a73 [gh-pages] Add more basic descriptions about the Droonga itself.
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]