lsph 0.1.9

Learned Spatial HashMap
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

use core::ops::{Deref, DerefMut};
use smallvec::SmallVec;

/// Bucket is the lower unit in the HashMap to store the points
#[derive(Debug, Clone)]
pub(crate) struct Bucket<V> {
    entry: SmallVec<[V; 6]>,
}

impl<V> Bucket<V> {
    /// Returns a default Bucket with value type.
    #[inline]
    pub fn new() -> Self {
        Self {
            entry: SmallVec::new(),
        }
    }

    /// Removes an element from the Bucket and returns it.
    /// The removed element is replaced by the last element of the Bucket.
    #[inline]
    pub fn swap_remove(&mut self, index: usize) -> V {
        self.entry.swap_remove(index)
    }
}

impl<V> Deref for Bucket<V> {
    type Target = SmallVec<[V; 6]>;
    fn deref(&self) -> &Self::Target {
        &self.entry
    }
}

impl<V> DerefMut for Bucket<V> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.entry
    }
}

/// Table containing a Vec of Bucket to store the values
#[derive(Debug, Clone)]
pub(crate) struct Table<V> {
    buckets: Vec<Bucket<V>>,
}

impl<V> Table<V> {
    /// Returns a default Table with empty Vec.
    #[inline]
    pub fn new() -> Self {
        Self {
            buckets: Vec::new(),
        }
    }

    /// Returns a default Table with Vec that with the given capacity.
    ///
    /// # Arguments
    /// * `capacity` - A capacity size for the Table
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            buckets: Vec::with_capacity(capacity),
        }
    }

    /// Returns the capacity of the Table.
    #[inline]
    pub fn capacity(&self) -> usize {
        self.buckets.capacity()
    }

    /// Returns the Bucket with given hash value.
    ///
    /// # Arguments
    /// * `hash` - A hash value for indexing the bucket in the table
    #[inline]
    pub fn bucket(&self, hash: u64) -> usize {
        hash as usize % self.buckets.len()
    }
}
impl<V> Table<V>
where
    V: PartialEq,
{
    /// Remove entry with given hash value and entry.
    ///
    /// # Arguments
    /// * `hash` - A hash value for indexing the bucket in the table
    /// * `entry` - Entry to remove
    #[inline]
    pub fn remove_entry(&mut self, hash: u64, entry: V) -> Option<V> {
        let index = self.bucket(hash);
        let bucket = &mut self.buckets[index];
        let i = bucket.iter().position(|ek| ek == &entry)?;
        Some(bucket.swap_remove(i))
    }
}

impl<V> Deref for Table<V> {
    type Target = Vec<Bucket<V>>;
    fn deref(&self) -> &Self::Target {
        &self.buckets
    }
}

impl<V> DerefMut for Table<V> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.buckets
    }
}