map_of_indexes/
lib.rs

1//! # Map-of-indexes
2//!
3//! [![crates.io](https://img.shields.io/crates/v/map-of-indexes.svg)](https://crates.io/crates/map-of-indexes)
4//! [![docs.rs](https://docs.rs/map-of-indexes/badge.svg)](https://docs.rs/map-of-indexes)
5//!
6//! A small utility crate when you have a list of unique but not dense indexes for which to each you want to associates a value.
7//! In the documentation the indexes are referred as `key`. *Not* an indexed map!
8//!
9//! It can be considered a slower but more compact version of [`BTreeMap`](std::collections::BTreeMap).
10//! # Examples
11//! A brief example of the crate's capacities
12//! ```
13//! use map_of_indexes::{MapOfIndexes, MapOfIndexesError, KeyValue};
14//!
15//! # fn main() -> Result<(), MapOfIndexesError> {
16//! let v = vec![(3, 4), (1, 2), (5, 6)];
17//! let mut map: MapOfIndexes::<(u8, u16)> = v.try_into()?;
18//!
19//! map.push((7,8));
20//! let push_res = map.push_checked((0,9));
21//! assert_eq!(push_res, Err(MapOfIndexesError::SmallerKey));
22//!
23//! let old_key_value = map.set((1,9))?;
24//! assert_eq!(old_key_value.key(), &1);
25//! assert_eq!(old_key_value.value(), &2);
26//! # Ok(())
27//! # }
28//! ```
29//! [`CombinedKeyValue`](crate::CombinedKeyValue) is a compact representation when you need to save space.
30//! ```
31//! # use map_of_indexes::{MapOfIndexes, MapOfIndexesError, KeyValue};
32//! use map_of_indexes::{CombinedKeyValue};
33//! # fn main() -> Result<(), MapOfIndexesError> {
34//! // We have keys that take up to 40 bits, and value up to 24;
35//! // Using (u64, u64) would have wasted 8 byte per entry.
36//! type CombinedU64 = CombinedKeyValue<u64, 40, 24>;
37//! CombinedU64::safety_check(); // ensure that key and value size fit on the unsigned integer.
38//!
39//! let v = vec![CombinedU64::new(3u64, 4u32), CombinedU64::new(1u64, 2u32), CombinedU64::new(5u64, 6u32)];
40//! let map: MapOfIndexes<_> = v.try_into()?;
41//! let inner_raw: Vec<u64> = Vec::from_iter(map.iter().map(|x| *x.as_ref()));
42//! assert_eq!(inner_raw, vec![2199023255553, 4398046511107, 6597069766661]);
43//! # Ok(())
44//! # }
45//! ```
46//! For an even more compact representation, consider using the [`bitvec`](https://docs.rs/bitvec/latest/bitvec/index.html) crate.
47
48#![warn(clippy::pedantic)]
49#![warn(clippy::cargo)]
50#![allow(clippy::semicolon_if_nothing_returned)]
51// #![allow(clippy::missing_panics_doc)]
52// #![allow(clippy::missing_errors_doc)]
53
54use std::fmt::Debug;
55use std::ops::Deref;
56
57use thiserror::Error;
58
59/// Trait that `T` must implement to be able to work with [`MapOfIndexes`](crate::MapOfIndexes) of `T`.
60///
61/// Can be implemented on your own custom structs. `KeyValue::K` represents the key (index) of the pair, while `KeyValue::V` is the value.
62///
63/// [`KeyValue`](crate::KeyValue) is already implemented for all 2-tuples, the first element being considered as the key.
64/// # Examples
65/// ```
66/// use map_of_indexes::KeyValue;
67///
68/// let tuple: (String, i64) = ("Key".to_string(), 123);
69/// // In this blanket implementation, both functions return a reference
70/// assert_eq!(tuple.key(), &"Key");
71/// assert_eq!(tuple.value(), &123i64);
72/// ```
73///
74/// If you need a very compact representation, see [`CombinedKeyValue`](crate::CombinedKeyValue), which stores both the key and the key on a uint of a given size.
75// #[doc(notable_trait)]
76pub trait KeyValue<'a> {
77    type K: Ord;
78    type V;
79    fn key(&'a self) -> Self::K;
80    fn value(&'a self) -> Self::V;
81}
82
83impl<'a, KEY: Ord, VALUE> KeyValue<'a> for (KEY, VALUE)
84where
85    KEY: 'a,
86    VALUE: 'a,
87{
88    type K = &'a KEY;
89    type V = &'a VALUE;
90    fn key(&'a self) -> Self::K {
91        &self.0
92    }
93    fn value(&'a self) -> Self::V {
94        &self.1
95    }
96}
97
98/// Different kind of errors generated by the library
99#[derive(Error, Debug, PartialEq, Eq, Hash)]
100pub enum MapOfIndexesError {
101    /// At least two elements with same keys. Keys must be uniques.
102    #[error("At least two elements with same keys. Keys must be uniques.")]
103    DuplicateKeys,
104    /// No elements were found with this key.
105    #[error("No elements were found with this key.")]
106    KeyNotFound,
107    /// Attempted to push an element with a lower key than last element.
108    #[error("Attempted to push an element with a lower key than last element.")]
109    SmallerKey,
110}
111
112/// Basically a sorted vec
113#[derive(Clone, Debug)]
114pub struct MapOfIndexes<T> {
115    inner: Vec<T>,
116}
117
118/// Easy access to the underlying vec
119impl<T> Deref for MapOfIndexes<T> {
120    type Target = Vec<T>;
121
122    fn deref(&self) -> &Self::Target {
123        &self.inner
124    }
125}
126
127impl<T: for<'a> KeyValue<'a>> Default for MapOfIndexes<T> {
128    fn default() -> Self {
129        Self::new()
130    }
131}
132
133/// Under the hood, will sort the vec by key. Will succeed if there are no elements with the same key
134impl<T: for<'a> KeyValue<'a>> TryFrom<Vec<T>> for MapOfIndexes<T> {
135    type Error = MapOfIndexesError;
136
137    fn try_from(mut vec: Vec<T>) -> Result<Self, Self::Error> {
138        // Other solution was to check duplicate while sorting, supposedly faster to make linear search after
139        // when comparing elements is cheap
140        vec.sort_unstable_by(|a, b| a.key().cmp(&b.key()));
141        let duplicate = vec.windows(2).any(|w| w[0].key() == w[1].key());
142        if duplicate {
143            Err(MapOfIndexesError::DuplicateKeys)
144        } else {
145            Ok(Self { inner: vec })
146        }
147    }
148}
149
150impl<T: for<'a> KeyValue<'a>> MapOfIndexes<T> {
151    #[must_use]
152    pub fn new() -> Self {
153        Self { inner: Vec::new() }
154    }
155
156    #[must_use]
157    pub fn with_capacity(capacity: usize) -> Self {
158        Self {
159            inner: Vec::with_capacity(capacity),
160        }
161    }
162
163    /// Push an element to the map. Panic if the pushed key is smaller than the last element's one.
164    /// # Panics
165    /// ```should_panic
166    /// use map_of_indexes::MapOfIndexes;
167    ///
168    /// let mut m: MapOfIndexes<(isize, &'static str)> = MapOfIndexes::new();
169    /// m.push((1, "cool"));
170    /// m.push((-10, "panic!"));
171    /// ```
172    #[inline]
173    pub fn push(&mut self, element: T) {
174        match self.push_checked(element) {
175            Ok(()) => (),
176            Err(err) => panic!("{}", err),
177        }
178    }
179
180    /// Push an element to the map.
181    /// # Example
182    /// ```
183    /// use map_of_indexes::{MapOfIndexes, MapOfIndexesError};
184    ///
185    /// let mut m: MapOfIndexes<(isize, &'static str)> = MapOfIndexes::new();
186    /// assert!(m.push_checked((1, "cool")).is_ok())
187    /// ```
188    /// # Errors
189    /// Returns [`MapOfIndexesError::SmallerKey`](crate::MapOfIndexesError) if the pushed key is smaller than the last element's one.
190    /// ```
191    /// # use map_of_indexes::{MapOfIndexes, MapOfIndexesError};
192    ///
193    /// let mut m: MapOfIndexes<(isize, &'static str)> = MapOfIndexes::new();
194    /// m.push((1, "cool"));
195    /// let err = m.push_checked((-10, "err!"));
196    /// assert_eq!(err, Err(MapOfIndexesError::SmallerKey))
197    /// ```
198    pub fn push_checked(&mut self, element: T) -> Result<(), MapOfIndexesError> {
199        if let Some(last) = self.last() {
200            if last.key() >= element.key() {
201                return Err(MapOfIndexesError::SmallerKey);
202            }
203        }
204        self.inner.push(element);
205        Ok(())
206    }
207
208    #[inline]
209    fn get_idx<'a>(&'a self, key: &<T as KeyValue<'a>>::K) -> Option<usize> {
210        self.binary_search_by(|t| t.key().cmp(key)).ok()
211    }
212
213    /// Performs a dichotomal search and returns the element
214    pub fn get_element<'a>(&'a self, key: &<T as KeyValue<'a>>::K) -> Option<&T> {
215        self.get_idx(key).map(|idx| &self[idx])
216    }
217
218    /// Performs a dichotomal search and returns the value
219    pub fn get_value<'a>(&'a self, key: &<T as KeyValue<'a>>::K) -> Option<<T as KeyValue<'_>>::V> {
220        self.get_idx(key).map(|idx| self[idx].value())
221    }
222
223    /// Find and replace the key-value element, returning the previous key-value if found, or an error otherwise.
224    /// # Examples
225    /// ```
226    /// # use map_of_indexes::MapOfIndexes;
227    /// let mut s = MapOfIndexes::<(u16, u16)>::new();
228    /// s.push((10, 10));
229    /// s.push((11, 11));
230    /// s.push((12, 12));
231    /// s.push((13, 13));
232    /// let old_key_value = s.set((10, 100)).unwrap();
233    /// assert_eq!(old_key_value, (10, 10));
234    /// assert_eq!(*s, &[(10, 100), (11, 11), (12, 12), (13, 13)]);
235    /// ```
236    /// # Errors
237    /// ```
238    /// use map_of_indexes::{MapOfIndexes, MapOfIndexesError};
239    ///
240    /// let mut s = MapOfIndexes::<(&'static str, &'static str)>::new();
241    /// s.push(("test", "value"));
242    /// let err = s
243    /// .set(("key does not exist", "err must be returned"))
244    /// .err()
245    /// .unwrap();
246    /// assert_eq!(err, MapOfIndexesError::KeyNotFound);
247    /// ```
248    pub fn set(&mut self, element: T) -> Result<T, MapOfIndexesError> {
249        let idx_opt = self.get_idx(&element.key());
250        idx_opt
251            .map(|idx| std::mem::replace(&mut self.inner[idx], element))
252            .ok_or(MapOfIndexesError::KeyNotFound)
253    }
254}
255
256/// A compact struct that implement [`KeyValue`](crate::KeyValue)
257///
258/// Both the key and value are stored on the same element which can be any unsigned integer.
259///
260/// # Examples
261///
262/// ```
263/// # use map_of_indexes::{MapOfIndexes, MapOfIndexesError, KeyValue};
264/// use map_of_indexes::{CombinedKeyValue};
265/// # fn main() -> Result<(), MapOfIndexesError> {
266/// // We have keys that take up to 40 bits, and value up to 24;
267/// // Using (u64, u64) would have wasted 8 byte per entry.
268/// type CombinedU64 = CombinedKeyValue<u64, 40, 24>;
269/// CombinedU64::safety_check(); // ensure that key and value size fit on the unsigned integer.
270///
271/// let v = vec![CombinedU64::new(3u64, 4u32), CombinedU64::new(1u64, 2u32), CombinedU64::new(5u64, 6u32)];
272/// let map: MapOfIndexes<_> = v.try_into()?;
273/// let inner_raw: Vec<u64> = Vec::from_iter(map.iter().map(|x| *x.as_ref()));
274/// assert_eq!(inner_raw, vec![2199023255553, 4398046511107, 6597069766661]);
275/// # Ok(())
276/// # }
277/// ```
278///
279/// Not working with signed integer
280/// ```compile_fail
281/// use map_of_indexes::CombinedKeyValue;
282///
283/// // Will not be able to be instanciated
284/// type CombinedI8 = CombinedKeyValue<i8, 4, 4>;
285/// let combined = CombinedI8::new(-10, 3);
286/// ```
287#[derive(Debug, Clone, Copy, Eq, PartialEq, Ord, PartialOrd)]
288pub struct CombinedKeyValue<T, const KEY_NB_BITS: u8, const VALUE_NB_BITS: u8>(T);
289
290// TODO, make that work
291// impl<'a, T, const KEY_NB_BITS: u8, const VALUE_NB_BITS: u8> Debug for CombinedKeyValue<T, KEY_NB_BITS, VALUE_NB_BITS> where CombinedKeyValue<T, KEY_NB_BITS, VALUE_NB_BITS>: KeyValue<'a> + Debug{
292//     fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
293//         write!(f, "CombinedKeyValue<{},{},{}> {{ key: {:?}, value: {:?} }}", std::any::type_name::<T>(), KEY_NB_BITS, VALUE_NB_BITS, self.key(), self.value())
294//     }
295// }
296
297/// Easy access to the underlying `T`
298impl<T, const KEY_NB_BITS: u8, const VALUE_NB_BITS: u8> AsRef<T>
299    for CombinedKeyValue<T, KEY_NB_BITS, VALUE_NB_BITS>
300{
301    fn as_ref(&self) -> &T {
302        &self.0
303    }
304}
305
306// If `KEY_NB_BITS` and `VALUE_NB_BITS` are compatible with backed type, `TryFrom<u128>` should never fail.
307impl<T: TryFrom<u128> + Into<u128>, const KEY_NB_BITS: u8, const VALUE_NB_BITS: u8>
308    CombinedKeyValue<T, { KEY_NB_BITS }, { VALUE_NB_BITS }>
309where
310    <T as TryFrom<u128>>::Error: Debug,
311{
312    // To be run once after defining a type alias.
313    // TODO use Macro instead(?) or associated constant?
314    // pub const TEST: usize = std::mem::size_of::<T>() * 8 - (KEY_NB_BITS + VALUE_NB_BITS) as usize;
315
316    /// Check that chosen values `VALUE_NB_BITS` and `KEY_NB_BITS` can fit on `T`
317    /// # Panics
318    /// Panic when this is not the case
319    /// ```should_panic
320    /// use map_of_indexes::CombinedKeyValue;
321    ///
322    /// type CombinedU8 = CombinedKeyValue<u8, 3, 6>;
323    /// CombinedU8::safety_check();
324    /// ```
325    pub fn safety_check() {
326        assert!(
327            !(std::mem::size_of::<T>() * 8 < (KEY_NB_BITS + VALUE_NB_BITS).into()),
328            "KEY_NB_BITS + VALUE_NB_BITS value is higher than the number of bits of the backup type."
329        );
330    }
331
332    /// # Panics
333    /// panics if `value` or `value` has more bits than their declared size
334    /// ```should_panic
335    /// # use map_of_indexes::CombinedKeyValue;
336    /// type CombinedU8 = CombinedKeyValue<u8, 4, 4>;
337    /// CombinedU8::safety_check(); // always
338    ///
339    /// CombinedU8::new(2u8, 16u8); // 2 ** 4 = 16;
340    /// ```
341    pub fn new<K: Into<u128>, V: Into<u128>>(key: K, value: V) -> Self {
342        let key_uint: u128 = key.into();
343        let value_uint: u128 = value.into();
344        assert!(key_uint < 2u128.pow(KEY_NB_BITS.into()));
345        assert!(value_uint < 2u128.pow(VALUE_NB_BITS.into()));
346        Self(
347            T::try_from(key_uint | (value_uint << KEY_NB_BITS))
348                .expect("Run `Self::safety_check` and should never panic"),
349        )
350    }
351}
352
353impl<'a, T: TryFrom<u128> + Ord + Copy, const KEY_NB_BITS: u8, const VALUE_NB_BITS: u8> KeyValue<'a>
354    for CombinedKeyValue<T, { KEY_NB_BITS }, { VALUE_NB_BITS }>
355where
356    u128: From<T>,
357    <T as TryFrom<u128>>::Error: Debug,
358{
359    type K = T;
360    type V = T;
361    fn key(&self) -> Self::K {
362        T::try_from(u128::from(self.0) & (u128::MAX >> (u128::BITS - u32::from(KEY_NB_BITS))))
363            .expect("Run `Self::safety_check` and should never panic")
364    }
365    fn value(&self) -> Self::V {
366        T::try_from(u128::from(self.0) >> KEY_NB_BITS)
367            .expect("Run `Self::safety_check` and should never panic")
368    }
369}
370
371#[cfg(test)]
372mod test {
373    use super::*;
374
375    #[test]
376    fn test_push_sorted() {
377        let mut s = MapOfIndexes::<(i128, u8)>::new();
378        s.push((1, 1));
379        s.push((2, 1));
380        assert_eq!(&s.inner, &[(1, 1), (2, 1)]);
381    }
382
383    #[test]
384    fn test_get_1() {
385        let mut s = MapOfIndexes::<(i128, u8)>::new();
386        s.push((10, 10));
387        s.push((11, 11));
388        s.push((12, 12));
389        s.push((13, 13));
390        for i in 10..14 {
391            assert_eq!(s.get_value(&&i128::from(i)), Some(&(i as u8)));
392        }
393    }
394    #[test]
395    fn test_get_2() {
396        let mut s = MapOfIndexes::<(u8, u8)>::new();
397        for i in 0..u8::MAX {
398            s.push((i, i));
399            assert_eq!(s.get_value(&&i), Some(&i));
400        }
401    }
402
403    #[test]
404    fn test_try_from() {
405        let s: Vec<(i32, u64)> = vec![(1, 1), (-100, 2), (3, 15)];
406        let sorted_map: MapOfIndexes<(i32, u64)> = s.try_into().unwrap();
407        assert_eq!(&sorted_map.inner, &[(-100, 2), (1, 1), (3, 15)])
408    }
409
410    #[test]
411    fn test_try_from_fail_duplicate() {
412        let s: Vec<(i32, u64)> = vec![(1, 1), (1, 2), (3, 15)];
413        let sorted_map_err = MapOfIndexes::<(i32, u64)>::try_from(s).err().unwrap();
414        assert_eq!(sorted_map_err, MapOfIndexesError::DuplicateKeys)
415    }
416
417    #[test]
418    fn test_combined_key_value_type() {
419        type CombinedU8 = CombinedKeyValue<u8, 4, 4>;
420        CombinedU8::safety_check();
421    }
422
423    #[test]
424    #[should_panic]
425    fn test_combined_key_value_type_error_key() {
426        type CombinedU8 = CombinedKeyValue<u8, 5, 4>;
427        CombinedU8::safety_check();
428    }
429
430    #[test]
431    #[should_panic]
432    fn test_combined_key_value_type_error_value() {
433        type CombinedU8 = CombinedKeyValue<u8, 4, 5>;
434        CombinedU8::safety_check();
435    }
436
437    #[test]
438    fn test_combined_key_value_new() {
439        type CombinedU8 = CombinedKeyValue<u8, 4, 4>;
440        CombinedU8::safety_check();
441        let x = CombinedU8::new(4u8, 3u8);
442        assert_eq!(x.key(), 4u8);
443        assert_eq!(x.value(), 3u8);
444    }
445
446    #[test]
447    fn test_get_element_on_large_map() {
448        let mut map = MapOfIndexes::<(u32, u64)>::with_capacity(400000);
449        for i in 0..400000 {
450            map.push((i as u32, i as u64))
451        }
452        println!("{:?}", &map[0..10]);
453        for j in 0..400000 {
454            assert_eq!(map.get_element(&&(j as u32)), Some(&(j as u32, j as u64)))
455        }
456    }
457}
map_of_indexes/lib.rs

map_of_indexes/
lib.rs
