ranges::BubbleSort

BreadSort.hpp

#pragma once

#include <algorithm>
#include <ranges>
#include <functional>
#include <iterator>
#include <type_traits>

namespace BreadSort {
	namespace detail {
		template <class Implementation>
		struct SortFunctionBoilerplate
		{
			template<std::random_access_iterator I, std::sentinel_for<I> S,
				class Comp = std::ranges::less, class Proj = std::identity>
				requires std::sortable<I, Comp, Proj>
			constexpr I
				operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
			{
				if (first == last)
				{
					return first;
				}

				I last_iter = std::ranges::next(first, last);
				std::invoke(Implementation{}, first, last_iter, std::ref(comp), std::ref(proj));
				return last_iter;
			}

			template<std::ranges::random_access_range R, class Comp = std::ranges::less,
				class Proj = std::identity>
				requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
			constexpr std::ranges::borrowed_iterator_t<R>
				operator()(R&& r, Comp comp = {}, Proj proj = {}) const
			{
				return (*this)(std::ranges::begin(r), std::ranges::end(r), std::move(comp), std::move(proj));
			}
		};

		// Based on https://en.cppreference.com/w/cpp/algorithm/ranges/sort#Possible_implementation
		constexpr auto ReferenceSortImplementation = []<std::random_access_iterator I>(I first, I last, auto comp, auto proj) {
			std::ranges::make_heap(first, last, std::ref(comp), std::ref(proj));
			std::ranges::sort_heap(first, last, std::ref(comp), std::ref(proj));
		};
		using ReferenceSortFunction = SortFunctionBoilerplate<decltype(ReferenceSortImplementation)>;

		constexpr auto BubbleSortImplementation = []<std::random_access_iterator I>(I first, I last, auto comp, auto proj) {
			bool clean = false;
			while (!clean) {
				clean = true;
				for (I previous(first), current(first + 1); current != last; previous = current++) {
					if (std::invoke(comp, std::invoke(proj, *current), std::invoke(proj, *previous))) {
						std::ranges::iter_swap(previous, current);
						clean = false;
					}
				}
			}
		};
		using BubbleSortFunction = SortFunctionBoilerplate<decltype(BubbleSortImplementation)>;
	}

	constexpr detail::ReferenceSortFunction ReferenceSort{};
	constexpr detail::BubbleSortFunction BubbleSort{};
}