amonoid 0.1.2

//! The [list monoid](List).

use std::borrow::Borrow;
use std::iter::FusedIterator;
use std::ops::Deref;

use crate::hom::graph::Graph;
use crate::hom::HomStaticBorrowed;
use crate::{Monoid, PreMonoidBorrowed};

/// Any list is a monoid, with concatenation as the operation and the empty list as the identity.
/// This is also known as the [free monoid](https://en.wikipedia.org/wiki/Free_monoid) over the element type (`Self::Item`).
pub trait List: Monoid {
	#[allow(missing_docs)]
	type Item;

	/// Construct a list from a single element.
	fn single(value: Self::Item) -> Self;
	/// Construct a list from an iterator.
	///
	/// The iterator should be assumed to terminate and this method should stop on the first `None`.
	/// (The default impl does this)
	fn from_items(iter: impl IntoIterator<Item = Self::Item>) -> Self {
		Self::combine_iter(iter.into_iter().map(Self::single))
	}

	/// Push a single item onto the end of the list.
	fn push(&mut self, value: Self::Item) {
		self.combine_assign(Self::single(value));
	}
	/// Extend the list from an iterator.
	///
	/// The iterator should be assumed to terminate and this method should stop on the first `None`.
	/// (The default impl does this)
	fn extend(&mut self, iter: impl IntoIterator<Item = Self::Item>) {
		self.combine_iter_assign(iter.into_iter().map(Self::single));
	}

	/// Returns an iterator over the elements of this list, consuming `self`.
	fn into_items(self) -> impl FusedIterator<Item = Self::Item>;
}

/// A [`Borrow`] of a [`List`] that can iterate over its items by (sort-of) reference.
#[allow(clippy::len_without_is_empty)]
pub trait ListBorrowed: PreMonoidBorrowed<MonoidOwned: List> {
	/// A type that can be treated as a reference to `Self::MonoidOwned::Item`.
	type ItemRef<'a>: Borrow<<Self::MonoidOwned as List>::Item>
	where
		Self: 'a;

	/// Returns an iterator over the elements of this list, by sort-of reference.
	fn items(&self) -> impl FusedIterator<Item = Self::ItemRef<'_>>;

	/// Returns the length of this list.
	fn len(&self) -> usize {
		self.items().count()
	}
}

impl<L: List + Deref<Target: ListBorrowed<MonoidOwned = L>>> ListBorrowed for L {
	type ItemRef<'a> = <L::Target as ListBorrowed>::ItemRef<'a>
	    where
		    Self: 'a;

	fn items(&self) -> impl FusedIterator<Item = Self::ItemRef<'_>> {
		L::Target::items(self)
	}
}

/// Extension methods that any list has
pub trait ListExt: List {
	/// Construct an empty list. This is an alias for [`Self::ident`](Monoid::ident).
	#[inline]
	fn empty() -> Self {
		Self::ident()
	}

	/// Concatenate two lists. This is an alias for [`Self::combine`](Monoid::combine).
	#[inline]
	fn concat(self, rhs: Self) -> Self {
		self.combine(rhs)
	}
}
impl<L: List> ListExt for L {}

impl<T> List for Vec<T> {
	type Item = T;

	fn single(value: T) -> Self {
		vec![value]
	}
	fn from_items(iter: impl IntoIterator<Item = T>) -> Self {
		<Self as FromIterator<T>>::from_iter(iter)
	}

	fn into_items(self) -> impl FusedIterator<Item = T> {
		<Self as IntoIterator>::into_iter(self)
	}
}
impl<T> ListBorrowed for [T] {
	type ItemRef<'a> = &'a T
	where T: 'a;

	fn items(&self) -> impl FusedIterator<Item = Self::ItemRef<'_>> {
		<[T]>::iter(self)
	}

	fn len(&self) -> usize {
		<Self>::len(self)
	}
}

impl List for String {
	type Item = char;

	fn single(value: char) -> Self {
		value.into()
	}
	fn from_items(iter: impl IntoIterator<Item = char>) -> Self {
		<Self as FromIterator<char>>::from_iter(iter)
	}

	fn into_items(self) -> impl FusedIterator<Item = char> {
		IntoIterator::into_iter(self.chars().collect::<Vec<_>>())
	}
}
impl ListBorrowed for str {
	type ItemRef<'a> = char;

	fn items(&self) -> impl FusedIterator<Item = Self::ItemRef<'_>> {
		self.chars()
	}
}

impl<L: List, H: HomStaticBorrowed<L>> Graph<L, H> {
	/// Push a single item onto the end of the input.
	pub fn push_input(&mut self, input: L::Item) {
		self.input_mut().push(input);
	}
}