ovtile/open/
column_cache.rs

1use crate::{
2    delta_decode_array, delta_encode_array, unweave_and_delta_decode_3d_array,
3    unweave_and_delta_decode_array, weave_and_delta_encode_3d_array, weave_and_delta_encode_array,
4    CustomOrdWrapper, Point, Point3D, VectorPoints, VectorPoints3D, BBOX,
5};
6
7use pbf::{ProtoRead, ProtoWrite, Protobuf};
8
9use alloc::collections::BTreeMap;
10use alloc::string::String;
11use alloc::vec::Vec;
12use core::cell::RefCell;
13
14/// Column Types take up 3 bits.
15/// ColumnNames define various common data structures to be stored in a column fashion
16#[derive(Debug, Default, Clone, PartialEq, PartialOrd, Eq, Ord)]
17pub enum OColumnName {
18    /// stores string values
19    #[default]
20    String = 0,
21    /// Note: IDs are stored in unsigned
22    /// Number types are sorted prior to storing
23    Unsigned = 1,
24    /// Number types are sorted prior to storing
25    Signed = 2,
26    /// Floating precision helps ensure only 32 bit cost
27    /// Number types are sorted prior to storing
28    Float = 3,
29    /// worst case, no compression
30    /// Number types are sorted prior to storing
31    Double = 4,
32    /// points is an array of { x: number, y: number }
33    /// points also stores lines.
34    /// if a line is stored, note that it has an acompanying offset and potentially mValues
35    /// Polygons are stored as a collection of lines.
36    /// The points feature type that has more than one will be stored here as well.
37    Points = 5,
38    /// points3D is an array of { x: number, y: number, z: number }
39    /// points3D also stores lines.
40    /// if a line is stored, note that it has an acompanying offset and potentially mValues
41    /// Polygons are stored as a collection of lines.
42    /// The points 3D feature type that has more than one will be stored here as well.
43    Points3D = 6,
44    /// store M-Value, Shape, and Value encodings
45    /// store geometry shapes.
46    /// store geometry indices.
47    Indices = 7,
48    /// Shapes describe how to rebuild objects
49    Shapes = 8,
50    /// BBox - specially compressed to reduce byte cost. each value is only 3 bytes worst case
51    /// BBox3D - specially compressed to reduce byte cost. each value is only 3 bytes worst case.
52    /// The z values are stored as floats and cost 4 bytes.
53    BBox = 9,
54}
55impl From<u8> for OColumnName {
56    fn from(value: u8) -> Self {
57        match value {
58            0 => OColumnName::String,
59            1 => OColumnName::Unsigned,
60            2 => OColumnName::Signed,
61            3 => OColumnName::Float,
62            4 => OColumnName::Double,
63            5 => OColumnName::Points,
64            6 => OColumnName::Points3D,
65            7 => OColumnName::Indices,
66            8 => OColumnName::Shapes,
67            9 => OColumnName::BBox,
68            _ => OColumnName::String,
69        }
70    }
71}
72impl From<OColumnName> for u64 {
73    fn from(col: OColumnName) -> Self {
74        col as u64
75    }
76}
77
78//? READING
79
80/// note: base1 type allows you to decode as needed for each grouping of data.
81/// for instance OColumnString is an array of strings, but you may only need a few strings on use.
82/// Store either data itself or a reference to the position in the protobuf to deserialize
83#[derive(Debug)]
84pub enum ColumnContainer<T> {
85    /// reference to a position in the protobuf
86    Pos(usize),
87    /// data itself
88    Data(T),
89}
90
91/// Column Cache Reader
92/// Stores all data in a column format.
93/// Upon construction, all columns are decoded from the protobuf.
94/// This allows for quick and easy access to data in a column format.
95#[derive(Debug, Default)]
96pub struct ColumnCacheReader {
97    /// strings are stored in a column of strings
98    string: Vec<String>,
99    /// unsigned whole numbers are stored in unsigned
100    unsigned: Vec<u64>,
101    /// negative numbers are stored in signed
102    signed: Vec<i64>,
103    /// non-whole 32-bit numbers are stored in float
104    float: Vec<f32>,
105    /// non-whole numbers greater than 32-bit are stored in double
106    double: Vec<f64>,
107    /// for geometry types each column is individually weaved and delta encoded
108    points: Vec<VectorPoints>,
109    /// for geometry types each column is individually weaved and delta encoded
110    points_3d: Vec<VectorPoints3D>,
111    /// store M-Value indices>, geometry indices>, and geometry shapes
112    indices: Vec<Vec<u32>>,
113    /// shapes and possibly value indices are stored in a number[] to be decoded by readShape
114    shapes: Vec<Vec<usize>>,
115    /// Stores both BBox and BBox3D in a single column
116    bbox: Vec<BBOX>,
117}
118impl ColumnCacheReader {
119    /// create an instance
120    pub fn new() -> Self {
121        ColumnCacheReader { ..Default::default() }
122    }
123
124    /// get a string
125    pub fn get_string(&mut self, index: usize) -> String {
126        self.string[index].clone()
127    }
128
129    /// get an unsigned integer
130    pub fn get_unsigned(&self, index: usize) -> u64 {
131        self.unsigned[index]
132    }
133
134    /// get a signed integer
135    pub fn get_signed(&self, index: usize) -> i64 {
136        self.signed[index]
137    }
138
139    /// get a float
140    pub fn get_float(&self, index: usize) -> f32 {
141        self.float[index]
142    }
143
144    /// get a double
145    pub fn get_double(&self, index: usize) -> f64 {
146        self.double[index]
147    }
148
149    /// get a vector of points used by all geometry types
150    pub fn get_points(&mut self, index: usize) -> VectorPoints {
151        self.points[index].clone()
152    }
153
154    /// get a vector of 3D points used by all geometry types
155    pub fn get_points_3d(&mut self, index: usize) -> VectorPoints3D {
156        self.points_3d[index].clone()
157    }
158
159    /// get a vector of indices used by all geometry types
160    pub fn get_indices(&mut self, index: usize) -> Vec<u32> {
161        self.indices[index].clone()
162    }
163
164    /// get a vector of encoded data that helps decode shapes
165    pub fn get_shapes(&mut self, index: usize) -> Vec<usize> {
166        self.shapes[index].clone()
167    }
168
169    /// get a BBox
170    pub fn get_bbox(&mut self, index: usize) -> BBOX {
171        self.bbox[index]
172    }
173}
174impl ProtoRead for ColumnCacheReader {
175    fn read(&mut self, tag: u64, pb: &mut Protobuf) {
176        match tag {
177            0 => self.string.push(pb.read_string()),
178            1 => self.unsigned.push(pb.read_varint::<u64>()),
179            2 => self.signed.push(pb.read_s_varint::<i64>()),
180            3 => self.float.push(pb.read_varint::<f32>()),
181            4 => self.double.push(pb.read_varint::<f64>()),
182            5 => self.points.push(unweave_and_delta_decode_array(&pb.read_packed::<u64>())),
183            6 => self.points_3d.push(unweave_and_delta_decode_3d_array(&pb.read_packed::<u64>())),
184            7 => self.indices.push(delta_decode_array(&pb.read_packed::<u32>())),
185            8 => self.shapes.push(pb.read_packed::<usize>()),
186            9 => self.bbox.push((&pb.read_packed::<u8>()[..]).into()),
187            #[tarpaulin::skip]
188            _ => panic!("Unknown column type"),
189        }
190    }
191}
192
193//? WRITING
194
195/// Numbers track their own index for sorting purposes
196#[derive(Debug, Default, Clone, PartialEq, PartialOrd, Eq, Ord)]
197pub struct OColumnBaseChunk {
198    /// The index in the column. Will be updated during the writing phase when converted
199    /// from a map to an array
200    pub index: usize,
201    /// track how many times this chunk is reused
202    pub count: usize,
203}
204/// A value is a collection of lookup devices. A number is decoded by the appropriate function,
205/// but the object is a reference to one of the number columns.
206/// Number types are eventually sorted, so we track the column and index with the data.
207#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord)]
208pub enum ColumnValue {
209    /// raw number index pointing to a location in the cache column
210    Number(usize),
211    /// a reference to a column
212    Column(RefCell<OColumnBaseChunk>),
213}
214impl From<usize> for ColumnValue {
215    fn from(index: usize) -> Self {
216        ColumnValue::Number(index)
217    }
218}
219impl From<RefCell<OColumnBaseChunk>> for ColumnValue {
220    fn from(chunk: RefCell<OColumnBaseChunk>) -> Self {
221        ColumnValue::Column(chunk)
222    }
223}
224/// A building block for all column types.
225pub type OColumnBaseWrite<K> = BTreeMap<K, RefCell<OColumnBaseChunk>>;
226
227/// A building block for all number column types.
228pub type OColumnBaseFloatWrite<K> = BTreeMap<CustomOrdWrapper<K>, RefCell<OColumnBaseChunk>>;
229
230/// The cache where all data is stored in a column format.
231/// Each column type has its own array of data.
232/// Number types maintain their own index for sorting purposes.
233#[derive(Debug, Default)]
234pub struct ColumnCacheWriter {
235    /// strings are grouped by their bytes.
236    string: OColumnBaseWrite<String>,
237    /// Unsigned integers are sorted prior to storing
238    unsigned: OColumnBaseWrite<u64>,
239    /// Signed integers are sorted prior to storing
240    signed: OColumnBaseWrite<i64>,
241    /// 32-bit partial values are sorted prior to storing
242    float: OColumnBaseFloatWrite<f32>,
243    /// 64-bit partial values are sorted prior to storing
244    double: OColumnBaseFloatWrite<f64>,
245    /// for geometry types each column is individually weaved and delta encoded
246    points: OColumnBaseWrite<Vec<Point>>,
247    /// for geometry types each column is individually weaved and delta encoded
248    points_3d: OColumnBaseWrite<Vec<Point3D>>,
249    /// Indices track geometry indices, geometry shapes, or other indexing data
250    indices: OColumnBaseWrite<Vec<u32>>,
251    /// Contains number arrays of how to rebuild objects
252    shapes: OColumnBaseWrite<Vec<ColumnValue>>,
253    /// Features should be sorted by id prior to building a column
254    bbox: OColumnBaseWrite<BBOX>,
255}
256impl ColumnCacheWriter {
257    /// add string to cache
258    pub fn add_string(&mut self, value: String) -> usize {
259        add(&mut self.string, value)
260    }
261
262    /// add u64 to cache
263    pub fn add_u64(&mut self, value: u64) -> RefCell<OColumnBaseChunk> {
264        add_number(&mut self.unsigned, value)
265    }
266
267    /// add i64 to cache
268    pub fn add_i64(&mut self, value: i64) -> RefCell<OColumnBaseChunk> {
269        add_number(&mut self.signed, value)
270    }
271
272    /// add f32 to cache
273    pub fn add_f32(&mut self, value: f32) -> RefCell<OColumnBaseChunk> {
274        add_number(&mut self.float, CustomOrdWrapper(value))
275    }
276
277    /// add f64 to cache
278    pub fn add_f64(&mut self, value: f64) -> RefCell<OColumnBaseChunk> {
279        add_number(&mut self.double, CustomOrdWrapper(value))
280    }
281
282    /// add points to cache
283    pub fn add_points(&mut self, value: Vec<Point>) -> usize {
284        add(&mut self.points, value)
285    }
286
287    /// add points_3d to cache
288    pub fn add_points_3d(&mut self, value: Vec<Point3D>) -> usize {
289        add(&mut self.points_3d, value)
290    }
291
292    /// add indices to cache
293    pub fn add_indices(&mut self, value: Vec<u32>) -> usize {
294        add(&mut self.indices, value)
295    }
296
297    /// add shapes to cache
298    pub fn add_shapes(&mut self, value: Vec<ColumnValue>) -> usize {
299        add(&mut self.shapes, value)
300    }
301
302    /// add bbox to cache
303    pub fn add_bbox(&mut self, value: BBOX) -> usize {
304        add(&mut self.bbox, value)
305    }
306}
307impl ProtoWrite for ColumnCacheWriter {
308    fn write(&self, pbf: &mut Protobuf) {
309        // setup
310        let mut strings: Vec<(&String, &RefCell<OColumnBaseChunk>)> = self.string.iter().collect();
311        let mut unsigned: Vec<(&u64, &RefCell<OColumnBaseChunk>)> = self.unsigned.iter().collect();
312        let mut signed: Vec<(&i64, &RefCell<OColumnBaseChunk>)> = self.signed.iter().collect();
313        let mut float: Vec<(&CustomOrdWrapper<f32>, &RefCell<OColumnBaseChunk>)> =
314            self.float.iter().collect();
315        let mut double: Vec<(&CustomOrdWrapper<f64>, &RefCell<OColumnBaseChunk>)> =
316            self.double.iter().collect();
317        let mut points: Vec<(&Vec<Point>, &RefCell<OColumnBaseChunk>)> =
318            self.points.iter().collect();
319        let mut points_3d: Vec<(&Vec<Point3D>, &RefCell<OColumnBaseChunk>)> =
320            self.points_3d.iter().collect();
321        let mut indices: Vec<(&Vec<u32>, &RefCell<OColumnBaseChunk>)> =
322            self.indices.iter().collect();
323        let mut shapes: Vec<(&Vec<ColumnValue>, &RefCell<OColumnBaseChunk>)> =
324            self.shapes.iter().collect();
325        let mut bbox: Vec<(&BBOX, &RefCell<OColumnBaseChunk>)> = self.bbox.iter().collect();
326
327        // sort them
328        // TODO: bring this back
329        // sort_column(&mut unsigned);
330        // sort_column(&mut signed);
331        // sort_column(&mut float);
332        // sort_column(&mut double);
333        strings.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
334        unsigned.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
335        signed.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
336        float.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
337        double.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
338        points.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
339        points_3d.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
340        indices.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
341        shapes.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
342        bbox.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
343
344        // store
345        // strings
346        for string in strings {
347            pbf.write_string_field(OColumnName::String.into(), string.0);
348        }
349        // u64
350        for u in unsigned {
351            pbf.write_varint_field(OColumnName::Unsigned.into(), *u.0);
352        }
353        // i64
354        for s in signed {
355            pbf.write_s_varint_field(OColumnName::Signed.into(), *s.0);
356        }
357        // f32
358        for f in float {
359            pbf.write_varint_field(OColumnName::Float.into(), f.0 .0);
360        }
361        // f64
362        for d in double {
363            pbf.write_varint_field(OColumnName::Double.into(), d.0 .0);
364        }
365        // points
366        for p in points {
367            pbf.write_packed_varint(OColumnName::Points.into(), &weave_and_delta_encode_array(p.0));
368        }
369        // points 3D
370        for p_3d in points_3d {
371            pbf.write_packed_varint(
372                OColumnName::Points3D.into(),
373                &weave_and_delta_encode_3d_array(p_3d.0),
374            );
375        }
376        // indices
377        for i in indices {
378            pbf.write_packed_varint(OColumnName::Indices.into(), &delta_encode_array(i.0));
379        }
380        // shapes
381        for s in shapes {
382            let packed: Vec<usize> =
383                s.0.iter()
384                    .map(|v| match v {
385                        ColumnValue::Number(n) => *n,
386                        ColumnValue::Column(c) => c.borrow().index,
387                    })
388                    .collect();
389            pbf.write_packed_varint(OColumnName::Shapes.into(), &packed);
390        }
391        // bbox
392        for bbox in bbox {
393            pbf.write_packed_varint(OColumnName::BBox.into(), &bbox.0.quantize());
394        }
395    }
396}
397
398/// Add value to column and return index
399pub fn add<T>(col: &mut OColumnBaseWrite<T>, value: T) -> usize
400where
401    T: Ord,
402{
403    if let Some(col) = col.get_mut(&value) {
404        let mut chunk = col.borrow_mut();
405        chunk.count += 1;
406        chunk.index
407    } else {
408        let index = col.len();
409        col.insert(value, RefCell::new(OColumnBaseChunk { index, count: 1 }));
410        index
411    }
412}
413
414/// Add a **number** value to column and return index
415pub fn add_number<T>(col: &mut OColumnBaseWrite<T>, value: T) -> RefCell<OColumnBaseChunk>
416where
417    T: Ord,
418{
419    if let Some(chunk) = col.get_mut(&value) {
420        {
421            let mut chunk_mut = chunk.borrow_mut();
422            chunk_mut.count += 1;
423        }
424        chunk.clone()
425    } else {
426        let index = col.len();
427        let new_chunk = RefCell::new(OColumnBaseChunk { index, count: 1 });
428        col.insert(value, new_chunk.clone());
429        new_chunk
430    }
431}
432
433// /// Sort number types and value types by index then update the index of each row for better
434// /// compression down the line.
435// pub fn sort_column<T: CustomOrd + core::fmt::Debug>(
436//     input: &mut [(&T, &RefCell<OColumnBaseChunk>)],
437// ) {
438//     // first sort
439//     input.sort_by(|a, b| {
440//         // First sort by count in descending order
441//         match b.1.borrow().count.cmp(&a.1.borrow().count) {
442//             Ordering::Equal => a.0.custom_cmp(b.0), // Then sort by data if counts are equal
443//             other => other,
444//         }
445//     });
446//     // than update indexes
447//     input
448//         .iter_mut()
449//         .enumerate()
450//         .for_each(|(i, v)| v.1.borrow_mut().index = i);
451// }
ovtile/open/column_cache.rs

ovtile/open/
column_cache.rs
