Cpaulyz commented on code in PR #10874:
URL: https://github.com/apache/iotdb/pull/10874#discussion_r1297925444
##########
iotdb-core/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java:
##########
@@ -492,6 +497,54 @@ public boolean overlapWith(PartialPath rPath) {
return this.nodes.length == rNodes.length;
}
+ /**
+ * Try to check overlap between nodes1 and nodes2 with
MULTI_LEVEL_PATH_WILDCARD. Time complexity
+ * O(n^2).
+ *
+ * @return true if overlapping, otherwise return false
+ */
+ 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]
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]
