segment_tree/ops/
mod.rs

1//! Module of operations that can be performed in a segment tree.
2//!
3//! A segment tree needs some operation, and this module contains the main [`Operation`]
4//! trait, together with the marker trait [`Commutative`]. This module also contains
5//! implementations for simple operations.
6//!
7//! [`Operation`]: trait.Operation.html
8//! [`Commutative`]: trait.Commutative.html
9
10use std::num::Wrapping;
11
12#[cfg(feature = "num-bigint")]
13mod num;
14
15/// A trait that specifies which associative operator to use in a segment tree.
16pub trait Operation<N> {
17    /// The operation that is performed to combine two intervals in the segment tree.
18    ///
19    /// This function must be [associative][1], that is `combine(combine(a, b), c) =
20    /// combine(a, combine(b, c))`.
21    ///
22    /// [1]: https://en.wikipedia.org/wiki/Associative_property
23    fn combine(&self, a: &N, b: &N) -> N;
24    /// Replace the value in `a` with `combine(a, b)`. This function exists to allow
25    /// certain optimizations and by default simply calls `combine`.
26    #[inline]
27    fn combine_mut(&self, a: &mut N, b: &N) {
28        let res = self.combine(&*a, b);
29        *a = res;
30    }
31    /// Replace the value in `b` with `combine(a, b)`. This function exists to allow
32    /// certain optimizations and by default simply calls `combine`.
33    #[inline]
34    fn combine_mut2(&self, a: &N, b: &mut N) {
35        let res = self.combine(a, &*b);
36        *b = res;
37    }
38    /// Must return the same as `combine`. This function exists to allow certain
39    /// optimizations and by default simply calls `combine_mut`.
40    #[inline]
41    fn combine_left(&self, mut a: N, b: &N) -> N {
42        self.combine_mut(&mut a, b); a
43    }
44    /// Must return the same as `combine`. This function exists to allow certain
45    /// optimizations and by default simply calls `combine_mut2`.
46    #[inline]
47    fn combine_right(&self, a: &N, mut b: N) -> N {
48        self.combine_mut2(a, &mut b); b
49    }
50    /// Must return the same as `combine`. This function exists to allow certain
51    /// optimizations and by default simply calls `combine_left`.
52    #[inline]
53    fn combine_both(&self, a: N, b: N) -> N {
54        self.combine_left(a, &b)
55    }
56}
57
58/// A marker trait that specifies that an [`Operation`] is [commutative][1], that is:
59/// `combine(a, b) = combine(b, a)`.
60///
61/// [`Operation`]: trait.Operation.html
62/// [1]: https://en.wikipedia.org/wiki/Commutative_property
63pub trait Commutative<N>: Operation<N> {}
64
65/// A trait that specifies that this [`Operation`] has an [identity element][1].
66///
67/// An identity must satisfy `combine(a, id) = a` and `combine(id, a) = a`, where `id` is
68/// something returned by [`identity`].
69///
70/// [`Operation`]: trait.Operation.html
71/// [`identity`]: #tymethod.identity
72/// [1]: https://en.wikipedia.org/wiki/Identity_element
73pub trait Identity<N> {
74    /// Returns an element such that if [combined][1] with any element `a` the result must
75    /// be `a`.
76    ///
77    /// [1]: trait.Operation.html#tymethod.combine
78    fn identity(&self) -> N;
79}
80
81/// A trait for invertible operations.
82pub trait Invertible<N> {
83    /// A method such that the following code will leave `a` in the same state as it
84    /// started.
85    ///
86    ///```rust
87    ///# use segment_tree::ops::{Add, Operation, Invertible};
88    ///# let op = Add;
89    ///# let mut a = 1i32;
90    ///# let mut original_value_of_a = 1i32;
91    ///# let mut b = 2i32;
92    /// // after running these two methods, a should be unchanged:
93    ///op.combine_mut(&mut a, &b);
94    ///op.uncombine(&mut a, &b);
95    ///assert_eq!(a, original_value_of_a);
96    /// // a should also be unchanged after running them in the reverse order
97    ///op.uncombine(&mut a, &b);
98    ///op.combine_mut(&mut a, &b);
99    ///assert_eq!(a, original_value_of_a);
100    ///```
101    fn uncombine(&self, a: &mut N, b: &N);
102}
103
104/// Each node contains the sum of the interval it represents.
105#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
106pub struct Add;
107/// Each node contains the product of the interval it represents.
108#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
109pub struct Mul;
110
111
112/// Each node contains the bitwise and of the interval it represents.
113#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
114pub struct And;
115/// Each node contains the bitwise or of the interval it represents.
116#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
117pub struct Or;
118/// Each node contains the bitwise xor of the interval it represents.
119#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
120pub struct Xor;
121
122/// Each node contains the minimum of the interval it represents.
123#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
124pub struct Min;
125/// Each node contains the maximum of the interval it represents.
126#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
127pub struct Max;
128
129macro_rules! impl_operation_infix {
130    ($op:ty, $ty:ty, $combineop:tt, $doc:expr) => {
131        impl Operation<$ty> for $op {
132            #[doc = $doc]
133            #[inline]
134            fn combine(&self, a: &$ty, b: &$ty) -> $ty {
135                *a $combineop *b
136            }
137        }
138    }
139}
140macro_rules! impl_operation_prefix {
141    ($op:ty, $ty:ty, $combinef:expr, $doc:expr) => {
142        impl Operation<$ty> for $op {
143            #[doc = $doc]
144            #[inline]
145            fn combine(&self, a: &$ty, b: &$ty) -> $ty {
146                $combinef(*a, *b)
147            }
148        }
149    }
150}
151macro_rules! impl_identity {
152    ($op:ty, $ty:ty, $iden:expr, $doc:expr) => {
153        impl Identity<$ty> for $op {
154            #[doc = $doc]
155            #[inline]
156            fn identity(&self) -> $ty {
157                $iden
158            }
159        }
160    }
161}
162macro_rules! impl_inverse {
163    ($op:ty, $ty:ty, $uncombineop:tt, $doc:expr) => {
164        impl Invertible<$ty> for $op {
165            #[doc = $doc]
166            #[inline]
167            fn uncombine(&self, a: &mut $ty, b: &$ty) {
168                *a = *a $uncombineop *b;
169            }
170        }
171    }
172}
173macro_rules! impl_unsigned_primitive {
174    ($ty:tt) => {
175        impl_operation_infix!(Add, $ty, +, "Returns the sum.");
176        impl_identity!(Add, $ty, 0, "Returns zero.");
177        impl Commutative<$ty> for Add {}
178
179        impl_operation_infix!(Add, Wrapping<$ty>, +, "Returns the sum.");
180        impl_identity!(Add, Wrapping<$ty>, Wrapping(0), "Returns zero.");
181        impl_inverse!(Add, Wrapping<$ty>, -, "Returns the difference.");
182        impl Commutative<Wrapping<$ty>> for Add {}
183
184        impl_operation_infix!(Xor, $ty, ^, "Returns the bitwise exclusive or.");
185        impl_identity!(Xor, $ty, 0, "Returns zero.");
186        impl_inverse!(Xor, $ty, ^, "Returns the bitwise exclusive or.");
187        impl Commutative<$ty> for Xor {}
188
189        impl_operation_infix!(Mul, $ty, *, "Returns the product.");
190        impl_identity!(Mul, $ty, 1, "Returns one.");
191        impl Commutative<$ty> for Mul {}
192
193        impl_operation_infix!(Mul, Wrapping<$ty>, *, "Returns the product.");
194        impl_identity!(Mul, Wrapping<$ty>, Wrapping(1), "Returns one.");
195        impl Commutative<Wrapping<$ty>> for Mul {}
196
197        impl_operation_infix!(And, $ty, &, "Returns the bitwise and.");
198        impl_identity!(And, $ty, std::$ty::MAX, "Returns the largest possible value.");
199        impl Commutative<$ty> for And {}
200
201        impl_operation_infix!(Or, $ty, &, "Returns the bitwise or.");
202        impl_identity!(Or, $ty, 0, "Returns zero.");
203        impl Commutative<$ty> for Or {}
204
205        impl_operation_prefix!(Min, $ty, std::cmp::min, "Returns the minimum.");
206        impl_identity!(Min, $ty, std::$ty::MAX, "Returns the largest possible value.");
207        impl Commutative<$ty> for Min {}
208
209        impl_operation_prefix!(Max, $ty, std::cmp::max, "Returns the maximum.");
210        impl_identity!(Max, $ty, 0, "Returns zero.");
211        impl Commutative<$ty> for Max {}
212    }
213}
214impl_unsigned_primitive!(u8);
215impl_unsigned_primitive!(u16);
216impl_unsigned_primitive!(u32);
217impl_unsigned_primitive!(u64);
218impl_unsigned_primitive!(u128);
219impl_unsigned_primitive!(usize);
220
221macro_rules! impl_signed_primitive {
222    ($ty:tt) => {
223        impl_operation_infix!(Add, $ty, +, "Returns the sum.");
224        impl_identity!(Add, $ty, 0, "Returns zero.");
225        impl_inverse!(Add, $ty, -, "Returns the difference.");
226        impl Commutative<$ty> for Add {}
227
228        impl_operation_infix!(Add, Wrapping<$ty>, +, "Returns the sum.");
229        impl_identity!(Add, Wrapping<$ty>, Wrapping(0), "Returns zero.");
230        impl_inverse!(Add, Wrapping<$ty>, -, "Returns the difference.");
231        impl Commutative<Wrapping<$ty>> for Add {}
232
233        impl_operation_infix!(Xor, $ty, ^, "Returns the bitwise exclusive or.");
234        impl_identity!(Xor, $ty, 0, "Returns zero.");
235        impl_inverse!(Xor, $ty, ^, "Returns the bitwise exclusive or.");
236        impl Commutative<$ty> for Xor {}
237
238        impl_operation_infix!(Mul, $ty, *, "Returns the product.");
239        impl_identity!(Mul, $ty, 1, "Returns one.");
240        impl Commutative<$ty> for Mul {}
241
242        impl_operation_infix!(Mul, Wrapping<$ty>, *, "Returns the product.");
243        impl_identity!(Mul, Wrapping<$ty>, Wrapping(1), "Returns one.");
244        impl Commutative<Wrapping<$ty>> for Mul {}
245
246        impl_operation_infix!(And, $ty, &, "Returns the bitwise and.");
247        impl_identity!(And, $ty, -1, "Returns negative one.");
248        impl Commutative<$ty> for And {}
249
250        impl_operation_infix!(Or, $ty, &, "Returns the bitwise or.");
251        impl_identity!(Or, $ty, 0, "Returns zero.");
252        impl Commutative<$ty> for Or {}
253
254        impl_operation_prefix!(Min, $ty, std::cmp::min, "Returns the minimum.");
255        impl_identity!(Min, $ty, std::$ty::MAX, "Returns the largest possible value.");
256        impl Commutative<$ty> for Min {}
257
258        impl_operation_prefix!(Max, $ty, std::cmp::max, "Returns the maximum.");
259        impl_identity!(Max, $ty, std::$ty::MIN, "Returns the smallest possible value.");
260        impl Commutative<$ty> for Max {}
261    }
262}
263impl_signed_primitive!(i8);
264impl_signed_primitive!(i16);
265impl_signed_primitive!(i32);
266impl_signed_primitive!(i64);
267impl_signed_primitive!(i128);
268impl_signed_primitive!(isize);
269
270impl_operation_infix!(Add, f32, +, "Returns the sum.");
271impl_inverse!(Add, f32, -, "Returns the difference.");
272impl_identity!(Add, f32, 0.0, "Returns zero.");
273impl Commutative<f32> for Add {}
274
275impl_operation_infix!(Mul, f32, *, "Returns the product.");
276impl_inverse!(Mul, f32, /, "Returns the ratio.");
277impl_identity!(Mul, f32, 1.0, "Returns one.");
278impl Commutative<f32> for Mul {}
279
280impl_operation_infix!(Add, f64, +, "Returns the sum.");
281impl_inverse!(Add, f64, -, "Returns the difference.");
282impl_identity!(Add, f64, 0.0, "Returns zero.");
283impl Commutative<f64> for Add {}
284
285impl_operation_infix!(Mul, f64, *, "Returns the product.");
286impl_inverse!(Mul, f64, /, "Returns the ratio.");
287impl_identity!(Mul, f64, 1.0, "Returns one.");
288impl Commutative<f64> for Mul {}
289
290
291/// Variant of [`Min`] that considers NaN the largest value.
292///
293/// [`Min`]: struct.Min.html
294#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
295pub struct MinIgnoreNaN;
296impl_identity!(MinIgnoreNaN, f32, std::f32::NAN, "Returns NaN.");
297impl_identity!(MinIgnoreNaN, f64, std::f64::NAN, "Returns NaN.");
298impl Commutative<f32> for MinIgnoreNaN {}
299impl Commutative<f64> for MinIgnoreNaN {}
300impl Operation<f32> for MinIgnoreNaN {
301    /// Returns the smallest of the two values.
302    ///
303    /// If either argument is NaN, the other is returned.
304    fn combine(&self, a: &f32, b: &f32) -> f32 {
305        if b > a || b.is_nan() { *a } else { *b }
306    }
307}
308impl Operation<f64> for MinIgnoreNaN {
309    /// Returns the smallest of the two values.
310    ///
311    /// If either argument is NaN, the other is returned.
312    fn combine(&self, a: &f64, b: &f64) -> f64 {
313        if b > a || b.is_nan() { *a } else { *b }
314    }
315}
316
317/// Variant of [`Min`] that considers NaN the smallest value.
318///
319/// [`Min`]: struct.Min.html
320#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
321pub struct MinTakeNaN;
322impl_identity!(MinTakeNaN, f32, std::f32::INFINITY, "Returns infinity.");
323impl_identity!(MinTakeNaN, f64, std::f64::INFINITY, "Returns infinity.");
324impl Commutative<f32> for MinTakeNaN {}
325impl Commutative<f64> for MinTakeNaN {}
326impl Operation<f32> for MinTakeNaN {
327    /// Returns the smallest of the two values.
328    ///
329    /// If either argument is NaN, this method returns NaN.
330    fn combine(&self, a: &f32, b: &f32) -> f32 {
331        if b > a || a.is_nan() { *a } else { *b }
332    }
333}
334impl Operation<f64> for MinTakeNaN {
335    /// Returns the smallest of the two values.
336    ///
337    /// If either argument is NaN, this method returns NaN.
338    fn combine(&self, a: &f64, b: &f64) -> f64 {
339        if b > a || a.is_nan() { *a } else { *b }
340    }
341}
342
343/// Variant of [`Max`] that considers NaN the smallest value.
344///
345/// [`Max`]: struct.Max.html
346#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
347pub struct MaxIgnoreNaN;
348impl_identity!(MaxIgnoreNaN, f32, std::f32::NAN, "Returns NaN.");
349impl_identity!(MaxIgnoreNaN, f64, std::f64::NAN, "Returns NaN.");
350impl Commutative<f32> for MaxIgnoreNaN {}
351impl Commutative<f64> for MaxIgnoreNaN {}
352impl Operation<f32> for MaxIgnoreNaN {
353    /// Returns the largest of the two values.
354    ///
355    /// If either argument is NaN, the other is returned.
356    fn combine(&self, a: &f32, b: &f32) -> f32 {
357        if b < a || b.is_nan() { *a } else { *b }
358    }
359}
360impl Operation<f64> for MaxIgnoreNaN {
361    /// Returns the largest of the two values.
362    ///
363    /// If either argument is NaN, the other is returned.
364    fn combine(&self, a: &f64, b: &f64) -> f64 {
365        if b < a || b.is_nan() { *a } else { *b }
366    }
367}
368
369/// Variant of [`Max`] that considers NaN the largest value.
370///
371/// [`Max`]: struct.Max.html
372#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
373pub struct MaxTakeNaN;
374impl_identity!(MaxTakeNaN, f32, std::f32::NEG_INFINITY, "Returns negative infinity.");
375impl_identity!(MaxTakeNaN, f64, std::f64::NEG_INFINITY, "Returns negative infinity.");
376impl Commutative<f32> for MaxTakeNaN {}
377impl Commutative<f64> for MaxTakeNaN {}
378impl Operation<f32> for MaxTakeNaN {
379    /// Returns the largest of the two values.
380    ///
381    /// If either argument is NaN, this method returns NaN.
382    fn combine(&self, a: &f32, b: &f32) -> f32 {
383        if b < a || a.is_nan() { *a } else { *b }
384    }
385}
386impl Operation<f64> for MaxTakeNaN {
387    /// Returns the largest of the two values.
388    ///
389    /// If either argument is NaN, this method returns NaN.
390    fn combine(&self, a: &f64, b: &f64) -> f64 {
391        if b < a || a.is_nan() { *a } else { *b }
392    }
393}
394
395impl_operation_infix!(And, bool, &&, "Returns the boolean and.");
396impl_identity!(And, bool, true, "Returns `true`.");
397
398impl_operation_infix!(Or, bool, ||, "Returns the boolean or.");
399impl_identity!(Or, bool, false, "Returns `false`.");
400
401impl_operation_infix!(Xor, bool, ^, "Returns the boolean xor.");
402impl_inverse!(Xor, bool, ^, "Returns the boolean xor.");
403impl_identity!(Xor, bool, false, "Returns `false`.");
404
405#[cfg(test)]
406mod tests {
407    use std::{f32, i32, u32};
408    use crate::ops::*;
409    #[test]
410    fn ops_nan() {
411        assert_eq!(MaxIgnoreNaN.combine_both(0.0, 1.0), 1.0);
412        assert_eq!(MaxIgnoreNaN.combine_both(1.0, 0.0), 1.0);
413        assert_eq!(MaxIgnoreNaN.combine_both(f32::NAN, 1.0), 1.0);
414        assert_eq!(MaxIgnoreNaN.combine_both(1.0, f32::NAN), 1.0);
415        assert_eq!(MaxIgnoreNaN.combine_both(f32::NAN, f32::NEG_INFINITY),
416            f32::NEG_INFINITY);
417        assert_eq!(MaxIgnoreNaN.combine_both(f32::NEG_INFINITY, f32::NAN),
418            f32::NEG_INFINITY);
419        assert!(MaxIgnoreNaN.combine_both(f32::NAN, f32::NAN).is_nan());
420
421        assert_eq!(MinIgnoreNaN.combine_both(0.0, 1.0), 0.0);
422        assert_eq!(MinIgnoreNaN.combine_both(1.0, 0.0), 0.0);
423        assert_eq!(MinIgnoreNaN.combine_both(f32::NAN, 1.0), 1.0);
424        assert_eq!(MinIgnoreNaN.combine_both(1.0, f32::NAN), 1.0);
425        assert_eq!(MinIgnoreNaN.combine_both(f32::NAN, f32::INFINITY), f32::INFINITY);
426        assert_eq!(MinIgnoreNaN.combine_both(f32::INFINITY, f32::NAN), f32::INFINITY);
427        assert!(MinIgnoreNaN.combine_both(f32::NAN, f32::NAN).is_nan());
428
429        assert_eq!(MaxTakeNaN.combine_both(0.0, 1.0), 1.0);
430        assert_eq!(MaxTakeNaN.combine_both(1.0, 0.0), 1.0);
431        assert!(MaxTakeNaN.combine_both(f32::NAN, f32::INFINITY).is_nan());
432        assert!(MaxTakeNaN.combine_both(f32::INFINITY, f32::NAN).is_nan());
433        assert!(MaxTakeNaN.combine_both(f32::NAN, f32::NEG_INFINITY).is_nan());
434        assert!(MaxTakeNaN.combine_both(f32::NEG_INFINITY, f32::NAN).is_nan());
435        assert!(MaxTakeNaN.combine_both(f32::NAN, f32::NAN).is_nan());
436
437        assert_eq!(MinTakeNaN.combine_both(0.0, 1.0), 0.0);
438        assert_eq!(MinTakeNaN.combine_both(1.0, 0.0), 0.0);
439        assert!(MinTakeNaN.combine_both(f32::NAN, f32::INFINITY).is_nan());
440        assert!(MinTakeNaN.combine_both(f32::INFINITY, f32::NAN).is_nan());
441        assert!(MinTakeNaN.combine_both(f32::NAN, f32::NEG_INFINITY).is_nan());
442        assert!(MinTakeNaN.combine_both(f32::NEG_INFINITY, f32::NAN).is_nan());
443        assert!(MinTakeNaN.combine_both(f32::NAN, f32::NAN).is_nan());
444    }
445    #[test]
446    fn ops_and_identity() {
447        for i in -200i32 ..= 200i32 {
448            assert_eq!(And.combine_both(i, And.identity()), i);
449        }
450        assert_eq!(And.combine_both(i32::MAX, And.identity()), i32::MAX);
451        assert_eq!(And.combine_both(i32::MIN, And.identity()), i32::MIN);
452        assert_eq!(And.combine_both(0i32, And.identity()), 0i32);
453
454        assert_eq!(And.combine_both(0u32, And.identity()), 0u32);
455        assert_eq!(And.combine_both(u32::MAX, And.identity()), u32::MAX);
456    }
457}
458
459/// Store several pieces of information in each node.
460#[derive(Clone,Copy,Eq,PartialEq,Ord,PartialOrd,Debug,Default,Hash)]
461pub struct Pair<A, B> {
462    a: A, b: B
463}
464impl<A, B> Pair<A, B> {
465    /// Create a pair operation.
466    pub fn wrap(a: A, b: B) -> Pair<A, B> {
467        Pair { a: a, b: b }
468    }
469    /// Returns the inner operations.
470    pub fn into_inner(self) -> (A, B) {
471        (self.a, self.b)
472    }
473}
474impl<TA, TB, A: Operation<TA>, B: Operation<TB>> Operation<(TA, TB)> for Pair<A, B> {
475    #[inline]
476    fn combine(&self, a: &(TA, TB), b: &(TA, TB)) -> (TA, TB) {
477        (self.a.combine(&a.0, &b.0), self.b.combine(&a.1, &b.1))
478    }
479    #[inline]
480    fn combine_mut(&self, a: &mut (TA, TB), b: &(TA, TB)) {
481        self.a.combine_mut(&mut a.0, &b.0);
482        self.b.combine_mut(&mut a.1, &b.1);
483    }
484    #[inline]
485    fn combine_mut2(&self, a: &(TA, TB), b: &mut (TA, TB)) {
486        self.a.combine_mut2(&a.0, &mut b.0);
487        self.b.combine_mut2(&a.1, &mut b.1);
488    }
489    #[inline]
490    fn combine_left(&self, a: (TA, TB), b: &(TA, TB)) -> (TA, TB) {
491        (self.a.combine_left(a.0, &b.0), self.b.combine_left(a.1, &b.1))
492    }
493    #[inline]
494    fn combine_right(&self, a: &(TA, TB), b: (TA, TB)) -> (TA, TB) {
495        (self.a.combine_right(&a.0, b.0), self.b.combine_right(&a.1, b.1))
496    }
497    #[inline]
498    fn combine_both(&self, a: (TA, TB), b: (TA, TB)) -> (TA, TB) {
499        (self.a.combine_both(a.0, b.0), self.b.combine_both(a.1, b.1))
500    }
501}
502impl<TA, TB, A: Invertible<TA>, B: Invertible<TB>> Invertible<(TA, TB)> for Pair<A, B> {
503    #[inline(always)]
504    fn uncombine(&self, a: &mut (TA, TB), b: &(TA, TB)) {
505        self.a.uncombine(&mut a.0, &b.0);
506        self.b.uncombine(&mut a.1, &b.1);
507    }
508}
509impl<TA, TB, A: Commutative<TA>, B: Commutative<TB>> Commutative<(TA, TB)> for Pair<A, B> {}
510impl<TA, TB, A: Identity<TA>, B: Identity<TB>> Identity<(TA,TB)> for Pair<A, B> {
511    fn identity(&self) -> (TA, TB) {
512        (self.a.identity(), self.b.identity())
513    }
514}
segment_tree/ops/mod.rs

segment_tree/ops/
mod.rs
