// deqmap::deqmap
//
//!
//
use crate::{DeqMapError as Error, DeqMapResult as Result};
use core::{borrow::Borrow, hash::Hash};
use std::collections::{
hash_map::{Entry, HashMap},
VecDeque,
};
/// A double-ended queue with optional keys,
/// implemented a with [`VecDeque`] and a [`HashMap`].
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct DeqMap<K: Hash + Eq, V> {
vals: VecDeque<V>,
keys: HashMap<K, usize>,
}
/// # general construction & configuration
impl<K: Hash + Eq, V> DeqMap<K, V> {
/* construct */
/// Returns a new empty deqmap.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<&str, i32> = DeqMap::new();
/// ```
pub fn new() -> DeqMap<K, V> {
DeqMap {
vals: VecDeque::default(),
keys: HashMap::default(),
}
}
/// Converts an array of values `[V; N]` into a `DeqMap<_, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<&str, _> = DeqMap::from_array([1, 2, 3, 4]);
/// ```
pub fn from_array<const N: usize>(arr: [V; N]) -> DeqMap<K, V> {
DeqMap {
vals: VecDeque::from(arr),
keys: HashMap::default(),
}
}
/// Converts an array of keys and values `[(K, V); N]` into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let arr = [("b", 2), ("c", 3), ("d", 4), ("e", 5)];
/// let dm = DeqMap::from_keyed_array(arr);
/// ```
pub fn from_keyed_array<const N: usize>(arr: [(K, V); N]) -> DeqMap<K, V> {
let mut dm = Self::with_capacity(N, N);
dm.extend_keyed(arr);
dm
}
/// Converts an array of optional keys and values `[(Option<K>, V); N]`
/// into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let arr = [(Some("b"), 2), (None, 3), (None, 4), (Some("e"), 5)];
/// let dm = DeqMap::from_some_keyed_array(arr);
///
/// assert_eq![dm.len_keys(), 2];
/// assert_eq![dm.len_values(), 4];
/// ```
pub fn from_some_keyed_array<const N: usize>(arr: [(Option<K>, V); N]) -> DeqMap<K, V> {
let mut dm = Self::with_capacity(N, N);
dm.extend_some_keyed(arr);
dm.shrink_keys_to_fit();
dm
}
/// Converts a vec of values `Vec<V>` into a `DeqMap<_, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<&str, _> = DeqMap::from_vec(vec![1, 2, 3, 4]);
/// ```
pub fn from_vec(vec: Vec<V>) -> DeqMap<K, V> {
DeqMap {
vals: VecDeque::from(vec),
keys: HashMap::default(),
}
}
/// Converts a vec of keys and values `Vec<(K, V)>` into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let vec = vec![("b", 2), ("c", 3), ("d", 4), ("e", 5)];
/// let dm = DeqMap::from_keyed_vec(vec);
/// ```
pub fn from_keyed_vec(vec: Vec<(K, V)>) -> DeqMap<K, V> {
let mut dm = Self::with_capacity(vec.len(), vec.len());
dm.extend_keyed(vec);
dm
}
/// Converts a vec of optional keys and values `Vec<(Option<K>, V)>`
/// into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let vec = vec![(Some("b"), 2), (None, 3), (None, 4), (Some("e"), 5)];
/// let dm = DeqMap::from_some_keyed_vec(vec);
///
/// assert_eq![dm.len_keys(), 2];
/// assert_eq![dm.len_values(), 4];
/// ```
pub fn from_some_keyed_vec(vec: Vec<(Option<K>, V)>) -> DeqMap<K, V> {
let mut dm = Self::with_capacity(vec.len(), vec.len());
dm.extend_some_keyed(vec);
dm.shrink_keys_to_fit();
dm
}
/// Returns a new empty `DeqMap`, with at least the specified capacity for
/// `keys` and `values`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<u64, i32> = DeqMap::with_capacity(10, 30);
/// assert![dm.capacity() >= (10, 30)];
/// ```
pub fn with_capacity(keys: usize, values: usize) -> DeqMap<K, V> {
DeqMap {
keys: HashMap::with_capacity(keys),
vals: VecDeque::with_capacity(values),
}
}
/// Returns a new empty `DeqMap`, with at least the specified `capacity` for
/// just the values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm1: DeqMap<u64, i32> = DeqMap::with_capacity(10, 30);
/// let dm2: DeqMap<u64, i32> = DeqMap::with_capacity_values(30);
/// assert_eq![dm1.capacity_values(), dm2.capacity_values()];
/// ```
pub fn with_capacity_values(capacity: usize) -> DeqMap<K, V> {
DeqMap {
keys: HashMap::default(),
vals: VecDeque::with_capacity(capacity),
}
}
/* capacity */
/// Returns the number of `(keys, values)` the deqmap can hold without
/// reallocating.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<u64, i32> = DeqMap::with_capacity(10, 30);
/// assert![dm.capacity().0 == dm.capacity_keys()];
/// assert![dm.capacity().1 == dm.capacity_values()];
/// ```
#[inline]
pub fn capacity(&self) -> (usize, usize) {
(self.keys.capacity(), self.vals.capacity())
}
/// Returns the number of keys the deqmap can hold without reallocating.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<u64, i32> = DeqMap::with_capacity(10, 30);
/// assert![dm.capacity_keys() >= 10];
/// assert![dm.capacity_keys() < 30];
/// ```
#[inline]
pub fn capacity_keys(&self) -> usize {
self.keys.capacity()
}
/// Returns the number of values the deqmap can hold without reallocating.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<u64, i32> = DeqMap::with_capacity(10, 30);
/// assert![dm.capacity_values() >= 30];
/// ```
#[inline]
pub fn capacity_values(&self) -> usize {
self.vals.capacity()
}
/* reserve */
/// Reserves capacity for at least additional more `keys` and `values` to be
/// inserted.
///
/// # Panics
/// Panics if either capacity overflows `usize`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = DeqMap::new();
/// dm.reserve(10, 30);
/// assert![dm.capacity() >= (10, 30)];
/// ```
#[inline]
pub fn reserve(&mut self, keys: usize, values: usize) {
self.keys.reserve(keys);
self.vals.reserve(values);
}
/// Reserves capacity for at least `additional` more values to be inserted.
///
/// # Panics
/// Panics if the new capacity overflows `usize`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = [1, 2].into();
/// dm.reserve_values(30);
/// assert![dm.capacity_values() >= 32];
/// ```
#[inline]
pub fn reserve_values(&mut self, additional: usize) {
self.vals.reserve(additional);
}
/// Reserves capacity for at least `additional` more keys to be inserted.
///
/// # Panics
/// Panics if the new capacity overflows `usize`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = DeqMap::new();
/// dm.reserve_keys(10);
/// assert![dm.capacity_keys() >= 10];
/// assert![dm.capacity_values() < 10];
/// ```
#[inline]
pub fn reserve_keys(&mut self, additional: usize) {
self.keys.reserve(additional);
}
/// Tries to reserve capacity for at least additional more `keys` and `values`
/// to be inserted.
/// The collection may reserve more space to speculatively avoid frequent
/// reallocations. After calling `try_reserve`, capacity will be greater
/// than or equal to `self.len() + additional` if it returns Ok(()).
/// Does nothing if capacity is already sufficient.
///
/// # Errors
/// If either capacity overflows, or the allocator reports a failure, then
/// an error is returned.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = DeqMap::new();
/// if dm.try_reserve(10, 30).is_ok() {
/// assert![dm.capacity() >= (10, 30)];
/// }
/// ```
#[inline]
pub fn try_reserve(&mut self, keys: usize, values: usize) -> Result<()> {
self.keys.try_reserve(keys)?;
self.vals.try_reserve(values)?;
Ok(())
}
/// Tries to reserve capacity for at least `additional` more values to be inserted.
/// The collection may reserve more space to speculatively avoid frequent
/// reallocations. After calling `try_reserve_values`, capacity will be greater
/// than or equal to `self.len_values() + additional` if it returns Ok(()).
/// Does nothing if capacity is already sufficient.
///
/// # Errors
/// If the capacity overflows, or the allocator reports a failure, then
/// an error is returned.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = DeqMap::new();
/// if dm.try_reserve_values(30).is_ok() {
/// assert![dm.capacity_values() >= 30];
/// }
/// ```
#[inline]
pub fn try_reserve_values(&mut self, additional: usize) -> Result<()> {
Ok(self.vals.try_reserve(additional)?)
}
/// Tries to reserve capacity for at least `additional` more keys to be inserted.
/// The collection may reserve more space to speculatively avoid frequent
/// reallocations. After calling `try_reserve_keys`, capacity will be greater
/// than or equal to `self.alen_keys() + additional` if it returns Ok(()).
/// Does nothing if capacity is already sufficient.
///
/// # Errors
/// If the capacity overflows, or the allocator reports a failure, then
/// an error is returned.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u64, i32> = DeqMap::new();
/// if dm.try_reserve_keys(10).is_ok() {
/// assert![dm.capacity_keys() >= 10];
/// }
/// ```
#[inline]
pub fn try_reserve_keys(&mut self, additional: usize) -> Result<()> {
Ok(self.keys.try_reserve(additional)?)
}
/* shrink */
/// Shrinks the capacity of both keys and values as much as possible.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = DeqMap::with_capacity(7, 7);
/// dm.extend(0..4);
/// assert_eq![dm.capacity(), (7, 7)];
/// dm.shrink_to_fit();
/// assert![dm.capacity_keys() == 0];
/// assert![dm.capacity_values() >= 4];
/// ```
#[inline]
pub fn shrink_to_fit(&mut self) {
self.vals.shrink_to_fit();
self.keys.shrink_to_fit();
}
/// Shrinks the capacity of just the values as much as possible.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = DeqMap::with_capacity(0, 15);
/// dm.extend(0..4);
/// assert_eq![dm.capacity_values(), 15];
/// dm.shrink_to_fit();
/// assert![dm.capacity_values() >= 4];
/// assert![dm.capacity_values() < 15];
/// ```
#[inline]
pub fn shrink_values_to_fit(&mut self) {
self.vals.shrink_to_fit();
}
/// Shrinks the capacity of just the keys as much as possible.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::with_capacity(14, 4);
/// dm.extend_keyed([("a", 1), ("b", 2), ("c", 3), ("d", 4)].into_iter());
/// assert_eq![dm.capacity_keys(), 14];
/// dm.shrink_to_fit();
/// assert![dm.capacity_keys() >= 4];
/// assert![dm.capacity_keys() < 14];
/// ```
#[inline]
pub fn shrink_keys_to_fit(&mut self) {
self.keys.shrink_to_fit();
}
/// Shrinks the capacity of both keys and values, with a lower limit.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = DeqMap::with_capacity(14, 15);
/// dm.extend(0..4);
/// assert_eq![dm.capacity(), (14, 15)];
/// dm.shrink_to(6);
/// assert![dm.capacity() >= (6, 6)];
/// assert![dm.capacity() < (14, 15)];
/// ```
#[inline]
pub fn shrink_to(&mut self, min_capacity: usize) {
self.vals.shrink_to(min_capacity);
self.keys.shrink_to(min_capacity);
}
/// Shrinks the capacity of just the values, with a lower limit.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = DeqMap::with_capacity(14, 15);
/// dm.extend(0..4);
/// assert_eq![dm.capacity_values(), 15];
/// dm.shrink_values_to(6);
/// assert![dm.capacity_values() >= 6];
/// assert![dm.capacity_values() < 15];
/// assert_eq![dm.capacity_keys(), 14];
/// ```
#[inline]
pub fn shrink_values_to(&mut self, min_capacity: usize) {
self.vals.shrink_to(min_capacity);
}
/// Shrinks the capacity of just the keys, with a lower limit.
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = DeqMap::with_capacity(14, 15);
/// dm.extend_keyed([("a", 1), ("b", 2)]);
/// assert_eq![dm.capacity_keys(), 14];
/// dm.shrink_keys_to(6);
/// assert![dm.capacity_keys() >= 6];
/// assert![dm.capacity_keys() < 14];
/// assert![dm.capacity_values() == 15];
/// ```
#[inline]
pub fn shrink_keys_to(&mut self, min_capacity: usize) {
self.keys.shrink_to(min_capacity);
}
/* slicing */
/// Returns a slice of the values, in order.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u32, u8> = DeqMap::from([3, 4]);
/// assert_eq![dm.as_mut_slice(), &[3, 4]];
/// ```
#[inline]
pub fn as_slice(&mut self) -> &[V] {
self.vals.make_contiguous();
self.vals.as_slices().0
}
/// Returns a mutable slice of the values, in order.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u32, u8> = [3, 4].into();
/// assert_eq![dm.as_mut_slice(), &mut [3, 4]];
/// ```
#[inline]
pub fn as_mut_slice(&mut self) -> &mut [V] {
self.vals.make_contiguous()
}
/* to vec */
/// Returns a vec of the optional keys and values, in order.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, u8> = DeqMap::from([(Some("a"), 1), (None, 2), (Some("c"), 3)]);
/// let vec = dm.to_vec();
///
/// assert_eq![dm.to_vec(), vec![(Some(&"a"), &1), (None, &2), (Some(&"c"), &3)]];
/// ```
#[inline]
pub fn as_vec_with_keys(&self) -> Vec<(Option<&K>, &V)> {
self.iter_with_keys().collect()
}
}
/// # general query, retrieval, insertion & removal
impl<K: Hash + Eq, V> DeqMap<K, V> {
/// Returns the number of (keys, values).
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, u8> = [3].into();
/// dm.insert_back("five", 5);
/// assert_eq![dm.len(), (1, 2)];
/// ```
#[inline]
pub fn len(&self) -> (usize, usize) {
(self.keys.len(), self.vals.len())
}
/// Returns the number of values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, u8> = [3, 4].into();
/// assert_eq![dm.len_values(), 2];
/// ```
#[inline]
pub fn len_values(&self) -> usize {
self.vals.len()
}
/// Returns the number of keys.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from_keyed_array([("c", 3), ("d", 4)]);
/// assert_eq![dm.len_keys(), 2];
/// ```
#[inline]
pub fn len_keys(&self) -> usize {
self.keys.len()
}
/// Returns `true` if there are no values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, i32> = DeqMap::new();
/// assert_eq![dm.is_empty(), true];
///
/// dm.push_back(1);
/// assert_eq![dm.is_empty(), false];
/// ```
#[inline]
pub fn is_empty(&self) -> bool {
self.vals.is_empty()
}
/// Returns `true` if there are no keys.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, i32> = DeqMap::from([1]);
/// assert_eq![dm.has_no_keys(), true];
///
/// dm.insert_back("key", 2);
/// assert_eq![dm.has_no_keys(), false];
/// ```
#[inline]
pub fn has_no_keys(&self) -> bool {
self.keys.is_empty()
}
/// Returns the index of the value at the back, or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, i32>::new();
/// assert_eq![dm.back_index(), None];
///
/// dm.push_back(1);
/// assert_eq![dm.back_index(), Some(0)];
/// ```
#[inline]
pub fn back_index(&self) -> Option<usize> {
let len = self.vals.len();
if len > 0 {
Some(len - 1)
} else {
None
}
}
/// Clears the deqmap, removing all values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from_keyed_array([("c", 3), ("d", 4)]);
/// assert_eq![dm.len(), (2, 2)];
///
/// dm.clear();
/// assert_eq![dm.len(), (0, 0)];
/// ```
#[inline]
pub fn clear(&mut self) {
self.vals.clear();
self.keys.clear();
}
/// Removes all the keys, leaves the values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, i32>::from([("c", 3), ("d", 4)]);
/// assert_eq![dm.len(), (2, 2)];
///
/// dm.clear_keys();
/// assert_eq![dm.len(), (0, 2)];
/// ```
#[inline]
pub fn clear_keys(&mut self) {
self.keys.clear();
}
/// Provides a reference to the front element,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm: DeqMap<&str, _> = [3, 4].into();
/// assert_eq![dm.front(), Some(&3)];
/// ```
#[inline]
pub fn front(&self) -> Option<&V> {
self.vals.front()
}
/// Provides a mutable reference to the front element,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = [3, 4].into();
/// assert_eq![dm.front_mut(), Some(&mut 3)];
/// ```
#[inline]
pub fn front_mut(&mut self) -> Option<&mut V> {
self.vals.front_mut()
}
/// Provides a reference to the front element, alongside its key, if any,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("c", 3), ("d", 4)]);
/// assert_eq![dm.front_with_key(), Some((Some(&"c"), &3))];
/// ```
#[inline]
pub fn front_with_key(&self) -> Option<(Option<&K>, &V)> {
self.get_with_key(0).ok()
}
/// Provides a mutable reference to the front element, alongside its key,
/// if any, or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("c", 3), ("d", 4)]);
/// assert_eq![dm.front_mut_with_key(), Some((Some(&"c"), &mut 3))];
/// ```
#[inline]
pub fn front_mut_with_key(&mut self) -> Option<(Option<&K>, &mut V)> {
self.get_mut_with_key(0).ok()
}
/// Provides a reference to the back element,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = [3, 4].into();
/// assert_eq![dm.back(), Some(&4)];
/// ```
#[inline]
pub fn back(&self) -> Option<&V> {
self.vals.back()
}
/// Provides a mutable reference to the back element,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = [3, 4].into();
/// assert_eq![dm.back_mut(), Some(&mut 4)];
/// ```
#[inline]
pub fn back_mut(&mut self) -> Option<&mut V> {
self.vals.back_mut()
}
/// Provides a reference to the back element, alongside its key, if any,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("c", 3), ("d", 4)]);
/// assert_eq![dm.back_with_key(), Some((Some(&"d"), &4))];
/// ```
#[inline]
pub fn back_with_key(&self) -> Option<(Option<&K>, &V)> {
self.get_with_key(self.back_index()?).ok()
}
/// Provides a mutable reference to the back element, alongside its key,
/// if any, or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("c", 3), ("d", 4)]);
/// assert_eq![dm.back_mut_with_key(), Some((Some(&"d"), &mut 4))];
/// ```
#[inline]
pub fn back_mut_with_key(&mut self) -> Option<(Option<&K>, &mut V)> {
self.get_mut_with_key(self.back_index()?).ok()
}
/// Removes the front element and returns it, or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = [3, 4].into();
///
/// assert_eq![dm.pop_front(), Some(3)];
/// assert_eq![dm.pop_front(), Some(4)];
/// assert_eq![dm.pop_front(), None];
/// ```
#[inline]
pub fn pop_front(&mut self) -> Option<V> {
self.keys.retain(|_, v| {
// retain and and update the entries with values > 0
if *v == 0 {
false
} else {
*v -= 1;
true
}
});
self.vals.pop_front()
}
/// Removes the front element and returns it alongside its key, if any,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([(Some("c"), 3), (Some("d"), 4), (None, 5)]);
///
/// assert_eq![dm.pop_front_with_key(), Some((Some("c"), 3))];
/// assert_eq![dm.pop_front_with_key(), Some((Some("d"), 4))];
/// assert_eq![dm.pop_front_with_key(), Some((None, 5))];
/// assert_eq![dm.pop_front_with_key(), None];
/// ```
#[inline]
pub fn pop_front_with_key(&mut self) -> Option<(Option<K>, V)>
where
K: Clone,
{
const IDX: usize = 0;
let key = self.find_key(IDX).cloned();
// retain and update the entries with values > idx
self.keys.retain(|_, v| {
if *v == IDX {
false
} else {
*v -= 1;
true
}
});
self.vals.pop_front().map(|v| (key, v))
}
/// Removes the back element and returns it, or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<&str, _> = [3, 4].into();
///
/// assert_eq![dm.pop_back(), Some(4)];
/// assert_eq![dm.pop_back(), Some(3)];
/// assert_eq![dm.pop_back(), None];
/// ```
#[inline]
pub fn pop_back(&mut self) -> Option<V> {
// remove any keyed entry pointing to the last value.
let idx = self.back_index()?;
self.keys.retain(|_, v| *v != idx);
self.vals.pop_back()
}
/// Removes the back element and returns it alongside its key, if any,
/// or `None` if the deqmap is empty.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([(None, 2), (Some("c"), 3), (Some("d"), 4)]);
///
/// assert_eq![dm.pop_back_with_key(), Some((Some("d"), 4))];
/// assert_eq![dm.pop_back_with_key(), Some((Some("c"), 3))];
/// assert_eq![dm.pop_back_with_key(), Some((None, 2))];
/// assert_eq![dm.pop_back_with_key(), None];
/// ```
#[inline]
pub fn pop_back_with_key(&mut self) -> Option<(Option<K>, V)>
where
K: Clone,
{
let idx = self.back_index()?;
let key = self.find_key(idx).cloned();
if let Some(ref k) = key {
self.keys.remove_entry(k);
};
self.vals.pop_back().map(|v| (key, v))
}
/// Pushes an unkeyed `value` to the front (index 0).
///
/// This operation updates all entries in the hashmap.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u8, u8> = DeqMap::from([1]);
/// dm.push_front(2);
/// assert_eq!(dm.front(), Some(&2));
/// assert_eq!(dm.back(), Some(&1));
/// ```
#[inline]
pub fn push_front(&mut self, value: V) {
self.vals.push_front(value);
// update all the map values
self.keys.iter_mut().for_each(|(_k, v)| *v += 1);
}
/// Pushes an unkeyed `value` to the back and returns its index.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm: DeqMap<u8, u8> = DeqMap::from([1]);
/// dm.push_back(2);
/// assert_eq!(dm.front(), Some(&1));
/// assert_eq!(dm.back(), Some(&2));
/// ```
#[inline]
pub fn push_back(&mut self, value: V) -> usize {
self.vals.push_back(value);
self.vals.len() - 1
}
/// Inserts a `value` associated to a `key`, at the front of the collection.
///
/// If the `key` doesn't already exist, proceeds with the insertion and
/// returns `None`. Otherwise if the key exists, it remains unchanged and
/// and returns the existing value.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1)]);
/// dm.insert_front("b", 2);
/// assert_eq!(dm.front(), Some(&2));
/// assert_eq!(dm.back(), Some(&1));
/// ```
#[inline]
pub fn insert_front(&mut self, key: K, value: V) -> Option<&V> {
if let Some(idx) = self.keys.get(&key) {
// return existing
self.vals.get(*idx)
} else {
// insert at the front
self.vals.push_front(value);
self.keys.insert(key, 0);
// update map indices
self.keys.iter_mut().for_each(|(_, i)| *i += 1);
None
}
}
/// Inserts a `value` associated to a `key`, at the back of the collection.
///
/// If the `key` doesn't already exist, proceeds with the insertion and
/// returns `None`. Otherwise if the key exists, it remains unchanged and
/// and returns the existing value.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1)]);
/// dm.insert_back("b", 2);
/// assert_eq!(dm.front(), Some(&1));
/// assert_eq!(dm.back(), Some(&2));
/// ```
#[inline]
pub fn insert_back(&mut self, key: K, value: V) -> Option<&V> {
if let Some(idx) = self.keys.get(&key) {
self.vals.get(*idx)
} else {
// insert at the back
self.vals.push_back(value);
self.keys.insert(key, self.vals.len() - 1);
None
}
}
}
/// # query, retrieval, insertion & removal by `key`
impl<K: Hash + Eq, V> DeqMap<K, V> {
/// Returns `true` if the deqmap contains a value with the specified `key`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 1), ("b", 2), ("c", 3)]);
/// assert_eq![dm.contains_key(&"b"), true];
/// assert_eq![dm.contains_key(&"f"), false];
/// ```
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
self.keys.contains_key(key)
}
/// Returns the index of the value associated to the `key`.
///
/// Returns `None` if there is no such key.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 0xA), ("b", 0xB), ("c", 0xC)]);
/// assert_eq![dm.get_index(&"b"), Some(1)];
/// assert_eq![dm.get_index(&"f"), None];
/// ```
#[inline]
pub fn get_index<Q>(&self, key: &Q) -> Option<usize>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
self.keys.get(key).copied()
}
/// Returns a reference to the value associated to the `key`.
///
/// Returns `None` if there is no such key.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 0xA), ("b", 0xB), ("c", 0xC)]);
/// assert_eq![dm.get_keyed(&"b"), Some(&0xB)];
/// assert_eq![dm.get_index(&"f"), None];
/// ```
#[inline]
pub fn get_keyed<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
if let Some(idx) = self.keys.get(key) {
self.vals.get(*idx)
} else {
None
}
}
/// Returns a mutable reference to the value associated to the `key`.
///
/// Returns `None` if there is no such key.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 0xA), ("b", 0xB), ("c", 0xC)]);
/// assert_eq![dm.get_mut_keyed(&"b"), Some(&mut 0xB)];
/// assert_eq![dm.get_mut_keyed(&"f"), None];
/// ```
#[inline]
pub fn get_mut_keyed<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
if let Some(idx) = self.keys.get(key) {
self.vals.get_mut(*idx)
} else {
None
}
}
/// Resets the `old_key` associated with a value, to `new_key`.
///
/// On success returns `true`. Otherwise, if the `old_key` doesn't exists,
/// it does nothing and returns `false`.
///
/// See also [`set_key`][Self::set_key].
///
/// # Errors
/// Errors if `new_key` already exists.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1), ("b", 2), ("c", 3)]);
///
/// assert_eq![dm.reset_key("a", "A"), Ok(true)];
/// assert_eq![dm.reset_key("d", "D"), Ok(false)];
/// assert![dm.reset_key("c", "b").is_err()];
///
/// assert_eq![dm.get_keyed("A"), Some(&1)];
/// assert_eq![dm.get_keyed("b"), Some(&2)];
/// assert_eq![dm.get_keyed("c"), Some(&3)];
/// assert_eq![dm.get_keyed("D"), None];
/// ```
pub fn reset_key<Q>(&mut self, old_key: &Q, new_key: K) -> Result<bool>
where
K: Borrow<Q>,
Q: Hash + Eq + ?Sized,
{
if self.contains_key(new_key.borrow()) {
Err(Error::KeyAlreadyExists)
} else if let Some(v) = self.keys.remove(old_key) {
self.keys.insert(new_key, v);
Ok(true)
} else {
Ok(false)
}
}
}
/// # query, retrieval, insertion & removal by `index`
impl<K: Hash + Eq, V> DeqMap<K, V> {
/// Returns `true` if there is a value at `index`.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::<&str, u8>::from([1, 2]);
/// assert_eq![dm.is_at(0), true];
/// assert_eq![dm.is_at(2), false];
/// ```
#[inline]
pub fn is_at(&self, index: usize) -> bool {
self.len_values() > index
}
/// Returns `true` if there is a value at `index`, with an associated key.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::from([1, 2, 3]);
/// dm.set_key(0, "a");
/// assert_eq![dm.is_keyed_at(0), true];
/// assert_eq![dm.is_keyed_at(1), false];
/// ```
#[inline]
pub fn is_keyed_at(&self, index: usize) -> bool {
self.keys.iter().any(|(_k, &i)| i == index)
}
/// Provides a reference to the value at `index`.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::<&str, _>::from([1, 2, 3]);
/// assert_eq![dm.get(2), Ok(&3)];
/// assert![dm.get(3).is_err()];
/// ```
#[inline]
pub fn get(&self, index: usize) -> Result<&V> {
self.vals.get(index).ok_or(Error::IndexOutOfBounds)
}
/// Provides a mutable reference to the value at `index`.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::<&str, _>::from([1, 2, 3]);
/// assert_eq![dm.get_mut(0), Ok(&mut 1)];
/// assert![dm.get(3).is_err()];
/// ```
#[inline]
pub fn get_mut(&mut self, index: usize) -> Result<&mut V> {
self.vals.get_mut(index).ok_or(Error::IndexOutOfBounds)
}
/// Provides a reference to the value at `index` and to its associated key.
///
/// See also [`find_key_value`][Self::find_key_value], which wont return
/// the value if it has no associated key.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([1, 2]);
/// dm.insert_back("c", 3);
///
/// assert_eq![dm.get_with_key(1), Ok((None, &2))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"c"), &3))];
/// assert![dm.get_with_key(3).is_err()];
/// ```
#[inline]
pub fn get_with_key(&self, index: usize) -> Result<(Option<&K>, &V)> {
if let Some(value) = self.vals.get(index) {
let key = self.find_key(index);
Ok((key, value))
} else {
Err(Error::IndexOutOfBounds)
}
}
/// Provides a mutable reference to the value at `index` and its associated
/// key, if there is any.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([1, 2]);
/// dm.insert_back("c", 3);
///
/// assert_eq![dm.get_mut_with_key(1), Ok((None, &mut 2))];
/// assert_eq![dm.get_mut_with_key(2), Ok((Some(&"c"), &mut 3))];
/// assert![dm.get_mut_with_key(3).is_err()];
/// ```
#[inline]
pub fn get_mut_with_key(&mut self, index: usize) -> Result<(Option<&K>, &mut V)> {
if let Some(value) = self.vals.get_mut(index) {
let key = self
.keys
.iter_mut()
.find_map(|(key, &mut idx)| if idx == index { Some(key) } else { None });
Ok((key, value))
} else {
Err(Error::IndexOutOfBounds)
}
}
/// Provides a reference to the associated key at `index`, or `None`
/// if there is no associated key, or if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::with_capacity(2, 3);
/// dm.push_back(1);
/// dm.insert_back("b", 2);
/// dm.insert_back("c", 3);
///
/// assert_eq![dm.find_key(0), None];
/// assert_eq![dm.find_key(2), Some(&"c")];
/// assert_eq![dm.find_key(9), None];
/// ```
#[inline]
pub fn find_key(&self, index: usize) -> Option<&K> {
self.keys
.iter()
.find_map(|(key, &i)| if i == index { Some(key) } else { None })
}
/// Provides a reference to the associated key, and the value at `index`,
/// or `None` if there is no associated key, or the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::with_capacity(2, 3);
/// dm.push_back(1);
/// dm.insert_back("b", 2);
/// dm.insert_back("c", 3);
///
/// assert_eq![dm.find_key_value(0), None];
/// assert_eq![dm.find_key_value(2), Some((&"c", &3))];
/// assert_eq![dm.find_key_value(9), None];
/// ```
#[inline]
pub fn find_key_value(&self, index: usize) -> Option<(&K, &V)> {
self.keys.iter().find_map(|(key, &i)| {
if i == index {
self.vals.get(i).map(|v| (key, v))
} else {
None
}
})
}
/// Provides the associated key and mutable value at `index`, or `None`
/// if there is no associated key, or if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::with_capacity(2, 3);
/// dm.push_back(1);
/// dm.insert_back("b", 2);
/// dm.insert_back("c", 3);
///
/// assert_eq![dm.find_mut_key_value(0), None];
/// assert_eq![dm.find_mut_key_value(2), Some((&"c", &mut 3))];
/// assert_eq![dm.find_mut_key_value(9), None];
/// ```
#[inline]
pub fn find_mut_key_value(&mut self, index: usize) -> Option<(&K, &mut V)> {
if let Some(key) =
self.keys
.iter_mut()
.find_map(|(key, &mut idx)| if idx == index { Some(key) } else { None })
{
let value = self.vals.get_mut(index).unwrap();
Some((key, value))
} else {
None
}
}
/// Pushes an unkeyed `value` at `index`.
///
/// This operation cycles through all entries in the hashmap.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u16>::from([1, 2, 3]);
///
/// assert![dm.push_at(3, 300).is_err()];
/// assert![dm.push_at(2, 200).is_ok()];
///
/// assert_eq![dm.as_slice(), &[1, 2, 200, 3]];
/// ```
#[inline]
pub fn push_at(&mut self, index: usize, value: V) -> Result<()> {
if index < self.len_values() {
self.push_at_unchecked(index, value);
Ok(())
} else {
Err(Error::IndexOutOfBounds)
}
}
/// Pushes an unkeyed `value` at `index`.
///
/// This operation cycles through all entries in the hashmap.
///
/// # Panics
/// Panics if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u16>::from([1, 2, 3]);
///
/// dm.push_at_unchecked(2, 200);
/// assert_eq![dm.get(2), Ok(&200)];
///
/// use std::panic::catch_unwind;
/// assert![catch_unwind(move || { dm.push_at_unchecked(9, 900); }).is_err()];
/// ```
#[inline]
pub fn push_at_unchecked(&mut self, index: usize, value: V) {
// inserting at `index` shifts the indices >= index
self.vals.insert(index, value);
// update existing map indices
self.keys.iter_mut().for_each(|(_, i)| {
if *i >= index {
*i += 1
}
});
}
/// Inserts a `key`ed `value` at `index`,
/// shifting the columns with a greater index towards the back.
///
/// Returns `None` on successful insertion.
///
/// If the key already exists, the existing value will be returned unmodified.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from(["v1", "v2"]);
///
/// assert![matches![dm.insert_at(1, "k3", "v3"), Ok(None)]];
/// assert_eq![dm.as_slice(), &["v1", "v3", "v2"]];
///
/// // an existing key remains unmodified, exiting value is returned
/// assert![matches![dm.insert_at(1, "k3", "v3_new"), Ok(Some(v)) if *v == "v3"]];
/// // an out-of-bounds index returns an error
/// assert![dm.insert_at(9, "k4", "v4").is_err()];
/// ```
#[inline]
pub fn insert_at(&mut self, index: usize, key: K, value: V) -> Result<Option<&V>> {
if index < self.len_values() {
Ok(self.insert_at_unchecked(index, key, value))
} else {
Err(Error::IndexOutOfBounds)
}
}
/// Inserts a `key`ed `value` at `index`,
/// shifting the columns with a greater index towards the back.
///
/// Returns `None` on successful insertion.
///
/// If the key already exists, the existing value will be returned unmodified.
///
/// # Panics
/// Panics if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from(["v1", "v2"]);
///
/// assert![matches![dm.insert_at_unchecked(1, "k3", "v3"), None]];
/// assert_eq![dm.as_slice(), &["v1", "v3", "v2"]];
///
/// // an existing key remains unmodified, exiting value is returned
/// assert![matches![dm.insert_at_unchecked(1, "k3", "v3_new"), Some(v) if *v == "v3"]];
///
/// use std::panic::catch_unwind;
/// assert![catch_unwind(move || { dm.insert_at_unchecked(9, "k9", "v9"); }).is_err()];
/// ```
#[inline]
pub fn insert_at_unchecked(&mut self, index: usize, key: K, value: V) -> Option<&V> {
if let Some(idx) = self.keys.get(&key) {
self.vals.get(*idx)
} else {
// inserting at `index` shifts the indices >= index
self.vals.insert(index, value);
// update existing map indices before inserting the new one
self.keys.iter_mut().for_each(|(_, i)| {
if *i >= index {
*i += 1
}
});
self.keys.insert(key, index);
None
}
}
/* retain */
/// Retains only the elements specified by the predicate over the values.
///
/// In other words, remove all values `v` for which `f(&v)` returns false,
/// along with their keys, if any.
///
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// This operation is slow, since it first allocates the retained indexes
/// and then iterates over the keys to update them.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 1), ("b", 2), ("c", 3)]);
///
/// dm.retain(|&v| v == 3);
/// assert_eq![dm.as_slice(), &[3]];
/// assert_eq![dm.len(), (1, 1)];
/// ```
#[inline]
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&V) -> bool,
{
self.retain_mut(|elem| f(elem));
}
/// Retains only the elements specified by the predicate over the values.
///
/// In other words, remove all values `v` for which `f(&v)` returns false,
/// along with their keys, if any.
///
/// This method operates in place, visiting each element exactly once in the
/// original order, and preserves the order of the retained elements.
///
/// This operation is slow, because it allocates the retained indexes and
/// then iterates over the keys in order to retain and update them.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::from([("a", 1), ("b", 2), ("c", 3)]);
///
/// dm.retain_mut(|v| if *v == 3 {
/// *v += 1;
/// true
/// } else {
/// false
/// });
/// assert_eq![dm.as_slice(), &[4]];
/// assert_eq![dm.len(), (1, 1)];
/// ```
pub fn retain_mut<F>(&mut self, mut f: F)
where
F: FnMut(&mut V) -> bool,
{
// based on:
// https://doc.rust-lang.org/1.64.0/src/alloc/collections/vec_deque/mod.rs.html#2225
let mut mapretain = vec![];
let mut mapchange = vec![];
let len = self.vals.len();
let mut idx = 0;
let mut cur = 0;
// Stage 1: All values are retained.
while cur < len {
if !f(&mut self.vals[cur]) {
cur += 1;
break;
}
cur += 1;
idx += 1;
}
// Stage 2: Swap retained value into current idx.
while cur < len {
if !f(&mut self.vals[cur]) {
cur += 1;
continue;
}
// save the indexes to determine which keys to retain
mapretain.push(cur);
mapchange.push((cur, idx));
self.vals.swap(idx, cur);
cur += 1;
idx += 1;
}
// Stage 3: Truncate all values after idx.
if cur != idx {
self.vals.truncate(idx);
}
// Stage 4: retain the associated keys
self.keys.retain(|_, &mut ival| {
if let Some(idx) = mapretain.iter().position(|e| e == &ival) {
// removes value for shorter subsequent loops
mapretain.swap_remove(idx);
true
} else {
false
}
});
// Stage 5: update the keys
self.keys.iter_mut().for_each(|(_k, v)| {
let mut idx = 0;
while idx < mapchange.len() {
let (pre_idx, new_idx) = mapchange[idx];
if *v == pre_idx {
*v = new_idx;
// ensure shorter subsequent loops
mapchange.swap_remove(idx);
break;
}
idx += 1;
}
});
}
/* truncate */
/// Shortens the deqmap, keeping the first `len` values and dropping the rest.
///
/// If `len` is greater than the current `len_values`, this has no effect.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1), ("b", 2), ("c", 3)]);
/// assert_eq![dm.len_values(), 3];
///
/// dm.truncate(2);
/// assert_eq![dm.len_values(), 2];
/// assert_eq![dm.pop_back_with_key(), Some((Some("b"), 2))];
/// ```
#[inline]
pub fn truncate(&mut self, len: usize) {
if len <= self.vals.len() {
self.vals.truncate(len);
self.keys.retain(|_, v| *v <= len);
}
}
/* swap */
/// Swaps elements at indices `i` and `j`.
///
/// `i` and `j` may be equal.
///
/// Element at index 0 is the front of the deqmap.
///
/// # Errors
/// Errors if either index is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1), ("b", 2), ("c", 3), ("d", 4)]);
///
/// assert![dm.swap(0, 2).is_ok()];
/// assert_eq![dm.get_with_key(0), Ok((Some(&"c"), &3))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"a"), &1))];
/// assert![dm.swap(0, 7).is_err()];
/// ```
#[inline]
pub fn swap(&mut self, i: usize, j: usize) -> Result<()> {
if i < self.vals.len() && j < self.vals.len() {
self.swap_unchecked(i, j);
Ok(())
} else {
Err(Error::IndexOutOfBounds)
}
}
/// Swaps elements at indices `i` and `j`.
///
/// `i` and `j` may be equal.
///
/// Element at index 0 is the front of the deqmap.
///
/// # Panics
/// Panics if either index is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::from([("a", 1), ("b", 2), ("c", 3), ("d", 4)]);
///
/// dm.swap_unchecked(0, 2);
/// assert_eq![dm.get_with_key(0), Ok((Some(&"c"), &3))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"a"), &1))];
///
/// use std::panic::catch_unwind;
/// assert![catch_unwind(move || dm.swap_unchecked(0, 7)).is_err()];
/// ```
#[inline]
pub fn swap_unchecked(&mut self, i: usize, j: usize) {
self.vals.swap(i, j);
// Update the map, breaking the loop early if we can
let mut counter = 2;
for (_, v) in self.keys.iter_mut() {
if *v == i {
*v = j;
counter -= 1;
} else if *v == j {
*v = i;
counter -= 1;
}
if counter == 0 {
break;
}
}
}
/// Removes an element from anywhere in the deqmap and returns it, replacing
/// it with the first element.
///
/// This does not preserve ordering.
///
/// It's O(1) on the number of values and O(n) on the number of keys.
///
/// Element at index 0 is the front of the queue.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::from([("a", 0xA), ("b", 0xB), ("c", 0xC), ("d", 0xD)]);
///
/// assert_eq![dm.swap_remove_front(2), Ok(0xC)];
/// assert_eq![dm.get_with_key(0), Ok((Some(&"b"), &0xB))];
/// assert_eq![dm.get_with_key(1), Ok((Some(&"a"), &0xA))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"d"), &0xD))];
/// ```
pub fn swap_remove_front(&mut self, index: usize) -> Result<V>
where
V: core::fmt::Debug,
K: core::fmt::Debug,
{
let value = self
.vals
.swap_remove_front(index)
.ok_or(Error::IndexOutOfBounds)?;
self.keys.retain(|_k, ival| {
if *ival == index {
false
} else if *ival == 0 {
*ival = index - 1;
true
} else {
*ival -= 1;
true
}
});
Ok(value)
}
/// Removes an element from anywhere in the deqmap and returns it, replacing
/// it with the last element.
///
/// This does not preserve ordering.
///
/// It's O(1) on the number of values and O(n) on the number of keys.
///
/// Element at index 0 is the front of the queue.
///
/// # Errors
/// Errors if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::from([("a", 0xA), ("b", 0xB), ("c", 0xC), ("d", 0xD)]);
///
/// assert_eq![dm.swap_remove_back(1), Ok(0xB)];
/// assert_eq![dm.get_with_key(0), Ok((Some(&"a"), &0xA))];
/// assert_eq![dm.get_with_key(1), Ok((Some(&"d"), &0xD))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"c"), &0xC))];
/// ```
pub fn swap_remove_back(&mut self, index: usize) -> Result<V> {
let back_idx = self.back_index().ok_or(Error::IndexOutOfBounds)?;
let value = self
.vals
.swap_remove_back(index)
.ok_or(Error::IndexOutOfBounds)?;
self.keys.retain(|_, ival| {
if *ival == index {
false
} else if *ival == back_idx {
*ival = index;
true
} else {
true
}
});
Ok(value)
}
/* set key */
/// Sets the `key` associated with a value at `index`.
///
/// Returns the old key if there was any, or `None` otherwise.
///
/// See also [`reset_key`][Self::reset_key].
///
/// # Errors
/// Errors if the `key` already exists, or if the `index` is out of bounds.
///
/// # Examples
/// ```
/// use deqmap::{DeqMap, DeqMapError};
///
/// let mut dm = DeqMap::from([("a", 1), ("b", 2), ("c", 3)]);
/// dm.push_back(4);
///
/// assert_eq![dm.set_key(0, "A"), Ok(Some("a"))];
/// assert_eq![dm.set_key(3, "d"), Ok(None)];
/// assert_eq![dm.set_key(2, "b"), Err(DeqMapError::KeyAlreadyExists)];
/// assert_eq![dm.set_key(6, "f"), Err(DeqMapError::IndexOutOfBounds)];
///
/// assert_eq![dm.get_keyed("A"), Some(&1)];
/// assert_eq![dm.get_keyed("b"), Some(&2)];
/// assert_eq![dm.get_keyed("c"), Some(&3)];
/// assert_eq![dm.get_keyed("d"), Some(&4)];
/// ```
pub fn set_key(&mut self, index: usize, key: K) -> Result<Option<K>>
where
K: Clone,
{
if self.contains_key(&key) {
Err(Error::KeyAlreadyExists)
} else if index >= self.vals.len() {
Err(Error::IndexOutOfBounds)
} else {
let old_key = self.find_key(index).cloned();
if let Some(ref k) = old_key {
self.keys.remove(k.borrow());
};
self.keys.insert(key, index);
Ok(old_key)
}
}
}
/// # query, retrieval, insertion & removal by `value`
impl<K: Hash + Eq, V> DeqMap<K, V> {
/// Returns `true` if the deqmap contains an element with the given value.
///
/// The operations is *O(n)*.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, _>::from([1, 2, 3]);
///
/// assert_eq![dm.contains(&2), true];
/// assert_eq![dm.contains(&5), false];
/// ```
pub fn contains(&self, value: &V) -> bool
where
V: PartialEq,
{
self.vals.contains(value)
}
/// Extends the deqmap with the contents of an iterator over values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, u8>::new();
///
/// dm.extend(0..5);
/// assert_eq![dm.as_slice(), &[0, 1, 2, 3, 4]];
/// ```
#[inline]
pub fn extend<I>(&mut self, iterator: I)
where
I: IntoIterator<Item = V>,
{
self.vals.extend(iterator);
}
/// Extends the deqmap with the contents of an iterator over `(K, V)` tuples.
///
/// If a key already exists, its associated value will get updated.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::new();
///
/// dm.extend_keyed([("a", 1), ("b", 2), ("c", 3)]);
/// assert_eq![dm.find_key_value(0), Some((&"a", &1))];
/// assert_eq![dm.find_key_value(1), Some((&"b", &2))];
/// assert_eq![dm.find_key_value(2), Some((&"c", &3))];
/// ```
pub fn extend_keyed<I>(&mut self, iterator: I)
where
I: IntoIterator<Item = (K, V)>,
{
let (keys, values): (Vec<_>, Vec<_>) = iterator.into_iter().unzip();
// the index of the next new element
let mut index = self.vals.len();
for (k, v) in keys.into_iter().zip(values) {
match self.keys.entry(k) {
// if the key already exists, just updates the value
Entry::Occupied(_) => self.vals[index] = v,
Entry::Vacant(e) => {
e.insert(index);
self.vals.push_back(v);
index += 1;
}
}
}
}
/// Extends the deqmap with the contents of an iterator over
/// `(Option<K>, V)` tuples.
///
/// If a key already exists, its associated value will get updated.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::new();
///
/// dm.extend_some_keyed([(Some("a"), 1), (None, 2), (Some("c"), 3)]);
/// assert_eq![dm.get_with_key(0), Ok((Some(&"a"), &1))];
/// assert_eq![dm.get_with_key(1), Ok((None, &2))];
/// assert_eq![dm.get_with_key(2), Ok((Some(&"c"), &3))];
/// ```
pub fn extend_some_keyed<I>(&mut self, iterator: I)
where
I: IntoIterator<Item = (Option<K>, V)>,
{
let (keys, values): (Vec<_>, Vec<_>) = iterator.into_iter().unzip();
// the index of the next new element
let mut index = self.vals.len();
for (some_k, v) in keys.into_iter().zip(values) {
if let Some(k) = some_k {
match self.keys.entry(k) {
// if the key already exists, just updates the value
Entry::Occupied(_) => self.vals[index] = v,
Entry::Vacant(e) => {
e.insert(index);
self.vals.push_back(v);
index += 1;
}
}
} else {
self.vals.push_back(v);
index += 1;
}
}
}
}
/// # iterators
impl<K: Hash + Eq, V> DeqMap<K, V> {
/// Returns an iterator over a slice of all the values,
/// (and only the values).
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm = DeqMap::<&str, i32>::from([5, 3, 4]);
/// let b: &[_] = &[&5, &3, &4];
/// let c: Vec<&i32> = dm.iter().collect();
/// assert_eq!(&c[..], b);
/// ```
#[inline]
pub fn iter(&self) -> impl Iterator<Item = &V> {
self.vals.iter()
}
/// Returns a mutable iterator over a slice of all the values.
/// (and only the values).
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut dm = DeqMap::<&str, i32>::from([5, 3, 4]);
/// for val in dm.iter_mut() {
/// *val = *val - 2;
/// }
/// let b: &[_] = &[&3, &1, &2];
/// let c: Vec<&mut i32> = dm.iter_mut().collect();
/// assert_eq!(&c[..], b);
/// ```
#[inline]
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut V> {
self.vals.iter_mut()
}
/// Returns an **unordered** iterator of (key, value) over the keyed values.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut v = DeqMap::new();
/// v.insert_back(-1, 1);
/// v.push_back(2);
/// v.insert_back(-3, 3);
/// v.push_back(4);
///
/// let mut vec: Vec<(&i8, &u8)> = v.iter_keyed().collect();
/// vec.sort();
/// assert_eq![vec, vec![(&-3, &3), (&-1, &1)]];
/// ```
#[inline]
pub fn iter_keyed(&self) -> impl Iterator<Item = (&K, &V)> {
// SAFETY: methods ensure each key points to a valid index
self.keys
.iter()
.map(|(k, idx)| (k, self.vals.get(*idx).unwrap()))
}
/// Returns an iterator over the values, with their optional keys.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let mut v = DeqMap::new();
/// v.insert_back("a", 1);
/// v.push_back(2);
///
/// let mut i = v.iter_with_keys();
/// assert_eq![i.next(), Some((Some(&"a"), &1))];
/// assert_eq![i.next(), Some((None, &2))];
/// assert_eq![i.next(), None];
/// ```
#[inline]
pub fn iter_with_keys(&self) -> DeqMapIter<'_, K, V> {
DeqMapIter { dm: self, idx: 0 }
}
}
impl<K, V> FromIterator<V> for DeqMap<K, V>
where
K: Hash + Eq,
{
fn from_iter<I: IntoIterator<Item = V>>(iter: I) -> Self {
let mut dm = DeqMap::new();
dm.extend(iter);
dm
}
}
impl<K, V> FromIterator<(K, V)> for DeqMap<K, V>
where
K: Hash + Eq,
{
fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let mut dm = DeqMap::new();
dm.extend_keyed(iter);
dm
}
}
/// An iterator over references to values and optional keys of a [`DeqMap`].
pub struct DeqMapIter<'dm, K, V>
where
K: Hash + Eq,
{
idx: usize,
dm: &'dm DeqMap<K, V>,
}
impl<'dm, K, V> Iterator for DeqMapIter<'dm, K, V>
where
K: Hash + Eq,
{
type Item = (Option<&'dm K>, &'dm V);
fn next(&mut self) -> Option<Self::Item> {
if self.dm.vals.get(self.idx).is_some() {
self.idx += 1;
self.dm.get_with_key(self.idx - 1).ok()
} else {
None
}
}
}
// FIXME:
// /// An iterator over mutable references to values and optional keys of a [`DeqMap`].
// pub struct DeqMapIterMut<'dm, K, V>
// where
// K: Hash + Eq,
// {
// idx: usize,
// dm: &'dm mut DeqMap<K, V>,
// }
//
// impl<'dm, 'a, K, V> Iterator for DeqMapIterMut<'dm, K, V>
// where
// K: Hash + Eq,
// {
// type Item = (Option<&'dm K>, &'dm mut V);
// fn next(&'dm mut self) -> Option<Self::Item> {
// // if let Some(v) = self.dm.vec.get(self.idx) {
// if self.dm.vec.get(self.idx).is_some() {
// self.idx += 1;
// self.dm.get_mut_with_key(self.idx -1)
// } else {
// None
// }
// }
// }
/* impl From array */
impl<K: Hash + Eq, V, const N: usize> From<[V; N]> for DeqMap<K, V> {
/// Converts an array of values `[V; N]` into a `DeqMap<_, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// assert_eq![DeqMap::<&str, _>::from([1, 2, 3, 4]), [1, 2, 3, 4].into()];
/// ```
fn from(arr: [V; N]) -> Self {
DeqMap::from_array(arr)
}
}
impl<K: Hash + Eq, V, const N: usize> From<[(K, V); N]> for DeqMap<K, V> {
/// Converts an array of keyed values `[(K, V); N]` into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm1 = DeqMap::<&str, i32>::from([("a", 1), ("b", 2)]);
/// let dm2 = [("a", 1), ("b", 2)].into();
/// assert_eq![dm1, dm2];
/// ```
fn from(arr: [(K, V); N]) -> Self {
DeqMap::from_keyed_array(arr)
}
}
impl<K: Hash + Eq, V, const N: usize> From<[(Option<K>, V); N]> for DeqMap<K, V> {
/// Converts an array of optional keys and values `[(Option<K>, V); N]`
/// into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm1 = DeqMap::<&str, i32>::from([(Some("a"), 1), (None, 2)]);
/// let dm2 = [(Some("a"), 1), (None, 2)].into();
/// assert_eq![dm1, dm2];
/// ```
fn from(arr: [(Option<K>, V); N]) -> Self {
DeqMap::from_some_keyed_array(arr)
}
}
/* impl From vec */
// TODO
impl<K: Hash + Eq, V> From<Vec<V>> for DeqMap<K, V> {
/// Converts a vec of values `Vec<V>` into a `DeqMap<_, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// assert_eq![DeqMap::<&str, _>::from(vec![1, 2, 3, 4]), vec![1, 2, 3, 4].into()];
/// ```
fn from(vec: Vec<V>) -> Self {
DeqMap::from_vec(vec)
}
}
impl<K: Hash + Eq, V> From<Vec<(K, V)>> for DeqMap<K, V> {
/// Converts a vec of keys and values `Vec<K, V>` into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm1 = DeqMap::<&str, i32>::from(vec![("a", 1), ("b", 2)]);
/// let dm2 = vec![("a", 1), ("b", 2)].into();
/// assert_eq![dm1, dm2];
/// ```
fn from(vec: Vec<(K, V)>) -> Self {
DeqMap::from_keyed_vec(vec)
}
}
impl<K: Hash + Eq, V> From<Vec<(Option<K>, V)>> for DeqMap<K, V> {
/// Converts a vec of optional keys and values `Vec<Option<K>, V>`
/// into a `DeqMap<K, V>`.
///
/// # Examples
/// ```
/// use deqmap::DeqMap;
///
/// let dm1 = DeqMap::<&str, i32>::from(vec![(Some("a"), 1), (None, 2)]);
/// let dm2 = vec![(Some("a"), 1), (None, 2)].into();
/// assert_eq![dm1, dm2];
/// ```
fn from(vec: Vec<(Option<K>, V)>) -> Self {
DeqMap::from_some_keyed_vec(vec)
}
}