src/ds/mono_queue/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/num/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T, class Comp = std::less<T>> | ||
| 8 | class mono_queue { | ||
| 9 | static CEXP Comp compare{}; | ||
| 10 | |||
| 11 | cu32 k; | ||
| 12 | u32 i{0}; | ||
| 13 | std::deque<std::pair<T, u32>> q; | ||
| 14 | |||
| 15 | public: | ||
| 16 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 42 times.
|
42 | CEXPE mono_queue(u32 k) NE : k{k} { assert(k > 0); } |
| 17 | // @return minimum of last k (at most) pushed elements | ||
| 18 | 18428285 | CEXP T CR push(cT_(T) x) NE { | |
| 19 |
6/6✓ Branch 1 taken 18428243 times.
✓ Branch 2 taken 42 times.
✓ Branch 4 taken 4856634 times.
✓ Branch 5 taken 13571609 times.
✓ Branch 6 taken 4856634 times.
✓ Branch 7 taken 13571651 times.
|
18428285 | if (!q.empty() && q.front().second + k == i) q.pop_front(); |
| 20 |
6/6✓ Branch 2 taken 29105349 times.
✓ Branch 3 taken 2866159 times.
✓ Branch 6 taken 13543223 times.
✓ Branch 7 taken 15562126 times.
✓ Branch 8 taken 13543223 times.
✓ Branch 9 taken 18428285 times.
|
31971508 | while (!q.empty() && compare(x, q.back().first)) q.pop_back(); |
| 21 | 18428285 | q.emplace_back(x, i++); | |
| 22 | 18428285 | return q.front().first; | |
| 23 | } | ||
| 24 | }; | ||
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |