oxihuman_core/
interval_tree_simple.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Simple interval overlap query structure.
6
7pub struct IntervalSimple {
8    pub lo: f32,
9    pub hi: f32,
10    pub id: usize,
11}
12
13pub struct IntervalTreeSimple {
14    pub intervals: Vec<IntervalSimple>,
15}
16
17pub fn new_interval_tree_simple() -> IntervalTreeSimple {
18    IntervalTreeSimple {
19        intervals: Vec::new(),
20    }
21}
22
23pub fn itree_simple_insert(t: &mut IntervalTreeSimple, lo: f32, hi: f32, id: usize) {
24    t.intervals.push(IntervalSimple { lo, hi, id });
25}
26
27pub fn itree_simple_query_overlaps(t: &IntervalTreeSimple, lo: f32, hi: f32) -> Vec<usize> {
28    t.intervals
29        .iter()
30        .filter(|i| i.lo <= hi && i.hi >= lo)
31        .map(|i| i.id)
32        .collect()
33}
34
35pub fn itree_simple_count_overlaps(t: &IntervalTreeSimple, lo: f32, hi: f32) -> usize {
36    t.intervals
37        .iter()
38        .filter(|i| i.lo <= hi && i.hi >= lo)
39        .count()
40}
41
42pub fn itree_simple_size(t: &IntervalTreeSimple) -> usize {
43    t.intervals.len()
44}
45
46pub fn itree_simple_contains_point(t: &IntervalTreeSimple, pt: f32) -> Vec<usize> {
47    t.intervals
48        .iter()
49        .filter(|i| i.lo <= pt && i.hi >= pt)
50        .map(|i| i.id)
51        .collect()
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_new_interval_tree_simple() {
60        /* empty tree has size 0 */
61        let t = new_interval_tree_simple();
62        assert_eq!(itree_simple_size(&t), 0);
63    }
64
65    #[test]
66    fn test_insert_and_size() {
67        /* inserting intervals increases size */
68        let mut t = new_interval_tree_simple();
69        itree_simple_insert(&mut t, 0.0, 5.0, 1);
70        itree_simple_insert(&mut t, 3.0, 8.0, 2);
71        assert_eq!(itree_simple_size(&t), 2);
72    }
73
74    #[test]
75    fn test_query_overlaps() {
76        /* overlapping interval query returns correct ids */
77        let mut t = new_interval_tree_simple();
78        itree_simple_insert(&mut t, 0.0, 5.0, 1);
79        itree_simple_insert(&mut t, 6.0, 10.0, 2);
80        let overlaps = itree_simple_query_overlaps(&t, 4.0, 7.0);
81        assert!(overlaps.contains(&1));
82        assert!(overlaps.contains(&2));
83    }
84
85    #[test]
86    fn test_no_overlap() {
87        /* non-overlapping intervals not returned */
88        let mut t = new_interval_tree_simple();
89        itree_simple_insert(&mut t, 0.0, 3.0, 1);
90        itree_simple_insert(&mut t, 7.0, 10.0, 2);
91        let overlaps = itree_simple_query_overlaps(&t, 4.0, 5.0);
92        assert!(overlaps.is_empty());
93    }
94
95    #[test]
96    fn test_count_overlaps() {
97        /* count returns correct number */
98        let mut t = new_interval_tree_simple();
99        itree_simple_insert(&mut t, 0.0, 10.0, 1);
100        itree_simple_insert(&mut t, 5.0, 15.0, 2);
101        itree_simple_insert(&mut t, 20.0, 30.0, 3);
102        assert_eq!(itree_simple_count_overlaps(&t, 6.0, 7.0), 2);
103    }
104
105    #[test]
106    fn test_contains_point() {
107        /* point query returns intervals that contain the point */
108        let mut t = new_interval_tree_simple();
109        itree_simple_insert(&mut t, 0.0, 10.0, 1);
110        itree_simple_insert(&mut t, 5.0, 15.0, 2);
111        itree_simple_insert(&mut t, 20.0, 30.0, 3);
112        let ids = itree_simple_contains_point(&t, 7.0);
113        assert!(ids.contains(&1) && ids.contains(&2));
114        assert!(!ids.contains(&3));
115    }
116
117    #[test]
118    fn test_point_boundary() {
119        /* boundary points are included */
120        let mut t = new_interval_tree_simple();
121        itree_simple_insert(&mut t, 0.0, 5.0, 1);
122        let ids = itree_simple_contains_point(&t, 5.0);
123        assert!(ids.contains(&1));
124    }
125}
oxihuman_core/interval_tree_simple.rs

oxihuman_core/
interval_tree_simple.rs
