nautilus_persistence/backend/parquet/
intervals.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Closed-interval set operations used by the parquet catalog for coverage and gap analysis.
17
18use nautilus_core::ClosedInterval;
19
20use crate::common::coverage::missing_intervals;
21
22/// Checks if a list of closed integer intervals are all mutually disjoint.
23///
24/// Returns `true` for empty lists or lists with a single interval.
25#[must_use]
26pub fn are_intervals_disjoint(intervals: &[(u64, u64)]) -> bool {
27    if intervals.len() <= 1 {
28        return true;
29    }
30
31    let mut sorted_intervals = intervals.to_vec();
32    sorted_intervals.sort_by_key(|&(start, _)| start);
33    sorted_intervals
34        .array_windows()
35        .all(|&[(_, end), (start, _)]| end < start)
36}
37
38/// Checks if intervals are contiguous (adjacent with no gaps).
39///
40/// Intervals are contiguous if, when sorted by start time, each interval's start
41/// timestamp is exactly one more than the previous interval's end timestamp.
42#[must_use]
43pub fn are_intervals_contiguous(intervals: &[(u64, u64)]) -> bool {
44    if intervals.len() <= 1 {
45        return true;
46    }
47
48    let mut sorted_intervals = intervals.to_vec();
49    sorted_intervals.sort_by_key(|&(start, _)| start);
50    sorted_intervals
51        .array_windows()
52        .all(|&[(_, end), (start, _)]| end + 1 == start)
53}
54
55/// Finds the parts of a query interval that are not covered by existing data intervals.
56///
57/// Returns a vector of (start, end) tuples representing the gaps in coverage.
58pub(crate) fn query_interval_diff(
59    start: u64,
60    end: u64,
61    closed_intervals: &[(u64, u64)],
62) -> Vec<(u64, u64)> {
63    if start > end {
64        return Vec::new();
65    }
66
67    let intervals = closed_intervals
68        .iter()
69        .filter_map(|&(start, end)| ClosedInterval::new(start, end))
70        .collect::<Vec<_>>();
71
72    missing_intervals(start, end, &intervals)
73        .into_iter()
74        .map(Into::into)
75        .collect()
76}
77
78#[cfg(test)]
79mod tests {
80    use rstest::rstest;
81
82    use super::{are_intervals_contiguous, are_intervals_disjoint};
83
84    #[rstest]
85    #[case::empty(&[], true)]
86    #[case::single(&[(1, 5)], true)]
87    #[case::separated(&[(1, 2), (3, 4)], true)]
88    #[case::shared_endpoint(&[(1, 5), (5, 6)], false)]
89    #[case::nested(&[(1, 5), (3, 4)], false)]
90    #[case::unsorted_separated(&[(5, 6), (1, 2)], true)]
91    #[case::unsorted_overlapping(&[(4, 6), (1, 4)], false)]
92    fn are_intervals_disjoint_cases(#[case] intervals: &[(u64, u64)], #[case] expected: bool) {
93        assert_eq!(are_intervals_disjoint(intervals), expected);
94    }
95
96    #[rstest]
97    #[case::empty(&[], true)]
98    #[case::single(&[(1, 1)], true)]
99    #[case::adjacent(&[(1, 2), (3, 4)], true)]
100    #[case::shared_endpoint(&[(1, 5), (5, 6)], false)]
101    #[case::gap(&[(1, 2), (4, 5)], false)]
102    #[case::unsorted_adjacent(&[(3, 4), (1, 2)], true)]
103    #[case::unsorted_gap(&[(5, 6), (1, 2)], false)]
104    fn are_intervals_contiguous_cases(#[case] intervals: &[(u64, u64)], #[case] expected: bool) {
105        assert_eq!(are_intervals_contiguous(intervals), expected);
106    }
107}
nautilus_persistence/backend/parquet/intervals.rs

nautilus_persistence/backend/parquet/
intervals.rs
