use super::*;
use core::fmt;
use scale::Error as DecodeError;

pub trait MapLike<K, V> {
	fn insert(&mut self, k: K, v: V) -> Option<V>;
	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>);
	fn contains_key(&self, t: &K) -> bool;
	fn remove(&mut self, t: &K) -> Option<V>;
	fn get(&self, k: &K) -> Option<&V>;
	fn get_mut(&mut self, k: &K) -> Option<&mut V>;
	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
	where
		K: 'a;
}

#[cfg(feature = "std")]
impl<K: Eq + std::hash::Hash, V> MapLike<K, V> for std::collections::HashMap<K, V> {
	fn insert(&mut self, k: K, v: V) -> Option<V> {
		std::collections::HashMap::<K, V>::insert(self, k, v)
	}
	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
		<std::collections::HashMap<K, V> as Extend<(K, V)>>::extend(self, iter)
	}
	fn contains_key(&self, k: &K) -> bool {
		std::collections::HashMap::<K, V>::contains_key(self, k)
	}
	fn remove(&mut self, k: &K) -> Option<V> {
		std::collections::HashMap::<K, V>::remove(self, k)
	}
	fn get(&self, k: &K) -> Option<&V> {
		std::collections::HashMap::<K, V>::get(self, k)
	}
	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
		std::collections::HashMap::<K, V>::get_mut(self, k)
	}
	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
	where
		K: 'a,
	{
		std::collections::HashMap::<K, V>::keys(self)
	}
}

impl<K: Eq + PartialEq + Ord + PartialOrd, V> MapLike<K, V> for alloc::collections::BTreeMap<K, V> {
	fn insert(&mut self, k: K, v: V) -> Option<V> {
		alloc::collections::BTreeMap::<K, V>::insert(self, k, v)
	}
	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
		<alloc::collections::BTreeMap<K, V> as Extend<(K, V)>>::extend(self, iter)
	}
	fn contains_key(&self, k: &K) -> bool {
		alloc::collections::BTreeMap::<K, V>::contains_key(self, k)
	}
	fn remove(&mut self, k: &K) -> Option<V> {
		alloc::collections::BTreeMap::<K, V>::remove(self, k)
	}
	fn get(&self, k: &K) -> Option<&V> {
		alloc::collections::BTreeMap::<K, V>::get(self, k)
	}
	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
		alloc::collections::BTreeMap::<K, V>::get_mut(self, k)
	}
	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
	where
		K: 'a,
	{
		alloc::collections::BTreeMap::<K, V>::keys(self)
	}
}

#[derive(Clone, Encode, Eq, PartialEq, Ord, PartialOrd)]
pub struct VecMap<K, V>(Vec<(K, V)>);
impl<K: Eq + PartialEq + Ord + PartialOrd, V> VecMap<K, V> {
	pub fn new() -> Self {
		Self(Vec::new())
	}
	pub fn from_sorted(v: Vec<(K, V)>) -> Result<Self, ()> {
		let Some((first, _)) = v.first() else { return Ok(Self::new()) };
		v.iter()
			.skip(1)
			.try_fold(first, |a, (e, _)| if a < e { Some(e) } else { None })
			.ok_or(())?;
		Ok(Self(v))
	}
	pub fn len(&self) -> usize {
		self.0.len()
	}
	pub fn is_empty(&self) -> bool {
		self.0.is_empty()
	}
	pub fn iter(&self) -> core::slice::Iter<(K, V)> {
		self.0.iter()
	}
	pub fn iter_mut(&mut self) -> core::slice::IterMut<(K, V)> {
		self.0.iter_mut()
	}
	pub fn keys(&self) -> impl Iterator<Item = &K> {
		self.0.iter().map(|(k, _)| k)
	}
	pub fn values(&self) -> impl Iterator<Item = &V> {
		self.0.iter().map(|(_, v)| v)
	}
	pub fn get(&self, k: &K) -> Option<&V> {
		self.0.binary_search_by(|x| x.0.cmp(k)).ok().map(|i| &self.0[i].1)
	}
	pub fn get_mut(&mut self, k: &K) -> Option<&mut V> {
		self.0.binary_search_by(|x| x.0.cmp(k)).ok().map(move |i| &mut self.0[i].1)
	}
	pub fn map<U>(self, mut f: impl FnMut(K, V) -> U) -> Vec<U> {
		self.0.into_iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
	}
	pub fn map_ref<U>(&self, mut f: impl FnMut(&K, &V) -> U) -> Vec<U> {
		self.0.iter().map(|(k, v)| f(k, v)).collect::<Vec<_>>()
	}
	pub fn to_vec(&self) -> Vec<(K, V)>
	where
		K: Clone,
		V: Clone,
	{
		self.0.clone()
	}
	pub fn into_vec(self) -> Vec<(K, V)> {
		self.0
	}
	pub fn insert(&mut self, k: K, v: V) -> Option<(K, V)> {
		match self.0.binary_search_by(|x| x.0.cmp(&k)) {
			Ok(i) => Some(core::mem::replace(&mut self.0[i], (k, v))),
			Err(i) => {
				self.0.insert(i, (k, v));
				None
			},
		}
	}
	pub fn extend(&mut self, iter: impl IntoIterator<Item = (K, V)>) {
		self.0.extend(iter);
		self.0.sort_unstable_by(|x, y| x.0.cmp(&y.0));
		self.0.dedup_by(|x, y| x.0 == y.0);
	}
	pub fn contains_key(&self, k: &K) -> bool {
		self.0.binary_search_by(|x| x.0.cmp(k)).is_ok()
	}
	pub fn remove(&mut self, k: &K) -> Option<(K, V)> {
		match self.0.binary_search_by(|x| x.0.cmp(k)) {
			Ok(i) => Some(self.0.remove(i)),
			Err(_) => None,
		}
	}
	pub fn retain(&mut self, mut f: impl FnMut(&K, &V) -> bool) {
		self.0.retain(|x| f(&x.0, &x.1));
	}
}

impl<K: Eq + PartialEq + Ord + PartialOrd, V> MapLike<K, V> for VecMap<K, V> {
	fn insert(&mut self, k: K, v: V) -> Option<V> {
		VecMap::<K, V>::insert(self, k, v).map(|(_, v)| v)
	}
	fn extend(&mut self, iter: impl Iterator<Item = (K, V)>) {
		VecMap::<K, V>::extend(self, iter)
	}
	fn contains_key(&self, k: &K) -> bool {
		VecMap::<K, V>::contains_key(self, k)
	}
	fn remove(&mut self, k: &K) -> Option<V> {
		VecMap::<K, V>::remove(self, k).map(|x| x.1)
	}
	fn get(&self, k: &K) -> Option<&V> {
		VecMap::<K, V>::get(self, k)
	}
	fn get_mut(&mut self, k: &K) -> Option<&mut V> {
		VecMap::<K, V>::get_mut(self, k)
	}
	fn keys<'a>(&'a self) -> impl Iterator<Item = &'a K>
	where
		K: 'a,
	{
		VecMap::<K, V>::keys(self)
	}
}

impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for VecMap<K, V> {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		match self.0.len() {
			0 => write!(f, "[]"),
			_ => {
				write!(f, "[{:?}=>{:?}", self.0[0].0, self.0[0].1)?;
				for i in 1..self.0.len() {
					write!(f, ", {:?}=>{:?}", self.0[i].0, self.0[i].1)?;
				}
				write!(f, "]")
			},
		}
	}
}

impl<K: fmt::Display, V: fmt::Display> fmt::Display for VecMap<K, V> {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		match self.0.len() {
			0 => write!(f, "[]"),
			_ => {
				write!(f, "[{}=>{}", self.0[0].0, self.0[0].1)?;
				for i in 1..self.0.len() {
					write!(f, ", {}=>{}", self.0[i].0, self.0[i].1)?;
				}
				write!(f, "]")
			},
		}
	}
}

impl<K: Decode + Eq + PartialEq + Ord + PartialOrd, V: Decode> Decode for VecMap<K, V> {
	fn decode<I: scale::Input>(input: &mut I) -> Result<Self, DecodeError> {
		Ok(Self::from_sorted(Vec::<(K, V)>::decode(input)?).map_err(|()| "set out-of-order")?)
	}
}

impl<K, V> Default for VecMap<K, V> {
	fn default() -> Self {
		Self(Vec::new())
	}
}
impl<K, V> AsRef<[(K, V)]> for VecMap<K, V> {
	fn as_ref(&self) -> &[(K, V)] {
		&self.0[..]
	}
}
impl<K, V> AsMut<[(K, V)]> for VecMap<K, V> {
	fn as_mut(&mut self) -> &mut [(K, V)] {
		&mut self.0[..]
	}
}

impl<K, V> From<VecMap<K, V>> for Vec<(K, V)> {
	fn from(s: VecMap<K, V>) -> Vec<(K, V)> {
		s.0
	}
}
impl<K: Eq + PartialEq + Ord + PartialOrd, V> From<Vec<(K, V)>> for VecMap<K, V> {
	fn from(mut v: Vec<(K, V)>) -> Self {
		v.sort_unstable_by(|x, y| x.0.cmp(&y.0));
		v.dedup_by(|x, y| x.0 == y.0);
		Self(v)
	}
}
impl<K: Eq + PartialEq + Ord + PartialOrd, V> FromIterator<(K, V)> for VecMap<K, V> {
	fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
		Vec::<(K, V)>::from_iter(iter).into()
	}
}
impl<K: Eq + PartialEq + Ord + PartialOrd, V> Extend<(K, V)> for VecMap<K, V> {
	fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
		VecMap::<K, V>::extend(self, iter)
	}
}
impl<K: Eq + PartialEq + Ord + PartialOrd, V> IntoIterator for VecMap<K, V> {
	type Item = (K, V);
	type IntoIter = <Vec<(K, V)> as IntoIterator>::IntoIter;

	fn into_iter(self) -> Self::IntoIter {
		self.0.into_iter()
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	#[test]
	fn encode_decode_works() {
		let v = VecMap::<u32, u32>::from_iter((0..100).map(|j| ((j * 97) % 101, j)));
		println!("{}", v);
		let e = v.encode();
		let d = VecMap::<u32, u32>::decode(&mut &e[..]).unwrap();
		assert_eq!(v, d);
	}
}
