[−][src]Crate dynamization
Making static containers dynamic
Sometimes it's much easier to construct some data structure from a predetermined set of data than to implement a way to update this data structure with new elements after construction.
E.g. it's trivial to make a perfectly balanced search tree when the data is already known but not so trivial to keep its balance after adding/deleting some elements.
This crate provides a cheap workaround for the case of a data structure not having any sensible method of insertion.
Example
Suppose you have a sorted vector:
struct SortedVec<T> { vec: Vec<T> } impl<T: Ord> FromIterator<T> for SortedVec<T> { fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=T> { let mut vec: Vec<_> = iter.into_iter().collect(); vec.sort(); SortedVec { vec } } }
This is almost a perfect data structure for many use cases but every insertion is on the average linear in the length of the array.
This crate provides a struct Dynamic
:
use dynamization::Dynamic; type DynamicSortedVec<T> = Dynamic<SortedVec<T>>;
which groups the stored data into independent
units
of different sizes.
The unit sizes are selected in such a way to make single-element
insertions on the average logarithmic.
The only thing needed to make Dynamic
work is
to implement the Static
trait:
use dynamization::Static; impl<T: Ord> Static for SortedVec<T> { fn len(&self) -> usize { self.vec.len() } fn merge_with(self, other: Self) -> Self { // Only for documentation purposes: two sorted arrays can be merged // much more efficiently than sorting the concatenation result! self.vec.into_iter().chain(other.vec).collect() } }
Now DynamicSortedVec
has the add_unit
method.
An optional trait Singleton
can also be
implemented to make the insert
method
available:
use dynamization::Singleton; impl<T> Singleton for SortedVec<T> { type Item = T; fn singleton(item: Self::Item) -> Self { SortedVec { vec: vec![item] } } }
Now you can use DynamicSortedVec
as a rather efficient universal
data structure:
let mut foo = DynamicSortedVec::new(); for x in vec![(1, "one"), (5, "five"), (4, "four"), (3, "tree"), (6, "six")] { foo.insert(x); } // Each query now must be implemented in terms of partial containers: foo.units_mut().filter_map(|unit| { unit.vec .binary_search_by_key(&3, |pair| pair.0) .ok() .map(move |index| &mut unit.vec[index]) }).for_each(|three| { assert_eq!(three, &(3, "tree")); three.1 = "three"; }); // A dynamic structure can be "freezed" with .try_collect(): assert_eq!(foo.try_collect().unwrap().vec, vec![ (1, "one"), (3, "three"), (4, "four"), (5, "five"), (6, "six"), ]);
Modules
sorted_vec | Sorted |
strategy | Different dynamization strategies. |
Structs
Dynamic | A dynamic version of |
DynamicIntoIter | Owning iterator over all the partial containers. |
Units | Shared-reference iterator over all the partial containers. |
UnitsMut | Unique-reference iterator over all the partial containers. |
Traits
Singleton | A trait which can be implemented to provide a dynamized structure
with a convenient |
Static | A trait that a static container must implement to become dynamizable. |