#ifndef FIND_CLOSEST_H
#define FIND_CLOSEST_H

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

// Find the element in a sorted range that is closest to the requested value.
// @pre: is_sorted(range, comp, proj)
//
// The return value contains:
// * An iterator pointing at the closest element (or end() when the range is
//   empty). When two neighboring elements are equally close, the earlier
//   element is returned.
// * The absolute distance between that element and the requested value. When
//   the range is empty the distance is unspecified.
template<std::bidirectional_iterator I, std::sentinel_for<I> S, typename T,
         typename Compare = std::ranges::less, typename Proj = std::identity>
[[nodiscard]] constexpr auto find_closest(
	I first, S last, const T& value, Compare comp = {}, Proj proj = {})
{
	using Ref = std::iter_reference_t<I>;
	using Key = std::remove_cvref_t<std::invoke_result_t<Proj&, Ref>>;
	using LeftDiff = std::remove_cvref_t<decltype(std::declval<Key>() - std::declval<T>())>;
	using RightDiff = std::remove_cvref_t<decltype(std::declval<T>() - std::declval<Key>())>;
	static_assert(std::is_same_v<LeftDiff, RightDiff>,
	              "find_closest() requires symmetric subtraction results.");
	using Diff = LeftDiff;
	using Result = std::pair<I, Diff>;

	auto it = std::ranges::lower_bound(first, last, value, comp, proj);

	if (it == first) {
		if (it == last) return Result{last, Diff{}};
		return Result{it, std::invoke(proj, *it) - value};
	}
	if (it == last) {
		auto prev = std::prev(last);
		return Result{prev, value - std::invoke(proj, *prev)};
	}

	auto prev = std::prev(it);
	auto distPrev = value - std::invoke(proj, *prev);
	auto distCurr = std::invoke(proj, *it) - value;
	return (distPrev <= distCurr) ? Result{prev, distPrev}
	                              : Result{it, distCurr};
}

template<std::ranges::bidirectional_range Range, typename T,
         typename Compare = std::ranges::less, typename Proj = std::identity>
[[nodiscard]] constexpr auto find_closest(
	Range&& range, const T& value, Compare comp = {}, Proj proj = {})
{
	auto first = std::ranges::begin(range);
	auto last = std::ranges::end(range);
	return find_closest(first, last, value, comp, proj);
}

#endif