// pop_range.hpp
//
// Adapts std::stack, std::queue, std::priority_queue -- and, more
// generally, any container exposing pop()+top()/front(), or
// pop_front()+front(), or pop_back()+back() (so std::vector, std::deque,
// and std::list work too) -- to the C++20 <ranges>/<iterator> machinery.
//
// The resulting range is a *view* whose iterator models input_iterator
// only: dereferencing yields (an rvalue reference to) the next element and
// incrementing removes it from the underlying container. Because this is
// destructive and irreversible, it can only ever be a single-pass (input)
// range -- it deliberately does NOT model forward_range, since a
// forward_range must guarantee that iterating twice observes the same
// sequence, which is impossible once elements are being consumed. It DOES
// model sized_range, since (unlike forward_range) sized_range does not
// require size() to stay meaningful independent of begin() -- reporting
// "how many elements are left right now" is perfectly legitimate for a
// single-pass range.
//
// Usage:
//
//   std::stack<int> s;  s.push(1); s.push(2); s.push(3);
//   for (int v : pop_range::views::pop(s)) std::cout << v << ' ';   // 3 2 1
//
//   std::queue<int> q;  q.push(1); q.push(2); q.push(3);
//   for (int v : q | pop_range::views::pop) std::cout << v << ' '; // 1 2 3
//
//   std::vector<int> v{1, 2, 3};
//   for (int x : pop_range::views::pop(v)) std::cout << x << ' ';  // 3 2 1
//
//   std::priority_queue<int> pq{...};
//   auto v = pop_range::views::pop(pq) | std::views::take(2)
//                                       | std::ranges::to<std::vector>();
//
#pragma once

#include <concepts>
#include <cstddef>
#include <iterator>
#include <memory>
#include <optional>
#include <ranges>
#include <type_traits>
#include <utility>

namespace pop_range {

// ---------------------------------------------------------------------
// Concepts describing what we need from the underlying container.
//
// Two shapes are supported:
//   1) "Adaptor" shape: pop() (nullary) + top() or front()
//      -- covers std::stack, std::queue, std::priority_queue.
//   2) "Sequence" shape: pop_front()/front() or pop_back()/back()
//      -- covers std::vector (back()/pop_back()), std::deque and
//      std::list (either end).
//
// When a type could satisfy more than one shape (e.g. std::list and
// std::deque have both pop_front() and pop_back()), the SAME priority
// order is used everywhere below (nullary-pop first, then front, then
// back) so peek() and consume() always agree on which end is in use.
// ---------------------------------------------------------------------

template <typename A>
concept has_top = requires(A& a) { a.top(); };
template <typename A>
concept has_front = requires(A& a) { a.front(); };
template <typename A>
concept has_back = requires(A& a) { a.back(); };
template <typename A>
concept has_nullary_pop = requires(A& a) { a.pop(); };
template <typename A>
concept has_pop_front = requires(A& a) { a.pop_front(); };
template <typename A>
concept has_pop_back = requires(A& a) { a.pop_back(); };

template <typename A>
concept poppable_adaptor =
    requires(A& a) {
        typename A::value_type;
        { a.empty() } -> std::convertible_to<bool>;
    } &&
    ((has_nullary_pop<A> && (has_top<A> || has_front<A>)) ||
     (has_pop_front<A> && has_front<A>) ||
     (has_pop_back<A> && has_back<A>));

// Peek at "the next element" without removing it.
template <poppable_adaptor A>
decltype(auto) peek(A& a) {
    if constexpr (has_nullary_pop<A> && has_top<A>)
        return a.top();                 // stack, priority_queue
    else if constexpr (has_nullary_pop<A> && has_front<A>)
        return a.front();               // queue
    else if constexpr (has_pop_front<A> && has_front<A>)
        return a.front();               // deque/list, front end
    else
        return a.back();                // vector, or deque/list, back end
}

// Remove "the next element", using whichever removal function pairs with
// the branch peek() selected above (kept in the same priority order).
template <poppable_adaptor A>
void consume(A& a) {
    if constexpr (has_nullary_pop<A>)
        a.pop();
    else if constexpr (has_pop_front<A> && has_front<A>)
        a.pop_front();
    else
        a.pop_back();
}

// ---------------------------------------------------------------------
// Iterator: forward-only in the C++ sense of "moves only forward through
// the input", modeled as std::input_iterator. Every operator++ pops.
// ---------------------------------------------------------------------

template <poppable_adaptor A>
class pop_iterator {
public:
    using value_type      = typename A::value_type;
    using difference_type = std::ptrdiff_t;
    using iterator_concept = std::input_iterator_tag;

    pop_iterator() = default;

    explicit pop_iterator(A* adaptor) noexcept : adaptor_(adaptor) {
        if (adaptor_ && adaptor_->empty())
            adaptor_ = nullptr; // normalize to the "end" state immediately
    }

    // Returns an *rvalue reference* to the element still stored in the
    // container, not a copy. This is safe specifically because we only
    // model input_iterator: nothing requires a previous *it result to
    // stay valid once the iterator is incremented (contrast
    // forward_iterator, which does require that). The same technique is
    // used by std::move_iterator for the same reason. Binding the result
    // with `auto v = *it;` or a range-based for's `auto v` selects v's
    // move constructor (falling back to its copy constructor if it has
    // no move constructor); binding with `const auto&` or `auto&&` reads
    // the element in place with no copy or move at all.
    //
    // Note this is only sound because peek() never returns a *dangling*
    // reference here -- the referenced element is still alive in the
    // container until the next pop_front()/pop_back()/pop().
    decltype(auto) operator*() const {
        return std::move(peek(*adaptor_));
    }

    pop_iterator& operator++() {
        consume(*adaptor_);
        if (adaptor_->empty())
            adaptor_ = nullptr;
        return *this;
    }

    // input_iterator only requires i++ to be valid, not that it return
    // anything useful (see [iterator.concept.winc]).
    void operator++(int) { ++(*this); }

    friend bool operator==(const pop_iterator& it, std::default_sentinel_t) noexcept {
        return it.adaptor_ == nullptr;
    }

private:
    A* adaptor_ = nullptr;
};

// ---------------------------------------------------------------------
// View: either references an existing adaptor (view(a)) or owns one that
// was handed to it as an rvalue (view(std::move(a))). The owned adaptor is
// kept behind a unique_ptr so its address is stable even if the view
// itself is moved -- iterators only ever point at the adaptor, not at the
// view.
// ---------------------------------------------------------------------

template <poppable_adaptor A>
class pop_view : public std::ranges::view_interface<pop_view<A>> {
public:
    pop_view() = default;

    // Adapt an existing adaptor in place; caller must keep `adaptor`
    // alive for as long as the view (and its iterators) are used.
    explicit pop_view(A& adaptor) noexcept : ptr_(&adaptor) {}

    // Take ownership of a temporary/moved-in adaptor.
    explicit pop_view(A&& adaptor)
        : owned_(std::make_unique<A>(std::move(adaptor))), ptr_(owned_.get()) {}

    pop_view(pop_view&&) = default;
    pop_view& operator=(pop_view&&) = default;
    // Not copyable: copying would either duplicate a whole container
    // (surprising / expensive) or alias the same adaptor from two views
    // that would then race to pop() it. Move-only is the honest model.
    pop_view(const pop_view&) = delete;
    pop_view& operator=(const pop_view&) = delete;

    pop_iterator<A> begin() const { return pop_iterator<A>(ptr_); }
    std::default_sentinel_t end() const noexcept { return std::default_sentinel; }

    [[nodiscard]] bool empty() const noexcept {
        return ptr_ == nullptr || ptr_->empty();
    }

    // sized_range only requires ranges::size(t) to be well-defined
    // *regardless of evaluating ranges::begin(t)* when T models
    // forward_range. pop_view deliberately never models forward_range (see
    // above), so that extra stability clause doesn't apply to us, and
    // exposing size() here is legitimate -- it simply reports how many
    // elements are left to pop right now, which shrinks as the range is
    // consumed, same as the underlying container's own size().
    [[nodiscard]] auto size() const
        requires requires(const A& a) { a.size(); }
    {
        using size_type = decltype(std::declval<const A&>().size());
        return ptr_ ? static_cast<size_type>(ptr_->size()) : size_type{0};
    }

private:
    std::unique_ptr<A> owned_;
    A* ptr_ = nullptr;
};

template <poppable_adaptor A>
pop_view(A&) -> pop_view<A>;
template <poppable_adaptor A>
pop_view(A&&) -> pop_view<A>;

} // namespace pop_range

// A pop_view is always single-pass and destructive, so it is explicitly
// NOT a forward_range/common_range no matter what view_interface might
// otherwise infer; it only ever models input_range.
template <typename A>
inline constexpr bool std::ranges::enable_view<pop_range::pop_view<A>> = true;

namespace pop_range::views {

// Adaptor-closure object supporting both call syntax and pipe syntax:
//   pop(container)          // C++20-portable, no library dependency
//   container | pop         // via the operator| overloads below
//
// (std::ranges::range_adaptor_closure would give us `|` for free, but
// it's C++23-only, so it's implemented by hand here to keep this usable
// under plain C++20.)
struct pop_fn {
    template <poppable_adaptor A>
    [[nodiscard]] auto operator()(A& adaptor) const {
        return pop_view<A>(adaptor);
    }

    template <poppable_adaptor A>
    [[nodiscard]] auto operator()(A&& adaptor) const {
        return pop_view<A>(std::move(adaptor));
    }
};

inline constexpr pop_fn pop{};

template <poppable_adaptor A>
[[nodiscard]] auto operator|(A& adaptor, pop_fn) {
    return pop_view<A>(adaptor);
}

template <poppable_adaptor A>
[[nodiscard]] auto operator|(A&& adaptor, pop_fn) {
    return pop_view<A>(std::move(adaptor));
}

} // namespace pop_range::views