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.
//!
//! ## [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
//! [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(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};

#[cfg(test)]
#[macro_use]
mod test_macros;

mod binary_merge;
mod merge_state;

mod vec_map;
mod vec_set;

#[cfg(total)]
mod total_vec_map;
#[cfg(total)]
mod total_vec_set;

mod dedup;
mod iterators;

mod macros;

#[cfg(test)]
mod obey;

mod small_vec_builder;

pub use dedup::{sort_and_dedup, sort_and_dedup_by_key};
pub use macros::*;
#[cfg(total)]
pub use total_vec_map::*;
#[cfg(total)]
pub use total_vec_set::*;
pub use vec_map::*;
pub use vec_set::*;