src/ds/dq/w/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T, auto e, auto op> | ||
| 8 | requires requires(T a, T b) { | ||
| 9 | { e() } -> std::same_as<T>; | ||
| 10 | { op(a, b) } -> std::same_as<T>; | ||
| 11 | } | ||
| 12 | class deque_with_w { | ||
| 13 | // front [q[0].back q[0].front][q[1].front q[1].back] back | ||
| 14 | vvec<T> q, s; | ||
| 15 | 76268 | CEXP void bf() NE { | |
| 16 | 76268 | s[0].resize(q[0].size() + 1), s[0][0] = e(); | |
| 17 |
2/2✓ Branch 10 taken 509811 times.
✓ Branch 11 taken 76268 times.
|
586079 | flt_ (u32, i, 0, (u32)q[0].size()) s[0][i + 1] = op(q[0][i], s[0][i]); |
| 18 | 76268 | s[1].resize(q[1].size() + 1), s[1][0] = e(); | |
| 19 |
2/2✓ Branch 10 taken 510114 times.
✓ Branch 11 taken 76268 times.
|
586382 | flt_ (u32, i, 0, (u32)q[1].size()) s[1][i + 1] = op(s[1][i], q[1][i]); |
| 20 | 76268 | } | |
| 21 | |||
| 22 | public: | ||
| 23 | 80 | CEXPE deque_with_w() NE : q(2), s(2) { bf(); } | |
| 24 | |||
| 25 | 1456994 | CEXP void push_front(T x) NE { | |
| 26 |
1/2✓ Branch 4 taken 1456994 times.
✗ Branch 5 not taken.
|
1456994 | if (q[0].push_back(x); s[0].size()) s[0].push_back(op(x, s[0].back())); |
| 27 | ✗ | else s[0].push_back(x); | |
| 28 | 1456994 | } | |
| 29 | 1459156 | CEXP void push_back(T x) NE { | |
| 30 |
1/2✓ Branch 4 taken 1459156 times.
✗ Branch 5 not taken.
|
1459156 | if (q[1].push_back(x); s[1].size()) s[1].push_back(op(s[1].back(), x)); |
| 31 | ✗ | else s[1].push_back(x); | |
| 32 | 1459156 | } | |
| 33 | 532025 | CEXP T pop_front() NE { | |
| 34 |
2/2✓ Branch 2 taken 37862 times.
✓ Branch 3 taken 494163 times.
|
532025 | if (q[0].empty()) { |
| 35 | 37862 | cu32 _ = u32(q[1].size()) / 2; | |
| 36 | 37862 | q[0] = vec<T>(q[1].rbegin() + _, q[1].rend()); | |
| 37 | 37862 | q[1] = vec<T>(end(q[1]) - _, end(q[1])); | |
| 38 | 37862 | bf(); | |
| 39 | } | ||
| 40 | 532025 | const T ret = q[0].back(); | |
| 41 | 532025 | q[0].pop_back(), s[0].pop_back(); | |
| 42 | 532025 | return ret; | |
| 43 | } | ||
| 44 | 531116 | CEXP T pop_back() NE { | |
| 45 |
2/2✓ Branch 2 taken 38390 times.
✓ Branch 3 taken 492726 times.
|
531116 | if (q[1].empty()) { |
| 46 | 38390 | cu32 _ = u32(q[0].size()) / 2; | |
| 47 | 38390 | q[1] = vec<T>(q[0].rbegin() + _, q[0].rend()); | |
| 48 | 38390 | q[0] = vec<T>(end(q[0]) - _, end(q[0])); | |
| 49 | 38390 | bf(); | |
| 50 | } | ||
| 51 | 531116 | const T ret = q[1].back(); | |
| 52 | 531116 | q[1].pop_back(), s[1].pop_back(); | |
| 53 | 531116 | return ret; | |
| 54 | } | ||
| 55 | 1427025 | CEXP T w() NE { return op(s[0].back(), s[1].back()); } | |
| 56 | }; | ||
| 57 | |||
| 58 | } // namespace tifa_libs | ||
| 59 |