Oregami
Repositories/oxedyne/fe2o3

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

22.2 KiB, 86 runs

created by r1870400018:8462, 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//! Temporal B-tree for time-based data.
2//!
3//! Entries are held in timestamp order with secondary indexes on category,
4//! recurrence, business day and priority, so a query filtered on any of those
5//! can start from the most selective index rather than scanning.
6//!
7//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
8//! Anthropic Claude
9
10use oxedyne_fe2o3_core::prelude::*;
11use crate::time::{CalClock, CalClockZone};
12use std::{
13 collections::BTreeMap,
14 fmt,
15 cmp::Ordering,
16};
17
18#[derive(Debug, Clone)]
19pub struct TemporalEntry<T>
20where
21 T: Clone,
22{
23 pub timestamp: i64, // Unix milliseconds
24 pub time: CalClock,
25 pub data: T,
26 pub temporal_attrs: TemporalAttributes,
27}
28
29#[derive(Debug, Clone)]
30pub struct TemporalAttributes {
31 pub duration_millis: Option<i64>, // None means a point in time
32 pub recurrence_id: Option<String>,
33 pub category: Option<String>,
34 pub is_business_day: bool,
35 pub is_holiday: bool,
36 pub priority: u8,
37}
38
39impl Default for TemporalAttributes {
40 fn default() -> Self {
41 TemporalAttributes {
42 duration_millis: None,
43 recurrence_id: None,
44 category: None,
45 is_business_day: true,
46 is_holiday: false,
47 priority: 0,
48 }
49 }
50}
51
52impl<T: Clone> TemporalEntry<T> {
53 pub fn new(time: CalClock, data: T) -> Outcome<Self> {
54 let timestamp = res!(time.to_millis());
55 Ok(TemporalEntry {
56 timestamp,
57 time,
58 data,
59 temporal_attrs: TemporalAttributes::default(),
60 })
61 }
62
63 pub fn with_attributes(time: CalClock, data: T, attrs: TemporalAttributes) -> Outcome<Self> {
64 let timestamp = res!(time.to_millis());
65 Ok(TemporalEntry {
66 timestamp,
67 time,
68 data,
69 temporal_attrs: attrs,
70 })
71 }
72
73 pub fn with_duration(mut self, duration_millis: i64) -> Self {
74 self.temporal_attrs.duration_millis = Some(duration_millis);
75 self
76 }
77
78 pub fn with_recurrence(mut self, recurrence_id: String) -> Self {
79 self.temporal_attrs.recurrence_id = Some(recurrence_id);
80 self
81 }
82
83 pub fn with_category(mut self, category: String) -> Self {
84 self.temporal_attrs.category = Some(category);
85 self
86 }
87
88 pub fn with_business_day(mut self, is_business_day: bool) -> Self {
89 self.temporal_attrs.is_business_day = is_business_day;
90 self
91 }
92
93 pub fn with_holiday(mut self, is_holiday: bool) -> Self {
94 self.temporal_attrs.is_holiday = is_holiday;
95 self
96 }
97
98 pub fn with_priority(mut self, priority: u8) -> Self {
99 self.temporal_attrs.priority = priority;
100 self
101 }
102
103 pub fn end_timestamp(&self) -> Option<i64> {
104 self.temporal_attrs.duration_millis.map(|d| self.timestamp + d)
105 }
106
107 /// A point entry matches either bound, a range entry treats its own end as exclusive.
108 pub fn overlaps_range(&self, start_ts: i64, end_ts: i64) -> bool {
109 if let Some(end_timestamp) = self.end_timestamp() {
110 // Range-based entry
111 !(end_timestamp <= start_ts || self.timestamp >= end_ts)
112 } else {
113 // Point-in-time entry
114 self.timestamp >= start_ts && self.timestamp <= end_ts
115 }
116 }
117}
118
119#[derive(Debug, Clone)]
120pub struct TemporalQuery {
121 pub start_time: Option<CalClock>,
122 pub end_time: Option<CalClock>,
123 pub category_filter: Option<String>,
124 pub recurrence_filter: Option<String>,
125 pub business_days_only: bool,
126 pub exclude_holidays: bool,
127 pub min_priority: Option<u8>, // inclusive floor
128 pub limit: Option<usize>,
129 pub sort_order: SortOrder,
130}
131
132#[derive(Debug, Clone, PartialEq)]
133pub enum SortOrder {
134 TimeAscending, // chronological
135 TimeDescending,
136 PriorityThenTime,
137 CategoryThenTime,
138}
139
140impl Default for TemporalQuery {
141 fn default() -> Self {
142 TemporalQuery {
143 start_time: None,
144 end_time: None,
145 category_filter: None,
146 recurrence_filter: None,
147 business_days_only: false,
148 exclude_holidays: false,
149 min_priority: None,
150 limit: None,
151 sort_order: SortOrder::TimeAscending,
152 }
153 }
154}
155
156impl TemporalQuery {
157 pub fn new() -> Self {
158 Self::default()
159 }
160
161 pub fn time_range(mut self, start: CalClock, end: CalClock) -> Self {
162 self.start_time = Some(start);
163 self.end_time = Some(end);
164 self
165 }
166
167 pub fn category(mut self, category: String) -> Self {
168 self.category_filter = Some(category);
169 self
170 }
171
172 pub fn recurrence(mut self, recurrence_id: String) -> Self {
173 self.recurrence_filter = Some(recurrence_id);
174 self
175 }
176
177 pub fn business_days_only(mut self) -> Self {
178 self.business_days_only = true;
179 self
180 }
181
182 pub fn exclude_holidays(mut self) -> Self {
183 self.exclude_holidays = true;
184 self
185 }
186
187 pub fn min_priority(mut self, priority: u8) -> Self {
188 self.min_priority = Some(priority);
189 self
190 }
191
192 pub fn limit(mut self, limit: usize) -> Self {
193 self.limit = Some(limit);
194 self
195 }
196
197 pub fn sort_by(mut self, order: SortOrder) -> Self {
198 self.sort_order = order;
199 self
200 }
201}
202
203#[derive(Debug)]
204pub struct TemporalBTree<T: Clone> {
205 // The primary tree owns clones of the entries. Each secondary index is
206 // keyed by its attribute and then by timestamp, and holds positions into
207 // `all_entries`, so a query can pick whichever index narrows the search
208 // most and still come out in time order.
209 primary_tree: BTreeMap<i64, Vec<TemporalEntry<T>>>,
210 category_index: BTreeMap<String, BTreeMap<i64, Vec<usize>>>,
211 recurrence_index: BTreeMap<String, BTreeMap<i64, Vec<usize>>>,
212 business_day_index: BTreeMap<i64, Vec<usize>>,
213 priority_index: BTreeMap<u8, BTreeMap<i64, Vec<usize>>>,
214 all_entries: Vec<TemporalEntry<T>>,
215 #[allow(dead_code)]
216 zone: CalClockZone,
217}
218
219impl<T: Clone> TemporalBTree<T> {
220 pub fn new(zone: CalClockZone) -> Self {
221 TemporalBTree {
222 primary_tree: BTreeMap::new(),
223 category_index: BTreeMap::new(),
224 recurrence_index: BTreeMap::new(),
225 business_day_index: BTreeMap::new(),
226 priority_index: BTreeMap::new(),
227 all_entries: Vec::new(),
228 zone,
229 }
230 }
231
232 /// Returns the position of the new entry, which the secondary indexes use to refer to it.
233 pub fn insert(&mut self, entry: TemporalEntry<T>) -> Outcome<usize> {
234 let entry_index = self.all_entries.len();
235 let timestamp = entry.timestamp;
236
237 // Add to primary tree
238 self.primary_tree
239 .entry(timestamp)
240 .or_insert_with(Vec::new)
241 .push(entry.clone());
242
243 // Add to secondary indexes
244 self.add_to_secondary_indexes(entry_index, &entry);
245
246 // Store the entry
247 self.all_entries.push(entry);
248
249 Ok(entry_index)
250 }
251
252 fn add_to_secondary_indexes(&mut self, entry_index: usize, entry: &TemporalEntry<T>) {
253 let timestamp = entry.timestamp;
254
255 // Category index
256 if let Some(ref category) = entry.temporal_attrs.category {
257 self.category_index
258 .entry(category.clone())
259 .or_insert_with(BTreeMap::new)
260 .entry(timestamp)
261 .or_insert_with(Vec::new)
262 .push(entry_index);
263 }
264
265 // Recurrence index
266 if let Some(ref recurrence_id) = entry.temporal_attrs.recurrence_id {
267 self.recurrence_index
268 .entry(recurrence_id.clone())
269 .or_insert_with(BTreeMap::new)
270 .entry(timestamp)
271 .or_insert_with(Vec::new)
272 .push(entry_index);
273 }
274
275 // Business day index
276 if entry.temporal_attrs.is_business_day {
277 self.business_day_index
278 .entry(timestamp)
279 .or_insert_with(Vec::new)
280 .push(entry_index);
281 }
282
283 // Priority index
284 self.priority_index
285 .entry(entry.temporal_attrs.priority)
286 .or_insert_with(BTreeMap::new)
287 .entry(timestamp)
288 .or_insert_with(Vec::new)
289 .push(entry_index);
290 }
291
292 pub fn query(&self, query: &TemporalQuery) -> Outcome<Vec<&TemporalEntry<T>>> {
293 let mut results = Vec::new();
294
295 // Determine time range
296 let (start_ts, end_ts) = if let (Some(start), Some(end)) = (&query.start_time, &query.end_time) {
297 (res!(start.to_millis()), res!(end.to_millis()))
298 } else if let Some(start) = &query.start_time {
299 (res!(start.to_millis()), i64::MAX)
300 } else if let Some(end) = &query.end_time {
301 (i64::MIN, res!(end.to_millis()))
302 } else {
303 (i64::MIN, i64::MAX)
304 };
305
306 // Choose the most selective index
307 let candidate_indices = ok!(self.get_candidate_indices(query, start_ts, end_ts));
308
309 // Filter candidates
310 for &entry_index in &candidate_indices {
311 if let Some(entry) = self.all_entries.get(entry_index) {
312 if self.matches_query(entry, query, start_ts, end_ts) {
313 results.push(entry);
314 }
315 }
316 }
317
318 // Sort results
319 self.sort_results(&mut results, &query.sort_order);
320
321 // Apply limit
322 if let Some(limit) = query.limit {
323 results.truncate(limit);
324 }
325
326 Ok(results)
327 }
328
329 /// Picks whichever index narrows the search most.
330 fn get_candidate_indices(&self, query: &TemporalQuery, start_ts: i64, end_ts: i64) -> Outcome<Vec<usize>> {
331 let mut candidates = Vec::new();
332
333 // Use the most selective index available
334 if let Some(ref category) = query.category_filter {
335 if let Some(category_tree) = self.category_index.get(category) {
336 for (_, indices) in category_tree.range(start_ts..=end_ts) {
337 candidates.extend(indices);
338 }
339 }
340 } else if let Some(ref recurrence) = query.recurrence_filter {
341 if let Some(recurrence_tree) = self.recurrence_index.get(recurrence) {
342 for (_, indices) in recurrence_tree.range(start_ts..=end_ts) {
343 candidates.extend(indices);
344 }
345 }
346 } else if query.business_days_only {
347 for (_, indices) in self.business_day_index.range(start_ts..=end_ts) {
348 candidates.extend(indices);
349 }
350 } else if let Some(priority) = query.min_priority {
351 for priority_level in priority..=255 {
352 if let Some(priority_tree) = self.priority_index.get(&priority_level) {
353 for (_, indices) in priority_tree.range(start_ts..=end_ts) {
354 candidates.extend(indices);
355 }
356 }
357 }
358 } else {
359 // Use primary tree - add all entries in range
360 for i in 0..self.all_entries.len() {
361 let entry = &self.all_entries[i];
362 if entry.timestamp >= start_ts && entry.timestamp <= end_ts {
363 candidates.push(i);
364 }
365 }
366 }
367
368 // Remove duplicates
369 candidates.sort();
370 candidates.dedup();
371
372 Ok(candidates)
373 }
374
375 fn matches_query(&self, entry: &TemporalEntry<T>, query: &TemporalQuery, start_ts: i64, end_ts: i64) -> bool {
376 // Time range check
377 if !entry.overlaps_range(start_ts, end_ts) {
378 return false;
379 }
380
381 // Category filter
382 if let Some(ref category) = query.category_filter {
383 if entry.temporal_attrs.category.as_ref() != Some(category) {
384 return false;
385 }
386 }
387
388 // Recurrence filter
389 if let Some(ref recurrence) = query.recurrence_filter {
390 if entry.temporal_attrs.recurrence_id.as_ref() != Some(recurrence) {
391 return false;
392 }
393 }
394
395 // Business days filter
396 if query.business_days_only && !entry.temporal_attrs.is_business_day {
397 return false;
398 }
399
400 // Holiday exclusion
401 if query.exclude_holidays && entry.temporal_attrs.is_holiday {
402 return false;
403 }
404
405 // Priority filter
406 if let Some(min_priority) = query.min_priority {
407 if entry.temporal_attrs.priority < min_priority {
408 return false;
409 }
410 }
411
412 true
413 }
414
415 fn sort_results(&self, results: &mut Vec<&TemporalEntry<T>>, sort_order: &SortOrder) {
416 match sort_order {
417 SortOrder::TimeAscending => {
418 results.sort_by(|a, b| a.timestamp.cmp(&b.timestamp));
419 }
420 SortOrder::TimeDescending => {
421 results.sort_by(|a, b| b.timestamp.cmp(&a.timestamp));
422 }
423 SortOrder::PriorityThenTime => {
424 results.sort_by(|a, b| {
425 match b.temporal_attrs.priority.cmp(&a.temporal_attrs.priority) {
426 Ordering::Equal => a.timestamp.cmp(&b.timestamp),
427 other => other,
428 }
429 });
430 }
431 SortOrder::CategoryThenTime => {
432 results.sort_by(|a, b| {
433 match a.temporal_attrs.category.cmp(&b.temporal_attrs.category) {
434 Ordering::Equal => a.timestamp.cmp(&b.timestamp),
435 other => other,
436 }
437 });
438 }
439 }
440 }
441
442 /// Nearest in either direction.
443 pub fn find_nearest(&self, target: &CalClock) -> Outcome<Option<&TemporalEntry<T>>> {
444 let target_ts = res!(target.to_millis());
445
446 let mut nearest: Option<&TemporalEntry<T>> = None;
447 let mut min_distance = i64::MAX;
448
449 // Search around the target timestamp
450 let search_range = 100; // entries to check on each side
451 let mut count = 0;
452
453 // Check entries before and after target
454 for (_, entries) in self.primary_tree.iter() {
455 for entry in entries {
456 let distance = (entry.timestamp - target_ts).abs();
457 if distance < min_distance {
458 min_distance = distance;
459 nearest = Some(entry);
460 }
461 }
462 count += 1;
463 if count > search_range {
464 break;
465 }
466 }
467
468 Ok(nearest)
469 }
470
471 pub fn find_within_duration(&self, target: &CalClock, duration_millis: i64) -> Outcome<Vec<&TemporalEntry<T>>> {
472 let target_ts = res!(target.to_millis());
473 let start_ts = target_ts - duration_millis;
474 let end_ts = target_ts + duration_millis;
475
476 let mut results = Vec::new();
477
478 for (_, entries) in self.primary_tree.range(start_ts..=end_ts) {
479 results.extend(entries.iter());
480 }
481
482 Ok(results)
483 }
484
485 pub fn statistics(&self) -> TemporalStatistics {
486 TemporalStatistics {
487 total_entries: self.all_entries.len(),
488 unique_timestamps: self.primary_tree.len(),
489 categories: self.category_index.len(),
490 recurrence_patterns: self.recurrence_index.len(),
491 business_day_entries: self.business_day_index.values().map(|v| v.len()).sum(),
492 priority_levels: self.priority_index.len(),
493 }
494 }
495
496 pub fn len(&self) -> usize {
497 self.all_entries.len()
498 }
499
500 pub fn is_empty(&self) -> bool {
501 self.all_entries.is_empty()
502 }
503}
504
505#[derive(Debug, Clone)]
506pub struct TemporalStatistics {
507 pub total_entries: usize,
508 pub unique_timestamps: usize,
509 pub categories: usize,
510 pub recurrence_patterns: usize,
511 pub business_day_entries: usize,
512 pub priority_levels: usize,
513}
514
515impl fmt::Display for TemporalStatistics {
516 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
517 write!(f,
518 "Temporal B-Tree Statistics:\n\
519 - Total entries: {}\n\
520 - Unique timestamps: {}\n\
521 - Categories: {}\n\
522 - Recurrence patterns: {}\n\
523 - Business day entries: {}\n\
524 - Priority levels: {}",
525 self.total_entries,
526 self.unique_timestamps,
527 self.categories,
528 self.recurrence_patterns,
529 self.business_day_entries,
530 self.priority_levels
531 )
532 }
533}
534
535#[cfg(test)]
536mod tests {
537 use super::*;
538
539 #[test]
540 fn test_temporal_btree_basic_operations() {
541 let zone = CalClockZone::utc();
542 let mut btree = TemporalBTree::new(zone.clone());
543
544 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
545 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
546
547 let entry1 = TemporalEntry::new(time1, "data1").unwrap()
548 .with_category("work".to_string())
549 .with_priority(1);
550
551 let entry2 = TemporalEntry::new(time2, "data2").unwrap()
552 .with_category("personal".to_string())
553 .with_priority(2);
554
555 btree.insert(entry1).unwrap();
556 btree.insert(entry2).unwrap();
557
558 assert_eq!(btree.len(), 2);
559 }
560
561 #[test]
562 fn test_temporal_query_by_category() {
563 let zone = CalClockZone::utc();
564 let mut btree = TemporalBTree::new(zone.clone());
565
566 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
567 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
568 let time3 = CalClock::new(2024, 1, 16, 9, 0, 0, 0, zone.clone()).unwrap();
569
570 let entry1 = TemporalEntry::new(time1, "work1").unwrap()
571 .with_category("work".to_string());
572
573 let entry2 = TemporalEntry::new(time2, "personal1").unwrap()
574 .with_category("personal".to_string());
575
576 let entry3 = TemporalEntry::new(time3, "work2").unwrap()
577 .with_category("work".to_string());
578
579 btree.insert(entry1).unwrap();
580 btree.insert(entry2).unwrap();
581 btree.insert(entry3).unwrap();
582
583 let query = TemporalQuery::new()
584 .category("work".to_string());
585
586 let results = btree.query(&query).unwrap();
587 assert_eq!(results.len(), 2);
588 }
589
590 #[test]
591 fn test_temporal_query_with_time_range() {
592 let zone = CalClockZone::utc();
593 let mut btree = TemporalBTree::new(zone.clone());
594
595 let time1 = CalClock::new(2024, 1, 10, 12, 0, 0, 0, zone.clone()).unwrap();
596 let time2 = CalClock::new(2024, 1, 15, 12, 0, 0, 0, zone.clone()).unwrap();
597 let time3 = CalClock::new(2024, 1, 20, 12, 0, 0, 0, zone.clone()).unwrap();
598 let time4 = CalClock::new(2024, 1, 25, 12, 0, 0, 0, zone.clone()).unwrap();
599
600 let entry1 = TemporalEntry::new(time1, "entry1").unwrap();
601 let entry2 = TemporalEntry::new(time2, "entry2").unwrap();
602 let entry3 = TemporalEntry::new(time3, "entry3").unwrap();
603 let entry4 = TemporalEntry::new(time4, "entry4").unwrap();
604
605 btree.insert(entry1).unwrap();
606 btree.insert(entry2).unwrap();
607 btree.insert(entry3).unwrap();
608 btree.insert(entry4).unwrap();
609
610 let start = CalClock::new(2024, 1, 12, 0, 0, 0, 0, zone.clone()).unwrap();
611 let end = CalClock::new(2024, 1, 22, 23, 59, 59, 0, zone).unwrap();
612
613 let query = TemporalQuery::new()
614 .time_range(start, end);
615
616 let results = btree.query(&query).unwrap();
617 assert_eq!(results.len(), 2); // Should include time2 and time3
618 }
619
620 #[test]
621 fn test_priority_sorting() {
622 let zone = CalClockZone::utc();
623 let mut btree = TemporalBTree::new(zone.clone());
624
625 let time = CalClock::new(2024, 1, 15, 12, 0, 0, 0, zone.clone()).unwrap();
626
627 let entry1 = TemporalEntry::new(time.clone(), "low").unwrap().with_priority(1);
628 let entry2 = TemporalEntry::new(time.clone(), "high").unwrap().with_priority(5);
629 let entry3 = TemporalEntry::new(time, "medium").unwrap().with_priority(3);
630
631 btree.insert(entry1).unwrap();
632 btree.insert(entry2).unwrap();
633 btree.insert(entry3).unwrap();
634
635 let query = TemporalQuery::new()
636 .sort_by(SortOrder::PriorityThenTime);
637
638 let results = btree.query(&query).unwrap();
639 assert_eq!(results.len(), 3);
640 assert_eq!(results[0].temporal_attrs.priority, 5); // Highest priority first
641 assert_eq!(results[1].temporal_attrs.priority, 3);
642 assert_eq!(results[2].temporal_attrs.priority, 1);
643 }
644
645 #[test]
646 fn test_nearest_entry_search() {
647 let zone = CalClockZone::utc();
648 let mut btree = TemporalBTree::new(zone.clone());
649
650 let time1 = CalClock::new(2024, 1, 15, 10, 0, 0, 0, zone.clone()).unwrap();
651 let time2 = CalClock::new(2024, 1, 15, 16, 0, 0, 0, zone.clone()).unwrap();
652
653 let entry1 = TemporalEntry::new(time1, "morning").unwrap();
654 let entry2 = TemporalEntry::new(time2, "afternoon").unwrap();
655
656 btree.insert(entry1).unwrap();
657 btree.insert(entry2).unwrap();
658
659 let target = CalClock::new(2024, 1, 15, 12, 0, 0, 0, zone).unwrap();
660 let nearest = btree.find_nearest(&target).unwrap();
661
662 assert!(nearest.is_some());
663 // Should find the 10:00 entry as it's closer to 12:00 than 16:00
664 assert_eq!(nearest.unwrap().data, "morning");
665 }
666
667 #[test]
668 fn test_statistics() {
669 let zone = CalClockZone::utc();
670 let mut btree = TemporalBTree::new(zone.clone());
671
672 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
673 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
674
675 let entry1 = TemporalEntry::new(time1, "data1").unwrap()
676 .with_category("work".to_string())
677 .with_business_day(true);
678
679 let entry2 = TemporalEntry::new(time2, "data2").unwrap()
680 .with_category("personal".to_string())
681 .with_business_day(false);
682
683 btree.insert(entry1).unwrap();
684 btree.insert(entry2).unwrap();
685
686 let stats = btree.statistics();
687 assert_eq!(stats.total_entries, 2);
688 assert_eq!(stats.categories, 2);
689 assert_eq!(stats.business_day_entries, 1);
690 }
691}