summaryrefslogtreecommitdiff
path: root/boost/sort/spreadsort/detail
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 10:33:54 +0900
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-10-06 10:36:09 +0900
commitd9ec475d945d3035377a0d89ed42e382d8988891 (patch)
tree34aff2cee4b209906243ab5499d61f3edee2982f /boost/sort/spreadsort/detail
parent71d216b90256936a9638f325af9bc69d720e75de (diff)
downloadboost-d9ec475d945d3035377a0d89ed42e382d8988891.tar.gz
boost-d9ec475d945d3035377a0d89ed42e382d8988891.tar.bz2
boost-d9ec475d945d3035377a0d89ed42e382d8988891.zip
Imported Upstream version 1.60.0
Change-Id: Ie709530d6d5841088ceaba025cbe175a4ef43050 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/sort/spreadsort/detail')
-rw-r--r--boost/sort/spreadsort/detail/float_sort.hpp55
-rw-r--r--boost/sort/spreadsort/detail/string_sort.hpp2
2 files changed, 41 insertions, 16 deletions
diff --git a/boost/sort/spreadsort/detail/float_sort.hpp b/boost/sort/spreadsort/detail/float_sort.hpp
index 8af8a174bd..03dcbaf4f6 100644
--- a/boost/sort/spreadsort/detail/float_sort.hpp
+++ b/boost/sort/spreadsort/detail/float_sort.hpp
@@ -56,12 +56,36 @@ namespace spreadsort {
Div_type & max, Div_type & min, Right_shift rshift)
{
min = max = rshift(*current, 0);
- Div_type prev = min;
+ RandomAccessIter prev = current;
bool sorted = true;
while (++current < last) {
Div_type value = rshift(*current, 0);
- sorted &= value >= prev;
- prev = value;
+ sorted &= *current >= *prev;
+ prev = current;
+ if (max < value)
+ max = value;
+ else if (value < min)
+ min = value;
+ }
+ return sorted;
+ }
+
+ // Return true if the list is sorted. Otherwise, find the minimum and
+ // maximum. Uses comp to check if the data is already sorted.
+ template <class RandomAccessIter, class Div_type, class Right_shift,
+ class Compare>
+ inline bool
+ is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
+ Div_type & max, Div_type & min,
+ Right_shift rshift, Compare comp)
+ {
+ min = max = rshift(*current, 0);
+ RandomAccessIter prev = current;
+ bool sorted = true;
+ while (++current < last) {
+ Div_type value = rshift(*current, 0);
+ sorted &= !comp(*current, *prev);
+ prev = current;
if (max < value)
max = value;
else if (value < min)
@@ -123,12 +147,12 @@ namespace spreadsort {
Cast_type & max, Cast_type & min)
{
min = max = cast_float_iter<Cast_type, RandomAccessIter>(current);
- Cast_type prev = min;
+ RandomAccessIter prev = current;
bool sorted = true;
while (++current < last) {
Cast_type value = cast_float_iter<Cast_type, RandomAccessIter>(current);
- sorted &= value >= prev;
- prev = value;
+ sorted &= *current >= *prev;
+ prev = current;
if (max < value)
max = value;
else if (value < min)
@@ -205,8 +229,9 @@ namespace spreadsort {
{
Div_type max, min;
if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
- max, min))
+ max, min))
return;
+
unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
last - first, rough_log_2_size(Size_type(max - min)));
Div_type div_min = min >> log_divisor;
@@ -323,7 +348,7 @@ namespace spreadsort {
size_t *bin_sizes, Right_shift rshift, Compare comp)
{
Div_type max, min;
- if (is_sorted_or_find_extremes(first, last, max, min, rshift))
+ if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
return;
unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
last - first, rough_log_2_size(Size_type(max - min)));
@@ -578,7 +603,7 @@ namespace spreadsort {
size_t *bin_sizes, Right_shift rshift, Compare comp)
{
Div_type max, min;
- if (is_sorted_or_find_extremes(first, last, max, min, rshift))
+ if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
return;
unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
last - first, rough_log_2_size(Size_type(max - min)));
@@ -679,7 +704,7 @@ namespace spreadsort {
void >::type
float_sort(RandomAccessIter first, RandomAccessIter last)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, boost::int32_t, boost::uint32_t>
(first, last, bin_cache, 0, bin_sizes);
@@ -694,7 +719,7 @@ namespace spreadsort {
void >::type
float_sort(RandomAccessIter first, RandomAccessIter last)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, boost::int64_t, boost::uint64_t>
(first, last, bin_cache, 0, bin_sizes);
@@ -727,7 +752,7 @@ namespace spreadsort {
float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
Right_shift rshift)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, Div_type, Right_shift, size_t>
(first, last, bin_cache, 0, bin_sizes, rshift);
@@ -740,7 +765,7 @@ namespace spreadsort {
float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
Right_shift rshift)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, Div_type, Right_shift, boost::uintmax_t>
(first, last, bin_cache, 0, bin_sizes, rshift);
@@ -765,7 +790,7 @@ namespace spreadsort {
float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
Right_shift rshift, Compare comp)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
size_t>
@@ -780,7 +805,7 @@ namespace spreadsort {
float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
Right_shift rshift, Compare comp)
{
- size_t bin_sizes[1 << max_splits];
+ size_t bin_sizes[1 << max_finishing_splits];
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
boost::uintmax_t>
diff --git a/boost/sort/spreadsort/detail/string_sort.hpp b/boost/sort/spreadsort/detail/string_sort.hpp
index a5a40f056d..ef943b8ec4 100644
--- a/boost/sort/spreadsort/detail/string_sort.hpp
+++ b/boost/sort/spreadsort/detail/string_sort.hpp
@@ -42,7 +42,7 @@ namespace spreadsort {
{
const int char_size = sizeof(Unsigned_char_type);
size_t nextOffset = char_offset;
- int step_size = max_step_size;
+ int step_size = max_step_size / char_size;
while (true) {
RandomAccessIter curr = first;
do {