geo-index 0.3.4

Fast, immutable, ABI-stable spatial indexes.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

//! Data structures to hold insertion and internal tree indices that may be either `u16` or `u32`
//! to save space.

use bytemuck::{cast_slice, cast_slice_mut};

/// A mutable slice of indices that may be either `u16` or `u32`.
#[derive(Debug)]
pub enum MutableIndices<'a> {
    /// Indices stored as a u16 byte slice
    U16(&'a mut [u16]),
    /// Indices stored as a u32 byte slice
    U32(&'a mut [u32]),
}

impl<'a> MutableIndices<'a> {
    pub(crate) fn new(slice: &'a mut [u8], num_nodes: usize) -> Self {
        if num_nodes < 16384 {
            Self::U16(cast_slice_mut(slice))
        } else {
            Self::U32(cast_slice_mut(slice))
        }
    }
}

impl MutableIndices<'_> {
    #[inline]
    #[allow(dead_code)]
    pub(crate) fn bytes_per_element(&self) -> usize {
        match self {
            Self::U16(_) => 2,
            Self::U32(_) => 4,
        }
    }

    #[inline]
    pub(crate) fn swap(&mut self, a: usize, b: usize) {
        match self {
            Self::U16(arr) => arr.swap(a, b),
            Self::U32(arr) => arr.swap(a, b),
        }
    }

    #[inline]
    #[allow(dead_code)]
    pub(crate) fn get(&self, index: usize) -> usize {
        match self {
            Self::U16(arr) => arr[index] as usize,
            Self::U32(arr) => arr[index] as usize,
        }
    }

    #[inline]
    pub(crate) fn set(&mut self, index: usize, value: usize) {
        match self {
            Self::U16(arr) => arr[index] = value.try_into().unwrap(),
            Self::U32(arr) => arr[index] = value.try_into().unwrap(),
        }
    }

    #[allow(dead_code)]
    pub(crate) fn split_at_mut(&mut self, mid: usize) -> (MutableIndices<'_>, MutableIndices<'_>) {
        match self {
            Self::U16(arr) => {
                let (left, right) = arr.split_at_mut(mid);
                (MutableIndices::U16(left), MutableIndices::U16(right))
            }
            Self::U32(arr) => {
                let (left, right) = arr.split_at_mut(mid);
                (MutableIndices::U32(left), MutableIndices::U32(right))
            }
        }
    }

    #[allow(dead_code)]
    pub(crate) fn chunks_mut(&mut self, chunk_size: usize) -> Vec<MutableIndices<'_>> {
        match self {
            Self::U16(arr) => arr
                .chunks_mut(chunk_size)
                .map(MutableIndices::U16)
                .collect(),
            Self::U32(arr) => arr
                .chunks_mut(chunk_size)
                .map(MutableIndices::U32)
                .collect(),
        }
    }
}

/// A slice of indices that may be either `u16` or `u32`.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Indices<'a> {
    /// Indices stored as a u16 byte slice
    U16(&'a [u16]),
    /// Indices stored as a u32 byte slice
    U32(&'a [u32]),
}

impl<'a> Indices<'a> {
    pub(crate) fn new(slice: &'a [u8], num_nodes: usize) -> Self {
        if num_nodes < 16384 {
            Self::U16(cast_slice(slice))
        } else {
            Self::U32(cast_slice(slice))
        }
    }
}

impl Indices<'_> {
    /// The number of indices in this byte slice
    pub fn len(&self) -> usize {
        match self {
            Self::U16(arr) => arr.len(),
            Self::U32(arr) => arr.len(),
        }
    }

    /// Whether this slice is empty
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// A helper to access a single index from this slice.
    ///
    /// Values are casted from u16 or u32 to usize.
    #[inline]
    pub fn get(&self, index: usize) -> usize {
        match self {
            Self::U16(arr) => arr[index] as usize,
            Self::U32(arr) => arr[index] as usize,
        }
    }
}