susumu.yata
null+****@clear*****
Wed Aug 20 11:21:55 JST 2014
susumu.yata 2014-08-20 11:21:55 +0900 (Wed, 20 Aug 2014) New Revision: b2d0d8ceda5196be3005053579a196c197bef85d https://github.com/groonga/grnxx/commit/b2d0d8ceda5196be3005053579a196c197bef85d Message: Move and rename components of Sorter. Modified files: include/grnxx/sorter.hpp include/grnxx/types.hpp lib/grnxx/sorter.cpp lib/grnxx/types.cpp Modified: include/grnxx/sorter.hpp (+5 -9) =================================================================== --- include/grnxx/sorter.hpp 2014-08-19 17:37:54 +0900 (1cf6acd) +++ include/grnxx/sorter.hpp 2014-08-20 11:21:55 +0900 (6c4b179) @@ -5,17 +5,13 @@ #include "grnxx/types.hpp" namespace grnxx { +namespace sorter { -struct SortOrder { - unique_ptr<Expression> expression; - OrderType type; +class Node; - SortOrder(); - explicit SortOrder(unique_ptr<Expression> &&expression, - OrderType type = REGULAR_ORDER); - SortOrder(SortOrder &&order); - ~SortOrder(); -}; +} // namespace sorter + +using SorterNode = sorter::Node; class Sorter { public: Modified: include/grnxx/types.hpp (+11 -1) =================================================================== --- include/grnxx/types.hpp 2014-08-19 17:37:54 +0900 (896f0ca) +++ include/grnxx/types.hpp 2014-08-20 11:21:55 +0900 (1a013f8) @@ -419,9 +419,19 @@ class Datum; class Cursor; class Expression; class ExpressionBuilder; -class SorterNode; class Sorter; +struct SortOrder { + unique_ptr<Expression> expression; + OrderType type; + + SortOrder(); + explicit SortOrder(unique_ptr<Expression> &&expression, + OrderType type = REGULAR_ORDER); + SortOrder(SortOrder &&order); + ~SortOrder(); +}; + } // namespace grnxx #endif // GRNXX_TYPES_HPP Modified: lib/grnxx/sorter.cpp (+194 -173) =================================================================== --- lib/grnxx/sorter.cpp 2014-08-19 17:37:54 +0900 (0dc8d86) +++ lib/grnxx/sorter.cpp 2014-08-20 11:21:55 +0900 (7c1e791) @@ -6,34 +6,21 @@ #include "grnxx/expression.hpp" namespace grnxx { +namespace sorter { -SortOrder::SortOrder() : expression(), type(REGULAR_ORDER) {} +// -- Node -- -SortOrder::SortOrder(SortOrder &&order) - : expression(std::move(order.expression)), - type(order.type) {} - -SortOrder::SortOrder(unique_ptr<Expression> &&expression, OrderType type) - : expression(std::move(expression)), - type(type) {} - -SortOrder::~SortOrder() {} - -class SorterNode { +class Node { public: - static unique_ptr<SorterNode> create(Error *error, SortOrder &&order); + static unique_ptr<Node> create(Error *error, SortOrder &&order); - SorterNode() : next_(), error_(nullptr) {} - virtual ~SorterNode() {} + explicit Node(SortOrder &&order) : order_(std::move(order)), next_() {} + virtual ~Node() {} // Set the next node. - void set_next(unique_ptr<SorterNode> &&next) { + void set_next(unique_ptr<Node> &&next) { next_ = std::move(next); } - // Set a reference to an error object. - void set_error(Error *error) { - error_ = error; - } // Sort records in [begin, end). // @@ -46,102 +33,170 @@ class SorterNode { Int end) = 0; protected: - unique_ptr<SorterNode> next_; - Error *error_; + SortOrder order_; + unique_ptr<Node> next_; }; -namespace { +// --- TypedNode --- template <typename T> -struct RegularComparer { +class TypedNode : public Node { + public: using Value = T; - bool operator()(Value lhs, Value rhs) const { - return lhs < rhs; - } + + explicit TypedNode(SortOrder &&order) + : Node(std::move(order)), + values_() {} + virtual ~TypedNode() {} + + protected: + Array<Value> values_; }; -template <> -struct RegularComparer<Float> { - using Value = Float; - bool operator()(Value lhs, Value rhs) const { - // Numbers are prior to NaN. - if (std::isnan(lhs)) { - return false; - } else if (std::isnan(rhs)) { - return true; +// ---- SeparatorNode ---- + +template <typename T> +class SeparatorNode : public TypedNode<Bool> { + public: + using IsPrior = T; + + explicit SeparatorNode(SortOrder &&order) + : TypedNode<Bool>(std::move(order)), + is_prior_() {} + ~SeparatorNode() {} + + bool sort(Error *error, ArrayRef<Record> records, Int begin, Int end); + + private: + IsPrior is_prior_; +}; + +template <typename T> +bool SeparatorNode<T>::sort(Error *error, + ArrayRef<Record> records, + Int begin, + Int end) { + if (!order_.expression->evaluate(error, records, &values_)) { + return false; + } + + // Move prior entries to left and others to right. + Int left = 0; + Int right = records.size(); + while (left < right) { + if (is_prior_(values_[left])) { + ++left; + } else { + // Note that values_[left] will not be used again. + --right; + values_.set(left, values_[right]); + records.swap(left, right); } - return lhs < rhs; } -}; -template <> -struct RegularComparer<GeoPoint> { - using Value = GeoPoint; - bool operator()(Value lhs, Value rhs) const { - if (lhs.latitude() != rhs.latitude()) { - return lhs.latitude() < rhs.latitude(); + // Now "left" equals to "right" and it points to the boundary. + // The left group is [0, left) and the right group is [left, records.size()). + if (this->next_) { + // Apply the next sort condition if blocks contain 2 or more records. + if ((left >= 2) && (begin < left)) { + if (!this->next_->sort(error, records.ref(0, left), + begin, (end < left) ? end : left)) { + return false; + } + } + if (((records.size() - left) >= 2) && (end > left)) { + if (begin < left) { + begin = 0; + } else { + begin -= left; + } + end -= left; + if (!this->next_->sort(error, records.ref(left), begin, end)) { + return false; + } } - return lhs.longitude() < rhs.longitude(); + } + + return true; +} + +// ----- RegularIsPrior ----- + +struct RegularIsPrior { + bool operator()(Bool arg) const { + return !arg; } }; -template <typename T> -struct ReverseComparer { - using Value = T; - bool operator()(Value lhs, Value rhs) const { - return RegularComparer<T>()(rhs, lhs); +// ----- ReverseIsPrior ----- + +struct ReverseIsPrior { + bool operator()(Bool arg) const { + return arg; } }; -// -- Node<T> -- +// ---- QuickSortNode ---- template <typename T> -class Node : public SorterNode { +class QuickSortNode : public TypedNode<typename T::Value> { public: - using PriorTo = T; - using Value = typename PriorTo::Value; + using Comparer = T; + using Value = typename Comparer::Value; - explicit Node(SortOrder &&order) - : SorterNode(), - order_(std::move(order)), - values_(), - prior_to_() {} - ~Node() {} + explicit QuickSortNode(SortOrder &&order) + : TypedNode<Value>(std::move(order)), + comparer_() {} + ~QuickSortNode() {} bool sort(Error *error, ArrayRef<Record> records, Int begin, Int end); private: - SortOrder order_; - Array<Value> values_; - PriorTo prior_to_; + Comparer comparer_; // Sort records with ternary quick sort. // // Switches to insertion sort when the sorting range becomes small enough. - bool quick_sort(ArrayRef<Record> records, Value *values, - Int begin, Int end); + // + // On success, returns true. + // On failure, returns false and stores error information into "*error" if + // "error" != nullptr. + bool quick_sort(Error *error, + ArrayRef<Record> records, + Value *values, + Int begin, + Int end); // Sort records with insertion sort. // // Insertion sort should be used when there few records. - bool insertion_sort(ArrayRef<Record> records, Value *values); + // + // On success, returns true. + // On failure, returns false and stores error information into "*error" if + // "error" != nullptr. + bool insertion_sort(Error *error, ArrayRef<Record> records, Value *values); // Choose the pivot and move it to the front. void move_pivot_first(ArrayRef<Record> records, Value *values); }; template <typename T> -bool Node<T>::sort(Error *error, ArrayRef<Record> records, Int begin, Int end) { - if (!order_.expression->evaluate(error, records, &values_)) { +bool QuickSortNode<T>::sort(Error *error, + ArrayRef<Record> records, + Int begin, + Int end) { + if (!this->order_.expression->evaluate(error, records, &this->values_)) { return false; } - set_error(error); - return quick_sort(records, values_.data(), begin, end); + return quick_sort(error, records, this->values_.data(), begin, end); } template <typename T> -bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, - Int begin, Int end) { +bool QuickSortNode<T>::quick_sort(Error *error, + ArrayRef<Record> records, + Value *values, + Int begin, + Int end) { // Use ternary quick sort if there are enough records. // // TODO: Currently, the threshold is 16. @@ -159,7 +214,7 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, // Less prior entries are moved to right. // Entries which equal to the pivot are moved to the edges. while (left < right) { - if (prior_to_(pivot, values[left])) { + if (comparer_(pivot, values[left])) { break; } else if (pivot == values[left]) { std::swap(values[left], values[pivot_left]); @@ -170,7 +225,7 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, } while (left < right) { --right; - if (prior_to_(values[right], pivot)) { + if (comparer_(values[right], pivot)) { break; } else if (values[right] == pivot) { --pivot_right; @@ -206,8 +261,7 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, if (((right - left) >= 2) && (begin < right) && (end > left)) { Int next_begin = (begin < left) ? 0 : (begin - left); Int next_end = ((end > right) ? right : end) - left; - if (!this->next_->sort(this->error_, - records.ref(left, right - left), + if (!this->next_->sort(error, records.ref(left, right - left), next_begin, next_end)) { return false; } @@ -222,7 +276,8 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, if (left < (records.size() - right)) { if ((begin < left) && (left >= 2)) { Int next_end = (end < left) ? end : left; - if (!quick_sort(records.ref(0, left), values, begin, next_end)) { + if (!quick_sort(error, records.ref(0, left), values, + begin, next_end)) { return false; } } @@ -240,7 +295,7 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, if ((end > right) && ((records.size() - right) >= 2)) { Int next_begin = (begin < right) ? 0 : (begin - right); Int next_end = end - right; - if (!quick_sort(records.ref(right), + if (!quick_sort(error, records.ref(right), values + right, next_begin, next_end)) { return false; } @@ -256,16 +311,18 @@ bool Node<T>::quick_sort(ArrayRef<Record> records, Value *values, } if (records.size() >= 2) { - return insertion_sort(records, values); + return insertion_sort(error, records, values); } return true; } template <typename T> -bool Node<T>::insertion_sort(ArrayRef<Record> records, Value *values) { +bool QuickSortNode<T>::insertion_sort(Error *error, + ArrayRef<Record> records, + Value *values) { for (Int i = 1; i < records.size(); ++i) { for (Int j = i; j > 0; --j) { - if (prior_to_(values[j], values[j - 1])) { + if (comparer_(values[j], values[j - 1])) { std::swap(values[j], values[j - 1]); records.swap(j, j - 1); } else { @@ -280,8 +337,7 @@ bool Node<T>::insertion_sort(ArrayRef<Record> records, Value *values) { for (Int i = 1; i < records.size(); ++i) { if (values[i] != values[begin]) { if ((i - begin) >= 2) { - if (!this->next_->sort(this->error_, - records.ref(begin, i - begin), + if (!this->next_->sort(error, records.ref(begin, i - begin), 0, i - begin)) { return false; } @@ -290,8 +346,7 @@ bool Node<T>::insertion_sort(ArrayRef<Record> records, Value *values) { } } if ((records.size() - begin) >= 2) { - if (!this->next_->sort(this->error_, - records.ref(begin), + if (!this->next_->sort(error, records.ref(begin), 0, records.size() - begin)) { return false; } @@ -301,20 +356,21 @@ bool Node<T>::insertion_sort(ArrayRef<Record> records, Value *values) { } template <typename T> -void Node<T>::move_pivot_first(ArrayRef<Record> records, Value *values) { +void QuickSortNode<T>::move_pivot_first(ArrayRef<Record> records, + Value *values) { // Choose the median from values[1], values[1 / size], and values[size - 2]. // The reason why not using values[0] and values[size - 1] is to avoid the // worst case which occurs when the records are sorted in reverse order. Int first = 1; Int middle = records.size() / 2; Int last = records.size() - 2; - if (prior_to_(values[first], values[middle])) { + if (comparer_(values[first], values[middle])) { // first < middle. - if (prior_to_(values[middle], values[last])) { + if (comparer_(values[middle], values[last])) { // first < middle < last. std::swap(values[0], values[middle]); records.swap(0, middle); - } else if (prior_to_(values[first], values[last])) { + } else if (comparer_(values[first], values[last])) { // first < last < middle. std::swap(values[0], values[last]); records.swap(0, last); @@ -323,11 +379,11 @@ void Node<T>::move_pivot_first(ArrayRef<Record> records, Value *values) { std::swap(values[0], values[first]); records.swap(0, first); } - } else if (prior_to_(values[last], values[middle])) { + } else if (comparer_(values[last], values[middle])) { // last < middle < first. std::swap(values[0], values[middle]); records.swap(0, middle); - } else if (prior_to_(values[last], values[first])) { + } else if (comparer_(values[last], values[first])) { // middle < last < first. std::swap(values[0], values[last]); records.swap(0, last); @@ -338,149 +394,114 @@ void Node<T>::move_pivot_first(ArrayRef<Record> records, Value *values) { } } -// -- BoolNode<T> -- +// ----- RegularComparer ----- -struct RegularIsPrior { - bool operator()(Bool arg) const { - return !arg; +template <typename T> +struct RegularComparer { + using Value = T; + bool operator()(Value lhs, Value rhs) const { + return lhs < rhs; } }; -struct ReverseIsPrior { - bool operator()(Bool arg) const { - return arg; +template <> +struct RegularComparer<Float> { + using Value = Float; + bool operator()(Value lhs, Value rhs) const { + // Numbers are prior to NaN. + if (std::isnan(lhs)) { + return false; + } else if (std::isnan(rhs)) { + return true; + } + return lhs < rhs; } }; -template <typename T> -class BoolNode : public SorterNode { - public: - using IsPrior = T; - - explicit BoolNode(SortOrder &&order) - : SorterNode(), - order_(std::move(order)), - values_(), - is_prior_() {} - ~BoolNode() {} - - bool sort(Error *error, ArrayRef<Record> records, Int begin, Int end); - - private: - SortOrder order_; - Array<Bool> values_; - IsPrior is_prior_; -}; - -template <typename T> -bool BoolNode<T>::sort(Error *error, ArrayRef<Record> records, - Int begin, Int end) { - if (!order_.expression->evaluate(error, records, &values_)) { - return false; - } - set_error(error); - - // Move prior entries to left and others to right. - Int left = 0; - Int right = records.size(); - while (left < right) { - if (is_prior_(values_[left])) { - ++left; - } else { - // Note that values_[left] will not be used again. - --right; - values_.set(left, values_[right]); - records.swap(left, right); +template <> +struct RegularComparer<GeoPoint> { + using Value = GeoPoint; + bool operator()(Value lhs, Value rhs) const { + if (lhs.latitude() != rhs.latitude()) { + return lhs.latitude() < rhs.latitude(); } + return lhs.longitude() < rhs.longitude(); } +}; - // Now "left" equals to "right" and it points to the boundary. - // The left group is [0, left) and the right group is [left, records.size()). - if (this->next_) { - // Apply the next sort condition if blocks contain 2 or more records. - if ((left >= 2) && (begin < left)) { - if (!this->next_->sort(error, records.ref(0, left), - begin, (end < left) ? end : left)) { - return false; - } - } - if (((records.size() - left) >= 2) && (end > left)) { - if (begin < left) { - begin = 0; - } else { - begin -= left; - } - end -= left; - if (!this->next_->sort(error, records.ref(left), begin, end)) { - return false; - } - } +// ----- ReverseComparer ----- + +template <typename T> +struct ReverseComparer { + using Value = T; + bool operator()(Value lhs, Value rhs) const { + return RegularComparer<T>()(rhs, lhs); } +}; - return true; -} +} // namespace sorter -} // namespace +using namespace sorter; unique_ptr<SorterNode> SorterNode::create(Error *error, SortOrder &&order) { unique_ptr<SorterNode> node; switch (order.expression->data_type()) { case BOOL_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) BoolNode<RegularIsPrior>( + node.reset(new (nothrow) SeparatorNode<RegularIsPrior>( std::move(order))); } else { - node.reset(new (nothrow) BoolNode<ReverseIsPrior>( + node.reset(new (nothrow) SeparatorNode<ReverseIsPrior>( std::move(order))); } break; } case INT_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) Node<RegularComparer<Int>>( + node.reset(new (nothrow) QuickSortNode<RegularComparer<Int>>( std::move(order))); } else { - node.reset(new (nothrow) Node<ReverseComparer<Int>>( + node.reset(new (nothrow) QuickSortNode<ReverseComparer<Int>>( std::move(order))); } break; } case FLOAT_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) Node<RegularComparer<Float>>( + node.reset(new (nothrow) QuickSortNode<RegularComparer<Float>>( std::move(order))); } else { - node.reset(new (nothrow) Node<ReverseComparer<Float>>( + node.reset(new (nothrow) QuickSortNode<ReverseComparer<Float>>( std::move(order))); } break; } case TIME_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) Node<RegularComparer<Time>>( + node.reset(new (nothrow) QuickSortNode<RegularComparer<Time>>( std::move(order))); } else { - node.reset(new (nothrow) Node<ReverseComparer<Time>>( + node.reset(new (nothrow) QuickSortNode<ReverseComparer<Time>>( std::move(order))); } break; } case GEO_POINT_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) Node<RegularComparer<GeoPoint>>( + node.reset(new (nothrow) QuickSortNode<RegularComparer<GeoPoint>>( std::move(order))); } else { - node.reset(new (nothrow) Node<ReverseComparer<GeoPoint>>( + node.reset(new (nothrow) QuickSortNode<ReverseComparer<GeoPoint>>( std::move(order))); } break; } case TEXT_DATA: { if (order.type == REGULAR_ORDER) { - node.reset(new (nothrow) Node<RegularComparer<Text>>( + node.reset(new (nothrow) QuickSortNode<RegularComparer<Text>>( std::move(order))); } else { - node.reset(new (nothrow) Node<ReverseComparer<Text>>( + node.reset(new (nothrow) QuickSortNode<ReverseComparer<Text>>( std::move(order))); } break; Modified: lib/grnxx/types.cpp (+12 -0) =================================================================== --- lib/grnxx/types.cpp 2014-08-19 17:37:54 +0900 (ddad422) +++ lib/grnxx/types.cpp 2014-08-20 11:21:55 +0900 (d656302) @@ -60,4 +60,16 @@ SorterOptions::SorterOptions() : offset(0), limit(numeric_limits<Int>::max()) {} +SortOrder::SortOrder() : expression(), type(REGULAR_ORDER) {} + +SortOrder::SortOrder(SortOrder &&order) + : expression(std::move(order.expression)), + type(order.type) {} + +SortOrder::SortOrder(unique_ptr<Expression> &&expression, OrderType type) + : expression(std::move(expression)), + type(type) {} + +SortOrder::~SortOrder() {} + } // namespace grnxx -------------- next part -------------- HTML����������������������������...Download