This is an automated email from the ASF dual-hosted git repository.
xingtanzjr pushed a commit to branch overlap_check_tool
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/overlap_check_tool by this
push:
new 82122e106ae Time range tool (#10816)
82122e106ae is described below
commit 82122e106aec823a3443c5d727eed75fab81284c
Author: Zhijia Cao <[email protected]>
AuthorDate: Wed Aug 9 11:22:39 2023 +0800
Time range tool (#10816)
---
.../compaction/tool/ListTimeRangeImpl.java | 6 +-
.../compaction/tool/SegmentTreeImpl.java | 65 ++++++++++++++++++++++
.../compaction/tools/ListTimeRangeImplTest.java | 46 ++++++++++++++-
.../compaction/tools/SegmentTreeImplTest.java | 19 +++++++
4 files changed, 131 insertions(+), 5 deletions(-)
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
index 9b3991f58e1..ac882719c4a 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
@@ -77,10 +77,8 @@ public class ListTimeRangeImpl implements ITimeRange {
@Override
public boolean isOverlapped(Interval interval) {
for (Interval currentInterval : intervalList) {
- if (interval.getStart() <= currentInterval.getEnd()
- || interval.getEnd() <= currentInterval.getEnd()) {
- return true;
- }
+ return interval.getStart() <= currentInterval.getEnd()
+ && interval.getEnd() >= currentInterval.getStart();
}
return false;
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/SegmentTreeImpl.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/SegmentTreeImpl.java
new file mode 100644
index 00000000000..245d41cf9c7
--- /dev/null
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/SegmentTreeImpl.java
@@ -0,0 +1,65 @@
+package org.apache.iotdb.db.storageengine.dataregion.compaction.tool;
+
+public class SegmentTreeImpl implements ITimeRange {
+
+ private IntervalNode root;
+
+ @Override
+ public void addInterval(Interval interval) {
+ root = insert(root, interval);
+ }
+
+ @Override
+ public boolean isOverlapped(Interval interval) {
+ return overlaps(root, interval);
+ }
+
+ private boolean overlaps(IntervalNode node, Interval interval) {
+ if (node == null) {
+ return false;
+ }
+
+ if (node.interval.getStart() <= interval.getEnd()
+ && interval.getStart() <= node.interval.getEnd()) {
+ return true;
+ }
+
+ if (node.left != null && node.left.maxEnd >= interval.getStart()) {
+ return overlaps(node.left, interval);
+ }
+
+ return overlaps(node.right, interval);
+ }
+
+ public void insert(Interval interval) {
+ root = insert(root, interval);
+ }
+
+ private IntervalNode insert(IntervalNode node, Interval interval) {
+ if (node == null) {
+ return new IntervalNode(interval);
+ }
+
+ long start = interval.getStart();
+ if (start < node.interval.getStart()) {
+ node.left = insert(node.left, interval);
+ } else {
+ node.right = insert(node.right, interval);
+ }
+
+ node.maxEnd = Math.max(node.maxEnd, interval.getEnd());
+ return node;
+ }
+
+ private class IntervalNode {
+ Interval interval;
+ long maxEnd;
+ IntervalNode left;
+ IntervalNode right;
+
+ public IntervalNode(Interval interval) {
+ this.interval = interval;
+ this.maxEnd = interval.getEnd();
+ }
+ }
+}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
index 62044ec39e0..c3caaa16d77 100644
---
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
@@ -65,7 +65,7 @@ public class ListTimeRangeImplTest {
listTimeRange.addInterval(new Interval(15, 20));
listTimeRange.addInterval(new Interval(50, 60));
listTimeRange.addInterval(new Interval(5, 100));
- Assert.assertTrue(listTimeRange.isOverlapped(new Interval(1, 1)));
+ Assert.assertFalse(listTimeRange.isOverlapped(new Interval(1, 1)));
Assert.assertFalse(listTimeRange.isOverlapped(new Interval(101, 103)));
}
@@ -91,4 +91,48 @@ public class ListTimeRangeImplTest {
listTimeRange.addInterval(new Interval(51, 55));
Assert.assertEquals(51, listTimeRange.getIntervalList().get(1).getStart());
}
+
+ @Test
+ public void testNoOverlap() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(3, 5));
+ Assert.assertFalse(listTimeRange.isOverlapped(new Interval(6, 10)));
+ Assert.assertFalse(listTimeRange.isOverlapped(new Interval(1, 2)));
+ }
+
+ @Test
+ public void testStartTimeOverlap() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(1, 5));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(4, 8)));
+ }
+
+ @Test
+ public void testEndTimeOverlap() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(1, 5));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(0, 4)));
+ }
+
+ @Test
+ public void testFullyOverlap() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(2, 4));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(1, 5)));
+ }
+
+ @Test
+ public void testIntervalInsideCurrentInterval() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(1, 5));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(2, 4)));
+ }
+
+ @Test
+ public void testBoundary() {
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+ listTimeRange.addInterval(new Interval(3, 5));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(1, 3)));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(5, 6)));
+ }
}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/SegmentTreeImplTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/SegmentTreeImplTest.java
new file mode 100644
index 00000000000..2c40437e168
--- /dev/null
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/SegmentTreeImplTest.java
@@ -0,0 +1,19 @@
+package org.apache.iotdb.db.storageengine.dataregion.compaction.tools;
+
+import org.apache.iotdb.db.storageengine.dataregion.compaction.tool.Interval;
+import
org.apache.iotdb.db.storageengine.dataregion.compaction.tool.SegmentTreeImpl;
+
+import org.junit.Test;
+
+public class SegmentTreeImplTest {
+ @Test
+ public void test01() {
+ SegmentTreeImpl segmentTree = new SegmentTreeImpl();
+ segmentTree.insert(new Interval(15, 20));
+ segmentTree.insert(new Interval(10, 30));
+ segmentTree.insert(new Interval(17, 19));
+ segmentTree.insert(new Interval(5, 20));
+
+ System.out.println(segmentTree);
+ }
+}
