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);
}
}