datex_core/utils/
freemap.rs

1use crate::collections::HashMap;
2use crate::collections::hash_map::{Iter, IterMut};
3use crate::stdlib::vec::Vec;
4use core::prelude::rust_2024::*;
5
6pub trait NextKey: Copy + Eq + core::hash::Hash + Default {
7    fn next_key(&mut self) -> Self;
8}
9
10/// A HashMap that reuses freed IDs for new entries.
11pub struct FreeHashMap<K: NextKey, T> {
12    entries: HashMap<K, T>,
13    free_list: Vec<K>,
14    next_id: K,
15}
16
17impl<K: NextKey, T> Default for FreeHashMap<K, T> {
18    fn default() -> Self {
19        Self::new()
20    }
21}
22
23impl<K: NextKey, T> FreeHashMap<K, T> {
24    pub fn new() -> Self {
25        Self {
26            entries: HashMap::new(),
27            free_list: Vec::new(),
28            next_id: K::default(),
29        }
30    }
31
32    pub fn clear(&mut self) {
33        self.entries.clear();
34        self.free_list.clear();
35        self.next_id = K::default();
36    }
37
38    /// Adds a new entry and returns its unique ID.
39    pub fn add(&mut self, value: T) -> K {
40        if let Some(id) = self.free_list.pop() {
41            self.entries.insert(id, value);
42            id
43        } else {
44            let id = self.next_id.next_key();
45            self.entries.insert(id, value);
46            id
47        }
48    }
49
50    /// Checks if a value exists in the map.
51    pub fn has_value(&self, value: &T) -> bool
52    where
53        T: PartialEq,
54    {
55        self.entries.values().any(|v| v == value)
56    }
57
58    /// Returns the ID of a given value, if it exists.
59    pub fn get_id(&self, value: &T) -> Option<K>
60    where
61        T: PartialEq,
62    {
63        for (k, v) in &self.entries {
64            if v == value {
65                return Some(*k);
66            }
67        }
68        None
69    }
70
71    /// Returns the number of entries in the map.
72    pub fn len(&self) -> usize {
73        self.entries.len()
74    }
75
76    pub fn is_empty(&self) -> bool {
77        self.entries.is_empty()
78    }
79
80    /// Checks if an entry with the given ID exists.
81    pub fn has(&self, id: &K) -> bool {
82        self.entries.contains_key(id)
83    }
84
85    /// Removes the entry with the given ID, if it exists.
86    pub fn remove(&mut self, id: K) -> Option<T> {
87        let cur = self.entries.remove(&id);
88        if cur.is_some() {
89            self.free_list.push(id);
90        }
91        cur
92    }
93
94    /// Get a reference to an entry.
95    pub fn get(&self, id: &K) -> Option<&T> {
96        self.entries.get(id)
97    }
98
99    /// Get a mutable reference to an entry.
100    pub fn get_mut(&mut self, id: &K) -> Option<&mut T> {
101        self.entries.get_mut(id)
102    }
103
104    pub fn values(&self) -> impl Iterator<Item = &T> {
105        self.entries.values()
106    }
107    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut T> {
108        self.entries.values_mut()
109    }
110    pub fn keys(&self) -> impl Iterator<Item = &K> {
111        self.entries.keys()
112    }
113
114    pub fn iter(&self) -> Iter<'_, K, T> {
115        self.entries.iter()
116    }
117
118    pub fn iter_mut(&mut self) -> IterMut<'_, K, T> {
119        self.entries.iter_mut()
120    }
121}
122
123impl<K: NextKey, T> IntoIterator for FreeHashMap<K, T> {
124    type Item = (K, T);
125    type IntoIter = crate::collections::hash_map::IntoIter<K, T>;
126
127    fn into_iter(self) -> Self::IntoIter {
128        self.entries.into_iter()
129    }
130}
131
132impl<'a, K: NextKey, T> IntoIterator for &'a FreeHashMap<K, T> {
133    type Item = (&'a K, &'a T);
134    type IntoIter = Iter<'a, K, T>;
135
136    fn into_iter(self) -> Self::IntoIter {
137        self.entries.iter()
138    }
139}
140
141impl<'a, K: NextKey, T> IntoIterator for &'a mut FreeHashMap<K, T> {
142    type Item = (&'a K, &'a mut T);
143    type IntoIter = IterMut<'a, K, T>;
144
145    fn into_iter(self) -> Self::IntoIter {
146        self.entries.iter_mut()
147    }
148}
149
150impl NextKey for u32 {
151    fn next_key(&mut self) -> Self {
152        let current = *self;
153        *self = self.wrapping_add(1);
154        current
155    }
156}
datex_core/utils/freemap.rs

datex_core/utils/
freemap.rs
