// pop_range.hpp
//
// Adapts std::stack, std::queue and std::priority_queue (any type exposing
// empty()/pop() plus top() or front()) to the C++20 <ranges>/<iterator>
// machinery.
//
// The resulting range is a *view* whose iterator is forward-declared as an
// input_iterator only: dereferencing yields the next element (top()/front())
// and incrementing calls pop() on the underlying adaptor. Because popping is
// destructive and irreversible, this 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.
//
// 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::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 adaptor.
// ---------------------------------------------------------------------

template <typename A>
concept poppable_adaptor =
    requires(A& a) {
        typename A::value_type;
        { a.empty() } -> std::convertible_to<bool>;
        a.pop();
    } && (requires(A& a) { a.top(); } || requires(A& a) { a.front(); });

// Extract "the next element" regardless of whether the adaptor exposes
// top() (stack, priority_queue) or front() (queue).
template <poppable_adaptor A>
decltype(auto) peek(A& a) {
    if constexpr (requires { a.top(); })
        return a.top();
    else
        return a.front();
}

// ---------------------------------------------------------------------
// 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 a *copy* of the next element (top()/front() may be a
    // reference into the adaptor, which becomes dangling the instant we
    // pop() -- so operator* must not return a reference to it).
    value_type operator*() const {
        return peek(*adaptor_);
    }

    pop_iterator& operator++() {
        adaptor_->pop();
        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();
    }

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