14#ifndef OR_TOOLS_UTIL_SORT_H_
15#define OR_TOOLS_UTIL_SORT_H_
23template <
class Iterator>
24using value_type_t =
typename std::iterator_traits<Iterator>::value_type;
45template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
47 Compare comp = Compare{},
bool is_stable =
false) {
49 if (std::distance(
begin,
end) <= 1)
return;
53 Iterator last_sorted = std::prev(
end);
54 for (
auto it = last_sorted; it !=
begin; --it) {
55 if (comp(*it, *std::prev(it))) {
56 std::iter_swap(it, std::prev(it));
63 Iterator it = std::next(last_sorted);
64 for (; it !=
end && max_comparisons > 0; ++it) {
65 const auto inserted = *it;
68 while (comp(inserted, *std::prev(j))) {
77 if (it ==
end)
return;
80 std::stable_sort(last_sorted,
end, comp);
82 std::sort(last_sorted,
end, comp);
94template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
97 if (std::distance(
begin,
end) <= 1)
return;
101 Iterator last_sorted = std::prev(
end);
102 for (
auto it = last_sorted; it !=
begin; --it) {
103 if (comp(*it, *std::prev(it))) {
104 std::iter_swap(it, std::prev(it));
111 for (Iterator it = std::next(last_sorted); it !=
end; ++it) {
112 const auto inserted = *it;
114 while (comp(inserted, *std::prev(j))) {
128template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
130 bool is_stable =
false) {
131 const int size = std::distance(
begin,
end);
In SWIG mode, we don't want anything besides these top-level includes.
typename std::iterator_traits< Iterator >::value_type value_type_t
ClosedInterval::Iterator end(ClosedInterval interval)
void IncrementalSort(int max_comparisons, Iterator begin, Iterator end, Compare comp=Compare{}, bool is_stable=false)
ClosedInterval::Iterator begin(ClosedInterval interval)
void InsertionSort(Iterator begin, Iterator end, Compare comp=Compare{})