1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//! In mathematics, a semigroup is an algebraic structure consisting of a set together with an
//! associative binary operation. A semigroup generalizes a monoid in that there might not exist an
//! identity element. It also (originally) generalized a group (a monoid with all inverses) to a
//! type where every element did not have to have an inverse, thus the name semigroup.

use std::collections::HashMap;
use std::hash::BuildHasher;
use std::hash::Hash;
use std::iter::Extend;



// =================
// === Semigroup ===
// =================

/// Mutable Semigroup definition. Impls should satisfy the associativity law:
/// `x.concat(y.concat(z)) = x.concat(y).concat(z)`, in symbolic form:
/// `x <> (y <> z) = (x <> y) <> z`
pub trait PartialSemigroup<T> : Clone {
    /// An associative operation.
    fn concat_mut(&mut self, other:T);

    /// An associative operation.
    fn concat_ref(&self, other:T) -> Self where Self:Clone {
        self.clone().concat(other)
    }

    /// An associative operation.
    fn concat(mut self, other:T) -> Self {
        self.concat_mut(other);
        self
    }
}

impl<T>   Semigroup for T where T : PartialSemigroup<T> + for<'t> PartialSemigroup<&'t T> {}
pub trait Semigroup : PartialSemigroup<Self> + for<'t> PartialSemigroup<&'t Self> {
    fn partial_times_mut(&mut self, n:usize) {
        let val = self.clone();
        for _ in 0..n-1 {
            self.concat_mut(&val)
        }
    }

    fn partial_times(mut self, n:usize) -> Self {
        self.partial_times_mut(n);
        self
    }
}



// ====================
// === Stdlib Impls ===
// ====================

// === Option ===

impl<T:Semigroup> PartialSemigroup<&Option<T>> for Option<T> {
    fn concat_mut(&mut self, other:&Self) {
        if let Some(r) = other {
            match self {
                None    => *self = Some(r.clone()),
                Some(l) => l.concat_mut(r)
            }
        }
    }
}

impl<T:Semigroup> PartialSemigroup<Option<T>> for Option<T> {
    fn concat_mut(&mut self, other:Self) {
        if let Some(r) = other {
            match self {
                None    => *self = Some(r),
                Some(l) => l.concat_mut(r)
            }
        }
    }
}


// === HashMap ===

impl<K,V,S> PartialSemigroup<&HashMap<K,V,S>> for HashMap<K,V,S>
where K : Eq + Hash + Clone,
      V : Semigroup,
      S : Clone + BuildHasher {
    fn concat_mut(&mut self, other:&Self) {
        for (key,new_val) in other {
            let key = key.clone();
            self.entry(key)
                .and_modify(|val| val.concat_mut(new_val))
                .or_insert_with(|| new_val.clone());
        }
    }
}

impl<K,V,S> PartialSemigroup<HashMap<K,V,S>> for HashMap<K,V,S>
    where K : Eq + Hash + Clone,
          V : Semigroup,
          S : Clone + BuildHasher {
    fn concat_mut(&mut self, other:Self) {
        for (key,new_val) in other {
            self.entry(key)
                .and_modify(|val| val.concat_mut(&new_val))
                .or_insert(new_val);
        }
    }
}


// === Vec ===

impl<T:Clone> PartialSemigroup<&Vec<T>> for Vec<T> {
    fn concat_mut(&mut self, other:&Self) {
        self.extend(other.iter().cloned())
    }
}

impl<T:Clone> PartialSemigroup<Vec<T>> for Vec<T> {
    fn concat_mut(&mut self, other:Self) {
        self.extend(other.into_iter())
    }
}



// =============
// === Tests ===
// =============

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn option() {
        assert_eq!(None::<Vec<usize>>.concat(&None)     , None);
        assert_eq!(Some(vec![1]).concat(&None)          , Some(vec![1]));
        assert_eq!(None.concat(&Some(vec![1]))          , Some(vec![1]));
        assert_eq!(Some(vec![1]).concat(&Some(vec![2])) , Some(vec![1,2]));
    }
}