CPTH/headers/MonotonousQueue.h at master · ouuan/CPTH · GitHub

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Get more headers at https://github.com/ouuan/CPTH

#ifndef CPTH_MONOTONOUSQUEUE
#define CPTH_MONOTONOUSQUEUE

#include <cassert>
#include <cstddef>
#include <functional>
#include <vector>

namespace CPTH
{
template <typename T, typename cmp = std::less<T>>
class MonotonousQueue
{
   public:
    explicit MonotonousQueue(std::function<bool(const T &)> validate = [](const T &) {
        return true;
    });

    void setValidate(std::function<bool(const T &)> validate);

    bool empty();

    void clear();

    void push(const T &x);

    T top();

   private:
    bool m_empty() const;

    void removeInvalidElements();

    std::vector<T> a;
    size_t head = 0;
    std::function<bool(const T &)> m_validate;
};

template <typename T, typename cmp>
MonotonousQueue<T, cmp>::MonotonousQueue(std::function<bool(const T &)> validate)
    : m_validate(validate)
{}

template <typename T, typename cmp>
void MonotonousQueue<T, cmp>::setValidate(std::function<bool(const T &)> validate)
{
    m_validate = validate;
}

template <typename T, typename cmp>
bool MonotonousQueue<T, cmp>::empty()
{
    removeInvalidElements();
    return m_empty();
}

template <typename T, typename cmp>
void MonotonousQueue<T, cmp>::clear()
{
    a.clear();
    head = 0;
}

template <typename T, typename cmp>
void MonotonousQueue<T, cmp>::push(const T &x)
{
    while (!m_empty() && cmp()(a.back(), x))
        a.pop_back();
    a.push_back(x);
}

template <typename T, typename cmp>
T MonotonousQueue<T, cmp>::top()
{
    removeInvalidElements();
    assert(!m_empty());
    return a[head];
}

template <typename T, typename cmp>
bool MonotonousQueue<T, cmp>::m_empty() const
{
    return head >= a.size();
}

template <typename T, typename cmp>
void MonotonousQueue<T, cmp>::removeInvalidElements()
{
    while (!m_empty() && !m_validate(a[head]))
        ++head;
}

}  // namespace CPTH

#endif  // CPTH_MONOTONOUSQUEUE