arrayset/ord/
map.rs

1mod entry;
2mod into_iter;
3mod iter;
4mod iter_mut;
5mod keys;
6mod values;
7mod values_mut;
8
9pub use entry::{Entry, OccupiedEntry, VacantEntry};
10pub use into_iter::IntoIter;
11pub use iter::Iter;
12pub use iter_mut::IterMut;
13pub use keys::Keys;
14pub use values::Values;
15pub use values_mut::ValuesMut;
16
17use core::{
18    borrow::Borrow,
19    cmp::{Ord, Ordering},
20    fmt,
21    hash::{Hash, Hasher},
22    mem::{self, MaybeUninit},
23    ops::{Index, Range},
24    ptr,
25};
26
27enum InsertIndex {
28    Found(usize),
29    NotFound(usize),
30}
31
32/// Unwind safety struct for retain function.
33struct RetainRestDropper<'a, K, V, const N: usize> {
34    range: Range<usize>,
35    keys: &'a mut [MaybeUninit<K>; N],
36    values: &'a mut [MaybeUninit<V>; N],
37}
38
39impl<'a, K, V, const N: usize> RetainRestDropper<'a, K, V, N> {
40    fn consume(&mut self) {
41        self.range.next();
42    }
43}
44
45impl<'a, K, V, const N: usize> Drop for RetainRestDropper<'a, K, V, N> {
46    fn drop(&mut self) {
47        if self.range.is_empty() {
48            return;
49        }
50        let ptr = unsafe { self.keys.as_mut_ptr().offset(self.range.start as isize) } as *mut K;
51        let key_slice = ptr::slice_from_raw_parts_mut(ptr, self.range.len());
52        let ptr = unsafe { self.values.as_mut_ptr().offset(self.range.start as isize) as *mut V };
53        let value_slice = ptr::slice_from_raw_parts_mut(ptr, self.range.len());
54        unsafe {
55            ptr::drop_in_place(key_slice);
56            ptr::drop_in_place(value_slice);
57        }
58    }
59}
60
61/// A heapless, ord-based array map. Operates very similarly to [`BTreeMap`],
62/// but maintains its keys and values as single arrays stored inside itself.
63/// Sorted insertions are optimized and will be processed in constant time.
64///
65/// [`BTreeMap`]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
66pub struct OrdMap<K, V, const N: usize> {
67    len: usize,
68    keys: [MaybeUninit<K>; N],
69    values: [MaybeUninit<V>; N],
70}
71
72impl<K, V, const N: usize> OrdMap<K, V, N> {
73    fn insert_index(&self, key: &K) -> InsertIndex
74    where
75        K: Ord,
76    {
77        let Some((last, _)) = self.last_key_value() else {
78            return InsertIndex::NotFound(0);
79        };
80        match last.cmp(key) {
81            Ordering::Less => InsertIndex::NotFound(self.len),
82            Ordering::Equal => InsertIndex::Found(self.len - 1),
83            Ordering::Greater => match self.keys_slice().binary_search(key) {
84                Ok(index) => InsertIndex::Found(index),
85                Err(index) => InsertIndex::NotFound(index),
86            },
87        }
88    }
89
90    fn get_index<Q>(&self, key: &Q) -> Option<usize>
91    where
92        K: Borrow<Q>,
93        Q: Ord + ?Sized,
94    {
95        self.keys_slice()
96            .binary_search_by(move |k| <K as Borrow<Q>>::borrow(k).cmp(key))
97            .ok()
98    }
99
100    pub(crate) fn keys_ptr(&self) -> *const K {
101        self.keys.as_ptr() as *const K
102    }
103
104    /// Get the keys as a slice.  The keys will always be ordered.
105    ///
106    ///
107    /// # Examples
108    ///
109    /// ```
110    /// # use arrayset::OrdMap;
111    /// let mut map: OrdMap<_, _, 16> = Default::default();
112    /// map.insert(7, "alpha");
113    /// map.insert(8, "beta");
114    /// map.insert(1, "gamma");
115    /// map.insert(2, "delta");
116    /// assert_eq!(map.keys_slice(), &[1, 2, 7, 8]);
117    /// ```
118    pub fn keys_slice(&self) -> &[K] {
119        let ptr = self.keys.as_ptr() as *const K;
120        unsafe { core::slice::from_raw_parts(ptr, self.len) }
121    }
122
123    /// Get the values as a slice.  The values are ordered by their respective keys.
124    ///
125    ///
126    /// # Examples
127    ///
128    /// ```
129    /// # use arrayset::OrdMap;
130    /// let mut map: OrdMap<_, _, 16> = Default::default();
131    /// map.insert(7, "alpha");
132    /// map.insert(8, "beta");
133    /// map.insert(1, "gamma");
134    /// map.insert(2, "delta");
135    /// assert_eq!(map.values_slice(), &["gamma", "delta", "alpha", "beta"]);
136    /// ```
137    pub fn values_slice(&self) -> &[V] {
138        let ptr = self.values.as_ptr() as *const V;
139        unsafe { core::slice::from_raw_parts(ptr, self.len) }
140    }
141
142    /// Get the values as a slice.  The values are ordered by their respective keys.
143    ///
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// # use arrayset::OrdMap;
149    /// let mut map: OrdMap<_, _, 16> = Default::default();
150    /// map.insert(7, "alpha");
151    /// map.insert(8, "beta");
152    /// map.insert(1, "gamma");
153    /// map.insert(2, "delta");
154    /// map.values_mut_slice()[1] = "epsilon";
155    /// assert_eq!(map.values_slice(), &["gamma", "epsilon", "alpha", "beta"]);
156    /// assert_eq!(map.get(&2), Some(&"epsilon"));
157    /// ```
158    pub fn values_mut_slice(&mut self) -> &mut [V] {
159        let ptr = self.values.as_mut_ptr() as *mut V;
160        unsafe { core::slice::from_raw_parts_mut(ptr, self.len) }
161    }
162
163    /// Get the values as a slice.  The values are ordered by their respective keys.
164    ///
165    ///
166    /// # Examples
167    ///
168    /// ```
169    /// # use arrayset::OrdMap;
170    /// let mut map: OrdMap<_, _, 16> = Default::default();
171    /// map.insert(7, "alpha");
172    /// map.insert(8, "beta");
173    /// map.insert(1, "gamma");
174    /// map.insert(2, "delta");
175    /// assert_eq!(map.slices(), ([1, 2, 7, 8].as_slice(), ["gamma", "delta", "alpha", "beta"].as_slice()));
176    /// ```
177    pub fn slices(&self) -> (&[K], &[V]) {
178        (self.keys_slice(), self.values_slice())
179    }
180    pub fn slices_mut(&mut self) -> (&[K], &mut [V]) {
181        let keys = {
182            let ptr = self.keys.as_ptr() as *const K;
183            unsafe { core::slice::from_raw_parts(ptr, self.len) }
184        };
185        let values = {
186            let ptr = self.values.as_mut_ptr() as *mut V;
187            unsafe { core::slice::from_raw_parts_mut(ptr, self.len) }
188        };
189        (keys, values)
190    }
191
192    pub fn new() -> Self {
193        Self::default()
194    }
195
196    pub fn len(&self) -> usize {
197        self.len
198    }
199    pub fn is_empty(&self) -> bool {
200        self.len == 0
201    }
202
203    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, N>
204    where
205        K: Ord,
206    {
207        match self.insert_index(&key) {
208            InsertIndex::Found(index) => Entry::occupied(self, index),
209            InsertIndex::NotFound(index) => Entry::vacant(self, index, key),
210        }
211    }
212
213    /// Insert the value into the map.  Note that the semantics of this
214    /// operation are not exactly the same as for BTreeMap.  This will not
215    /// replace existing values.
216    ///  The possible results are:
217    /// * `Ok(Some((K, V)))`: If the key already existed in the map.  The key
218    ///   and value are not inserted, and they are returned back to the caller.
219    /// * `Ok(None)`: If the key and value were inserted successfully without
220    ///   replacement.
221    /// * `Err((K, V))`: If the set was full; the and value are returned to the caller.
222    ///
223    /// # Examples
224    ///
225    /// ```
226    /// # use arrayset::OrdMap;
227    /// let mut map: OrdMap<_, _, 2> = Default::default();
228    /// assert_eq!(
229    ///     map.insert("alpha", 1),
230    ///     Ok(None),
231    /// );
232    /// assert_eq!(
233    ///     map.insert("alpha", 2),
234    ///     Ok(Some(("alpha", 2))),
235    /// );
236    /// assert_eq!(
237    ///     map.insert("beta", 3),
238    ///     Ok(None),
239    /// );
240    /// assert_eq!(
241    ///     map.insert("gamma", 4),
242    ///     Err(("gamma", 4)),
243    /// );
244    /// ```
245    pub fn insert(&mut self, key: K, value: V) -> Result<Option<(K, V)>, (K, V)>
246    where
247        K: Ord,
248    {
249        match self.insert_index(&key) {
250            InsertIndex::Found(_) => Ok(Some((key, value))),
251            InsertIndex::NotFound(index) => self.insert_at(index, key, value).map(|()| None),
252        }
253    }
254
255    /// A raw insert at a particular index.  The key and value are returned on a
256    /// full map.
257    fn insert_at(&mut self, index: usize, key: K, value: V) -> Result<(), (K, V)> {
258        if self.len == N {
259            Err((key, value))
260        } else {
261            self.keys[index..=self.len].rotate_right(1);
262            self.keys[index].write(key);
263            self.values[index..=self.len].rotate_right(1);
264            self.values[index].write(value);
265            self.len += 1;
266            Ok(())
267        }
268    }
269
270    /// Replace the key and value at the index and return the old ones.
271    fn replace_at(&mut self, index: usize, key: K, value: V) -> (K, V) {
272        let prev_key = mem::replace(&mut self.keys[index], MaybeUninit::new(key));
273        let prev_value = mem::replace(&mut self.values[index], MaybeUninit::new(value));
274        unsafe { (prev_key.assume_init(), prev_value.assume_init()) }
275    }
276
277    /// Insert the value into the map, replacing an existing key if found.
278    ///  The possible results are:
279    /// * `Ok(Some((K, V)))`: If the key already existed in the map.  The key
280    ///   and value are replaced, and the previous key and value are returned
281    ///   back to the caller.
282    /// * `Ok(None)`: If the key and value were inserted successfully without
283    ///   replacement.
284    /// * `Err((K, V))`: If the set was full; the and value are returned to the caller.
285    ///
286    /// # Examples
287    ///
288    /// ```
289    /// # use arrayset::OrdMap;
290    /// let mut map: OrdMap<_, _, 2> = Default::default();
291    /// assert_eq!(
292    ///     map.replace("alpha", 1),
293    ///     Ok(None),
294    /// );
295    /// assert_eq!(
296    ///     map.replace("alpha", 2),
297    ///     Ok(Some(("alpha", 1))),
298    /// );
299    /// assert_eq!(
300    ///     map.replace("beta", 3),
301    ///     Ok(None),
302    /// );
303    /// assert_eq!(
304    ///     map.replace("gamma", 4),
305    ///     Err(("gamma", 4)),
306    /// );
307    /// ```
308    pub fn replace(&mut self, key: K, value: V) -> Result<Option<(K, V)>, (K, V)>
309    where
310        K: Ord,
311    {
312        match self.insert_index(&key) {
313            InsertIndex::Found(index) => Ok(Some(self.replace_at(index, key, value))),
314            InsertIndex::NotFound(index) => self.insert_at(index, key, value).map(|()| None),
315        }
316    }
317
318    pub fn get<Q>(&self, key: &Q) -> Option<&V>
319    where
320        K: Borrow<Q>,
321        Q: Ord + ?Sized,
322    {
323        self.get_index(key)
324            .map(|index| unsafe { self.values[index].assume_init_ref() })
325    }
326
327    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
328    where
329        K: Borrow<Q>,
330        Q: Ord + ?Sized,
331    {
332        self.get_index(key).map(|index| unsafe {
333            (
334                self.keys[index].assume_init_ref(),
335                self.values[index].assume_init_ref(),
336            )
337        })
338    }
339
340    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
341    where
342        K: Borrow<Q>,
343        Q: Ord + ?Sized,
344    {
345        self.get_index(key)
346            .map(|index| unsafe { self.values[index].assume_init_mut() })
347    }
348
349    pub fn get_key_value_mut<Q>(&mut self, key: &Q) -> Option<(&K, &mut V)>
350    where
351        K: Borrow<Q>,
352        Q: Ord + ?Sized,
353    {
354        self.get_index(key).map(|index| unsafe {
355            (
356                self.keys[index].assume_init_ref(),
357                self.values[index].assume_init_mut(),
358            )
359        })
360    }
361
362    pub fn contains_key<Q>(&self, key: &Q) -> bool
363    where
364        K: Borrow<Q>,
365        Q: Ord + ?Sized,
366    {
367        self.get_index(key).is_some()
368    }
369
370    /// Remove the value from the map.
371    /// Returns the removed value.
372    pub fn remove<Q>(&mut self, key: &Q) -> Option<(K, V)>
373    where
374        K: Borrow<Q>,
375        Q: Ord + ?Sized,
376    {
377        self.get_index(key).map(move |index| self.remove_at(index))
378    }
379
380    /// Remove the entry at the index.
381    /// Returns the removed key and value.
382    fn remove_at(&mut self, index: usize) -> (K, V) {
383        self.keys[index..self.len].rotate_left(1);
384        self.values[index..self.len].rotate_left(1);
385        self.len -= 1;
386        unsafe {
387            (
388                self.keys[self.len].assume_init_read(),
389                self.values[self.len].assume_init_read(),
390            )
391        }
392    }
393
394    pub fn clear(&mut self) {
395        if self.len == 0 {
396            return;
397        }
398
399        let ptr = self.keys.as_mut_ptr() as *mut K;
400        let key_slice = ptr::slice_from_raw_parts_mut(ptr, self.len);
401        let ptr = self.values.as_mut_ptr() as *mut V;
402        let value_slice = ptr::slice_from_raw_parts_mut(ptr, self.len);
403        self.len = 0;
404        unsafe {
405            ptr::drop_in_place(key_slice);
406            ptr::drop_in_place(value_slice);
407        }
408    }
409
410    pub fn iter(&self) -> Iter<'_, K, V> {
411        Iter::new(self.keys_slice(), self.values_slice())
412    }
413
414    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
415        let (keys, values) = self.slices_mut();
416        IterMut::new(keys, values)
417    }
418
419    pub fn keys(&self) -> Keys<'_, K> {
420        Keys::new(self.keys_slice())
421    }
422    pub fn values(&self) -> Values<'_, V> {
423        Values::new(self.values_slice())
424    }
425    pub fn values_mut(&mut self) -> ValuesMut<'_, V> {
426        ValuesMut::new(self.values_mut_slice())
427    }
428    pub fn first_key_value(&self) -> Option<(&K, &V)> {
429        if self.len == 0 {
430            None
431        } else {
432            let key_slot = &self.keys[0];
433            let value_slot = &self.values[0];
434            Some(unsafe { (key_slot.assume_init_ref(), value_slot.assume_init_ref()) })
435        }
436    }
437    pub fn last_key_value(&self) -> Option<(&K, &V)> {
438        if self.len == 0 {
439            None
440        } else {
441            let key_slot = &self.keys[self.len - 1];
442            let value_slot = &self.values[self.len - 1];
443            Some(unsafe { (key_slot.assume_init_ref(), value_slot.assume_init_ref()) })
444        }
445    }
446    pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>> {
447        if self.len == 0 {
448            None
449        } else {
450            Some(OccupiedEntry {
451                map: self,
452                index: 0,
453            })
454        }
455    }
456    pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>> {
457        if self.len == 0 {
458            None
459        } else {
460            let index = self.len - 1;
461            Some(OccupiedEntry { map: self, index })
462        }
463    }
464    pub fn pop_first(&mut self) -> Option<(K, V)> {
465        if self.len == 0 {
466            None
467        } else {
468            self.keys[..self.len].rotate_left(1);
469            self.values[..self.len].rotate_left(1);
470            self.len -= 1;
471            let key_slot = &self.keys[self.len];
472            let value_slot = &self.values[self.len];
473            Some(unsafe { (key_slot.assume_init_read(), value_slot.assume_init_read()) })
474        }
475    }
476    pub fn pop_last(&mut self) -> Option<(K, V)> {
477        if self.len == 0 {
478            None
479        } else {
480            self.len -= 1;
481            let key_slot = &self.keys[self.len];
482            let value_slot = &self.values[self.len];
483            Some(unsafe { (key_slot.assume_init_read(), value_slot.assume_init_read()) })
484        }
485    }
486
487    /// Retains only the elements specified by the predicate.
488
489    /// In other words, remove all pairs (k, v) for which f(&k, &mut v) returns
490    /// false. The elements are visited in ascending key order.
491    /// If the predicate panics, everything will still be correctly dropped.
492    ///
493    /// # Examples
494    ///
495    /// ```
496    /// # use arrayset::OrdMap;
497    /// let mut map: OrdMap<_, _, 16> = Default::default();
498    /// for s in ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", "eta"] {
499    ///     assert_eq!(
500    ///         map.insert(s, ()),
501    ///         Ok(None),
502    ///     );
503    /// }
504    /// map.retain(|k, v| matches!(k.chars().next().unwrap(), 'a' | 'e' | 'i' | 'o' | 'u'));
505    /// assert_eq!(map.keys_slice(), &["alpha", "epsilon", "eta"]);
506    /// ```
507    ///
508    /// ## Panic safety
509    ///
510    /// ```
511    /// # use arrayset::OrdMap;
512    /// use std::rc::Rc;
513    /// use std::sync::atomic::{AtomicBool, Ordering};
514    /// let mut dropped = Vec::new();
515    /// let mut map: OrdMap<_, _, 16> = Default::default();
516    /// struct Dropper {
517    ///   b: Rc<AtomicBool>,
518    /// }
519    /// impl Drop for Dropper {
520    ///     fn drop(&mut self) {
521    ///         self.b.store(true, Ordering::SeqCst);
522    ///     }
523    /// }
524    /// for s in ["alpha", "beta", "gamma", "delta", "epsilon", "zeta", "eta"] {
525    ///     let b = Rc::new(AtomicBool::new(false));
526    ///     dropped.push(b.clone());
527    ///     map.insert(s, Dropper { b });
528    /// }
529    /// std::panic::catch_unwind(move || {
530    ///     map.retain(|k, v| if *k == "delta" {
531    ///         panic!()
532    ///     } else {
533    ///         true
534    ///     });
535    /// });
536    /// assert!(dropped.into_iter().all(|b| b.load(Ordering::SeqCst)));
537    /// ```
538    pub fn retain<F>(&mut self, mut f: F)
539    where
540        K: Ord,
541        F: FnMut(&K, &mut V) -> bool,
542    {
543        // Prevent leaking on panic of the FnMut
544        let mut dropper = RetainRestDropper {
545            range: 0..self.len,
546            keys: &mut self.keys,
547            values: &mut self.values,
548        };
549        let prev_len = self.len;
550        self.len = 0;
551        for index in 0..prev_len {
552            if f(unsafe { dropper.keys[index].assume_init_ref() }, unsafe {
553                dropper.values[index].assume_init_mut()
554            }) {
555                if index != self.len {
556                    dropper.keys[self.len].write(unsafe { dropper.keys[index].assume_init_read() });
557                    dropper.values[self.len]
558                        .write(unsafe { dropper.values[index].assume_init_read() });
559                }
560                self.len += 1;
561            } else {
562                unsafe {
563                    dropper.keys[index].assume_init_drop();
564                    dropper.values[index].assume_init_drop();
565                }
566            }
567            dropper.consume();
568        }
569    }
570}
571
572impl<K, V, const N: usize> Default for OrdMap<K, V, N> {
573    fn default() -> Self {
574        Self {
575            len: 0,
576            keys: unsafe { MaybeUninit::uninit().assume_init() },
577            values: unsafe { MaybeUninit::uninit().assume_init() },
578        }
579    }
580}
581impl<K, V, const N: usize> Clone for OrdMap<K, V, N>
582where
583    K: Clone,
584    V: Clone,
585{
586    fn clone(&self) -> Self {
587        let mut keys: [MaybeUninit<K>; N] = unsafe { MaybeUninit::uninit().assume_init() };
588        let mut values: [MaybeUninit<V>; N] = unsafe { MaybeUninit::uninit().assume_init() };
589
590        for (source, destination) in self.keys_slice().iter().zip(&mut keys[..self.len]) {
591            destination.write(source.clone());
592        }
593
594        for (source, destination) in self.values_slice().iter().zip(&mut values[..self.len]) {
595            destination.write(source.clone());
596        }
597
598        Self {
599            keys,
600            values,
601            len: self.len,
602        }
603    }
604}
605
606impl<K, V, const N: usize> Drop for OrdMap<K, V, N> {
607    fn drop(&mut self) {
608        self.clear();
609    }
610}
611
612impl<K, V, const N: usize> fmt::Debug for OrdMap<K, V, N>
613where
614    K: fmt::Debug,
615    V: fmt::Debug,
616{
617    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
618        f.debug_map().entries(self.iter()).finish()
619    }
620}
621
622impl<K, Q, V, const N: usize> Index<&Q> for OrdMap<K, V, N>
623where
624    K: Borrow<Q>,
625    Q: Ord + ?Sized,
626{
627    type Output = V;
628
629    fn index(&self, key: &Q) -> &Self::Output {
630        self.get(key).unwrap()
631    }
632}
633
634impl<K, V, const N: usize> IntoIterator for OrdMap<K, V, N> {
635    type Item = (K, V);
636
637    type IntoIter = IntoIter<K, V, N>;
638
639    fn into_iter(self) -> Self::IntoIter {
640        IntoIter::new(self)
641    }
642}
643
644impl<'a, K, V, const N: usize> IntoIterator for &'a OrdMap<K, V, N> {
645    type Item = (&'a K, &'a V);
646
647    type IntoIter = Iter<'a, K, V>;
648
649    fn into_iter(self) -> Self::IntoIter {
650        self.iter()
651    }
652}
653
654impl<'a, K, V, const N: usize> IntoIterator for &'a mut OrdMap<K, V, N> {
655    type Item = (&'a K, &'a mut V);
656
657    type IntoIter = IterMut<'a, K, V>;
658
659    fn into_iter(self) -> Self::IntoIter {
660        self.iter_mut()
661    }
662}
663
664impl<K, V, const N1: usize, const N2: usize> PartialOrd<OrdMap<K, V, N2>> for OrdMap<K, V, N1>
665where
666    K: PartialOrd<K>,
667    V: PartialOrd<V>,
668{
669    fn partial_cmp(&self, other: &OrdMap<K, V, N2>) -> Option<core::cmp::Ordering> {
670        self.iter().partial_cmp(other.iter())
671    }
672}
673impl<K, V, const N1: usize, const N2: usize> PartialEq<OrdMap<K, V, N2>> for OrdMap<K, V, N1>
674where
675    K: PartialEq<K>,
676    V: PartialEq<V>,
677{
678    fn eq(&self, other: &OrdMap<K, V, N2>) -> bool {
679        self.iter().eq(other.iter())
680    }
681}
682
683impl<K, V, const N: usize> Eq for OrdMap<K, V, N>
684where
685    K: Eq,
686    V: Eq,
687{
688}
689
690impl<K, V, const N: usize> Ord for OrdMap<K, V, N>
691where
692    K: Ord,
693    V: Ord,
694{
695    fn cmp(&self, other: &OrdMap<K, V, N>) -> core::cmp::Ordering {
696        self.iter().cmp(other.iter())
697    }
698}
699
700impl<K, V, const N: usize> Hash for OrdMap<K, V, N>
701where
702    K: Hash,
703    V: Hash,
704{
705    fn hash<H: Hasher>(&self, state: &mut H) {
706        state.write_usize(self.len);
707        for pair in self {
708            pair.hash(state);
709        }
710    }
711}
712
713/// Panics on overflow
714impl<K, V, const N: usize> Extend<(K, V)> for OrdMap<K, V, N>
715where
716    K: Ord,
717{
718    fn extend<I>(&mut self, iter: I)
719    where
720        I: IntoIterator<Item = (K, V)>,
721    {
722        for (key, value) in iter {
723            if let Err(_) = self.insert(key, value) {
724                panic!("map overflowed on extend");
725            }
726        }
727    }
728}
729
730/// Panics on overflow
731impl<'a, K, V, const N: usize> Extend<(&'a K, &'a V)> for OrdMap<K, V, N>
732where
733    K: Ord + Copy,
734    V: Copy,
735{
736    fn extend<I>(&mut self, iter: I)
737    where
738        I: IntoIterator<Item = (&'a K, &'a V)>,
739    {
740        for (key, value) in iter {
741            if let Err(_) = self.insert(*key, *value) {
742                panic!("map overflowed on extend");
743            }
744        }
745    }
746}
747
748/// Panics on overflow
749impl<K, V, const N: usize> FromIterator<(K, V)> for OrdMap<K, V, N>
750where
751    K: Ord,
752{
753    fn from_iter<I>(iter: I) -> Self
754    where
755        I: IntoIterator<Item = (K, V)>,
756    {
757        let mut map = Self::new();
758        for (key, value) in iter {
759            if let Err(_) = map.insert(key, value) {
760                panic!("map overflowed on extend");
761            }
762        }
763        map
764    }
765}
766
767impl<K, V, const N1: usize, const N2: usize> From<[(K, V); N1]> for OrdMap<K, V, N2>
768where
769    K: Ord,
770{
771    fn from(mut value: [(K, V); N1]) -> Self {
772        value.sort_unstable_by(|a, b| a.0.cmp(&b.0));
773        let mut map = Self::new();
774        for (key, value) in value {
775            if map.len == 0 || unsafe { map.keys[map.len - 1].assume_init_ref() } < &key {
776                if map.len == N2 {
777                    panic!("map overflowed on extend");
778                }
779                map.keys[map.len].write(key);
780                map.values[map.len].write(value);
781                map.len += 1;
782            }
783        }
784        map
785    }
786}
arrayset/ord/map.rs

arrayset/ord/
map.rs
