1 #pragma once
2 
3 #include "../core.hh"
4 #include <functional>
5 
6 using NodeAction = std::function<void(NodeID)>;
7 
8 namespace cpprofiler
9 {
10 namespace tree
11 {
12 class NodeTree;
13 }
14 } // namespace cpprofiler
15 
16 namespace cpprofiler
17 {
18 namespace utils
19 {
20 
21 /// Count all descendants of `n`
22 int count_descendants(const tree::NodeTree &nt, NodeID n);
23 
24 /// Compute the node's depth (the distance to the root)
25 int calculate_depth(const tree::NodeTree &nt, NodeID nid);
26 
27 /// Apply `action` to `root` and to all of its descendants
28 void apply_below(const tree::NodeTree &nt, NodeID root, const NodeAction &action);
29 
30 /// Apply `action` to nodes in the order that corresponds to a pre-order traversal
31 void pre_order_apply(const tree::NodeTree &nt, NodeID start, const NodeAction &action);
32 
33 /// Inquire if the node is the right-most child
34 bool is_right_most_child(const tree::NodeTree &nt, NodeID nid);
35 
36 /// Return a list of nodes under `nid` (including `nid`)
37 std::vector<NodeID> nodes_below(const tree::NodeTree &tree, NodeID nid);
38 
39 /// Return node identifires in an arbitrary order
40 std::vector<NodeID> any_order(const tree::NodeTree &tree);
41 
42 /// Return node identifires in the order that corresponds to a pre-order traversal
43 std::vector<NodeID> pre_order(const tree::NodeTree &tree);
44 
45 /// Return node identifires in the order that corresponds to a post-order traversal
46 std::vector<NodeID> post_order(const tree::NodeTree &tree);
47 
48 /// Calculate subtree sizes for every node in the tree
49 std::vector<int> calc_subtree_sizes(const tree::NodeTree &tree);
50 
51 } // namespace utils
52 } // namespace cpprofiler