copc_temporal/
temporal_index.rs

1use std::collections::HashMap;
2use std::io::Cursor;
3use std::ops::Range;
4
5use byteorder::{LittleEndian, ReadBytesExt};
6
7use copc_streaming::VoxelKey;
8
9use crate::error::TemporalError;
10use crate::gps_time::GpsTime;
11use crate::vlr::VlrData;
12
13/// Per-node temporal data: a set of sampled GPS timestamps.
14#[derive(Debug, Clone)]
15pub struct NodeTemporalEntry {
16    /// The octree node this entry describes.
17    pub key: VoxelKey,
18    samples: Vec<GpsTime>,
19}
20
21impl NodeTemporalEntry {
22    /// Create a new entry with the given key and samples.
23    ///
24    /// # Panics
25    ///
26    /// Panics if `samples` is empty — every node must have at least one sample.
27    pub fn new(key: VoxelKey, samples: Vec<GpsTime>) -> Self {
28        assert!(
29            !samples.is_empty(),
30            "NodeTemporalEntry requires at least one sample"
31        );
32        Self { key, samples }
33    }
34
35    /// The sampled GPS time values for this node.
36    pub fn samples(&self) -> &[GpsTime] {
37        &self.samples
38    }
39
40    /// Returns (min_time, max_time) for this node.
41    pub fn time_range(&self) -> (GpsTime, GpsTime) {
42        (self.samples[0], self.samples[self.samples.len() - 1])
43    }
44
45    /// Returns true if this node may contain points in [start, end].
46    pub fn overlaps(&self, start: GpsTime, end: GpsTime) -> bool {
47        let (min, max) = self.time_range();
48        // Node overlaps if its max >= start AND its min <= end
49        max >= start && min <= end
50    }
51
52    /// Estimate the point index range within the decompressed chunk for a time range.
53    ///
54    /// Implements the binary search logic from spec section 8.2:
55    /// 1. Find first sample index `i` where `samples[i] >= t_start`
56    /// 2. Find last sample index `j` where `samples[j] <= t_end`
57    /// 3. Start point = i * stride
58    /// 4. End point = min(j * stride + stride - 1, point_count - 1)
59    pub fn estimate_point_range(
60        &self,
61        start: GpsTime,
62        end: GpsTime,
63        stride: u32,
64        point_count: u32,
65    ) -> Range<u32> {
66        if point_count == 0 {
67            return 0..0;
68        }
69
70        // First index i where samples[i] >= start
71        let i = self.samples.partition_point(|s| *s < start);
72
73        // Last index j where samples[j] <= end
74        // partition_point finds first index where samples[j] > end, subtract 1
75        let past_end = self.samples.partition_point(|s| *s <= end);
76
77        if i >= past_end {
78            // No samples in range
79            return 0..0;
80        }
81        let j = past_end - 1;
82
83        let start_point = (i as u64 * stride as u64).min(point_count as u64) as u32;
84        let end_point =
85            ((j as u64 * stride as u64 + stride as u64 - 1).min(point_count as u64 - 1)) as u32;
86
87        start_point..(end_point + 1)
88    }
89}
90
91/// The top-level temporal index parsed from an EVLR.
92/// Not part of the public API — used internally and in tests.
93#[derive(Debug, Clone)]
94#[cfg_attr(not(test), allow(dead_code))]
95pub(crate) struct TemporalIndex {
96    version: u32,
97    stride: u32,
98    entries: HashMap<VoxelKey, NodeTemporalEntry>,
99}
100
101#[cfg_attr(not(test), allow(dead_code))]
102impl TemporalIndex {
103    /// Parse the temporal index from a list of EVLRs.
104    ///
105    /// Returns `Ok(None)` if no temporal EVLR is present.
106    /// Returns `Err` if the EVLR is present but malformed.
107    pub fn from_evlrs(evlrs: &[VlrData]) -> Result<Option<Self>, TemporalError> {
108        let vlr = evlrs
109            .iter()
110            .find(|v| v.user_id == "copc_temporal" && v.record_id == 1000);
111
112        let vlr = match vlr {
113            Some(v) => v,
114            None => return Ok(None),
115        };
116
117        let data = &vlr.data;
118        if data.len() < 32 {
119            return Err(TemporalError::TruncatedHeader);
120        }
121
122        let mut cursor = Cursor::new(data);
123
124        let version = cursor.read_u32::<LittleEndian>()?;
125        if version != 1 {
126            return Err(TemporalError::UnsupportedVersion(version));
127        }
128
129        let stride = cursor.read_u32::<LittleEndian>()?;
130        if stride < 1 {
131            return Err(TemporalError::InvalidStride(stride));
132        }
133
134        let node_count = cursor.read_u32::<LittleEndian>()?;
135        let _page_count = cursor.read_u32::<LittleEndian>()?;
136        let _root_page_offset = cursor.read_u64::<LittleEndian>()?;
137        let _root_page_size = cursor.read_u32::<LittleEndian>()?;
138        let _reserved = cursor.read_u32::<LittleEndian>()?;
139
140        // For local file access, all pages are contiguous after the header.
141        // Scan sequentially, skipping page pointers (sample_count == 0).
142        let mut entries = HashMap::with_capacity(node_count as usize);
143
144        while entries.len() < node_count as usize {
145            let level = match cursor.read_i32::<LittleEndian>() {
146                Ok(v) => v,
147                Err(e) => return Err(TemporalError::Io(e)),
148            };
149            let x = cursor.read_i32::<LittleEndian>()?;
150            let y = cursor.read_i32::<LittleEndian>()?;
151            let z = cursor.read_i32::<LittleEndian>()?;
152            let sample_count = cursor.read_u32::<LittleEndian>()?;
153
154            if sample_count == 0 {
155                // Page pointer: skip the remaining 28 bytes
156                // (child_page_offset u64 + child_page_size u32 + subtree_time_min f64 + subtree_time_max f64)
157                cursor.set_position(cursor.position() + 28);
158                continue;
159            }
160
161            let mut samples = Vec::with_capacity(sample_count as usize);
162            for _ in 0..sample_count {
163                let t = cursor.read_f64::<LittleEndian>()?;
164                samples.push(GpsTime(t));
165            }
166
167            let key = VoxelKey { level, x, y, z };
168
169            entries.insert(key, NodeTemporalEntry { key, samples });
170        }
171
172        Ok(Some(TemporalIndex {
173            version,
174            stride,
175            entries,
176        }))
177    }
178
179    /// Look up the temporal entry for a given voxel key.
180    pub fn get(&self, key: &VoxelKey) -> Option<&NodeTemporalEntry> {
181        self.entries.get(key)
182    }
183
184    /// Return all node entries whose time range overlaps [start, end].
185    pub fn nodes_in_range(&self, start: GpsTime, end: GpsTime) -> Vec<&NodeTemporalEntry> {
186        self.entries
187            .values()
188            .filter(|e| e.overlaps(start, end))
189            .collect()
190    }
191
192    /// The sampling stride.
193    pub fn stride(&self) -> u32 {
194        self.stride
195    }
196
197    /// The format version.
198    pub fn version(&self) -> u32 {
199        self.version
200    }
201
202    /// The number of node entries.
203    pub fn len(&self) -> usize {
204        self.entries.len()
205    }
206}
207
208#[cfg(test)]
209mod tests {
210    use super::*;
211    use byteorder::WriteBytesExt;
212
213    /// Build a v2 EVLR payload: header (32 bytes) + single root page with all entries.
214    fn build_evlr_payload(
215        version: u32,
216        stride: u32,
217        nodes: &[(i32, i32, i32, i32, &[f64])],
218    ) -> Vec<u8> {
219        // Compute root page size
220        let mut page_size: u32 = 0;
221        for (_, _, _, _, samples) in nodes {
222            page_size += 20 + samples.len() as u32 * 8;
223        }
224
225        let mut buf = Vec::new();
226        // Header (32 bytes)
227        buf.write_u32::<LittleEndian>(version).unwrap();
228        buf.write_u32::<LittleEndian>(stride).unwrap();
229        buf.write_u32::<LittleEndian>(nodes.len() as u32).unwrap();
230        buf.write_u32::<LittleEndian>(1).unwrap(); // page_count
231        buf.write_u64::<LittleEndian>(32).unwrap(); // root_page_offset (relative to EVLR data start, used as absolute in tests)
232        buf.write_u32::<LittleEndian>(page_size).unwrap();
233        buf.write_u32::<LittleEndian>(0).unwrap(); // reserved
234
235        // Root page: all node entries
236        for &(level, x, y, z, samples) in nodes {
237            buf.write_i32::<LittleEndian>(level).unwrap();
238            buf.write_i32::<LittleEndian>(x).unwrap();
239            buf.write_i32::<LittleEndian>(y).unwrap();
240            buf.write_i32::<LittleEndian>(z).unwrap();
241            buf.write_u32::<LittleEndian>(samples.len() as u32).unwrap();
242            for &s in samples.iter() {
243                buf.write_f64::<LittleEndian>(s).unwrap();
244            }
245        }
246
247        buf
248    }
249
250    fn make_vlr(user_id: &str, record_id: u16, data: Vec<u8>) -> VlrData {
251        VlrData {
252            user_id: user_id.to_string(),
253            record_id,
254            data,
255        }
256    }
257
258    #[test]
259    fn test_parse_roundtrip() {
260        let samples_a: &[f64] = &[100.0, 200.0, 300.0];
261        let samples_b: &[f64] = &[400.0, 500.0];
262        let nodes = vec![(0, 0, 0, 0, samples_a), (1, 1, 0, 0, samples_b)];
263        let data = build_evlr_payload(1, 10, &nodes);
264        let vlr = make_vlr("copc_temporal", 1000, data);
265
266        let index = TemporalIndex::from_evlrs(&[vlr]).unwrap().unwrap();
267        assert_eq!(index.stride(), 10);
268        assert_eq!(index.version(), 1);
269        assert_eq!(index.len(), 2);
270
271        let entry_a = index
272            .get(&VoxelKey {
273                level: 0,
274                x: 0,
275                y: 0,
276                z: 0,
277            })
278            .unwrap();
279        assert_eq!(entry_a.samples().len(), 3);
280        assert_eq!(entry_a.samples()[0], GpsTime(100.0));
281        assert_eq!(entry_a.samples()[2], GpsTime(300.0));
282
283        let entry_b = index
284            .get(&VoxelKey {
285                level: 1,
286                x: 1,
287                y: 0,
288                z: 0,
289            })
290            .unwrap();
291        assert_eq!(entry_b.samples().len(), 2);
292        assert_eq!(entry_b.time_range(), (GpsTime(400.0), GpsTime(500.0)));
293    }
294
295    #[test]
296    fn test_no_temporal_evlr() {
297        let vlr = make_vlr("copc", 1, vec![0; 160]);
298        let result = TemporalIndex::from_evlrs(&[vlr]).unwrap();
299        assert!(result.is_none());
300    }
301
302    #[test]
303    fn test_empty_evlr_list() {
304        let result = TemporalIndex::from_evlrs(&[]).unwrap();
305        assert!(result.is_none());
306    }
307
308    #[test]
309    fn test_wrong_version() {
310        let data = build_evlr_payload(99, 10, &[]);
311        let vlr = make_vlr("copc_temporal", 1000, data);
312        let result = TemporalIndex::from_evlrs(&[vlr]);
313        assert!(matches!(result, Err(TemporalError::UnsupportedVersion(99))));
314    }
315
316    #[test]
317    fn test_truncated_header() {
318        let vlr = make_vlr("copc_temporal", 1000, vec![1, 0, 0, 0]); // only 4 bytes
319        let result = TemporalIndex::from_evlrs(&[vlr]);
320        assert!(matches!(result, Err(TemporalError::TruncatedHeader)));
321    }
322
323    #[test]
324    fn test_truncated_node_data() {
325        // Header says 1 node, but no node data follows
326        let data = build_evlr_payload(1, 10, &[]);
327        let mut modified = data.clone();
328        // Patch node_count to 1
329        modified[8] = 1;
330        let vlr = make_vlr("copc_temporal", 1000, modified);
331        let result = TemporalIndex::from_evlrs(&[vlr]);
332        assert!(result.is_err());
333    }
334
335    #[test]
336    fn test_overlaps_exact_boundaries() {
337        let entry = NodeTemporalEntry {
338            key: VoxelKey {
339                level: 0,
340                x: 0,
341                y: 0,
342                z: 0,
343            },
344            samples: vec![GpsTime(100.0), GpsTime(200.0), GpsTime(300.0)],
345        };
346
347        // Exact match on boundaries
348        assert!(entry.overlaps(GpsTime(100.0), GpsTime(300.0)));
349        // Query ends exactly at start
350        assert!(entry.overlaps(GpsTime(50.0), GpsTime(100.0)));
351        // Query starts exactly at end
352        assert!(entry.overlaps(GpsTime(300.0), GpsTime(400.0)));
353        // Query entirely before
354        assert!(!entry.overlaps(GpsTime(0.0), GpsTime(99.9)));
355        // Query entirely after
356        assert!(!entry.overlaps(GpsTime(300.1), GpsTime(400.0)));
357        // Query contains node
358        assert!(entry.overlaps(GpsTime(0.0), GpsTime(1000.0)));
359        // Query within node
360        assert!(entry.overlaps(GpsTime(150.0), GpsTime(250.0)));
361    }
362
363    #[test]
364    fn test_overlaps_single_sample() {
365        let entry = NodeTemporalEntry {
366            key: VoxelKey {
367                level: 0,
368                x: 0,
369                y: 0,
370                z: 0,
371            },
372            samples: vec![GpsTime(100.0)],
373        };
374
375        assert!(entry.overlaps(GpsTime(100.0), GpsTime(100.0)));
376        assert!(entry.overlaps(GpsTime(50.0), GpsTime(150.0)));
377        assert!(!entry.overlaps(GpsTime(50.0), GpsTime(99.9)));
378        assert!(!entry.overlaps(GpsTime(100.1), GpsTime(200.0)));
379    }
380
381    #[test]
382    fn test_nodes_in_range() {
383        let samples_a: &[f64] = &[100.0, 200.0, 300.0];
384        let samples_b: &[f64] = &[400.0, 500.0];
385        let samples_c: &[f64] = &[600.0, 700.0, 800.0];
386        let data = build_evlr_payload(
387            1,
388            10,
389            &[
390                (0, 0, 0, 0, samples_a),
391                (1, 0, 0, 0, samples_b),
392                (1, 1, 0, 0, samples_c),
393            ],
394        );
395        let vlr = make_vlr("copc_temporal", 1000, data);
396        let index = TemporalIndex::from_evlrs(&[vlr]).unwrap().unwrap();
397
398        // Should match only node A and B
399        let result = index.nodes_in_range(GpsTime(250.0), GpsTime(450.0));
400        assert_eq!(result.len(), 2);
401
402        // Should match only node C
403        let result = index.nodes_in_range(GpsTime(650.0), GpsTime(750.0));
404        assert_eq!(result.len(), 1);
405        assert_eq!(
406            result[0].key,
407            VoxelKey {
408                level: 1,
409                x: 1,
410                y: 0,
411                z: 0
412            }
413        );
414    }
415
416    #[test]
417    fn test_estimate_point_range_basic() {
418        // Samples at indices 0, 10, 20, 30, 39 (stride=10, 40 points)
419        let entry = NodeTemporalEntry {
420            key: VoxelKey {
421                level: 0,
422                x: 0,
423                y: 0,
424                z: 0,
425            },
426            samples: vec![
427                GpsTime(100.0),
428                GpsTime(200.0),
429                GpsTime(300.0),
430                GpsTime(400.0),
431                GpsTime(450.0),
432            ],
433        };
434
435        // Query covers samples[1] through samples[3] (200..400)
436        let range = entry.estimate_point_range(GpsTime(200.0), GpsTime(400.0), 10, 40);
437        // i=1 (first sample >= 200), j=3 (last sample <= 400)
438        // start = 1*10 = 10, end = min(3*10 + 9, 39) = 39
439        assert_eq!(range, 10..40);
440
441        // Query covers only sample[2] (300..300)
442        let range = entry.estimate_point_range(GpsTime(300.0), GpsTime(300.0), 10, 40);
443        // i=2, j=2
444        // start = 20, end = min(29, 39) = 29
445        assert_eq!(range, 20..30);
446    }
447
448    #[test]
449    fn test_estimate_point_range_no_overlap() {
450        let entry = NodeTemporalEntry {
451            key: VoxelKey {
452                level: 0,
453                x: 0,
454                y: 0,
455                z: 0,
456            },
457            samples: vec![GpsTime(100.0), GpsTime(200.0), GpsTime(300.0)],
458        };
459
460        // Query entirely before
461        let range = entry.estimate_point_range(GpsTime(0.0), GpsTime(50.0), 10, 30);
462        assert_eq!(range, 0..0);
463
464        // Query entirely after
465        let range = entry.estimate_point_range(GpsTime(400.0), GpsTime(500.0), 10, 30);
466        assert_eq!(range, 0..0);
467    }
468
469    #[test]
470    fn test_estimate_point_range_stride_1() {
471        let entry = NodeTemporalEntry {
472            key: VoxelKey {
473                level: 0,
474                x: 0,
475                y: 0,
476                z: 0,
477            },
478            samples: vec![
479                GpsTime(1.0),
480                GpsTime(2.0),
481                GpsTime(3.0),
482                GpsTime(4.0),
483                GpsTime(5.0),
484            ],
485        };
486
487        // With stride 1, every point is sampled
488        let range = entry.estimate_point_range(GpsTime(2.0), GpsTime(4.0), 1, 5);
489        // i=1, j=3, start=1, end=min(3+0, 4)=3
490        assert_eq!(range, 1..4);
491    }
492}
copc_temporal/temporal_index.rs

copc_temporal/
temporal_index.rs
