oxihuman_core/
interval_tree.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3
4//! 1D interval tree for range queries.
5
6#[allow(dead_code)]
7#[derive(Debug, Clone)]
8pub struct Interval {
9    pub lo: f32,
10    pub hi: f32,
11    pub id: u32,
12}
13
14#[allow(dead_code)]
15#[derive(Debug, Clone)]
16pub struct IntervalTree {
17    pub intervals: Vec<Interval>,
18}
19
20#[allow(dead_code)]
21pub fn new_interval_tree() -> IntervalTree {
22    IntervalTree {
23        intervals: Vec::new(),
24    }
25}
26
27#[allow(dead_code)]
28pub fn it_insert(tree: &mut IntervalTree, lo: f32, hi: f32, id: u32) {
29    tree.intervals.push(Interval { lo, hi, id });
30}
31
32#[allow(dead_code)]
33pub fn it_remove(tree: &mut IntervalTree, id: u32) {
34    tree.intervals.retain(|iv| iv.id != id);
35}
36
37#[allow(dead_code)]
38pub fn it_query_point(tree: &IntervalTree, x: f32) -> Vec<u32> {
39    tree.intervals
40        .iter()
41        .filter(|iv| (iv.lo..=iv.hi).contains(&x))
42        .map(|iv| iv.id)
43        .collect()
44}
45
46#[allow(dead_code)]
47pub fn it_query_range(tree: &IntervalTree, lo: f32, hi: f32) -> Vec<u32> {
48    tree.intervals
49        .iter()
50        .filter(|iv| iv.lo <= hi && iv.hi >= lo)
51        .map(|iv| iv.id)
52        .collect()
53}
54
55#[allow(dead_code)]
56pub fn it_count(tree: &IntervalTree) -> usize {
57    tree.intervals.len()
58}
59
60#[allow(dead_code)]
61pub fn it_clear(tree: &mut IntervalTree) {
62    tree.intervals.clear();
63}
64
65#[allow(dead_code)]
66pub fn it_contains_id(tree: &IntervalTree, id: u32) -> bool {
67    tree.intervals.iter().any(|iv| iv.id == id)
68}
69
70#[allow(dead_code)]
71pub fn it_to_json(tree: &IntervalTree) -> String {
72    let entries: Vec<String> = tree
73        .intervals
74        .iter()
75        .map(|iv| format!("{{\"id\":{},\"lo\":{},\"hi\":{}}}", iv.id, iv.lo, iv.hi))
76        .collect();
77    format!("[{}]", entries.join(","))
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_new_empty() {
86        let t = new_interval_tree();
87        assert_eq!(it_count(&t), 0);
88    }
89
90    #[test]
91    fn test_insert_and_count() {
92        let mut t = new_interval_tree();
93        it_insert(&mut t, 1.0, 5.0, 1);
94        it_insert(&mut t, 3.0, 8.0, 2);
95        assert_eq!(it_count(&t), 2);
96    }
97
98    #[test]
99    fn test_query_point() {
100        let mut t = new_interval_tree();
101        it_insert(&mut t, 1.0, 5.0, 1);
102        it_insert(&mut t, 6.0, 10.0, 2);
103        let res = it_query_point(&t, 3.0);
104        assert!(res.contains(&1));
105        assert!(!res.contains(&2));
106    }
107
108    #[test]
109    fn test_query_range_overlap() {
110        let mut t = new_interval_tree();
111        it_insert(&mut t, 1.0, 5.0, 1);
112        it_insert(&mut t, 4.0, 9.0, 2);
113        it_insert(&mut t, 10.0, 15.0, 3);
114        let res = it_query_range(&t, 3.0, 6.0);
115        assert!(res.contains(&1));
116        assert!(res.contains(&2));
117        assert!(!res.contains(&3));
118    }
119
120    #[test]
121    fn test_remove() {
122        let mut t = new_interval_tree();
123        it_insert(&mut t, 1.0, 5.0, 1);
124        it_insert(&mut t, 6.0, 10.0, 2);
125        it_remove(&mut t, 1);
126        assert_eq!(it_count(&t), 1);
127        assert!(!it_contains_id(&t, 1));
128    }
129
130    #[test]
131    fn test_contains_id() {
132        let mut t = new_interval_tree();
133        it_insert(&mut t, 0.0, 1.0, 42);
134        assert!(it_contains_id(&t, 42));
135        assert!(!it_contains_id(&t, 99));
136    }
137
138    #[test]
139    fn test_clear() {
140        let mut t = new_interval_tree();
141        it_insert(&mut t, 0.0, 1.0, 1);
142        it_clear(&mut t);
143        assert_eq!(it_count(&t), 0);
144    }
145
146    #[test]
147    fn test_to_json() {
148        let mut t = new_interval_tree();
149        it_insert(&mut t, 0.0, 1.0, 1);
150        let json = it_to_json(&t);
151        assert!(json.contains("\"id\":1"));
152    }
153
154    #[test]
155    fn test_query_point_boundary() {
156        let mut t = new_interval_tree();
157        it_insert(&mut t, 2.0, 4.0, 7);
158        let at_lo = it_query_point(&t, 2.0);
159        let at_hi = it_query_point(&t, 4.0);
160        assert!(at_lo.contains(&7));
161        assert!(at_hi.contains(&7));
162    }
163}
oxihuman_core/interval_tree.rs

oxihuman_core/
interval_tree.rs
