Dynamization of static containers

A crate allowing one to endow a static (i.e. not supporting insertion) data structure with an effective insertion procedure with a small decrease in query performance.

Usage

Simply include

dynamization = "0.4"

in your Cargo.toml.

Examples

This part of readme is WIP. You can read the docs.

Versions

• 0.4.0: Small improvements for Dynamic & introduced SVMap & made the crate no_std (but still requires alloc).
• 0.3.0: Updated/fixed docs & added two new dynamization variants & SVQueue has now a Strategy generic parameter.
• 0.2.0: Bugfixes && some renames && better docs.
• 0.1.0: Initial commit (yanked: the provided SortedVec was unsound).

lib.rs:

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"),
]);