segment_tree/ops/
num.rs

1#[cfg(feature = "num-bigint")]
2mod bigint {
3
4    use crate::ops::{Operation, Commutative, Identity, Invertible};
5    use crate::ops::{Add, Mul};
6    use num_bigint::{BigInt, BigUint};
7
8    impl Operation<BigInt> for Add {
9        /// Returns the sum. This usually allocates memory.
10        fn combine(&self, a: &BigInt, b: &BigInt) -> BigInt {
11            a + b
12        }
13        /// Computes the sum while reusing memory in `a`.
14        fn combine_mut(&self, a: &mut BigInt, b: &BigInt) {
15            *a += b;
16        }
17        /// Computes the sum while reusing memory in `b`.
18        fn combine_mut2(&self, a: &BigInt, b: &mut BigInt) {
19            *b += a;
20        }
21        /// Computes the sum while reusing memory from `a`.
22        fn combine_left(&self, a: BigInt, b: &BigInt) -> BigInt {
23            a + b
24        }
25        /// Computes the sum while reusing memory from `b`.
26        fn combine_right(&self, a: &BigInt, b: BigInt) -> BigInt {
27            a + b
28        }
29        /// Computes the sum while reusing memory from the larger of `a` and `b`.
30        fn combine_both(&self, a: BigInt, b: BigInt) -> BigInt {
31            a + b
32        }
33    }
34    impl Commutative<BigInt> for Add {}
35    impl Identity<BigInt> for Add {
36        /// Returns zero.
37        fn identity(&self) -> BigInt {
38            0.into()
39        }
40    }
41    impl Invertible<BigInt> for Add {
42        /// Computes the difference, while reusing memory in `a`.
43        fn uncombine(&self, a: &mut BigInt, b: &BigInt) {
44            *a -= b;
45        }
46    }
47
48    impl Operation<BigUint> for Add {
49        /// Returns the sum. This usually allocates memory.
50        fn combine(&self, a: &BigUint, b: &BigUint) -> BigUint {
51            a + b
52        }
53        /// Computes the sum while reusing memory in `a`.
54        fn combine_mut(&self, a: &mut BigUint, b: &BigUint) {
55            *a += b;
56        }
57        /// Computes the sum while reusing memory in `b`.
58        fn combine_mut2(&self, a: &BigUint, b: &mut BigUint) {
59            *b += a;
60        }
61        /// Computes the sum while reusing memory from `a`.
62        fn combine_left(&self, a: BigUint, b: &BigUint) -> BigUint {
63            a + b
64        }
65        /// Computes the sum while reusing memory from `b`.
66        fn combine_right(&self, a: &BigUint, b: BigUint) -> BigUint {
67            a + b
68        }
69        /// Computes the sum while reusing memory from the larger of `a` and `b`.
70        fn combine_both(&self, a: BigUint, b: BigUint) -> BigUint {
71            a + b
72        }
73    }
74    impl Commutative<BigUint> for Add {}
75    impl Identity<BigUint> for Add {
76        /// Returns zero.
77        fn identity(&self) -> BigUint {
78            0u32.into()
79        }
80    }
81
82
83    impl Operation<BigInt> for Mul {
84        /// Returns the product. This usually allocates memory.
85        fn combine(&self, a: &BigInt, b: &BigInt) -> BigInt {
86            a * b
87        }
88        /// Computes the product while reusing memory in `a`.
89        fn combine_mut(&self, a: &mut BigInt, b: &BigInt) {
90            *a *= b;
91        }
92        /// Computes the product while reusing memory in `b`.
93        fn combine_mut2(&self, a: &BigInt, b: &mut BigInt) {
94            *b *= a;
95        }
96        /// Computes the product while reusing memory from `a`.
97        fn combine_left(&self, a: BigInt, b: &BigInt) -> BigInt {
98            a * b
99        }
100        /// Computes the product while reusing memory from `b`.
101        fn combine_right(&self, a: &BigInt, b: BigInt) -> BigInt {
102            a * b
103        }
104        /// Computes the product while reusing memory from the larger of `a` and `b`.
105        fn combine_both(&self, a: BigInt, b: BigInt) -> BigInt {
106            a * b
107        }
108    }
109    impl Commutative<BigInt> for Mul {}
110    impl Identity<BigInt> for Mul {
111        /// Returns one.
112        fn identity(&self) -> BigInt {
113            1.into()
114        }
115    }
116
117    impl Operation<BigUint> for Mul {
118        /// Returns the product. This usually allocates memory.
119        fn combine(&self, a: &BigUint, b: &BigUint) -> BigUint {
120            a * b
121        }
122        /// Computes the product while reusing memory in `a`.
123        fn combine_mut(&self, a: &mut BigUint, b: &BigUint) {
124            *a *= b;
125        }
126        /// Computes the product while reusing memory in `b`.
127        fn combine_mut2(&self, a: &BigUint, b: &mut BigUint) {
128            *b *= a;
129        }
130        /// Computes the product while reusing memory from `a`.
131        fn combine_left(&self, a: BigUint, b: &BigUint) -> BigUint {
132            a * b
133        }
134        /// Computes the product while reusing memory from `b`.
135        fn combine_right(&self, a: &BigUint, b: BigUint) -> BigUint {
136            a * b
137        }
138        /// Computes the product while reusing memory from the larger of `a` and `b`.
139        fn combine_both(&self, a: BigUint, b: BigUint) -> BigUint {
140            a * b
141        }
142    }
143    impl Commutative<BigUint> for Mul {}
144    impl Identity<BigUint> for Mul {
145        /// Returns zero.
146        fn identity(&self) -> BigUint {
147            1u32.into()
148        }
149    }
150}
151
segment_tree/ops/num.rs

segment_tree/ops/
num.rs
