syd 3.58.0

//
// Syd: rock-solid application kernel
// src/imap.rs: Insertion-order preserving map and set
//
// Copyright (c) 2026 Ali Polatel <alip@chesswob.org>
// Based in part upon the indexmap crate which is:
//   Copyright (c) 2016--2017 The indexmap Developers
//   SPDX-License-Identifier: Apache-2.0 OR MIT
//
// SPDX-License-Identifier: GPL-3.0

// SAFETY: This module has been liberated from unsafe code!
#![forbid(unsafe_code)]
// SAFETY: This module has been liberated from arithmetic side effects!
#![forbid(clippy::arithmetic_side_effects)]
#![forbid(clippy::cast_possible_truncation)]
#![forbid(clippy::cast_possible_wrap)]
#![forbid(clippy::cast_sign_loss)]

//! Insertion-order preserving map and set

use std::{
    borrow::Borrow,
    fmt,
    hash::{BuildHasher, Hash},
};

use nix::errno::Errno;

use crate::hash::SydRandomState;

struct Bucket<K, V> {
    hash: u64,
    key: K,
    value: V,
}

impl<K: Clone, V: Clone> Clone for Bucket<K, V> {
    fn clone(&self) -> Self {
        Bucket {
            hash: self.hash,
            key: self.key.clone(),
            value: self.value.clone(),
        }
    }
}

/// Insertion-order preserving map keyed on `K` with values `V`.
pub struct SydIndexMap<K, V, S = SydRandomState> {
    entries: Vec<Bucket<K, V>>,
    hasher: S,
}

impl<K, V, S: Default> Default for SydIndexMap<K, V, S> {
    fn default() -> Self {
        SydIndexMap {
            entries: Vec::new(),
            hasher: S::default(),
        }
    }
}

impl<K, V, S: Default> SydIndexMap<K, V, S> {
    /// Create a new, empty map.
    pub fn new() -> Self {
        Self::default()
    }

    /// Attempt to create a map able to hold `capacity` entries.
    pub fn try_with_capacity(capacity: usize) -> Result<Self, Errno> {
        Self::try_with_capacity_and_hasher(capacity, S::default())
    }

    /// Attempt to collect iterator into a new map.
    pub fn try_from_iter<I>(iterable: I) -> Result<Self, Errno>
    where
        K: Hash + Eq,
        S: BuildHasher,
        I: IntoIterator<Item = (K, V)>,
    {
        let iter = iterable.into_iter();
        let (lower, _) = iter.size_hint();
        let mut map = Self::try_with_capacity_and_hasher(lower, S::default())?;
        for (key, value) in iter {
            map.try_insert(key, value)?;
        }
        Ok(map)
    }
}

impl<K, V, S> SydIndexMap<K, V, S> {
    /// Create a new, empty map with given hasher.
    pub fn with_hasher(hasher: S) -> Self {
        SydIndexMap {
            entries: Vec::new(),
            hasher,
        }
    }

    /// Attempt to create a map with given hasher able to hold `capacity` entries.
    pub fn try_with_capacity_and_hasher(capacity: usize, hasher: S) -> Result<Self, Errno> {
        let mut entries = Vec::new();
        entries.try_reserve(capacity).or(Err(Errno::ENOMEM))?;
        Ok(SydIndexMap { entries, hasher })
    }

    /// Return number of entries in the map.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Return `true` if map contains no entries.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Remove all entries.
    pub fn clear(&mut self) {
        self.entries.clear();
    }

    /// Return capacity of map.
    pub fn capacity(&self) -> usize {
        self.entries.capacity()
    }

    /// Retain only the entries for which `keep` returns `true`.
    pub fn retain<F>(&mut self, mut keep: F)
    where
        F: FnMut(&K, &mut V) -> bool,
    {
        self.entries
            .retain_mut(|bucket| keep(&bucket.key, &mut bucket.value));
    }

    /// Reserve capacity for at least `additional` more entries.
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), Errno> {
        self.entries.try_reserve(additional).or(Err(Errno::ENOMEM))
    }

    /// Iterate over entries in insertion order as `(&K, &V)`.
    pub fn iter(&self) -> Iter<'_, K, V> {
        Iter {
            inner: self.entries.iter(),
        }
    }

    /// Iterate over entries in insertion order as `(&K, &mut V)`.
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut {
            inner: self.entries.iter_mut(),
        }
    }

    /// Iterate over keys in insertion order.
    pub fn keys(&self) -> Keys<'_, K, V> {
        Keys {
            inner: self.entries.iter(),
        }
    }

    /// Iterate over values in insertion order.
    pub fn values(&self) -> Values<'_, K, V> {
        Values {
            inner: self.entries.iter(),
        }
    }
}

impl<K, V, S: BuildHasher> SydIndexMap<K, V, S> {
    fn hash_of<Q: Hash + ?Sized>(&self, key: &Q) -> u64 {
        self.hasher.hash_one(key)
    }

    /// Return position of `key` in entries, or `None`.
    pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let hash = self.hash_of(key);
        self.entries
            .iter()
            .position(|bucket| bucket.hash == hash && bucket.key.borrow() == key)
    }

    /// Return `true` if the map contains `key`.
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        self.get_index_of(key).is_some()
    }

    /// Return a reference to value for `key`, or `None`.
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let index = self.get_index_of(key)?;
        self.entries.get(index).map(|bucket| &bucket.value)
    }

    /// Return `(key, value)` pair for `key`, or `None`.
    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let index = self.get_index_of(key)?;
        self.entries
            .get(index)
            .map(|bucket| (&bucket.key, &bucket.value))
    }

    /// Return a mutable reference to value for `key`, or `None`.
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let index = self.get_index_of(key)?;
        self.entries.get_mut(index).map(|bucket| &mut bucket.value)
    }

    /// Attempt to insert a key-value pair.
    pub fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, Errno>
    where
        K: Hash + Eq,
    {
        let hash = self.hash_of(&key);
        if let Some(index) = self
            .entries
            .iter()
            .position(|bucket| bucket.hash == hash && bucket.key == key)
        {
            if let Some(bucket) = self.entries.get_mut(index) {
                return Ok(Some(std::mem::replace(&mut bucket.value, value)));
            }
            return Ok(None);
        }
        self.entries.try_reserve(1).or(Err(Errno::ENOMEM))?;
        self.entries.push(Bucket { hash, key, value });
        Ok(None)
    }

    /// Remove `key`, shifting later entries down to preserve order.
    pub fn shift_remove<Q>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let index = self.get_index_of(key)?;
        Some(self.entries.remove(index).value)
    }
}

impl<K, V, S> fmt::Debug for SydIndexMap<K, V, S>
where
    K: fmt::Debug,
    V: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_map()
            .entries(self.entries.iter().map(|b| (&b.key, &b.value)))
            .finish()
    }
}

impl<K, V, S> SydIndexMap<K, V, S>
where
    K: Clone,
    V: Clone,
    S: Clone,
{
    /// Attempt to clone the map.
    pub fn try_clone(&self) -> Result<Self, Errno> {
        let mut entries = Vec::new();
        entries
            .try_reserve_exact(self.entries.len())
            .or(Err(Errno::ENOMEM))?;
        for bucket in &self.entries {
            entries.push(bucket.clone());
        }
        Ok(SydIndexMap {
            entries,
            hasher: self.hasher.clone(),
        })
    }
}

impl<K, V, S1, S2> PartialEq<SydIndexMap<K, V, S2>> for SydIndexMap<K, V, S1>
where
    K: Hash + Eq,
    V: PartialEq,
    S1: BuildHasher,
    S2: BuildHasher,
{
    fn eq(&self, other: &SydIndexMap<K, V, S2>) -> bool {
        self.len() == other.len()
            && self
                .iter()
                .all(|(key, value)| other.get(key).is_some_and(|v| *value == *v))
    }
}

impl<K, V, S> Eq for SydIndexMap<K, V, S>
where
    K: Hash + Eq,
    V: Eq,
    S: BuildHasher,
{
}

/// Borrowed insertion-order iterator over `(&K, &V)`.
pub struct Iter<'a, K, V> {
    inner: std::slice::Iter<'a, Bucket<K, V>>,
}

impl<'a, K, V> Iterator for Iter<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|bucket| (&bucket.key, &bucket.value))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner
            .next_back()
            .map(|bucket| (&bucket.key, &bucket.value))
    }
}

impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}

/// Mutable insertion-order iterator over `(&K, &mut V)`.
pub struct IterMut<'a, K, V> {
    inner: std::slice::IterMut<'a, Bucket<K, V>>,
}

impl<'a, K, V> Iterator for IterMut<'a, K, V> {
    type Item = (&'a K, &'a mut V);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner
            .next()
            .map(|bucket| (&bucket.key, &mut bucket.value))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner
            .next_back()
            .map(|bucket| (&bucket.key, &mut bucket.value))
    }
}

impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {}

/// Owning insertion-order iterator over `(K, V)`.
pub struct IntoIter<K, V> {
    inner: std::vec::IntoIter<Bucket<K, V>>,
}

impl<K, V> Iterator for IntoIter<K, V> {
    type Item = (K, V);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|bucket| (bucket.key, bucket.value))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner
            .next_back()
            .map(|bucket| (bucket.key, bucket.value))
    }
}

impl<K, V> ExactSizeIterator for IntoIter<K, V> {}

/// Insertion-order iterator over `&K`.
pub struct Keys<'a, K, V> {
    inner: std::slice::Iter<'a, Bucket<K, V>>,
}

impl<'a, K, V> Iterator for Keys<'a, K, V> {
    type Item = &'a K;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|bucket| &bucket.key)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|bucket| &bucket.key)
    }
}

impl<K, V> ExactSizeIterator for Keys<'_, K, V> {}

/// Insertion-order iterator over `&V`.
pub struct Values<'a, K, V> {
    inner: std::slice::Iter<'a, Bucket<K, V>>,
}

impl<'a, K, V> Iterator for Values<'a, K, V> {
    type Item = &'a V;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|bucket| &bucket.value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|bucket| &bucket.value)
    }
}

impl<K, V> ExactSizeIterator for Values<'_, K, V> {}

impl<'a, K, V, S> IntoIterator for &'a SydIndexMap<K, V, S> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;

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

impl<K, V, S> IntoIterator for SydIndexMap<K, V, S> {
    type Item = (K, V);
    type IntoIter = IntoIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner: self.entries.into_iter(),
        }
    }
}

/// Insertion-order preserving set of `T`.
pub struct SydIndexSet<T, S = SydRandomState> {
    map: SydIndexMap<T, (), S>,
}

impl<T, S: Default> Default for SydIndexSet<T, S> {
    fn default() -> Self {
        SydIndexSet {
            map: SydIndexMap::default(),
        }
    }
}

impl<T, S: Default> SydIndexSet<T, S> {
    /// Create a new, empty set.
    pub fn new() -> Self {
        Self::default()
    }

    /// Attempt to collect iterator into a new set.
    pub fn try_from_iter<I>(iterable: I) -> Result<Self, Errno>
    where
        T: Hash + Eq,
        S: BuildHasher,
        I: IntoIterator<Item = T>,
    {
        let iter = iterable.into_iter();
        let (lower, _) = iter.size_hint();
        let mut set = Self::with_capacity_hasher(lower, S::default())?;
        for value in iter {
            set.try_insert(value)?;
        }
        Ok(set)
    }
}

impl<T, S> SydIndexSet<T, S> {
    /// Create a new, empty set with given hasher.
    pub fn with_hasher(hasher: S) -> Self {
        SydIndexSet {
            map: SydIndexMap::with_hasher(hasher),
        }
    }

    fn with_capacity_hasher(capacity: usize, hasher: S) -> Result<Self, Errno> {
        Ok(SydIndexSet {
            map: SydIndexMap::try_with_capacity_and_hasher(capacity, hasher)?,
        })
    }

    /// Return number of values in set.
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Return `true` if set contains no values.
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Iterate over values in insertion order.
    pub fn iter(&self) -> SetIter<'_, T> {
        SetIter {
            inner: self.map.keys(),
        }
    }
}

impl<T, S: BuildHasher> SydIndexSet<T, S> {
    /// Return `true` if set contains `value`.
    pub fn contains<Q>(&self, value: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        self.map.contains_key(value)
    }

    /// Attempt to insert `value`
    ///
    /// Return `true` if it was newly inserted.
    pub fn try_insert(&mut self, value: T) -> Result<bool, Errno>
    where
        T: Hash + Eq,
    {
        Ok(self.map.try_insert(value, ())?.is_none())
    }
}

/// Owning insertion-order iterator over set values `T`.
pub struct SetIntoIter<T> {
    inner: IntoIter<T, ()>,
}

impl<T> Iterator for SetIntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(value, ())| value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<T> ExactSizeIterator for SetIntoIter<T> {}

impl<T, S> IntoIterator for SydIndexSet<T, S> {
    type Item = T;
    type IntoIter = SetIntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        SetIntoIter {
            inner: self.map.into_iter(),
        }
    }
}

impl<T: fmt::Debug, S> fmt::Debug for SydIndexSet<T, S> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.iter()).finish()
    }
}

/// Insertion-order iterator over `&T`.
pub struct SetIter<'a, T> {
    inner: Keys<'a, T, ()>,
}

impl<'a, T> Iterator for SetIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<T> DoubleEndedIterator for SetIter<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back()
    }
}

impl<T> ExactSizeIterator for SetIter<'_, T> {}

impl<'a, T, S> IntoIterator for &'a SydIndexSet<T, S> {
    type Item = &'a T;
    type IntoIter = SetIter<'a, T>;

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

#[cfg(test)]
#[allow(clippy::disallowed_methods)]
mod tests {
    use super::*;

    fn map() -> SydIndexMap<u64, u64> {
        SydIndexMap::default()
    }

    fn ins(map: &mut SydIndexMap<u64, u64>, key: u64, value: u64) -> Option<u64> {
        map.try_insert(key, value).unwrap()
    }

    fn set_of(values: impl IntoIterator<Item = u64>) -> SydIndexSet<u64> {
        SydIndexSet::try_from_iter(values).unwrap()
    }

    #[test]
    fn test_new_1() {
        let map: SydIndexMap<u64, u64> = SydIndexMap::new();
        assert!(map.is_empty());
        assert_eq!(map.len(), 0);
    }

    #[test]
    fn test_default_1() {
        let map: SydIndexMap<u64, u64> = SydIndexMap::default();
        assert!(map.is_empty());
    }

    #[test]
    fn test_with_hasher_1() {
        let mut map: SydIndexMap<u64, u64> = SydIndexMap::with_hasher(SydRandomState::default());
        assert!(map.is_empty());
        assert_eq!(ins(&mut map, 1, 10), None);
        assert_eq!(map.get(&1), Some(&10));
    }

    #[test]
    fn test_try_with_capacity_1() {
        let map: SydIndexMap<u64, u64> = SydIndexMap::try_with_capacity(8).unwrap();
        assert!(map.is_empty());
        assert!(map.capacity() >= 8);
    }

    #[test]
    fn test_try_reserve_1() {
        let mut map = map();
        assert!(map.try_reserve(16).is_ok());
        assert!(map.capacity() >= 16);
    }

    #[test]
    fn test_capacity_1() {
        assert_eq!(map().capacity(), 0);
    }

    #[test]
    fn test_try_insert_1() {
        let mut map = map();
        assert_eq!(map.try_insert(1, 10), Ok(None));
        assert_eq!(map.try_insert(1, 11), Ok(Some(10)));
        assert_eq!(map.len(), 1);
        assert_eq!(map.get(&1), Some(&11));
    }

    #[test]
    fn test_try_insert_2() {
        let mut map = map();
        assert_eq!(ins(&mut map, 1, 10), None);
        assert_eq!(ins(&mut map, 2, 20), None);
        assert_eq!(map.len(), 2);
        assert_eq!(map.get(&1), Some(&10));
        assert_eq!(map.get(&3), None);
    }

    #[test]
    fn test_try_clone_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        let mut clone = map.try_clone().unwrap();
        assert_eq!(ins(&mut clone, 2, 20), None);
        assert_eq!(map.len(), 1);
        assert_eq!(clone.len(), 2);
        assert_eq!(clone.get(&1), Some(&10));
    }

    #[test]
    fn test_get_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        assert_eq!(map.get(&1), Some(&10));
        assert_eq!(map.get(&2), None);
    }

    #[test]
    fn test_get_mut_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        if let Some(value) = map.get_mut(&1) {
            *value = 99;
        }
        assert_eq!(map.get(&1), Some(&99));
        assert!(map.get_mut(&2).is_none());
    }

    #[test]
    fn test_get_key_value_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        assert_eq!(map.get_key_value(&1), Some((&1, &10)));
        assert_eq!(map.get_key_value(&2), None);
    }

    #[test]
    fn test_get_index_of_1() {
        let mut map = map();
        ins(&mut map, 5, 50);
        ins(&mut map, 6, 60);
        assert_eq!(map.get_index_of(&5), Some(0));
        assert_eq!(map.get_index_of(&6), Some(1));
        assert_eq!(map.get_index_of(&7), None);
    }

    #[test]
    fn test_contains_key_1() {
        let mut map = map();
        ins(&mut map, 7, 70);
        assert!(map.contains_key(&7));
        assert!(!map.contains_key(&8));
    }

    #[test]
    fn test_shift_remove_1() {
        let mut map = map();
        for key in [1u64, 2, 3, 4] {
            ins(&mut map, key, key);
        }
        assert_eq!(map.shift_remove(&2), Some(2));
        assert_eq!(map.shift_remove(&2), None);
        let keys: Vec<u64> = map.keys().copied().collect();
        assert_eq!(keys, vec![1, 3, 4]);
    }

    #[test]
    fn test_clear_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        map.clear();
        assert!(map.is_empty());
    }

    #[test]
    fn test_retain_1() {
        let mut map = map();
        for key in [1u64, 2, 3, 4] {
            ins(&mut map, key, key);
        }
        map.retain(|key, _value| key % 2 == 0);
        let keys: Vec<u64> = map.keys().copied().collect();
        assert_eq!(keys, vec![2, 4]);
    }

    #[test]
    fn test_iter_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        ins(&mut map, 2, 20);
        assert_eq!(map.iter().len(), 2);
        let fwd: Vec<(u64, u64)> = map.iter().map(|(k, v)| (*k, *v)).collect();
        assert_eq!(fwd, vec![(1, 10), (2, 20)]);
        let rev: Vec<(u64, u64)> = map.iter().rev().map(|(k, v)| (*k, *v)).collect();
        assert_eq!(rev, vec![(2, 20), (1, 10)]);
    }

    #[test]
    fn test_iter_mut_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        ins(&mut map, 2, 20);
        assert_eq!(map.iter_mut().len(), 2);
        for (_key, value) in map.iter_mut() {
            *value = value.saturating_add(1);
        }
        for (_key, value) in map.iter_mut().rev() {
            *value = value.saturating_add(1);
        }
        let values: Vec<u64> = map.values().copied().collect();
        assert_eq!(values, vec![12, 22]);
    }

    #[test]
    fn test_keys_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        ins(&mut map, 2, 20);
        assert_eq!(map.keys().len(), 2);
        let fwd: Vec<u64> = map.keys().copied().collect();
        assert_eq!(fwd, vec![1, 2]);
        let rev: Vec<u64> = map.keys().rev().copied().collect();
        assert_eq!(rev, vec![2, 1]);
    }

    #[test]
    fn test_values_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        ins(&mut map, 2, 20);
        assert_eq!(map.values().len(), 2);
        let fwd: Vec<u64> = map.values().copied().collect();
        assert_eq!(fwd, vec![10, 20]);
        let rev: Vec<u64> = map.values().rev().copied().collect();
        assert_eq!(rev, vec![20, 10]);
    }

    #[test]
    fn test_into_iter_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        ins(&mut map, 2, 20);
        let it = map.try_clone().unwrap().into_iter();
        assert_eq!(it.len(), 2);
        let fwd: Vec<(u64, u64)> = it.collect();
        assert_eq!(fwd, vec![(1, 10), (2, 20)]);
        let rev: Vec<(u64, u64)> = map.into_iter().rev().collect();
        assert_eq!(rev, vec![(2, 20), (1, 10)]);
    }

    #[test]
    fn test_into_iter_2() {
        let mut map = map();
        ins(&mut map, 1, 10);
        let pairs: Vec<(u64, u64)> = (&map).into_iter().map(|(k, v)| (*k, *v)).collect();
        assert_eq!(pairs, vec![(1, 10)]);
    }

    #[test]
    fn test_debug_1() {
        let mut map = map();
        ins(&mut map, 1, 10);
        assert_eq!(format!("{map:?}"), "{1: 10}");
    }

    #[test]
    fn test_partial_eq_1() {
        let mut a = map();
        ins(&mut a, 1, 10);
        ins(&mut a, 2, 20);
        let mut b = map();
        ins(&mut b, 2, 20);
        ins(&mut b, 1, 10);
        assert_eq!(a, b);
        ins(&mut b, 1, 99);
        assert_ne!(a, b);
    }

    #[test]
    fn test_try_from_iter_1() {
        let map: SydIndexMap<u64, u64> =
            SydIndexMap::try_from_iter([(1, 10), (2, 20), (1, 11)]).unwrap();
        assert_eq!(map.len(), 2);
        assert_eq!(map.get(&1), Some(&11));
        assert_eq!(map.get_index_of(&1), Some(0));
    }

    #[test]
    fn test_borrowed_key_1() {
        let mut map: SydIndexMap<String, u64> = SydIndexMap::default();
        map.try_insert("hello".to_string(), 1).unwrap();
        assert_eq!(map.get("hello"), Some(&1));
        assert!(map.contains_key("hello"));
        assert_eq!(map.get_key_value("hello"), Some((&"hello".to_string(), &1)));
        assert_eq!(map.shift_remove("hello"), Some(1));
    }

    #[test]
    fn test_set_new_1() {
        let set: SydIndexSet<u64> = SydIndexSet::new();
        assert!(set.is_empty());
        assert_eq!(set.len(), 0);
    }

    #[test]
    fn test_set_default_1() {
        let set: SydIndexSet<u64> = SydIndexSet::default();
        assert!(set.is_empty());
    }

    #[test]
    fn test_set_with_hasher_1() {
        let mut set: SydIndexSet<u64> = SydIndexSet::with_hasher(SydRandomState::default());
        assert_eq!(set.try_insert(1), Ok(true));
        assert!(set.contains(&1));
    }

    #[test]
    fn test_set_try_insert_1() {
        let mut set: SydIndexSet<u64> = SydIndexSet::new();
        assert_eq!(set.try_insert(1), Ok(true));
        assert_eq!(set.try_insert(1), Ok(false));
        assert_eq!(set.len(), 1);
    }

    #[test]
    fn test_set_contains_1() {
        let set = set_of([1u64]);
        assert!(set.contains(&1));
        assert!(!set.contains(&2));
    }

    #[test]
    fn test_set_iter_1() {
        let set = set_of([3u64, 1, 2]);
        assert_eq!(set.iter().len(), 3);
        let fwd: Vec<u64> = set.iter().copied().collect();
        assert_eq!(fwd, vec![3, 1, 2]);
        let rev: Vec<u64> = set.iter().rev().copied().collect();
        assert_eq!(rev, vec![2, 1, 3]);
    }

    #[test]
    fn test_set_into_iter_1() {
        let set = set_of([3u64, 1, 2]);
        let it = set.into_iter();
        assert_eq!(it.len(), 3);
        let values: Vec<u64> = it.collect();
        assert_eq!(values, vec![3, 1, 2]);
    }

    #[test]
    fn test_set_into_iter_2() {
        let set = set_of([1u64, 2, 3]);
        let values: Vec<u64> = (&set).into_iter().copied().collect();
        assert_eq!(values, vec![1, 2, 3]);
    }

    #[test]
    fn test_set_debug_1() {
        let set = set_of([1u64]);
        assert_eq!(format!("{set:?}"), "{1}");
    }

    #[test]
    fn test_set_try_from_iter_1() {
        let set: SydIndexSet<u64> = SydIndexSet::try_from_iter([3u64, 1, 3, 2, 1]).unwrap();
        assert_eq!(set.len(), 3);
        let values: Vec<u64> = set.iter().copied().collect();
        assert_eq!(values, vec![3, 1, 2]);
    }
}