amonoid 0.1.2

use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::ffi::OsString;
use std::hash::Hash;

/// A [monoid](https://en.wikipedia.org/wiki/Monoid).
pub trait Monoid: Sized {
	/// The identity element for [`combine`](Self::combine).
	fn ident() -> Self;

	/// Combine an element with another element.
	/// This must obey
	/// - the left and right identity laws, that is `combine(ident(), x) == x` and `combine(x, ident()) == x` for all `x`.
	/// - the associative law, that is `combine(combine(a, b), c) == combine(a, combine(b, c))` for all `a, b, c`.
	fn combine(self, rhs: Self) -> Self;

	/// Like [`combine`](Self::combine), but assigns the result to `self`.
	///
	/// The default impl uses [`std::mem::replace`] with [`Self::ident`].
	fn combine_assign(&mut self, rhs: Self) {
		*self = std::mem::replace(self, Self::ident()).combine(rhs);
	}

	/// Like [`combine`](Self::combine), but assigns the result to `rhs`.
	///
	/// The default impl uses [`std::mem::replace`] with [`Self::ident`].
	fn combine_assign_to(self, rhs: &mut Self) {
		*rhs = self.combine(std::mem::replace(rhs, Self::ident()));
	}

	/// An overridable method to provide some optimization based on the fact that [`combine`](Self::combine) is associative.
	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.reduce(Self::combine).unwrap_or_else(Self::ident)
	}

	/// Like [`combine_iter`](Self::combine_iter), but assigns the result to `self`.
	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.combine_assign(Self::combine_iter(iter))
	}
}

/// The unit type (type with one value) is a monoid, known as the [trivial], or [zero], monoid.
///
/// [trivial]: https://en.wikipedia.org/wiki/Trivial_monoid
/// [zero]: https://en.wikipedia.org/wiki/Initial_and_terminal_objects
impl Monoid for () {
	#[inline]
	fn ident() {}

	#[inline]
	fn combine(self, (): Self) {}

	#[inline]
	fn combine_assign(&mut self, (): Self) {}

	#[inline]
	fn combine_assign_to(self, (): &mut Self) {}

	#[inline]
	fn combine_iter<I: Iterator<Item = Self>>(_iter: I) {}

	#[inline]
	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, _iter: I) {}
}

/// A tuple of two monoids is a monoid (with the operation acting componentwise), known as the [product] monoid.
///
/// [product]: https://en.wikipedia.org/wiki/Direct_product
impl<M1: Monoid, M2: Monoid> Monoid for (M1, M2) {
	#[inline]
	fn ident() -> Self {
		(M1::ident(), M2::ident())
	}

	#[inline]
	fn combine(self, rhs: Self) -> Self {
		(self.0.combine(rhs.0), self.1.combine(rhs.1))
	}

	#[inline]
	fn combine_assign(&mut self, rhs: Self) {
		self.0.combine_assign(rhs.0);
		self.1.combine_assign(rhs.1);
	}

	fn combine_assign_to(self, rhs: &mut Self) {
		self.0.combine_assign_to(&mut rhs.0);
		self.1.combine_assign_to(&mut rhs.1);
	}
}

/// The opposite monoid ([wiki](https://en.wikipedia.org/wiki/Monoid#Examples)), where `combine(a, b) = M::combine(b, a)`.
#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct Opposite<M: Monoid>(pub M);

impl<M: Monoid> Monoid for Opposite<M> {
	fn ident() -> Self {
		Self(M::ident())
	}

	fn combine(self, rhs: Self) -> Self {
		Self(M::combine(rhs.0, self.0))
	}

	fn combine_assign(&mut self, rhs: Self) {
		M::combine_assign_to(rhs.0, &mut self.0);
	}

	fn combine_assign_to(self, rhs: &mut Self) {
		rhs.0.combine_assign(self.0);
	}

	// TODO: if specialization ever becomes stable, use it here to specialize `combine_iter` on `DoubleEndedIterator`.
}

/// An `Option<impl Monoid>` is also a monoid with `None` as the identity.
///
/// Actually, the inner type wouldn't even need to be a monoid
/// (since the `Option` provides the identity element, so the inner type would only need to be a [semigroup]),
/// but this crate is strictly about monoids, so it lacks a `Semigroup` trait.
/// Thus, the impl is a bit more restrictive than it would theoretically need to be.
///
/// [semigroup]: https://en.wikipedia.org/wiki/Semigroup
impl<M: Monoid> Monoid for Option<M> {
	#[inline]
	fn ident() -> Self {
		None
	}

	fn combine(self, rhs: Self) -> Self {
		self.zip(rhs).map(|(l, r)| l.combine(r))
	}

	fn combine_assign(&mut self, rhs: Self) {
		if let Some(rhs) = rhs {
			match self {
				None => *self = Some(rhs),
				Some(lhs) => lhs.combine_assign(rhs),
			}
		}
	}

	fn combine_assign_to(self, rhs: &mut Self) {
		if let Some(lhs) = self {
			match rhs {
				None => *rhs = Some(lhs),
				Some(rhs) => lhs.combine_assign_to(rhs),
			}
		}
	}

	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.flatten().reduce(M::combine)
	}
}

#[cfg(feature = "syn")]
/// [`syn::Error`] represents a non-empty list of [`compile_error!`] statements
/// and [`syn::Error::combine`] acts as concatenation.
/// This makes `syn::Error` into a semigroup
/// and `Option<syn::Error>` thus into a monoid,
/// as described [here](#impl-Monoid-for-Option<M>).
impl Monoid for Option<syn::Error> {
	#[inline]
	fn ident() -> Self {
		None
	}

	fn combine(self, rhs: Self) -> Self {
		self.zip(rhs).map(|(mut l, r)| {
			l.combine(r);
			l
		})
	}

	fn combine_assign(&mut self, rhs: Self) {
		if let Some(rhs) = rhs {
			match self {
				None => *self = Some(rhs),
				Some(lhs) => lhs.combine(rhs),
			}
		}
	}

	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.flatten().reduce(|mut l, r| {
			l.combine(r);
			l
		})
	}
}

/// The monoid of lists of `T` with concatenation as the operation,
/// also known as the [free monoid] on `T`.
///
/// [free monoid]: https://en.wikipedia.org/wiki/Free_monoid
impl<T> Monoid for Vec<T> {
	#[inline]
	fn ident() -> Self {
		Vec::new()
	}

	#[inline]
	fn combine(mut self, mut rhs: Self) -> Self {
		self.append(&mut rhs);
		self
	}

	#[inline]
	fn combine_assign(&mut self, mut rhs: Self) {
		self.append(&mut rhs);
	}

	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.flatten().collect()
	}

	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.extend(iter.flatten());
	}
}

/// `String` is just a different encoding of `Vec<char>`
/// (see [`impl Monoid for Vec<T>`](Monoid#impl-Monoid-for-Vec<T>) for details).
impl Monoid for String {
	#[inline]
	fn ident() -> Self {
		String::new()
	}

	#[inline]
	fn combine(self, rhs: Self) -> Self {
		self + &rhs
	}

	#[inline]
	fn combine_assign(&mut self, rhs: Self) {
		self.push_str(&rhs);
	}

	#[inline]
	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.collect()
	}

	#[inline]
	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.extend(iter);
	}
}

/// `OsString` is just a different encoding of `Vec<Something>` (What `Something` is depends on the OS)
/// (see [`impl Monoid for Vec<T>`](Monoid#impl-Monoid-for-Vec<T>) for details).
impl Monoid for OsString {
	#[inline]
	fn ident() -> Self {
		OsString::new()
	}

	#[inline]
	fn combine(mut self, rhs: Self) -> Self {
		self.push(rhs);
		self
	}

	#[inline]
	fn combine_assign(&mut self, rhs: Self) {
		self.push(rhs);
	}

	#[inline]
	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.collect()
	}

	#[inline]
	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.extend(iter);
	}
}

/// Finite sets with elements of type `T` form a monoid under set union.
impl<T: Hash + Eq> Monoid for HashSet<T> {
	#[inline]
	fn ident() -> Self {
		HashSet::new()
	}

	#[inline]
	fn combine(mut self, rhs: Self) -> Self {
		self.extend(rhs);
		self
	}

	#[inline]
	fn combine_assign(&mut self, rhs: Self) {
		self.extend(rhs);
	}

	// note: `Self::combine` is commutative.
	#[inline]
	fn combine_assign_to(self, rhs: &mut Self) {
		rhs.extend(self);
	}

	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.flatten().collect()
	}

	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.extend(iter.flatten())
	}
}

/// Finite sets with elements of type `T` form a monoid under set union.
impl<T: Ord> Monoid for BTreeSet<T> {
	#[inline]
	fn ident() -> Self {
		BTreeSet::new()
	}

	#[inline]
	fn combine(mut self, mut rhs: Self) -> Self {
		self.append(&mut rhs);
		self
	}

	#[inline]
	fn combine_assign(&mut self, mut rhs: Self) {
		self.append(&mut rhs);
	}

	// note: `Self::combine` is commutative.
	#[inline]
	fn combine_assign_to(mut self, rhs: &mut Self) {
		rhs.append(&mut self);
	}

	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		iter.flatten().collect()
	}

	fn combine_iter_assign<I: Iterator<Item = Self>>(&mut self, iter: I) {
		self.extend(iter.flatten())
	}
}

/// Partial functions from any set to a monoid form a monoid
/// under union of domains and (if needed) combination of function values.
impl<K: Hash + Eq, M: Monoid> Monoid for HashMap<K, M> {
	#[inline]
	fn ident() -> Self {
		HashMap::new()
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine(mut self, rhs: Self) -> Self {
		self.combine_assign(rhs);
		self
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine_assign(&mut self, rhs: Self) {
		use std::collections::hash_map::Entry;

		for (k, vr) in rhs {
			match self.entry(k) {
				Entry::Occupied(e) => {
					let (k, vl) = e.remove_entry();
					self.insert(k, vl.combine(vr));
				}
				Entry::Vacant(e) => {
					e.insert(vr);
				}
			}
		}
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine_assign_to(self, rhs: &mut Self) {
		use std::collections::hash_map::Entry;

		for (k, vl) in self {
			match rhs.entry(k) {
				Entry::Occupied(e) => {
					let (k, vr) = e.remove_entry();
					rhs.insert(k, vl.combine(vr));
				}
				Entry::Vacant(e) => {
					e.insert(vl);
				}
			}
		}
	}
}

/// Partial functions from any set to a monoid form a monoid
/// under union of domains and (if needed) combination of function values.
impl<K: Ord, M: Monoid> Monoid for BTreeMap<K, M> {
	#[inline]
	fn ident() -> Self {
		BTreeMap::new()
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine(mut self, rhs: Self) -> Self {
		self.combine_assign(rhs);
		self
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine_assign(&mut self, rhs: Self) {
		use std::collections::btree_map::Entry;

		for (k, vr) in rhs {
			match self.entry(k) {
				Entry::Occupied(e) => {
					let (k, vl) = e.remove_entry();
					self.insert(k, vl.combine(vr));
				}
				Entry::Vacant(e) => {
					e.insert(vr);
				}
			}
		}
	}

	/// Use with caution; This might not be a very efficient operation.
	fn combine_assign_to(self, rhs: &mut Self) {
		use std::collections::btree_map::Entry;

		for (k, vl) in self {
			match rhs.entry(k) {
				Entry::Occupied(e) => {
					let (k, vr) = e.remove_entry();
					rhs.insert(k, vl.combine(vr));
				}
				Entry::Vacant(e) => {
					e.insert(vl);
				}
			}
		}
	}
}

/// Functions `T -> T` are monoids under composition.
impl<'a, T: 'a> Monoid for Box<dyn 'a + FnMut(T) -> T> {
	fn ident() -> Self {
		Box::new(std::convert::identity)
	}

	fn combine(mut self, mut rhs: Self) -> Self {
		Box::new(move |t| (*self)((*rhs)(t)))
	}
}
/// Functions `T -> T` are monoids under composition.
impl<'a, T: 'a> Monoid for Box<dyn 'a + Fn(T) -> T> {
	fn ident() -> Self {
		Box::new(std::convert::identity)
	}

	fn combine(self, rhs: Self) -> Self {
		Box::new(move |t| (*self)((*rhs)(t)))
	}
}