differential_dataflow/
difference.rs1pub trait IsZero {
15 fn is_zero(&self) -> bool;
24}
25
26pub trait Semigroup<Rhs: ?Sized = Self> : Clone + IsZero {
38 fn plus_equals(&mut self, rhs: &Rhs);
40}
41
42impl<'a, S, T: Semigroup<S>> Semigroup<&'a S> for T {
44 fn plus_equals(&mut self, rhs: &&'a S) {
45 self.plus_equals(&**rhs);
46 }
47}
48
49pub trait Monoid : Semigroup {
51 fn zero() -> Self;
53}
54
55pub trait Abelian : Monoid {
61 fn negate(&mut self);
63}
64
65pub trait Multiply<Rhs = Self> {
67 type Output;
69 fn multiply(self, rhs: &Rhs) -> Self::Output;
71}
72
73macro_rules! builtin_implementation {
75 ($t:ty) => {
76 impl IsZero for $t {
77 #[inline] fn is_zero(&self) -> bool { self == &0 }
78 }
79 impl Semigroup for $t {
80 #[inline] fn plus_equals(&mut self, rhs: &Self) { *self += rhs; }
81 }
82
83 impl Monoid for $t {
84 #[inline] fn zero() -> Self { 0 }
85 }
86
87 impl Multiply<Self> for $t {
88 type Output = Self;
89 fn multiply(self, rhs: &Self) -> Self { self * rhs}
90 }
91 };
92}
93
94macro_rules! builtin_abelian_implementation {
95 ($t:ty) => {
96 impl Abelian for $t {
97 #[inline] fn negate(&mut self) { *self = -*self; }
98 }
99 };
100}
101
102builtin_implementation!(i8);
103builtin_implementation!(i16);
104builtin_implementation!(i32);
105builtin_implementation!(i64);
106builtin_implementation!(i128);
107builtin_implementation!(isize);
108builtin_implementation!(u8);
109builtin_implementation!(u16);
110builtin_implementation!(u32);
111builtin_implementation!(u64);
112builtin_implementation!(u128);
113builtin_implementation!(usize);
114
115builtin_abelian_implementation!(i8);
116builtin_abelian_implementation!(i16);
117builtin_abelian_implementation!(i32);
118builtin_abelian_implementation!(i64);
119builtin_abelian_implementation!(i128);
120builtin_abelian_implementation!(isize);
121
122macro_rules! wrapping_implementation {
124 ($t:ty) => {
125 impl IsZero for $t {
126 #[inline] fn is_zero(&self) -> bool { self == &std::num::Wrapping(0) }
127 }
128 impl Semigroup for $t {
129 #[inline] fn plus_equals(&mut self, rhs: &Self) { *self += rhs; }
130 }
131
132 impl Monoid for $t {
133 #[inline] fn zero() -> Self { std::num::Wrapping(0) }
134 }
135
136 impl Abelian for $t {
137 #[inline] fn negate(&mut self) { *self = -*self; }
138 }
139
140 impl Multiply<Self> for $t {
141 type Output = Self;
142 fn multiply(self, rhs: &Self) -> Self { self * rhs}
143 }
144 };
145}
146
147wrapping_implementation!(std::num::Wrapping<i8>);
148wrapping_implementation!(std::num::Wrapping<i16>);
149wrapping_implementation!(std::num::Wrapping<i32>);
150wrapping_implementation!(std::num::Wrapping<i64>);
151wrapping_implementation!(std::num::Wrapping<i128>);
152wrapping_implementation!(std::num::Wrapping<isize>);
153
154
155pub use self::present::Present;
156mod present {
157 use serde::{Deserialize, Serialize};
158
159 #[derive(Copy, Ord, PartialOrd, Eq, PartialEq, Debug, Clone, Serialize, Deserialize, Hash)]
168 pub struct Present;
169
170 impl<T: Clone> super::Multiply<T> for Present {
171 type Output = T;
172 fn multiply(self, rhs: &T) -> T {
173 rhs.clone()
174 }
175 }
176
177 impl super::IsZero for Present {
178 fn is_zero(&self) -> bool { false }
179 }
180
181 impl super::Semigroup for Present {
182 fn plus_equals(&mut self, _rhs: &Self) { }
183 }
184}
185
186mod tuples {
188
189 use super::{IsZero, Semigroup, Monoid, Abelian, Multiply};
190
191 macro_rules! tuple_implementation {
193 ( ($($name:ident)*), ($($name2:ident)*) ) => (
194
195 impl<$($name: IsZero),*> IsZero for ($($name,)*) {
196 #[allow(unused_mut)]
197 #[allow(non_snake_case)]
198 #[inline] fn is_zero(&self) -> bool {
199 let mut zero = true;
200 let ($(ref $name,)*) = *self;
201 $( zero &= $name.is_zero(); )*
202 zero
203 }
204 }
205
206 impl<$($name: Semigroup),*> Semigroup for ($($name,)*) {
207 #[allow(non_snake_case)]
208 #[inline] fn plus_equals(&mut self, rhs: &Self) {
209 let ($(ref mut $name,)*) = *self;
210 let ($(ref $name2,)*) = *rhs;
211 $($name.plus_equals($name2);)*
212 }
213 }
214
215 impl<$($name: Monoid),*> Monoid for ($($name,)*) {
216 #[allow(non_snake_case)]
217 #[inline] fn zero() -> Self {
218 ( $($name::zero(), )* )
219 }
220 }
221
222 impl<$($name: Abelian),*> Abelian for ($($name,)*) {
223 #[allow(non_snake_case)]
224 #[inline] fn negate(&mut self) {
225 let ($(ref mut $name,)*) = self;
226 $($name.negate();)*
227 }
228 }
229
230 impl<T, $($name: Multiply<T>),*> Multiply<T> for ($($name,)*) {
231 type Output = ($(<$name as Multiply<T>>::Output,)*);
232 #[allow(unused_variables)]
233 #[allow(non_snake_case)]
234 #[inline] fn multiply(self, rhs: &T) -> Self::Output {
235 let ($($name,)*) = self;
236 ( $($name.multiply(rhs), )* )
237 }
238 }
239 )
240 }
241
242 tuple_implementation!((), ());
243 tuple_implementation!((A1), (A2));
244 tuple_implementation!((A1 B1), (A2 B2));
245 tuple_implementation!((A1 B1 C1), (A2 B2 C2));
246 tuple_implementation!((A1 B1 C1 D1), (A2 B2 C2 D2));
247}
248
249mod vector {
251
252 use super::{IsZero, Semigroup, Monoid, Abelian, Multiply};
253
254 impl<R: IsZero> IsZero for Vec<R> {
255 fn is_zero(&self) -> bool {
256 self.iter().all(|x| x.is_zero())
257 }
258 }
259
260 impl<R: Semigroup> Semigroup for Vec<R> {
261 fn plus_equals(&mut self, rhs: &Self) {
262 self.plus_equals(&rhs[..])
263 }
264 }
265
266 impl<R: Semigroup> Semigroup<[R]> for Vec<R> {
267 fn plus_equals(&mut self, rhs: &[R]) {
268 for (index, update) in rhs.iter().enumerate().take(self.len()) {
270 self[index].plus_equals(update);
271 }
272
273 while self.len() < rhs.len() {
275 let element = &rhs[self.len()];
276 self.push(element.clone());
277 }
278 }
279 }
280
281 #[cfg(test)]
282 mod tests {
283 use crate::difference::Semigroup;
284
285 #[test]
286 fn test_semigroup_vec() {
287 let mut a = vec![1,2,3];
288 a.plus_equals([1,1,1,1].as_slice());
289 assert_eq!(vec![2,3,4,1], a);
290 }
291 }
292
293 impl<R: Monoid> Monoid for Vec<R> {
294 fn zero() -> Self {
295 Self::new()
296 }
297 }
298
299 impl<R: Abelian> Abelian for Vec<R> {
300 fn negate(&mut self) {
301 for update in self.iter_mut() {
302 update.negate();
303 }
304 }
305 }
306
307 impl<T, R: Multiply<T>> Multiply<T> for Vec<R> {
308 type Output = Vec<<R as Multiply<T>>::Output>;
309 fn multiply(self, rhs: &T) -> Self::Output {
310 self.into_iter()
311 .map(|x| x.multiply(rhs))
312 .collect()
313 }
314 }
315}