use crate::map::SecondaryMap;
use crate::EntityRef;
use alloc::vec::Vec;
use core::mem;
use core::slice;
use core::u32;
pub trait SparseMapValue<K> {
fn key(&self) -> K;
}
pub struct SparseMap<K, V>
where
K: EntityRef,
V: SparseMapValue<K>,
{
sparse: SecondaryMap<K, u32>,
dense: Vec<V>,
}
impl<K, V> SparseMap<K, V>
where
K: EntityRef,
V: SparseMapValue<K>,
{
pub fn new() -> Self {
Self {
sparse: SecondaryMap::new(),
dense: Vec::new(),
}
}
pub fn len(&self) -> usize {
self.dense.len()
}
pub fn is_empty(&self) -> bool {
self.dense.is_empty()
}
pub fn clear(&mut self) {
self.dense.clear();
}
pub fn get(&self, key: K) -> Option<&V> {
if let Some(idx) = self.sparse.get(key).cloned() {
if let Some(entry) = self.dense.get(idx as usize) {
if entry.key() == key {
return Some(entry);
}
}
}
None
}
pub fn get_mut(&mut self, key: K) -> Option<&mut V> {
if let Some(idx) = self.sparse.get(key).cloned() {
if let Some(entry) = self.dense.get_mut(idx as usize) {
if entry.key() == key {
return Some(entry);
}
}
}
None
}
fn index(&self, key: K) -> Option<usize> {
if let Some(idx) = self.sparse.get(key).cloned() {
let idx = idx as usize;
if let Some(entry) = self.dense.get(idx) {
if entry.key() == key {
return Some(idx);
}
}
}
None
}
pub fn contains_key(&self, key: K) -> bool {
self.get(key).is_some()
}
pub fn insert(&mut self, value: V) -> Option<V> {
let key = value.key();
if let Some(entry) = self.get_mut(key) {
return Some(mem::replace(entry, value));
}
let idx = self.dense.len();
debug_assert!(idx <= u32::MAX as usize, "SparseMap overflow");
self.dense.push(value);
self.sparse[key] = idx as u32;
None
}
pub fn remove(&mut self, key: K) -> Option<V> {
if let Some(idx) = self.index(key) {
let back = self.dense.pop().unwrap();
if idx == self.dense.len() {
return Some(back);
}
self.sparse[back.key()] = idx as u32;
return Some(mem::replace(&mut self.dense[idx], back));
}
None
}
pub fn pop(&mut self) -> Option<V> {
self.dense.pop()
}
pub fn values(&self) -> slice::Iter<V> {
self.dense.iter()
}
pub fn as_slice(&self) -> &[V] {
self.dense.as_slice()
}
}
impl<'a, K, V> IntoIterator for &'a SparseMap<K, V>
where
K: EntityRef,
V: SparseMapValue<K>,
{
type Item = &'a V;
type IntoIter = slice::Iter<'a, V>;
fn into_iter(self) -> Self::IntoIter {
self.values()
}
}
impl<T> SparseMapValue<T> for T
where
T: EntityRef,
{
fn key(&self) -> Self {
*self
}
}
pub type SparseSet<T> = SparseMap<T, T>;
#[cfg(test)]
mod tests {
use super::*;
use crate::EntityRef;
#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Inst(u32);
entity_impl!(Inst, "inst");
#[derive(PartialEq, Eq, Debug)]
struct Obj(Inst, &'static str);
impl SparseMapValue<Inst> for Obj {
fn key(&self) -> Inst {
self.0
}
}
#[test]
fn empty_immutable_map() {
let i1 = Inst::new(1);
let map: SparseMap<Inst, Obj> = SparseMap::new();
assert!(map.is_empty());
assert_eq!(map.len(), 0);
assert_eq!(map.get(i1), None);
assert_eq!(map.values().count(), 0);
}
#[test]
fn single_entry() {
let i0 = Inst::new(0);
let i1 = Inst::new(1);
let i2 = Inst::new(2);
let mut map = SparseMap::new();
assert!(map.is_empty());
assert_eq!(map.len(), 0);
assert_eq!(map.get(i1), None);
assert_eq!(map.get_mut(i1), None);
assert_eq!(map.remove(i1), None);
assert_eq!(map.insert(Obj(i1, "hi")), None);
assert!(!map.is_empty());
assert_eq!(map.len(), 1);
assert_eq!(map.get(i0), None);
assert_eq!(map.get(i1), Some(&Obj(i1, "hi")));
assert_eq!(map.get(i2), None);
assert_eq!(map.get_mut(i0), None);
assert_eq!(map.get_mut(i1), Some(&mut Obj(i1, "hi")));
assert_eq!(map.get_mut(i2), None);
assert_eq!(map.remove(i0), None);
assert_eq!(map.remove(i2), None);
assert_eq!(map.remove(i1), Some(Obj(i1, "hi")));
assert_eq!(map.len(), 0);
assert_eq!(map.get(i1), None);
assert_eq!(map.get_mut(i1), None);
assert_eq!(map.remove(i0), None);
assert_eq!(map.remove(i1), None);
assert_eq!(map.remove(i2), None);
}
#[test]
fn multiple_entries() {
let i0 = Inst::new(0);
let i1 = Inst::new(1);
let i2 = Inst::new(2);
let i3 = Inst::new(3);
let mut map = SparseMap::new();
assert_eq!(map.insert(Obj(i2, "foo")), None);
assert_eq!(map.insert(Obj(i1, "bar")), None);
assert_eq!(map.insert(Obj(i0, "baz")), None);
assert_eq!(
map.values().map(|obj| obj.1).collect::<Vec<_>>(),
["foo", "bar", "baz"]
);
assert_eq!(map.len(), 3);
assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
assert_eq!(map.get(i1), Some(&Obj(i1, "bar")));
assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
assert_eq!(map.get(i3), None);
assert_eq!(map.remove(i1), Some(Obj(i1, "bar")));
assert_eq!(map.len(), 2);
assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
assert_eq!(map.get(i1), None);
assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
assert_eq!(map.get(i3), None);
assert_eq!(map.insert(Obj(i1, "barbar")), None);
assert_eq!(map.len(), 3);
assert_eq!(map.get(i0), Some(&Obj(i0, "baz")));
assert_eq!(map.get(i1), Some(&Obj(i1, "barbar")));
assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
assert_eq!(map.get(i3), None);
assert_eq!(map.insert(Obj(i0, "bazbaz")), Some(Obj(i0, "baz")));
assert_eq!(map.len(), 3);
assert_eq!(map.get(i0), Some(&Obj(i0, "bazbaz")));
assert_eq!(map.get(i1), Some(&Obj(i1, "barbar")));
assert_eq!(map.get(i2), Some(&Obj(i2, "foo")));
assert_eq!(map.get(i3), None);
let mut v = Vec::new();
for i in &map {
v.push(i.1);
}
assert_eq!(v.len(), map.len());
}
#[test]
fn entity_set() {
let i0 = Inst::new(0);
let i1 = Inst::new(1);
let mut set = SparseSet::new();
assert_eq!(set.insert(i0), None);
assert_eq!(set.insert(i0), Some(i0));
assert_eq!(set.insert(i1), None);
assert_eq!(set.get(i0), Some(&i0));
assert_eq!(set.get(i1), Some(&i1));
}
}