[GitHub] [iotdb] JackieTien97 commented on a diff in pull request #7359: [IOTDB-4391] Apply PatternTreeMap in parsing .mods file to optimize query

[GitBox <gi...@apache.org>]

JackieTien97 commented on code in PR #7359:
URL: https://github.com/apache/iotdb/pull/7359#discussion_r975296513


##########
tsfile/src/main/java/org/apache/iotdb/tsfile/file/metadata/ChunkMetadata.java:
##########
@@ -197,32 +198,30 @@ public void setVersion(long version) {
   }
 
   public List<TimeRange> getDeleteIntervalList() {
-    return deleteIntervalList;
-  }
-
-  public void setDeleteIntervalList(List<TimeRange> list) {
-    this.deleteIntervalList = list;
+    return deleteIntervalSet == null ? null : new ArrayList<>(deleteIntervalSet);
   }
 
   public void insertIntoSortedDeletions(long startTime, long endTime) {
-    List<TimeRange> resultInterval = new ArrayList<>();
-    if (deleteIntervalList != null) {
-      for (TimeRange interval : deleteIntervalList) {
-        if (interval.getMax() < startTime) {
-          resultInterval.add(interval);
-        } else if (interval.getMin() > endTime) {
-          resultInterval.add(new TimeRange(startTime, endTime));
-          startTime = interval.getMin();
-          endTime = interval.getMax();
-        } else if (interval.getMax() >= startTime || interval.getMin() <= endTime) {
-          startTime = Math.min(interval.getMin(), startTime);
-          endTime = Math.max(interval.getMax(), endTime);
-        }
+    TimeRange timeRange = new TimeRange(startTime, endTime);
+
+    if (deleteIntervalSet != null) {
+      TimeRange interval = deleteIntervalSet.floor(timeRange);
+      while (interval != null && timeRange.intersects(interval)) {
+        timeRange.merge(interval);
+        deleteIntervalSet.remove(interval);
+        interval = deleteIntervalSet.floor(timeRange);
       }
+      interval = deleteIntervalSet.ceiling(timeRange);
+      while (interval != null && timeRange.intersects(interval)) {
+        timeRange.merge(interval);
+        deleteIntervalSet.remove(interval);
+        interval = deleteIntervalSet.ceiling(timeRange);
+      }
+    } else {
+      deleteIntervalSet = new TreeSet<>();
     }
 
-    resultInterval.add(new TimeRange(startTime, endTime));
-    deleteIntervalList = resultInterval;
+    deleteIntervalSet.add(timeRange);

Review Comment:
   The time complexity of this method seems not to be O(logN), becasue it's still possible that we need to merge more than one element in this TreeMap.
   Actually, it's a classic algorithm problem called range merge, and in our case, we can also have all the time range firstly, and then do merge together(or if you like, you still can keep current style that update it every time this method is called.) You can refer to this [blog](https://juejin.cn/post/7083845140283916325 ) about the concrete algorithm solution 



-- 
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: reviews-unsubscribe@iotdb.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org