competitive::data_structure

Trait RankSelectDictionaries

Source 
pub trait RankSelectDictionaries {
    // Required methods
    fn bit_length(&self) -> usize;
    fn access(&self, k: usize) -> bool;

    // Provided methods
    fn rank1(&self, k: usize) -> usize { ... }
    fn rank0(&self, k: usize) -> usize { ... }
    fn select1(&self, k: usize) -> Option<usize> { ... }
    fn select0(&self, k: usize) -> Option<usize> { ... }
}
Expand description

rank_i(select_i(k)) = k rank_i(select_i(k) + 1) = k + 1

Required Methods§

Source

fn bit_length(&self) -> usize

Source

fn access(&self, k: usize) -> bool

get k-th bit

Provided Methods§

Source

fn rank1(&self, k: usize) -> usize

the number of 1 in [0, k)

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 15)
14    fn rank0(&self, k: usize) -> usize {
15        k - self.rank1(k)
16    }
17    /// index of k-th 1
18    fn select1(&self, k: usize) -> Option<usize> {
19        let n = self.bit_length();
20        if self.rank1(n) <= k {
21            return None;
22        }
23        let (mut l, mut r) = (0, n);
24        while r - l > 1 {
25            let m = (l + r) / 2;
26            if self.rank1(m) <= k {
27                l = m;
28            } else {
29                r = m;
30            }
31        }
32        Some(l)
33    }
More examples
Hide additional examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 38)
29    pub fn new_with_init<T, F>(v: Vec<T>, bit_length: usize, mut f: F) -> Self
30    where
31        T: Clone + RankSelectDictionaries,
32        F: FnMut(usize, usize, T),
33    {
34        let this = Self::new(v.clone(), bit_length);
35        for (mut k, v) in v.into_iter().enumerate() {
36            for (d, &(c, ref b)) in this.table.iter().rev().enumerate().rev() {
37                if v.access(d) {
38                    k = c + b.rank1(k);
39                } else {
40                    k = b.rank0(k);
41                }
42                f(d, k, v.clone());
43            }
44        }
45        this
46    }
47    /// get k-th value
48    pub fn access(&self, mut k: usize) -> usize {
49        let mut val = 0;
50        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
51            if b.access(k) {
52                k = c + b.rank1(k);
53                val |= 1 << d;
54            } else {
55                k = b.rank0(k);
56            }
57        }
58        val
59    }
60    /// the number of val in range
61    pub fn rank(&self, val: usize, mut range: Range<usize>) -> usize {
62        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
63            if val.access(d) {
64                range.start = c + b.rank1(range.start);
65                range.end = c + b.rank1(range.end);
66            } else {
67                range.start = b.rank0(range.start);
68                range.end = b.rank0(range.end);
69            }
70        }
71        range.end - range.start
72    }
73    /// index of k-th val
74    pub fn select(&self, val: usize, k: usize) -> Option<usize> {
75        if self.rank(val, 0..self.len) <= k {
76            return None;
77        }
78        let mut i = 0;
79        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
80            if val.access(d) {
81                i = c + b.rank1(i);
82            } else {
83                i = b.rank0(i);
84            }
85        }
86        i += k;
87        for &(c, ref b) in self.table.iter().rev() {
88            if i >= c {
89                i = b.select1(i - c).unwrap();
90            } else {
91                i = b.select0(i).unwrap();
92            }
93        }
94        Some(i)
95    }
96    /// get k-th smallest value in range
97    pub fn quantile(&self, mut range: Range<usize>, mut k: usize) -> usize {
98        let mut val = 0;
99        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
100            let z = b.rank0(range.end) - b.rank0(range.start);
101            if z <= k {
102                k -= z;
103                val |= 1 << d;
104                range.start = c + b.rank1(range.start);
105                range.end = c + b.rank1(range.end);
106            } else {
107                range.start = b.rank0(range.start);
108                range.end = b.rank0(range.end);
109            }
110        }
111        val
112    }
113    /// get k-th smallest value out of range
114    pub fn quantile_outer(&self, mut range: Range<usize>, mut k: usize) -> usize {
115        let mut val = 0;
116        let mut orange = 0..self.len;
117        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
118            let z = b.rank0(orange.end) - b.rank0(orange.start) + b.rank0(range.start)
119                - b.rank0(range.end);
120            if z <= k {
121                k -= z;
122                val |= 1 << d;
123                range.start = c + b.rank1(range.start);
124                range.end = c + b.rank1(range.end);
125                orange.start = c + b.rank1(orange.start);
126                orange.end = c + b.rank1(orange.end);
127            } else {
128                range.start = b.rank0(range.start);
129                range.end = b.rank0(range.end);
130                orange.start = b.rank0(orange.start);
131                orange.end = b.rank0(orange.end);
132            }
133        }
134        val
135    }
136    /// the number of value less than val in range
137    pub fn rank_lessthan(&self, val: usize, mut range: Range<usize>) -> usize {
138        let mut res = 0;
139        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
140            if val.access(d) {
141                res += b.rank0(range.end) - b.rank0(range.start);
142                range.start = c + b.rank1(range.start);
143                range.end = c + b.rank1(range.end);
144            } else {
145                range.start = b.rank0(range.start);
146                range.end = b.rank0(range.end);
147            }
148        }
149        res
150    }
151    /// the number of valrange in range
152    pub fn rank_range(&self, valrange: Range<usize>, range: Range<usize>) -> usize {
153        self.rank_lessthan(valrange.end, range.clone()) - self.rank_lessthan(valrange.start, range)
154    }
155    pub fn query_less_than<F>(&self, val: usize, mut range: Range<usize>, mut f: F)
156    where
157        F: FnMut(usize, Range<usize>),
158    {
159        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
160            if val.access(d) {
161                f(d, b.rank0(range.start)..b.rank0(range.end));
162                range.start = c + b.rank1(range.start);
163                range.end = c + b.rank1(range.end);
164            } else {
165                range.start = b.rank0(range.start);
166                range.end = b.rank0(range.end);
167            }
168        }
169    }
Source

fn rank0(&self, k: usize) -> usize

the number of 0 in [0, k)

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 37)
35    fn select0(&self, k: usize) -> Option<usize> {
36        let n = self.bit_length();
37        if self.rank0(n) <= k {
38            return None;
39        }
40        let (mut l, mut r) = (0, n);
41        while r - l > 1 {
42            let m = (l + r) / 2;
43            if self.rank0(m) <= k {
44                l = m;
45            } else {
46                r = m;
47            }
48        }
49        Some(l)
50    }
More examples
Hide additional examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 19)
11    pub fn new<T>(mut v: Vec<T>, bit_length: usize) -> Self
12    where
13        T: Clone + RankSelectDictionaries,
14    {
15        let len = v.len();
16        let mut table = Vec::new();
17        for d in (0..bit_length).rev() {
18            let b: BitVector = v.iter().map(|x| x.access(d)).collect();
19            table.push((b.rank0(len), b));
20            v = v
21                .iter()
22                .filter(|&x| !x.access(d))
23                .chain(v.iter().filter(|&x| x.access(d)))
24                .cloned()
25                .collect();
26        }
27        Self { len, table }
28    }
29    pub fn new_with_init<T, F>(v: Vec<T>, bit_length: usize, mut f: F) -> Self
30    where
31        T: Clone + RankSelectDictionaries,
32        F: FnMut(usize, usize, T),
33    {
34        let this = Self::new(v.clone(), bit_length);
35        for (mut k, v) in v.into_iter().enumerate() {
36            for (d, &(c, ref b)) in this.table.iter().rev().enumerate().rev() {
37                if v.access(d) {
38                    k = c + b.rank1(k);
39                } else {
40                    k = b.rank0(k);
41                }
42                f(d, k, v.clone());
43            }
44        }
45        this
46    }
47    /// get k-th value
48    pub fn access(&self, mut k: usize) -> usize {
49        let mut val = 0;
50        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
51            if b.access(k) {
52                k = c + b.rank1(k);
53                val |= 1 << d;
54            } else {
55                k = b.rank0(k);
56            }
57        }
58        val
59    }
60    /// the number of val in range
61    pub fn rank(&self, val: usize, mut range: Range<usize>) -> usize {
62        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
63            if val.access(d) {
64                range.start = c + b.rank1(range.start);
65                range.end = c + b.rank1(range.end);
66            } else {
67                range.start = b.rank0(range.start);
68                range.end = b.rank0(range.end);
69            }
70        }
71        range.end - range.start
72    }
73    /// index of k-th val
74    pub fn select(&self, val: usize, k: usize) -> Option<usize> {
75        if self.rank(val, 0..self.len) <= k {
76            return None;
77        }
78        let mut i = 0;
79        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
80            if val.access(d) {
81                i = c + b.rank1(i);
82            } else {
83                i = b.rank0(i);
84            }
85        }
86        i += k;
87        for &(c, ref b) in self.table.iter().rev() {
88            if i >= c {
89                i = b.select1(i - c).unwrap();
90            } else {
91                i = b.select0(i).unwrap();
92            }
93        }
94        Some(i)
95    }
96    /// get k-th smallest value in range
97    pub fn quantile(&self, mut range: Range<usize>, mut k: usize) -> usize {
98        let mut val = 0;
99        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
100            let z = b.rank0(range.end) - b.rank0(range.start);
101            if z <= k {
102                k -= z;
103                val |= 1 << d;
104                range.start = c + b.rank1(range.start);
105                range.end = c + b.rank1(range.end);
106            } else {
107                range.start = b.rank0(range.start);
108                range.end = b.rank0(range.end);
109            }
110        }
111        val
112    }
113    /// get k-th smallest value out of range
114    pub fn quantile_outer(&self, mut range: Range<usize>, mut k: usize) -> usize {
115        let mut val = 0;
116        let mut orange = 0..self.len;
117        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
118            let z = b.rank0(orange.end) - b.rank0(orange.start) + b.rank0(range.start)
119                - b.rank0(range.end);
120            if z <= k {
121                k -= z;
122                val |= 1 << d;
123                range.start = c + b.rank1(range.start);
124                range.end = c + b.rank1(range.end);
125                orange.start = c + b.rank1(orange.start);
126                orange.end = c + b.rank1(orange.end);
127            } else {
128                range.start = b.rank0(range.start);
129                range.end = b.rank0(range.end);
130                orange.start = b.rank0(orange.start);
131                orange.end = b.rank0(orange.end);
132            }
133        }
134        val
135    }
136    /// the number of value less than val in range
137    pub fn rank_lessthan(&self, val: usize, mut range: Range<usize>) -> usize {
138        let mut res = 0;
139        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
140            if val.access(d) {
141                res += b.rank0(range.end) - b.rank0(range.start);
142                range.start = c + b.rank1(range.start);
143                range.end = c + b.rank1(range.end);
144            } else {
145                range.start = b.rank0(range.start);
146                range.end = b.rank0(range.end);
147            }
148        }
149        res
150    }
151    /// the number of valrange in range
152    pub fn rank_range(&self, valrange: Range<usize>, range: Range<usize>) -> usize {
153        self.rank_lessthan(valrange.end, range.clone()) - self.rank_lessthan(valrange.start, range)
154    }
155    pub fn query_less_than<F>(&self, val: usize, mut range: Range<usize>, mut f: F)
156    where
157        F: FnMut(usize, Range<usize>),
158    {
159        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
160            if val.access(d) {
161                f(d, b.rank0(range.start)..b.rank0(range.end));
162                range.start = c + b.rank1(range.start);
163                range.end = c + b.rank1(range.end);
164            } else {
165                range.start = b.rank0(range.start);
166                range.end = b.rank0(range.end);
167            }
168        }
169    }
Source

fn select1(&self, k: usize) -> Option<usize>

index of k-th 1

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 115)
100    fn select1(&self, mut k: usize) -> Option<usize> {
101        let (mut l, mut r) = (0, self.data.len());
102        if self.sum <= k {
103            return None;
104        }
105        while r - l > 1 {
106            let m = (l + r) / 2;
107            if self.data[m].1 <= k {
108                l = m;
109            } else {
110                r = m;
111            }
112        }
113        let (bit, sum) = self.data[l];
114        k -= sum;
115        Some(l * Self::WORD_SIZE + bit.select1(k).unwrap())
116    }
More examples
Hide additional examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 89)
74    pub fn select(&self, val: usize, k: usize) -> Option<usize> {
75        if self.rank(val, 0..self.len) <= k {
76            return None;
77        }
78        let mut i = 0;
79        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
80            if val.access(d) {
81                i = c + b.rank1(i);
82            } else {
83                i = b.rank0(i);
84            }
85        }
86        i += k;
87        for &(c, ref b) in self.table.iter().rev() {
88            if i >= c {
89                i = b.select1(i - c).unwrap();
90            } else {
91                i = b.select0(i).unwrap();
92            }
93        }
94        Some(i)
95    }
Source

fn select0(&self, k: usize) -> Option<usize>

index of k-th 0

Examples found in repository?
crates/competitive/src/data_structure/bit_vector.rs (line 132)
117    fn select0(&self, mut k: usize) -> Option<usize> {
118        let (mut l, mut r) = (0, self.data.len());
119        if r * Self::WORD_SIZE - self.sum <= k {
120            return None;
121        }
122        while r - l > 1 {
123            let m = (l + r) / 2;
124            if m * Self::WORD_SIZE - self.data[m].1 <= k {
125                l = m;
126            } else {
127                r = m;
128            }
129        }
130        let (bit, sum) = self.data[l];
131        k -= l * Self::WORD_SIZE - sum;
132        Some(l * Self::WORD_SIZE + bit.select0(k).unwrap())
133    }
More examples
Hide additional examples
crates/competitive/src/data_structure/wavelet_matrix.rs (line 91)
74    pub fn select(&self, val: usize, k: usize) -> Option<usize> {
75        if self.rank(val, 0..self.len) <= k {
76            return None;
77        }
78        let mut i = 0;
79        for (d, &(c, ref b)) in self.table.iter().rev().enumerate().rev() {
80            if val.access(d) {
81                i = c + b.rank1(i);
82            } else {
83                i = b.rank0(i);
84            }
85        }
86        i += k;
87        for &(c, ref b) in self.table.iter().rev() {
88            if i >= c {
89                i = b.select1(i - c).unwrap();
90            } else {
91                i = b.select0(i).unwrap();
92            }
93        }
94        Some(i)
95    }

Implementations on Foreign Types§

Source§

impl RankSelectDictionaries for i8

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for i16

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for i32

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for i64

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for i128

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for isize

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for u8

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for u16

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for u32

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for u64

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for u128

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Source§

impl RankSelectDictionaries for usize

Source§

fn bit_length(&self) -> usize

Source§

fn access(&self, k: usize) -> bool

Source§

fn rank1(&self, k: usize) -> usize

Implementors§