Time range tool (#10816)
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 9b3991f..ac88271 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 @@ @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 0000000..245d41c --- /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 62044ec..c3caaa1 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 @@ 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 @@ 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 0000000..2c40437 --- /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); + } +}