pub trait RangeBoundsExt<T> {
Show 18 methods
// Required methods
fn start_bound_included_checked(&self) -> Option<T>;
fn start_bound_excluded_checked(&self) -> Option<T>;
fn end_bound_included_checked(&self) -> Option<T>;
fn end_bound_excluded_checked(&self) -> Option<T>;
fn start_bound_included(&self) -> T;
fn start_bound_excluded(&self) -> T;
fn end_bound_included(&self) -> T;
fn end_bound_excluded(&self) -> T;
fn start_bound_included_bounded(&self, lb: T) -> Option<T>
where T: Ord;
fn start_bound_excluded_bounded(&self, lb: T) -> Option<T>
where T: Ord;
fn end_bound_included_bounded(&self, ub: T) -> Option<T>
where T: Ord;
fn end_bound_excluded_bounded(&self, ub: T) -> Option<T>
where T: Ord;
// Provided methods
fn to_range_checked(&self) -> Option<Range<T>> { ... }
fn to_range(&self) -> Range<T> ⓘ { ... }
fn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>
where T: Ord { ... }
fn to_range_inclusive_checked(&self) -> Option<RangeInclusive<T>> { ... }
fn to_range_inclusive(&self) -> RangeInclusive<T> ⓘ { ... }
fn to_range_inclusive_bounded(
&self,
min: T,
max: T,
) -> Option<RangeInclusive<T>>
where T: Ord { ... }
}Required Methods§
fn start_bound_included_checked(&self) -> Option<T>
fn start_bound_excluded_checked(&self) -> Option<T>
fn end_bound_included_checked(&self) -> Option<T>
fn end_bound_excluded_checked(&self) -> Option<T>
fn start_bound_included(&self) -> T
fn start_bound_excluded(&self) -> T
fn end_bound_included(&self) -> T
fn end_bound_excluded(&self) -> T
fn start_bound_included_bounded(&self, lb: T) -> Option<T>where
T: Ord,
fn start_bound_excluded_bounded(&self, lb: T) -> Option<T>where
T: Ord,
fn end_bound_included_bounded(&self, ub: T) -> Option<T>where
T: Ord,
fn end_bound_excluded_bounded(&self, ub: T) -> Option<T>where
T: Ord,
Provided Methods§
fn to_range_checked(&self) -> Option<Range<T>>
Sourcefn to_range(&self) -> Range<T> ⓘ
fn to_range(&self) -> Range<T> ⓘ
Examples found in repository?
crates/competitive/src/data_structure/segment_tree_map.rs (line 89)
85 pub fn fold<R>(&self, range: R) -> M::T
86 where
87 R: RangeBounds<usize>,
88 {
89 let range = range.to_range();
90 debug_assert!(range.end <= self.n);
91 let mut l = range.start + self.n;
92 let mut r = range.end + self.n;
93 let mut vl = M::unit();
94 let mut vr = M::unit();
95 while l < r {
96 if l & 1 != 0 {
97 vl = M::operate(&vl, self.get_ref(l));
98 l += 1;
99 }
100 if r & 1 != 0 {
101 r -= 1;
102 vr = M::operate(self.get_ref(r), &vr);
103 }
104 l /= 2;
105 r /= 2;
106 }
107 M::operate(&vl, &vr)
108 }Sourcefn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>where
T: Ord,
fn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>where
T: Ord,
Examples found in repository?
More examples
crates/competitive/src/data_structure/accumulate.rs (line 86)
81 pub fn fold<R>(&self, range: R) -> M::T
82 where
83 R: RangeBounds<usize>,
84 {
85 let n = self.data.len() - 1;
86 let range = range.to_range_bounded(0, n).expect("invalid range");
87 let (l, r) = (range.start, range.end);
88 assert!(l <= r, "bad range [{}, {})", l, r);
89 M::operate(&M::inverse(unsafe { self.data.get_unchecked(l) }), unsafe {
90 self.data.get_unchecked(r)
91 })
92 }
93}
94
95/// 2-dimensional accumlated data
96pub struct Accumulate2d<M>
97where
98 M: AbelianMonoid,
99{
100 h: usize,
101 w: usize,
102 data: Vec<M::T>,
103}
104
105impl<M> Debug for Accumulate2d<M>
106where
107 M: AbelianMonoid<T: Debug>,
108{
109 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
110 f.debug_struct("Accumulate2d")
111 .field("h", &self.h)
112 .field("w", &self.w)
113 .field("data", &self.data)
114 .finish()
115 }
116}
117
118impl<M> Accumulate2d<M>
119where
120 M: AbelianMonoid,
121{
122 pub fn new(arr2d: &[Vec<M::T>]) -> Self {
123 let h = arr2d.len();
124 assert!(h > 0);
125 let w = arr2d[0].len();
126 assert!(w > 0);
127 let w1 = w + 1;
128 let mut data = Vec::with_capacity((h + 1) * w1);
129 data.resize_with(w1, M::unit);
130 for (i, arr) in arr2d.iter().enumerate() {
131 assert_eq!(w, arr.len(), "expected 2d array");
132 let mut acc = M::unit();
133 for (j, x) in arr.iter().enumerate() {
134 let y = M::operate(&acc, x);
135 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + j) }));
136 acc = y;
137 }
138 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + w) }));
139 }
140 Self { h, w, data }
141 }
142 pub fn from_fn<F>(h: usize, w: usize, mut f: F) -> Self
143 where
144 F: FnMut(usize, usize) -> M::T,
145 {
146 let w1 = w + 1;
147 let mut data = Vec::with_capacity((h + 1) * w1);
148 data.resize_with(w1, M::unit);
149 for i in 0..h {
150 let mut acc = M::unit();
151 for j in 0..w {
152 let y = M::operate(&acc, &f(i, j));
153 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + j) }));
154 acc = y;
155 }
156 data.push(M::operate(&acc, unsafe { data.get_unchecked(w1 * i + w) }));
157 }
158 Self { h, w, data }
159 }
160 /// Return fold of \[0, x\) × \[0, y\)
161 pub fn accumulate(&self, x: usize, y: usize) -> M::T {
162 let h1 = self.h + 1;
163 let w1 = self.w + 1;
164 assert!(
165 x < h1,
166 "index out of range: the first len is {} but the index is {}",
167 h1,
168 x
169 );
170 assert!(
171 y < w1,
172 "index out of range: the second len is {} but the index is {}",
173 w1,
174 y
175 );
176 unsafe { self.data.get_unchecked(w1 * x + y) }.clone()
177 }
178}
179
180impl<M> Accumulate2d<M>
181where
182 M: AbelianGroup,
183{
184 /// Return fold of range
185 pub fn fold<R0, R1>(&self, range0: R0, range1: R1) -> M::T
186 where
187 R0: RangeBounds<usize>,
188 R1: RangeBounds<usize>,
189 {
190 let range0 = range0.to_range_bounded(0, self.h).expect("invalid range");
191 let range1 = range1.to_range_bounded(0, self.w).expect("invalid range");
192 let (xl, xr) = (range0.start, range0.end);
193 let (yl, yr) = (range1.start, range1.end);
194 assert!(xl <= xr, "bad range [{}, {})", xl, xr);
195 assert!(yl <= yr, "bad range [{}, {})", yl, yr);
196 let w1 = self.w + 1;
197 unsafe {
198 M::rinv_operate(
199 &M::operate(
200 self.data.get_unchecked(w1 * xl + yl),
201 self.data.get_unchecked(w1 * xr + yr),
202 ),
203 &M::operate(
204 self.data.get_unchecked(w1 * xl + yr),
205 self.data.get_unchecked(w1 * xr + yl),
206 ),
207 )
208 }
209 }
210}
211
212pub struct AccumulateKd<const K: usize, M>
213where
214 M: AbelianMonoid,
215{
216 dim: [usize; K],
217 offset: [usize; K],
218 data: Vec<M::T>,
219}
220
221impl<const K: usize, M> Debug for AccumulateKd<K, M>
222where
223 M: AbelianMonoid<T: Debug>,
224{
225 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
226 f.debug_struct("AccumulateKd")
227 .field("dim", &self.dim)
228 .field("offset", &self.offset)
229 .field("data", &self.data)
230 .finish()
231 }
232}
233
234impl<const K: usize, M> AccumulateKd<K, M>
235where
236 M: AbelianMonoid,
237{
238 pub fn from_fn(dim: [usize; K], mut f: impl FnMut([usize; K]) -> M::T) -> Self {
239 fn fill<const K: usize, T>(
240 dim: &[usize; K],
241 offset: &[usize; K],
242 data: &mut [T],
243 f: &mut impl FnMut([usize; K]) -> T,
244 mut index: [usize; K],
245 pos: usize,
246 ) {
247 if pos < K {
248 for i in 0..dim[pos] {
249 index[pos] = i;
250 fill(dim, offset, data, f, index, pos + 1);
251 }
252 } else {
253 let i: usize = index.iter().zip(offset).map(|(x, y)| (x + 1) * y).sum();
254 data[i] = f(index);
255 }
256 }
257
258 let mut offset = [1; K];
259 for d in (1..K).rev() {
260 offset[d - 1] = offset[d] * (dim[d] + 1);
261 }
262 let size = offset[0] * (dim[0] + 1);
263 let mut data = vec![M::unit(); size];
264 fill(&dim, &offset, &mut data, &mut f, [0; K], 0);
265 for d in 0..K {
266 for i in 1..size {
267 if i / offset[d] % (dim[d] + 1) != 0 {
268 data[i] = M::operate(&data[i], &data[i - offset[d]]);
269 }
270 }
271 }
272 Self { dim, offset, data }
273 }
274 pub fn accumulate(&self, x: [usize; K]) -> M::T {
275 for (d, x) in x.into_iter().enumerate() {
276 assert!(
277 x <= self.dim[d],
278 "index out of range: the len is {} but the index is {}",
279 self.dim[d] + 1,
280 x
281 );
282 }
283 let p: usize = x.iter().zip(&self.offset).map(|(x, y)| x * y).sum();
284 unsafe { self.data.get_unchecked(p) }.clone()
285 }
286}
287
288impl<const K: usize, M> AccumulateKd<K, M>
289where
290 M: AbelianGroup,
291{
292 pub fn fold<R>(&self, ranges: [R; K]) -> M::T
293 where
294 R: RangeBounds<usize>,
295 {
296 let ranges: [_; K] = std::array::from_fn(|i| {
297 let range = ranges[i]
298 .to_range_bounded(0, self.dim[i])
299 .expect("invalid range");
300 let (l, r) = (range.start, range.end);
301 assert!(l <= r, "bad range [{}, {})", l, r);
302 [l, r]
303 });
304 let mut p: usize = ranges
305 .iter()
306 .zip(&self.offset)
307 .map(|(range, offset)| range[1] * offset)
308 .sum();
309 let delta: [_; K] = std::array::from_fn(|d| (ranges[d][1] - ranges[d][0]) * self.offset[d]);
310 let mut acc = M::unit();
311 let len = 1usize << K;
312 let mut gray = 0usize;
313 let mut inv = false;
314 for i in 0..len {
315 if inv {
316 acc = M::rinv_operate(&acc, unsafe { self.data.get_unchecked(p) });
317 } else {
318 acc = M::operate(&acc, unsafe { self.data.get_unchecked(p) });
319 }
320 if i + 1 < len {
321 let next_gray = (i + 1) ^ ((i + 1) >> 1);
322 let changed = gray ^ next_gray;
323 let d = changed.trailing_zeros() as usize;
324 if (next_gray >> d) & 1 == 1 {
325 p -= delta[d];
326 } else {
327 p += delta[d];
328 }
329 gray = next_gray;
330 inv = !inv;
331 }
332 }
333 acc
334 }crates/competitive/src/data_structure/segment_tree.rs (line 89)
85 pub fn fold<R>(&self, range: R) -> M::T
86 where
87 R: RangeBounds<usize>,
88 {
89 let range = range.to_range_bounded(0, self.n).expect("invalid range");
90 let mut l = range.start + self.n;
91 let mut r = range.end + self.n;
92 let mut vl = M::unit();
93 let mut vr = M::unit();
94 while l < r {
95 if l & 1 != 0 {
96 vl = M::operate(&vl, &self.seg[l]);
97 l += 1;
98 }
99 if r & 1 != 0 {
100 r -= 1;
101 vr = M::operate(&self.seg[r], &vr);
102 }
103 l /= 2;
104 r /= 2;
105 }
106 M::operate(&vl, &vr)
107 }crates/competitive/src/algorithm/sqrt_decomposition.rs (line 65)
61 pub fn update<R>(&mut self, range: R, x: <S::M as Magma>::T)
62 where
63 R: RangeBounds<usize>,
64 {
65 let range = range.to_range_bounded(0, self.n).expect("invalid range");
66 for (i, Bucket { cells, bucket }) in self.buckets.iter_mut().enumerate() {
67 let s = i * self.bucket_size;
68 let t = s + cells.len();
69 if t <= range.start || range.end <= s {
70 } else if range.start <= s && t <= range.end {
71 S::update_bucket(bucket, &x);
72 } else {
73 for cell in &mut cells[range.start.max(s) - s..range.end.min(t) - s] {
74 S::update_cell(bucket, cell, &x);
75 }
76 }
77 }
78 }
79 pub fn get(&self, i: usize) -> <S::M as Magma>::T {
80 let Bucket { cells, bucket } = &self.buckets[i / self.bucket_size];
81 let j = i % self.bucket_size;
82 S::fold_cell(bucket, &cells[j])
83 }
84 pub fn fold<R>(&self, range: R) -> <S::M as Magma>::T
85 where
86 R: RangeBounds<usize>,
87 {
88 let range = range.to_range_bounded(0, self.n).expect("invalid range");
89 let mut res = S::M::unit();
90 for (i, Bucket { cells, bucket }) in self.buckets.iter().enumerate() {
91 let s = i * self.bucket_size;
92 let t = s + cells.len();
93 if t <= range.start || range.end <= s {
94 } else if range.start <= s && t <= range.end {
95 <S::M as Magma>::operate_assign(&mut res, &S::fold_bucket(bucket));
96 } else {
97 for cell in &cells[range.start.max(s) - s..range.end.min(t) - s] {
98 <S::M as Magma>::operate_assign(&mut res, &S::fold_cell(bucket, cell));
99 }
100 }
101 }
102 res
103 }crates/competitive/src/data_structure/lazy_segment_tree_map.rs (line 119)
115 pub fn update<R>(&mut self, range: R, x: M::Act)
116 where
117 R: RangeBounds<usize>,
118 {
119 let range = range.to_range_bounded(0, self.n).expect("invalid range");
120 if M::is_act_unit(&x) {
121 return;
122 }
123 let mut a = range.start + self.n;
124 let mut b = range.end + self.n;
125 self.propagate(a, false, false);
126 self.propagate(b, true, false);
127 while a < b {
128 if a & 1 != 0 {
129 self.update_at(a, &x);
130 a += 1;
131 }
132 if b & 1 != 0 {
133 b -= 1;
134 self.update_at(b, &x);
135 }
136 a /= 2;
137 b /= 2;
138 }
139 self.recalc(range.start + self.n, false, false);
140 self.recalc(range.end + self.n, true, false);
141 }
142 pub fn fold<R>(&mut self, range: R) -> M::Agg
143 where
144 R: RangeBounds<usize>,
145 {
146 let range = range.to_range_bounded(0, self.n).expect("invalid range");
147 let mut l = range.start + self.n;
148 let mut r = range.end + self.n;
149 self.propagate(l, false, true);
150 self.propagate(r, true, true);
151 let mut vl = M::agg_unit();
152 let mut vr = M::agg_unit();
153 while l < r {
154 if l & 1 != 0 {
155 if let Some((x, _)) = self.seg.get(&l) {
156 vl = M::agg_operate(&vl, x);
157 }
158 l += 1;
159 }
160 if r & 1 != 0 {
161 r -= 1;
162 if let Some((x, _)) = self.seg.get(&r) {
163 vr = M::agg_operate(x, &vr);
164 }
165 }
166 l /= 2;
167 r /= 2;
168 }
169 M::agg_operate(&vl, &vr)
170 }crates/competitive/src/data_structure/dual_segment_tree.rs (line 83)
78 pub fn update<R>(&mut self, range: R, a: M::Act)
79 where
80 R: RangeBounds<usize>,
81 {
82 let range = range
83 .to_range_bounded(0, self.keys.len())
84 .expect("invalid range");
85 if range.is_empty() || M::ActMonoid::is_unit(&a) {
86 return;
87 }
88 let mut l = range.start + self.n;
89 let mut r = range.end + self.n;
90 for i in (1..=self.n.trailing_zeros()).rev() {
91 if (l >> i) << i != l {
92 self.propagate_at(l >> i);
93 }
94 if (r >> i) << i != r && ((l >> i) << i == l || l >> i != (r - 1) >> i) {
95 self.propagate_at((r - 1) >> i);
96 }
97 }
98 while l < r {
99 if l & 1 != 0 {
100 self.update_at(l, &a);
101 l += 1;
102 }
103 if r & 1 != 0 {
104 r -= 1;
105 self.update_at(r, &a);
106 }
107 l >>= 1;
108 r >>= 1;
109 }
110 }Additional examples can be found in:
fn to_range_inclusive_checked(&self) -> Option<RangeInclusive<T>>
fn to_range_inclusive(&self) -> RangeInclusive<T> ⓘ
fn to_range_inclusive_bounded(
&self,
min: T,
max: T,
) -> Option<RangeInclusive<T>>where
T: Ord,
Dyn Compatibility§
This trait is dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".