use eytzinger::SliceExt;
use std::borrow::Borrow;
pub trait AsSlice {
type Key: Ord;
type Value;
fn as_slice<'a>(&'a self) -> &'a [(Self::Key, Self::Value)];
}
pub trait AsMutSlice: AsSlice {
fn as_mut_slice(&mut self) -> &mut [(Self::Key, Self::Value)];
}
impl<K: Ord, V, const LEN: usize> AsSlice for [(K, V); LEN] {
type Key = K;
type Value = V;
fn as_slice(&self) -> &[(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V, const LEN: usize> AsMutSlice for [(K, V); LEN] {
fn as_mut_slice(&mut self) -> &mut [(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V> AsSlice for &[(K, V)] {
type Key = K;
type Value = V;
fn as_slice(&self) -> &[(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V> AsSlice for &mut [(K, V)] {
type Key = K;
type Value = V;
fn as_slice(&self) -> &[(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V> AsMutSlice for &mut [(K, V)] {
fn as_mut_slice(&mut self) -> &mut [(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V> AsSlice for Vec<(K, V)> {
type Key = K;
type Value = V;
fn as_slice(&self) -> &[(Self::Key, Self::Value)] {
self
}
}
impl<K: Ord, V> AsMutSlice for Vec<(K, V)> {
fn as_mut_slice(&mut self) -> &mut [(Self::Key, Self::Value)] {
self
}
}
#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, Hash)]
pub struct EytzingerMap<S>(S);
impl<S, K, V> AsRef<[(K, V)]> for EytzingerMap<S>
where
S: AsRef<[(K, V)]>,
{
fn as_ref(&self) -> &[(K, V)] {
self.0.as_ref()
}
}
impl<S, K, V> AsMut<[(K, V)]> for EytzingerMap<S>
where
K: Ord,
S: AsMut<[(K, V)]>,
{
fn as_mut(&mut self) -> &mut [(K, V)] {
self.0.as_mut()
}
}
impl<Q: ?Sized, S> std::ops::Index<&Q> for EytzingerMap<S>
where
S::Key: Borrow<Q> + Ord,
Q: Ord,
S: AsSlice,
{
type Output = S::Value;
#[inline]
fn index(&self, key: &Q) -> &S::Value {
self.get(key).expect("no entry found for key")
}
}
impl<S, K, V> IntoIterator for EytzingerMap<S>
where
S: std::iter::IntoIterator<Item = (K, V)>,
{
type Item = (K, V);
type IntoIter = S::IntoIter;
fn into_iter(self) -> S::IntoIter {
self.0.into_iter()
}
}
impl<K, V> std::iter::FromIterator<(K, V)> for EytzingerMap<Vec<(K, V)>>
where
K: Ord,
{
fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let items: Vec<_> = iter.into_iter().collect();
Self::new(items)
}
}
impl<S> EytzingerMap<S>
where
S: AsSlice,
{
pub fn new(mut s: S) -> Self
where
S: AsMutSlice,
{
s.as_mut_slice().sort_unstable_by(|a, b| a.0.cmp(&b.0));
Self::from_sorted(s)
}
pub fn from_sorted(mut s: S) -> Self
where
S: AsSlice + AsMutSlice,
{
s.as_mut_slice()
.eytzingerize(&mut eytzinger::permutation::InplacePermutator);
Self(s)
}
pub fn from_eytzingerized(s: S) -> Self
where
S: AsSlice,
{
Self(s)
}
#[inline]
fn find<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
S::Key: Borrow<Q> + Ord,
Q: Ord,
{
self.0
.as_slice()
.eytzinger_search_by(|x| x.0.borrow().cmp(key))
}
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&S::Value>
where
S::Key: Borrow<Q> + Ord,
Q: Ord,
{
self.find(key)
.map(|i| &unsafe { self.0.as_slice().get_unchecked(i) }.1)
}
pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<&(S::Key, S::Value)>
where
S::Key: Borrow<Q> + Ord,
Q: Ord,
{
self.find(key)
.map(|i| unsafe { self.0.as_slice().get_unchecked(i) })
}
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
S::Key: Borrow<Q> + Ord,
Q: Ord + ?Sized,
{
self.find(key).is_some()
}
pub fn iter(&self) -> impl std::iter::Iterator<Item = &(S::Key, S::Value)> {
self.0.as_slice().iter()
}
pub fn keys(&self) -> impl std::iter::Iterator<Item = &S::Key> {
self.iter().map(|(k, _v)| k)
}
pub fn values(&self) -> impl std::iter::Iterator<Item = &S::Value> {
self.iter().map(|(_k, v)| v)
}
pub fn len(&self) -> usize {
self.0.as_slice().len()
}
pub fn is_empty(&self) -> bool {
self.0.as_slice().is_empty()
}
}
impl<S> EytzingerMap<S>
where
S: AsMutSlice,
{
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut S::Value>
where
S::Key: Borrow<Q> + Ord,
Q: Ord,
{
let i = self.find(key)?;
Some(&mut unsafe { self.0.as_mut_slice().get_unchecked_mut(i) }.1)
}
pub fn iter_mut(&mut self) -> impl std::iter::Iterator<Item = &mut (S::Key, S::Value)> {
self.0.as_mut_slice().iter_mut()
}
pub fn values_mut(&mut self) -> impl std::iter::Iterator<Item = &mut S::Value> {
self.iter_mut().map(|(_k, v)| v)
}
}
pub type EytzingerArrayMap<K, V, const LEN: usize> = EytzingerMap<[(K, V); LEN]>;
pub type EytzingerVecMap<K, V> = EytzingerMap<Vec<(K, V)>>;
pub type EytzingerRefMap<'a, K, V> = EytzingerMap<&'a [(K, V)]>;
impl<'a, K, V> EytzingerRefMap<'a, K, V>
where
K: Ord,
{
pub fn from_sorted_ref(s: &'a mut [(K, V)]) -> Self {
s.eytzingerize(&mut eytzinger::permutation::InplacePermutator);
Self(s)
}
pub fn from_ref(s: &'a mut [(K, V)]) -> Self {
s.sort_unstable_by(|a, b| a.0.cmp(&b.0));
Self::from_sorted_ref(s)
}
}