[−][src]Struct granite::SparseStorage
A wrapper around a list-like storage type which considerably improves performance when removing elements.
Sparse storage with element type E
wraps a normal storage which stores Slot<E>
, which is a tagged union storing either an element or a "hole". Those holes count as regular elements, but trying to get their value produces a panic, since the storage provides E
as its element type, rather than Slot<E>
. This behavior does not depend on whether checked or unchecked get
/get_mut
methods are used - all of those are guaranteed to panic upon fetching a hole.
When remove_and_shiftfix
is called, elements are not actually shifted, but the element is replaced with a hole. If the elements of the storage store indicies towards other elements of the storage, they don't get invalidated.
Example
use granite::{ ListStorage, // ListStorage trait, for interfacing with the sparse // storage's generic list-like storage capabilities SparseVec, // A sparse storage type definition for Vec DummyMoveFix, // Utility struct to have elements which can be removed with // a move fix but which actually don't react to the hooks at all. }; // Use the new() method from the Storage trait to create a sparse storage: let mut storage = SparseVec::<DummyMoveFix<u32>>::new(); // Or, the with_capacity() method to preallocate some space for the elements: let mut storage = SparseVec::<DummyMoveFix<u32>>::with_capacity(32); // Let's put some elements in! storage.add(0.into()); storage.add(1.into()); storage.add(2.into()); // Now that we have some elements, we can remove the one in the // middle to create a hole, and see what sparse storage is about. let val = storage.remove_and_shiftfix(1); assert_eq!(val, 1); // Let's check the length of the storage: let len = storage.len(); // It hasn't changed, because the element from the wrapped storage wasn't actually removed... assert_eq!(len, 3); // ...but instead dropped and turned into a hole: let num_holes = storage.num_holes(); assert_eq!(num_holes, 1); // Let's remove yet another element: let val = storage.remove_and_shiftfix(2); assert_eq!(val, 2); // It's the third element (index 2), because removing the // previous one did not shift the elements from their indicies. // The previous hole is still there, and we have a new one: let num_holes = storage.num_holes(); assert_eq!(num_holes, 2); // Let's remove the holes from the storage entirely: storage.defragment(); // We could've called defragment_and_fix, but since we have // the dummy move fix wrapper, that wouldn't make a difference. // The holes are gone! let num_holes = storage.num_holes(); assert_eq!(num_holes, 0); // We can also use the is_dense() method to check for this: assert!(storage.is_dense()); // The method is specific to sparse storage and is not a part of the Storage trait.
Implementations
impl<E, S> SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
pub fn defragment(&mut self)
[src]
Removes all holes from the sparse storage, without fixing elements' indicies. This is an expensive operation and should only be called if is_dense
is false
to avoid needless overhead.
pub fn defragment_and_fix(&mut self) where
E: MoveFix,
[src]
E: MoveFix,
Removes all holes from the sparse storage, fixing elements' indicies. This is an expensive operation and should only be called if is_dense
is false
to avoid needless overhead.
pub fn into_inner(self) -> S
[src]
Consumes the sparse storage and returns its inner storage.
pub fn num_holes(&self) -> usize
[src]
Returns the number of holes in the storage. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.
pub fn is_dense(&self) -> bool
[src]
Returns true
if there are no holes in the storage, false
otherwise. This operation returns immediately instead of looping through the entire storage, since the sparse storage automatically tracks the number of holes it creates and destroys.
Trait Implementations
impl<E: Clone, S: Clone> Clone for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
fn clone(&self) -> SparseStorage<E, S>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<E: Copy, S: Copy> Copy for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
impl<E: Debug, S: Debug> Debug for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
impl<E: Default, S: Default> Default for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
fn default() -> SparseStorage<E, S>
[src]
impl<E: Eq, S: Eq> Eq for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
impl<E, S> ListStorage for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
type Element = E
The type of values in the container.
fn with_capacity(capacity: usize) -> Self
[src]
fn insert(&mut self, index: usize, element: Self::Element)
[src]
fn remove(&mut self, index: usize) -> Self::Element
[src]
fn len(&self) -> usize
[src]
unsafe fn get_unchecked(&self, index: usize) -> &Self::Element
[src]
unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element
[src]
fn get(&self, index: usize) -> Option<&Self::Element>
[src]
fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>
[src]
fn new() -> Self
[src]
fn push(&mut self, element: Self::Element)
[src]
fn pop(&mut self) -> Option<Self::Element>
[src]
fn capacity(&self) -> usize
[src]
fn reserve(&mut self, additional: usize)
[src]
fn shrink_to_fit(&mut self)
[src]
fn truncate(&mut self, len: usize)
[src]
fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element) where
Self::Element: MoveFix,
[src]
Self::Element: MoveFix,
fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element where
Self::Element: MoveFix,
[src]
Self::Element: MoveFix,
fn add(&mut self, element: Self::Element) -> usize
[src]
fn is_empty(&self) -> bool
[src]
impl<E: PartialEq, S: PartialEq> PartialEq<SparseStorage<E, S>> for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
fn eq(&self, other: &SparseStorage<E, S>) -> bool
[src]
fn ne(&self, other: &SparseStorage<E, S>) -> bool
[src]
impl<E, S> StructuralEq for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
impl<E, S> StructuralPartialEq for SparseStorage<E, S> where
S: ListStorage<Element = Slot<E>>,
[src]
S: ListStorage<Element = Slot<E>>,
Auto Trait Implementations
impl<E, S> RefUnwindSafe for SparseStorage<E, S> where
S: RefUnwindSafe,
S: RefUnwindSafe,
impl<E, S> Send for SparseStorage<E, S> where
S: Send,
S: Send,
impl<E, S> Sync for SparseStorage<E, S> where
S: Sync,
S: Sync,
impl<E, S> Unpin for SparseStorage<E, S> where
S: Unpin,
S: Unpin,
impl<E, S> UnwindSafe for SparseStorage<E, S> where
S: UnwindSafe,
S: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> Slottable for T where
T: Copy,
[src]
T: Copy,
impl<T, E> Storage for T where
E: MoveFix,
T: ListStorage<Element = E>,
[src]
E: MoveFix,
T: ListStorage<Element = E>,
type Key = usize
The type used for element naming.
type Element = E
The type of the elements stored.
pub fn add(&mut Self, <T as Storage>::Element) -> usize
[src]
pub fn remove(&mut Self, &usize) -> <T as Storage>::Element
[src]
pub fn len(&Self) -> usize
[src]
pub fn with_capacity(usize) -> T
[src]
pub unsafe fn get_unchecked(&Self, &usize) -> &<T as Storage>::Element
[src]
pub unsafe fn get_unchecked_mut(
&mut Self,
&usize
) -> &mut <T as Storage>::Element
[src]
&mut Self,
&usize
) -> &mut <T as Storage>::Element
pub fn contains_key(&Self, &usize) -> bool
[src]
pub fn get(&Self, &usize) -> Option<&<T as Storage>::Element>
[src]
pub fn get_mut(&mut Self, &usize) -> Option<&mut <T as Storage>::Element>
[src]
pub fn new() -> T
[src]
pub fn capacity(&Self) -> usize
[src]
pub fn reserve(&mut Self, usize)
[src]
pub fn shrink_to_fit(&mut Self)
[src]
fn is_empty(&self) -> bool
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,