GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 82 / 0 / 82
Functions: 100.0% 58 / 0 / 58
Branches: 100.0% 28 / 0 / 28
src/tree/dfs/info/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4 #include "../../ds/lib.hpp"
5
6 namespace tifa_libs {
7
8 struct tdi_dfn {
9 vecu dfn;
10
11 protected:
12 u32 cnt{0};
13 612 CEXPE tdi_dfn(u32 n) NE : dfn(n) {}
14 42186168 void init(u32 u, u32) NE { dfn[u] = cnt++; }
15 42185862 void pre_dfs(u32, u32, auto) NE {}
16 42185862 void post_dfs(u32, u32, auto) NE {}
17 42186168 void before_return(u32, u32) NE {}
18 };
19 struct tdi_sz {
20 vecu sz;
21
22 protected:
23 612 CEXPE tdi_sz(u32 n) NE : sz(n) {}
24 42186168 void init(u32 u, u32) NE { sz[u] = 1; }
25 42185862 void pre_dfs(u32, u32, auto) NE {}
26 42185862 void post_dfs(u32 to, u32 u, auto) NE { sz[u] += sz[to]; }
27 42186168 void before_return(u32, u32) NE {}
28 };
29 struct tdi_fa {
30 vecu fa;
31
32 protected:
33 580 CEXPE tdi_fa(u32 n) NE : fa(n) {}
34 38070979 void init(u32 u, u32 f) NE { fa[u] = f; }
35 38070689 void pre_dfs(u32, u32, auto) NE {}
36 38070689 void post_dfs(u32, u32, auto) NE {}
37 38070979 void before_return(u32, u32) NE {}
38 };
39 struct tdi_dep {
40 vecu dep;
41
42 protected:
43 580 CEXPE tdi_dep(u32 n) NE : dep(n) {}
44 38070979 void init(u32, u32) NE {}
45 38070689 void pre_dfs(u32 to, u32 u, auto) NE { dep[to] = dep[u] + 1; }
46 38070689 void post_dfs(u32, u32, auto) NE {}
47 38070979 void before_return(u32, u32) NE {}
48 };
49 struct tdi_maxson : tdi_sz {
50 vecu maxson;
51
52 protected:
53 612 CEXPE tdi_maxson(u32 n) NE : tdi_sz(n), maxson(n, n) {}
54 42186168 void init(u32 u, u32 f) NE { tdi_sz::init(u, f); }
55 42185862 void pre_dfs(u32 to, u32 u, auto w) NE { tdi_sz::pre_dfs(to, u, w); }
56 42185862 void post_dfs(u32 to, u32 u, auto w) NE {
57
12/12
void tifa_libs::tdi_maxson::post_dfs<int>(unsigned int, unsigned int, int):
✓ Branch 3 taken 12196786 times.
✓ Branch 4 taken 28486976 times.
✓ Branch 8 taken 1637265 times.
✓ Branch 9 taken 10559521 times.
✓ Branch 10 taken 30124241 times.
✓ Branch 11 taken 10559521 times.
void tifa_libs::tdi_maxson::post_dfs<unsigned int>(unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 510956 times.
✓ Branch 4 taken 991144 times.
✓ Branch 8 taken 59298 times.
✓ Branch 9 taken 451658 times.
✓ Branch 10 taken 1050442 times.
✓ Branch 11 taken 451658 times.
 42185862 if (tdi_sz::post_dfs(to, u, w); maxson[u] == (u32)maxson.size() || sz[to] > sz[maxson[u]]) maxson[u] = to;
58 42185862 }
59 42186168 void before_return(u32 u, u32 f) NE { tdi_sz::before_return(u, f); }
60 };
61 struct tdi_maxdfn {
62 vecu maxdfn;
63
64 protected:
65 u32 cnt{0};
66 32 CEXPE tdi_maxdfn(u32 n) NE : maxdfn(n) {}
67 4115189 void init(u32, u32) NE { ++cnt; }
68 4115173 void pre_dfs(u32, u32, auto) NE {}
69 4115173 void post_dfs(u32, u32, auto) NE {}
70 4115189 void before_return(u32 u, u32) NE { maxdfn[u] = cnt - 1; }
71 };
72 struct tdi_euler {
73 vecu euler;
74
75 protected:
76 u32 cnt{0};
77 32 CEXPE tdi_euler(u32 n) NE : euler(n) {}
78 4115189 void init(u32 u, u32) NE { euler[cnt++] = u; }
79 4115173 void pre_dfs(u32, u32, auto) NE {}
80 4115173 void post_dfs(u32, u32, auto) NE {}
81 4115189 void before_return(u32, u32) NE {}
82 };
83 struct tdi_go {
84 vvecu go;
85
86 protected:
87 CEXP static u32 N = 21;
88 CEXPE tdi_go(u32 n) NE : go(n, vecu(N, n)) { assert(n < 1u << N); }
89 void init(u32 u, u32 f) NE {
90 go[u][0] = f;
91 for (u32 i = 1; i < N && go[u][i - 1] < go.size(); ++i) go[u][i] = go[go[u][i - 1]][i - 1];
92 }
93 void pre_dfs(u32, u32, auto) NE {}
94 void post_dfs(u32, u32, auto) NE {}
95 void before_return(u32, u32) NE {}
96 };
97 template <tree_c G>
98 struct tdi_dis {
99 using w_t = std::conditional_t<std::is_void_v<TPN G::Et>, u32, TPN G::Et>;
100 vec<w_t> dis;
101
102 protected:
103 64 CEXPE tdi_dis(u32 n) NE : dis(n) {}
104 7225528 void init(u32, u32) NE {}
105 7225496 void pre_dfs(u32 to, u32 u, auto w) NE { dis[to] = dis[u] + w; }
106 7225496 void post_dfs(u32, u32, auto) NE {}
107 7225528 void before_return(u32, u32) NE {}
108 };
109
110 template <tree_c G, class... Ts>
111 struct tree_dfs_info : Ts... {
112 using w_t = std::conditional_t<std::is_void_v<TPN G::Et>, u32, TPN G::Et>;
113 338 CEXPE tree_dfs_info(G CR tree) : Ts(tree.vsize())... { dfs(tree, tree.root); }
114
115 private:
116 49411696 void dfs(G CR g, u32 u, u32 fa = -1_u32) NE {
117 49411696 if CEXP ((Ts::init(u, fa), ...); wtree_c<G>) {
118
4/4
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_dep, tifa_libs::tdi_fa>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > const&, unsigned int, unsigned int):
✓ Branch 6 taken 3004200 times.
✓ Branch 7 taken 1502110 times.
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > >, tifa_libs::tdi_dis<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > > > >::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > > const&, unsigned int, unsigned int):
✓ Branch 6 taken 14450992 times.
✓ Branch 7 taken 7225528 times.
 26182830 for (auto [v, w] : g[u])
119
4/4
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_dep, tifa_libs::tdi_fa>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned int> > > const&, unsigned int, unsigned int):
✓ Branch 0 taken 1502100 times.
✓ Branch 1 taken 1502100 times.
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > >, tifa_libs::tdi_dis<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > > > >::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<unsigned long> > > const&, unsigned int, unsigned int):
✓ Branch 0 taken 7225496 times.
✓ Branch 1 taken 7225496 times.
 17455192 if (v != fa) (Ts::pre_dfs(v, u, w), ...), dfs(g, v, u), (Ts::post_dfs(v, u, w), ...);
120 } else
121
4/4
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_dep, tifa_libs::tdi_fa>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, unsigned int, unsigned int):
✓ Branch 6 taken 69022005 times.
✓ Branch 7 taken 36568869 times.
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_maxdfn, tifa_libs::tdi_euler>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, unsigned int, unsigned int):
✓ Branch 6 taken 8230346 times.
✓ Branch 7 taken 4115189 times.
 117936409 for (auto v : g[u])
122
4/4
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_dep, tifa_libs::tdi_fa>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, unsigned int, unsigned int):
✓ Branch 1 taken 36568589 times.
✓ Branch 2 taken 32453416 times.
tifa_libs::tree_dfs_info<tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >, tifa_libs::tdi_dfn, tifa_libs::tdi_maxson, tifa_libs::tdi_maxdfn, tifa_libs::tdi_euler>::dfs(tifa_libs::tree<tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > > const&, unsigned int, unsigned int):
✓ Branch 1 taken 4115173 times.
✓ Branch 2 taken 4115173 times.
 77252351 if ((u32)v != fa) (Ts::pre_dfs((u32)v, u, 1), ...), dfs(g, (u32)v, u), (Ts::post_dfs((u32)v, u, 1), ...);
123 49411696 (Ts::before_return(u, fa), ...);
124 49411696 }
125 };
126
127 } // namespace tifa_libs
128