Open-S2 / open-vector-tile / #17

Committed 12 Aug 2024 09:02PM UTC coverage: 27.612% (+4.4%) from 23.175%

Build # #17

Build Type

push

Committed by Mr Martian

Commit Message

tests moving along

Run Details

1915 of 2437 new or added lines in 17 files covered. (78.58%)

14 existing lines in 5 files now uncovered.

11082 of 40134 relevant lines covered (27.61%)

105.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

71.06

/rust/open/column_cache.rs

use crate::util::{
    delta_decode_array, delta_encode_array, unweave_and_delta_decode_3d_array,
    unweave_and_delta_decode_array, weave_and_delta_encode_3d_array, weave_and_delta_encode_array,
};
use crate::util::{CustomOrd, CustomOrdWrapper};
use crate::{Point, Point3D, VectorPoints, VectorPoints3D, BBOX};

use pbf::{ProtoRead, ProtoWrite, Protobuf};

use alloc::collections::BTreeMap;
use alloc::rc::Rc;
use alloc::string::String;
use alloc::vec::Vec;
use core::cell::RefCell;
use core::cmp::Ordering;

/// Column Types take up 3 bits.
/// ColumnNames define various common data structures to be stored in a column fashion
#[derive(Debug, Default, Clone, PartialEq, PartialOrd, Eq, Ord)]
pub enum OColumnName {
    /// stores string values
    #[default]
    String = 0,
    /// Note: IDs are stored in unsigned
    /// Number types are sorted prior to storing
    Unsigned = 1,
    /// Number types are sorted prior to storing
    Signed = 2,
    /// Floating precision helps ensure only 32 bit cost
    /// Number types are sorted prior to storing
    Float = 3,
    /// worst case, no compression
    /// Number types are sorted prior to storing
    Double = 4,
    /// points is an array of { x: number, y: number }
    /// points also stores lines.
    /// if a line is stored, note that it has an acompanying offset and potentially mValues
    /// Polygons are stored as a collection of lines.
    /// The points feature type that has more than one will be stored here as well.
    Points = 5,
    /// points3D is an array of { x: number, y: number, z: number }
    /// points3D also stores lines.
    /// if a line is stored, note that it has an acompanying offset and potentially mValues
    /// Polygons are stored as a collection of lines.
    /// The points 3D feature type that has more than one will be stored here as well.
    Points3D = 6,
    /// store M-Value, Shape, and Value encodings
    /// store geometry shapes.
    /// store geometry indices.
    Indices = 7,
    /// Shapes describe how to rebuild objects
    Shapes = 8,
    /// BBox - specially compressed to reduce byte cost. each value is only 3 bytes worst case
    /// BBox3D - specially compressed to reduce byte cost. each value is only 3 bytes worst case.
    /// The z values are stored as floats and cost 4 bytes.
    BBox = 9,
}
impl From<u8> for OColumnName {
    fn from(value: u8) -> Self {
        match value {
            0 => OColumnName::String,
            1 => OColumnName::Unsigned,
            2 => OColumnName::Signed,
            3 => OColumnName::Float,
            4 => OColumnName::Double,
            5 => OColumnName::Points,
            6 => OColumnName::Points3D,
            7 => OColumnName::Indices,
            8 => OColumnName::Shapes,
            9 => OColumnName::BBox,
            _ => OColumnName::String,
        }
    }
}
impl From<OColumnName> for u64 {
    fn from(col: OColumnName) -> Self {
        col as u64
    }
}

//? READING

/// note: base1 type allows you to decode as needed for each grouping of data.
/// for instance OColumnString is an array of strings, but you may only need a few strings on use.
/// Store either data itself or a reference to the position in the protobuf to deserialize
#[derive(Debug)]
pub enum ColumnContainer<T> {
    /// reference to a position in the protobuf
    Pos(usize),
    /// data itself
    Data(T),
}

/// Column Cache Reader
/// Stores all data in a column format.
/// Upon construction, all columns are decoded from the protobuf.
/// This allows for quick and easy access to data in a column format.
#[derive(Debug, Default)]
pub struct ColumnCacheReader {
    /// strings are stored in a column of strings
    string: Vec<ColumnContainer<String>>,
    /// unsigned whole numbers are stored in unsigned
    unsigned: Vec<u64>,
    /// negative numbers are stored in signed
    signed: Vec<i64>,
    /// non-whole 32-bit numbers are stored in float
    float: Vec<f32>,
    /// non-whole numbers greater than 32-bit are stored in double
    double: Vec<f64>,
    /// for geometry types each column is individually weaved and delta encoded
    points: Vec<ColumnContainer<VectorPoints>>,
    /// for geometry types each column is individually weaved and delta encoded
    points_3d: Vec<ColumnContainer<VectorPoints3D>>,
    /// store M-Value indices>, geometry indices>, and geometry shapes
    indices: Vec<ColumnContainer<Vec<u32>>>,
    /// shapes and possibly value indices are stored in a number[] to be decoded by readShape
    shapes: Vec<ColumnContainer<Vec<usize>>>,
    /// Stores both BBox and BBox3D in a single column
    bbox: Vec<ColumnContainer<BBOX>>,

    /// keep tabs on the pbf
    pbf: Rc<RefCell<Protobuf>>,
}
impl ColumnCacheReader {
    /// create an instance
    pub fn new(pbf: Rc<RefCell<Protobuf>>, end: usize) -> Self {
        let pbf_clone = pbf.clone();
        let mut ccr = ColumnCacheReader {
            pbf,
            ..Default::default()
        };

        let mut tmp_pbf = pbf_clone.borrow_mut();
        tmp_pbf.read_fields(&mut ccr, Some(end));

        ccr
    }

    /// get a string
    pub fn get_string(&mut self, index: usize) -> String {
        get_value(index, self.pbf.clone(), &mut self.string, |pbf| {
            pbf.read_string()
        })
    }

    /// get an unsigned integer
    pub fn get_unsigned(&self, index: usize) -> u64 {
        self.unsigned[index]
    }

    /// get a signed integer
    pub fn get_signed(&self, index: usize) -> i64 {
        self.signed[index]
    }

    /// get a float
    pub fn get_float(&self, index: usize) -> f32 {
        self.float[index]
    }

    /// get a double
    pub fn get_double(&self, index: usize) -> f64 {
        self.double[index]
    }

    /// get a vector of points used by all geometry types
    pub fn get_points(&mut self, index: usize) -> VectorPoints {
        get_value(index, self.pbf.clone(), &mut self.points, |pbf| {
            unweave_and_delta_decode_array(&pbf.read_packed::<u64>())
        })
    }

    /// get a vector of 3D points used by all geometry types
    pub fn get_points_3d(&mut self, index: usize) -> VectorPoints3D {
        get_value(index, self.pbf.clone(), &mut self.points_3d, |pbf| {
            unweave_and_delta_decode_3d_array(&pbf.read_packed::<u64>())
        })
    }

    /// get a vector of indices used by all geometry types
    pub fn get_indices(&mut self, index: usize) -> Vec<u32> {
        get_value(index, self.pbf.clone(), &mut self.indices, |pbf| {
            delta_decode_array(&pbf.read_packed::<u32>())
        })
    }

    /// get a vector of encoded data that helps decode shapes
    pub fn get_shapes(&mut self, index: usize) -> Vec<usize> {
        get_value(index, self.pbf.clone(), &mut self.shapes, |pbf| {
            pbf.read_packed::<usize>()
        })
    }

    /// get a BBox
    pub fn get_bbox(&mut self, index: usize) -> BBOX {
        get_value(index, self.pbf.clone(), &mut self.bbox, |pbf| {
            let buf = pbf.read_packed::<u8>();
            (&buf[..]).into()
        })
    }
}
impl ProtoRead for ColumnCacheReader {
    fn read(&mut self, tag: u64, pb: &mut Protobuf) {
        let pos = pb.get_pos();
        match tag {
            0 => self.string.push(ColumnContainer::Pos(pos)),
            1 => self.unsigned.push(pb.read_varint::<u64>()),
            2 => self.signed.push(pb.read_s_varint::<i64>()),
            3 => self.float.push(pb.read_varint::<f32>()),
            4 => self.double.push(pb.read_varint::<f64>()),
            5 => self.points.push(ColumnContainer::Pos(pos)),
            6 => self.points_3d.push(ColumnContainer::Pos(pos)),
            7 => self.indices.push(ColumnContainer::Pos(pos)),
            8 => self.shapes.push(ColumnContainer::Pos(pos)),
            9 => self.bbox.push(ColumnContainer::Pos(pos)),
            _ => panic!("Unknown column type"),
        }
    }
}

fn get_value<T, F>(
    index: usize,
    pbf: Rc<RefCell<Protobuf>>,
    container: &mut [ColumnContainer<T>],
    read_func: F,
) -> T
where
    T: Clone,
    F: FnOnce(&mut Protobuf) -> T,
{
    match &container[index] {
        ColumnContainer::Pos(pos) => {
            let mut tmp_pbf = pbf.borrow_mut();
            tmp_pbf.set_pos(*pos);
            let data = read_func(&mut tmp_pbf);
            container[index] = ColumnContainer::Data(data.clone());
            data
        }
        ColumnContainer::Data(data) => data.clone(),
    }
}

//? WRITING

/// Numbers track their own index for sorting purposes
#[derive(Debug, Default, Clone, PartialEq, PartialOrd, Eq, Ord)]
pub struct OColumnBaseChunk {
    /// The index in the column. Will be updated during the writing phase when converted
    /// from a map to an array
    pub index: usize,
    /// track how many times this chunk is reused
    pub count: usize,
}
/// A value is a collection of lookup devices. A number is decoded by the appropriate function,
/// but the object is a reference to one of the number columns.
/// Number types are eventually sorted, so we track the column and index with the data.
#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord)]
pub enum ColumnValue {
    /// raw number index pointing to a location in the cache column
    Number(usize),
    /// a reference to a column
    Column(RefCell<OColumnBaseChunk>),
}
impl From<usize> for ColumnValue {
    fn from(index: usize) -> Self {
        ColumnValue::Number(index)
    }
}
impl From<RefCell<OColumnBaseChunk>> for ColumnValue {
    fn from(chunk: RefCell<OColumnBaseChunk>) -> Self {
        ColumnValue::Column(chunk)
    }
}
/// A building block for all column types.
pub type OColumnBaseWrite<K> = BTreeMap<K, RefCell<OColumnBaseChunk>>;

/// A building block for all number column types.
pub type OColumnBaseFloatWrite<K> = BTreeMap<CustomOrdWrapper<K>, RefCell<OColumnBaseChunk>>;

/// The cache where all data is stored in a column format.
/// Each column type has its own array of data.
/// Number types maintain their own index for sorting purposes.
#[derive(Debug, Default)]
pub struct ColumnCacheWriter {
    /// strings are grouped by their bytes.
    string: OColumnBaseWrite<String>,
    /// Unsigned integers are sorted prior to storing
    unsigned: OColumnBaseWrite<u64>,
    /// Signed integers are sorted prior to storing
    signed: OColumnBaseWrite<i64>,
    /// 32-bit partial values are sorted prior to storing
    float: OColumnBaseFloatWrite<f32>,
    /// 64-bit partial values are sorted prior to storing
    double: OColumnBaseFloatWrite<f64>,
    /// for geometry types each column is individually weaved and delta encoded
    points: OColumnBaseWrite<Vec<Point>>,
    /// for geometry types each column is individually weaved and delta encoded
    points_3d: OColumnBaseWrite<Vec<Point3D>>,
    /// Indices track geometry indices, geometry shapes, or other indexing data
    indices: OColumnBaseWrite<Vec<u32>>,
    /// Contains number arrays of how to rebuild objects
    shapes: OColumnBaseWrite<Vec<ColumnValue>>,
    /// Features should be sorted by id prior to building a column
    bbox: OColumnBaseWrite<BBOX>,
}
impl ColumnCacheWriter {
    /// add string to cache
    pub fn add_string(&mut self, value: String) -> usize {
        add(&mut self.string, value)
    }

    /// add u64 to cache
    pub fn add_u64(&mut self, value: u64) -> RefCell<OColumnBaseChunk> {
        add_number(&mut self.unsigned, value)
    }

    /// add i64 to cache
    pub fn add_i64(&mut self, value: i64) -> RefCell<OColumnBaseChunk> {
        add_number(&mut self.signed, value)
    }

    /// add f32 to cache
    pub fn add_f32(&mut self, value: f32) -> RefCell<OColumnBaseChunk> {
        add_number(&mut self.float, CustomOrdWrapper(value))
    }

    /// add f64 to cache
    pub fn add_f64(&mut self, value: f64) -> RefCell<OColumnBaseChunk> {
        add_number(&mut self.double, CustomOrdWrapper(value))
    }

    /// add points to cache
    pub fn add_points(&mut self, value: Vec<Point>) -> usize {
        add(&mut self.points, value)
    }

    /// add points_3d to cache
    pub fn add_points_3d(&mut self, value: Vec<Point3D>) -> usize {
        add(&mut self.points_3d, value)
    }

    /// add indices to cache
    pub fn add_indices(&mut self, value: Vec<u32>) -> usize {
        add(&mut self.indices, value)
    }

    /// add shapes to cache
    pub fn add_shapes(&mut self, value: Vec<ColumnValue>) -> usize {
        add(&mut self.shapes, value)
    }

    /// add bbox to cache
    pub fn add_bbox(&mut self, value: BBOX) -> usize {
        add(&mut self.bbox, value)
    }
}
impl ProtoWrite for ColumnCacheWriter {
    fn write(&self, pbf: &mut Protobuf) {
        // setup
        let mut strings: Vec<(&String, &RefCell<OColumnBaseChunk>)> = self.string.iter().collect();
        let mut unsigned: Vec<(&u64, &RefCell<OColumnBaseChunk>)> = self.unsigned.iter().collect();
        let mut signed: Vec<(&i64, &RefCell<OColumnBaseChunk>)> = self.signed.iter().collect();
        let mut float: Vec<(&CustomOrdWrapper<f32>, &RefCell<OColumnBaseChunk>)> =
            self.float.iter().collect();
        let mut double: Vec<(&CustomOrdWrapper<f64>, &RefCell<OColumnBaseChunk>)> =
            self.double.iter().collect();
        let mut points: Vec<(&Vec<Point>, &RefCell<OColumnBaseChunk>)> =
            self.points.iter().collect();
        let mut points_3d: Vec<(&Vec<Point3D>, &RefCell<OColumnBaseChunk>)> =
            self.points_3d.iter().collect();
        let mut indices: Vec<(&Vec<u32>, &RefCell<OColumnBaseChunk>)> =
            self.indices.iter().collect();
        let mut shapes: Vec<(&Vec<ColumnValue>, &RefCell<OColumnBaseChunk>)> =
            self.shapes.iter().collect();
        let mut bbox: Vec<(&BBOX, &RefCell<OColumnBaseChunk>)> = self.bbox.iter().collect();

        // sort them
        // TODO: bring this back
        // sort_column(&mut unsigned);
        // sort_column(&mut signed);
        // sort_column(&mut float);
        // sort_column(&mut double);
        strings.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        unsigned.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        signed.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        float.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        double.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        points.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        points_3d.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        indices.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        shapes.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));
        bbox.sort_by(|a, b| a.1.borrow().index.cmp(&b.1.borrow().index));

        // store
        // strings
        for string in strings {
            pbf.write_string_field(OColumnName::String.into(), string.0);
        }
        // u64
        for u in unsigned {
            pbf.write_varint_field(OColumnName::Unsigned.into(), *u.0);
        }
        // i64
        for s in signed {
            pbf.write_s_varint_field(OColumnName::Signed.into(), *s.0);
        }
        // f32
        for f in float {
            pbf.write_varint_field(OColumnName::Float.into(), f.0 .0);
        }
        // f64
        for d in double {
            pbf.write_varint_field(OColumnName::Double.into(), d.0 .0);
        }
        // points
        for p in points {
            pbf.write_packed_varint(
                OColumnName::Points.into(),
                &weave_and_delta_encode_array(p.0),
            );
        }
        // points 3D
        for p_3d in points_3d {
            pbf.write_packed_varint(
                OColumnName::Points3D.into(),
                &weave_and_delta_encode_3d_array(p_3d.0),
            );
        }
        // indices
        for i in indices {
            pbf.write_packed_varint(OColumnName::Indices.into(), &delta_encode_array(i.0));
        }
        // shapes
        for s in shapes {
            println!("SHAPE!!!: {:?}", s.0);
            println!();
            println!();
            let packed: Vec<usize> =
                s.0.iter()
                    .map(|v| match v {
                        ColumnValue::Number(n) => *n,
                        ColumnValue::Column(c) => c.borrow().index,
                    })
                    .collect();
            pbf.write_packed_varint(OColumnName::Shapes.into(), &packed);
        }
        // bbox
        for bbox in bbox {
            let quantized = bbox.0.quantize();
            pbf.write_packed_varint(OColumnName::BBox.into(), &quantized);
        }
    }
}

/// Add value to column and return index
pub fn add<T>(col: &mut OColumnBaseWrite<T>, value: T) -> usize
where
    T: Ord,
{
    if let Some(col) = col.get_mut(&value) {
        let mut chunk = col.borrow_mut();
        chunk.count += 1;
        chunk.index
    } else {
        let index = col.len();
        col.insert(value, RefCell::new(OColumnBaseChunk { index, count: 1 }));
        index
    }
}

/// Add a **number** value to column and return index
pub fn add_number<T>(col: &mut OColumnBaseWrite<T>, value: T) -> RefCell<OColumnBaseChunk>
where
    T: Ord,
{
    if let Some(chunk) = col.get_mut(&value) {
        {
            let mut chunk_mut = chunk.borrow_mut();
            chunk_mut.count += 1;
        }
        chunk.clone()
    } else {
        let index = col.len();
        let new_chunk = RefCell::new(OColumnBaseChunk { index, count: 1 });
        col.insert(value, new_chunk.clone());
        new_chunk
    }
}

/// Sort number types and value types by index then update the index of each row for better
/// compression down the line.
pub fn sort_column<T: CustomOrd + core::fmt::Debug>(
    input: &mut [(&T, &RefCell<OColumnBaseChunk>)],
) {
    // first sort
    println!("BEFORE SORT: {:?}", input);
    input.sort_by(|a, b| {
        // First sort by count in descending order
        match b.1.borrow().count.cmp(&a.1.borrow().count) {
            Ordering::Equal => a.0.custom_cmp(b.0), // Then sort by data if counts are equal
            other => other,
        }
    });
    println!("AFTER SORT: {:?}", input);
    // than update indexes
    input
        .iter_mut()
        .enumerate()
        .for_each(|(i, v)| v.1.borrow_mut().index = i);
    println!("AFTER INDEX: {:?}", input);
    println!();
    println!();
}

// SHAPE!!!: [Column(RefCell { value: OColumnBaseChunk { index: 0, count: 1 } }), Number(2), Number(0), Number(1), Column(RefCell { value: OColumnBase
// Chunk { index: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { ind▐
// ex: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 1, count: 1 } })]                                                          ▐

// SHAPE!!!: [Column(RefCell { value: OColumnBaseChunk { index: 0, count: 1 } }), Number(2), Number(0), Number(1), Column(RefCell { value: OColumnBase▐
// Chunk { index: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { ind▐
// ex: 0, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 1, count: 1 } })]                                                          ▐

//                                                                                                                                                     ▐
//                                                                                                                                                     ▐
// SHAPE!!!: [Column(RefCell { value: OColumnBaseChunk { index: 1, count: 1 } }), Number(3), Number(2), Number(3), Number(0), Column(RefCell { value: ▐
// OColumnBaseChunk { index: 1, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 2, count: 1 } }), Column(RefCell { value: OColumnBase▐
// Chunk { index: 1, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 2, count: 2 } })]

//                                                                                                                                                     ▐
//                                                                                                                                                     ▐
// SHAPE!!!: [Column(RefCell { value: OColumnBaseChunk { index: 1, count: 1 } }), Number(3), Number(2), Number(3), Number(0), Column(RefCell { value: ▐
// OColumnBaseChunk { index: 1, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 2, count: 1 } }), Column(RefCell { value: OColumnBase▐
// Chunk { index: 1, count: 1 } }), Column(RefCell { value: OColumnBaseChunk { index: 2, count: 2 } })]

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

Open-S2 / open-vector-tile / #17

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous