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