VGalaxies commented on code in PR #16789:
URL: https://github.com/apache/iotdb/pull/16789#discussion_r2609400926
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/pipe/datastructure/pattern/TreePattern.java:
##########
@@ -649,4 +758,86 @@ public static int[] checkAndLogPatternCoverage(
return new int[] {coveredCount, inclusionPaths.size()};
}
+
+ /** A specialized Trie to efficiently check path coverage. */
+ private static class PatternTrie {
+ private final TrieNode root = new TrieNode();
+
+ private static class TrieNode {
+ // Children nodes mapped by path segment
+ Map<String, TrieNode> children = new HashMap<>();
+ // Marks if a pattern ends here (e.g., "root.sg" is a set path)
+ boolean isLeaf = false;
+ // Special flags for optimization
+ boolean isMultiLevelWildcard = false; // Ends with **
+ }
+
+ /** Adds a path to the Trie. */
+ public void add(final PartialPath path) {
+ TrieNode node = root;
+ final String[] nodes = path.getNodes();
+
+ for (final String segment : nodes) {
+ // If we are at a node that is already a MultiLevelWildcard (**),
+ // everything below is already covered. We can stop adding.
+ if (node.isMultiLevelWildcard) {
+ return;
+ }
+
+ node = node.children.computeIfAbsent(segment, k -> new TrieNode());
+
+ // If this segment is **, mark it.
+ // Note: In IoTDB PartialPath, ** is usually the last node or specific
wildcard.
+ if (segment.equals(IoTDBConstant.MULTI_LEVEL_PATH_WILDCARD)) {
+ node.isMultiLevelWildcard = true;
+ // Optimization: clear children as ** covers everything
+ node.children.clear();
+ node.isLeaf = true;
+ return;
+ }
+ }
+ node.isLeaf = true;
+ }
+
+ /**
+ * Checks if the given path is covered by any existing pattern in the
Trie. e.g., if Trie has
+ * "root.sg.**", then "root.sg.d1.s1" returns true.
+ */
+ public boolean isCovered(final PartialPath path) {
+ return checkCoverage(root, path.getNodes(), 0);
+ }
+
+ private boolean checkCoverage(final TrieNode node, final String[]
pathNodes, final int index) {
+ // 1. If the Trie node is a Multi-Level Wildcard (**), it covers
everything remainder
+ if (node.isMultiLevelWildcard) {
+ return true;
+ }
+
+ // 2. If we reached the end of the query path
+ if (index >= pathNodes.length) {
+ // The path is covered if the Trie also ends here (isLeaf)
+ // Example: Trie="root.sg", Path="root.sg" -> Covered
+ // Example: Trie="root.sg.d1", Path="root.sg" -> Not Covered (Trie is
more specific)
+ return node.isLeaf;
+ }
+
+ final String currentSegment = pathNodes[index];
+
+ // 3. Direct Match or Single Level Wildcard (*) in Trie
+ // Check exact match child
+ final TrieNode child = node.children.get(currentSegment);
+ if (child != null && checkCoverage(child, pathNodes, index + 1)) {
+ return true;
+ }
+
+ // Check if Trie has a '*' child (One Level Wildcard)
+ // '*' in Trie covers any single level in Path
+ final TrieNode wildcardChild =
node.children.get(IoTDBConstant.ONE_LEVEL_PATH_WILDCARD);
+ if (wildcardChild != null) {
+ return checkCoverage(wildcardChild, pathNodes, index + 1);
+ }
Review Comment:
done
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
