fugue_tinyset/lib.rs
1// Copyright 2017-2018 David Roundy
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8//! `tinyset` contains a few collections that are optimized to scale
9//! in size well for small numbers of elements, while still scaling
10//! well in time (and size) for numbers of elements. We now have
11//! just a few types that you might care for.
12//!
13//! 1. [`Set64`] is a set for types that are 64 bits in size or less
14//! and are `Copy`, intended for essentially integer types. This is
15//! our most efficient type, since it can store small sets with just
16//! the size of one pointer, with no heap storage.
17//!
18//! 2. [`SetU64`] just holds `u64` items, and is the internal storage
19//! of [`Set64`].
20//!
21//! 3. [`SetU32`] just holds `u32` items, and uses a bit less memory
22//! than [`SetU64`].
23//!
24//! 4. [`SetUsize`] holds `usize` items, and uses either [SetU64] or
25//! [SetU32] internally.
26//!
27//! All of these set types will do no heap allocation for small sets of
28//! small elements. Small sets occupy the same space as a single
29//! pointer, typically 64 bits. In these 64 bits (or 32 bits), you can
30//! store up to
31//! seven elements if the elements are sufficiently small and not too
32//! widely spaced. For larger numbers and more widely spaced numbers,
33//! you can store progressively
34//! fewer elements without doing a heap allocation. When it does require
35//! a heap allocation, tinyset is still far more compact than a `HashSet`,
36//! particularly when the elements themselves are small.
37//!
38//! These sets all differ from the standard sets in that they iterate
39//! over items rather than references to items, because they do not
40//! store values directly in a way that can be referenced. All of the
41//! type-specific sets further differ in that `remove` and `contains`
42//! accept values rather than references.
43//!
44//! # Examples
45//!
46//! ```
47//! use fugue_tinyset::Set64;
48//! let mut s: Set64<usize> = Set64::new();
49//! s.insert(1);
50//! assert!(s.contains(&1));
51//! ```
52
53#![deny(missing_docs)]
54
55mod rand;
56mod sets;
57
58pub mod setusize;
59pub use setusize::SetUsize;
60
61pub mod setu32;
62pub use setu32::SetU32;
63
64pub mod setu64;
65pub use setu64::SetU64;
66
67pub mod set64;
68pub use crate::set64::{Fits64, Set64};
69
70mod copyset;