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 Vec. Can be used as a priority queue or as an associative array. Requires feature sorted_vec.

strategy

Different dynamization strategies.

Structs

Dynamic

A dynamic version of Container.

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 insert method.

Static

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