datex_core/utils/
freemap.rs

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

datex_core/utils/
freemap.rs
