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
seq/alphabetic_huffman_code.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <vector>
4 #include <array>
5 #include <cassert>
6
7 namespace wala {
8
9 // Finds an optimal alphabetic (binary) Huffman code, i.e. one that preserves the ordering of the original weights
10 // Implements the Garsia-Wachs algorithm: https://en.wikipedia.org/wiki/Garsia%E2%80%93Wachs_algorithm
11 // Returns the code specified as a sequence of depths for each input weight
12 1001 template <typename T, typename T_sum = T> std::vector<int> alphabetic_huffman_code(std::vector<T> weights) {
13 1001 int N = int(weights.size());
14
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 12 taken 1001 times.
 1001 if (N == 0) return {};
15
1/1
✓ Branch 13 → 14 taken 1001 times.
 1001 std::vector<std::array<int, 2>> ch; ch.reserve(N-1);
16
17 {
18 struct splay_node {
19 mutable splay_node* p = nullptr;
20 std::array<splay_node*, 2> c{nullptr, nullptr};
21 866764 int d() const { return this == p->c[1]; }
22
23 T_sum value;
24 T_sum max_value;
25 int idx;
26
27 271604 void update() {
28 271604 max_value = value;
29
2/2
✓ Branch 38 → 19 taken 543208 times.
✓ Branch 38 → 39 taken 271604 times.
 1358020 for (auto ch : c) {
30
4/4
✓ Branch 21 → 22 taken 256773 times.
✓ Branch 21 → 36 taken 286435 times.
✓ Branch 28 → 29 taken 156608 times.
✓ Branch 28 → 36 taken 100165 times.
 543208 if (ch && max_value < ch->max_value) max_value = ch->max_value;
31 }
32 271604 }
33
34 154852 void rot() {
35 154852 assert(p);
36
37 154852 int x = d();
38 154852 splay_node* pa = p;
39 154852 splay_node* ch = c[!x];
40
41
2/2
✓ Branch 16 → 17 taken 35997 times.
✓ Branch 16 → 20 taken 118855 times.
 154852 if (ch) ch->p = pa;
42 154852 pa->c[x] = ch;
43
44
1/2
✓ Branch 28 → 29 taken 154852 times.
✗ Branch 28 → 40 not taken.
 154852 if (pa->p) pa->p->c[pa->d()] = this;
45 154852 this->p = pa->p;
46
47 154852 this->c[!x] = pa;
48 154852 pa->p = this;
49
50 154852 pa->update();
51 154852 }
52
53 84608 void splay_no_update(splay_node* top) {
54
2/2
✓ Branch 25 → 3 taken 93013 times.
✓ Branch 25 → 26 taken 84608 times.
 177621 while (p != top) {
55
2/2
✓ Branch 7 → 8 taken 61839 times.
✓ Branch 7 → 21 taken 31174 times.
 93013 if (p->p != top) {
56
2/2
✓ Branch 14 → 15 taken 16654 times.
✓ Branch 14 → 19 taken 45185 times.
 61839 if (p->d() == d()) p->rot();
57 45185 else rot();
58 }
59 93013 rot();
60 }
61 84608 }
62 };
63
1/1
✓ Branch 16 → 17 taken 1001 times.
 1001 std::vector<splay_node> nodes(N+1);
64
2/2
✓ Branch 45 → 19 taken 31143 times.
✓ Branch 45 → 46 taken 1001 times.
 32144 for (int i = 0; i < N; i++) {
65 31143 nodes[i].p = &nodes[i+1];
66 62286 nodes[i+1].c[0] = &nodes[i];
67 31143 nodes[i].value = T_sum(weights[i]);
68 31143 nodes[i].idx = i;
69 }
70 1001 nodes[0].update();
71 1001 splay_node* cur = &nodes[1];
72
73 // We'll store our current state as the left spine of some splay tree.
74 // All vertices from cur to the root are precisely the vertices that may satisfy w[n-2] <= w[n]
75 // (all others provably satisfy w[x-2] > w[x] at all times),
76 // so cur is exactly the leftmost vertex that might satisfy w[n-2] <= w[n].
77 //
78 // We then check this condition, and if it does have w[n-2] <= w[n],
79 // we merge w[n-2] and w[n-1] and reinsert somewhere according to Garsia-Wachs,
80 // i.e. right after the last element of w[0:n-1] greater than or equal to it.
81 // Then, the newly inserted node is added to the candidate chain
82 // (exercise: prove that all other positions still satisfy w[x-2] > w[x]).
83
84
2/2
✓ Branch 461 → 51 taken 76852 times.
✓ Branch 461 → 462 taken 1001 times.
 77853 while (cur) {
85 // Note: cur is not necessarily updated
86
87 // First, grab the 2nd child of the left side of cur
88 153704 splay_node* a = cur->c[0];
89 76852 assert(a);
90
2/2
✓ Branch 79 → 61 taken 39377 times.
✓ Branch 79 → 80 taken 76852 times.
 232458 while (a->c[1]) a = a->c[1];
91
2/2
✓ Branch 88 → 89 taken 58401 times.
✓ Branch 88 → 117 taken 18451 times.
 153704 if (a->c[0]) {
92 116802 a = a->c[0];
93
2/2
✓ Branch 116 → 98 taken 41571 times.
✓ Branch 116 → 120 taken 58401 times.
 199944 while (a->c[1]) a = a->c[1];
94 } else {
95 18451 a = a->p;
96 }
97
2/2
✓ Branch 120 → 121 taken 7811 times.
✓ Branch 120 → 126 taken 69041 times.
 76852 if (a == cur) {
98 // size one, so we're done
99 7811 cur->update();
100 7811 cur = cur->p;
101 7811 continue;
102 }
103 69041 a->splay_no_update(cur);
104 138082 assert(a == cur->c[0]);
105 414246 assert(a->c[1] && !a->c[1]->c[0] && !a->c[1]->c[1]);
106
4/4
✓ Branch 188 → 189 taken 58642 times.
✓ Branch 188 → 203 taken 10399 times.
✓ Branch 195 → 196 taken 38899 times.
✓ Branch 195 → 203 taken 19743 times.
 69041 if (cur->p && cur->value < a->value) {
107 // no merging, so we're done
108 38899 a->update();
109 38899 cur->update();
110 38899 cur = cur->p;
111 38899 continue;
112 }
113
114 // Otherwise, merge a and a->c[1]
115 {
116 30142 int n_idx = N + int(ch.size());
117 90426 ch.push_back({a->idx, a->c[1]->idx});
118 30142 a->idx = n_idx;
119 }
120 60284 a->value += a->c[1]->value;
121 60284 a->c[1]->p = nullptr;
122 60284 a->c[1] = nullptr;
123
124 // Now, insert a right after the first guy b which is b.v >= a.v
125
4/4
✓ Branch 273 → 274 taken 25774 times.
✓ Branch 273 → 289 taken 4368 times.
✓ Branch 288 → 289 taken 10207 times.
✓ Branch 288 → 317 taken 15567 times.
 86058 if (!a->c[0] || a->c[0]->max_value < a->value) {
126 43725 a->c[1] = a->c[0];
127 29150 a->c[0] = nullptr;
128 14575 a->update();
129 // Don't recurse on a, since it has no left child
130 14575 continue;
131 }
132
133 31134 splay_node* b = a->c[0];
134 while (true) {
135 41710 assert(b);
136 41710 assert(!(b->max_value < a->value));
137
4/4
✓ Branch 345 → 346 taken 13446 times.
✓ Branch 345 → 371 taken 28264 times.
✓ Branch 361 → 362 taken 4090 times.
✓ Branch 361 → 371 taken 9356 times.
 96866 if (!b->c[1] || b->c[1]->max_value < a->value) {
138
2/2
✓ Branch 377 → 378 taken 22053 times.
✓ Branch 377 → 396 taken 15567 times.
 37620 if (b->value < a->value) {
139 44106 assert(b->c[0]);
140 44106 b = b->c[0];
141 } else {
142 break;
143 }
144 } else {
145 8180 b = b->c[1];
146 }
147 }
148 15567 b->splay_no_update(a);
149 31134 assert(b == a->c[0]);
150
2/2
✓ Branch 417 → 418 taken 8989 times.
✓ Branch 417 → 430 taken 6578 times.
 40123 if (b->c[1]) b->c[1]->p = a;
151 46701 a->c[1] = b->c[1];
152 31134 b->c[1] = nullptr;
153 15567 b->update();
154 15567 cur = a;
155 15567 continue;
156 }
157 1001 }
158
159 // Reconstruct depths
160 1001 assert(int(ch.size()) == N-1);
161
1/1
✓ Branch 485 → 486 taken 1001 times.
 1001 std::vector<int> res(2*N-1, -1);
162 1001 res[2*N-2] = 0;
163
2/2
✓ Branch 525 → 492 taken 30142 times.
✓ Branch 525 → 526 taken 1001 times.
 31143 for (int i = 2*N-2; i >= N; i--) {
164 30142 assert(res[i] != -1);
165 60284 res[ch[i-N][0]] = res[i] + 1;
166 60284 res[ch[i-N][1]] = res[i] + 1;
167 }
168
1/1
✓ Branch 526 → 527 taken 1001 times.
 1001 res.resize(N);
169 1001 return res;
170 2002 }
171
172 // Returns the lca array of length N - 1, suitable for building a Cartesian tree
173 1001 inline std::vector<int> binary_code_depths_to_lca_depths(std::vector<int> depths) {
174 1001 int N = int(depths.size());
175
1/4
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 12 taken 1001 times.
wala::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 {};
176
1/2
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 13 → 14 taken 1001 times.
wala::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);
177
1/2
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 15 → 16 taken 1001 times.
wala::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);
178
2/4
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 55 → 20 taken 31143 times.
✓ Branch 55 → 56 taken 1001 times.
wala::binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 39 → 9 not taken.
✗ Branch 39 → 40 not taken.
 63287 for (int v : depths) {
179
4/10
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 26 → 27 taken 53721 times.
✓ Branch 26 → 33 taken 7564 times.
✓ Branch 30 → 31 taken 30142 times.
✓ Branch 30 → 33 taken 23579 times.
wala::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.
 61285 while (!stk.empty() && stk.back() == v) {
180 30142 stk.pop_back();
181 30142 v--;
182 }
183 31143 assert(stk.empty() || stk.back() < v);
184
2/5
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 40 → 41 taken 30142 times.
✓ Branch 40 → 46 taken 1001 times.
wala::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.
 61285 if (v != 0) res.push_back(v-1);
185
1/2
wala::binary_code_depths_to_lca_depths(std::__debug::vector<int, std::allocator<int> >):
✓ Branch 46 → 47 taken 31143 times.
wala::binary_code_depths_to_lca_depths(std::vector<int, std::allocator<int> >):
✗ Branch 29 → 30 not taken.
 31143 stk.push_back(v);
186 2002 }
187 1001 assert(int(stk.size()) == 1 && stk.back() == 0);
188 1001 return res;
189 2002 }
190
191 } // namespace wala
192