[][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.


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();


        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 { 

    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!

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")] {

// Each query now must be implemented in terms of partial containers:
foo.units_mut().filter_map(|unit| {
        .binary_search_by_key(&3, |pair| pair.0)
        .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"),



Sorted Vec. Can be used as a priority queue or as an associative array. Requires feature sorted_vec.


Different dynamization strategies.



A dynamic version of Container.


Owning iterator over all the partial containers.


Shared-reference iterator over all the partial containers.


Unique-reference iterator over all the partial containers.



A trait which can be implemented to provide a dynamized structure with a convenient insert method.


A trait that a static container must implement to become dynamizable.