ferroui_base/utilities/
small_dictionary.rs

1use std::collections::hash_map::{self, Entry};
2use std::collections::HashMap;
3use std::hash::Hash;
4
5/// The number of entries of the inline array.
6const ARRAY_LENGTH: usize = 6;
7
8/// A dictionary that holds one entry in place, up to six entries in a small
9/// array and more in a hash map.
10///
11/// The original restricts keys to reference types and compares them by
12/// reference while the dictionary holds its entries in place or in the
13/// array; here keys compare with `==` in every state, which is identity for
14/// the handle types of this crate.
15pub struct InlineDictionary<TKey, TValue> {
16    data: Data<TKey, TValue>,
17    value: TValue,
18}
19
20/// The original's `object? _data`: nothing, the one key, the small array or
21/// the dictionary.
22enum Data<TKey, TValue> {
23    Null,
24    Key(TKey),
25    Array(Vec<KeyValuePair<TKey, TValue>>),
26    Dictionary(HashMap<TKey, TValue>),
27}
28
29#[derive(Clone, Copy, PartialEq, Eq)]
30enum DataKind {
31    Null,
32    Key,
33    Array,
34    Dictionary,
35}
36
37struct KeyValuePair<TKey, TValue> {
38    key: Option<TKey>,
39    value: TValue,
40}
41
42impl<TKey, TValue: Default> Default for KeyValuePair<TKey, TValue> {
43    fn default() -> Self {
44        Self { key: None, value: TValue::default() }
45    }
46}
47
48impl<TKey, TValue> KeyValuePair<TKey, TValue> {
49    fn new(key: TKey, value: TValue) -> Self {
50        Self { key: Some(key), value }
51    }
52}
53
54impl<TKey: Clone + Eq + Hash, TValue: Default> Default for InlineDictionary<TKey, TValue> {
55    fn default() -> Self {
56        Self::new()
57    }
58}
59
60impl<TKey: Clone + Eq + Hash, TValue: Default> InlineDictionary<TKey, TValue> {
61    pub fn new() -> Self {
62        Self { data: Data::Null, value: TValue::default() }
63    }
64
65    fn kind(&self) -> DataKind {
66        match &self.data {
67            Data::Null => DataKind::Null,
68            Data::Key(_) => DataKind::Key,
69            Data::Array(_) => DataKind::Array,
70            Data::Dictionary(_) => DataKind::Dictionary,
71        }
72    }
73
74    fn new_array() -> Vec<KeyValuePair<TKey, TValue>> {
75        (0..ARRAY_LENGTH).map(|_| KeyValuePair::default()).collect()
76    }
77
78    /// Moves the entries of the small array into a new dictionary.
79    fn upgrade_to_dictionary(arr: Vec<KeyValuePair<TKey, TValue>>) -> HashMap<TKey, TValue> {
80        let mut new_dic = HashMap::new();
81        for kvp in arr {
82            if let Some(key) = kvp.key {
83                new_dic.insert(key, kvp.value);
84            }
85        }
86        new_dic
87    }
88
89    fn set_core(&mut self, key: TKey, value: TValue, overwrite: bool) {
90        match self.kind() {
91            DataKind::Null => {
92                self.data = Data::Key(key);
93                self.value = value;
94            }
95            DataKind::Array => {
96                let Data::Array(arr) = &mut self.data else { unreachable!() };
97                let mut free: Option<usize> = None;
98                let mut existing: Option<usize> = None;
99                for (c, entry) in arr.iter().enumerate() {
100                    if entry.key.as_ref() == Some(&key) {
101                        existing = Some(c);
102                        break;
103                    }
104
105                    if entry.key.is_none() && free.is_none() {
106                        free = Some(c);
107                    }
108                }
109
110                if let Some(c) = existing {
111                    if overwrite {
112                        arr[c] = KeyValuePair::new(key, value);
113                        return;
114                    }
115                    panic!("Key already exists in dictionary");
116                }
117
118                if let Some(free) = free {
119                    arr[free] = KeyValuePair::new(key, value);
120                    return;
121                }
122
123                // Upgrade to dictionary
124                let mut new_dic = Self::upgrade_to_dictionary(std::mem::take(arr));
125                new_dic.insert(key, value);
126                self.data = Data::Dictionary(new_dic);
127            }
128            DataKind::Dictionary => {
129                let Data::Dictionary(dic) = &mut self.data else { unreachable!() };
130                if overwrite {
131                    dic.insert(key, value);
132                } else {
133                    if dic.contains_key(&key) {
134                        panic!("An item with the same key has already been added.");
135                    }
136                    dic.insert(key, value);
137                }
138            }
139            DataKind::Key => {
140                // We have a single element, check if we should update the value.
141                let same = matches!(&self.data, Data::Key(data) if *data == key);
142                if same && overwrite {
143                    self.value = value;
144
145                    return;
146                }
147                // If we do not replace it, upgrade to array.
148                let Data::Key(data) = std::mem::replace(&mut self.data, Data::Null) else { unreachable!() };
149                let mut arr = Self::new_array();
150                arr[0] = KeyValuePair::new(data, std::mem::take(&mut self.value));
151                arr[1] = KeyValuePair::new(key, value);
152                self.data = Data::Array(arr);
153            }
154        }
155    }
156
157    /// Adds an entry.
158    ///
159    /// Panics when the small array or the dictionary has the key already.
160    /// As in the original, a dictionary that holds one entry in place does
161    /// not test for it.
162    pub fn add(&mut self, key: TKey, value: TValue) {
163        self.set_core(key, value, false)
164    }
165
166    /// Adds an entry or replaces its value.
167    pub fn set(&mut self, key: TKey, value: TValue) {
168        self.set_core(key, value, true)
169    }
170
171    /// The value of a key (the getter of the indexer).
172    ///
173    /// Panics when the dictionary does not have the key.
174    pub fn get(&self, key: &TKey) -> &TValue {
175        match self.try_get_value(key) {
176            Some(rv) => rv,
177            None => throw_key_not_found(),
178        }
179    }
180
181    pub fn remove(&mut self, key: &TKey) -> bool {
182        match self.kind() {
183            DataKind::Key => {
184                let same = matches!(&self.data, Data::Key(data) if data == key);
185                if same {
186                    self.data = Data::Null;
187                    self.value = TValue::default();
188                    return true;
189                }
190
191                false
192            }
193            DataKind::Array => {
194                let Data::Array(arr) = &mut self.data else { unreachable!() };
195                for entry in arr.iter_mut() {
196                    if entry.key.as_ref() == Some(key) {
197                        *entry = KeyValuePair::default();
198                        return true;
199                    }
200                }
201
202                false
203            }
204            DataKind::Dictionary => {
205                let Data::Dictionary(dic) = &mut self.data else { unreachable!() };
206                dic.remove(key).is_some()
207            }
208            DataKind::Null => false,
209        }
210    }
211
212    /// Removes every entry.
213    ///
214    /// As in the original, the value of an entry that is held in place is
215    /// kept and becomes the value of the next key that
216    /// [`get_value_ref_or_add_default`](Self::get_value_ref_or_add_default)
217    /// adds in place.
218    pub fn clear(&mut self) {
219        match self.kind() {
220            DataKind::Null => {}
221            DataKind::Array => {
222                let Data::Array(arr) = &mut self.data else { unreachable!() };
223                for entry in arr.iter_mut() {
224                    *entry = KeyValuePair::default();
225                }
226            }
227            DataKind::Dictionary => {
228                let Data::Dictionary(dic) = &mut self.data else { unreachable!() };
229                dic.clear();
230            }
231            DataKind::Key => self.data = Data::Null,
232        }
233    }
234
235    pub fn has_entries(&self) -> bool {
236        !matches!(self.data, Data::Null)
237    }
238
239    pub fn try_get_value(&self, key: &TKey) -> Option<&TValue> {
240        match &self.data {
241            Data::Key(data) => {
242                if data == key {
243                    Some(&self.value)
244                } else {
245                    None
246                }
247            }
248            Data::Array(arr) => arr.iter().find(|entry| entry.key.as_ref() == Some(key)).map(|entry| &entry.value),
249            Data::Dictionary(dic) => dic.get(key),
250            Data::Null => None,
251        }
252    }
253
254    /// A reference to the value of a key, or `None` (the original's null
255    /// reference) when the dictionary does not have the key.
256    pub fn get_value_ref_or_null_ref(&mut self, key: &TKey) -> Option<&mut TValue> {
257        match self.kind() {
258            DataKind::Key => {
259                let same = matches!(&self.data, Data::Key(data) if data == key);
260                if same {
261                    Some(&mut self.value)
262                } else {
263                    None
264                }
265            }
266            DataKind::Array => {
267                let Data::Array(arr) = &mut self.data else { unreachable!() };
268                arr.iter_mut().find(|entry| entry.key.as_ref() == Some(key)).map(|entry| &mut entry.value)
269            }
270            DataKind::Dictionary => {
271                let Data::Dictionary(dic) = &mut self.data else { unreachable!() };
272                dic.get_mut(key)
273            }
274            DataKind::Null => None,
275        }
276    }
277
278    /// A reference to the value of a key, which is added with the default
279    /// value when the dictionary does not have it, and whether it existed.
280    pub fn get_value_ref_or_add_default(&mut self, key: TKey) -> (&mut TValue, bool) {
281        match self.kind() {
282            DataKind::Null => {
283                self.data = Data::Key(key);
284                (&mut self.value, false)
285            }
286            // Single element
287            DataKind::Key => {
288                let same = matches!(&self.data, Data::Key(data) if *data == key);
289                if same {
290                    return (&mut self.value, true);
291                }
292
293                // This is a second element, convert to array
294                // We have a single element, upgrade to array
295                let Data::Key(data) = std::mem::replace(&mut self.data, Data::Null) else { unreachable!() };
296                let mut arr = Self::new_array();
297                arr[0] = KeyValuePair::new(data, std::mem::take(&mut self.value));
298                arr[1] = KeyValuePair::new(key, TValue::default());
299                self.data = Data::Array(arr);
300                let Data::Array(arr) = &mut self.data else { unreachable!() };
301                (&mut arr[1].value, false)
302            }
303            // Small array
304            DataKind::Array => {
305                // Try to find the element and look for the first free slot while we are at it
306                let mut free: Option<usize> = None;
307                let mut existing: Option<usize> = None;
308                if let Data::Array(arr) = &self.data {
309                    for (c, entry) in arr.iter().enumerate() {
310                        if entry.key.as_ref() == Some(&key) {
311                            existing = Some(c);
312                            break;
313                        } else if free.is_none() && entry.key.is_none() {
314                            free = Some(c);
315                        }
316                    }
317                }
318
319                if let Some(c) = existing {
320                    let Data::Array(arr) = &mut self.data else { unreachable!() };
321                    return (&mut arr[c].value, true);
322                }
323
324                // There is a free slot, use it
325                if let Some(free) = free {
326                    let Data::Array(arr) = &mut self.data else { unreachable!() };
327                    arr[free] = KeyValuePair::new(key, TValue::default());
328                    return (&mut arr[free].value, false);
329                }
330
331                // Upgrade to dictionary
332                let Data::Array(arr) = std::mem::replace(&mut self.data, Data::Null) else { unreachable!() };
333                self.data = Data::Dictionary(Self::upgrade_to_dictionary(arr));
334                Self::dictionary_value_ref_or_add_default(&mut self.data, key)
335            }
336            DataKind::Dictionary => Self::dictionary_value_ref_or_add_default(&mut self.data, key),
337        }
338    }
339
340    fn dictionary_value_ref_or_add_default(data: &mut Data<TKey, TValue>, key: TKey) -> (&mut TValue, bool) {
341        let Data::Dictionary(dic) = data else { unreachable!() };
342        match dic.entry(key) {
343            Entry::Occupied(entry) => (entry.into_mut(), true),
344            Entry::Vacant(entry) => (entry.insert(TValue::default()), false),
345        }
346    }
347
348    /// Removes an entry and returns its value.
349    ///
350    /// As in the original, an entry of a dictionary that has grown into a
351    /// hash map is removed without its value being returned.
352    pub fn try_get_and_remove_value(&mut self, key: &TKey) -> Option<TValue> {
353        match self.kind() {
354            DataKind::Key => {
355                let same = matches!(&self.data, Data::Key(data) if data == key);
356                if same {
357                    let value = std::mem::take(&mut self.value);
358                    self.data = Data::Null;
359                    return Some(value);
360                }
361
362                None
363            }
364            DataKind::Array => {
365                let Data::Array(arr) = &mut self.data else { unreachable!() };
366                for entry in arr.iter_mut() {
367                    if entry.key.as_ref() == Some(key) {
368                        let removed = std::mem::take(entry);
369                        return Some(removed.value);
370                    }
371                }
372
373                None
374            }
375            DataKind::Dictionary => {
376                let Data::Dictionary(dic) = &mut self.data else { unreachable!() };
377                dic.remove(key);
378
379                None
380            }
381            DataKind::Null => None,
382        }
383    }
384
385    /// Removes an entry and returns its value.
386    ///
387    /// Panics when [`try_get_and_remove_value`](Self::try_get_and_remove_value)
388    /// returns nothing.
389    pub fn get_and_remove(&mut self, key: &TKey) -> TValue {
390        match self.try_get_and_remove_value(key) {
391            Some(v) => v,
392            None => throw_key_not_found(),
393        }
394    }
395
396    pub fn get_enumerator(&self) -> InlineDictionaryEnumerator<'_, TKey, TValue> {
397        InlineDictionaryEnumerator::new(self)
398    }
399}
400
401impl<'a, TKey: Clone + Eq + Hash, TValue: Default> IntoIterator for &'a InlineDictionary<TKey, TValue> {
402    type Item = (&'a TKey, &'a TValue);
403    type IntoIter = InlineDictionaryEnumerator<'a, TKey, TValue>;
404
405    fn into_iter(self) -> Self::IntoIter {
406        self.get_enumerator()
407    }
408}
409
410fn throw_key_not_found() -> ! {
411    panic!("The given key was not present in the dictionary.")
412}
413
414#[derive(Clone, Copy, PartialEq, Eq)]
415enum EnumeratorType {
416    Empty,
417    Single,
418    Array,
419    Dictionary,
420}
421
422/// The enumerator of an [`InlineDictionary`] (the original's nested
423/// `Enumerator`). It is an `Iterator` as well.
424pub struct InlineDictionaryEnumerator<'a, TKey, TValue> {
425    dictionary: Option<&'a HashMap<TKey, TValue>>,
426    inner: Option<hash_map::Iter<'a, TKey, TValue>>,
427    inner_current: Option<(&'a TKey, &'a TValue)>,
428    arr: Option<&'a [KeyValuePair<TKey, TValue>]>,
429    first: Option<(&'a TKey, &'a TValue)>,
430    index: i32,
431    type_: EnumeratorType,
432}
433
434impl<'a, TKey, TValue> InlineDictionaryEnumerator<'a, TKey, TValue> {
435    pub fn new(parent: &'a InlineDictionary<TKey, TValue>) -> Self {
436        let mut result = Self {
437            dictionary: None,
438            inner: None,
439            inner_current: None,
440            arr: None,
441            first: None,
442            index: -1,
443            type_: EnumeratorType::Empty,
444        };
445        match &parent.data {
446            Data::Dictionary(inner) => {
447                result.dictionary = Some(inner);
448                result.inner = Some(inner.iter());
449                result.type_ = EnumeratorType::Dictionary;
450            }
451            Data::Array(arr) => {
452                result.type_ = EnumeratorType::Array;
453                result.arr = Some(arr.as_slice());
454            }
455            Data::Key(key) => {
456                result.type_ = EnumeratorType::Single;
457                result.first = Some((key, &parent.value));
458            }
459            Data::Null => result.type_ = EnumeratorType::Empty,
460        }
461        result
462    }
463
464    pub fn move_next(&mut self) -> bool {
465        match self.type_ {
466            EnumeratorType::Single => {
467                if self.index != -1 {
468                    return false;
469                }
470                self.index = 0;
471                true
472            }
473            EnumeratorType::Array => {
474                let Some(arr) = self.arr else { return false };
475                let mut next = self.index + 1;
476                while (next as usize) < arr.len() {
477                    if arr[next as usize].key.is_some() {
478                        self.index = next;
479                        return true;
480                    }
481                    next += 1;
482                }
483                false
484            }
485            EnumeratorType::Dictionary => {
486                self.inner_current = match &mut self.inner {
487                    Some(inner) => inner.next(),
488                    None => None,
489                };
490                self.inner_current.is_some()
491            }
492            EnumeratorType::Empty => false,
493        }
494    }
495
496    pub fn reset(&mut self) {
497        self.index = -1;
498        if self.type_ == EnumeratorType::Dictionary {
499            self.inner = self.dictionary.map(|dictionary| dictionary.iter());
500            self.inner_current = None;
501        }
502    }
503
504    /// The current entry.
505    ///
506    /// Panics when the enumerator is not positioned on an entry.
507    pub fn current(&self) -> (&'a TKey, &'a TValue) {
508        let current = match self.type_ {
509            EnumeratorType::Single => self.first,
510            EnumeratorType::Array => match self.arr {
511                Some(arr) if self.index >= 0 && (self.index as usize) < arr.len() => {
512                    let entry = &arr[self.index as usize];
513                    entry.key.as_ref().map(|key| (key, &entry.value))
514                }
515                _ => None,
516            },
517            EnumeratorType::Dictionary => self.inner_current,
518            EnumeratorType::Empty => None,
519        };
520        match current {
521            Some(current) => current,
522            None => panic!("Operation is not valid due to the current state of the object."),
523        }
524    }
525
526    pub fn dispose(&mut self) {}
527}
528
529impl<'a, TKey, TValue> Iterator for InlineDictionaryEnumerator<'a, TKey, TValue> {
530    type Item = (&'a TKey, &'a TValue);
531
532    fn next(&mut self) -> Option<Self::Item> {
533        if self.move_next() {
534            Some(self.current())
535        } else {
536            None
537        }
538    }
539}
540
541#[cfg(test)]
542mod tests {
543    use super::*;
544
545    fn entries(dic: &InlineDictionary<&'static str, i32>) -> Vec<(&'static str, i32)> {
546        dic.get_enumerator().map(|(key, value)| (*key, *value)).collect()
547    }
548
549    #[test]
550    fn set_twice_with_single_item_works() {
551        let mut dic = InlineDictionary::<&'static str, i32>::new();
552        dic.set("foo", 1);
553        assert_eq!(1, *dic.get(&"foo"));
554
555        dic.set("foo", 2);
556        assert_eq!(2, *dic.get(&"foo"));
557    }
558
559    #[test]
560    fn enumeration_after_add_with_internal_array_works() {
561        let mut dic = InlineDictionary::<&'static str, i32>::new();
562        dic.add("foo", 1);
563        dic.add("bar", 2);
564        dic.add("baz", 3);
565
566        assert_eq!(vec![("foo", 1), ("bar", 2), ("baz", 3)], entries(&dic));
567    }
568
569    #[test]
570    fn enumeration_after_remove_with_internal_array_works() {
571        let mut dic = InlineDictionary::<&'static str, i32>::new();
572        dic.add("foo", 1);
573        dic.add("bar", 2);
574        dic.add("baz", 3);
575
576        assert_eq!(vec![("foo", 1), ("bar", 2), ("baz", 3)], entries(&dic));
577
578        dic.remove(&"bar");
579
580        assert_eq!(vec![("foo", 1), ("baz", 3)], entries(&dic));
581    }
582
583    // The tests below are not from upstream.
584
585    #[test]
586    fn grows_into_a_dictionary_and_keeps_its_entries() {
587        let names = ["a", "b", "c", "d", "e", "f", "g", "h"];
588        let mut dic = InlineDictionary::<&'static str, i32>::new();
589        assert!(!dic.has_entries());
590        for (index, name) in names.iter().enumerate() {
591            dic.add(*name, index as i32);
592        }
593        assert!(dic.has_entries());
594
595        for (index, name) in names.iter().enumerate() {
596            assert_eq!(Some(&(index as i32)), dic.try_get_value(name));
597        }
598        assert_eq!(None, dic.try_get_value(&"z"));
599
600        let mut all = entries(&dic);
601        all.sort();
602        assert_eq!(names.len(), all.len());
603        assert_eq!(("a", 0), all[0]);
604
605        assert!(dic.remove(&"a"));
606        assert!(!dic.remove(&"a"));
607        dic.clear();
608        assert_eq!(None, dic.try_get_value(&"b"));
609    }
610
611    #[test]
612    fn value_references_add_and_find_entries_in_every_state() {
613        let mut dic = InlineDictionary::<i32, i32>::new();
614        for key in 0..10 {
615            assert!(dic.get_value_ref_or_null_ref(&key).is_none());
616            let (value, exists) = dic.get_value_ref_or_add_default(key);
617            assert!(!exists);
618            assert_eq!(0, *value);
619            *value = key * 10;
620
621            let (value, exists) = dic.get_value_ref_or_add_default(key);
622            assert!(exists);
623            assert_eq!(key * 10, *value);
624        }
625
626        for key in 0..10 {
627            assert_eq!(Some(&mut (key * 10)), dic.get_value_ref_or_null_ref(&key));
628        }
629    }
630
631    #[test]
632    fn get_and_remove_returns_the_value_of_an_entry_held_in_place_or_in_the_array() {
633        let mut dic = InlineDictionary::<i32, i32>::new();
634        dic.add(1, 10);
635        assert_eq!(10, dic.get_and_remove(&1));
636        assert!(!dic.has_entries());
637
638        dic.add(1, 10);
639        dic.add(2, 20);
640        assert_eq!(Some(20), dic.try_get_and_remove_value(&2));
641        assert_eq!(None, dic.try_get_and_remove_value(&2));
642        assert_eq!(Some(&10), dic.try_get_value(&1));
643    }
644
645    #[test]
646    #[should_panic(expected = "Key already exists in dictionary")]
647    fn add_throws_for_a_key_of_the_array() {
648        let mut dic = InlineDictionary::<i32, i32>::new();
649        dic.add(1, 10);
650        dic.add(2, 20);
651        dic.add(2, 21);
652    }
653
654    #[test]
655    #[should_panic(expected = "The given key was not present in the dictionary.")]
656    fn get_throws_for_a_missing_key() {
657        let dic = InlineDictionary::<i32, i32>::new();
658        dic.get(&1);
659    }
660}
ferroui_base/utilities/small_dictionary.rs

ferroui_base/utilities/
small_dictionary.rs
