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

//! Space efficient storage using ranges
//!
//! # When should you use `RangedSet`?
//!
//! `RangedSet` is designed for use cases where a large number of values
//! that are contiguous need storage and fast lookup. The inspiration
//! came from implementing a cache lookup for a program that worked out
//! converging number sequences for the Collatz conjecture. Using a
//! `HashSet` became very slow after caching about 3 million `u64`s. (A
//! smaller, incorrect version of this program is given below. It is
//! incorrect in that it automatically caches values before knowing that
//! the sequence converges. It can do this because all the values below
//! 256 are known to converge.)
//!
//! # Example
//!
//! ```rust
//! use ranged_set::RangedSet;
//!
//! fn collatz(number: u64) -> u64 {
//!    match number % 2 == 0 {
//!        false => 3 * number + 1,
//!        true => number / 2,
//!    }
//! }
//!
//! fn main() {
//!     let mut cache = RangedSet::new();
//!
//!     for i in 1..256 {
//!         let mut current = i;
//!         print!("{}: ", current);
//!
//!         loop {
//!             println!("{} -> ", current);
//!
//!             if cache.contains(&current) {
//!                 println!("(converges)");
//!                 break;
//!             } else {
//!                 cache.insert(current.clone());
//!                 current = collatz(current);
//!             }
//!         }
//!     }
//! }
//! ```

extern crate num_traits;
extern crate step;

mod element;
mod range_inclusive;
mod set;

pub use set::RangedSet;