Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_datime/src/index/range_index.rs

16.3 KiB, 72 runs

created by r1870400018:8460, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Range-based indexing for temporal range queries.
2//!
3//! Ranges are indexed at both ends, so a query can find the ranges that
4//! overlap it, sit inside it, or contain it without scanning them all.
5//!
6//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
7//! Anthropic Claude
8
9use oxedyne_fe2o3_core::prelude::*;
10use crate::{
11 time::{CalClock, CalClockZone},
12 interval::CalClockRange,
13};
14use std::{
15 collections::BTreeMap,
16 fmt,
17};
18
19#[derive(Debug, Clone)]
20pub struct RangeQuery {
21 pub start: CalClock,
22 pub end: CalClock,
23 // Which kinds of overlap count as a match.
24 pub include_partial_overlaps: bool,
25 pub include_contained: bool, // range inside the query
26 pub include_containing: bool, // query inside the range
27}
28
29impl RangeQuery {
30 pub fn new(start: CalClock, end: CalClock) -> Self {
31 RangeQuery {
32 start,
33 end,
34 include_partial_overlaps: true,
35 include_contained: true,
36 include_containing: true,
37 }
38 }
39
40 pub fn exact_overlaps(start: CalClock, end: CalClock) -> Self {
41 RangeQuery {
42 start,
43 end,
44 include_partial_overlaps: true,
45 include_contained: false,
46 include_containing: false,
47 }
48 }
49
50 pub fn contained_ranges(start: CalClock, end: CalClock) -> Self {
51 RangeQuery {
52 start,
53 end,
54 include_partial_overlaps: false,
55 include_contained: true,
56 include_containing: false,
57 }
58 }
59
60 pub fn containing_ranges(start: CalClock, end: CalClock) -> Self {
61 RangeQuery {
62 start,
63 end,
64 include_partial_overlaps: false,
65 include_contained: false,
66 include_containing: true,
67 }
68 }
69}
70
71#[derive(Debug, Clone)]
72pub struct RangeResult<T> {
73 pub range: CalClockRange,
74 pub data: T,
75 pub overlap_type: OverlapType,
76 pub overlap_percentage: f64, // 0.0 to 1.0, not 0 to 100
77}
78
79#[derive(Debug, Clone, PartialEq)]
80pub enum OverlapType {
81 // Named for whichever side is the smaller of the two.
82 QueryContained, // query sits inside the indexed range
83 RangeContained, // indexed range sits inside the query
84 PartialStart,
85 PartialEnd,
86 Identical,
87 NoOverlap,
88}
89
90#[derive(Debug, Clone)]
91pub struct RangeEntry<T> {
92 pub range: CalClockRange,
93 pub data: T,
94 pub id: usize,
95}
96
97impl<T> RangeEntry<T> {
98 pub fn new(range: CalClockRange, data: T, id: usize) -> Self {
99 RangeEntry { range, data, id }
100 }
101
102 pub fn overlaps_with(&self, other_range: &CalClockRange) -> Outcome<bool> {
103 self.range.overlaps(other_range)
104 }
105
106 /// The overlap type, then the fraction of the query the range covers.
107 pub fn calculate_overlap(&self, query: &RangeQuery) -> Outcome<(OverlapType, f64)> {
108 let query_start_ts = res!(query.start.to_millis());
109 let query_end_ts = res!(query.end.to_millis());
110 let range_start_ts = res!(self.range.start().to_millis());
111 let range_end_ts = res!(self.range.end().to_millis());
112
113 // Check for no overlap
114 if range_end_ts < query_start_ts || range_start_ts > query_end_ts {
115 return Ok((OverlapType::NoOverlap, 0.0));
116 }
117
118 // Check for identical ranges
119 if range_start_ts == query_start_ts && range_end_ts == query_end_ts {
120 return Ok((OverlapType::Identical, 1.0));
121 }
122
123 // Check for containment relationships
124 if range_start_ts <= query_start_ts && range_end_ts >= query_end_ts {
125 // Query is contained within this range
126 let query_duration = query_end_ts - query_start_ts;
127 let range_duration = range_end_ts - range_start_ts;
128 let percentage = if range_duration > 0 {
129 query_duration as f64 / range_duration as f64
130 } else {
131 1.0
132 };
133 return Ok((OverlapType::QueryContained, percentage));
134 }
135
136 if query_start_ts <= range_start_ts && query_end_ts >= range_end_ts {
137 // This range is contained within query
138 let range_duration = range_end_ts - range_start_ts;
139 let query_duration = query_end_ts - query_start_ts;
140 let percentage = if query_duration > 0 {
141 range_duration as f64 / query_duration as f64
142 } else {
143 1.0
144 };
145 return Ok((OverlapType::RangeContained, percentage));
146 }
147
148 // Partial overlaps
149 let overlap_start = std::cmp::max(range_start_ts, query_start_ts);
150 let overlap_end = std::cmp::min(range_end_ts, query_end_ts);
151 let overlap_duration = overlap_end - overlap_start;
152
153 let range_duration = range_end_ts - range_start_ts;
154 let percentage = if range_duration > 0 {
155 overlap_duration as f64 / range_duration as f64
156 } else {
157 0.0
158 };
159
160 let overlap_type = if range_start_ts < query_start_ts {
161 OverlapType::PartialEnd
162 } else {
163 OverlapType::PartialStart
164 };
165
166 Ok((overlap_type, percentage))
167 }
168}
169
170#[derive(Debug)]
171pub struct RangeIndex<T> {
172 // Two ordered indexes, one on each end of the range, both holding
173 // positions into `entries`.
174 start_index: BTreeMap<i64, Vec<usize>>,
175 end_index: BTreeMap<i64, Vec<usize>>,
176 entries: Vec<RangeEntry<T>>,
177 #[allow(dead_code)]
178 zone: CalClockZone,
179 next_id: usize,
180}
181
182impl<T> RangeIndex<T> {
183 pub fn new(zone: CalClockZone) -> Self {
184 RangeIndex {
185 start_index: BTreeMap::new(),
186 end_index: BTreeMap::new(),
187 entries: Vec::new(),
188 zone,
189 next_id: 0,
190 }
191 }
192
193 /// Returns the entry id, which is not the position in the entry list.
194 pub fn insert(&mut self, range: CalClockRange, data: T) -> Outcome<usize> {
195 let entry_id = self.next_id;
196 self.next_id += 1;
197
198 let start_ts = res!(range.start().to_millis());
199 let end_ts = res!(range.end().to_millis());
200
201 // Add to start index
202 self.start_index
203 .entry(start_ts)
204 .or_insert_with(Vec::new)
205 .push(self.entries.len());
206
207 // Add to end index
208 self.end_index
209 .entry(end_ts)
210 .or_insert_with(Vec::new)
211 .push(self.entries.len());
212
213 // Store the entry
214 let entry = RangeEntry::new(range, data, entry_id);
215 self.entries.push(entry);
216
217 Ok(entry_id)
218 }
219
220 pub fn query(&self, query: &RangeQuery) -> Outcome<Vec<RangeResult<&T>>> {
221 let query_start_ts = res!(query.start.to_millis());
222 let query_end_ts = res!(query.end.to_millis());
223
224 let mut results = Vec::new();
225 let mut seen = std::collections::HashSet::new();
226
227 // Find all ranges that could potentially overlap
228 // Look at ranges that start before or at query end
229 for (&_start_ts, entry_indices) in self.start_index.range(..=query_end_ts) {
230 for &entry_idx in entry_indices {
231 if seen.contains(&entry_idx) {
232 continue;
233 }
234 seen.insert(entry_idx);
235
236 if let Some(entry) = self.entries.get(entry_idx) {
237 let end_ts = res!(entry.range.end().to_millis());
238
239 // Skip if range ends before query starts
240 if end_ts < query_start_ts {
241 continue;
242 }
243
244 let (overlap_type, overlap_percentage) = res!(entry.calculate_overlap(query));
245
246 // Filter based on query preferences
247 let include = match overlap_type {
248 OverlapType::NoOverlap => false,
249 OverlapType::Identical => true,
250 OverlapType::QueryContained => query.include_containing,
251 OverlapType::RangeContained => query.include_contained,
252 OverlapType::PartialStart | OverlapType::PartialEnd => query.include_partial_overlaps,
253 };
254
255 if include {
256 results.push(RangeResult {
257 range: entry.range.clone(),
258 data: &entry.data,
259 overlap_type,
260 overlap_percentage,
261 });
262 }
263 }
264 }
265 }
266
267 // Sort results by start time
268 results.sort_by(|a, b| {
269 a.range.start().partial_cmp(b.range.start()).unwrap_or(std::cmp::Ordering::Equal)
270 });
271
272 Ok(results)
273 }
274
275 pub fn find_starting_in_range(&self, start: &CalClock, end: &CalClock) -> Outcome<Vec<&RangeEntry<T>>> {
276 let start_ts = res!(start.to_millis());
277 let end_ts = res!(end.to_millis());
278
279 let mut results = Vec::new();
280
281 for (&_ts, entry_indices) in self.start_index.range(start_ts..=end_ts) {
282 for &entry_idx in entry_indices {
283 if let Some(entry) = self.entries.get(entry_idx) {
284 results.push(entry);
285 }
286 }
287 }
288
289 Ok(results)
290 }
291
292 pub fn find_ending_in_range(&self, start: &CalClock, end: &CalClock) -> Outcome<Vec<&RangeEntry<T>>> {
293 let start_ts = res!(start.to_millis());
294 let end_ts = res!(end.to_millis());
295
296 let mut results = Vec::new();
297
298 for (&_ts, entry_indices) in self.end_index.range(start_ts..=end_ts) {
299 for &entry_idx in entry_indices {
300 if let Some(entry) = self.entries.get(entry_idx) {
301 results.push(entry);
302 }
303 }
304 }
305
306 Ok(results)
307 }
308
309 pub fn len(&self) -> usize {
310 self.entries.len()
311 }
312
313 pub fn is_empty(&self) -> bool {
314 self.entries.is_empty()
315 }
316
317 pub fn all_entries(&self) -> &[RangeEntry<T>] {
318 &self.entries
319 }
320
321 pub fn remove(&mut self, entry_id: usize) -> Outcome<Option<RangeEntry<T>>> {
322 if let Some(pos) = self.entries.iter().position(|e| e.id == entry_id) {
323 let entry = self.entries.remove(pos);
324
325 // Rebuild indexes (could be optimized but good enough for now)
326 ok!(self.rebuild_indexes());
327
328 Ok(Some(entry))
329 } else {
330 Ok(None)
331 }
332 }
333
334 fn rebuild_indexes(&mut self) -> Outcome<()> {
335 self.start_index.clear();
336 self.end_index.clear();
337
338 for (idx, entry) in self.entries.iter().enumerate() {
339 let start_ts = res!(entry.range.start().to_millis());
340 let end_ts = res!(entry.range.end().to_millis());
341
342 self.start_index
343 .entry(start_ts)
344 .or_insert_with(Vec::new)
345 .push(idx);
346
347 self.end_index
348 .entry(end_ts)
349 .or_insert_with(Vec::new)
350 .push(idx);
351 }
352
353 Ok(())
354 }
355}
356
357impl fmt::Display for OverlapType {
358 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
359 match self {
360 OverlapType::QueryContained => write!(f, "Query Contained"),
361 OverlapType::RangeContained => write!(f, "Range Contained"),
362 OverlapType::PartialStart => write!(f, "Partial Start"),
363 OverlapType::PartialEnd => write!(f, "Partial End"),
364 OverlapType::Identical => write!(f, "Identical"),
365 OverlapType::NoOverlap => write!(f, "No Overlap"),
366 }
367 }
368}
369
370#[cfg(test)]
371mod tests {
372 use super::*;
373
374 #[test]
375 fn test_range_index_basic_operations() {
376 let zone = CalClockZone::utc();
377 let mut index = RangeIndex::new(zone.clone());
378
379 let start1 = CalClock::new(2024, 1, 1, 10, 0, 0, 0, zone.clone()).unwrap();
380 let end1 = CalClock::new(2024, 1, 1, 12, 0, 0, 0, zone.clone()).unwrap();
381 let range1 = CalClockRange::new(start1, end1).unwrap();
382
383 let start2 = CalClock::new(2024, 1, 1, 14, 0, 0, 0, zone.clone()).unwrap();
384 let end2 = CalClock::new(2024, 1, 1, 16, 0, 0, 0, zone.clone()).unwrap();
385 let range2 = CalClockRange::new(start2, end2).unwrap();
386
387 let id1 = index.insert(range1, "meeting1").unwrap();
388 let id2 = index.insert(range2, "meeting2").unwrap();
389
390 assert_eq!(index.len(), 2);
391 assert_eq!(id1, 0);
392 assert_eq!(id2, 1);
393 }
394
395 #[test]
396 fn test_overlap_detection() {
397 let zone = CalClockZone::utc();
398 let mut index = RangeIndex::new(zone.clone());
399
400 // Add overlapping ranges
401 let range1_start = CalClock::new(2024, 1, 1, 10, 0, 0, 0, zone.clone()).unwrap();
402 let range1_end = CalClock::new(2024, 1, 1, 14, 0, 0, 0, zone.clone()).unwrap();
403 let range1 = CalClockRange::new(range1_start, range1_end).unwrap();
404
405 let range2_start = CalClock::new(2024, 1, 1, 12, 0, 0, 0, zone.clone()).unwrap();
406 let range2_end = CalClock::new(2024, 1, 1, 16, 0, 0, 0, zone.clone()).unwrap();
407 let range2 = CalClockRange::new(range2_start, range2_end).unwrap();
408
409 index.insert(range1, "event1").unwrap();
410 index.insert(range2, "event2").unwrap();
411
412 // Query for overlaps
413 let query_start = CalClock::new(2024, 1, 1, 11, 0, 0, 0, zone.clone()).unwrap();
414 let query_end = CalClock::new(2024, 1, 1, 13, 0, 0, 0, zone).unwrap();
415 let query = RangeQuery::new(query_start, query_end);
416
417 let results = index.query(&query).unwrap();
418 assert_eq!(results.len(), 2); // Both ranges should overlap
419 }
420
421 #[test]
422 fn test_containment_queries() {
423 let zone = CalClockZone::utc();
424 let mut index = RangeIndex::new(zone.clone());
425
426 // Large containing range
427 let large_start = CalClock::new(2024, 1, 1, 8, 0, 0, 0, zone.clone()).unwrap();
428 let large_end = CalClock::new(2024, 1, 1, 18, 0, 0, 0, zone.clone()).unwrap();
429 let large_range = CalClockRange::new(large_start, large_end).unwrap();
430
431 // Small contained range
432 let small_start = CalClock::new(2024, 1, 1, 10, 0, 0, 0, zone.clone()).unwrap();
433 let small_end = CalClock::new(2024, 1, 1, 12, 0, 0, 0, zone.clone()).unwrap();
434 let small_range = CalClockRange::new(small_start, small_end).unwrap();
435
436 index.insert(large_range, "full_day").unwrap();
437 index.insert(small_range, "meeting").unwrap();
438
439 // Query that should be contained within large range
440 let query_start = CalClock::new(2024, 1, 1, 9, 0, 0, 0, zone.clone()).unwrap();
441 let query_end = CalClock::new(2024, 1, 1, 11, 0, 0, 0, zone).unwrap();
442 let query = RangeQuery::containing_ranges(query_start, query_end);
443
444 let results = index.query(&query).unwrap();
445 assert_eq!(results.len(), 1); // Only the large range should match
446 assert_eq!(results[0].overlap_type, OverlapType::QueryContained);
447 }
448
449 #[test]
450 fn test_range_removal() {
451 let zone = CalClockZone::utc();
452 let mut index = RangeIndex::new(zone.clone());
453
454 let start = CalClock::new(2024, 1, 1, 10, 0, 0, 0, zone.clone()).unwrap();
455 let end = CalClock::new(2024, 1, 1, 12, 0, 0, 0, zone).unwrap();
456 let range = CalClockRange::new(start, end).unwrap();
457
458 let id = index.insert(range, "test").unwrap();
459 assert_eq!(index.len(), 1);
460
461 let removed = index.remove(id).unwrap();
462 assert!(removed.is_some());
463 assert_eq!(index.len(), 0);
464 }
465
466 #[test]
467 fn test_overlap_percentage_calculation() {
468 let zone = CalClockZone::utc();
469
470 let start1 = CalClock::new(2024, 1, 1, 10, 0, 0, 0, zone.clone()).unwrap();
471 let end1 = CalClock::new(2024, 1, 1, 14, 0, 0, 0, zone.clone()).unwrap(); // 4 hours
472 let range = CalClockRange::new(start1, end1).unwrap();
473 let entry = RangeEntry::new(range, "test", 0);
474
475 // Query that overlaps 2 hours (50% of the range)
476 let query_start = CalClock::new(2024, 1, 1, 12, 0, 0, 0, zone.clone()).unwrap();
477 let query_end = CalClock::new(2024, 1, 1, 16, 0, 0, 0, zone).unwrap();
478 let query = RangeQuery::new(query_start, query_end);
479
480 let (overlap_type, percentage) = entry.calculate_overlap(&query).unwrap();
481 assert_eq!(overlap_type, OverlapType::PartialEnd);
482 assert!((percentage - 0.5).abs() < 0.01); // Should be 50%
483 }
484}