// Algorithm implementation -*- C++ -*-
-// Copyright (C) 2001-2013 Free Software Foundation, Inc.
+// Copyright (C) 2001-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
- /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
+ /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
void
- __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
- _Compare __comp)
+ __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
+ _Iterator __c, _Compare __comp)
{
if (__comp(__a, __b))
{
if (__comp(__b, __c))
- std::iter_swap(__a, __b);
+ std::iter_swap(__result, __b);
else if (__comp(__a, __c))
- std::iter_swap(__a, __c);
+ std::iter_swap(__result, __c);
+ else
+ std::iter_swap(__result, __a);
}
else if (__comp(__a, __c))
- return;
+ std::iter_swap(__result, __a);
else if (__comp(__b, __c))
- std::iter_swap(__a, __c);
+ std::iter_swap(__result, __c);
else
- std::iter_swap(__a, __b);
+ std::iter_swap(__result, __b);
}
/// This is an overload used by find algos for the Input Iterator case.
// partition
- /// This is a helper function...
- /// Requires __len != 0 and !__pred(*__first),
- /// same as __stable_partition_adaptive.
- template<typename _ForwardIterator, typename _Predicate, typename _Distance>
- _ForwardIterator
- __inplace_stable_partition(_ForwardIterator __first,
- _Predicate __pred, _Distance __len)
- {
- if (__len == 1)
- return __first;
- _ForwardIterator __middle = __first;
- std::advance(__middle, __len / 2);
- _ForwardIterator __left_split =
- std::__inplace_stable_partition(__first, __pred, __len / 2);
- // Advance past true-predicate values to satisfy this
- // function's preconditions.
- _Distance __right_len = __len - __len / 2;
- _ForwardIterator __right_split =
- std::__find_if_not_n(__middle, __right_len, __pred);
- if (__right_len)
- __right_split = std::__inplace_stable_partition(__middle,
- __pred,
- __right_len);
- std::rotate(__left_split, __middle, __right_split);
- std::advance(__left_split, std::distance(__middle, __right_split));
- return __left_split;
- }
-
/// This is a helper function...
/// Requires __first != __last and !__pred(__first)
/// and __len == distance(__first, __last).
_Pointer __buffer,
_Distance __buffer_size)
{
+ if (__len == 1)
+ return __first;
+
if (__len <= __buffer_size)
{
_ForwardIterator __result1 = __first;
_Pointer __result2 = __buffer;
+
// The precondition guarantees that !__pred(__first), so
// move that element to the buffer before starting the loop.
// This ensures that we only call __pred once per element.
*__result2 = _GLIBCXX_MOVE(*__first);
++__result2;
}
+
_GLIBCXX_MOVE3(__buffer, __result2, __result1);
return __result1;
}
- else
- {
- _ForwardIterator __middle = __first;
- std::advance(__middle, __len / 2);
- _ForwardIterator __left_split =
- std::__stable_partition_adaptive(__first, __middle, __pred,
- __len / 2, __buffer,
- __buffer_size);
- // Advance past true-predicate values to satisfy this
- // function's preconditions.
- _Distance __right_len = __len - __len / 2;
- _ForwardIterator __right_split =
- std::__find_if_not_n(__middle, __right_len, __pred);
- if (__right_len)
- __right_split =
- std::__stable_partition_adaptive(__right_split, __last, __pred,
- __right_len,
- __buffer, __buffer_size);
- std::rotate(__left_split, __middle, __right_split);
- std::advance(__left_split, std::distance(__middle, __right_split));
- return __left_split;
- }
+
+ _ForwardIterator __middle = __first;
+ std::advance(__middle, __len / 2);
+ _ForwardIterator __left_split =
+ std::__stable_partition_adaptive(__first, __middle, __pred,
+ __len / 2, __buffer,
+ __buffer_size);
+
+ // Advance past true-predicate values to satisfy this
+ // function's preconditions.
+ _Distance __right_len = __len - __len / 2;
+ _ForwardIterator __right_split =
+ std::__find_if_not_n(__middle, __right_len, __pred);
+
+ if (__right_len)
+ __right_split =
+ std::__stable_partition_adaptive(__right_split, __last, __pred,
+ __right_len,
+ __buffer, __buffer_size);
+
+ std::rotate(__left_split, __middle, __right_split);
+ std::advance(__left_split, std::distance(__middle, __right_split));
+ return __left_split;
}
template<typename _ForwardIterator, typename _Predicate>
_DistanceType;
_Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
- if (__buf.size() > 0)
- return
- std::__stable_partition_adaptive(__first, __last, __pred,
- _DistanceType(__buf.requested_size()),
- __buf.begin(),
- _DistanceType(__buf.size()));
- else
- return
- std::__inplace_stable_partition(__first, __pred,
- _DistanceType(__buf.requested_size()));
+ return
+ std::__stable_partition_adaptive(__first, __last, __pred,
+ _DistanceType(__buf.requested_size()),
+ __buf.begin(),
+ _DistanceType(__buf.size()));
}
/**
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
- std::__move_median_first(__first, __mid, (__last - 1), __comp);
+ std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
+ __comp);
return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}
__gnu_cxx::__ops::__val_comp_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
+
_BidirectionalIterator __new_middle
= std::__rotate_adaptive(__first_cut, __middle, __second_cut,
__len1 - __len11, __len22, __buffer,
{
if (__len1 == 0 || __len2 == 0)
return;
+
if (__len1 + __len2 == 2)
{
if (__comp(__middle, __first))
std::iter_swap(__first, __middle);
return;
}
+
_BidirectionalIterator __first_cut = __first;
_BidirectionalIterator __second_cut = __middle;
_Distance __len11 = 0;
__gnu_cxx::__ops::__val_comp_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
+
std::rotate(__first_cut, __middle, __second_cut);
_BidirectionalIterator __new_middle = __first_cut;
std::advance(__new_middle, std::distance(__middle, __second_cut));
if (__first != __last)
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
- std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
+ {
+ // XXX rand() % N is not uniformly distributed
+ _RandomAccessIterator __j = __first
+ + std::rand() % ((__i - __first) + 1);
+ if (__i != __j)
+ std::iter_swap(__i, __j);
+ }
}
/**
if (__first == __last)
return;
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
- std::iter_swap(__i, __first + __rand((__i - __first) + 1));
+ {
+ _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
+ if (__i != __j)
+ std::iter_swap(__i, __j);
+ }
}
projects / gcc.git / blobdiff