wavelet_matrix/lib.rs
1//! This crate provides state-of-the-art O(1) or alike queries on large number of unsigned integers.
2//!
3//! The typical memory usage of this data structure is calculated like below.
4//!
5//! - `bit_len * num_of_elements / 8 * 1.25` [bytes]
6//!
7//! In other words, it roughly consumes additional 25% space compared with the original data.
8//!
9//! # Example
10//!
11//! ```rust
12//! use wavelet_matrix::WaveletMatrix;
13//!
14//! let vec: Vec<u64> = vec![1, 2, 4, 5, 1, 0, 4, 6, 2, 9, 2, 0];
15//! // 0 1 2 3 4 5 6 7 8 9 10 11 (length = 12)
16//! let wm = WaveletMatrix::new(&vec);
17//!
18//! // Basic access
19//! assert_eq!(wm.len(), vec.len());
20//! assert_eq!(wm.lookup(7), vec[7]);
21//! assert_eq!(wm.dim(), 10); // max value + 1
22//! assert_eq!(wm.bit_len(), 4); // bit length stored internally
23//!
24//! // Counting
25//! assert_eq!(wm.count(0..wm.len(), 2), 3);
26//! assert_eq!(wm.count(0..wm.len(), 4), 2);
27//! assert_eq!(wm.count(0..wm.len(), 5), 1);
28//! assert_eq!(wm.count(0..wm.len(), 7), 0);
29//! assert_eq!(wm.count(0..wm.len(), 39), 0);
30//!
31//! assert_eq!(wm.count_prefix(0..wm.len(), 8, 3), 1);
32//! assert_eq!(wm.count_prefix(0..wm.len(), 6, 1), 1);
33//! assert_eq!(wm.count_prefix(0..wm.len(), 0, 1), 4);
34//! assert_eq!(wm.count_prefix(0..wm.len(), 0, 2), 7);
35//!
36//! assert_eq!(wm.count_lt(0..wm.len(), 2), 4);
37//! assert_eq!(wm.count_lt(0..wm.len(), 7), 11);
38//!
39//! assert_eq!(wm.count_gt(0..wm.len(), 2), 5);
40//! assert_eq!(wm.count_gt(0..wm.len(), 7), 1);
41//!
42//! assert_eq!(wm.count_range(0..wm.len(), 0..wm.dim()), 12);
43//! assert_eq!(wm.count_range(0..wm.len(), 4..6), 3);
44//!
45//! // Searching
46//! assert_eq!(wm.search(0..wm.len(), 4).collect::<Vec<usize>>(), vec![2, 6]);
47//! assert_eq!(wm.search(3..wm.len(), 4).collect::<Vec<usize>>(), vec![6]);
48//! assert_eq!(wm.search(0..wm.len(), 7).collect::<Vec<usize>>(), vec![]);
49//!
50//! // Ranking: (value, count), frequent values first
51//! assert_eq!(wm.top_k(0..wm.len(), 0..wm.dim(), 12),
52//! vec![(2, 3), (1, 2), (4, 2), (0, 2), (5, 1), (6, 1), (9, 1)]);
53//! assert_eq!(wm.top_k(0..wm.len(), 0..wm.dim(), 4),
54//! vec![(2, 3), (1, 2), (4, 2), (0, 2)]);
55//! assert_eq!(wm.top_k(0..wm.len(), 2..9, 12),
56//! vec![(2, 3), (4, 2), (5, 1), (6, 1)]);
57//!
58//! // Ranking: (value, count), max values first
59//! assert_eq!(wm.max_k(0..wm.len(), 0..wm.dim(), 12),
60//! vec![(9, 1), (6, 1), (5, 1), (4, 2), (2, 3), (1, 2), (0, 2)]);
61//! assert_eq!(wm.max_k(0..wm.len(), 0..wm.dim(), 4),
62//! vec![(9, 1), (6, 1), (5, 1), (4, 2)]);
63//! assert_eq!(wm.max_k(0..wm.len(), 2..9, 12),
64//! vec![(6, 1), (5, 1), (4, 2), (2, 3)]);
65//!
66//! // Ranking: (value, count), min values first
67//! assert_eq!(wm.min_k(0..wm.len(), 0..wm.dim(), 12),
68//! vec![(0, 2), (1, 2), (2, 3), (4, 2), (5, 1), (6, 1), (9, 1)]);
69//! assert_eq!(wm.min_k(0..wm.len(), 0..wm.dim(), 4),
70//! vec![(0, 2), (1, 2), (2, 3), (4, 2)]);
71//! assert_eq!(wm.min_k(0..wm.len(), 2..9, 12),
72//! vec![(2, 3), (4, 2), (5, 1), (6, 1)]);
73//!
74//! // Statistics
75//! assert_eq!(wm.quantile(0..wm.len(), 0), 0);
76//! assert_eq!(wm.quantile(0..wm.len(), 8), 4);
77//! assert_eq!(wm.quantile(0..wm.len(), 11), 9);
78//! ```
79
80extern crate succinct;
81
82mod rsdic_simple;
83mod node_range;
84mod wavelet_matrix;
85
86pub use wavelet_matrix::*;