1 //! Densely numbered entity references as set keys. 2 3 use crate::keys::Keys; 4 use crate::EntityRef; 5 use core::marker::PhantomData; 6 use cranelift_bitset::CompoundBitSet; 7 8 /// A set of `K` for densely indexed entity references. 9 /// 10 /// The `EntitySet` data structure uses the dense index space to implement a set with a bitvector. 11 /// Like `SecondaryMap`, an `EntitySet` is used to associate secondary information with entities. 12 #[derive(Debug, Clone)] 13 pub struct EntitySet<K> 14 where 15 K: EntityRef, 16 { 17 bitset: CompoundBitSet, 18 unused: PhantomData<K>, 19 } 20 21 impl<K: EntityRef> Default for EntitySet<K> { 22 fn default() -> Self { 23 Self { 24 bitset: CompoundBitSet::default(), 25 unused: PhantomData, 26 } 27 } 28 } 29 30 /// Shared `EntitySet` implementation for all value types. 31 impl<K> EntitySet<K> 32 where 33 K: EntityRef, 34 { 35 /// Create a new empty set. 36 pub fn new() -> Self { 37 Self::default() 38 } 39 40 /// Creates a new empty set with the specified capacity. 41 pub fn with_capacity(capacity: usize) -> Self { 42 Self { 43 bitset: CompoundBitSet::with_capacity(capacity), 44 unused: PhantomData, 45 } 46 } 47 48 /// Get the element at `k` if it exists. 49 pub fn contains(&self, k: K) -> bool { 50 let index = k.index(); 51 self.bitset.contains(index) 52 } 53 54 /// Is this set completely empty? 55 pub fn is_empty(&self) -> bool { 56 self.bitset.is_empty() 57 } 58 59 /// Remove all entries from this set. 60 pub fn clear(&mut self) { 61 self.bitset.clear() 62 } 63 64 /// Iterate over all the keys in this set. 65 pub fn keys(&self) -> Keys<K> { 66 Keys::with_len(self.bitset.max().map_or(0, |x| x + 1)) 67 } 68 69 /// Insert the element at `k`. 70 pub fn insert(&mut self, k: K) -> bool { 71 let index = k.index(); 72 self.bitset.insert(index) 73 } 74 75 /// Removes and returns the entity from the set if it exists. 76 pub fn pop(&mut self) -> Option<K> { 77 let index = self.bitset.pop()?; 78 Some(K::new(index)) 79 } 80 } 81 82 #[cfg(test)] 83 mod tests { 84 use super::*; 85 use alloc::vec::Vec; 86 use core::u32; 87 88 // `EntityRef` impl for testing. 89 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] 90 struct E(u32); 91 92 impl EntityRef for E { 93 fn new(i: usize) -> Self { 94 E(i as u32) 95 } 96 fn index(self) -> usize { 97 self.0 as usize 98 } 99 } 100 101 #[test] 102 fn basic() { 103 let r0 = E(0); 104 let r1 = E(1); 105 let r2 = E(2); 106 let mut m = EntitySet::new(); 107 108 let v: Vec<E> = m.keys().collect(); 109 assert_eq!(v, []); 110 assert!(m.is_empty()); 111 112 m.insert(r2); 113 m.insert(r1); 114 115 assert!(!m.contains(r0)); 116 assert!(m.contains(r1)); 117 assert!(m.contains(r2)); 118 assert!(!m.contains(E(3))); 119 assert!(!m.is_empty()); 120 121 let v: Vec<E> = m.keys().collect(); 122 assert_eq!(v, [r0, r1, r2]); 123 124 assert!(!m.contains(E(3))); 125 assert!(!m.contains(E(4))); 126 assert!(!m.contains(E(8))); 127 assert!(!m.contains(E(15))); 128 assert!(!m.contains(E(19))); 129 130 m.insert(E(8)); 131 m.insert(E(15)); 132 assert!(!m.contains(E(3))); 133 assert!(!m.contains(E(4))); 134 assert!(m.contains(E(8))); 135 assert!(!m.contains(E(9))); 136 assert!(!m.contains(E(14))); 137 assert!(m.contains(E(15))); 138 assert!(!m.contains(E(16))); 139 assert!(!m.contains(E(19))); 140 assert!(!m.contains(E(20))); 141 assert!(!m.contains(E(u32::MAX))); 142 143 m.clear(); 144 assert!(m.is_empty()); 145 } 146 147 #[test] 148 fn pop_ordered() { 149 let r0 = E(0); 150 let r1 = E(1); 151 let r2 = E(2); 152 let mut m = EntitySet::new(); 153 m.insert(r0); 154 m.insert(r1); 155 m.insert(r2); 156 157 assert_eq!(r2, m.pop().unwrap()); 158 assert_eq!(r1, m.pop().unwrap()); 159 assert_eq!(r0, m.pop().unwrap()); 160 assert!(m.pop().is_none()); 161 assert!(m.pop().is_none()); 162 } 163 164 #[test] 165 fn pop_unordered() { 166 let mut blocks = [ 167 E(0), 168 E(1), 169 E(6), 170 E(7), 171 E(5), 172 E(9), 173 E(10), 174 E(2), 175 E(3), 176 E(11), 177 E(12), 178 ]; 179 180 let mut m = EntitySet::new(); 181 for &block in &blocks { 182 m.insert(block); 183 } 184 assert_eq!(m.bitset.max(), Some(12)); 185 blocks.sort(); 186 187 for &block in blocks.iter().rev() { 188 assert_eq!(block, m.pop().unwrap()); 189 } 190 191 assert!(m.is_empty()); 192 } 193 } 194