Trait treap_map::TreapMapConfig

source ·

pub trait TreapMapConfig: Sized {
    type SearchKey;
    type SortKey;
    type Value: Clone;
    type ExtMap: KeyMngTrait<Self>;
    type Weight: ConsoliableWeight;

    // Required method
    fn next_node_dir(
        me: (&Self::SortKey, &Self::SearchKey),
        other: (&Self::SortKey, &Self::SearchKey)
    ) -> Option<Direction>;
}

Expand description

TreapMap is a struct which implements a treap which can be indexed by a different key (type SearchKey). The associate type SortKey and SearchKey defines how to order node in treap collaborately.

As the user only needs to provider the SearchKey in searching an element, but the underlying treap is ordered by both SortKey and SearchKey. TreapMap also maintains KeyMng to recover SortKey from SearchKey. It could be a HashMap.

If TreapMap is indexed in the same key as the inside treap. The SortKey can be deprecated to () and the KeyMng can be deprecated to a unit type. Since it is compiled through static dispatch, unnecessary operations will be optimized away.