Cpaulyz commented on code in PR #10874:
URL: https://github.com/apache/iotdb/pull/10874#discussion_r1297901291
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java:
##########
@@ -533,51 +586,66 @@ public boolean overlapWithFullPathPrefix(PartialPath
prefixFullPath) {
}
/**
- * Try to check overlap between nodes1 and nodes2 with
MULTI_LEVEL_PATH_WILDCARD. Time complexity
- * O(n^2).
+ * Generate a list of partial paths which are the intersection of this path
pattern and input
+ * prefix pattern.
*
- * @return true if overlapping, otherwise return false
+ * @param prefixPattern must be a prefix full path ending with one "**",
like "root.sg.**"
+ * @return a list of partial paths which are the intersection of this path
pattern and input
+ * prefix pattern.
*/
- private boolean checkOverlapWithMultiLevelWildcard(String[] nodes1, String[]
nodes2) {
- // dp[i][j] means if nodes1[0:i) and nodes[0:j) overlapping
- boolean[][] dp = new boolean[nodes1.length + 1][nodes2.length + 1];
- dp[0][0] = true;
- for (int i = 1; i <= nodes1.length; i++) {
- for (int j = 1; j <= nodes2.length; j++) {
- if (nodes1[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)
- || nodes2[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- // if encounter MULTI_LEVEL_PATH_WILDCARD
- if (nodes1[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- // if nodes1[i-1] is MULTI_LEVEL_PATH_WILDCARD,
dp[i][k(k>=j)]=dp[i-1][j-1]
- if (dp[i - 1][j - 1]) {
- for (int k = j; k <= nodes2.length; k++) {
- dp[i][k] = true;
- }
- }
- }
- if (nodes2[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- // if nodes2[j-1] is MULTI_LEVEL_PATH_WILDCARD,
dp[k(k>=i)][j]=dp[i-1][j-1]
- if (dp[i - 1][j - 1]) {
- for (int k = i; k <= nodes1.length; k++) {
- dp[k][j] = true;
- }
- }
- }
- } else {
- // if without MULTI_LEVEL_PATH_WILDCARD, scan and check
- if ((PathPatternUtil.hasWildcard(nodes1[i - 1])
- && PathPatternUtil.isNodeMatch(nodes1[i - 1], nodes2[j - 1]))
- || (PathPatternUtil.hasWildcard(nodes2[j - 1])
- && PathPatternUtil.isNodeMatch(nodes2[j - 1], nodes1[i - 1]))
- || nodes1[i - 1].equals(nodes2[j - 1])) {
- // if nodes1[i-1] and nodes[2] is matched, dp[i][j] = dp[i-1][j-1]
- dp[i][j] |= dp[i - 1][j - 1];
+ public List<PartialPath> intersectWithPrefixPattern(PartialPath
prefixPattern) {
+ if (prefixPattern.equals(ALL_MATCH_PATTERN)) {
+ return Collections.singletonList(this);
+ }
+ String[] prefixFullPath =
+ Arrays.copyOf(prefixPattern.getNodes(), prefixPattern.getNodeLength()
- 1);
+ // init dp array
+ int thisLength = this.getNodeLength();
+ boolean[] matchIndex = new boolean[thisLength];
+ matchIndex[0] = true; // "root" must match "root"
+
+ // dp[i][j] means if nodes[0:i) matches prefixFullPath[0:j)
+ // for example: "root.**.d1.**" intersect "root.sg1.d1(.**)"
+ // dp[i][j] = (nodes[i]=="**"&&dp[i][j-1]) ||
(nodes[i]==prefixFullPath[j]&&dp[i-1][j-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]
