ryley 0.1.1

//! Module `hash_dict`
//! 
//! This module (which can be found in `structs`) contains the type `HashDict` which
//! is an unsorted `dictionary` or `map`.
//! 
//! # Getting Started:
//! 
//! ## Create a new `HashDict`:
//! ```
//! # use ryley::structs::prelude::HashDict;
//! let mut d: HashDict<i32,i32>=HashDict::new();
//! ```
//! or
//! ```
//! # use ryley::structs::prelude::*;
//! let mut d: HashDict<i32,i32>=hash_dict!{1:1, 2:4, 3:9};
//! ```
//! 
//! ## Utilitise `HashDict`:
//! ```
//! # use ryley::structs::prelude::*;
//! # let mut d: HashDict<i32,i32>=hash_dict!{1:1, 2:4, 3:9};
//! d.add((4,16)).add((5,16)).distinct().remove_slice(&[1,2,4]);
//! 
//! assert!(d.contains(&9));
//! ```
//! 
//! ## Remember that dictionaries are associated key-value pairs!
//! 
//! Also it is an unsorted container, therefore its keys will be distributed randomly.
//! If you need a stable order for your keys, you can try `HashDict` instead.

use core::cmp::Ordering;
use std::collections::hash_map::{IntoIter, Iter, IterMut};
use std::collections::{BTreeSet, HashMap};
use core::fmt::{Debug, Display, Formatter, Result};
use core::hash::{Hash, Hasher};
use core::ops::{Index, IndexMut};
use core::str::FromStr;

use algo::{contains_slice, count, count_fn, count_item_fn, count_key_fn, count_slice, difference, distinct, distinct_fn, ext, find, find_fn, find_slice, intersect, pop, pop_slice, remove, remove_slice, replace, replace_fn, replace_slice, sym_diff, union, Dict, DictMut, DictRef};

use super::algorithm::{DictDisplay, DictFromStr};
use super::UDSI::{Container, Indexed, IndContainer};

/// Type `HashDict` is a thin wrapper for `HashMap`
/// 
/// `HashDict` implements the Unified Data Structure Interface (or UDSI for short).
/// 
/// ## Beware
/// - `HashDict` is an indexed container, therefore it contains 1 of each key and these
///   keys are also associated with a value
/// - `HashDict` is also an unsorted container, which means it has its keys randomly organised 
#[derive(Debug, Clone, Default)]
pub struct HashDict<Key, Value> {
    /// Internal storage of `HashDict`
    /// 
    /// Type `HashDict` is actually a thin wrapper for `HashMap`.
    /// 
    /// Every datastructure implementing `UDSI` has `cont` as its inner storage.
    pub cont: HashMap<Key, Value>
}
impl<T: Ord,U: Ord> PartialEq for HashDict<T,U> {
    fn eq(&self, other: &Self) -> bool {
        if self.len()==other.len() { self.into_iter().collect::<BTreeSet<_>>().eq(&other.into_iter().collect::<BTreeSet<_>>()) }
        else { false }
    }
}
impl<T: Ord,U: Ord> Eq for HashDict<T,U> {}
impl<T: Ord,U: Ord> PartialOrd for HashDict<T,U> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.into_iter().collect::<BTreeSet<_>>().partial_cmp(&other.into_iter().collect::<BTreeSet<_>>())
    }
}
impl<T: Ord,U: Ord> Ord for HashDict<T,U> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.into_iter().collect::<BTreeSet<_>>().cmp(&other.into_iter().collect::<BTreeSet<_>>())
    }
}
impl<T: Hash,U: Hash> Hash for HashDict<T,U> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.cont.iter().collect::<Vec<_>>().hash(state);
    }
}

impl<T,U> Container<(T,U)> for HashDict<T,U> {
    fn len(&self) -> usize {
        self.cont.len()
    }
}
impl<T,U> IndContainer<T,U> for HashDict<T,U> {
    fn iter<'a>(&'a self) -> impl Iterator<Item = (&'a T,&'a U)> where T: 'a, U: 'a {
        self.cont.iter()
    }
    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = (&'a T,&'a mut U)> where T: 'a, U: 'a {
        self.cont.iter_mut()
    }
}
impl<T: Display, U: Display> DictDisplay<T,U> for HashDict<T,U> {}
impl<T: Display, U: Display> Display for HashDict<T,U> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        self.display(f, "HashDict")
    }
}
impl<T: Eq + Hash,U> Extend<(T,U)> for HashDict<T,U> {
    fn extend<I: IntoIterator<Item = (T,U)>>(&mut self, iter: I) {
        self.cont.extend(iter);
    }
}
impl<T: Eq + Hash,U> FromIterator<(T,U)> for HashDict<T,U> {
    fn from_iter<I: IntoIterator<Item = (T,U)>>(iter: I) -> Self {
        let mut cont = Self::new();
        cont.extend(iter);
        cont
    }
}
impl<T,U> IntoIterator for HashDict<T,U> {
    type Item = (T,U);
    type IntoIter = IntoIter<T,U>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.into_iter()
    }
}
impl<'a,T,U> IntoIterator for &'a HashDict<T,U> {
    type Item = (&'a T,&'a U);
    type IntoIter = Iter<'a,T,U>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter()
    }
}
impl<'a,T,U> IntoIterator for &'a mut HashDict<T,U> {
    type Item = (&'a T,&'a mut U);
    type IntoIter = IterMut<'a,T,U>;
    fn into_iter(self) -> Self::IntoIter {
        self.cont.iter_mut()
    }
}
impl<T,U,V: Into<HashMap<T,U>>> From<V> for HashDict<T,U> {
    fn from(value: V) -> Self {
        use crate::hash_dict;
        hash_dict![cont: value.into()]
    }
}
impl<T: Eq + Hash + FromStr + Default, U: FromStr + Default> DictFromStr<T,U> for HashDict<T,U> where <T as FromStr>::Err : Display, <U as FromStr>::Err : Display {}
impl<T: Eq + Hash + FromStr + Default, U: FromStr + Default> FromStr for HashDict<T,U> where <T as FromStr>::Err : Display, <U as FromStr>::Err : Display {
    type Err = String;
    fn from_str(s: &str) -> core::result::Result<Self, Self::Err> {
        Self::from_string(s, "HashDict", |cont, t, u| {cont.cont.insert(t,u);})
    }
}


/// Constructs a new `HashDict`
/// 
/// `hash_dict!` allows for the effortless contruction of Dictionaries. This macro has
/// multiple forms:
/// 
/// - Create a new `HashDict` from elements:
/// ```
/// # use ryley::structs::prelude::*;
/// let d = hash_dict!{1:2,2:4,3:6,4:8,5:10};
/// assert_eq!(d.len(), 5);
/// ```
///
/// - Create a new `HashDict` from a `HashMap`:
/// 
/// ```
/// # use ryley::structs::prelude::*;
/// # use std::collections::HashMap;
/// let d = hash_dict!{cont: HashMap::from([(1,1),(2,2),(3,3),(4,4),(5,5)])};
/// assert_eq!(d.len(), 5);
/// ```
#[macro_export]
macro_rules! hash_dict {
    [cont: $x:expr] => {
        {
            use $crate::structs::hash_dict::HashDict;
            HashDict { cont: ($x)}
        }
    };
    [$($x:tt : $y:tt),*] => {
        {
            use std::collections::HashMap;
            use $crate::structs::hash_dict::HashDict;
            let mut inner=HashMap::new();
            $(
                inner.insert($x,$y);
            )*
            HashDict { cont: (inner) }
        }
    };
}

pub(crate) mod algo {
    use crate::structs::algorithm::{make_multiset, unsafe_ref, KMP};
    use core::hash::Hash;
    use std::collections::{BTreeMap, BTreeSet, HashMap};
    

    pub fn ext<X: PartialOrd,T: PartialOrd>(cont: DictRef<X,T>, max: bool) -> (*const T, *const X) {
        debug_assert!(!cont.is_empty(), "Can't find extremum in empty Dict!");
        let (mut e_ind, mut e_val)=
        match cont {
            DictRef::HashMap(h) => unsafe {h.as_ref().unwrap().iter().next().unwrap()},
            DictRef::OrdMap(o) => unsafe {o.as_ref().unwrap().iter().next().unwrap()},
        };
        for i in cont.iter() {
            if (max && i.1>e_val) || (!max && i.1<e_val) || (cont.is_hash() && i.1==e_val && i.0<e_ind) {
                (e_ind,e_val)=i;
            }
        }
        (e_val,e_ind)
    }

    pub enum Dict<X,T> {
        HashMap(HashMap<X,T>),
        OrdMap(BTreeMap<X,T>)
    }
    impl<X,T> Dict<X,T> {
        const fn as_ref(&self) -> DictRef<X,T> {
            match self {
                Self::HashMap(h) => DictRef::HashMap(h),
                Self::OrdMap(o) => DictRef::OrdMap(o),
            }
        }
        fn as_mut(&mut self) -> DictMut<X,T> {
            match self {
                Self::HashMap(h) => DictMut::HashMap(h),
                Self::OrdMap(o) => DictMut::OrdMap(o),
            }
        }
    }
    pub enum DictRef<X,T> {
        HashMap(*const HashMap<X,T>),
        OrdMap(*const BTreeMap<X,T>)
    }
    impl<X,T> DictRef<X,T> {
        const fn is_hash(&self) -> bool {
            matches!(self,Self::HashMap(_))
        }
        fn len(&self) -> usize {
            match self {
                Self::HashMap(h) => unsafe {(*h).as_ref().unwrap().len()},
                Self::OrdMap(o) => unsafe {(*o).as_ref().unwrap().len()},
            }
        }
        fn is_empty(&self) -> bool {
            self.len()==0
        }
        fn iter(&self) -> Iter<'_,X,T> {
            match self {
                Self::HashMap(h) => Iter::HashIter(unsafe {(*h).as_ref().unwrap().iter()}),
                Self::OrdMap(o) => Iter::OrdIter(unsafe {(*o).as_ref().unwrap().iter()}),
            }
        }
        fn keys(&self) -> Keys<'_,X,T> {
            match self {
                Self::HashMap(h) => Keys::HashKeys(unsafe {(*h).as_ref().unwrap().keys()}),
                Self::OrdMap(o) => Keys::OrdKeys(unsafe {(*o).as_ref().unwrap().keys()}),
            }
        }
        fn values(&self) -> Values<'_,X,T> {
            match self {
                Self::HashMap(h) => Values::HashVals(unsafe {(*h).as_ref().unwrap().values()}),
                Self::OrdMap(o) => Values::OrdVals(unsafe {(*o).as_ref().unwrap().values()}),
            }
        }
    }
    impl<X: Ord + Hash,T> DictRef<X,T> {
        fn get(&self, key: &X) -> Option<&T> {
            match self {
                Self::HashMap(h) => unsafe {(*h).as_ref().unwrap().get(key)},
                Self::OrdMap(o) => unsafe {(*o).as_ref().unwrap().get(key)},
            }
        }
    }
    pub enum DictMut<X,T> {
        HashMap(*mut HashMap<X,T>),
        OrdMap(*mut BTreeMap<X,T>)
    }
    impl<X,T> DictMut<X,T> {
        const fn as_ref(&self) -> DictRef<X,T> {
            match self {
                Self::HashMap(h) => DictRef::HashMap(*h),
                Self::OrdMap(o) => DictRef::OrdMap(*o),
            }
        }
        fn iter_mut(&self) -> IterMut<'_,X,T> {
            match self {
                Self::HashMap(h) => IterMut::HashIter(unsafe {(*h).as_mut().unwrap().iter_mut()}),
                Self::OrdMap(o) => IterMut::OrdIter(unsafe {(*o).as_mut().unwrap().iter_mut()}),
            }
        }
        const fn deref(&self) -> Self {
            match self {
                Self::HashMap(h) => Self::HashMap(*h),
                Self::OrdMap(o) => Self::OrdMap(*o)
            }
        }
    }
    impl<X: Ord + Hash,T> DictMut<X,T> {
        fn insert(&self, key: X, value: T) -> Option<T> {
            match self {
                Self::HashMap(h) => unsafe {(*h).as_mut().unwrap().insert(key,value)},
                Self::OrdMap(o) => unsafe {(*o).as_mut().unwrap().insert(key,value)},
            }
        }
        fn remove(&self, key: &X) -> Option<T> {
            match self {
                Self::HashMap(h) => unsafe {(*h).as_mut().unwrap().remove(key)},
                Self::OrdMap(o) => unsafe {(*o).as_mut().unwrap().remove(key)},
            }
        }
    }

    pub enum Iter<'a,X,T> {
        HashIter(std::collections::hash_map::Iter<'a,X,T>),
        OrdIter(std::collections::btree_map::Iter<'a,X,T>)
    }
    impl<'a,X,T> Iterator for Iter<'a,X,T> {
        type Item = (&'a X,&'a T);
        fn next(&mut self) -> Option<Self::Item> {
            match self {
                Iter::HashIter(h) => h.next(),
                Iter::OrdIter(o) => o.next(),
            }
        }
    }

    pub enum IterMut<'a,X,T> {
        HashIter(std::collections::hash_map::IterMut<'a,X,T>),
        OrdIter(std::collections::btree_map::IterMut<'a,X,T>)
    }
    impl<'a,X,T> Iterator for IterMut<'a,X,T> {
        type Item = (&'a X,&'a mut T);
        fn next(&mut self) -> Option<Self::Item> {
            match self {
                IterMut::HashIter(h) => h.next(),
                IterMut::OrdIter(o) => o.next(),
            }
        }
    }

    pub enum Keys<'a,X,T> {
        HashKeys(std::collections::hash_map::Keys<'a,X,T>),
        OrdKeys(std::collections::btree_map::Keys<'a,X,T>)
    }
    impl<'a,X,T> Iterator for Keys<'a,X,T> {
        type Item = &'a X;
        fn next(&mut self) -> Option<Self::Item> {
            match self {
                Keys::HashKeys(h) => h.next(),
                Keys::OrdKeys(o) => o.next(),
            }
        }
    }
    pub enum Values<'a,X,T> {
        HashVals(std::collections::hash_map::Values<'a,X,T>),
        OrdVals(std::collections::btree_map::Values<'a,X,T>)
    }
    impl<'a,X,T> Iterator for Values<'a,X,T> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> {
            match self {
                Values::HashVals(h) => h.next(),
                Values::OrdVals(o) => o.next(),
            }
        }
    }

    pub fn contains_slice<X: Ord, T: PartialEq>(cont: DictRef<X,T>, slice: &[T]) -> bool {
        let base=
        if cont.is_hash() {
            let mut b=cont.iter().collect::<Vec<_>>();
            b.sort_by(|a,b| a.0.cmp(b.0));
            b.into_iter().map(|x| x.1).collect::<Vec<_>>()
        } 
        else { cont.iter().map(|(_,t)| t).collect::<Vec<_>>() };
        !KMP(base.as_slice(), slice.iter().collect::<Vec<_>>().as_ref(), Some(1)).is_empty()
    }
    pub fn count<X, T: PartialEq>(cont: DictRef<X,T>, elem: &T) -> usize {
        count_fn(cont, |item| item==elem)
    }
    pub fn count_fn<X, T>(cont: DictRef<X,T>, mut f: impl FnMut(&T) -> bool) -> usize {
        let mut counter=0;
        for (_,e) in cont.iter() { if f(e) { counter+=1; } }
        counter
    }
    pub fn count_slice<X: Ord, T: PartialEq>(cont: DictRef<X,T>, slice: &[T]) -> usize {
        let base=
        if cont.is_hash() {
            let mut b=cont.iter().collect::<Vec<_>>();
            b.sort_by(|a,b| a.0.cmp(b.0));
            b.into_iter().map(|x| x.1).collect::<Vec<_>>()
        } 
        else { cont.iter().map(|(_,t)| t).collect::<Vec<_>>() };
        KMP(base.as_ref(), slice.iter().collect::<Vec<_>>().as_ref(), None).len()
    }
    pub fn count_key_fn<X, T>(cont: DictRef<X,T>, mut f: impl FnMut(&X) -> bool) -> usize {
        let mut counter=0;
        for (k,_) in cont.iter() { if f(k) { counter+=1; } }
        counter
    }
    pub fn count_item_fn<X, T>(cont: DictRef<X,T>, mut f: impl FnMut((&X,&T)) -> bool) -> usize {
        let mut counter=0;
        for item in cont.iter() { if f(item) { counter+=1; } }
        counter
    }
    pub fn find<X: Ord, T: PartialEq>(cont: DictRef<X,T>, elem: &T, maxcount: Option<isize>) -> Vec<*const X> {
        find_fn(cont, |item| item==elem, maxcount)
    }
    pub fn find_fn<X: Ord, T>(cont: DictRef<X,T>, mut f: impl FnMut(&T) -> bool, maxcount: Option<isize>) -> Vec<*const X> {
        let mut counter=maxcount.unwrap_or(1);
        if counter==0 {return vec![]}
        let mut v=vec![];

        let mut c=cont.iter().collect::<Vec<_>>();
        if cont.is_hash() {c.sort_by(|a,b| a.0.cmp(b.0));}
        for item in c {
            if f(item.1) {
                v.push(core::ptr::from_ref::<X>(item.0));
                counter-=1;
                if counter==0 {break}
            }
        }
        v
    }
    pub fn find_slice<X: Ord, T: Eq>(cont: DictRef<X,T>, slice: &[T], maxcount: Option<isize>) -> Vec<*const X> {
        let mut base=cont.iter().collect::<Vec<_>>();
        if cont.is_hash() {base.sort_by(|a,b| a.0.cmp(b.0));}
        let v=KMP(base.iter().map(|x| x.1).collect::<Vec<_>>().as_ref(), slice.iter().collect::<Vec<_>>().as_ref(), maxcount);
        v.into_iter().map(|i| core::ptr::from_ref::<X>(base[i].0)).collect()
    }
    pub fn pop<X: Ord + Hash, T>(cont: DictMut<X,T>, index: &X) -> T {
        cont.remove(index).unwrap()
    }
    pub fn pop_slice<X: Ord + Hash, T>(cont: DictMut<X,T>, indices: &[X]) -> Vec<T> {
        let mut out=vec![];
        for key in indices {
            out.push(cont.remove(key).unwrap());
        }
        out
    }
    pub fn remove<X: Ord + Hash, T>(cont: DictMut<X,T>, index: &X) {
        cont.remove(index);
    }
    pub fn remove_slice<X: Ord + Hash, T>(cont: DictMut<X,T>, indices: &[X]) {
        for key in indices { cont.remove(key); }
    }
    pub fn replace<X: Ord + Hash, T: PartialEq + Clone>(cont: DictMut<X,T>, what: &T, to_what: Option<&T>, max_count: Option<isize>) {
        replace_fn(cont, |item| item==what, to_what, max_count);
    }
    pub fn replace_fn<X: Ord + Hash, T: Clone>(cont: DictMut<X,T>, mut f: impl FnMut(&T)->bool, to_what: Option<&T>, max_count: Option<isize>) {
        let mut counter=max_count.unwrap_or(-1);
        if counter==0 { return; }
        let mut keys=vec![];
        for (x,t) in cont.iter_mut() {
            if f(t) { keys.push((x,t)); }
        }
        if cont.as_ref().is_hash() {keys.sort_by(|a,b| a.0.cmp(b.0));}

        if let Some(val) = to_what {
            for (_,t) in keys {
                *t=val.clone();
                counter-=1;
                if counter==0 { break; }
            }
        }
        else {
            let num=if counter<0 {keys.len()} else {counter.unsigned_abs()};
            let min_keys=keys.into_iter().map(|x| unsafe_ref(x.0)).take(num).collect::<Vec<_>>();
            for key in min_keys { cont.remove(key); }
        }
    }
    pub fn replace_slice<const N: usize,X: Hash + Ord + Clone, T: Clone + PartialEq>(cont: DictMut<X,T>, slice: &[T;N], to_what: Option<&[T;N]>, max_count: Option<isize>) {
        if max_count.unwrap_or(-1)==0 || slice.is_empty() { return; }
        let mut vals=cont.as_ref().iter().map(|(x,t)| (unsafe_ref(x),unsafe_ref(t))).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {vals.sort_by(|a,b| a.0.cmp(b.0));}
        let v=vals.iter().map(|x| x.1).collect::<Vec<_>>();

        let indices=KMP(v.as_slice(), slice.iter().collect::<Vec<_>>().as_slice(), max_count);
        if indices.is_empty() { return; }
        match to_what {
            Some(rep) => {
                for i in indices {
                    for idx in vals[i..i+N].into_iter().map(|x| x.0).zip(rep) {
                        cont.insert(idx.0.clone(), idx.1.clone());
                    }
                }
            },
            None => {
                for i in indices {
                    let inds=vals[i..i+N].into_iter().map(|x| x.0).cloned().collect::<Vec<_>>();
                    remove_slice(cont.deref(),&inds);
                }
            },
        }
    }
    pub fn distinct<X: Hash + Ord, T: Ord>(cont: DictMut<X,T>) {
        let mut keys=cont.as_ref().keys().map(|x| unsafe_ref(x)).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {keys.sort();}
        let mut set=BTreeSet::new();
        for key in keys {
            let val=unsafe_ref(cont.as_ref().get(key).unwrap());
            if set.contains(&val) { cont.remove(key); }
            else { set.insert(val); }
        }
    }
    pub fn distinct_fn<X: Hash + Ord, T, U: Ord>(cont: DictMut<X,T>, mut f: impl FnMut(&T) -> U) {
        let mut keys=cont.as_ref().keys().map(|x| unsafe_ref(x)).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {keys.sort();}
        let mut set=BTreeSet::new();
        for key in keys {
            let val=f(cont.as_ref().get(key).unwrap());
            if set.contains(&val) { cont.remove(key); }
            else { set.insert(val); }
        }
    }

    pub fn union<X: Hash + Ord + Clone, T>(cont: DictMut<X,T>, other: Dict<X,T>) {
        match other {
            Dict::HashMap(hash_map) => {
                if let DictMut::HashMap(h)=cont {
                    for i in hash_map {
                        unsafe {h.as_mut()}.unwrap().entry(i.0).or_insert(i.1);
                    }
                }
                else {unreachable!()}
            },
            Dict::OrdMap(mut btree_map) => {
                if let DictMut::OrdMap(o)=cont {
                    unsafe {o.as_mut()}.unwrap().append(&mut btree_map);
                }
                else {unreachable!()}
            },
        }
    }
    pub fn intersect<X: Ord + Hash, T: Ord>(cont: DictMut<X,T>, other: DictRef<X,T>) {
        let mut h=make_multiset(other.values());
        let mut v=cont.as_ref().iter().map(|(x,t)| (unsafe_ref(x),unsafe_ref(t))).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {v.sort_by(|a,b| a.0.cmp(b.0));}
        for (x,t) in v {
            let k = h.get(t);
            if k.is_some() {
                let mut_ref=h.get_mut(t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(t); }
            }
            else { cont.remove(x); }
        }
    }
    pub fn difference<X: Ord + Hash, T: Ord>(cont: DictMut<X,T>, other: DictRef<X,T>) {
        let h=make_multiset(other.values());
        diff_with_multiset(cont, h);
    }
    pub fn diff_with_multiset<X: Ord + Hash, T: Ord>(cont: DictMut<X,T>, mut h: BTreeMap<&T,i128>) {
        let mut v=cont.as_ref().iter().map(|(x,t)| (unsafe_ref(x),unsafe_ref(t))).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {v.sort_by(|a,b| a.0.cmp(b.0));}
        for (x,t) in v {
            let k = h.get(t);
            if k.is_some() {
                let mut_ref=h.get_mut(t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(t); }
                cont.remove(x);
            }
        }
    }
    pub fn difference_with_out<X: Ord + Hash, T: Ord>(cont: DictMut<X,T>, other: DictRef<X,T>) -> Vec<T> {
        let mut h=make_multiset(other.values());
        let mut v=cont.as_ref().iter().map(|(x,t)| (unsafe_ref(x),unsafe_ref(t))).collect::<Vec<_>>();
        if cont.as_ref().is_hash() {v.sort_by(|a,b| a.0.cmp(b.0));}
        let mut out=vec![];
        for (x,t) in v {
            let k = h.get(t);
            if k.is_some() {
                let mut_ref=h.get_mut(t).unwrap();
                *mut_ref-=1;
                if *mut_ref==0 { h.remove(t); }
                out.push(cont.remove(x).unwrap());
            }
        }
        out
    }
    pub fn sym_diff<X: Hash + Ord + Clone, T: Ord>(cont: DictMut<X,T>, mut other: Dict<X,T>) {
        let removed=difference_with_out(other.as_mut(), cont.as_ref());
        difference(cont.deref(),other.as_ref());
        diff_with_multiset(cont.deref(),make_multiset(&removed));
        union(cont, other);
    }
}

impl<X: Ord + Hash + Clone, T: Ord + Clone> Indexed<X,T> for HashDict<X,T> {
    fn add(&mut self, elem: (X,T)) -> &mut Self {
        self.cont.insert(elem.0, elem.1);
        self
    }
    fn add_slice(&mut self, slice: Vec<(X,T)>) -> &mut Self {
        for val in slice { self.cont.insert(val.0, val.1); }
        self
    }
    fn contains(&self, elem: &T) -> bool {
        self.cont.iter().any(|x| x.1==elem)
    }
    fn contains_fn(&self, mut f: impl FnMut(&T) -> bool) -> bool {
        self.cont.iter().any(|(_,t)| f(t))
    }
    fn contains_slice(&self, slice: &[T]) -> bool {
        contains_slice(DictRef::HashMap(&self.cont), slice)
    }
    fn contains_key(&self, key: &X) -> bool {
        self.cont.contains_key(key)
    }
    fn contains_key_fn(&self, mut f: impl FnMut(&X) -> bool) -> bool {
        self.cont.iter().any(|(x,_)| f(x))
    }
    fn contains_item(&self, item: (&X,&T)) -> bool {
        self.contains_key(item.0) && self.cont[item.0]==*item.1
    }
    fn contains_item_fn(&self, f: impl FnMut((&X,&T)) -> bool) -> bool {
        self.cont.iter().any(f)
    }
    fn count(&self, elem: &T) -> usize {
        count(DictRef::HashMap(&self.cont), elem)
    }
    fn count_fn(&self, f: impl FnMut(&T) -> bool) -> usize {
        count_fn(DictRef::HashMap(&self.cont), f)
    }
    fn count_slice(&self, slice: &[T]) -> usize {
        count_slice(DictRef::HashMap(&self.cont), slice)
    }
    fn count_key(&self, key: &X) -> usize {
        usize::from(self.contains_key(key))
    }
    fn count_key_fn(&self, f: impl FnMut(&X) -> bool) -> usize {
        count_key_fn(DictRef::HashMap(&self.cont), f)
    }
    fn count_item(&self, item: (&X,&T)) -> usize {
        usize::from(self.contains_item(item))
    }
    fn count_item_fn(&self, f: impl FnMut((&X,&T)) -> bool) -> usize {
        count_item_fn(DictRef::HashMap(&self.cont), f)
    }
    fn find(&self, elem: &T, maxcount: Option<isize>) -> Vec<&X> {
        find(DictRef::HashMap(&self.cont), elem, maxcount).into_iter().map(|x| unsafe {x.as_ref().unwrap()}).collect()
    }
    fn find_fn(&self, f: impl FnMut(&T) -> bool, maxcount: Option<isize>) -> Vec<&X> {
        find_fn(DictRef::HashMap(&self.cont), f, maxcount).into_iter().map(|x| unsafe {x.as_ref().unwrap()}).collect()
    }
    fn find_slice(&self, slice: &[T], maxcount: Option<isize>) -> Vec<&X> {
        find_slice(DictRef::HashMap(&self.cont), slice, maxcount).into_iter().map(|x| unsafe {x.as_ref().unwrap()}).collect()
    }
    fn pop(&mut self, index: &X) -> T {
        pop(DictMut::HashMap(&mut self.cont), index)
    }
    fn pop_slice(&mut self, indices: &[X]) -> Vec<T> {
        pop_slice(DictMut::HashMap(&mut self.cont), indices)
    }
    fn remove(&mut self, index: &X) -> &mut Self {
        remove(DictMut::HashMap(&mut self.cont), index);
        self
    }
    fn remove_slice(&mut self, indices: &[X]) -> &mut Self {
        remove_slice(DictMut::HashMap(&mut self.cont), indices);
        self
    }
    fn replace(&mut self, what: &T, to_what: Option<&T>, max_count: Option<isize>) -> &mut Self {
        replace(DictMut::HashMap(&mut self.cont), what, to_what, max_count);
        self
    }
    fn replace_fn(&mut self, f: impl FnMut(&T)->bool, to_what: Option<&T>, max_count: Option<isize>) -> &mut Self {
        replace_fn(DictMut::HashMap(&mut self.cont), f, to_what, max_count);
        self
    }
    fn replace_slice<const N: usize>(&mut self, slice: &[T;N], to_what: Option<&[T;N]>, max_count: Option<isize>) -> &mut Self {
        replace_slice(DictMut::HashMap(&mut self.cont), slice, to_what, max_count);
        self
    }
    fn distinct(&mut self) -> &mut Self {
        distinct(DictMut::HashMap(&mut self.cont));
        self
    }
    fn distinct_fn<U: Ord>(&mut self, f: impl FnMut(&T) -> U) -> &mut Self {
        distinct_fn(DictMut::HashMap(&mut self.cont), f);
        self
    }
    fn clear(&mut self) -> &mut Self {
        self.cont.clear();
        self
    }
    fn union(&mut self, other: Self) -> &mut Self {
        union(DictMut::HashMap(&mut self.cont), Dict::HashMap(other.cont));
        self
    }
    fn intersect(&mut self, other: &Self) -> &mut Self {
        intersect(DictMut::HashMap(&mut self.cont), DictRef::HashMap(&other.cont));
        self
    }
    fn difference(&mut self, other: &Self) -> &mut Self {
        difference(DictMut::HashMap(&mut self.cont), DictRef::HashMap(&other.cont));
        self
    }
    fn sym_diff(&mut self, other: Self) -> &mut Self {
        sym_diff(DictMut::HashMap(&mut self.cont), Dict::HashMap(other.cont));
        self
    }
    fn maxi(&self) -> (&T, &X) {
        let res=ext(DictRef::HashMap(&self.cont), true);
        unsafe {(res.0.as_ref().unwrap(),res.1.as_ref().unwrap())}
    }
    fn mini(&self) -> (&T, &X) {
        let res=ext(DictRef::HashMap(&self.cont), false);
        unsafe {(res.0.as_ref().unwrap(),res.1.as_ref().unwrap())}
    }
    fn keys<'a>(&'a self) -> impl Iterator<Item = &'a X> where X: 'a {
        self.cont.keys()
    }
    fn values<'a>(&'a self) -> impl Iterator<Item = &'a T> where T: 'a {
        self.cont.values()
    }
    fn into_keys(self) -> impl IntoIterator<Item = X> {
        self.cont.into_keys()
    }
    fn into_values(self) -> impl IntoIterator<Item = T> {
        self.cont.into_values()
    }
}


impl<T,U> HashDict<T,U> {
    /// Constructs a new, empty `HashDict<X,T>`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ryley::structs::prelude::HashDict;
    /// let mut dict: HashDict<i32,i32> = HashDict::new();
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self { cont: (HashMap::new()) }
    }
}

impl<T: Eq + Hash,U> Index<&T> for HashDict<T,U> {
    type Output = U;
    fn index(&self, index: &T) -> &Self::Output {
        &self.cont[index]
    }
}
impl<T: Eq + Hash,U> IndexMut<&T> for HashDict<T,U> {
    fn index_mut(&mut self, index: &T) -> &mut Self::Output {
        self.cont.get_mut(index).unwrap()
    }
}