-
Notifications
You must be signed in to change notification settings - Fork 1
/
RePairTreeHasher.h
64 lines (54 loc) · 2.15 KB
/
RePairTreeHasher.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma once
#include "Labels.h"
/// Hash a node for RePair combiner
template <typename TreeType, typename DataType>
struct NodeHasher {
/// Create hasher for a tree and its tentative Top DAG
/// \param tree The input tree
/// \param topDag An empty Top DAG
/// \param nodeIds An empty mapping from tree nodes to Top DAG clusters
NodeHasher(TreeType &tree, const TopDag<DataType> &topDag, const std::vector<int> &nodeIds) :
tree(tree), topDag(topDag), nodeIds(nodeIds), cache(tree._numNodes * 2, 0) {}
/// Hash a node
/// \param nodeId node identified by its tree node ID
void hashNode(const int nodeId) {
assert(nodeId < tree._numNodes);
tree.nodes[nodeId].hash = hashCluster(nodeIds[nodeId]);
}
/// Hash a cluster
/// \param clusterId cluster identified by its Top DAG cluster ID
/// \param returns the hash value (which is also set)
uint hashCluster(const int clusterId) {
assert(clusterId < (int)topDag.clusterToDag.size());
uint hash = 0;
const int nodeId = topDag.clusterToDag[clusterId];
const DagNode<DataType> &dagNode = topDag.nodes[nodeId];
// Hash merge type
boost_hash_combine(hash, (int)dagNode.mergeType);
// Hash label
if (dagNode.label != NULL) {
assert(dagNode.left < 0 && dagNode.right < 0);
boost_hash_combine<DataType>(hash, *dagNode.label);
} else {
assert(dagNode.left >= 0 && dagNode.right >= 0);
assert(cache[dagNode.left] > 0 && cache[dagNode.right] > 0);
boost_hash_combine(hash, cache[dagNode.left]);
boost_hash_combine(hash, cache[dagNode.right]);
}
cache[nodeId] = hash;
return hash;
}
/// Hash the entire tree in post-order
void hashTree(const int nodeId = 0) {
for (auto *edge = tree.firstEdge(nodeId); edge <= tree.lastEdge(nodeId); ++edge) {
if (edge->valid) {
hashTree(edge->headNode);
}
}
hashNode(nodeId);
}
TreeType &tree;
const TopDag<DataType> &topDag;
const std::vector<int> &nodeIds;
std::vector<uint> cache;
};