bp3d_util/
index_map.rs

1// Copyright (c) 2024, BlockProject 3D
2//
3// All rights reserved.
4//
5// Redistribution and use in source and binary forms, with or without modification,
6// are permitted provided that the following conditions are met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//     * Redistributions in binary form must reproduce the above copyright notice,
11//       this list of conditions and the following disclaimer in the documentation
12//       and/or other materials provided with the distribution.
13//     * Neither the name of BlockProject 3D nor the names of its contributors
14//       may be used to endorse or promote products derived from this software
15//       without specific prior written permission.
16//
17// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
21// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
25// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29//! A map with the key stored as part of the value.
30
31use std::borrow::Borrow;
32use std::collections::HashSet;
33use std::hash::{Hash, Hasher};
34use std::rc::Rc;
35use std::sync::Arc;
36
37/// The main index type to implement for each type to be stored in an IndexMap.
38pub trait Index {
39    /// The type of the key.
40    type Key: ?Sized + Hash + PartialEq + Eq;
41
42    /// The index function which returns a reference to the key stored in the object.
43    fn index(&self) -> &Self::Key;
44}
45
46impl<T: Index> Index for Rc<T> {
47    type Key = T::Key;
48
49    fn index(&self) -> &Self::Key {
50        (**self).index()
51    }
52}
53
54impl<T: Index> Index for Arc<T> {
55    type Key = T::Key;
56
57    fn index(&self) -> &Self::Key {
58        (**self).index()
59    }
60}
61
62#[derive(Clone, Debug)]
63struct Item<V>(V);
64
65impl<V: Index> Hash for Item<V> {
66    fn hash<H: Hasher>(&self, state: &mut H) {
67        self.0.index().hash(state);
68    }
69}
70
71impl<V: Index> PartialEq for Item<V> {
72    fn eq(&self, other: &Self) -> bool {
73        self.0.index().eq(other.0.index())
74    }
75}
76
77impl<V: Index> Eq for Item<V> {}
78
79impl<V: Index<Key = str>> Borrow<str> for Item<V> {
80    fn borrow(&self) -> &V::Key {
81        self.0.index()
82    }
83}
84
85impl<V: Index<Key = usize>> Borrow<usize> for Item<V> {
86    fn borrow(&self) -> &V::Key {
87        self.0.index()
88    }
89}
90
91/// The main IndexMap data-structure type.
92///
93/// This map type uses a [HashSet] to store the underlying items.
94/// The underlying items are wrapped in a custom struct, hidden from the public API, to workaround
95/// Rust broken coherence and WTF other stupid similar rules.
96#[derive(Default, Clone, Debug)]
97pub struct IndexMap<V>(HashSet<Item<V>>);
98
99impl<V> IndexMap<V> {
100    /// Creates a new instance of an [IndexMap].
101    pub fn new() -> IndexMap<V> {
102        IndexMap(HashSet::new())
103    }
104
105    /// Returns the number of items in this [IndexMap].
106    pub fn len(&self) -> usize {
107        self.0.len()
108    }
109
110    /// Returns true when this [IndexMap] is empty.
111    pub fn is_empty(&self) -> bool {
112        self.0.is_empty()
113    }
114
115    /// Creates a new instance of an [IndexMap] with a given capacity.
116    ///
117    /// # Arguments
118    ///
119    /// * `capacity`: the capacity of the new [IndexMap].
120    pub fn with_capacity(capacity: usize) -> IndexMap<V> {
121        Self(HashSet::with_capacity(capacity))
122    }
123
124    /// Returns an iterator over all elements contained in the map.
125    pub fn iter(&self) -> impl Iterator<Item = &V> {
126        self.0.iter().map(|v| &v.0)
127    }
128}
129
130impl<V: Index> IndexMap<V> {
131    /// Inserts a new item in this [IndexMap].
132    ///
133    /// # Arguments
134    ///
135    /// * `value`: the value to be inserted.
136    ///
137    /// returns: ()
138    pub fn insert(&mut self, value: V) {
139        self.0.insert(Item(value));
140    }
141
142    /// Gets an element stored in this [IndexMap] from its key.
143    ///
144    /// # Arguments
145    ///
146    /// * `key`: the key of the element to look for.
147    #[allow(private_bounds)] // Because Rust is a piece of shit!!
148    pub fn get(&self, key: &V::Key) -> Option<&V>
149    where
150        Item<V>: Borrow<V::Key>,
151    {
152        self.0.get(key).map(|v| &v.0)
153    }
154}
155
156impl<'a, V: Index> std::ops::Index<&'a V::Key> for IndexMap<V>
157where
158    Item<V>: Borrow<V::Key>,
159{
160    type Output = V;
161
162    fn index(&self, index: &'a V::Key) -> &Self::Output {
163        self.get(index).unwrap()
164    }
165}
bp3d_util/index_map.rs

bp3d_util/
index_map.rs
