1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
//! This crate provides collections (sets and maps) that wrap [SmallVec].
//!
//! # Use cases
//!
//! ## Small collections
//!
//! It happens very frequently that you have collections that have on average just a very small number of elements. If you know
//! the maximum size or even the maximum _typical_ size in advance, you can use this crate to store such collections without allocations.
//! For a larger number of elements, the underlying [SmallVec] will allocate the elements on the heap as a single allocation.
//!
//! ## Read-heavy collections
//!
//! Another very frequent pattern is that you have a possibly large collection that is being created once and then used readonly for
//! a long time. E.g. lookup tables. In these cases, ease of adding individual new elements is less important than compact in-memory
//! representation and lookup performance. This crate provides succinct collections that have only a very small constant overhead over
//! the contents of the collections.
//!
//! # Performance
//!
//! Performance for bulk creation as well as lookup is better than [BTreeMap]/[BTreeSet] and comparable with [HashMap]/[HashSet] for
//! types with a cheap [Ord] instance, like primitive types, and small to medium sizes. Performance for insertion or removal of
//! individual elements to/from large collections is bad, however. This is not the intended use case.
//!
//! # Collections overview
//!
//! ## [VecSet]
//!
//! Provides a set backed by a [SmallVec] of elements.
//!
//! ## [VecMap]
//!
//! Provides a map backed by a [SmallVec] of key value pairs.
//!
//! ## [RadixTree]
//!
//! A [RadixTree] that comes in different flavours.
//!
//! ## [TotalVecSet]
//!
//! A [VecSet] with an additional flag so it can support negation. This way it is possible to represent e.g. the set of all u64 except 1.
//!
//! ## [TotalVecMap]
//!
//! A [VecMap] with an additional default value, so lookup is a total function.
//!
//! # Unsafe
//!
//! The in place operations use unsafe code. If that is a problem for you, let me know and I can hide them behind a feature.
//!
//! [SmallVec]: https://docs.rs/smallvec/1.4.1/smallvec/struct.SmallVec.html
//! [VecSet]: struct.VecSet.html
//! [VecMap]: struct.VecMap.html
//! [TotalVecSet]: struct.TotalVecSet
//! [TotalVecMap]: struct.TotalVecMap
//! [RadixTree]: radix_tree/struct.RadixTree.html
//! [Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html
//! [BTreeSet]: https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
//! [BTreeMap]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
//! [HashSet]: https://doc.rust-lang.org/std/collections/struct.HashSet.html
//! [HashMap]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
#[cfg_attr(docsrs, doc(cfg(feature = "rkyv_validated", feature = "radixtree")))]
#[cfg(test)]
extern crate quickcheck;
#[cfg(test)]
#[macro_use(quickcheck)]
extern crate quickcheck_macros;
#[cfg(test)]
extern crate maplit;
extern crate sorted_iter;
pub use sorted_iter::{SortedIterator, SortedPairIterator};
mod merge_state;
mod vec_map;
mod vec_set;
#[cfg(feature = "radixtree")]
pub mod radix_tree;
#[cfg(feature = "total")]
pub mod total_vec_map;
#[cfg(feature = "total")]
pub mod total_vec_set;
#[cfg(feature = "std_support")]
pub mod btree_map;
mod dedup;
mod iterators;
mod macros;
pub use dedup::{sort_dedup, sort_dedup_by_key};
pub use macros::*;
pub use smallvec::Array;
pub use vec_map::*;
pub use vec_set::*;