GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 88.9% 112 / 0 / 126
Functions: 85.7% 6 / 0 / 7
Branches: 76.5% 62 / 40 / 121
alphabetic_huffman_code.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <vector>
4 #include <array>
5 #include <cassert>
6
7 // Finds an optimal alphabetic (binary) Huffman code, i.e. one that preserves the ordering of the original weights
8 // Implements the Garsia-Wachs algorithm: https://en.wikipedia.org/wiki/Garsia%E2%80%93Wachs_algorithm
9 // Returns the code specified as a sequence of depths for each input weight
10 1001 template <typename T, typename T_sum = T> std::vector<int> alphabetic_huffman_code(std::vector<T> weights) {
11 1001 int N = int(weights.size());
12
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 12 taken 1001 times.
 1001 if (N == 0) return {};
13
1/1
✓ Branch 13 → 14 taken 1001 times.
 1001 std::vector<std::array<int, 2>> ch; ch.reserve(N-1);
14
15 {
16 struct splay_node {
17 mutable splay_node* p = nullptr;
18 std::array<splay_node*, 2> c{nullptr, nullptr};
19 840948 int d() const { return this == p->c[1]; }
20
21 T_sum value;
22 T_sum max_value;
23 int idx;
24
25 263287 void update() {
26 263287 max_value = value;
27
2/2
✓ Branch 38 → 19 taken 526574 times.
✓ Branch 38 → 39 taken 263287 times.
 1316435 for (auto ch : c) {
28
4/4
✓ Branch 21 → 22 taken 248836 times.
✓ Branch 21 → 36 taken 277738 times.
✓ Branch 28 → 29 taken 152134 times.
✓ Branch 28 → 36 taken 96702 times.
 526574 if (ch && max_value < ch->max_value) max_value = ch->max_value;
29 }
30 263287 }
31
32 150071 void rot() {
33 150071 assert(p);
34
35 150071 int x = d();
36 150071 splay_node* pa = p;
37 150071 splay_node* ch = c[!x];
38
39
2/2
✓ Branch 16 → 17 taken 34422 times.
✓ Branch 16 → 20 taken 115649 times.
 150071 if (ch) ch->p = pa;
40 150071 pa->c[x] = ch;
41
42
1/2
✓ Branch 28 → 29 taken 150071 times.
✗ Branch 28 → 40 not taken.
 150071 if (pa->p) pa->p->c[pa->d()] = this;
43 150071 this->p = pa->p;
44
45 150071 this->c[!x] = pa;
46 150071 pa->p = this;
47
48 150071 pa->update();
49 150071 }
50
51 82199 void splay_no_update(splay_node* top) {
52
2/2
✓ Branch 25 → 3 taken 89905 times.
✓ Branch 25 → 26 taken 82199 times.
 172104 while (p != top) {
53
2/2
✓ Branch 7 → 8 taken 60166 times.
✓ Branch 7 → 21 taken 29739 times.
 89905 if (p->p != top) {
54
2/2
✓ Branch 14 → 15 taken 16148 times.
✓ Branch 14 → 19 taken 44018 times.
 60166 if (p->d() == d()) p->rot();
55 44018 else rot();
56 }
57 89905 rot();
58 }
59 82199 }
60 };
61
1/1
✓ Branch 16 → 17 taken 1001 times.
 1001 std::vector<splay_node> nodes(N+1);
62
2/2
✓ Branch 45 → 19 taken 30016 times.
✓ Branch 45 → 46 taken 1001 times.
 31017 for (int i = 0; i < N; i++) {
63 30016 nodes[i].p = &nodes[i+1];
64 60032 nodes[i+1].c[0] = &nodes[i];
65 30016 nodes[i].value = T_sum(weights[i]);
66 30016 nodes[i].idx = i;
67 }
68 1001 nodes[0].update();
69 1001 splay_node* cur = &nodes[1];
70
71 // We'll store our current state as the left spine of some splay tree.
72 // All vertices from cur to the root are precisely the vertices that may satisfy w[n-2] <= w[n]
73 // (all others provably satisfy w[x-2] > w[x] at all times),
74 // so cur is exactly the leftmost vertex that might satisfy w[n-2] <= w[n].
75 //
76 // We then check this condition, and if it does have w[n-2] <= w[n],
77 // we merge w[n-2] and w[n-1] and reinsert somewhere according to Garsia-Wachs,
78 // i.e. right after the last element of w[0:n-1] greater than or equal to it.
79 // Then, the newly inserted node is added to the candidate chain
80 // (exercise: prove that all other positions still satisfy w[x-2] > w[x]).
81
82
2/2
✓ Branch 461 → 51 taken 74244 times.
✓ Branch 461 → 462 taken 1001 times.
 75245 while (cur) {
83 // Note: cur is not necessarily updated
84
85 // First, grab the 2nd child of the left side of cur
86 148488 splay_node* a = cur->c[0];
87 74244 assert(a);
88
2/2
✓ Branch 79 → 61 taken 38104 times.
✓ Branch 79 → 80 taken 74244 times.
 224696 while (a->c[1]) a = a->c[1];
89
2/2
✓ Branch 88 → 89 taken 56597 times.
✓ Branch 88 → 117 taken 17647 times.
 148488 if (a->c[0]) {
90 113194 a = a->c[0];
91
2/2
✓ Branch 116 → 98 taken 40648 times.
✓ Branch 116 → 120 taken 56597 times.
 194490 while (a->c[1]) a = a->c[1];
92 } else {
93 17647 a = a->p;
94 }
95
2/2
✓ Branch 120 → 121 taken 7258 times.
✓ Branch 120 → 126 taken 66986 times.
 74244 if (a == cur) {
96 // size one, so we're done
97 7258 cur->update();
98 7258 cur = cur->p;
99 7258 continue;
100 }
101 66986 a->splay_no_update(cur);
102 133972 assert(a == cur->c[0]);
103 401916 assert(a->c[1] && !a->c[1]->c[0] && !a->c[1]->c[1]);
104
4/4
✓ Branch 188 → 189 taken 56732 times.
✓ Branch 188 → 203 taken 10254 times.
✓ Branch 195 → 196 taken 37971 times.
✓ Branch 195 → 203 taken 18761 times.
 66986 if (cur->p && cur->value < a->value) {
105 // no merging, so we're done
106 37971 a->update();
107 37971 cur->update();
108 37971 cur = cur->p;
109 37971 continue;
110 }
111
112 // Otherwise, merge a and a->c[1]
113 {
114 29015 int n_idx = N + int(ch.size());
115 87045 ch.push_back({a->idx, a->c[1]->idx});
116 29015 a->idx = n_idx;
117 }
118 58030 a->value += a->c[1]->value;
119 58030 a->c[1]->p = nullptr;
120 58030 a->c[1] = nullptr;
121
122 // Now, insert a right after the first guy b which is b.v >= a.v
123
4/4
✓ Branch 273 → 274 taken 25203 times.
✓ Branch 273 → 289 taken 3812 times.
✓ Branch 288 → 289 taken 9990 times.
✓ Branch 288 → 317 taken 15213 times.
 83233 if (!a->c[0] || a->c[0]->max_value < a->value) {
124 41406 a->c[1] = a->c[0];
125 27604 a->c[0] = nullptr;
126 13802 a->update();
127 // Don't recurse on a, since it has no left child
128 13802 continue;
129 }
130
131 30426 splay_node* b = a->c[0];
132 while (true) {
133 40324 assert(b);
134 40324 assert(!(b->max_value < a->value));
135
4/4
✓ Branch 345 → 346 taken 12894 times.
✓ Branch 345 → 371 taken 27430 times.
✓ Branch 361 → 362 taken 3861 times.
✓ Branch 361 → 371 taken 9033 times.
 93542 if (!b->c[1] || b->c[1]->max_value < a->value) {
136
2/2
✓ Branch 377 → 378 taken 21250 times.
✓ Branch 377 → 396 taken 15213 times.
 36463 if (b->value < a->value) {
137 42500 assert(b->c[0]);
138 42500 b = b->c[0];
139 } else {
140 break;
141 }
142 } else {
143 7722 b = b->c[1];
144 }
145 }
146 15213 b->splay_no_update(a);
147 30426 assert(b == a->c[0]);
148
2/2
✓ Branch 417 → 418 taken 8706 times.
✓ Branch 417 → 430 taken 6507 times.
 39132 if (b->c[1]) b->c[1]->p = a;
149 45639 a->c[1] = b->c[1];
150 30426 b->c[1] = nullptr;
151 15213 b->update();
152 15213 cur = a;
153 15213 continue;
154 }
155 1001 }
156
157 // Reconstruct depths
158 1001 assert(int(ch.size()) == N-1);
159
1/1
✓ Branch 485 → 486 taken 1001 times.
 1001 std::vector<int> res(2*N-1, -1);
160 1001 res[2*N-2] = 0;
161
2/2
✓ Branch 525 → 492 taken 29015 times.
✓ Branch 525 → 526 taken 1001 times.
 30016 for (int i = 2*N-2; i >= N; i--) {
162 29015 assert(res[i] != -1);
163 58030 res[ch[i-N][0]] = res[i] + 1;
164 58030 res[ch[i-N][1]] = res[i] + 1;
165 }
166
1/1
✓ Branch 526 → 527 taken 1001 times.
 1001 res.resize(N);
167 1001 return res;
168 2002 }
169
170 // Returns the lca array of length N - 1, suitable for building a Cartesian tree
171 1001 inline std::vector<int> binary_code_depths_to_lca_depths(std::vector<int> depths) {
172 1001 int N = int(depths.size());
173
1/4
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 12 taken 1001 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
 1001 if (N == 0) return {};
174
1/2
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 13 → 14 taken 1001 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 5 → 6 not taken.
 1001 std::vector<int> res; res.reserve(N-1);
175
1/2
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 15 → 16 taken 1001 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 6 → 7 not taken.
 1001 std::vector<int> stk; stk.reserve(N);
176
2/4
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 55 → 20 taken 30016 times.
✓ Branch 55 → 56 taken 1001 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 39 → 9 not taken.
✗ Branch 39 → 40 not taken.
 61033 for (int v : depths) {
177
4/10
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 26 → 27 taken 52029 times.
✓ Branch 26 → 33 taken 7002 times.
✓ Branch 30 → 31 taken 29015 times.
✓ Branch 30 → 33 taken 23014 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 15 → 16 not taken.
✗ Branch 15 → 19 not taken.
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 19 not taken.
✗ Branch 20 → 12 not taken.
✗ Branch 20 → 21 not taken.
 59031 while (!stk.empty() && stk.back() == v) {
178 29015 stk.pop_back();
179 29015 v--;
180 }
181 30016 assert(stk.empty() || stk.back() < v);
182
2/5
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 40 → 41 taken 29015 times.
✓ Branch 40 → 46 taken 1001 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 26 → 27 not taken.
✗ Branch 26 → 29 not taken.
✗ Branch 27 → 28 not taken.
 59031 if (v != 0) res.push_back(v-1);
183
1/2
binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 46 → 47 taken 30016 times.
binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 29 → 30 not taken.
 30016 stk.push_back(v);
184 2002 }
185 1001 assert(int(stk.size()) == 1 && stk.back() == 0);
186 1001 return res;
187 2002 }
188