iddqd/tri_hash_map/

imp.rs

use super::{IntoIter, Iter, IterMut, RefMut, tables::TriHashMapTables};
use crate::{
    DefaultHashBuilder, TriHashItem,
    errors::{DuplicateItem, TryReserveError},
    internal::ValidationError,
    support::{
        ItemIndex,
        alloc::{Allocator, Global, global_alloc},
        fmt_utils::StrDisplayAsDebug,
        hash_table,
        item_set::ItemSet,
        map_hash::MapHash,
    },
};
use alloc::{collections::BTreeSet, vec::Vec};
use core::{
    fmt,
    hash::{BuildHasher, Hash},
};
use equivalent::Equivalent;

#[derive(Debug)]
#[must_use]
struct PreparedDuplicate {
    index: ItemIndex,
    hashes: [MapHash; 3],
}

impl PreparedDuplicate {
    fn from_indexes<const N: usize>(
        indexes: [Option<ItemIndex>; N],
        mut prepare: impl FnMut(ItemIndex) -> Self,
    ) -> Vec<Self> {
        let mut duplicates = Vec::new();

        for index in indexes.into_iter().flatten() {
            if duplicates
                .iter()
                .any(|duplicate: &PreparedDuplicate| duplicate.index == index)
            {
                continue;
            }

            duplicates.push(prepare(index));
        }

        duplicates
    }
}

#[derive(Debug)]
#[must_use]
struct PreparedInsertOverwrite {
    duplicates: Vec<PreparedDuplicate>,
    hashes: [MapHash; 3],
}

impl PreparedInsertOverwrite {
    #[inline]
    fn duplicate_count(&self) -> usize {
        self.duplicates.len()
    }

    #[inline]
    fn needs_new_item_slot(&self) -> bool {
        self.duplicates.is_empty()
    }
}

/// A 1:1:1 (trijective) map for three keys and a value.
///
/// The storage mechanism is a list of items with an embedded free chain, with
/// indexes to occupied slots stored in three hash tables. This allows for
/// efficient lookups by any of the three keys, while preventing duplicates.
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
///
/// #[derive(Debug, PartialEq, Eq)]
/// struct Person {
///     id: u32,
///     email: String,
///     phone: String,
///     name: String,
/// }
///
/// // Implement TriHashItem to define the three key types.
/// impl TriHashItem for Person {
///     type K1<'a> = u32;
///     type K2<'a> = &'a str;
///     type K3<'a> = &'a str;
///
///     fn key1(&self) -> Self::K1<'_> {
///         self.id
///     }
///
///     fn key2(&self) -> Self::K2<'_> {
///         &self.email
///     }
///
///     fn key3(&self) -> Self::K3<'_> {
///         &self.phone
///     }
///
///     tri_upcast!();
/// }
///
/// // Create a TriHashMap and insert items.
/// let mut people = TriHashMap::new();
/// people
///     .insert_unique(Person {
///         id: 1,
///         email: "alice@example.com".to_string(),
///         phone: "555-1234".to_string(),
///         name: "Alice".to_string(),
///     })
///     .unwrap();
///
/// // Lookup by any of the three keys.
/// let person = people.get1(&1).unwrap();
/// assert_eq!(person.name, "Alice");
///
/// let person = people.get2("alice@example.com").unwrap();
/// assert_eq!(person.id, 1);
///
/// let person = people.get3("555-1234").unwrap();
/// assert_eq!(person.email, "alice@example.com");
/// # }
/// ```
#[derive(Clone)]
pub struct TriHashMap<T, S = DefaultHashBuilder, A: Allocator = Global> {
    pub(super) items: ItemSet<T, A>,
    // Invariant: the values (ItemIndex) in these tables are valid indexes into
    // `items`, and are a 1:1 mapping.
    tables: TriHashMapTables<S, A>,
}

impl<T: TriHashItem, S: Default, A: Allocator + Default> Default
    for TriHashMap<T, S, A>
{
    fn default() -> Self {
        Self {
            items: ItemSet::with_capacity_in(0, A::default()),
            tables: TriHashMapTables::default(),
        }
    }
}

#[cfg(feature = "default-hasher")]
impl<T: TriHashItem> TriHashMap<T> {
    /// Creates a new, empty `TriHashMap`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let map: TriHashMap<Person> = TriHashMap::new();
    /// assert!(map.is_empty());
    /// assert_eq!(map.len(), 0);
    /// # }
    /// ```
    #[inline]
    pub fn new() -> Self {
        Self { items: ItemSet::new(), tables: TriHashMapTables::default() }
    }

    /// Creates a new `TriHashMap` with the given capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let map: TriHashMap<Person> = TriHashMap::with_capacity(10);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, global_alloc()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                capacity,
                DefaultHashBuilder::default(),
                global_alloc(),
            ),
        }
    }
}

impl<T: TriHashItem, S: BuildHasher> TriHashMap<T, S> {
    /// Creates a new, empty `TriHashMap` with the given hasher.
    ///
    /// # Examples
    ///
    /// ```
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    /// use std::collections::hash_map::RandomState;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let map: TriHashMap<Person, RandomState> =
    ///     TriHashMap::with_hasher(RandomState::new());
    /// assert!(map.is_empty());
    /// ```
    pub const fn with_hasher(hasher: S) -> Self {
        Self {
            items: ItemSet::new(),
            tables: TriHashMapTables::with_hasher(hasher),
        }
    }

    /// Creates a new `TriHashMap` with the given capacity and hasher.
    ///
    /// # Examples
    ///
    /// ```
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    /// use std::collections::hash_map::RandomState;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let map: TriHashMap<Person, RandomState> =
    ///     TriHashMap::with_capacity_and_hasher(10, RandomState::new());
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// ```
    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, global_alloc()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                capacity,
                hasher,
                global_alloc(),
            ),
        }
    }
}

#[cfg(feature = "default-hasher")]
impl<T: TriHashItem, A: Clone + Allocator>
    TriHashMap<T, DefaultHashBuilder, A>
{
    /// Creates a new empty `TriHashMap` using the given allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new TriHashMap using the allocator.
    /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::new_in(&bump);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn new_in(alloc: A) -> Self {
        Self {
            items: ItemSet::with_capacity_in(0, alloc.clone()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                0,
                DefaultHashBuilder::default(),
                alloc,
            ),
        }
    }

    /// Creates an empty `TriHashMap` with the specified capacity using the given
    /// allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new TriHashMap with capacity using the allocator.
    /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::with_capacity_in(10, &bump);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                capacity,
                DefaultHashBuilder::default(),
                alloc,
            ),
        }
    }
}

impl<T: TriHashItem, S: Clone + BuildHasher, A: Clone + Allocator>
    TriHashMap<T, S, A>
{
    /// Creates a new, empty `TriHashMap` with the given hasher and allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(feature = "allocator-api2")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    /// use std::collections::hash_map::RandomState;
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// let hasher = RandomState::new();
    /// // Create a new TriHashMap with hasher using the allocator.
    /// let map: TriHashMap<Person, _, &bumpalo::Bump> =
    ///     TriHashMap::with_hasher_in(hasher, &bump);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
        Self {
            items: ItemSet::with_capacity_in(0, alloc.clone()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                0,
                hasher.clone(),
                alloc,
            ),
        }
    }

    /// Creates a new `TriHashMap` with the given capacity, hasher, and
    /// allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(feature = "allocator-api2")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    /// use std::collections::hash_map::RandomState;
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// let hasher = RandomState::new();
    /// // Create a new TriHashMap with capacity and hasher using the allocator.
    /// let map: TriHashMap<Person, _, &bumpalo::Bump> =
    ///     TriHashMap::with_capacity_and_hasher_in(10, hasher, &bump);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity_and_hasher_in(
        capacity: usize,
        hasher: S,
        alloc: A,
    ) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
            tables: TriHashMapTables::with_capacity_and_hasher_in(
                capacity, hasher, alloc,
            ),
        }
    }
}

impl<T: TriHashItem, S: Default + Clone + BuildHasher, A: Allocator + Default>
    TriHashMap<T, S, A>
{
    /// Creates a new `TriHashMap` from an iterator of values, rejecting
    /// duplicates.
    ///
    /// A value conflicts when any of its keys matches an already-inserted
    /// item, so a single value can collide with up to three distinct
    /// existing items (one per key). On the first conflict, this returns a
    /// [`DuplicateItem`] error containing the new value and every
    /// conflicting item.
    ///
    /// To overwrite duplicates instead, use [`TriHashMap::from_iter`].
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let items = vec![
    ///     Item {
    ///         id: 1,
    ///         name: "foo".to_string(),
    ///         email: "foo@example.com".to_string(),
    ///     },
    ///     Item {
    ///         id: 2,
    ///         name: "bar".to_string(),
    ///         email: "bar@example.com".to_string(),
    ///     },
    /// ];
    ///
    /// // Successful creation with unique keys.
    /// let map: TriHashMap<Item> = TriHashMap::from_iter_unique(items).unwrap();
    /// assert_eq!(map.len(), 2);
    /// assert_eq!(map.get1(&1).unwrap().name, "foo");
    ///
    /// // Error with a duplicate key3.
    /// let duplicate_items = vec![
    ///     Item {
    ///         id: 1,
    ///         name: "foo".to_string(),
    ///         email: "dup@example.com".to_string(),
    ///     },
    ///     Item {
    ///         id: 2,
    ///         name: "bar".to_string(),
    ///         email: "dup@example.com".to_string(),
    ///     },
    /// ];
    /// assert!(TriHashMap::<Item>::from_iter_unique(duplicate_items).is_err());
    /// # }
    /// ```
    pub fn from_iter_unique<I: IntoIterator<Item = T>>(
        iter: I,
    ) -> Result<Self, DuplicateItem<T>> {
        let iter = iter.into_iter();
        let mut map = Self::default();
        map.reserve(iter.size_hint().0);
        for value in iter {
            if let Err((value, indexes)) =
                map.insert_unique_or_dup_indexes(value)
            {
                // Removal produces owned duplicates, so that we don't need to
                // specify `T: Clone` here.
                let duplicates = indexes
                    .iter()
                    .map(|ix| {
                        map.remove_by_index(*ix)
                            .expect("duplicate index is present")
                    })
                    .collect();
                return Err(DuplicateItem::__internal_new(value, duplicates));
            }
        }

        Ok(map)
    }
}

impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> TriHashMap<T, S, A> {
    /// Returns the hasher.
    #[cfg(feature = "daft")]
    #[inline]
    pub(crate) fn hasher(&self) -> &S {
        self.tables.hasher()
    }

    /// Returns the allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{TriHashMap, TriHashItem, tri_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new TriHashMap using the allocator.
    /// let map: TriHashMap<Person, _, &bumpalo::Bump> = TriHashMap::new_in(&bump);
    /// // Access the allocator.
    /// let allocator = map.allocator();
    /// # }
    /// ```
    #[inline]
    pub fn allocator(&self) -> &A {
        self.items.allocator()
    }

    /// Returns the currently allocated capacity of the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let map: TriHashMap<Person> = TriHashMap::with_capacity(10);
    /// assert!(map.capacity() >= 10);
    /// # }
    /// ```
    pub fn capacity(&self) -> usize {
        // items and tables.capacity might theoretically diverge: use
        // items.capacity.
        self.items.capacity()
    }

    /// Returns true if the map is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// assert!(map.is_empty());
    ///
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    /// assert!(!map.is_empty());
    /// # }
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    /// Returns the number of items in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// assert_eq!(map.len(), 0);
    ///
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    /// map.insert_unique(Person {
    ///     id: 2,
    ///     email: "bob@example.com".to_string(),
    ///     phone: "555-5678".to_string(),
    ///     name: "Bob".to_string(),
    /// })
    /// .unwrap();
    /// assert_eq!(map.len(), 2);
    /// # }
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.items.len()
    }

    /// Clears the map, removing all items.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    /// assert_eq!(map.len(), 1);
    ///
    /// map.clear();
    /// assert!(map.is_empty());
    /// assert_eq!(map.len(), 0);
    /// # }
    /// ```
    pub fn clear(&mut self) {
        // Clear the internal indexes before dropping items. This way, if a user
        // `Drop` panics during `self.items.clear()`, the tables cannot retain
        // indexes pointing to removed item slots.
        self.tables.k1_to_item.clear();
        self.tables.k2_to_item.clear();
        self.tables.k3_to_item.clear();
        self.items.clear();
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the `TriHashMap`. The collection may reserve more space to
    /// speculatively avoid frequent reallocations. After calling `reserve`,
    /// capacity will be greater than or equal to `self.len() + additional`.
    /// Does nothing if capacity is already sufficient.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows [`isize::MAX`] bytes, and
    /// [`abort`]s the program in case of an allocation error. Use
    /// [`try_reserve`](Self::try_reserve) instead if you want to handle memory
    /// allocation failure.
    ///
    /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
    /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map: TriHashMap<Item> = TriHashMap::new();
    /// map.reserve(100);
    /// assert!(map.capacity() >= 100);
    /// # }
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        self.items.reserve(additional);
        self.tables.k1_to_item.reserve(additional);
        self.tables.k2_to_item.reserve(additional);
        self.tables.k3_to_item.reserve(additional);
    }

    /// Tries to reserve capacity for at least `additional` more elements to be
    /// inserted in the `TriHashMap`. 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 the capacity overflows, or the allocator reports a failure, then an
    /// error is returned.
    ///
    /// # Notes
    ///
    /// If reservation fails partway through, some internal structures may have
    /// already increased their capacity. The map remains in a valid state but
    /// may have uneven capacities across its internal structures.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map: TriHashMap<Item> = TriHashMap::new();
    /// map.try_reserve(100).expect("allocation should succeed");
    /// assert!(map.capacity() >= 100);
    /// # }
    /// ```
    pub fn try_reserve(
        &mut self,
        additional: usize,
    ) -> Result<(), crate::errors::TryReserveError> {
        self.items.try_reserve(additional)?;
        self.tables
            .k1_to_item
            .try_reserve(additional)
            .map_err(crate::errors::TryReserveError::from_hashbrown)?;
        self.tables
            .k2_to_item
            .try_reserve(additional)
            .map_err(crate::errors::TryReserveError::from_hashbrown)?;
        self.tables
            .k3_to_item
            .try_reserve(additional)
            .map_err(crate::errors::TryReserveError::from_hashbrown)?;
        Ok(())
    }

    /// Shrinks the capacity of the map as much as possible. It will drop
    /// down as much as possible while maintaining the internal rules
    /// and possibly leaving some space in accordance with the resize policy.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map: TriHashMap<Item> = TriHashMap::with_capacity(100);
    /// map.insert_unique(Item {
    ///     id: 1,
    ///     name: "foo".to_string(),
    ///     email: "foo@example.com".to_string(),
    /// })
    /// .unwrap();
    /// map.insert_unique(Item {
    ///     id: 2,
    ///     name: "bar".to_string(),
    ///     email: "bar@example.com".to_string(),
    /// })
    /// .unwrap();
    /// assert!(map.capacity() >= 100);
    /// map.shrink_to_fit();
    /// assert!(map.capacity() >= 2);
    /// # }
    /// ```
    pub fn shrink_to_fit(&mut self) {
        // Sequence this carefully.
        //
        // * First, compact the item set. This does not allocate through A
        //   (it allocates a small remap buffer through the global allocator),
        //   and returns a remapper.
        // * Then, remap the tables using the remapper.
        // * Finally, shrink the capacities of the tables and items.
        //
        // An allocator panic during either capacity shrink leaves the tables
        // and items already in sync, because remap has already been committed.
        let remap = self.items.compact();
        if !remap.is_identity() {
            self.tables.k1_to_item.remap_indexes(&remap);
            self.tables.k2_to_item.remap_indexes(&remap);
            self.tables.k3_to_item.remap_indexes(&remap);
        }
        self.items.shrink_capacity_to_fit();
        self.tables.k1_to_item.shrink_to_fit();
        self.tables.k2_to_item.shrink_to_fit();
        self.tables.k3_to_item.shrink_to_fit();
    }

    /// Shrinks the capacity of the map with a lower limit. It will drop
    /// down no lower than the supplied limit while maintaining the internal
    /// rules and possibly leaving some space in accordance with the resize
    /// policy.
    ///
    /// If the current capacity is less than the lower limit, this is a no-op.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map: TriHashMap<Item> = TriHashMap::with_capacity(100);
    /// map.insert_unique(Item {
    ///     id: 1,
    ///     name: "foo".to_string(),
    ///     email: "foo@example.com".to_string(),
    /// })
    /// .unwrap();
    /// map.insert_unique(Item {
    ///     id: 2,
    ///     name: "bar".to_string(),
    ///     email: "bar@example.com".to_string(),
    /// })
    /// .unwrap();
    /// assert!(map.capacity() >= 100);
    /// map.shrink_to(10);
    /// assert!(map.capacity() >= 10);
    /// map.shrink_to(0);
    /// assert!(map.capacity() >= 2);
    /// # }
    /// ```
    pub fn shrink_to(&mut self, min_capacity: usize) {
        // See `shrink_to_fit` for the rationale behind the sequence.
        let remap = self.items.compact();
        if !remap.is_identity() {
            self.tables.k1_to_item.remap_indexes(&remap);
            self.tables.k2_to_item.remap_indexes(&remap);
            self.tables.k3_to_item.remap_indexes(&remap);
        }
        self.items.shrink_capacity_to(min_capacity);
        self.tables.k1_to_item.shrink_to(min_capacity);
        self.tables.k2_to_item.shrink_to(min_capacity);
        self.tables.k3_to_item.shrink_to(min_capacity);
    }

    /// Iterates over the items in the map.
    ///
    /// Similar to [`HashMap`], the iteration order is arbitrary and not
    /// guaranteed to be stable.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    /// map.insert_unique(Person {
    ///     id: 2,
    ///     email: "bob@example.com".to_string(),
    ///     phone: "555-5678".to_string(),
    ///     name: "Bob".to_string(),
    /// })
    /// .unwrap();
    ///
    /// let mut count = 0;
    /// for person in map.iter() {
    ///     assert!(person.id == 1 || person.id == 2);
    ///     count += 1;
    /// }
    /// assert_eq!(count, 2);
    /// # }
    /// ```
    ///
    /// [`HashMap`]: std::collections::HashMap
    #[inline]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(&self.items)
    }

    /// Iterates over the items in the map, allowing for mutation.
    ///
    /// Similar to [`HashMap`], the iteration order is arbitrary and not
    /// guaranteed to be stable.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// for mut person in map.iter_mut() {
    ///     person.name.push_str(" Updated");
    /// }
    ///
    /// let person = map.get1(&1).unwrap();
    /// assert_eq!(person.name, "Alice Updated");
    /// # }
    /// ```
    ///
    /// [`HashMap`]: std::collections::HashMap
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, T, S, A> {
        IterMut::new(&self.tables, &mut self.items)
    }

    /// Checks general invariants of the map.
    ///
    /// The code below always upholds these invariants, but it's useful to have
    /// an explicit check for tests.
    #[doc(hidden)]
    pub fn validate(
        &self,
        compactness: crate::internal::ValidateCompact,
    ) -> Result<(), ValidationError>
    where
        T: fmt::Debug,
    {
        self.validate_structural(compactness)?;

        // Check that the indexes are all correct.
        //
        // Unlike the structural checks, this re-looks up each key through the
        // user `Hash`, so it only holds when that `Hash` is lawful.
        for (ix, item) in self.items.iter() {
            let key1 = item.key1();
            let key2 = item.key2();
            let key3 = item.key3();

            let Some(ix1) = self.find1_index(&key1) else {
                return Err(ValidationError::general(format!(
                    "item at index {ix} has no key1 index"
                )));
            };
            let Some(ix2) = self.find2_index(&key2) else {
                return Err(ValidationError::general(format!(
                    "item at index {ix} has no key2 index"
                )));
            };
            let Some(ix3) = self.find3_index(&key3) else {
                return Err(ValidationError::general(format!(
                    "item at index {ix} has no key3 index"
                )));
            };

            if ix1 != ix || ix2 != ix || ix3 != ix {
                return Err(ValidationError::general(format!(
                    "item at index {ix} has inconsistent indexes: {ix1}/{ix2}/{ix3}"
                )));
            }
        }

        Ok(())
    }

    /// Checks the structural invariants of the map:
    ///
    /// * The item set is well-formed.
    /// * Each per-key hash table holds exactly one entry per live item, with no
    ///   duplicate `ItemIndex`es.
    ///
    /// Unlike [`validate`](Self::validate), this does not re-look-up keys
    /// through the user `Hash`, so it holds regardless of whether that `Hash`
    /// is lawful. A buggy hasher can desync the logical key→item mapping, but
    /// it must never break these structural invariants! Doing so would be
    /// unsoundness, e.g. duplicate indexes enabling mutable aliasing.
    #[doc(hidden)]
    pub fn validate_structural(
        &self,
        compactness: crate::internal::ValidateCompact,
    ) -> Result<(), ValidationError> {
        self.items.validate(compactness)?;
        self.tables.validate(self.len(), compactness)?;
        Ok(())
    }

    /// Inserts a value into the map, removing any conflicting items and
    /// returning a list of those items.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    ///
    /// // First insertion - no conflicts
    /// let overwritten = map.insert_overwrite(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// });
    /// assert!(overwritten.is_empty());
    ///
    /// // Overwrite with same id - returns the old item
    /// let overwritten = map.insert_overwrite(Person {
    ///     id: 1,
    ///     email: "alice.new@example.com".to_string(),
    ///     phone: "555-9999".to_string(),
    ///     name: "Alice New".to_string(),
    /// });
    /// assert_eq!(overwritten.len(), 1);
    /// assert_eq!(overwritten[0].name, "Alice");
    /// # }
    /// ```
    #[doc(alias = "insert")]
    pub fn insert_overwrite(&mut self, value: T) -> Vec<T> {
        let prepared = self.prepare_insert_overwrite(&value);

        let mut duplicates = Vec::with_capacity(prepared.duplicate_count());

        self.try_reserve_insert_overwrite_commit(
            prepared.needs_new_item_slot(),
        )
        .expect("reserved space successfully");

        self.commit_insert_overwrite(value, prepared, &mut duplicates);

        duplicates
    }

    /// Inserts a value into the set, returning an error if any duplicates were
    /// added.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    ///
    /// // Successful insertion
    /// assert!(
    ///     map.insert_unique(Person {
    ///         id: 1,
    ///         email: "alice@example.com".to_string(),
    ///         phone: "555-1234".to_string(),
    ///         name: "Alice".to_string(),
    ///     })
    ///     .is_ok()
    /// );
    /// assert!(
    ///     map.insert_unique(Person {
    ///         id: 2,
    ///         email: "bob@example.com".to_string(),
    ///         phone: "555-5678".to_string(),
    ///         name: "Bob".to_string(),
    ///     })
    ///     .is_ok()
    /// );
    ///
    /// // Duplicate key1
    /// assert!(
    ///     map.insert_unique(Person {
    ///         id: 1,
    ///         email: "charlie@example.com".to_string(),
    ///         phone: "555-9999".to_string(),
    ///         name: "Charlie".to_string(),
    ///     })
    ///     .is_err()
    /// );
    ///
    /// // Duplicate key2
    /// assert!(
    ///     map.insert_unique(Person {
    ///         id: 3,
    ///         email: "alice@example.com".to_string(),
    ///         phone: "555-7777".to_string(),
    ///         name: "Alice2".to_string(),
    ///     })
    ///     .is_err()
    /// );
    ///
    /// // Duplicate key3
    /// assert!(
    ///     map.insert_unique(Person {
    ///         id: 4,
    ///         email: "dave@example.com".to_string(),
    ///         phone: "555-1234".to_string(),
    ///         name: "Dave".to_string(),
    ///     })
    ///     .is_err()
    /// );
    /// # }
    /// ```
    pub fn insert_unique(
        &mut self,
        value: T,
    ) -> Result<(), DuplicateItem<T, &T>> {
        match self.insert_unique_or_dup_indexes(value) {
            Ok(_) => Ok(()),
            Err((value, duplicates)) => Err(DuplicateItem::__internal_new(
                value,
                duplicates.iter().map(|ix| &self.items[*ix]).collect(),
            )),
        }
    }

    fn insert_unique_or_dup_indexes(
        &mut self,
        value: T,
    ) -> Result<ItemIndex, (T, BTreeSet<ItemIndex>)> {
        let mut duplicates = BTreeSet::new();

        // Check for duplicates *before* inserting the new item, because we
        // don't want to partially insert the new item and then have to roll
        // back.
        let state = &self.tables.state;
        let (e1, e2, e3) = {
            let k1 = value.key1();
            let k2 = value.key2();
            let k3 = value.key3();

            let e1 = detect_dup_or_insert(
                self.tables
                    .k1_to_item
                    .entry(state, k1, |index| self.items[index].key1()),
                &mut duplicates,
            );
            let e2 = detect_dup_or_insert(
                self.tables
                    .k2_to_item
                    .entry(state, k2, |index| self.items[index].key2()),
                &mut duplicates,
            );
            let e3 = detect_dup_or_insert(
                self.tables
                    .k3_to_item
                    .entry(state, k3, |index| self.items[index].key3()),
                &mut duplicates,
            );
            (e1, e2, e3)
        };

        if !duplicates.is_empty() {
            return Err((value, duplicates));
        }

        let next_index = self.items.assert_can_grow().insert(value);
        // e1, e2 and e3 are all Some because if they were None, duplicates
        // would be non-empty, and we'd have bailed out earlier.
        e1.unwrap().insert(next_index);
        e2.unwrap().insert(next_index);
        e3.unwrap().insert(next_index);

        Ok(next_index)
    }

    /// Returns true if the map contains a single item that matches all three
    /// keys.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// }).unwrap();
    /// map.insert_unique(Person {
    ///     id: 2,
    ///     email: "bob@example.com".to_string(),
    ///     phone: "555-5678".to_string(),
    ///     name: "Bob".to_string(),
    /// }).unwrap();
    ///
    /// assert!(map.contains_key_unique(&1, &"alice@example.com", &"555-1234"));
    /// assert!(map.contains_key_unique(&2, &"bob@example.com", &"555-5678"));
    /// assert!(!map.contains_key_unique(&1, &"bob@example.com", &"555-1234")); // key1 exists but key2 doesn't match
    /// assert!(!map.contains_key_unique(&3, &"charlie@example.com", &"555-9999")); // none of the keys exist
    /// # }
    /// ```
    pub fn contains_key_unique<'a, Q1, Q2, Q3>(
        &'a self,
        key1: &Q1,
        key2: &Q2,
        key3: &Q3,
    ) -> bool
    where
        Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
        Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
        Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        self.get_unique(key1, key2, key3).is_some()
    }

    /// Gets a reference to the unique item associated with the given `key1`,
    /// `key2`, and `key3`, if it exists.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// // All three keys must match
    /// assert_eq!(
    ///     map.get_unique(&1, &"alice@example.com", &"555-1234").unwrap().name,
    ///     "Alice"
    /// );
    ///
    /// // If any key doesn't match, returns None
    /// assert!(map.get_unique(&1, &"wrong@example.com", &"555-1234").is_none());
    /// assert!(map.get_unique(&2, &"alice@example.com", &"555-1234").is_none());
    /// # }
    /// ```
    pub fn get_unique<'a, Q1, Q2, Q3>(
        &'a self,
        key1: &Q1,
        key2: &Q2,
        key3: &Q3,
    ) -> Option<&'a T>
    where
        Q1: Hash + Equivalent<T::K1<'a>> + ?Sized,
        Q2: Hash + Equivalent<T::K2<'a>> + ?Sized,
        Q3: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        let index = self.find1_index(key1)?;
        let item = &self.items[index];
        if key2.equivalent(&item.key2()) && key3.equivalent(&item.key3()) {
            Some(item)
        } else {
            None
        }
    }

    /// Gets a mutable reference to the unique item associated with the given
    /// `key1`, `key2`, and `key3`, if it exists.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// // Modify the item through the mutable reference
    /// if let Some(mut person) =
    ///     map.get_mut_unique(1, "alice@example.com", "555-1234")
    /// {
    ///     person.name = "Alice Updated".to_string();
    /// }
    ///
    /// // Verify the change
    /// assert_eq!(map.get1(&1).unwrap().name, "Alice Updated");
    /// # }
    /// ```
    pub fn get_mut_unique(
        &mut self,
        key1: T::K1<'_>,
        key2: T::K2<'_>,
        key3: T::K3<'_>,
    ) -> Option<RefMut<'_, T, S>> {
        let index = self.find_unique_index_by_keys(key1, key2, key3)?;
        self.get_by_index_mut(index)
    }

    /// Removes the item uniquely identified by `key1`, `key2`, and `key3`, if
    /// it exists.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// // Remove the item using all three keys
    /// let removed = map.remove_unique(1, "alice@example.com", "555-1234");
    /// assert!(removed.is_some());
    /// assert_eq!(removed.unwrap().name, "Alice");
    ///
    /// // Map is now empty
    /// assert!(map.is_empty());
    ///
    /// // Trying to remove again returns None
    /// assert!(map.remove_unique(1, "alice@example.com", "555-1234").is_none());
    /// # }
    /// ```
    pub fn remove_unique(
        &mut self,
        key1: T::K1<'_>,
        key2: T::K2<'_>,
        key3: T::K3<'_>,
    ) -> Option<T> {
        let remove_index = self.find_unique_index_by_keys(key1, key2, key3)?;
        self.remove_by_index(remove_index)
    }

    /// Returns true if the map contains the given `key1`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert!(map.contains_key1(&1));
    /// assert!(!map.contains_key1(&2));
    /// # }
    /// ```
    pub fn contains_key1<'a, Q>(&'a self, key1: &Q) -> bool
    where
        Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
    {
        self.find1_index(key1).is_some()
    }

    /// Gets a reference to the value associated with the given `key1`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert_eq!(map.get1(&1).unwrap().name, "Alice");
    /// assert!(map.get1(&2).is_none());
    /// # }
    /// ```
    pub fn get1<'a, Q>(&'a self, key1: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
    {
        self.find1(key1)
    }

    /// Gets a mutable reference to the value associated with the given `key1`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// if let Some(mut person) = map.get1_mut(1) {
    ///     person.name = "Alice Updated".to_string();
    /// }
    ///
    /// assert_eq!(map.get1(&1).unwrap().name, "Alice Updated");
    /// # }
    /// ```
    pub fn get1_mut(&mut self, key1: T::K1<'_>) -> Option<RefMut<'_, T, S>> {
        let index = self.find1_index_by_key(key1)?;
        self.get_by_index_mut(index)
    }

    /// Removes an item from the map by its `key1`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// let removed = map.remove1(1);
    /// assert!(removed.is_some());
    /// assert_eq!(removed.unwrap().name, "Alice");
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn remove1(&mut self, key1: T::K1<'_>) -> Option<T> {
        let remove_index = self.find1_index_by_key(key1)?;
        self.remove_by_index(remove_index)
    }

    /// Returns true if the map contains the given `key2`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert!(map.contains_key2("alice@example.com"));
    /// assert!(!map.contains_key2("bob@example.com"));
    /// # }
    /// ```
    pub fn contains_key2<'a, Q>(&'a self, key2: &Q) -> bool
    where
        Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
    {
        self.find2_index(key2).is_some()
    }

    /// Gets a reference to the value associated with the given `key2`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert_eq!(map.get2("alice@example.com").unwrap().name, "Alice");
    /// assert!(map.get2("bob@example.com").is_none());
    /// # }
    /// ```
    pub fn get2<'a, Q>(&'a self, key2: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
    {
        self.find2(key2)
    }

    /// Gets a mutable reference to the value associated with the given `key2`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// if let Some(mut person) = map.get2_mut("alice@example.com") {
    ///     person.name = "Alice Updated".to_string();
    /// }
    ///
    /// assert_eq!(map.get2("alice@example.com").unwrap().name, "Alice Updated");
    /// # }
    /// ```
    pub fn get2_mut(&mut self, key2: T::K2<'_>) -> Option<RefMut<'_, T, S>> {
        let index = self.find2_index_by_key(key2)?;
        self.get_by_index_mut(index)
    }

    /// Removes an item from the map by its `key2`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// let removed = map.remove2("alice@example.com");
    /// assert!(removed.is_some());
    /// assert_eq!(removed.unwrap().name, "Alice");
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn remove2(&mut self, key2: T::K2<'_>) -> Option<T> {
        let remove_index = self.find2_index_by_key(key2)?;
        self.remove_by_index(remove_index)
    }

    /// Returns true if the map contains the given `key3`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert!(map.contains_key3("555-1234"));
    /// assert!(!map.contains_key3("555-5678"));
    /// # }
    /// ```
    pub fn contains_key3<'a, Q>(&'a self, key3: &Q) -> bool
    where
        Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        self.find3_index(key3).is_some()
    }

    /// Gets a reference to the value associated with the given `key3`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert_eq!(map.get3("555-1234").unwrap().name, "Alice");
    /// assert!(map.get3("555-5678").is_none());
    /// # }
    /// ```
    pub fn get3<'a, Q>(&'a self, key3: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        self.find3(key3)
    }

    /// Gets a mutable reference to the value associated with the given `key3`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// if let Some(mut person) = map.get3_mut("555-1234") {
    ///     person.name = "Alice Updated".to_string();
    /// }
    ///
    /// assert_eq!(map.get3("555-1234").unwrap().name, "Alice Updated");
    /// # }
    /// ```
    pub fn get3_mut(&mut self, key3: T::K3<'_>) -> Option<RefMut<'_, T, S>> {
        let index = self.find3_index_by_key(key3)?;
        self.get_by_index_mut(index)
    }

    /// Removes an item from the map by its `key3`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq)]
    /// struct Person {
    ///     id: u32,
    ///     email: String,
    ///     phone: String,
    ///     name: String,
    /// }
    ///
    /// impl TriHashItem for Person {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.email
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.phone
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Person {
    ///     id: 1,
    ///     email: "alice@example.com".to_string(),
    ///     phone: "555-1234".to_string(),
    ///     name: "Alice".to_string(),
    /// })
    /// .unwrap();
    ///
    /// let removed = map.remove3("555-1234");
    /// assert!(removed.is_some());
    /// assert_eq!(removed.unwrap().name, "Alice");
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn remove3(&mut self, key3: T::K3<'_>) -> Option<T> {
        let remove_index = self.find3_index_by_key(key3)?;
        self.remove_by_index(remove_index)
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all items `T` for which `f(RefMut<T>)` returns
    /// false. The elements are visited in an arbitrary order.
    ///
    /// The `RefMut<T, S>` wrapper allows mutable access to the item while
    /// enforcing that the three keys (`K1`, `K2`, `K3`) remain unchanged. If
    /// a key is modified during iteration, the method will panic.
    ///
    /// # Performance considerations
    ///
    /// This method may leave the internal storage fragmented. If you need
    /// compact storage afterward, call `make_compact()`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     code: String,
    ///     value: u32,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.code
    ///     }
    ///
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Item {
    ///     id: 1,
    ///     name: "foo".to_string(),
    ///     code: "x".to_string(),
    ///     value: 42,
    /// })
    /// .unwrap();
    /// map.insert_unique(Item {
    ///     id: 2,
    ///     name: "bar".to_string(),
    ///     code: "y".to_string(),
    ///     value: 20,
    /// })
    /// .unwrap();
    /// map.insert_unique(Item {
    ///     id: 3,
    ///     name: "baz".to_string(),
    ///     code: "z".to_string(),
    ///     value: 99,
    /// })
    /// .unwrap();
    ///
    /// // Retain only items where value is greater than 30
    /// map.retain(|item| item.value > 30);
    ///
    /// assert_eq!(map.len(), 2);
    /// assert_eq!(map.get1(&1).unwrap().value, 42);
    /// assert_eq!(map.get1(&3).unwrap().value, 99);
    /// assert!(map.get1(&2).is_none());
    /// # }
    /// ```
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: for<'b> FnMut(RefMut<'b, T, S>) -> bool,
    {
        let hash_state = self.tables.state.clone();
        let items = &mut self.items;
        let k2_to_item = &mut self.tables.k2_to_item;
        let k3_to_item = &mut self.tables.k3_to_item;
        // This variable is:
        //
        // * None, if the last time `f` was called, it returned true.
        // * Some with the previous index, if the last time `f` was called,
        //   it returned false.
        let mut pending_remove: Option<ItemIndex> = None;

        self.tables.k1_to_item.retain(|index| {
            // If `f` returned false last time, remove that item from `items`
            // now, one call later. We do this because of how
            // `HashTable::retain` sequences its work:
            //
            // 1. It calls this closure.
            // 2. If the closure returns false, it erases the entry.
            // 3. It calls this closure again for the next entry.
            //
            // If we removed the item from `items` during step 1, then between
            // steps 1 and 2 `k1_to_item` would hold an index whose slot is
            // vacant. Only hashbrown code runs in that gap today, so nothing
            // can panic there. But if something ever did, the map would be
            // left with a stale index in the table. A later insert could then
            // reuse the vacant slot, and the table would hold the same index
            // twice.
            //
            // Unlike `IdOrdMap`, the hash maps re-check every index they turn
            // into a `&mut T`, so a duplicate would panic rather than alias.
            // We defer the removal anyway so all four `retain` methods work
            // the same way.
            //
            // Removing the item here, during step 3, closes the gap. The
            // table entry is already gone, so if `items.remove` or the user
            // `Drop` below panics, the tables and `items` are still in sync.
            if let Some(prev) = pending_remove.take() {
                drop(
                    items
                        .remove(prev)
                        .expect("all indexes are present in self.items"),
                );
            }

            let (hash2, hash3, retain) = {
                let item = items
                    .get_mut(index)
                    .expect("all indexes are present in self.items");
                // Use T::key1(item) rather than item.key1() to force the key
                // trait function to be called for T rather than &mut T.
                let hash1 = hash_state.hash_one(T::key1(item));
                let hash2 = hash_state.hash_one(T::key2(item));
                let hash3 = hash_state.hash_one(T::key3(item));
                let hashes = [
                    MapHash::new(hash1),
                    MapHash::new(hash2),
                    MapHash::new(hash3),
                ];
                (hash2, hash3, f(RefMut::new(hash_state.clone(), hashes, item)))
            };

            if retain {
                true
            } else {
                let k2_entry = k2_to_item
                    .find_entry_by_hash(hash2, |map2_index| {
                        map2_index == index
                    });
                let k3_entry = k3_to_item
                    .find_entry_by_hash(hash3, |map3_index| {
                        map3_index == index
                    });

                if let Ok(k2_entry) = k2_entry {
                    k2_entry.remove();
                } else {
                    k2_to_item.remove_by_index(index);
                }
                if let Ok(k3_entry) = k3_entry {
                    k3_entry.remove();
                } else {
                    k3_to_item.remove_by_index(index);
                }

                pending_remove = Some(index);

                false
            }
        });

        // The last rejected item, if any, is freed and dropped now that its
        // table entry is gone.
        if let Some(prev) = pending_remove {
            drop(
                items
                    .remove(prev)
                    .expect("all indexes are present in self.items"),
            );
        }
    }

    fn find1<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
    {
        self.find1_index(k).map(|ix| &self.items[ix])
    }

    fn find1_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
    where
        Q: Hash + Equivalent<T::K1<'a>> + ?Sized,
    {
        self.tables
            .k1_to_item
            .find_index(&self.tables.state, k, |index| self.items[index].key1())
    }

    fn find2<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
    {
        self.find2_index(k).map(|ix| &self.items[ix])
    }

    fn find2_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
    where
        Q: Hash + Equivalent<T::K2<'a>> + ?Sized,
    {
        self.tables
            .k2_to_item
            .find_index(&self.tables.state, k, |index| self.items[index].key2())
    }

    fn find3<'a, Q>(&'a self, k: &Q) -> Option<&'a T>
    where
        Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        self.find3_index(k).map(|ix| &self.items[ix])
    }

    fn find3_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
    where
        Q: Hash + Equivalent<T::K3<'a>> + ?Sized,
    {
        self.tables
            .k3_to_item
            .find_index(&self.tables.state, k, |index| self.items[index].key3())
    }

    /// Looks up an owned `key1`, borrowing `self` only for as long as the
    /// upcast key lives.
    ///
    /// The `&mut self` methods use this rather than `find1_index` so that the
    /// caller's key never observes a borrow at the mutable lifetime. See the
    /// "Mutable lookups take owned keys" section in the crate docs.
    fn find1_index_by_key(&self, key1: T::K1<'_>) -> Option<ItemIndex> {
        let key1 = T::upcast_key1(key1);
        self.find1_index(&key1)
    }

    /// The `key2` analog of `find1_index_by_key`.
    fn find2_index_by_key(&self, key2: T::K2<'_>) -> Option<ItemIndex> {
        let key2 = T::upcast_key2(key2);
        self.find2_index(&key2)
    }

    /// The `key3` analog of `find1_index_by_key`.
    fn find3_index_by_key(&self, key3: T::K3<'_>) -> Option<ItemIndex> {
        let key3 = T::upcast_key3(key3);
        self.find3_index(&key3)
    }

    /// Looks up the item that has all three keys, with the same borrow
    /// discipline as `find1_index_by_key`.
    fn find_unique_index_by_keys(
        &self,
        key1: T::K1<'_>,
        key2: T::K2<'_>,
        key3: T::K3<'_>,
    ) -> Option<ItemIndex> {
        let key1 = T::upcast_key1(key1);
        let key2 = T::upcast_key2(key2);
        let key3 = T::upcast_key3(key3);
        let index = self.find1_index(&key1)?;
        let item = &self.items[index];
        if key2.equivalent(&item.key2()) && key3.equivalent(&item.key3()) {
            Some(index)
        } else {
            None
        }
    }

    fn get_by_index_mut(
        &mut self,
        index: ItemIndex,
    ) -> Option<RefMut<'_, T, S>> {
        let borrowed = self.items.get(index)?;
        let state = self.tables.state.clone();
        let hashes = self.tables.make_hashes(borrowed);
        let item = &mut self.items[index];
        Some(RefMut::new(state, hashes, item))
    }

    fn prepare_insert_overwrite(&self, value: &T) -> PreparedInsertOverwrite {
        let key1 = value.key1();
        let key2 = value.key2();
        let key3 = value.key3();

        let index1 = self.find1_index(&key1);
        let index2 = self.find2_index(&key2);
        let index3 = self.find3_index(&key3);
        let hashes = self.tables.make_hashes_for_keys::<T>(&key1, &key2, &key3);

        let duplicates = PreparedDuplicate::from_indexes(
            [index1, index2, index3],
            |index| self.prepare_duplicate(index),
        );

        PreparedInsertOverwrite { duplicates, hashes }
    }

    fn prepare_duplicate(&self, index: ItemIndex) -> PreparedDuplicate {
        let item = &self.items[index];
        let hashes = self.tables.make_hashes::<T>(item);

        PreparedDuplicate { index, hashes }
    }

    fn try_reserve_insert_overwrite_commit(
        &mut self,
        needs_new_item_slot: bool,
    ) -> Result<(), TryReserveError> {
        if needs_new_item_slot {
            self.items.try_reserve(1)?;
        }

        self.tables
            .k1_to_item
            .try_reserve(1)
            .map_err(TryReserveError::from_hashbrown)?;

        self.tables
            .k2_to_item
            .try_reserve(1)
            .map_err(TryReserveError::from_hashbrown)?;

        self.tables
            .k3_to_item
            .try_reserve(1)
            .map_err(TryReserveError::from_hashbrown)?;

        Ok(())
    }

    fn commit_insert_overwrite(
        &mut self,
        value: T,
        prepared: PreparedInsertOverwrite,
        duplicates: &mut Vec<T>,
    ) -> ItemIndex {
        // From here until insertion completes, do not call user code or
        // allocate. The caller prepared hashes/indexes and reserved capacity.
        for duplicate in prepared.duplicates {
            duplicates.push(
                self.remove_duplicate(duplicate)
                    .expect("duplicate index was prepared"),
            );
        }

        self.insert_unique_with_prepared_hashes(value, prepared.hashes)
    }

    fn insert_unique_with_prepared_hashes(
        &mut self,
        value: T,
        hashes: [MapHash; 3],
    ) -> ItemIndex {
        let [hash1, hash2, hash3] = hashes;
        let next_index = self.items.assert_can_grow().insert(value);

        self.tables.k1_to_item.insert_prehashed_unchecked(hash1, next_index);
        self.tables.k2_to_item.insert_prehashed_unchecked(hash2, next_index);
        self.tables.k3_to_item.insert_prehashed_unchecked(hash3, next_index);

        next_index
    }

    pub(super) fn remove_by_index(
        &mut self,
        remove_index: ItemIndex,
    ) -> Option<T> {
        // For panic safety, compute all three key hashes and look up all three
        // table entries while `self.items` still holds the value, then remove
        // from all three tables and items in sequence. These lookups
        // deliberately match by `ItemIndex` rather than by user `Eq`: at this
        // point we already know which item is being removed, and user `Eq`
        // might be pathological. hashbrown's `find_entry_by_hash` is
        // panic-safe because the table is not mutated until
        // `OccupiedEntry::remove` is called, so a panic while hashing leaves
        // items and all three tables unmodified. (Unlike the IdOrdMap path,
        // no separate two-phase commit is needed: the BTreeMap analog has to
        // guard against a user-`Ord` panic during the tree walk, but the
        // hash walk here never invokes user code.)
        //
        // If any hash lookup misses — which happens when a `mem::forget` on
        // a `RefMut` bypassed the drop-time hash check and one of the item's
        // keys now hashes to a different bucket than its entry sits in —
        // fall back to a linear scan by `ItemIndex` for that table. The
        // fallback never invokes user `Hash`, so cleanup remains panic-safe.
        let item = self.items.get(remove_index)?;
        let state = &self.tables.state;
        let hash1 = state.hash_one(item.key1());
        let hash2 = state.hash_one(item.key2());
        let hash3 = state.hash_one(item.key3());
        match self
            .tables
            .k1_to_item
            .find_entry_by_hash(hash1, |index| index == remove_index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k1_to_item.remove_by_index(remove_index),
        }
        match self
            .tables
            .k2_to_item
            .find_entry_by_hash(hash2, |index| index == remove_index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k2_to_item.remove_by_index(remove_index),
        }
        match self
            .tables
            .k3_to_item
            .find_entry_by_hash(hash3, |index| index == remove_index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k3_to_item.remove_by_index(remove_index),
        }
        Some(
            self.items
                .remove(remove_index)
                .expect("items[remove_index] was Occupied above"),
        )
    }

    /// Removes the item at `duplicate`, using already-computed key hashes when
    /// possible.
    ///
    /// The caller must ensure:
    ///
    /// * all user-controlled key extraction and hashing for the item at
    ///   `duplicate.index` has already completed;
    /// * the item at `duplicate.index` has not changed since those hashes were
    ///   computed;
    /// * removing this index from the item store and key tables preserves the
    ///   map/table invariants.
    ///
    /// The provided `duplicate.hashes` allow the normal commit path to remove
    /// key-table entries without recomputing user-controlled hashes. If a
    /// prehashed lookup misses, this falls back to removing by `ItemIndex`,
    /// which performs a linear scan over cached indexes and does not re-enter
    /// user code.
    fn remove_duplicate(&mut self, duplicate: PreparedDuplicate) -> Option<T> {
        let _ = self.items.get(duplicate.index)?;

        let [hash1, hash2, hash3] = duplicate.hashes;

        match self
            .tables
            .k1_to_item
            .find_entry_by_hash(hash1.hash(), |index| index == duplicate.index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k1_to_item.remove_by_index(duplicate.index),
        }

        match self
            .tables
            .k2_to_item
            .find_entry_by_hash(hash2.hash(), |index| index == duplicate.index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k2_to_item.remove_by_index(duplicate.index),
        }

        match self
            .tables
            .k3_to_item
            .find_entry_by_hash(hash3.hash(), |index| index == duplicate.index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.k3_to_item.remove_by_index(duplicate.index),
        }

        Some(
            self.items
                .remove(duplicate.index)
                .expect("items[duplicate.index] was Occupied above"),
        )
    }
}

impl<T: TriHashItem + fmt::Debug, S, A: Allocator> TriHashMap<T, S, A> {
    /// Returns a value that formats the map as `{{k1: key1, k2: key2, k3:
    /// key3}: item, ...}`, in arbitrary order.
    ///
    /// The [`Debug`](fmt::Debug) impl for `TriHashMap` formats items only, as
    /// a set, and requires just `T: Debug`. This method also requires the key
    /// types to be `Debug` for the lifetime of the borrow.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: u32,
    ///     name: String,
    ///     email: String,
    /// }
    ///
    /// impl TriHashItem for Item {
    ///     type K1<'a> = u32;
    ///     type K2<'a> = &'a str;
    ///     type K3<'a> = &'a str;
    ///     fn key1(&self) -> Self::K1<'_> {
    ///         self.id
    ///     }
    ///     fn key2(&self) -> Self::K2<'_> {
    ///         &self.name
    ///     }
    ///     fn key3(&self) -> Self::K3<'_> {
    ///         &self.email
    ///     }
    ///     tri_upcast!();
    /// }
    ///
    /// let mut map = TriHashMap::new();
    /// map.insert_unique(Item {
    ///     id: 1,
    ///     name: "foo".to_string(),
    ///     email: "foo@example.com".to_string(),
    /// })
    /// .unwrap();
    ///
    /// assert_eq!(
    ///     format!("{:?}", map.debug_with_keys()),
    ///     "{{k1: 1, k2: \"foo\", k3: \"foo@example.com\"}: \
    ///      Item { id: 1, name: \"foo\", email: \"foo@example.com\" }}",
    /// );
    /// # }
    /// ```
    pub fn debug_with_keys<'a>(&'a self) -> impl fmt::Debug + 'a
    where
        T::K1<'a>: fmt::Debug,
        T::K2<'a>: fmt::Debug,
        T::K3<'a>: fmt::Debug,
    {
        struct DebugWithKeys<'a, T: TriHashItem, S, A: Allocator>(
            &'a TriHashMap<T, S, A>,
        );

        impl<'a, T, S, A> fmt::Debug for DebugWithKeys<'a, T, S, A>
        where
            T: TriHashItem + fmt::Debug,
            T::K1<'a>: fmt::Debug,
            T::K2<'a>: fmt::Debug,
            T::K3<'a>: fmt::Debug,
            A: Allocator,
        {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                let mut map = f.debug_map();
                for item in self.0.items.values() {
                    // `self.0` is borrowed for 'a, so `item: &'a T` and the
                    // keys are `T::K1<'a>`, `T::K2<'a>`, and `T::K3<'a>`
                    // without any lifetime extension.
                    let key: KeyMap<'a, T> = KeyMap {
                        key1: item.key1(),
                        key2: item.key2(),
                        key3: item.key3(),
                    };
                    map.entry(&key, item);
                }
                map.finish()
            }
        }

        DebugWithKeys(self)
    }
}

impl<T: TriHashItem + fmt::Debug, S, A: Allocator> fmt::Debug
    for TriHashMap<T, S, A>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.items.values()).finish()
    }
}

struct KeyMap<'a, T: TriHashItem + 'a> {
    key1: T::K1<'a>,
    key2: T::K2<'a>,
    key3: T::K3<'a>,
}

impl<'a, T: TriHashItem> fmt::Debug for KeyMap<'a, T>
where
    T::K1<'a>: fmt::Debug,
    T::K2<'a>: fmt::Debug,
    T::K3<'a>: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // We don't want to show key1 and key2 as a tuple since it's
        // misleading (suggests maps of tuples). The best we can do
        // instead is to show "{k1: abc, k2: xyz, k3: def}"
        f.debug_map()
            .entry(&StrDisplayAsDebug("k1"), &self.key1)
            .entry(&StrDisplayAsDebug("k2"), &self.key2)
            .entry(&StrDisplayAsDebug("k3"), &self.key3)
            .finish()
    }
}

impl<T: TriHashItem + PartialEq, S: Clone + BuildHasher, A: Allocator> PartialEq
    for TriHashMap<T, S, A>
{
    fn eq(&self, other: &Self) -> bool {
        // Implementing PartialEq for TriHashMap is tricky because TriHashMap is
        // not semantically like an IndexMap: two maps are equivalent even if
        // their items are in a different order. In other words, any permutation
        // of items is equivalent.
        //
        // We also can't sort the items because they're not necessarily Ord.
        //
        // So we write a custom equality check that checks that each key in one
        // map points to the same item as in the other map.

        if self.items.len() != other.items.len() {
            return false;
        }

        // Walk over all the items in the first map and check that they point to
        // the same item in the second map.
        for item in self.items.values() {
            let k1 = item.key1();
            let k2 = item.key2();
            let k3 = item.key3();

            // Check that the indexes are the same in the other map.
            let Some(other_ix1) = other.find1_index(&k1) else {
                return false;
            };
            let Some(other_ix2) = other.find2_index(&k2) else {
                return false;
            };
            let Some(other_ix3) = other.find3_index(&k3) else {
                return false;
            };

            if other_ix1 != other_ix2 || other_ix1 != other_ix3 {
                // All the keys were present but they didn't point to the same
                // item.
                return false;
            }

            // Check that the other map's item is the same as this map's
            // item. (This is what we use the `PartialEq` bound on T for.)
            //
            // Because we've checked that other_ix1, other_ix2 and other_ix3 are
            // Some, we know that it is valid and points to the expected item.
            let other_item = &other.items[other_ix1];
            if item != other_item {
                return false;
            }
        }

        true
    }
}

// The Eq bound on T ensures that the TriHashMap forms an equivalence class.
impl<T: TriHashItem + Eq, S: Clone + BuildHasher, A: Allocator> Eq
    for TriHashMap<T, S, A>
{
}

/// The `Extend` implementation overwrites duplicates. In the future, there will
/// also be an `extend_unique` method that will return an error.
impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> Extend<T>
    for TriHashMap<T, S, A>
{
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        // Keys may already be present in the map, or multiple times in the
        // iterator. Reserve the entire hint lower bound if the map is empty.
        // Otherwise reserve half the hint (rounded up), so the map will only
        // resize twice in the worst case.
        let iter = iter.into_iter();
        let reserve = if self.is_empty() {
            iter.size_hint().0
        } else {
            iter.size_hint().0.div_ceil(2)
        };
        self.reserve(reserve);
        for item in iter {
            self.insert_overwrite(item);
        }
    }
}

fn detect_dup_or_insert<'a, A: Allocator>(
    item: hash_table::Entry<'a, A>,
    duplicates: &mut BTreeSet<ItemIndex>,
) -> Option<hash_table::VacantEntry<'a, A>> {
    match item {
        hash_table::Entry::Vacant(slot) => Some(slot),
        hash_table::Entry::Occupied(slot) => {
            duplicates.insert(slot.get());
            None
        }
    }
}

impl<'a, T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for &'a TriHashMap<T, S, A>
{
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for &'a mut TriHashMap<T, S, A>
{
    type Item = RefMut<'a, T, S>;
    type IntoIter = IterMut<'a, T, S, A>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T: TriHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for TriHashMap<T, S, A>
{
    type Item = T;
    type IntoIter = IntoIter<T, A>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self.items)
    }
}

/// The `FromIterator` implementation for `TriHashMap` overwrites duplicate
/// items.
///
/// To reject duplicates, use [`TriHashMap::from_iter_unique`].
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use iddqd::{TriHashItem, TriHashMap, tri_upcast};
///
/// #[derive(Debug, PartialEq, Eq)]
/// struct Item {
///     id: u32,
///     name: String,
///     email: String,
/// }
///
/// impl TriHashItem for Item {
///     type K1<'a> = u32;
///     type K2<'a> = &'a str;
///     type K3<'a> = &'a str;
///     fn key1(&self) -> Self::K1<'_> {
///         self.id
///     }
///     fn key2(&self) -> Self::K2<'_> {
///         &self.name
///     }
///     fn key3(&self) -> Self::K3<'_> {
///         &self.email
///     }
///     tri_upcast!();
/// }
///
/// let items = vec![
///     Item {
///         id: 1,
///         name: "foo".to_string(),
///         email: "foo@example.com".to_string(),
///     },
///     Item {
///         id: 2,
///         name: "bar".to_string(),
///         email: "bar@example.com".to_string(),
///     },
///     Item {
///         id: 1,
///         name: "baz".to_string(),
///         email: "baz@example.com".to_string(),
///     }, // overwrites first item
/// ];
///
/// let map: TriHashMap<Item> = items.into_iter().collect();
/// assert_eq!(map.len(), 2);
/// assert_eq!(map.get1(&1).unwrap().name, "baz"); // overwritten
/// assert_eq!(map.get1(&1).unwrap().email, "baz@example.com");
/// assert_eq!(map.get1(&2).unwrap().name, "bar");
/// # }
/// ```
impl<T: TriHashItem, S: Default + Clone + BuildHasher, A: Default + Allocator>
    FromIterator<T> for TriHashMap<T, S, A>
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut map = TriHashMap::default();
        map.extend(iter);
        map
    }
}