src/edh/huffman/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/heap/radix/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T = u64> | ||
| 8 | class huffman { | ||
| 9 | struct TIFA { | ||
| 10 | T weight; | ||
| 11 | vecu ch; | ||
| 12 | 3636 | CEXP TIFA(T weight = T{}, u32 child_cnt = 0) NE : weight(weight), ch(child_cnt) {} | |
| 13 | }; | ||
| 14 | u32 cnt_w, cnt_l{}, ch_sz; | ||
| 15 | vec<TIFA> data; | ||
| 16 | |||
| 17 | template <class Res, class Op> | ||
| 18 | 42 | CEXP vec<Res> run(Op&& operate) CNE { | |
| 19 | 42 | vec<Res> ret(cnt_w); | |
| 20 | 42 | std::queue<std::pair<u32, Res>> q; | |
| 21 | 42 | q.emplace(data.size() - 1, Res{}); | |
| 22 |
2/2✓ Branch 2 taken 888 times.
✓ Branch 3 taken 42 times.
|
1818 | while (!q.empty()) { |
| 23 | 888 | auto [now_idx, now_code] = q.front(); | |
| 24 | 888 | auto& ch = data[now_idx].ch; | |
| 25 | 888 | q.pop(); | |
| 26 |
2/2✓ Branch 0 taken 1776 times.
✓ Branch 1 taken 888 times.
|
2664 | flt_ (u32, i, 0, ch_sz) |
| 27 |
2/2✓ Branch 1 taken 930 times.
✓ Branch 2 taken 846 times.
|
1776 | if (auto&& next_child = ch[i]; next_child < cnt_l) { |
| 28 |
1/2✓ Branch 0 taken 930 times.
✗ Branch 1 not taken.
|
930 | if (next_child < cnt_w) ret[next_child] = operate(now_code, i); |
| 29 | 930 | continue; | |
| 30 | 846 | } else q.emplace(next_child, operate(now_code, i)); | |
| 31 | } | ||
| 32 | 42 | return ret; | |
| 33 | 42 | } | |
| 34 | |||
| 35 | public: | ||
| 36 | 42 | CEXPE huffman(vec<T> CR weights, u32 child_sz = 2_u32) NE : cnt_w((u32)weights.size()), ch_sz{child_sz}, data() { | |
| 37 |
2/4✓ Branch 0 taken 42 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
|
42 | assert(1 < child_sz && child_sz < weights.size()); |
| 38 |
2/2✓ Branch 6 taken 930 times.
✓ Branch 7 taken 42 times.
|
972 | for (T now : weights) data.emplace_back(now); |
| 39 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 42 times.
|
42 | flt_ (u32, i, 0, ((ch_sz - 1) - ((cnt_w - 1) % (ch_sz - 1))) % (ch_sz - 1)) data.emplace_back(); |
| 40 | 42 | cnt_l = (u32)data.size(); | |
| 41 | 42 | rheap<T, u32> q; | |
| 42 |
2/2✓ Branch 3 taken 930 times.
✓ Branch 4 taken 42 times.
|
972 | flt_ (u32, i, 0, (u32)data.size()) q.emplace(data[i].weight, i); |
| 43 |
2/2✓ Branch 1 taken 888 times.
✓ Branch 2 taken 42 times.
|
930 | while (q.size() > 1) { |
| 44 | 888 | data.emplace_back(T{}, ch_sz); | |
| 45 |
2/2✓ Branch 0 taken 1776 times.
✓ Branch 1 taken 888 times.
|
2664 | flt_ (u32, i, 0, ch_sz) { |
| 46 | 1776 | auto [now_weight, now_idx] = q.top(); | |
| 47 | 1776 | data.back().weight += now_weight, data.back().ch[i] = now_idx, q.pop(); | |
| 48 | } | ||
| 49 | 888 | q.emplace(data.back().weight, u32(data.size() - 1)); | |
| 50 | } | ||
| 51 | 42 | } | |
| 52 | |||
| 53 | 42 | ND CEXP vec<strn> encode(strnv char_set = "01") CNE { | |
| 54 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 42 times.
|
42 | assert(char_set.size() == ch_sz); |
| 55 | 42 | return run<strn>([&](strn pre_code, u32 idx) NE { | |
| 56 | 1776 | pre_code += char_set[idx]; | |
| 57 | 1776 | return pre_code; | |
| 58 | 42 | }); | |
| 59 | } | ||
| 60 | ND CEXP vecu depths() CNE { | ||
| 61 | return run<u32>([](u32 pre_depth, u32) NE { return pre_depth + 1; }); | ||
| 62 | } | ||
| 63 | }; | ||
| 64 | |||
| 65 | } // namespace tifa_libs | ||
| 66 |