1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma once


#include <algorithm><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <iterator><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.


#include "snippet/aliases.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"

#include "structure/grid.hpp"

#include "adaptor/vector.hpp"


namespace uni {


template<bool STRICT, class T, class container = vector<T>>
struct lis : container {
    using size_type = typename internal::size_t;

    std::vector<size_type> indices, positions;

    lis() noexcept = default;

    template<std::ranges::input_range R>
    explicit lis(R&& range) noexcept(NO_EXCEPT) : lis(ALL(range)) {}

    template<std::input_iterator I, std::sentinel_for<I> S>
    lis(I first, S last) noexcept(NO_EXCEPT) : positions(std::ranges::distance(first, last), -1) {
        this->reserve(std::ranges::distance(first, last));

        size_type pos = 0;
        for(auto itr=first; itr!=last; ++pos, ++itr) {
            typename container::iterator bound;

            if constexpr(STRICT) bound = std::ranges::lower_bound(*this, *itr);
            else bound = std::ranges::upper_bound(*this, *itr);

            this->positions[pos] = static_cast<size_type>(std::ranges::distance(std::ranges::begin(*this), bound));

            if(std::ranges::end(*this) == bound) this->emplace_back(*itr);
            else *bound = *itr;
        }

        size_type target = std::ranges::max(this->positions);

        for(size_type i = static_cast<size_type>(this->positions.size()); --i >= 0;){
            if(this->positions[i] == target) {
                this->operator[](target) = *(first + i);
                this->indices.emplace_back(i);
                --target;
            }
        }

        std::ranges::reverse(this->indices);
    }
};


} // namespace uni