#pragma once

#include <util/generic/ptr.h>
#include <util/generic/vector.h>
#include <util/generic/yexception.h>

#include <iterator>

namespace NPagedVector {
    template <class T, ui32 PageSize = 1u << 20u, class A = std::allocator<T>>
    class TPagedVector;

    namespace NPrivate {
        template <class T, class TT, ui32 PageSize, class A>
        struct TPagedVectorIterator {
        private:
            friend class TPagedVector<TT, PageSize, A>;
            using TVec = TPagedVector<TT, PageSize, A>;
            using TSelf = TPagedVectorIterator<T, TT, PageSize, A>;
            size_t Offset_;
            TVec* Vector_;

            template <class T1, class TT1, ui32 PageSize1, class A1>
            friend struct TPagedVectorIterator;

        public:
            TPagedVectorIterator()
                : Offset_()
                , Vector_()
            {
            }

            TPagedVectorIterator(TVec* vector, size_t offset)
                : Offset_(offset)
                , Vector_(vector)
            {
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            TPagedVectorIterator(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it)
                : Offset_(it.Offset_)
                , Vector_(it.Vector_)
            {
            }

            T& operator*() const {
                return (*Vector_)[Offset_];
            }

            T* operator->() const {
                return &(**this);
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator==(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return Offset_ == it.Offset_;
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator!=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return !(*this == it);
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator<(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return Offset_ < it.Offset_;
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator<=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return Offset_ <= it.Offset_;
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator>(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return !(*this <= it);
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            bool operator>=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return !(*this < it);
            }

            template <class T1, class TT1, ui32 PageSize1, class A1>
            ptrdiff_t operator-(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const {
                return Offset_ - it.Offset_;
            }

            TSelf& operator+=(ptrdiff_t off) {
                Offset_ += off;
                return *this;
            }

            TSelf& operator-=(ptrdiff_t off) {
                return this->operator+=(-off);
            }

            TSelf& operator++() {
                return this->operator+=(1);
            }

            TSelf& operator--() {
                return this->operator+=(-1);
            }

            TSelf operator++(int) {
                TSelf it = *this;
                this->operator+=(1);
                return it;
            }

            TSelf operator--(int) {
                TSelf it = *this;
                this->operator+=(-1);
                return it;
            }

            TSelf operator+(ptrdiff_t off) const {
                TSelf res = *this;
                res += off;
                return res;
            }

            TSelf operator-(ptrdiff_t off) const {
                return this->operator+(-off);
            }

            size_t GetOffset() const {
                return Offset_;
            }
        };
    } // namespace NPrivate
} // namespace NPagedVector

namespace std {
    template <class T, class TT, ui32 PageSize, class A>
    struct iterator_traits<NPagedVector::NPrivate::TPagedVectorIterator<T, TT, PageSize, A>> {
        using difference_type = ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = random_access_iterator_tag;
    };

} // namespace std

namespace NPagedVector {
    // 2-level radix tree
    template <class T, ui32 PageSize, class A>
    class TPagedVector {
        static_assert(PageSize, "expect PageSize");

        using TPage = TVector<T, A>;
        using TPages = TVector<THolder<TPage>, A>;
        using TSelf = TPagedVector<T, PageSize, A>;

        TPages Pages_;

    public:
        using iterator = NPrivate::TPagedVectorIterator<T, T, PageSize, A>;
        using const_iterator = NPrivate::TPagedVectorIterator<const T, T, PageSize, A>;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;
        using value_type = T;
        using reference = value_type&;
        using const_reference = const value_type&;

        TPagedVector() = default;
        TPagedVector(TPagedVector&& other) noexcept = default;

        TPagedVector(const TPagedVector& other) {
            Pages_.reserve(other.Pages_.size());
            for (auto& ptr : other.Pages_) {
                Pages_.emplace_back(MakeHolder<TPage>(*ptr));
            }
        }

        template <typename TIter>
        TPagedVector(TIter b, TIter e) {
            append(b, e);
        }

        TPagedVector& operator=(const TPagedVector& other) {
            if (this != &other) {
                TPagedVector tmp(other);
                swap(tmp);
            }
            return *this;
        }

        TPagedVector& operator=(TPagedVector&& other) noexcept = default;

        iterator begin() {
            return iterator(this, 0);
        }

        const_iterator begin() const {
            return const_iterator((TSelf*)this, 0);
        }

        iterator end() {
            return iterator(this, size());
        }

        const_iterator end() const {
            return const_iterator((TSelf*)this, size());
        }

        reverse_iterator rbegin() {
            return reverse_iterator(end());
        }

        const_reverse_iterator rbegin() const {
            return const_reverse_iterator(end());
        }

        reverse_iterator rend() {
            return reverse_iterator(begin());
        }

        const_reverse_iterator rend() const {
            return const_reverse_iterator(begin());
        }

        void swap(TSelf& v) {
            Pages_.swap(v.Pages_);
        }

    private:
        static size_t PageNumber(size_t idx) {
            return idx / PageSize;
        }

        static size_t InPageIndex(size_t idx) {
            return idx % PageSize;
        }

        static size_t Index(size_t pnum, size_t poff) {
            return pnum * PageSize + poff;
        }

        TPage& PageAt(size_t pnum) const {
            return *Pages_.at(pnum);
        }

        TPage& CurrentPage() const {
            return *Pages_.back();
        }

        size_t CurrentPageSize() const {
            return Pages_.empty() ? 0 : CurrentPage().size();
        }

        size_t NPages() const {
            return Pages_.size();
        }

        void AllocateNewPage() {
            Pages_.emplace_back(MakeHolder<TPage>());
            CurrentPage().reserve(PageSize);
        }

        void MakeNewPage() {
            AllocateNewPage();
            CurrentPage().resize(PageSize);
        }

        void PrepareAppend() {
            if (Pages_.empty() || CurrentPage().size() >= PageSize) {
                AllocateNewPage();
            }
        }

    public:
        size_t size() const {
            return Pages_.empty() ? 0 : (NPages() - 1) * PageSize + CurrentPage().size();
        }

        bool empty() const {
            return Pages_.empty() || (1 == NPages() && CurrentPage().empty());
        }

        explicit operator bool() const noexcept {
            return !empty();
        }

        template <typename... Args>
        reference emplace_back(Args&&... args) {
            PrepareAppend();
            return CurrentPage().emplace_back(std::forward<Args>(args)...);
        }

        void push_back(const_reference t) {
            PrepareAppend();
            CurrentPage().push_back(t);
        }

        void pop_back() {
            if (CurrentPage().empty()) {
                Pages_.pop_back();
            }
            CurrentPage().pop_back();
        }

        template <typename TIter>
        void append(TIter b, TIter e) {
            size_t sz = e - b;
            size_t sz1 = Min<size_t>(sz, PageSize - CurrentPageSize());
            size_t sz2 = (sz - sz1) / PageSize;
            size_t sz3 = (sz - sz1) % PageSize;

            if (sz1) {
                PrepareAppend();
                TPage& p = CurrentPage();
                p.insert(p.end(), b, b + sz1);
            }

            for (size_t i = 0; i < sz2; ++i) {
                AllocateNewPage();
                TPage& p = CurrentPage();
                p.insert(p.end(), b + sz1 + i * PageSize, b + sz1 + (i + 1) * PageSize);
            }

            if (sz3) {
                AllocateNewPage();
                TPage& p = CurrentPage();
                p.insert(p.end(), b + sz1 + sz2 * PageSize, e);
            }
        }

        iterator erase(iterator it) {
            const size_t pnum = PageNumber(it.Offset_);
            const size_t pidx = InPageIndex(it.Offset_);

            if (CurrentPage().empty()) {
                Pages_.pop_back();
            }

            auto currentPageIt = Pages_.begin() + pnum;

            (*currentPageIt)->erase((*currentPageIt)->begin() + pidx);

            for (auto nextPageIt = currentPageIt + 1; nextPageIt != Pages_.end(); currentPageIt = nextPageIt, ++nextPageIt) {
                (*currentPageIt)->push_back(std::move((**nextPageIt)[0]));
                (*nextPageIt)->erase((*nextPageIt)->begin());
            }

            return it;
        }

        iterator erase(iterator b, iterator e) {
            // todo : suboptimal!
            while (b != e) {
                b = erase(b);
                --e;
            }

            return b;
        }

        iterator insert(iterator it, const value_type& v) {
            size_t pnum = PageNumber(it.Offset_);
            size_t pidx = InPageIndex(it.Offset_);

            PrepareAppend();

            for (size_t p = NPages() - 1; p > pnum; --p) {
                PageAt(p).insert(PageAt(p).begin(), PageAt(p - 1).back());
                PageAt(p - 1).pop_back();
            }

            PageAt(pnum).insert(PageAt(pnum).begin() + pidx, v);
            return it;
        }

        template <typename TIter>
        void insert(iterator it, TIter b, TIter e) {
            // todo : suboptimal!
            for (; b != e; ++b, ++it) {
                it = insert(it, *b);
            }
        }

        reference front() {
            return Pages_.front()->front();
        }

        const_reference front() const {
            return Pages_.front()->front();
        }

        reference back() {
            return CurrentPage().back();
        }

        const_reference back() const {
            return CurrentPage().back();
        }

        void clear() {
            Pages_.clear();
        }

        void resize(size_t sz) {
            if (sz == size()) {
                return;
            }

            const size_t npages = NPages();
            const size_t newwholepages = sz / PageSize;
            const size_t pagepart = sz % PageSize;
            const size_t newpages = newwholepages + bool(pagepart);

            if (npages && newwholepages >= npages) {
                CurrentPage().resize(PageSize);
            }

            if (newpages < npages) {
                Pages_.resize(newpages);
            } else {
                for (size_t i = npages; i < newpages; ++i) {
                    MakeNewPage();
                }
            }

            if (pagepart) {
                CurrentPage().resize(pagepart);
            }

            Y_ABORT_UNLESS(sz == size(), "%" PRIu64 " %" PRIu64, (ui64)sz, (ui64)size());
        }

        reference at(size_t idx) {
            return Pages_.at(PageNumber(idx))->at(InPageIndex(idx));
        }

        const_reference at(size_t idx) const {
            return Pages_.at(PageNumber(idx))->at(InPageIndex(idx));
        }

        reference operator[](size_t idx) {
            return Pages_.operator[](PageNumber(idx))->operator[](InPageIndex(idx));
        }

        const_reference operator[](size_t idx) const {
            return Pages_.operator[](PageNumber(idx))->operator[](InPageIndex(idx));
        }

        friend bool operator==(const TSelf& a, const TSelf& b) {
            return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
        }

        friend bool operator<(const TSelf& a, const TSelf& b) {
            return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
        }
    };

    namespace NPrivate {
        using TIteratorCheck = std::is_same<std::random_access_iterator_tag, std::iterator_traits<
                                                                                 TPagedVector<ui32>::iterator>::iterator_category>;
        static_assert(TIteratorCheck::value, "expect TIteratorCheck::Result");
    } // namespace NPrivate

} // namespace NPagedVector