Oregami
Repositories/oxedyne/fe2o3

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

16.4 KiB, 62 runs

created by r1870400018:8466, 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//! Primary time indexing structure for fast temporal lookups.
2//!
3//! A TimeIndex stores entries in chronological order and maintains secondary
4//! indexes at coarser granularities, so a lookup by year or by day of week
5//! costs no scan.
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::{HashMap, BTreeMap},
14 fmt,
15 hash::Hash,
16};
17
18#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
19pub enum IndexKey {
20 Timestamp(i64), // Unix milliseconds
21 Date(i32, u8, u8), // year, month, day
22 Month(i32, u8), // year, month
23 Year(i32),
24 TimeOfDay(u8, u8), // hour, minute
25 DayOfWeek(u8), // 1 is Monday, 7 is Sunday
26 Custom(String),
27}
28
29impl IndexKey {
30 pub fn from_timestamp(calclock: &CalClock) -> Outcome<Self> {
31 let timestamp = res!(calclock.to_millis());
32 Ok(IndexKey::Timestamp(timestamp))
33 }
34
35 pub fn from_date(calclock: &CalClock) -> Self {
36 IndexKey::Date(
37 calclock.year(),
38 calclock.month(),
39 calclock.day(),
40 )
41 }
42
43 pub fn from_month(calclock: &CalClock) -> Self {
44 IndexKey::Month(calclock.year(), calclock.month())
45 }
46
47 pub fn from_year(calclock: &CalClock) -> Self {
48 IndexKey::Year(calclock.year())
49 }
50
51 pub fn from_time_of_day(calclock: &CalClock) -> Self {
52 IndexKey::TimeOfDay(calclock.hour(), calclock.minute())
53 }
54
55 pub fn from_day_of_week(calclock: &CalClock) -> Self {
56 IndexKey::DayOfWeek(calclock.day_of_week().of())
57 }
58}
59
60impl fmt::Display for IndexKey {
61 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
62 match self {
63 IndexKey::Timestamp(ts) => write!(f, "ts:{}", ts),
64 IndexKey::Date(y, m, d) => write!(f, "date:{:04}-{:02}-{:02}", y, m, d),
65 IndexKey::Month(y, m) => write!(f, "month:{:04}-{:02}", y, m),
66 IndexKey::Year(y) => write!(f, "year:{}", y),
67 IndexKey::TimeOfDay(h, m) => write!(f, "time:{:02}:{:02}", h, m),
68 IndexKey::DayOfWeek(d) => write!(f, "dow:{}", d),
69 IndexKey::Custom(s) => write!(f, "custom:{}", s),
70 }
71 }
72}
73
74#[derive(Debug, Clone)]
75pub struct TimeIndexEntry<T>
76where
77 T: Clone,
78{
79 pub time: CalClock,
80 pub data: T,
81 pub metadata: HashMap<String, String>,
82}
83
84impl<T: Clone> TimeIndexEntry<T> {
85 pub fn new(time: CalClock, data: T) -> Self {
86 TimeIndexEntry {
87 time,
88 data,
89 metadata: HashMap::new(),
90 }
91 }
92
93 pub fn with_metadata(time: CalClock, data: T, metadata: HashMap<String, String>) -> Self {
94 TimeIndexEntry {
95 time,
96 data,
97 metadata,
98 }
99 }
100
101 pub fn add_metadata(mut self, key: String, value: String) -> Self {
102 self.metadata.insert(key, value);
103 self
104 }
105
106 pub fn get_metadata(&self, key: &str) -> Option<&String> {
107 self.metadata.get(key)
108 }
109}
110
111#[derive(Debug)]
112pub struct TimeIndex<T: Clone> {
113 // The timestamp index owns clones of the entries and keeps them in
114 // chronological order. Every other index holds positions into `entries`
115 // instead, so a coarser granularity costs one usize per entry.
116 timestamp_index: BTreeMap<i64, Vec<TimeIndexEntry<T>>>,
117 date_index: HashMap<IndexKey, Vec<usize>>,
118 month_index: HashMap<IndexKey, Vec<usize>>,
119 year_index: HashMap<IndexKey, Vec<usize>>,
120 time_of_day_index: HashMap<IndexKey, Vec<usize>>,
121 day_of_week_index: HashMap<IndexKey, Vec<usize>>,
122 custom_indexes: HashMap<String, HashMap<IndexKey, Vec<usize>>>,
123 entries: Vec<TimeIndexEntry<T>>,
124 #[allow(dead_code)]
125 zone: CalClockZone,
126}
127
128impl<T: Clone> TimeIndex<T> {
129 pub fn new(zone: CalClockZone) -> Self {
130 TimeIndex {
131 timestamp_index: BTreeMap::new(),
132 date_index: HashMap::new(),
133 month_index: HashMap::new(),
134 year_index: HashMap::new(),
135 time_of_day_index: HashMap::new(),
136 day_of_week_index: HashMap::new(),
137 custom_indexes: HashMap::new(),
138 entries: Vec::new(),
139 zone,
140 }
141 }
142
143 /// Returns the position of the new entry, which every secondary index uses to refer to it.
144 pub fn insert(&mut self, entry: TimeIndexEntry<T>) -> Outcome<usize> {
145 let index_id = self.entries.len();
146
147 // Generate timestamp key
148 let timestamp = res!(entry.time.to_millis());
149
150 // Add to timestamp index
151 self.timestamp_index
152 .entry(timestamp)
153 .or_insert_with(Vec::new)
154 .push(entry.clone());
155
156 // Add to secondary indexes
157 self.add_to_secondary_indexes(index_id, &entry);
158
159 // Store the entry
160 self.entries.push(entry);
161
162 Ok(index_id)
163 }
164
165 fn add_to_secondary_indexes(&mut self, index_id: usize, entry: &TimeIndexEntry<T>) {
166 // Date index
167 let date_key = IndexKey::from_date(&entry.time);
168 self.date_index
169 .entry(date_key)
170 .or_insert_with(Vec::new)
171 .push(index_id);
172
173 // Month index
174 let month_key = IndexKey::from_month(&entry.time);
175 self.month_index
176 .entry(month_key)
177 .or_insert_with(Vec::new)
178 .push(index_id);
179
180 // Year index
181 let year_key = IndexKey::from_year(&entry.time);
182 self.year_index
183 .entry(year_key)
184 .or_insert_with(Vec::new)
185 .push(index_id);
186
187 // Time of day index
188 let time_key = IndexKey::from_time_of_day(&entry.time);
189 self.time_of_day_index
190 .entry(time_key)
191 .or_insert_with(Vec::new)
192 .push(index_id);
193
194 // Day of week index
195 let dow_key = IndexKey::from_day_of_week(&entry.time);
196 self.day_of_week_index
197 .entry(dow_key)
198 .or_insert_with(Vec::new)
199 .push(index_id);
200 }
201
202 pub fn find_by_timestamp(&self, timestamp: i64) -> Vec<&TimeIndexEntry<T>> {
203 self.timestamp_index
204 .get(&timestamp)
205 .map(|entries| entries.iter().collect())
206 .unwrap_or_default()
207 }
208
209 pub fn find_by_date(&self, year: i32, month: u8, day: u8) -> Vec<&TimeIndexEntry<T>> {
210 let key = IndexKey::Date(year, month, day);
211 self.find_by_secondary_index(&self.date_index, &key)
212 }
213
214 pub fn find_by_month(&self, year: i32, month: u8) -> Vec<&TimeIndexEntry<T>> {
215 let key = IndexKey::Month(year, month);
216 self.find_by_secondary_index(&self.month_index, &key)
217 }
218
219 pub fn find_by_year(&self, year: i32) -> Vec<&TimeIndexEntry<T>> {
220 let key = IndexKey::Year(year);
221 self.find_by_secondary_index(&self.year_index, &key)
222 }
223
224 pub fn find_by_time_of_day(&self, hour: u8, minute: u8) -> Vec<&TimeIndexEntry<T>> {
225 let key = IndexKey::TimeOfDay(hour, minute);
226 self.find_by_secondary_index(&self.time_of_day_index, &key)
227 }
228
229 pub fn find_by_day_of_week(&self, day_of_week: u8) -> Vec<&TimeIndexEntry<T>> {
230 let key = IndexKey::DayOfWeek(day_of_week);
231 self.find_by_secondary_index(&self.day_of_week_index, &key)
232 }
233
234 fn find_by_secondary_index(&self, index: &HashMap<IndexKey, Vec<usize>>, key: &IndexKey) -> Vec<&TimeIndexEntry<T>> {
235 index
236 .get(key)
237 .map(|indices| {
238 indices
239 .iter()
240 .filter_map(|&i| self.entries.get(i))
241 .collect()
242 })
243 .unwrap_or_default()
244 }
245
246 pub fn find_in_range(&self, start_timestamp: i64, end_timestamp: i64) -> Vec<&TimeIndexEntry<T>> {
247 self.timestamp_index
248 .range(start_timestamp..=end_timestamp)
249 .flat_map(|(_, entries)| entries.iter())
250 .collect()
251 }
252
253 pub fn find_in_time_range(&self, start: &CalClock, end: &CalClock) -> Outcome<Vec<&TimeIndexEntry<T>>> {
254 let start_ts = res!(start.to_millis());
255 let end_ts = res!(end.to_millis());
256 Ok(self.find_in_range(start_ts, end_ts))
257 }
258
259 pub fn create_custom_index<F>(&mut self, name: String, key_extractor: F) -> Outcome<()>
260 where
261 F: Fn(&TimeIndexEntry<T>) -> Vec<IndexKey>,
262 {
263 let mut custom_index = HashMap::new();
264
265 for (index_id, entry) in self.entries.iter().enumerate() {
266 let keys = key_extractor(entry);
267 for key in keys {
268 custom_index
269 .entry(key)
270 .or_insert_with(Vec::new)
271 .push(index_id);
272 }
273 }
274
275 self.custom_indexes.insert(name, custom_index);
276 Ok(())
277 }
278
279 pub fn find_by_custom_index(&self, index_name: &str, key: &IndexKey) -> Vec<&TimeIndexEntry<T>> {
280 self.custom_indexes
281 .get(index_name)
282 .and_then(|index| index.get(key))
283 .map(|indices| {
284 indices
285 .iter()
286 .filter_map(|&i| self.entries.get(i))
287 .collect()
288 })
289 .unwrap_or_default()
290 }
291
292 pub fn len(&self) -> usize {
293 self.entries.len()
294 }
295
296 pub fn is_empty(&self) -> bool {
297 self.entries.is_empty()
298 }
299
300 pub fn iter_chronological(&self) -> impl Iterator<Item = &TimeIndexEntry<T>> {
301 self.timestamp_index
302 .values()
303 .flat_map(|entries| entries.iter())
304 }
305
306 pub fn statistics(&self) -> IndexStatistics {
307 IndexStatistics {
308 total_entries: self.entries.len(),
309 unique_timestamps: self.timestamp_index.len(),
310 unique_dates: self.date_index.len(),
311 unique_months: self.month_index.len(),
312 unique_years: self.year_index.len(),
313 unique_times_of_day: self.time_of_day_index.len(),
314 custom_indexes: self.custom_indexes.len(),
315 }
316 }
317}
318
319#[derive(Debug, Clone)]
320pub struct IndexStatistics {
321 pub total_entries: usize,
322 pub unique_timestamps: usize,
323 pub unique_dates: usize,
324 pub unique_months: usize,
325 pub unique_years: usize,
326 pub unique_times_of_day: usize,
327 pub custom_indexes: usize,
328}
329
330impl fmt::Display for IndexStatistics {
331 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
332 write!(f,
333 "Index Statistics:\n\
334 - Total entries: {}\n\
335 - Unique timestamps: {}\n\
336 - Unique dates: {}\n\
337 - Unique months: {}\n\
338 - Unique years: {}\n\
339 - Unique times of day: {}\n\
340 - Custom indexes: {}",
341 self.total_entries,
342 self.unique_timestamps,
343 self.unique_dates,
344 self.unique_months,
345 self.unique_years,
346 self.unique_times_of_day,
347 self.custom_indexes
348 )
349 }
350}
351
352#[cfg(test)]
353mod tests {
354 use super::*;
355
356 #[test]
357 fn test_time_index_basic_operations() {
358 let zone = CalClockZone::utc();
359 let mut index = TimeIndex::new(zone.clone());
360
361 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
362 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
363
364 let entry1 = TimeIndexEntry::new(time1, "data1");
365 let entry2 = TimeIndexEntry::new(time2, "data2");
366
367 let id1 = index.insert(entry1).unwrap();
368 let id2 = index.insert(entry2).unwrap();
369
370 assert_eq!(index.len(), 2);
371 assert_eq!(id1, 0);
372 assert_eq!(id2, 1);
373 }
374
375 #[test]
376 fn test_date_based_lookups() {
377 let zone = CalClockZone::utc();
378 let mut index = TimeIndex::new(zone.clone());
379
380 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
381 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
382 let time3 = CalClock::new(2024, 1, 16, 9, 0, 0, 0, zone.clone()).unwrap();
383
384 index.insert(TimeIndexEntry::new(time1, "data1")).unwrap();
385 index.insert(TimeIndexEntry::new(time2, "data2")).unwrap();
386 index.insert(TimeIndexEntry::new(time3, "data3")).unwrap();
387
388 let jan_15_entries = index.find_by_date(2024, 1, 15);
389 assert_eq!(jan_15_entries.len(), 2);
390
391 let jan_16_entries = index.find_by_date(2024, 1, 16);
392 assert_eq!(jan_16_entries.len(), 1);
393
394 let jan_entries = index.find_by_month(2024, 1);
395 assert_eq!(jan_entries.len(), 3);
396 }
397
398 #[test]
399 fn test_time_of_day_lookups() {
400 let zone = CalClockZone::utc();
401 let mut index = TimeIndex::new(zone.clone());
402
403 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
404 let time2 = CalClock::new(2024, 2, 20, 10, 30, 0, 0, zone.clone()).unwrap();
405 let time3 = CalClock::new(2024, 3, 25, 14, 45, 0, 0, zone.clone()).unwrap();
406
407 index.insert(TimeIndexEntry::new(time1, "morning1")).unwrap();
408 index.insert(TimeIndexEntry::new(time2, "morning2")).unwrap();
409 index.insert(TimeIndexEntry::new(time3, "afternoon")).unwrap();
410
411 let morning_entries = index.find_by_time_of_day(10, 30);
412 assert_eq!(morning_entries.len(), 2);
413
414 let afternoon_entries = index.find_by_time_of_day(14, 45);
415 assert_eq!(afternoon_entries.len(), 1);
416 }
417
418 #[test]
419 fn test_range_queries() {
420 let zone = CalClockZone::utc();
421 let mut index = TimeIndex::new(zone.clone());
422
423 let time1 = CalClock::new(2024, 1, 10, 12, 0, 0, 0, zone.clone()).unwrap();
424 let time2 = CalClock::new(2024, 1, 15, 12, 0, 0, 0, zone.clone()).unwrap();
425 let time3 = CalClock::new(2024, 1, 20, 12, 0, 0, 0, zone.clone()).unwrap();
426 let time4 = CalClock::new(2024, 1, 25, 12, 0, 0, 0, zone.clone()).unwrap();
427
428 index.insert(TimeIndexEntry::new(time1, "entry1")).unwrap();
429 index.insert(TimeIndexEntry::new(time2, "entry2")).unwrap();
430 index.insert(TimeIndexEntry::new(time3, "entry3")).unwrap();
431 index.insert(TimeIndexEntry::new(time4, "entry4")).unwrap();
432
433 let start = CalClock::new(2024, 1, 12, 0, 0, 0, 0, zone.clone()).unwrap();
434 let end = CalClock::new(2024, 1, 22, 23, 59, 59, 0, zone).unwrap();
435
436 let range_entries = index.find_in_time_range(&start, &end).unwrap();
437 assert_eq!(range_entries.len(), 2); // Should include time2 and time3
438 }
439
440 #[test]
441 fn test_custom_index() {
442 let zone = CalClockZone::utc();
443 let mut index = TimeIndex::new(zone.clone());
444
445 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
446 let time2 = CalClock::new(2024, 1, 16, 14, 45, 0, 0, zone.clone()).unwrap();
447
448 let mut entry1 = TimeIndexEntry::new(time1, "data1");
449 entry1.metadata.insert("category".to_string(), "work".to_string());
450
451 let mut entry2 = TimeIndexEntry::new(time2, "data2");
452 entry2.metadata.insert("category".to_string(), "personal".to_string());
453
454 index.insert(entry1).unwrap();
455 index.insert(entry2).unwrap();
456
457 // Create custom index based on category metadata
458 index.create_custom_index("category".to_string(), |entry| {
459 if let Some(category) = entry.metadata.get("category") {
460 vec![IndexKey::Custom(category.clone())]
461 } else {
462 vec![]
463 }
464 }).unwrap();
465
466 let work_entries = index.find_by_custom_index("category", &IndexKey::Custom("work".to_string()));
467 assert_eq!(work_entries.len(), 1);
468
469 let personal_entries = index.find_by_custom_index("category", &IndexKey::Custom("personal".to_string()));
470 assert_eq!(personal_entries.len(), 1);
471 }
472
473 #[test]
474 fn test_index_statistics() {
475 let zone = CalClockZone::utc();
476 let mut index = TimeIndex::new(zone.clone());
477
478 let time1 = CalClock::new(2024, 1, 15, 10, 30, 0, 0, zone.clone()).unwrap();
479 let time2 = CalClock::new(2024, 1, 15, 14, 45, 0, 0, zone.clone()).unwrap();
480 let time3 = CalClock::new(2024, 2, 20, 10, 30, 0, 0, zone.clone()).unwrap();
481
482 index.insert(TimeIndexEntry::new(time1, "data1")).unwrap();
483 index.insert(TimeIndexEntry::new(time2, "data2")).unwrap();
484 index.insert(TimeIndexEntry::new(time3, "data3")).unwrap();
485
486 let stats = index.statistics();
487 assert_eq!(stats.total_entries, 3);
488 assert_eq!(stats.unique_dates, 2);
489 assert_eq!(stats.unique_months, 2);
490 assert_eq!(stats.unique_years, 1);
491 assert_eq!(stats.unique_times_of_day, 2);
492 }
493}