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

//! An ordered set that stores indices in a sparse bit field.
//!
//! [`IndexSet`] works similarly to a normal collection, but only stores indices
//! of its elements. In effect, [`IndexSet`] stores whether or not an element is
//! part of the set, whilst allowing the actual element itself to be stored
//! elsewhere; [`IndexSet`]s do not take ownership of their elements, or even a
//! reference to them, and elements can appear in multiple [`IndexSet`]s at
//! once.
//!
//! [`IndexSet`] can also be used as an efficient way of storing integers in an
//! ordered set.
//!
//! See the documentation for [`IndexSet`] for more information.
//!
//! [`IndexSet`]: struct.IndexSet.html
//!
//! # Examples
//!
//! Basic usage:
//!
//! ```
//! use index_set::{IndexSet, ToIndex};
//!
//! enum Topping {
//!     Anchovies,
//!     Cheese,
//!     Ham,
//!     Pineapple,
//! }
//!
//! impl ToIndex for Topping {
//!     type Index = u8;
//!
//!     fn to_index(&self) -> u8 {
//!         match self {
//!             Topping::Anchovies => 0,
//!             Topping::Cheese    => 1,
//!             Topping::Ham       => 2,
//!             Topping::Pineapple => 3,
//!         }
//!     }
//! }
//!
//! let mut pizza = IndexSet::<Topping>::new();
//! pizza.insert(&Topping::Cheese);
//! pizza.insert(&Topping::Ham);
//! pizza.insert(&Topping::Pineapple);
//!
//! assert_eq!(pizza.contains(&Topping::Pineapple), true);
//! assert_eq!(pizza.contains(&Topping::Anchovies), false);
//! ```
//!
//! Storing integers:
//!
//! ```
//! use index_set::IndexSet;
//!
//! let mut set = IndexSet::<u32>::new();
//! set.insert(&1000000);
//! set.insert(&1);
//! set.insert(&3);
//! set.insert(&2);
//!
//! let vec: Vec<u32> = set.into_iter().collect();
//! assert_eq!(vec, [1, 2, 3, 1000000])
//! ```
//!
//! # Implementation
//!
//! Internally, [`IndexSet`] uses a sparse bit field to represent the existence
//! of indices in the set. The bit field is divided into buckets of 256 bits and
//! stored in a `BTreeMap`.
//!
//! [`IndexSet`]: struct.IndexSet.html

mod bucket;
pub mod index;
pub mod set;

#[doc(inline)]
pub use self::index::FromIndex;

#[doc(inline)]
pub use self::index::ToIndex;

#[doc(inline)]
pub use self::set::IndexSet;