btree_indexmap/

multi_map.rs

use core::fmt;
use equivalent::Comparable;
use raw_btree::RawBTree;
use std::{
	cmp::Ordering,
	hash::{Hash, Hasher},
	iter::FusedIterator,
	mem::MaybeUninit,
	ops::Index,
};

#[derive(Clone)]
struct Indexes {
	first: usize,
	rest: Vec<usize>,
}

impl Indexes {
	fn new(i: usize) -> Self {
		Self {
			first: i,
			rest: Vec::new(),
		}
	}

	fn insert(&mut self, mut i: usize) {
		match i.cmp(&self.first) {
			Ordering::Equal => return,
			Ordering::Less => {
				std::mem::swap(&mut self.first, &mut i);
			}
			_ => (),
		}

		if let Err(offset) = self.rest.binary_search(&i) {
			self.rest.insert(offset, i);
		}
	}

	fn remove(&mut self, i: usize) -> Result<bool, ()> {
		if self.first == i {
			if self.rest.is_empty() {
				Err(())
			} else {
				self.first = self.rest.remove(0);
				Ok(true)
			}
		} else {
			match self.rest.binary_search(&i) {
				Ok(offset) => {
					self.rest.remove(offset);
					Ok(true)
				}
				Err(_) => Ok(false),
			}
		}
	}

	fn swap_last(&mut self, j: usize) {
		match self.rest.pop() {
			Some(i) => {
				self.insert(i);
			}
			None => self.first = j,
		}
	}

	fn len(&self) -> usize {
		1 + self.rest.len()
	}

	fn iter(&self) -> IndexesIter<'_> {
		IndexesIter {
			first: Some(self.first),
			rest: self.rest.iter(),
		}
	}

	fn iter_mut(&mut self) -> IndexesIterMut<'_> {
		IndexesIterMut {
			first: Some(&mut self.first),
			rest: self.rest.iter_mut(),
		}
	}
}

impl IntoIterator for Indexes {
	type Item = usize;
	type IntoIter = IndexesIntoIter;

	fn into_iter(self) -> Self::IntoIter {
		IndexesIntoIter {
			first: Some(self.first),
			rest: self.rest.into_iter(),
		}
	}
}

/// An iterator over the indexes of every entry associated with a key in a
/// [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::indexes_of`].
#[derive(Default, Clone)]
pub struct IndexesIter<'a> {
	first: Option<usize>,
	rest: std::slice::Iter<'a, usize>,
}

impl<'a> Iterator for IndexesIter<'a> {
	type Item = usize;

	fn size_hint(&self) -> (usize, Option<usize>) {
		let len = self.rest.len() + if self.first.is_some() { 1 } else { 0 };
		(len, Some(len))
	}

	fn next(&mut self) -> Option<Self::Item> {
		self.first.take().or_else(|| self.rest.next().copied())
	}
}

impl<'a> ExactSizeIterator for IndexesIter<'a> {}

#[derive(Default)]
struct IndexesIterMut<'a> {
	first: Option<&'a mut usize>,
	rest: std::slice::IterMut<'a, usize>,
}

impl<'a> Iterator for IndexesIterMut<'a> {
	type Item = &'a mut usize;

	fn size_hint(&self) -> (usize, Option<usize>) {
		let len = self.rest.len() + if self.first.is_some() { 1 } else { 0 };
		(len, Some(len))
	}

	fn next(&mut self) -> Option<Self::Item> {
		self.first.take().or_else(|| self.rest.next())
	}
}

impl<'a> ExactSizeIterator for IndexesIterMut<'a> {}

#[derive(Default)]
struct IndexesIntoIter {
	first: Option<usize>,
	rest: std::vec::IntoIter<usize>,
}

impl Iterator for IndexesIntoIter {
	type Item = usize;

	fn size_hint(&self) -> (usize, Option<usize>) {
		let len = self.rest.len() + if self.first.is_some() { 1 } else { 0 };
		(len, Some(len))
	}

	fn next(&mut self) -> Option<Self::Item> {
		self.first.take().or_else(|| self.rest.next())
	}
}

impl DoubleEndedIterator for IndexesIntoIter {
	fn next_back(&mut self) -> Option<Self::Item> {
		self.rest.next_back().or_else(|| self.first.take())
	}
}

impl ExactSizeIterator for IndexesIntoIter {}

/// An iterator over `(index, &key, &value)` for every entry associated
/// with a key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_indexed_entries`].
pub struct GetIndexedEntries<'a, K, V> {
	indexes: IndexesIter<'a>,
	entries: &'a [(K, V)],
}

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

	fn next(&mut self) -> Option<Self::Item> {
		self.indexes.next().map(|i| {
			let (k, v) = &self.entries[i];
			(i, k, v)
		})
	}
}

/// An iterator over `(&key, &value)` for every entry associated with a
/// key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_entries`].
pub struct GetEntries<'a, K, V>(GetIndexedEntries<'a, K, V>);

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(_, k, v)| (k, v))
	}
}

/// An iterator over a reference to the value of every entry associated
/// with a key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get`].
pub struct Get<'a, K, V>(GetIndexedEntries<'a, K, V>);

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

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

/// An iterator over `(index, &value)` for every entry associated with a
/// key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_indexed`].
pub struct GetIndexed<'a, K, V>(GetIndexedEntries<'a, K, V>);

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(i, _, v)| (i, v))
	}
}

/// An iterator over `(index, &key, &mut value)` for every entry
/// associated with a key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_indexed_entries_mut`].
pub struct GetIndexedEntriesMut<'a, K, V> {
	indexes: IndexesIter<'a>,
	entries: &'a mut [(K, V)],
}

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

	fn next(&mut self) -> Option<Self::Item> {
		self.indexes.next().map(|i| {
			let (k, v) = &mut self.entries[i];
			let (k, v) = unsafe {
				// SAFEY: values are not aliased, and cannot be borrowed more
				//        than once.
				std::mem::transmute::<(&mut K, &mut V), (&'a K, &'a mut V)>((k, v))
			};

			(i, k, v)
		})
	}
}

/// An iterator over `(&key, &mut value)` for every entry associated with
/// a key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_entries_mut`].
pub struct GetEntriesMut<'a, K, V>(GetIndexedEntriesMut<'a, K, V>);

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(_, k, v)| (k, v))
	}
}

/// An iterator over a mutable reference to the value of every entry
/// associated with a key in a [`BTreeIndexMultiMap`].
///
/// See [`BTreeIndexMultiMap::get_mut`].
pub struct GetMut<'a, K, V>(GetIndexedEntriesMut<'a, K, V>);

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

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

/// BTree-based multi-map with stable entry indices.
///
/// Each key may map to any number of values. Entries are stored in a
/// [`Vec`] and assigned a *stable index* equal to their position in that
/// `Vec`. The index of an entry does not change as long as no entry is
/// removed. A B-tree over the keys provides O(log n) lookup, insertion,
/// and removal, while the `Vec` backing allows O(1) random access by
/// index.
///
/// # Example
///
/// ```
/// use btree_indexmap::BTreeIndexMultiMap;
///
/// let mut map = BTreeIndexMultiMap::new();
///
/// // Multiple values per key, each with its own stable index.
/// map.push_back("fruit", "apple");
/// map.push_back("veggie", "carrot");
/// map.push_back("fruit", "banana");
///
/// assert_eq!(map.key_occurences("fruit"), 2);
///
/// let fruits: Vec<_> = map.get("fruit").copied().collect();
/// assert_eq!(fruits, ["apple", "banana"]);
/// ```
#[derive(Clone)]
pub struct BTreeIndexMultiMap<K, V> {
	entries: Vec<(K, V)>,
	map: RawBTree<Indexes>,
}

impl<K, V> Default for BTreeIndexMultiMap<K, V> {
	fn default() -> Self {
		Self::new()
	}
}

impl<K, V> BTreeIndexMultiMap<K, V> {
	/// Creates a new, empty multi-map.
	pub fn new() -> Self {
		Self {
			entries: Vec::new(),
			map: RawBTree::new(),
		}
	}

	/// Creates a new, empty multi-map with space reserved for at least
	/// `cap` entries.
	pub fn with_capacity(cap: usize) -> Self {
		Self {
			entries: Vec::with_capacity(cap),
			map: RawBTree::new(),
		}
	}

	/// Creates a new multi-map containing the single `(key, value)` entry.
	pub fn singleton(key: K, value: V) -> Self
	where
		K: Ord,
	{
		let mut result = Self::new();
		result.push_back(key, value);
		result
	}

	/// Removes all entries from the map.
	///
	/// This keeps the capacity allocated for the entries.
	pub fn clear(&mut self) {
		self.entries.clear();
		self.map.clear();
	}

	/// Returns the number of entries the map can hold without
	/// reallocating.
	pub fn capacity(&self) -> usize {
		self.entries.capacity()
	}

	/// Returns the entries of the map as a slice, in insertion (index)
	/// order.
	pub fn as_entries(&self) -> &[(K, V)] {
		&self.entries
	}

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

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

	/// Returns the key and value of the first entry in the map (in
	/// insertion order), if any.
	pub fn first(&self) -> Option<(&K, &V)> {
		self.entries.first().map(|(k, v)| (k, v))
	}

	/// Returns the key and value of the last entry in the map (in
	/// insertion order), if any.
	pub fn last(&self) -> Option<(&K, &V)> {
		self.entries.last().map(|(k, v)| (k, v))
	}

	/// Returns `true` if the map contains at least one entry for `key`.
	pub fn contains_key<Q>(&self, key: &Q) -> bool
	where
		Q: ?Sized + Comparable<K>,
	{
		self.map.get(outer_cmp(&self.entries), key).is_some()
	}

	/// Returns the number of entries associated with `key`.
	pub fn key_occurences<Q>(&self, key: &Q) -> usize
	where
		Q: ?Sized + Comparable<K>,
	{
		self.map
			.get(outer_cmp(&self.entries), key)
			.map(|i| i.len())
			.unwrap_or_default()
	}

	/// Returns an iterator over the indexes of every entry associated with
	/// `key`.
	pub fn indexes_of<Q>(&self, key: &Q) -> IndexesIter<'_>
	where
		Q: ?Sized + Comparable<K>,
	{
		self.map
			.get(outer_cmp(&self.entries), key)
			.map(Indexes::iter)
			.unwrap_or_default()
	}

	/// Returns the index of the first entry associated with `key`.
	pub fn index_of<Q>(&self, key: &Q) -> Option<usize>
	where
		Q: ?Sized + Comparable<K>,
	{
		self.indexes_of(key).next()
	}

	/// Returns an iterator over `(index, &key, &value)` for every entry
	/// associated with `key`.
	pub fn get_indexed_entries<Q>(&self, key: &Q) -> GetIndexedEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetIndexedEntries {
			indexes: self
				.map
				.get(outer_cmp(&self.entries), key)
				.map(Indexes::iter)
				.unwrap_or_default(),
			entries: &self.entries,
		}
	}

	/// Returns an iterator over `(index, &key, &value)` for every entry
	/// associated with `key`, inserting a single new entry with a value
	/// produced by `f` if `key` was not already present.
	pub fn get_or_insert_indexed_entries_with(
		&mut self,
		key: K,
		f: impl FnOnce() -> V,
	) -> GetIndexedEntries<'_, K, V>
	where
		K: Ord,
	{
		match self.map.address_of(outer_cmp(&self.entries), &key) {
			Ok(addr) => GetIndexedEntries {
				indexes: unsafe {
					// SAFETY: no `self.map` has been deallocated since we found
					//         `addr`.
					self.map.get_at(addr)
				}
				.unwrap()
				.iter(),
				entries: &self.entries,
			},
			Err(_) => {
				let (i, _) = self.push_back(key, f());
				GetIndexedEntries {
					indexes: self
						.map
						.get(inner_index_cmp(&self.entries), &i)
						.unwrap()
						.iter(),
					entries: &self.entries,
				}
			}
		}
	}

	/// Returns an iterator over `(index, &key, &value)` for every entry
	/// associated with `key`, inserting a single new entry with `value` if
	/// `key` was not already present.
	pub fn get_or_insert_indexed_entries(&mut self, key: K, value: V) -> GetIndexedEntries<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_indexed_entries_with(key, || value)
	}

	/// Returns an iterator over `(&key, &value)` for every entry associated
	/// with `key`.
	pub fn get_entries<Q>(&self, key: &Q) -> GetEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetEntries(self.get_indexed_entries(key))
	}

	/// Returns an iterator over `(&key, &value)` for every entry associated
	/// with `key`, inserting a single new entry with a value produced by
	/// `f` if `key` was not already present.
	pub fn get_or_insert_entries_with(
		&mut self,
		key: K,
		f: impl FnOnce() -> V,
	) -> GetEntries<'_, K, V>
	where
		K: Ord,
	{
		GetEntries(self.get_or_insert_indexed_entries_with(key, f))
	}

	/// Returns an iterator over `(&key, &value)` for every entry associated
	/// with `key`, inserting a single new entry with `value` if `key` was
	/// not already present.
	pub fn get_or_insert_entries(&mut self, key: K, value: V) -> GetEntries<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_entries_with(key, || value)
	}

	/// Returns an iterator over a reference to the value of every entry
	/// associated with `key`.
	pub fn get<Q>(&self, key: &Q) -> Get<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		Get(self.get_indexed_entries(key))
	}

	/// Returns an iterator over a reference to the value of every entry
	/// associated with `key`, inserting a single new entry with a value
	/// produced by `f` if `key` was not already present.
	pub fn get_or_insert_with(&mut self, key: K, f: impl FnOnce() -> V) -> Get<'_, K, V>
	where
		K: Ord,
	{
		Get(self.get_or_insert_indexed_entries_with(key, f))
	}

	/// Returns an iterator over a reference to the value of every entry
	/// associated with `key`, inserting a single new entry with `value` if
	/// `key` was not already present.
	pub fn get_or_insert(&mut self, key: K, value: V) -> Get<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_with(key, || value)
	}

	/// Returns an iterator over `(index, &value)` for every entry
	/// associated with `key`.
	pub fn get_indexed<Q>(&self, key: &Q) -> GetIndexed<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetIndexed(self.get_indexed_entries(key))
	}

	/// Returns an iterator over `(index, &value)` for every entry
	/// associated with `key`, inserting a single new entry with a value
	/// produced by `f` if `key` was not already present.
	pub fn get_or_insert_indexed_with(
		&mut self,
		key: K,
		f: impl FnOnce() -> V,
	) -> GetIndexed<'_, K, V>
	where
		K: Ord,
	{
		GetIndexed(self.get_or_insert_indexed_entries_with(key, f))
	}

	/// Returns an iterator over `(index, &value)` for every entry
	/// associated with `key`, inserting a single new entry with `value` if
	/// `key` was not already present.
	pub fn get_or_insert_indexed(&mut self, key: K, value: V) -> GetIndexed<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_indexed_with(key, || value)
	}

	/// Returns an iterator over `(index, &key, &mut value)` for every entry
	/// associated with `key`.
	pub fn get_indexed_entries_mut<Q>(&mut self, key: &Q) -> GetIndexedEntriesMut<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetIndexedEntriesMut {
			indexes: self
				.map
				.get(outer_cmp(&self.entries), key)
				.map(Indexes::iter)
				.unwrap_or_default(),
			entries: &mut self.entries,
		}
	}

	/// Returns an iterator over `(index, &key, &mut value)` for every entry
	/// associated with `key`, inserting a single new entry with a value
	/// produced by `f` if `key` was not already present.
	pub fn get_or_insert_indexed_entries_mut_with(
		&mut self,
		key: K,
		f: impl FnOnce() -> V,
	) -> GetIndexedEntriesMut<'_, K, V>
	where
		K: Ord,
	{
		match self.map.address_of(outer_cmp(&self.entries), &key) {
			Ok(addr) => GetIndexedEntriesMut {
				indexes: unsafe {
					// SAFETY: no `self.map` has been deallocated since we found
					//         `addr`.
					self.map.get_at(addr)
				}
				.unwrap()
				.iter(),
				entries: &mut self.entries,
			},
			Err(_) => {
				let (i, _) = self.push_back(key, f());
				GetIndexedEntriesMut {
					indexes: self
						.map
						.get(inner_index_cmp(&self.entries), &i)
						.unwrap()
						.iter(),
					entries: &mut self.entries,
				}
			}
		}
	}

	/// Returns an iterator over `(index, &key, &mut value)` for every entry
	/// associated with `key`, inserting a single new entry with `value` if
	/// `key` was not already present.
	pub fn get_or_insert_indexed_entries_mut(
		&mut self,
		key: K,
		value: V,
	) -> GetIndexedEntriesMut<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_indexed_entries_mut_with(key, || value)
	}

	/// Returns an iterator over `(&key, &mut value)` for every entry
	/// associated with `key`.
	pub fn get_entries_mut<Q>(&mut self, key: &Q) -> GetEntriesMut<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetEntriesMut(self.get_indexed_entries_mut(key))
	}

	/// Returns an iterator over `(&key, &mut value)` for every entry
	/// associated with `key`, inserting a single new entry with a value
	/// produced by `f` if `key` was not already present.
	pub fn get_or_insert_entries_mut_with(
		&mut self,
		key: K,
		f: impl FnOnce() -> V,
	) -> GetEntriesMut<'_, K, V>
	where
		K: Ord,
	{
		GetEntriesMut(self.get_or_insert_indexed_entries_mut_with(key, f))
	}

	/// Returns an iterator over `(&key, &mut value)` for every entry
	/// associated with `key`, inserting a single new entry with `value` if
	/// `key` was not already present.
	pub fn get_or_insert_entries_mut(&mut self, key: K, value: V) -> GetEntriesMut<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_entries_mut_with(key, || value)
	}

	/// Returns an iterator over a mutable reference to the value of every
	/// entry associated with `key`.
	pub fn get_mut<Q>(&mut self, key: &Q) -> GetMut<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		GetMut(self.get_indexed_entries_mut(key))
	}

	/// Returns an iterator over a mutable reference to the value of every
	/// entry associated with `key`, inserting a single new entry with a
	/// value produced by `f` if `key` was not already present.
	pub fn get_or_insert_mut_with(&mut self, key: K, f: impl FnOnce() -> V) -> GetMut<'_, K, V>
	where
		K: Ord,
	{
		GetMut(self.get_or_insert_indexed_entries_mut_with(key, f))
	}

	/// Returns an iterator over a mutable reference to the value of every
	/// entry associated with `key`, inserting a single new entry with
	/// `value` if `key` was not already present.
	pub fn get_or_insert_mut(&mut self, key: K, value: V) -> GetMut<'_, K, V>
	where
		K: Ord,
	{
		self.get_or_insert_mut_with(key, || value)
	}

	/// Gets the entry associated with `key` for in-place manipulation.
	///
	/// # Example
	///
	/// ```
	/// use btree_indexmap::{BTreeIndexMultiMap, multi_map::Entry};
	///
	/// let mut map: BTreeIndexMultiMap<&str, i32> = BTreeIndexMultiMap::new();
	///
	/// match map.entry("a") {
	///     Entry::Vacant(e) => {
	///         e.insert(1);
	///     }
	///     Entry::Occupied(_) => unreachable!(),
	/// }
	///
	/// assert_eq!(map.get("a").next(), Some(&1));
	/// ```
	pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
	where
		K: Ord,
	{
		if let Some(indices) = self.map.get(outer_cmp(&self.entries), &key) {
			return Entry::Occupied(OccupiedEntry {
				entries: &mut self.entries,
				indices,
			});
		}

		Entry::Vacant(VacantEntry {
			map: unsafe {
				// SAFETY: The compiler thinks `self` is still borrowed at this
				// point because `indices` has type `&'_ Indices` where `'_`
				// includes both the outer scope lifetime and the `self.map`
				// lifetime. However we know that `indices` is dropped before
				// this line is ever reached.
				std::mem::transmute_copy(&self)
			},
			key,
		})
	}

	/// Inserts a new entry at the end of the map.
	///
	/// Returns the index of the new entry, and whether `key` was not
	/// already present in the map.
	pub fn push_back(&mut self, key: K, value: V) -> (usize, bool)
	where
		K: Ord,
	{
		let i = self.entries.len();
		self.entries.push((key, value));

		let unique = match self.map.get_mut(inner_index_cmp(&self.entries), &i) {
			Some(indexes) => {
				indexes.rest.push(i);
				false
			}
			None => {
				self.map.insert(inner_cmp(&self.entries), Indexes::new(i));
				true
			}
		};

		(i, unique)
	}

	/// Inserts a new entry at the given `index`.
	///
	/// Returns whether `key` was not already present in the map.
	///
	/// # Panics
	///
	/// Panics if `index > len`.
	pub fn insert_at(&mut self, index: usize, key: K, value: V) -> bool
	where
		K: Ord,
	{
		for js in self.map.iter_mut() {
			for j in js.iter_mut() {
				if *j >= index {
					*j += 1;
				}
			}
		}

		self.entries.insert(index, (key, value));

		match self.map.get_mut(inner_index_cmp(&self.entries), &index) {
			Some(indexes) => {
				indexes.insert(index);
				false
			}
			None => {
				self.map
					.insert(inner_cmp(&self.entries), Indexes::new(index));
				true
			}
		}
	}

	/// Inserts a new entry at the front of the map.
	///
	/// Returns whether `key` was not already present in the map.
	pub fn push_front(&mut self, key: K, value: V) -> bool
	where
		K: Ord,
	{
		self.insert_at(0, key, value)
	}

	/// Inserts a `(key, value)` entry, keeping only this occurrence of
	/// `key`.
	///
	/// If `key` was already present, replaces its first occurrence and
	/// removes every other one (using shift semantics), returning the
	/// index of the kept entry and an iterator over the values it
	/// replaced or removed. Otherwise, appends a new entry and returns its
	/// index with an empty iterator.
	pub fn shift_insert_full(&mut self, key: K, value: V) -> (usize, ShiftInsert<'_, K, V>)
	where
		K: Ord,
	{
		match self.map.get_mut(outer_cmp(&self.entries), &key) {
			Some(indices) => {
				let i = indices.first;
				let mut indices = std::mem::replace(indices, Indexes::new(i))
					.into_iter()
					.enumerate();
				indices.next();

				let first = std::mem::replace(&mut self.entries[i].1, value);

				(
					i,
					ShiftInsert {
						first: Some(first),
						rest: ShiftRemove(ShiftRemoveIndexedEntries { indices, map: self }),
					},
				)
			}
			None => {
				let (i, _) = self.push_back(key, value);
				(
					i,
					ShiftInsert {
						first: None,
						rest: ShiftRemove(ShiftRemoveIndexedEntries {
							indices: Default::default(),
							map: self,
						}),
					},
				)
			}
		}
	}

	/// Inserts a `(key, value)` entry, keeping only this occurrence of
	/// `key`.
	///
	/// See [`Self::shift_insert_full`].
	pub fn shift_insert(&mut self, key: K, value: V) -> ShiftInsert<'_, K, V>
	where
		K: Ord,
	{
		self.shift_insert_full(key, value).1
	}

	/// Inserts a `(key, value)` entry, keeping only this occurrence of
	/// `key`.
	///
	/// If `key` was already present, replaces its first occurrence and
	/// removes every other one (using swap semantics), returning the
	/// index of the kept entry and an iterator over the values it
	/// replaced or removed. Otherwise, appends a new entry and returns its
	/// index with an empty iterator.
	pub fn swap_insert_full(&mut self, key: K, value: V) -> (usize, SwapInsert<'_, K, V>)
	where
		K: Ord,
	{
		match self.map.get_mut(outer_cmp(&self.entries), &key) {
			Some(indices) => {
				let i = indices.first;
				let mut indices = std::mem::replace(indices, Indexes::new(i)).into_iter();
				indices.next();

				let first = std::mem::replace(&mut self.entries[i].1, value);

				(
					i,
					SwapInsert {
						first: Some(first),
						rest: SwapRemove(SwapRemoveIndexedEntries { indices, map: self }),
					},
				)
			}
			None => {
				let (i, _) = self.push_back(key, value);
				(
					i,
					SwapInsert {
						first: None,
						rest: SwapRemove(SwapRemoveIndexedEntries {
							indices: Default::default(),
							map: self,
						}),
					},
				)
			}
		}
	}

	/// Inserts a `(key, value)` entry, keeping only this occurrence of
	/// `key`.
	///
	/// See [`Self::swap_insert_full`].
	pub fn swap_insert(&mut self, key: K, value: V) -> SwapInsert<'_, K, V>
	where
		K: Ord,
	{
		self.swap_insert_full(key, value).1
	}

	/// Inserts a `(key, value)` entry at the front of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns an iterator over the values of the removed occurrences,
	/// removed using shift semantics.
	pub fn shift_insert_front(&mut self, key: K, value: V) -> ShiftInsertFront<'_, K, V>
	where
		K: Ord,
	{
		ShiftInsertFront {
			remove: self.shift_remove(&key),
			entry: Some((key, value)),
		}
	}

	/// Inserts a `(key, value)` entry at the front of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns an iterator over the values of the removed occurrences,
	/// removed using swap semantics.
	pub fn swap_insert_front(&mut self, key: K, value: V) -> SwapInsertFront<'_, K, V>
	where
		K: Ord,
	{
		SwapInsertFront {
			remove: self.swap_remove(&key),
			entry: Some((key, value)),
		}
	}

	/// Inserts a `(key, value)` entry at the end of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns the index of the new entry and an iterator over the values
	/// of the removed occurrences, removed using shift semantics.
	pub fn shift_insert_back_full(&mut self, key: K, value: V) -> (usize, ShiftInsertBack<'_, K, V>)
	where
		K: Ord,
	{
		let len = self.len();
		let remove = self.shift_remove(&key);
		let i = len - remove.len();

		(
			i,
			ShiftInsertBack {
				remove,
				entry: Some((key, value)),
			},
		)
	}

	/// Inserts a `(key, value)` entry at the end of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns an iterator over the values of the removed occurrences,
	/// removed using shift semantics.
	pub fn shift_insert_back(&mut self, key: K, value: V) -> ShiftInsertBack<'_, K, V>
	where
		K: Ord,
	{
		ShiftInsertBack {
			remove: self.shift_remove(&key),
			entry: Some((key, value)),
		}
	}

	/// Inserts a `(key, value)` entry, keeping only this occurrence of
	/// `key`.
	///
	/// This is an alias for [`Self::shift_insert_back`].
	pub fn insert(&mut self, key: K, value: V) -> ShiftInsertBack<'_, K, V>
	where
		K: Ord,
	{
		self.shift_insert_back(key, value)
	}

	/// Inserts a `(key, value)` entry at the end of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns the index of the new entry and an iterator over the values
	/// of the removed occurrences, removed using swap semantics.
	pub fn swap_insert_back_full(&mut self, key: K, value: V) -> (usize, SwapInsertBack<'_, K, V>)
	where
		K: Ord,
	{
		let len = self.len();
		let remove = self.swap_remove(&key);
		let i = len - remove.len();

		(
			i,
			SwapInsertBack {
				remove,
				entry: Some((key, value)),
			},
		)
	}

	/// Inserts a `(key, value)` entry at the end of the map, replacing
	/// every previous occurrence of `key`.
	///
	/// Returns an iterator over the values of the removed occurrences,
	/// removed using swap semantics.
	pub fn swap_insert_back(&mut self, key: K, value: V) -> SwapInsertBack<'_, K, V>
	where
		K: Ord,
	{
		SwapInsertBack {
			remove: self.swap_remove(&key),
			entry: Some((key, value)),
		}
	}

	/// Removes the entry at the given `index`, returning its key and value,
	/// if it was present.
	///
	/// Shifts every following entry one index down.
	pub fn shift_remove_at(&mut self, i: usize) -> Option<(K, V)>
	where
		K: Ord,
	{
		self.map
			.address_of(inner_index_cmp(&self.entries), &i)
			.ok()
			.map(|addr| {
				let removed = unsafe { self.map.get_mut_at(addr).unwrap().remove(i) };

				if removed.is_err() {
					unsafe {
						// SAFETY: the node hasn't moved and hasn't been
						//         deallocated since we found its address.
						self.map.remove_at(addr).unwrap();
					}
				}

				let entry = self.entries.remove(i);

				for js in self.map.iter_mut() {
					for j in js.iter_mut() {
						if *j > i {
							*j -= 1;
						}
					}
				}

				entry
			})
	}

	/// Removes the entry at the given `index`, returning its key and value,
	/// if it was present.
	///
	/// Moves the last entry into the removed slot.
	pub fn swap_remove_at(&mut self, i: usize) -> Option<(K, V)>
	where
		K: Ord,
	{
		self.map
			.address_of(inner_index_cmp(&self.entries), &i)
			.ok()
			.map(|addr| {
				let removed = unsafe { self.map.get_mut_at(addr).unwrap().remove(i) };

				if removed.is_err() {
					unsafe {
						// SAFETY: the node hasn't moved and hasn't been
						//         deallocated since we found its address.
						self.map.remove_at(addr).unwrap();
					}
				}

				self.swap_already_removed_at(i)
			})
	}

	fn swap_already_removed_at(&mut self, i: usize) -> (K, V)
	where
		K: Ord,
	{
		let last = self.entries.len() - 1;

		if i == last {
			// The entry being removed is already the last one; just pop it.
			self.entries.pop().unwrap()
		} else {
			let last_key = &self.entries[last].0;
			self.map
				.get_mut(outer_cmp(&self.entries), last_key)
				.unwrap()
				.swap_last(i);

			self.entries.swap(i, last);
			self.entries.pop().unwrap()
		}
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over `(index, key, value)` for each removed entry.
	///
	/// Shifts the remaining entries down to fill the gaps.
	pub fn shift_remove_indexed_entries<Q>(
		&mut self,
		key: &Q,
	) -> ShiftRemoveIndexedEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		let indices = self
			.map
			.remove(outer_cmp(&self.entries), key)
			.map(Indexes::into_iter)
			.unwrap_or_default()
			.enumerate();

		ShiftRemoveIndexedEntries { indices, map: self }
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over `(key, value)` for each removed entry.
	///
	/// Shifts the remaining entries down to fill the gaps.
	pub fn shift_remove_entries<Q>(&mut self, key: &Q) -> ShiftRemoveEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		ShiftRemoveEntries(self.shift_remove_indexed_entries(key))
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over the value of each removed entry.
	///
	/// Shifts the remaining entries down to fill the gaps.
	pub fn shift_remove<Q>(&mut self, key: &Q) -> ShiftRemove<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
	{
		ShiftRemove(self.shift_remove_indexed_entries(key))
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over `(index, key, value)` for each removed entry.
	///
	/// Moves entries from the end of the map into the gaps.
	pub fn swap_remove_indexed_entries<Q>(&mut self, key: &Q) -> SwapRemoveIndexedEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
		K: Ord,
	{
		let indices = self
			.map
			.remove(outer_cmp(&self.entries), key)
			.map(Indexes::into_iter)
			.unwrap_or_default();

		SwapRemoveIndexedEntries { indices, map: self }
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over `(key, value)` for each removed entry.
	///
	/// Moves entries from the end of the map into the gaps.
	pub fn swap_remove_entries<Q>(&mut self, key: &Q) -> SwapRemoveEntries<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
		K: Ord,
	{
		SwapRemoveEntries(self.swap_remove_indexed_entries(key))
	}

	/// Removes every entry associated with `key`, returning an iterator
	/// over the value of each removed entry.
	///
	/// Moves entries from the end of the map into the gaps.
	pub fn swap_remove<Q>(&mut self, key: &Q) -> SwapRemove<'_, K, V>
	where
		Q: ?Sized + Comparable<K>,
		K: Ord,
	{
		SwapRemove(self.swap_remove_indexed_entries(key))
	}

	/// Returns an iterator over the entries of the map, in insertion
	/// (index) order.
	pub fn iter(&self) -> Iter<'_, K, V> {
		Iter(self.entries.iter())
	}

	/// Returns an iterator over the entries of the map, with a mutable
	/// reference to the value, in insertion (index) order.
	pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
		IterMut(self.entries.iter_mut())
	}

	/// Returns an iterator over the entries of the map, sorted by key
	/// according to `K`'s implementation of [`Ord`].
	///
	/// Entries that share the same key are visited in insertion (index)
	/// order.
	pub fn iter_sorted(&self) -> IterSorted<'_, K, V> {
		IterSorted {
			remaining: self.entries.len(),
			entries: &self.entries,
			inner: self.map.iter(),
			current: None,
		}
	}

	/// Returns an iterator over the entries of the map, with a mutable
	/// reference to the value, sorted by key according to `K`'s
	/// implementation of [`Ord`].
	///
	/// Entries that share the same key are visited in insertion (index)
	/// order.
	pub fn iter_mut_sorted(&mut self) -> IterMutSorted<'_, K, V> {
		IterMutSorted {
			remaining: self.entries.len(),
			entries: &mut self.entries,
			inner: self.map.iter(),
			current: None,
		}
	}

	/// Turns this map into an iterator over its entries, sorted by key
	/// according to `K`'s implementation of [`Ord`].
	///
	/// Entries that share the same key are visited in insertion (index)
	/// order.
	pub fn into_iter_sorted(self) -> IntoIterSorted<K, V> {
		IntoIterSorted {
			remaining: self.entries.len(),
			entries: unsafe {
				// SAFETY: `(K, V)` and `MaybeUninit<(K, V)>` have the exact
				//         same representation.
				std::mem::transmute::<Vec<(K, V)>, Vec<MaybeUninit<(K, V)>>>(self.entries)
			},
			inner: self.map.into_iter(),
			current: None,
		}
	}

	/// Returns an iterator over the keys of the map, in insertion (index)
	/// order.
	pub fn keys(&self) -> Keys<'_, K, V> {
		Keys(self.entries.iter())
	}

	/// Returns an iterator over the values of the map, in insertion (index)
	/// order.
	pub fn values(&self) -> Values<'_, K, V> {
		Values(self.entries.iter())
	}

	/// Returns an iterator over mutable references to the values of the
	/// map, in insertion (index) order.
	pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
		ValuesMut(self.entries.iter_mut())
	}

	/// Sort the entries by key name.
	///
	/// The relative order of entries with the same key is unchanged.
	pub fn sort(&mut self)
	where
		K: Ord,
	{
		let this = std::mem::take(self);
		self.extend(this.into_iter_sorted())
	}
}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::shift_insert_front`].
pub struct ShiftInsertFront<'a, K: Ord, V> {
	remove: ShiftRemove<'a, K, V>,
	entry: Option<(K, V)>,
}

impl<'a, K: Ord, V> Iterator for ShiftInsertFront<'a, K, V> {
	type Item = V;

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

impl<'a, K: Ord, V> Drop for ShiftInsertFront<'a, K, V> {
	fn drop(&mut self) {
		for _ in self.remove.0.by_ref() {}
		if let Some((key, value)) = self.entry.take() {
			self.remove.0.map.push_front(key, value);
		}
	}
}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::swap_insert_front`].
pub struct SwapInsertFront<'a, K: Ord, V> {
	remove: SwapRemove<'a, K, V>,
	entry: Option<(K, V)>,
}

impl<'a, K: Ord, V> Iterator for SwapInsertFront<'a, K, V> {
	type Item = V;

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

impl<'a, K: Ord, V> Drop for SwapInsertFront<'a, K, V> {
	fn drop(&mut self) {
		for _ in self.remove.0.by_ref() {}
		if let Some((key, value)) = self.entry.take() {
			self.remove.0.map.push_front(key, value);
		}
	}
}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::shift_insert_back`].
pub struct ShiftInsertBack<'a, K: Ord, V> {
	remove: ShiftRemove<'a, K, V>,
	entry: Option<(K, V)>,
}

impl<'a, K: Ord, V> Iterator for ShiftInsertBack<'a, K, V> {
	type Item = V;

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

impl<'a, K: Ord, V> Drop for ShiftInsertBack<'a, K, V> {
	fn drop(&mut self) {
		for _ in self.remove.0.by_ref() {}
		if let Some((key, value)) = self.entry.take() {
			self.remove.0.map.push_back(key, value);
		}
	}
}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::swap_insert_back`].
pub struct SwapInsertBack<'a, K: Ord, V> {
	remove: SwapRemove<'a, K, V>,
	entry: Option<(K, V)>,
}

impl<'a, K: Ord, V> Iterator for SwapInsertBack<'a, K, V> {
	type Item = V;

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

impl<'a, K: Ord, V> Drop for SwapInsertBack<'a, K, V> {
	fn drop(&mut self) {
		for _ in self.remove.0.by_ref() {}
		if let Some((key, value)) = self.entry.take() {
			self.remove.0.map.push_back(key, value);
		}
	}
}

/// An iterator over the values replaced or removed by
/// [`BTreeIndexMultiMap::shift_insert`].
pub struct ShiftInsert<'a, K, V> {
	first: Option<V>,
	rest: ShiftRemove<'a, K, V>,
}

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

	fn next(&mut self) -> Option<Self::Item> {
		self.first.take().or_else(|| self.rest.next())
	}
}

/// An iterator over the values replaced or removed by
/// [`BTreeIndexMultiMap::swap_insert`].
pub struct SwapInsert<'a, K: Ord, V> {
	first: Option<V>,
	rest: SwapRemove<'a, K, V>,
}

impl<'a, K: Ord, V> Iterator for SwapInsert<'a, K, V> {
	type Item = V;

	fn next(&mut self) -> Option<Self::Item> {
		self.first.take().or_else(|| self.rest.next())
	}
}

/// An iterator over `(index, key, value)` for every entry removed by
/// [`BTreeIndexMultiMap::swap_remove_indexed_entries`].
pub struct SwapRemoveIndexedEntries<'a, K: Ord, V> {
	indices: IndexesIntoIter,
	map: &'a mut BTreeIndexMultiMap<K, V>,
}

impl<'a, K: Ord, V> Iterator for SwapRemoveIndexedEntries<'a, K, V> {
	type Item = (usize, K, V);

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

	fn next(&mut self) -> Option<Self::Item> {
		// Process indices from highest to lowest so that the entry we pop
		// from the tail is never one of the entries we are removing.
		self.indices.next_back().map(|i| {
			let (k, v) = self.map.swap_already_removed_at(i);
			(i, k, v)
		})
	}
}

impl<'a, K: Ord, V> ExactSizeIterator for SwapRemoveIndexedEntries<'a, K, V> {}

impl<'a, K: Ord, V> Drop for SwapRemoveIndexedEntries<'a, K, V> {
	fn drop(&mut self) {
		// Consume the rest of the iterator to make sure everything is removed.
		for _ in self {}
	}
}

/// An iterator over `(key, value)` for every entry removed by
/// [`BTreeIndexMultiMap::swap_remove_entries`].
pub struct SwapRemoveEntries<'a, K: Ord, V>(SwapRemoveIndexedEntries<'a, K, V>);

impl<'a, K: Ord, V> Iterator for SwapRemoveEntries<'a, K, V> {
	type Item = (K, V);

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(_, k, v)| (k, v))
	}
}

impl<'a, K: Ord, V> ExactSizeIterator for SwapRemoveEntries<'a, K, V> {}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::swap_remove`].
pub struct SwapRemove<'a, K: Ord, V>(SwapRemoveIndexedEntries<'a, K, V>);

impl<'a, K: Ord, V> Iterator for SwapRemove<'a, K, V> {
	type Item = V;

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

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

impl<'a, K: Ord, V> ExactSizeIterator for SwapRemove<'a, K, V> {}

/// An iterator over `(index, key, value)` for every entry removed by
/// [`BTreeIndexMultiMap::shift_remove_indexed_entries`].
pub struct ShiftRemoveIndexedEntries<'a, K, V> {
	indices: std::iter::Enumerate<IndexesIntoIter>,
	map: &'a mut BTreeIndexMultiMap<K, V>,
}

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

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

	fn next(&mut self) -> Option<Self::Item> {
		self.indices.next().map(|(shift, i)| {
			let shifted_i = i - shift;
			let (k, v) = self.map.entries.remove(shifted_i);

			// Shift larger indices.
			for js in self.map.map.iter_mut() {
				for j in js.iter_mut() {
					if *j >= shifted_i {
						*j -= 1;
					}
				}
			}

			(i, k, v)
		})
	}
}

impl<'a, K, V> ExactSizeIterator for ShiftRemoveIndexedEntries<'a, K, V> {}

impl<'a, K, V> Drop for ShiftRemoveIndexedEntries<'a, K, V> {
	fn drop(&mut self) {
		// Consume the rest of the iterator to make sure everything is removed.
		for _ in self {}
	}
}

/// An iterator over `(key, value)` for every entry removed by
/// [`BTreeIndexMultiMap::shift_remove_entries`].
pub struct ShiftRemoveEntries<'a, K, V>(ShiftRemoveIndexedEntries<'a, K, V>);

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

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(_, k, v)| (k, v))
	}
}

impl<'a, K, V> ExactSizeIterator for ShiftRemoveEntries<'a, K, V> {}

/// An iterator over the values removed by
/// [`BTreeIndexMultiMap::shift_remove`].
pub struct ShiftRemove<'a, K, V>(ShiftRemoveIndexedEntries<'a, K, V>);

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

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

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

impl<'a, K, V> ExactSizeIterator for ShiftRemove<'a, K, V> {}

fn inner_index_cmp<K, V>(
	entries: &[(K, V)],
) -> impl use<'_, K, V> + Fn(&Indexes, &usize) -> Ordering
where
	K: Ord,
{
	|i, &j| entries[i.first].0.cmp(&entries[j].0)
}

fn inner_cmp<K, V>(entries: &[(K, V)]) -> impl use<'_, K, V> + Fn(&Indexes, &Indexes) -> Ordering
where
	K: Ord,
{
	|i, j| entries[i.first].0.cmp(&entries[j.first].0)
}

fn outer_cmp<K, V, Q>(entries: &[(K, V)]) -> impl use<'_, K, V, Q> + Fn(&Indexes, &Q) -> Ordering
where
	Q: ?Sized + Comparable<K>,
{
	|i, q| q.compare(&entries[i.first].0).reverse()
}

impl<K, V, Q> Index<&Q> for BTreeIndexMultiMap<K, V>
where
	Q: ?Sized + Comparable<K>,
{
	type Output = V;

	/// # Panics
	///
	/// Panics if `key` is not found in the map.
	fn index(&self, key: &Q) -> &Self::Output {
		self.get(key).next().expect("no entry found for key")
	}
}

/// An owning iterator over the entries of a [`BTreeIndexMultiMap`], in
/// insertion order.
pub type IntoIter<K, V> = std::vec::IntoIter<(K, V)>;

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

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

impl<K: PartialEq, V: PartialEq> PartialEq for BTreeIndexMultiMap<K, V> {
	fn eq(&self, other: &Self) -> bool {
		self.iter_sorted().eq(other.iter_sorted())
	}
}

impl<K: Eq, V: Eq> Eq for BTreeIndexMultiMap<K, V> {}

impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeIndexMultiMap<K, V> {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		self.iter_sorted().partial_cmp(other.iter_sorted())
	}
}

impl<K: Ord, V: Ord> Ord for BTreeIndexMultiMap<K, V> {
	fn cmp(&self, other: &Self) -> Ordering {
		self.iter_sorted().cmp(other.iter_sorted())
	}
}

impl<K: Hash, V: Hash> Hash for BTreeIndexMultiMap<K, V> {
	fn hash<H: Hasher>(&self, state: &mut H) {
		state.write_usize(self.len());
		for item in self.iter_sorted() {
			item.hash(state);
		}
	}
}

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

impl<K: Ord, V> Extend<(K, V)> for BTreeIndexMultiMap<K, V> {
	fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
		for (key, value) in iter {
			self.push_back(key, value);
		}
	}
}

impl<K: Ord, V> FromIterator<(K, V)> for BTreeIndexMultiMap<K, V> {
	fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
		let mut result = Self::new();
		result.extend(iter);
		result
	}
}

/// An iterator over the entries of a [`BTreeIndexMultiMap`], in insertion
/// order.
pub struct Iter<'a, K, V>(std::slice::Iter<'a, (K, V)>);

impl<K, V> Clone for Iter<'_, K, V> {
	fn clone(&self) -> Self {
		Self(self.0.clone())
	}
}

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

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

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

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

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

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

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

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

/// An iterator over the entries of a [`BTreeIndexMultiMap`], with a
/// mutable reference to the value, in insertion order.
pub struct IterMut<'a, K, V>(std::slice::IterMut<'a, (K, V)>);

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

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

	fn next(&mut self) -> Option<Self::Item> {
		self.0.next().map(|(k, v)| (&*k, v))
	}
}

impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
	fn next_back(&mut self) -> Option<Self::Item> {
		self.0.next_back().map(|(k, v)| (&*k, v))
	}
}

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

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

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

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

/// An iterator over the entries of a [`BTreeIndexMultiMap`], sorted by
/// key according to `K`'s implementation of [`Ord`].
///
/// Entries that share the same key are visited in insertion (index)
/// order.
pub struct IterSorted<'a, K, V> {
	entries: &'a [(K, V)],
	inner: raw_btree::Iter<'a, Indexes>,
	current: Option<IndexesIter<'a>>,
	remaining: usize,
}

impl<K, V> Clone for IterSorted<'_, K, V> {
	fn clone(&self) -> Self {
		Self {
			entries: self.entries,
			inner: self.inner,
			current: self.current.clone(),
			remaining: self.remaining,
		}
	}
}

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

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

	fn next(&mut self) -> Option<Self::Item> {
		loop {
			match &mut self.current {
				Some(indexes) => match indexes.next() {
					Some(i) => {
						self.remaining -= 1;
						let (k, v) = &self.entries[i];
						break Some((k, v));
					}
					None => self.current = None,
				},
				None => match self.inner.next() {
					Some(indexes) => self.current = Some(indexes.iter()),
					None => break None,
				},
			}
		}
	}
}

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

impl<K, V> FusedIterator for IterSorted<'_, K, V> {}

/// An iterator over the entries of a [`BTreeIndexMultiMap`], with a
/// mutable reference to the value, sorted by key according to `K`'s
/// implementation of [`Ord`].
///
/// Entries that share the same key are visited in insertion (index)
/// order.
pub struct IterMutSorted<'a, K, V> {
	entries: &'a mut [(K, V)],
	inner: raw_btree::Iter<'a, Indexes>,
	current: Option<IndexesIter<'a>>,
	remaining: usize,
}

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

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

	fn next(&mut self) -> Option<Self::Item> {
		loop {
			match &mut self.current {
				Some(indexes) => match indexes.next() {
					Some(i) => {
						self.remaining -= 1;
						let (k, v) = unsafe {
							std::mem::transmute::<&mut (K, V), &mut (K, V)>(&mut self.entries[i])
						};
						break Some((k, v));
					}
					None => self.current = None,
				},
				None => match self.inner.next() {
					Some(indexes) => self.current = Some(indexes.iter()),
					None => break None,
				},
			}
		}
	}
}

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

impl<K, V> FusedIterator for IterMutSorted<'_, K, V> {}

/// An owning iterator over the entries of a [`BTreeIndexMultiMap`],
/// sorted by key according to `K`'s implementation of [`Ord`].
///
/// Entries that share the same key are visited in insertion (index)
/// order.
pub struct IntoIterSorted<K, V> {
	entries: Vec<MaybeUninit<(K, V)>>,
	inner: raw_btree::IntoIter<Indexes>,
	current: Option<IndexesIntoIter>,
	remaining: usize,
}

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

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

	fn next(&mut self) -> Option<Self::Item> {
		loop {
			match &mut self.current {
				Some(indexes) => match indexes.next() {
					Some(i) => {
						self.remaining -= 1;
						let (k, v) = unsafe { self.entries[i].assume_init_read() };
						break Some((k, v));
					}
					None => self.current = None,
				},
				None => match self.inner.next() {
					Some(indexes) => self.current = Some(indexes.into_iter()),
					None => break None,
				},
			}
		}
	}
}

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

impl<K, V> FusedIterator for IntoIterSorted<K, V> {}

impl<K, V> Drop for IntoIterSorted<K, V> {
	fn drop(&mut self) {
		// Make sure the remaining entries are consumed.
		self.last();
	}
}

/// An iterator over the keys of a [`BTreeIndexMultiMap`], in insertion
/// order.
pub struct Keys<'a, K, V>(std::slice::Iter<'a, (K, V)>);

impl<K, V> Clone for Keys<'_, K, V> {
	fn clone(&self) -> Self {
		Self(self.0.clone())
	}
}

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

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

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

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

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

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

/// An iterator over the values of a [`BTreeIndexMultiMap`], in insertion
/// order.
pub struct Values<'a, K, V>(std::slice::Iter<'a, (K, V)>);

impl<K, V> Clone for Values<'_, K, V> {
	fn clone(&self) -> Self {
		Self(self.0.clone())
	}
}

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

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

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

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

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

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

/// An iterator over mutable references to the values of a
/// [`BTreeIndexMultiMap`], in insertion order.
pub struct ValuesMut<'a, K, V>(std::slice::IterMut<'a, (K, V)>);

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

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

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

impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
	fn next_back(&mut self) -> Option<Self::Item> {
		self.0.next_back().map(|(_, v)| v)
	}
}

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

impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}

/// A view into a single entry of a [`BTreeIndexMultiMap`], which may
/// either be vacant or occupied.
///
/// This is returned by [`BTreeIndexMultiMap::entry`].
pub enum Entry<'a, K, V> {
	Vacant(VacantEntry<'a, K, V>),
	Occupied(OccupiedEntry<'a, K, V>),
}

/// A view into a vacant entry of a [`BTreeIndexMultiMap`].
///
/// This is part of the [`Entry`] enum.
pub struct VacantEntry<'a, K, V> {
	map: &'a mut BTreeIndexMultiMap<K, V>,
	key: K,
}

impl<'a, K, V> VacantEntry<'a, K, V> {
	/// Returns a reference to the entry's key.
	pub fn key(&self) -> &K {
		&self.key
	}

	/// Consumes this entry, returning its key.
	pub fn into_key(self) -> K {
		self.key
	}

	/// Inserts `value` in the map for this entry's key, returning the new
	/// entry's index, key, and a mutable reference to the value.
	pub fn insert_full(self, value: V) -> (usize, &'a K, &'a mut V)
	where
		K: Ord,
	{
		let (i, _) = self.map.push_back(self.key, value);
		let (k, v) = &mut self.map.entries[i];
		(i, &*k, v)
	}

	/// Inserts `value` in the map for this entry's key, returning the new
	/// entry's key and a mutable reference to the value.
	pub fn insert_entry(self, value: V) -> (&'a K, &'a mut V)
	where
		K: Ord,
	{
		let (_, k, v) = self.insert_full(value);
		(k, v)
	}

	/// Inserts `value` in the map for this entry's key, returning a mutable
	/// reference to the value.
	pub fn insert(self, value: V) -> &'a mut V
	where
		K: Ord,
	{
		self.insert_full(value).2
	}
}

/// A view into an occupied entry of a [`BTreeIndexMultiMap`].
///
/// This is part of the [`Entry`] enum.
pub struct OccupiedEntry<'a, K, V> {
	entries: &'a mut Vec<(K, V)>,
	indices: &'a Indexes,
}

impl<'a, K, V> OccupiedEntry<'a, K, V> {
	/// Returns a reference to the entry's key.
	pub fn key(&self) -> &K {
		&self.entries[self.indices.first].0
	}

	/// Returns an iterator over `(index, &key, &value)` for every value
	/// associated with this entry's key.
	pub fn get_full(&self) -> GetIndexedEntries<'_, K, V> {
		GetIndexedEntries {
			indexes: self.indices.iter(),
			entries: self.entries,
		}
	}

	/// Returns an iterator over `(&key, &value)` for every value associated
	/// with this entry's key.
	pub fn get_entry(&self) -> GetEntries<'_, K, V> {
		GetEntries(self.get_full())
	}

	/// Returns an iterator over a reference to every value associated with
	/// this entry's key.
	pub fn get(&self) -> Get<'_, K, V> {
		Get(self.get_full())
	}

	/// Returns an iterator over `(index, &key, &mut value)` for every value
	/// associated with this entry's key.
	pub fn get_mut_full(&mut self) -> GetIndexedEntriesMut<'_, K, V> {
		GetIndexedEntriesMut {
			indexes: self.indices.iter(),
			entries: self.entries,
		}
	}

	/// Returns an iterator over `(&key, &mut value)` for every value
	/// associated with this entry's key.
	pub fn get_mut_entry(&mut self) -> GetEntriesMut<'_, K, V> {
		GetEntriesMut(self.get_mut_full())
	}

	/// Returns an iterator over a mutable reference to every value
	/// associated with this entry's key.
	pub fn get_mut(&mut self) -> GetMut<'_, K, V> {
		GetMut(self.get_mut_full())
	}

	/// Consumes this entry, returning an iterator over `(index, &key, &mut
	/// value)` for every value associated with this entry's key, tied to
	/// the lifetime of the map.
	pub fn into_mut_full(self) -> GetIndexedEntriesMut<'a, K, V> {
		GetIndexedEntriesMut {
			indexes: self.indices.iter(),
			entries: self.entries,
		}
	}

	/// Consumes this entry, returning an iterator over `(&key, &mut
	/// value)` for every value associated with this entry's key, tied to
	/// the lifetime of the map.
	pub fn into_mut_entry(self) -> GetEntriesMut<'a, K, V> {
		GetEntriesMut(self.into_mut_full())
	}

	/// Consumes this entry, returning an iterator over a mutable reference
	/// to every value associated with this entry's key, tied to the
	/// lifetime of the map.
	pub fn into_mut(self) -> GetMut<'a, K, V> {
		GetMut(self.into_mut_full())
	}

	/// Replaces the value of the first occurrence of this entry's key,
	/// returning the previous value.
	pub fn insert(&mut self, value: V) -> V {
		std::mem::replace(&mut self.entries[self.indices.first].1, value)
	}
}