88 lines
2.9 KiB
Rust
88 lines
2.9 KiB
Rust
use std::fmt;
|
|
|
|
// Error type
|
|
struct SparseSetError;
|
|
|
|
#[derive(Debug, Copy, Clone)]
|
|
struct DenseItem<T> {
|
|
index: usize,
|
|
value: T
|
|
}
|
|
|
|
// 'sparse' is the sparse list tracking the indices of densely-stored items
|
|
// 'dense' is the dense list containing the actual items
|
|
// 'n' is the total number of densely-stored items
|
|
#[derive(Debug)]
|
|
struct SparseSet<'s, 'd, T> {
|
|
sparse: &'s mut [Option<usize>],
|
|
dense: &'d mut [Option<DenseItem<T>>],
|
|
n: usize
|
|
}
|
|
|
|
impl<'s, 'd, T> SparseSet<'s, 'd, T> {
|
|
// A new sparse set can be created with two mutable slices: one for the sparse and one for the dense slices
|
|
pub fn new(sparse_slice: &'s mut [Option<usize>], dense_slice: &'d mut [Option<DenseItem<T>>], n: usize) -> SparseSet<'s, 'd, T> {
|
|
SparseSet {
|
|
sparse: sparse_slice,
|
|
dense: dense_slice,
|
|
n: n
|
|
}
|
|
}
|
|
|
|
// Add an item to the set at a target sparse location
|
|
fn insert(&mut self, target_sparse_index: usize, value: T) {
|
|
// Create the item, first of all
|
|
let item = DenseItem {
|
|
index: target_sparse_index,
|
|
value: value
|
|
};
|
|
|
|
// Insert the item into the dense slice at index N
|
|
self.dense[self.n] = Some(item);
|
|
|
|
// Write N to the sparse slice at the target index
|
|
self.sparse[target_sparse_index] = Some(self.n);
|
|
|
|
// Increase N by one, lastly
|
|
self.n += 1;
|
|
}
|
|
|
|
// Remove an item at the supplied target index from the set
|
|
// Replaces the selected target with the last item in the dense vector
|
|
fn remove(&mut self, target_sparse_index: usize) -> Result<(), SparseSetError> {
|
|
// Get the last dense item and clear its former dense entry
|
|
let last_item = self.dense[self.n - 1].as_ref().unwrap();
|
|
let last_item_sparse_index = last_item.index;
|
|
self.dense[self.n - 1] = None;
|
|
|
|
// Replace the target dense item with the last dense item
|
|
let target_dense_index = self.sparse[target_sparse_index].unwrap();
|
|
self.dense[target_dense_index] = Some(last_item);
|
|
|
|
// Update the (former) last dense item's corresponding dense index key to point to its new location (where the target used to be)
|
|
self.sparse[last_item_sparse_index] = Some(target_dense_index);
|
|
|
|
// Clear the target's sparse entry
|
|
self.sparse[target_sparse_index] = None;
|
|
|
|
// Decrement N
|
|
self.n -= 1;
|
|
|
|
Ok(())
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
// Create the arrays for our sparse set
|
|
let mut dense_array: [Option<DenseItem<f32>>; 8] = [None; 8];
|
|
let mut sparse_array: [Option<usize>; 8] = [None; 8];
|
|
|
|
let mut test_set: SparseSet<f32> = SparseSet::new(&mut sparse_array, &mut dense_array, 0);
|
|
test_set.insert(0, 69.0);
|
|
test_set.insert(4, 420.0);
|
|
test_set.insert(7, 9001.0);
|
|
println!("{:?}", test_set);
|
|
test_set.remove(1);
|
|
println!("{:?}", test_set);
|
|
}
|