ordered-multimap-0.3.1/src/list_ordered_multimap.rs

use dlv_list::{
    Drain as VecListDrain, Index, IntoIter as VecListIntoIter, Iter as VecListIter,
    IterMut as VecListIterMut, VecList,
};
use hashbrown::hash_map::{RawEntryMut, RawOccupiedEntryMut};
use hashbrown::HashMap;
use std::borrow::Borrow;
use std::collections::hash_map::RandomState;
use std::fmt::{self, Debug, Formatter};
use std::hash::{BuildHasher, Hash, Hasher};
use std::iter::{FromIterator, FusedIterator};
use std::marker::PhantomData;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

#[derive(Clone)]
pub struct ListOrderedMultimap<Key, Value, State = RandomState> {
    /// The hasher builder that constructs new hashers for hashing keys. We have to keep this
    /// separate from the hashmap itself as we need to be able to access it when the hashmap keys
    /// are reallocated due to reallocation. We cannot use the hash of the actual keys in the map
    /// as those hashes are not representative of what hash they truly represent.
    build_hasher: State,

    /// The list of the keys in the multimap. This is ordered by time of insertion.
    keys: VecList<Key>,

    /// The map from indices of keys to the indices of their values in the value list. The list of
    /// the indices is ordered by time of insertion. We never use hasher of the hashmap explicitly
    /// here, we instead use [`ListOrderedMultimap::build_hasher`].
    map: HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,

    /// The list of the values in the multimap. This is ordered by time of insertion.
    values: VecList<ValueEntry<Key, Value>>,
}

impl<Key, Value> ListOrderedMultimap<Key, Value, RandomState>
where
    Key: Eq + Hash,
{
    /// Creates a new multimap with no initial capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value1");
    /// assert_eq!(map.get(&"key1"), Some(&"value1"));
    /// ```
    pub fn new() -> ListOrderedMultimap<Key, Value, RandomState> {
        ListOrderedMultimap::default()
    }

    /// Creates a new multimap with the specified capacities.
    ///
    /// The multimap will be able to hold at least `key_capacity` keys and `value_capacity` values
    /// without reallocating. A capacity of 0 will result in no allocation for the respective
    /// container.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
    /// assert_eq!(map.keys_capacity(), 0);
    /// assert_eq!(map.values_capacity(), 0);
    ///
    /// let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(5, 10);
    /// assert_eq!(map.keys_capacity(), 5);
    /// assert_eq!(map.values_capacity(), 10);
    /// ```
    pub fn with_capacity(
        key_capacity: usize,
        value_capacity: usize,
    ) -> ListOrderedMultimap<Key, Value, RandomState> {
        ListOrderedMultimap {
            build_hasher: RandomState::new(),
            keys: VecList::with_capacity(key_capacity),
            map: HashMap::with_capacity_and_hasher(key_capacity, DummyState),
            values: VecList::with_capacity(value_capacity),
        }
    }
}

impl<Key, Value, State> ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    /// Appends a value to the list of values associated with the given key.
    ///
    /// If the key is not already in the multimap, this will be identical to an insert and the
    /// return value will be `false`. Otherwise, `true` will be returned.
    ///
    /// Complexity: amortized O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// let already_exists = map.append("key", "value");
    /// assert!(!already_exists);
    /// assert_eq!(map.values_len(), 1);
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// let already_exists = map.append("key", "value2");
    /// assert!(already_exists);
    /// assert_eq!(map.values_len(), 2);
    /// ```
    pub fn append(&mut self, key: Key, value: Value) -> bool {
        use self::RawEntryMut::*;

        let hash = hash_key(&self.build_hasher, &key);
        let entry = raw_entry_mut(&self.keys, &mut self.map, hash, &key);
        let build_hasher = &self.build_hasher;

        match entry {
            Occupied(mut entry) => {
                let key_index = entry.key();
                let mut value_entry = ValueEntry::new(*key_index, value);
                let map_entry = entry.get_mut();
                value_entry.previous_index = Some(map_entry.tail_index);
                let index = self.values.push_back(value_entry);
                self.values
                    .get_mut(map_entry.tail_index)
                    .unwrap()
                    .next_index = Some(index);
                map_entry.append(index);
                true
            }
            Vacant(entry) => {
                let key_index = self.keys.push_back(key);
                let value_entry = ValueEntry::new(key_index, value);
                let index = self.values.push_back(value_entry);
                let keys = &self.keys;
                entry.insert_with_hasher(hash, key_index, MapEntry::new(index), |&key_index| {
                    let key = keys.get(key_index).unwrap();
                    hash_key(build_hasher, key)
                });
                false
            }
        }
    }

    /// Returns an immutable reference to the first key-value pair in the multimap
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.back(), None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.back(), Some((&"key", &"value")));
    /// ```
    pub fn back(&self) -> Option<(&Key, &Value)> {
        self.iter().next_back()
    }

    /// Returns an immutable reference to the first key-value pair in the multimap
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.back_mut(), None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.back_mut(), Some((&"key", &mut "value")));
    /// ```
    pub fn back_mut(&mut self) -> Option<(&Key, &mut Value)> {
        self.iter_mut().next_back()
    }

    /// Removes all keys and values from the multimap.
    ///
    /// Complexity: O(|K| + |V|) where |K| is the number of keys and |V| is the number of values.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    /// assert_eq!(map.keys_len(), 1);
    /// assert_eq!(map.values_len(), 1);
    ///
    /// map.clear();
    /// assert_eq!(map.keys_len(), 0);
    /// assert_eq!(map.values_len(), 0);
    /// ```
    pub fn clear(&mut self) {
        self.keys.clear();
        self.map.clear();
        self.values.clear();
    }

    /// Returns whether the given key is in the multimap.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert!(!map.contains_key(&"key"));
    /// map.insert("key", "value");
    /// assert!(map.contains_key(&"key"));
    /// ```
    pub fn contains_key<KeyQuery>(&self, key: &KeyQuery) -> bool
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);
        raw_entry(&self.keys, &self.map, hash, key).is_some()
    }

    /// Returns an iterator that yields keys and all associated values with those keys as separate
    /// drain iterators. The order of yielded pairs will be the order in which the keys were first
    /// inserted into the multimap.
    ///
    /// Regardless of whether this iterator is fully consumed, all keys and values will be removed
    /// from the map.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let mut iter = map.drain_pairs();
    ///
    /// let (key, mut values) = iter.next().unwrap();
    /// assert_eq!(key, "key");
    /// assert_eq!(values.next(), Some("value1"));
    /// assert_eq!(values.next(), Some("value2"));
    /// assert_eq!(values.next(), None);
    /// ```
    pub fn drain_pairs(&mut self) -> KeyValuesDrain<Key, Value, State> {
        KeyValuesDrain {
            build_hasher: &self.build_hasher,
            keys: &self.keys as *const _,
            dropped: Arc::new(AtomicUsize::new(self.keys_len())),
            iter: self.keys.drain(),
            map: &mut self.map,
            values: &mut self.values as *mut _,
        }
    }

    /// Returns whether the given key is in the multimap.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// let value = map.entry("key").or_insert("value");
    /// assert_eq!(value, &"value");
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    /// ```
    pub fn entry(&mut self, key: Key) -> Entry<Key, Value, State> {
        use self::RawEntryMut::*;

        let hash = hash_key(&self.build_hasher, &key);

        // TODO: This ugliness arises from borrow checking issues which seems to happen when the
        // vacant entry is created in the match block further below for `Vacant` even though it
        // should be perfectly safe. Is there a better way to do this?
        if !self.contains_key(&key) {
            Entry::Vacant(VacantEntry {
                build_hasher: &self.build_hasher,
                hash,
                key,
                keys: &mut self.keys,
                map: &mut self.map,
                values: &mut self.values,
            })
        } else {
            match raw_entry_mut(&self.keys, &mut self.map, hash, &key) {
                Occupied(entry) => Entry::Occupied(OccupiedEntry {
                    entry,
                    keys: &mut self.keys,
                    values: &mut self.values,
                }),
                _ => panic!("expected occupied entry"),
            }
        }
    }

    /// Returns the number of values associated with a key.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.entry_len(&"key"), 0);
    ///
    /// map.insert("key", "value1");
    /// assert_eq!(map.entry_len(&"key"), 1);
    ///
    /// map.append(&"key", "value2");
    /// assert_eq!(map.entry_len(&"key"), 2);
    /// ```
    pub fn entry_len<KeyQuery>(&self, key: &KeyQuery) -> usize
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);

        match raw_entry(&self.keys, &self.map, hash, key) {
            Some((_, map_entry)) => map_entry.length,
            None => 0,
        }
    }

    /// Returns an immutable reference to the first key-value pair in the multimap
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.front(), None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.front(), Some((&"key", &"value")));
    /// ```
    pub fn front(&self) -> Option<(&Key, &Value)> {
        self.iter().next()
    }

    /// Returns an immutable reference to the first key-value pair in the multimap
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.front_mut(), None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.front_mut(), Some((&"key", &mut "value")));
    /// ```
    pub fn front_mut(&mut self) -> Option<(&Key, &mut Value)> {
        self.iter_mut().next()
    }

    /// Returns an immutable reference to the first value, by insertion order, associated with the
    /// given key, or `None` if the key is not in the multimap.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
    /// assert_eq!(map.get(&"key"), None);
    ///
    /// ```
    pub fn get<KeyQuery>(&self, key: &KeyQuery) -> Option<&Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);
        let (_, map_entry) = raw_entry(&self.keys, &self.map, hash, key)?;
        self.values
            .get(map_entry.head_index)
            .map(|entry| &entry.value)
    }

    /// Returns an iterator that yields immutable references to all values associated with the
    /// given key by insertion order.
    ///
    /// If the key is not in the multimap, the iterator will yield no values.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    /// map.append("key", "value2");
    ///
    /// let mut iter = map.get_all(&"key");
    /// assert_eq!(iter.next(), Some(&"value"));
    /// assert_eq!(iter.next(), Some(&"value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn get_all<KeyQuery>(&self, key: &KeyQuery) -> EntryValues<Key, Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);

        match raw_entry(&self.keys, &self.map, hash, key) {
            Some((_, map_entry)) => EntryValues::from_map_entry(&self.values, &map_entry),
            None => EntryValues::empty(&self.values),
        }
    }

    /// Returns an iterator that yields mutable references to all values associated with the given
    /// key by insertion order.
    ///
    /// If the key is not in the multimap, the iterator will yield no values.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let mut iter = map.get_all_mut(&"key");
    ///
    /// let first = iter.next().unwrap();
    /// assert_eq!(first, &mut "value1");
    /// *first = "value3";
    ///
    /// assert_eq!(iter.next(), Some(&mut "value2"));
    /// assert_eq!(iter.next(), None);
    ///
    /// assert_eq!(map.get(&"key"), Some(&"value3"));
    /// ```
    pub fn get_all_mut<KeyQuery>(&mut self, key: &KeyQuery) -> EntryValuesMut<Key, Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);

        match raw_entry(&self.keys, &self.map, hash, key) {
            Some((_, map_entry)) => EntryValuesMut::from_map_entry(&mut self.values, &map_entry),
            None => EntryValuesMut::empty(&mut self.values),
        }
    }

    /// Returns a mutable reference to the first value, by insertion order, associated with the
    /// given key, or `None` if the key is not in the multimap.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.get(&"key"), None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// let mut value = map.get_mut(&"key").unwrap();
    /// *value = "value2";
    ///
    /// assert_eq!(map.get(&"key"), Some(&"value2"));
    /// ```
    pub fn get_mut<KeyQuery>(&mut self, key: &KeyQuery) -> Option<&mut Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);
        let (_, map_entry) = raw_entry(&self.keys, &self.map, hash, key)?;
        self.values
            .get_mut(map_entry.head_index)
            .map(|entry| &mut entry.value)
    }

    /// Returns a reference to the multimap's [`BuildHasher`].
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
    /// let hasher = map.hasher();
    /// ```
    pub fn hasher(&self) -> &State {
        &self.build_hasher
    }

    /// Inserts the key-value pair into the multimap and returns the first value, by insertion
    /// order, that was already associated with the key.
    ///
    /// If the key is not already in the multimap, `None` will be returned. If the key is already in
    /// the multimap, the insertion ordering of the keys will remain unchanged.
    ///
    /// Complexity: O(1) amortized
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert!(map.is_empty());
    ///
    /// let old_value = map.insert("key", "value");
    /// assert!(old_value.is_none());
    /// assert_eq!(map.values_len(), 1);
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// let old_value = map.insert("key", "value2");
    /// assert_eq!(old_value, Some("value"));
    /// assert_eq!(map.values_len(), 1);
    /// assert_eq!(map.get(&"key"), Some(&"value2"));
    /// ```
    pub fn insert(&mut self, key: Key, value: Value) -> Option<Value> {
        self.insert_all(key, value).next()
    }

    /// Inserts the key-value pair into the multimap and returns an iterator that yields all values
    /// previously associated with the key by insertion order.
    ///
    /// If the key is not already in the multimap, the iterator will yield no values.If the key is
    /// already in the multimap, the insertion ordering of the keys will remain unchanged.
    ///
    /// Complexity: O(1) amortized
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert!(map.is_empty());
    ///
    /// {
    ///     let mut old_values = map.insert_all("key", "value");
    ///     assert_eq!(old_values.next(), None);
    /// }
    ///
    /// assert_eq!(map.values_len(), 1);
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// map.append("key", "value2");
    ///
    /// {
    ///     let mut old_values = map.insert_all("key", "value3");
    ///     assert_eq!(old_values.next(), Some("value"));
    ///     assert_eq!(old_values.next(), Some("value2"));
    ///     assert_eq!(old_values.next(), None);
    /// }
    ///
    /// assert_eq!(map.values_len(), 1);
    /// assert_eq!(map.get(&"key"), Some(&"value3"));
    /// ```
    pub fn insert_all(&mut self, key: Key, value: Value) -> EntryValuesDrain<Key, Value> {
        use self::RawEntryMut::*;

        let hash = hash_key(&self.build_hasher, &key);
        let entry = raw_entry_mut(&self.keys, &mut self.map, hash, &key);
        let build_hasher = &self.build_hasher;

        match entry {
            Occupied(mut entry) => {
                let key_index = entry.key();
                let value_entry = ValueEntry::new(*key_index, value);
                let index = self.values.push_back(value_entry);
                let map_entry = entry.get_mut();
                let iter = EntryValuesDrain::from_map_entry(&mut self.values, &map_entry);
                map_entry.reset(index);
                iter
            }
            Vacant(entry) => {
                let key_index = self.keys.push_back(key);
                let value_entry = ValueEntry::new(key_index, value);
                let index = self.values.push_back(value_entry);
                let keys = &self.keys;
                entry.insert_with_hasher(hash, key_index, MapEntry::new(index), |&key_index| {
                    let key = keys.get(key_index).unwrap();
                    hash_key(build_hasher, key)
                });
                EntryValuesDrain::empty(&mut self.values)
            }
        }
    }

    /// Returns whether the multimap is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert!(map.is_empty());
    ///
    /// map.insert("key1", "value");
    /// assert!(!map.is_empty());
    ///
    /// map.remove(&"key1");
    /// assert!(map.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.keys.is_empty()
    }

    /// Returns an iterator that yields immutable references to all key-value pairs in the multimap
    /// by insertion order.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value1");
    /// map.append(&"key1", "value2");
    /// map.append(&"key2", "value2");
    ///
    /// let mut iter = map.iter();
    /// assert_eq!(iter.size_hint(), (4, Some(4)));
    /// assert_eq!(iter.next(), Some((&"key1", &"value1")));
    /// assert_eq!(iter.next(), Some((&"key2", &"value1")));
    /// assert_eq!(iter.next(), Some((&"key1", &"value2")));
    /// assert_eq!(iter.next(), Some((&"key2", &"value2")));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&self) -> Iter<Key, Value> {
        Iter {
            keys: &self.keys,
            iter: self.values.iter(),
        }
    }

    /// Returns an iterator that yields mutable references to all key-value pairs in the multimap by
    /// insertion order.
    ///
    /// Only the values are mutable, the keys are immutable.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value1");
    /// map.append(&"key1", "value2");
    /// map.append(&"key2", "value2");
    ///
    /// let mut iter = map.iter_mut();
    /// assert_eq!(iter.size_hint(), (4, Some(4)));
    ///
    /// let first = iter.next().unwrap();
    /// assert_eq!(first, (&"key1", &mut "value1"));
    /// *first.1 = "value3";
    ///
    /// assert_eq!(iter.next(), Some((&"key2", &mut "value1")));
    /// assert_eq!(iter.next(), Some((&"key1", &mut "value2")));
    /// assert_eq!(iter.next(), Some((&"key2", &mut "value2")));
    /// assert_eq!(iter.next(), None);
    ///
    /// assert_eq!(map.get(&"key1"), Some(&"value3"));
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<Key, Value> {
        IterMut {
            keys: &self.keys,
            iter: self.values.iter_mut(),
        }
    }

    /// Returns an iterator that yields immutable references to all keys in the multimap by
    /// insertion order.
    ///
    /// Insertion order of keys is determined by the order in which a given key is first inserted
    /// into the multimap with a value. Any subsequent insertions with that key without first
    /// removing it will not affect its ordering.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value");
    /// map.insert("key2", "value");
    /// map.insert("key3", "value");
    ///
    /// let mut keys = map.keys();
    /// assert_eq!(keys.next(), Some(&"key1"));
    /// assert_eq!(keys.next(), Some(&"key2"));
    /// assert_eq!(keys.next(), Some(&"key3"));
    /// assert_eq!(keys.next(), None);
    /// ```
    pub fn keys(&self) -> Keys<Key> {
        Keys(self.keys.iter())
    }

    /// Returns the number of keys the multimap can hold without reallocating.
    ///
    /// This number is a lower bound, and the multimap may be able to hold more.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.keys_capacity(), 0);
    ///
    /// map.insert("key", "value");
    /// assert!(map.keys_capacity() > 0);
    /// ```
    pub fn keys_capacity(&self) -> usize {
        self.keys.capacity()
    }

    /// Returns the number of keys in the multimap.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.keys_len(), 0);
    ///
    /// map.insert("key1", "value");
    /// map.insert("key2", "value");
    /// map.insert("key3", "value");
    /// assert_eq!(map.keys_len(), 3);
    /// ```
    pub fn keys_len(&self) -> usize {
        self.keys.len()
    }

    /// Reorganizes the multimap to ensure maximum spatial locality and changes the key and value
    /// capacities to the provided values.
    ///
    /// This function can be used to actually increase the capacity of the multimap.
    ///
    /// Complexity: O(|K| + |V|) where |K| is the number of keys and |V| is the number of values.
    ///
    /// # Panics
    ///
    /// Panics if either of the given minimum capacities are less than their current respective
    /// lengths.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::with_capacity(10, 10);
    ///
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value2");
    /// map.append("key2", "value3");
    /// map.append("key1", "value4");
    /// map.pack_to(5, 5);
    ///
    /// assert_eq!(map.keys_capacity(), 5);
    /// assert_eq!(map.keys_len(), 2);
    /// assert_eq!(map.values_capacity(), 5);
    /// assert_eq!(map.values_len(), 4);
    /// ```
    pub fn pack_to(&mut self, keys_minimum_capacity: usize, values_minimum_capacity: usize)
    where
        State: Default,
    {
        assert!(
            keys_minimum_capacity >= self.keys_len(),
            "cannot pack multimap keys lower than current length"
        );
        assert!(
            values_minimum_capacity >= self.values_len(),
            "cannot pack multimap values lower than current length"
        );

        let key_map = self.keys.pack_to(keys_minimum_capacity);
        let value_map = self.values.pack_to(values_minimum_capacity);
        let mut map = HashMap::with_capacity_and_hasher(keys_minimum_capacity, DummyState);
        let build_hasher = &self.build_hasher;

        for value_entry in self.values.iter_mut() {
            value_entry.key_index = key_map[&value_entry.key_index];
            value_entry.next_index = value_entry.next_index.map(|index| value_map[&index]);
            value_entry.previous_index = value_entry.previous_index.map(|index| value_map[&index]);
        }

        for (key_index, mut map_entry) in self.map.drain() {
            map_entry.head_index = value_map[&map_entry.head_index];
            map_entry.tail_index = value_map[&map_entry.tail_index];
            let key_index = key_map[&key_index];
            let key = self.keys.get(key_index).unwrap();
            let hash = hash_key(&self.build_hasher, key);

            match map.raw_entry_mut().from_hash(hash, |_| false) {
                RawEntryMut::Vacant(entry) => {
                    let keys = &self.keys;
                    entry.insert_with_hasher(hash, key_index, map_entry, |&key_index| {
                        let key = keys.get(key_index).unwrap();
                        hash_key(build_hasher, key)
                    });
                }
                _ => panic!("expected vacant entry"),
            }
        }

        self.map = map;
    }

    /// Reorganizes the multimap to ensure maximum spatial locality and removes any excess key and
    /// value capacity.
    ///
    /// Complexity: O(|K| + |V|) where |K| is the number of keys and |V| is the number of values.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::with_capacity(5, 5);
    ///
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value2");
    /// map.append("key2", "value3");
    /// map.append("key1", "value4");
    /// map.pack_to_fit();
    ///
    /// assert_eq!(map.keys_capacity(), 2);
    /// assert_eq!(map.keys_len(), 2);
    /// assert_eq!(map.values_capacity(), 4);
    /// assert_eq!(map.values_len(), 4);
    /// ```
    pub fn pack_to_fit(&mut self)
    where
        State: Default,
    {
        self.pack_to(self.keys_len(), self.values_len());
    }

    /// Returns an iterator that yields immutable references to keys and all associated values with
    /// those keys as separate iterators. The order of yielded pairs will be the order in which the
    /// keys were first inserted into the multimap.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let mut iter = map.pairs();
    ///
    /// let (key, mut values) = iter.next().unwrap();
    /// assert_eq!(key, &"key");
    /// assert_eq!(values.next(), Some(&"value1"));
    /// assert_eq!(values.next(), Some(&"value2"));
    /// assert_eq!(values.next(), None);
    /// ```
    pub fn pairs(&self) -> KeyValues<Key, Value, State> {
        KeyValues {
            build_hasher: &self.build_hasher,
            keys: &self.keys,
            iter: self.keys.iter(),
            map: &self.map,
            values: &self.values,
        }
    }

    /// Returns an iterator that yields immutable references to keys and mutable references to all
    /// associated values with those keys as separate iterators. The order of yielded pairs will be
    /// the order in which the keys were first inserted into the multimap.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let mut iter = map.pairs_mut();
    ///
    /// let (key, mut values) = iter.next().unwrap();
    /// assert_eq!(key, &"key");
    /// assert_eq!(values.next(), Some(&mut "value1"));
    /// assert_eq!(values.next(), Some(&mut "value2"));
    /// assert_eq!(values.next(), None);
    /// ```
    pub fn pairs_mut(&mut self) -> KeyValuesMut<Key, Value, State> {
        KeyValuesMut {
            build_hasher: &self.build_hasher,
            keys: &self.keys,
            iter: self.keys.iter(),
            map: &self.map,
            values: &mut self.values as *mut _,
        }
    }

    /// Removes the last key-value pair to have been inserted.
    ///
    /// Because a single key can be associated with many values, the key returned by this function
    /// is a [`KeyWrapper`] which can be either owned or borrowed. If the value removed was the only
    /// value associated with the key, then the key will be returned. Otherwise, a reference to the
    /// key will be returned.
    ///
    /// This function along with [`ListOrderedMultimap::pop_front`] act as replacements for a drain
    /// iterator since an iterator cannot be done over [`KeyWrapper`].
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::KeyWrapper;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let (key, value) = map.pop_back().unwrap();
    /// assert_eq!(key, KeyWrapper::Borrowed(&"key"));
    /// assert_eq!(&value, &"value2");
    ///
    /// let (key, value) = map.pop_back().unwrap();
    /// assert_eq!(key, KeyWrapper::Owned("key"));
    /// assert_eq!(&value, &"value1");
    /// ```
    pub fn pop_back(&mut self) -> Option<(KeyWrapper<Key>, Value)> {
        let value_entry = self.values.pop_back()?;

        let key_wrapper = match value_entry.previous_index {
            Some(previous_index) => {
                let key = self.keys.get(value_entry.key_index).unwrap();
                let hash = hash_key(&self.build_hasher, &key);

                let mut entry = match raw_entry_mut(&self.keys, &mut self.map, hash, key) {
                    RawEntryMut::Occupied(entry) => entry,
                    _ => panic!("expected occupied entry in internal map"),
                };
                let map_entry = entry.get_mut();
                map_entry.length -= 1;
                map_entry.tail_index = previous_index;

                let previous_value_entry = self.values.get_mut(previous_index).unwrap();
                previous_value_entry.next_index = None;

                KeyWrapper::Borrowed(key)
            }
            None => {
                let key = self.keys.remove(value_entry.key_index).unwrap();
                let hash = hash_key(&self.build_hasher, &key);

                match raw_entry_mut_empty(&self.keys, &mut self.map, hash) {
                    RawEntryMut::Occupied(entry) => {
                        entry.remove();
                    }
                    _ => panic!("expectd occupied entry in internal map"),
                }

                KeyWrapper::Owned(key)
            }
        };

        Some((key_wrapper, value_entry.value))
    }

    /// Removes the first key-value pair to have been inserted.
    ///
    /// Because a single key can be associated with many values, the key returned by this function
    /// is a [`KeyWrapper`] which can be either owned or borrowed. If the value removed was the only
    /// value associated with the key, then the key will be returned. Otherwise, a reference to the
    /// key will be returned.
    ///
    /// This function along with [`ListOrderedMultimap::pop_back`] act as replacements for a drain
    /// iterator since an iterator cannot be done over [`KeyWrapper`].
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::KeyWrapper;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    ///
    /// let (key, value) = map.pop_front().unwrap();
    /// assert_eq!(key, KeyWrapper::Borrowed(&"key"));
    /// assert_eq!(&value, &"value1");
    ///
    /// let (key, value) = map.pop_front().unwrap();
    /// assert_eq!(key, KeyWrapper::Owned("key"));
    /// assert_eq!(&value, &"value2");
    /// ```
    pub fn pop_front(&mut self) -> Option<(KeyWrapper<Key>, Value)> {
        let value_entry = self.values.pop_front()?;

        let key_wrapper = match value_entry.next_index {
            Some(next_index) => {
                let key = self.keys.get(value_entry.key_index).unwrap();
                let hash = hash_key(&self.build_hasher, &key);

                let mut entry = match raw_entry_mut(&self.keys, &mut self.map, hash, key) {
                    RawEntryMut::Occupied(entry) => entry,
                    _ => panic!("expected occupied entry in internal map"),
                };
                let map_entry = entry.get_mut();
                map_entry.length -= 1;
                map_entry.head_index = next_index;

                let next_value_entry = self.values.get_mut(next_index).unwrap();
                next_value_entry.previous_index = None;

                KeyWrapper::Borrowed(key)
            }
            None => {
                let key = self.keys.remove(value_entry.key_index).unwrap();
                let hash = hash_key(&self.build_hasher, &key);

                match raw_entry_mut_empty(&self.keys, &mut self.map, hash) {
                    RawEntryMut::Occupied(entry) => {
                        entry.remove();
                    }
                    _ => panic!("expectd occupied entry in internal map"),
                }

                KeyWrapper::Owned(key)
            }
        };

        Some((key_wrapper, value_entry.value))
    }

    /// Removes all values associated with the given key from the map and returns the first value
    /// by insertion order.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// let removed_value = map.remove(&"key");
    /// assert_eq!(removed_value, None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// let removed_value = map.remove(&"key");
    /// assert_eq!(removed_value, Some("value"));
    /// assert_eq!(map.get(&"key"), None);
    /// ```
    pub fn remove<KeyQuery>(&mut self, key: &KeyQuery) -> Option<Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        self.remove_entry(key).map(|(_, value)| value)
    }

    /// Removes all values associated with the given key from the map and returns an iterator that
    /// yields those values.
    ///
    /// If the key is not already in the map, the iterator will yield no values.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// {
    ///     let mut removed_values = map.remove_all(&"key");
    ///     assert_eq!(removed_values.next(), None);
    /// }
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    /// assert_eq!(map.get(&"key"), Some(&"value1"));
    ///
    /// {
    ///     let mut removed_values = map.remove_all(&"key");
    ///     assert_eq!(removed_values.next(), Some("value1"));
    ///     assert_eq!(removed_values.next(), Some("value2"));
    ///     assert_eq!(removed_values.next(), None);
    /// }
    ///
    /// assert_eq!(map.get(&"key"), None);
    /// ```
    pub fn remove_all<KeyQuery>(&mut self, key: &KeyQuery) -> EntryValuesDrain<Key, Value>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        use self::RawEntryMut::*;

        let hash = hash_key(&self.build_hasher, &key);
        let entry = raw_entry_mut(&self.keys, &mut self.map, hash, key);

        match entry {
            Occupied(entry) => {
                let (key_index, map_entry) = entry.remove_entry();
                self.keys.remove(key_index).unwrap();
                EntryValuesDrain::from_map_entry(&mut self.values, &map_entry)
            }
            Vacant(_) => EntryValuesDrain::empty(&mut self.values),
        }
    }

    /// Removes all values associated with the given key from the map and returns the key and first
    /// value.
    ///
    /// If the key is not already in the map, then `None` will be returned.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// let entry = map.remove_entry(&"key");
    /// assert_eq!(entry, None);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    ///
    /// let entry = map.remove_entry(&"key");
    /// assert_eq!(entry, Some(("key", "value")));
    /// assert_eq!(map.get(&"key"), None);
    /// ```
    pub fn remove_entry<KeyQuery>(&mut self, key: &KeyQuery) -> Option<(Key, Value)>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let (key, mut iter) = self.remove_entry_all(key)?;
        Some((key, iter.next().unwrap()))
    }

    /// Removes all values associated with the given key from the map and returns the key and an
    /// iterator that yields those values.
    ///
    /// If the key is not already in the map, then `None` will be returned.
    ///
    /// Complexity: O(1)
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// {
    ///     let entry = map.remove_entry_all(&"key");
    ///     assert!(entry.is_none());
    /// }
    ///
    /// map.insert("key", "value1");
    /// map.append("key", "value2");
    /// assert_eq!(map.get(&"key"), Some(&"value1"));
    ///
    /// {
    ///     let (key, mut iter) = map.remove_entry_all(&"key").unwrap();
    ///     assert_eq!(key, "key");
    ///     assert_eq!(iter.next(), Some("value1"));
    ///     assert_eq!(iter.next(), Some("value2"));
    ///     assert_eq!(iter.next(), None);
    /// }
    ///
    /// assert_eq!(map.get(&"key"), None);
    /// ```
    pub fn remove_entry_all<KeyQuery>(
        &mut self,
        key: &KeyQuery,
    ) -> Option<(Key, EntryValuesDrain<Key, Value>)>
    where
        Key: Borrow<KeyQuery>,
        KeyQuery: ?Sized + Eq + Hash,
    {
        let hash = hash_key(&self.build_hasher, &key);
        let entry = raw_entry_mut(&self.keys, &mut self.map, hash, key);

        match entry {
            RawEntryMut::Occupied(entry) => {
                let (key_index, map_entry) = entry.remove_entry();
                let key = self.keys.remove(key_index).unwrap();
                let iter = EntryValuesDrain::from_map_entry(&mut self.values, &map_entry);
                Some((key, iter))
            }
            _ => None,
        }
    }

    /// Reserves additional capacity such that more keys can be stored in the multimap.
    ///
    /// If the existing capacity minus the current length is enough to satisfy the additional
    /// capacity, the capacity will remain unchanged.
    ///
    /// If the capacity is increased, the capacity may be increased by more than what was requested.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::with_capacity(1, 1);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.keys_capacity(), 1);
    ///
    /// map.reserve_keys(10);
    /// assert!(map.keys_capacity() >= 11);
    /// assert_eq!(map.get(&"key"), Some(&"value"));
    /// ```
    pub fn reserve_keys(&mut self, additional_capacity: usize) {
        if self.keys.capacity() - self.keys.len() >= additional_capacity {
            return;
        }

        let capacity = self.map.capacity() + additional_capacity;
        let mut map = HashMap::with_capacity_and_hasher(capacity, DummyState);

        for (key_index, map_entry) in self.map.drain() {
            let key = self.keys.get(key_index).unwrap();
            let hash = hash_key(&self.build_hasher, key);
            let entry = match raw_entry_mut(&self.keys, &mut map, hash, key) {
                RawEntryMut::Vacant(entry) => entry,
                _ => panic!("expected vacant entry"),
            };
            entry.insert_hashed_nocheck(hash, key_index, map_entry);
        }

        self.keys.reserve(additional_capacity);
        self.map = map;
    }

    /// Reserves additional capacity such that more values can be stored in the multimap.
    ///
    /// If the existing capacity minus the current length is enough to satisfy the additional
    /// capacity, the capacity will remain unchanged.
    ///
    /// If the capacity is increased, the capacity may be increased by more than what was requested.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::with_capacity(1, 1);
    ///
    /// map.insert("key", "value");
    /// assert_eq!(map.values_capacity(), 1);
    ///
    /// map.reserve_values(10);
    /// assert!(map.values_capacity() >= 11);
    /// ```
    pub fn reserve_values(&mut self, additional_capacity: usize) {
        self.values.reserve(additional_capacity);
    }

    /// Keeps all key-value pairs that satisfy the given predicate function.
    ///
    /// Complexity: O(|V|) where |V| is the number of values
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.insert("key1", 1);
    /// map.insert("key2", 5);
    /// map.append("key1", -1);
    /// map.insert("key3", -10);
    ///
    /// map.retain(|_, &mut value| value >= 0);
    ///
    /// let mut iter = map.iter();
    /// assert_eq!(iter.next(), Some((&"key1", &1)));
    /// assert_eq!(iter.next(), Some((&"key2", &5)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn retain<Function>(&mut self, function: Function)
    where
        Function: FnMut(&Key, &mut Value) -> bool,
    {
        ListOrderedMultimap::retain_helper(
            &self.build_hasher,
            &mut self.keys,
            &mut self.map,
            &mut self.values,
            function,
        );
    }

    /// Helper function for [`ListOrderedMultimap::retain`] to deal with borrowing issues.
    fn retain_helper<'map, Function>(
        build_hasher: &'map State,
        keys: &'map mut VecList<Key>,
        map: &'map mut HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,
        values: &'map mut VecList<ValueEntry<Key, Value>>,
        mut function: Function,
    ) where
        Function: FnMut(&Key, &mut Value) -> bool,
    {
        let values_ptr = values as *mut VecList<ValueEntry<Key, Value>>;
        values.retain(|value_entry| {
            let key = keys.get(value_entry.key_index).unwrap();

            if !function(key, &mut value_entry.value) {
                let hash = hash_key(build_hasher, key);
                let mut entry = match raw_entry_mut(keys, map, hash, key) {
                    RawEntryMut::Occupied(entry) => entry,
                    _ => panic!("expected occupied entry in internal map"),
                };

                if value_entry.previous_index.is_none() && value_entry.next_index.is_none() {
                    entry.remove();
                    keys.remove(value_entry.key_index);
                } else {
                    let map_entry = entry.get_mut();
                    map_entry.length -= 1;

                    if let Some(previous_index) = value_entry.previous_index {
                        let previous_value_entry =
                            unsafe { (*values_ptr).get_mut(previous_index) }.unwrap();
                        previous_value_entry.next_index = value_entry.next_index;
                    } else {
                        map_entry.head_index = value_entry.next_index.unwrap();
                    }

                    if let Some(next_index) = value_entry.next_index {
                        let next_value_entry =
                            unsafe { (*values_ptr).get_mut(next_index) }.unwrap();
                        next_value_entry.previous_index = value_entry.previous_index;
                    } else {
                        map_entry.tail_index = value_entry.previous_index.unwrap();
                    }
                }

                false
            } else {
                true
            }
        });
    }

    /// Returns an iterator that yields immutable references to all values in the multimap by
    /// insertion order.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value1");
    /// map.append(&"key1", "value2");
    /// map.append(&"key2", "value2");
    ///
    /// let mut iter = map.values();
    /// assert_eq!(iter.size_hint(), (4, Some(4)));
    /// assert_eq!(iter.next(), Some(&"value1"));
    /// assert_eq!(iter.next(), Some(&"value1"));
    /// assert_eq!(iter.next(), Some(&"value2"));
    /// assert_eq!(iter.next(), Some(&"value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn values(&self) -> Values<Key, Value> {
        Values(self.values.iter())
    }

    /// Returns an iterator that yields mutable references to all values in the multimap by
    /// insertion order.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key1", "value1");
    /// map.insert("key2", "value1");
    /// map.append(&"key1", "value2");
    /// map.append(&"key2", "value2");
    ///
    /// let mut iter = map.values_mut();
    /// assert_eq!(iter.size_hint(), (4, Some(4)));
    ///
    /// let first = iter.next().unwrap();
    /// assert_eq!(first, &mut "value1");
    /// *first = "value3";
    ///
    /// assert_eq!(iter.next(), Some(&mut "value1"));
    /// assert_eq!(iter.next(), Some(&mut "value2"));
    /// assert_eq!(iter.next(), Some(&mut "value2"));
    /// assert_eq!(iter.next(), None);
    ///
    /// assert_eq!(map.get(&"key1"), Some(&"value3"));
    /// ```
    pub fn values_mut(&mut self) -> ValuesMut<Key, Value> {
        ValuesMut(self.values.iter_mut())
    }

    /// Returns the number of values the multimap can hold without reallocating.
    ///
    /// This number is a lower bound, and the multimap may be able to hold more.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.values_capacity(), 0);
    ///
    /// map.insert("key", "value");
    /// assert!(map.values_capacity() > 0);
    /// ```
    pub fn values_capacity(&self) -> usize {
        self.values.capacity()
    }

    /// Returns the total number of values in the multimap across all keys.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// assert_eq!(map.values_len(), 0);
    ///
    /// map.insert("key1", "value1");
    /// assert_eq!(map.values_len(), 1);
    ///
    /// map.append("key1", "value2");
    /// assert_eq!(map.values_len(), 2);
    /// ```
    pub fn values_len(&self) -> usize {
        self.values.len()
    }

    /// Creates a new multimap with the specified capacities and the given hash builder to hash
    /// keys.
    ///
    /// The multimap will be able to hold at least `key_capacity` keys and `value_capacity` values
    /// without reallocating. A capacity of 0 will result in no allocation for the respective
    /// container.
    ///
    /// The `state` is normally randomly generated and is designed to allow multimaps to be
    /// resistant to attacks that cause many collisions and very poor performance. Setting it
    /// manually using this function can expose a DoS attack vector.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use std::collections::hash_map::RandomState;
    ///
    /// let state = RandomState::new();
    /// let mut map = ListOrderedMultimap::with_capacity_and_hasher(10, 10, state);
    /// map.insert("key", "value");
    /// assert_eq!(map.keys_capacity(), 10);
    /// assert_eq!(map.values_capacity(), 10);
    /// ```
    pub fn with_capacity_and_hasher(
        key_capacity: usize,
        value_capacity: usize,
        state: State,
    ) -> ListOrderedMultimap<Key, Value, State> {
        ListOrderedMultimap {
            build_hasher: state,
            keys: VecList::with_capacity(key_capacity),
            map: HashMap::with_capacity_and_hasher(key_capacity, DummyState),
            values: VecList::with_capacity(value_capacity),
        }
    }

    /// Creates a new multimap with no capacity which will use the given hash builder to hash keys.
    ///
    /// The `state` is normally randomly generated and is designed to allow multimaps to be
    /// resistant to attacks that cause many collisions and very poor performance. Setting it
    /// manually using this function can expose a DoS attack vector.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use std::collections::hash_map::RandomState;
    ///
    /// let state = RandomState::new();
    /// let mut map = ListOrderedMultimap::with_hasher(state);
    /// map.insert("key", "value");
    /// ```
    pub fn with_hasher(state: State) -> ListOrderedMultimap<Key, Value, State> {
        ListOrderedMultimap {
            build_hasher: state,
            keys: VecList::new(),
            map: HashMap::with_hasher(DummyState),
            values: VecList::new(),
        }
    }
}

impl<Key, Value, State> Debug for ListOrderedMultimap<Key, Value, State>
where
    Key: Debug + Eq + Hash,
    Value: Debug,
    State: BuildHasher,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.debug_map().entries(self.iter()).finish()
    }
}

impl<Key, Value> Default for ListOrderedMultimap<Key, Value, RandomState>
where
    Key: Eq + Hash,
{
    fn default() -> Self {
        ListOrderedMultimap {
            build_hasher: RandomState::new(),
            keys: VecList::new(),
            map: HashMap::with_hasher(DummyState),
            values: VecList::new(),
        }
    }
}

impl<Key, Value, State> Eq for ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    Value: PartialEq,
    State: BuildHasher,
{
}

impl<Key, Value, State> Extend<(Key, Value)> for ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    fn extend<Iter>(&mut self, iter: Iter)
    where
        Iter: IntoIterator<Item = (Key, Value)>,
    {
        let iter = iter.into_iter();
        self.reserve_values(iter.size_hint().0);

        for (key, value) in iter {
            self.append(key, value);
        }
    }
}

impl<'a, Key, Value, State> Extend<(&'a Key, &'a Value)> for ListOrderedMultimap<Key, Value, State>
where
    Key: Copy + Eq + Hash,
    Value: Copy,
    State: BuildHasher,
{
    fn extend<Iter>(&mut self, iter: Iter)
    where
        Iter: IntoIterator<Item = (&'a Key, &'a Value)>,
    {
        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
    }
}

impl<Key, Value, State> FromIterator<(Key, Value)> for ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher + Default,
{
    fn from_iter<Iter>(iter: Iter) -> Self
    where
        Iter: IntoIterator<Item = (Key, Value)>,
    {
        let mut map = ListOrderedMultimap::with_hasher(State::default());
        map.extend(iter);
        map
    }
}

impl<Key, Value, State> IntoIterator for ListOrderedMultimap<Key, Value, State>
where
    Key: Clone + Eq + Hash,
    State: BuildHasher,
{
    type IntoIter = IntoIter<Key, Value>;
    type Item = (Key, Value);

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

impl<'map, Key, Value, State> IntoIterator for &'map ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    type IntoIter = Iter<'map, Key, Value>;
    type Item = (&'map Key, &'map Value);

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

impl<'map, Key, Value, State> IntoIterator for &'map mut ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    type IntoIter = IterMut<'map, Key, Value>;
    type Item = (&'map Key, &'map mut Value);

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

impl<Key, Value, State> PartialEq for ListOrderedMultimap<Key, Value, State>
where
    Key: Eq + Hash,
    Value: PartialEq,
    State: BuildHasher,
{
    fn eq(&self, other: &ListOrderedMultimap<Key, Value, State>) -> bool {
        if self.keys_len() != other.keys_len() || self.values_len() != other.values_len() {
            return false;
        }

        self.iter().eq(other.iter())
    }
}

/// A wrapper around a key that is either borrowed or owned.
///
/// This type is similar to [`std::borrow::Cow`] but does not require a [`Clone`] trait bound on the
/// key.
#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
pub enum KeyWrapper<'map, Key> {
    /// An immutable reference to a key. This implies that the key is still associated to at least
    /// one value in the multimap.
    Borrowed(&'map Key),

    /// An owned key. This will occur when a key is no longer associated with any values in the
    /// multimap.
    Owned(Key),
}

impl<'map, Key> KeyWrapper<'map, Key> {
    /// If the key wrapped is owned, it is returned. Otherwise, the borrowed key is cloned and
    /// returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::list_ordered_multimap::KeyWrapper;
    ///
    /// let borrowed = KeyWrapper::Borrowed(&0);
    /// assert_eq!(borrowed.into_owned(), 0);
    ///
    /// let owned = KeyWrapper::Owned(0);
    /// assert_eq!(borrowed.into_owned(), 0);
    /// ```
    pub fn into_owned(self) -> Key
    where
        Key: Clone,
    {
        use self::KeyWrapper::*;

        match self {
            Borrowed(key) => key.clone(),
            Owned(key) => key,
        }
    }

    /// Returns whether the wrapped key is borrowed.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::list_ordered_multimap::KeyWrapper;
    ///
    /// let borrowed = KeyWrapper::Borrowed(&0);
    /// assert!(borrowed.is_borrowed());
    ///
    /// let owned = KeyWrapper::Owned(0);
    /// assert!(!owned.is_borrowed());
    /// ```
    pub fn is_borrowed(&self) -> bool {
        match self {
            KeyWrapper::Borrowed(_) => true,
            _ => false,
        }
    }

    /// Returns whether the wrapped key is owned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::list_ordered_multimap::KeyWrapper;
    ///
    /// let borrowed = KeyWrapper::Borrowed(&0);
    /// assert!(!borrowed.is_owned());
    ///
    /// let owned = KeyWrapper::Owned(0);
    /// assert!(owned.is_owned());
    /// ```
    pub fn is_owned(&self) -> bool {
        match self {
            KeyWrapper::Owned(_) => true,
            _ => false,
        }
    }
}

/// The value type of the internal hash map.
#[derive(Clone)]
struct MapEntry<Key, Value> {
    /// The index of the first value for this entry.
    head_index: Index<ValueEntry<Key, Value>>,

    /// The number of values for this entry.
    length: usize,

    /// The index of the last value for this entry.
    tail_index: Index<ValueEntry<Key, Value>>,
}

impl<Key, Value> MapEntry<Key, Value> {
    /// Convenience function for adding a new value to the entry.
    pub fn append(&mut self, index: Index<ValueEntry<Key, Value>>) {
        self.length += 1;
        self.tail_index = index;
    }

    /// Convenience function for creating a new multimap entry.
    pub fn new(index: Index<ValueEntry<Key, Value>>) -> Self {
        MapEntry {
            head_index: index,
            length: 1,
            tail_index: index,
        }
    }

    /// Convenience function for resetting the entry to contain only one value.
    pub fn reset(&mut self, index: Index<ValueEntry<Key, Value>>) {
        self.head_index = index;
        self.length = 1;
        self.tail_index = index;
    }
}

/// The value entry that is contained within the internal values list.
#[derive(Clone)]
struct ValueEntry<Key, Value> {
    /// The index of the key in the key list for this entry.
    key_index: Index<Key>,

    /// The index of the next value with the same key.
    next_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The index of the previous value with the same key.
    previous_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The actual value stored in this entry.
    value: Value,
}

impl<Key, Value> ValueEntry<Key, Value> {
    /// Convenience function for creating a new value entry.
    pub fn new(key_index: Index<Key>, value: Value) -> Self {
        ValueEntry {
            key_index,
            next_index: None,
            previous_index: None,
            value,
        }
    }
}

/// A view into a single entry in the multimap, which may either be vacant or occupied.
pub enum Entry<'map, Key, Value, State = RandomState> {
    /// An occupied entry associated with one or more values.
    Occupied(OccupiedEntry<'map, Key, Value>),

    /// A vacant entry with no associated values.
    Vacant(VacantEntry<'map, Key, Value, State>),
}

impl<'map, Key, Value, State> Entry<'map, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    /// Calls the given function with a mutable reference to the first value of this entry, by
    /// insertion order, if it is vacant, otherwise this function is a no-op.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// map.entry("key")
    ///     .and_modify(|value| *value += 1)
    ///     .or_insert(42);
    /// assert_eq!(map.get(&"key"), Some(&42));
    ///
    /// map.entry("key")
    ///     .and_modify(|value| *value += 1)
    ///     .or_insert(42);
    /// assert_eq!(map.get(&"key"), Some(&43));
    /// ```
    pub fn and_modify<Function>(self, function: Function) -> Self
    where
        Function: FnOnce(&mut Value),
    {
        use self::Entry::*;

        match self {
            Occupied(mut entry) => {
                function(entry.get_mut());
                Occupied(entry)
            }
            Vacant(entry) => Vacant(entry),
        }
    }

    /// If the entry is vacant, the given value will be inserted into it and a mutable reference to
    /// that value will be returned. Otherwise, a mutable reference to the first value, by insertion
    /// order, will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let value = map.entry("key").or_insert("value2");
    /// assert_eq!(value, &"value1");
    ///
    /// let value = map.entry("key2").or_insert("value2");
    /// assert_eq!(value, &"value2");
    /// ```
    pub fn or_insert(self, value: Value) -> &'map mut Value {
        use self::Entry::*;

        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(value),
        }
    }

    /// If the entry is vacant, the given value will be inserted into it and the new occupied entry
    /// will be returned. Otherwise, the existing occupied entry will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let entry = map.entry("key").or_insert_entry("value2");
    /// assert_eq!(entry.into_mut(), &"value1");
    ///
    /// let entry = map.entry("key2").or_insert_entry("value2");
    /// assert_eq!(entry.into_mut(), &"value2");
    /// ```
    pub fn or_insert_entry(self, value: Value) -> OccupiedEntry<'map, Key, Value> {
        use self::Entry::*;

        match self {
            Occupied(entry) => entry,
            Vacant(entry) => entry.insert_entry(value),
        }
    }

    /// If the entry is vacant, the value returned from the given function will be inserted into it
    /// and a mutable reference to that value will be returned. Otherwise, a mutable reference to
    /// the first value, by insertion order, will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let value = map.entry("key").or_insert_with(|| "value2");
    /// assert_eq!(value, &"value1");
    ///
    /// let value = map.entry("key2").or_insert_with(|| "value2");
    /// assert_eq!(value, &"value2");
    /// ```
    pub fn or_insert_with<Function>(self, function: Function) -> &'map mut Value
    where
        Function: FnOnce() -> Value,
    {
        use self::Entry::*;

        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(function()),
        }
    }

    /// If the entry is vacant, the value returned from the given function will be inserted into it
    /// and the new occupied entry will be returned. Otherwise, the existing occupied entry will be
    /// returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let entry = map.entry("key").or_insert_with_entry(|| "value2");
    /// assert_eq!(entry.into_mut(), &"value1");
    ///
    /// let entry = map.entry("key2").or_insert_with_entry(|| "value2");
    /// assert_eq!(entry.into_mut(), &"value2");
    /// ```
    pub fn or_insert_with_entry<Function>(
        self,
        function: Function,
    ) -> OccupiedEntry<'map, Key, Value>
    where
        Function: FnOnce() -> Value,
    {
        use self::Entry::*;

        match self {
            Occupied(entry) => entry,
            Vacant(entry) => entry.insert_entry(function()),
        }
    }
}

impl<'map, Key, Value, State> Debug for Entry<'map, Key, Value, State>
where
    Key: Debug,
    State: BuildHasher,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        use self::Entry::*;

        match self {
            Occupied(entry) => entry.fmt(formatter),
            Vacant(entry) => entry.fmt(formatter),
        }
    }
}

/// A view into an occupied entry in the multimap.
pub struct OccupiedEntry<'map, Key, Value> {
    entry: RawOccupiedEntryMut<'map, Index<Key>, MapEntry<Key, Value>, DummyState>,

    keys: &'map mut VecList<Key>,

    values: &'map mut VecList<ValueEntry<Key, Value>>,
}

#[allow(clippy::len_without_is_empty)]
impl<'map, Key, Value> OccupiedEntry<'map, Key, Value> {
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let mut iter = map.get_all(&"key");
    /// assert_eq!(iter.next(), Some(&"value1"));
    /// assert_eq!(iter.next(), Some(&"value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn append(&mut self, value: Value) {
        let key_index = *self.entry.key();
        let map_entry = self.entry.get_mut();
        let mut value_entry = ValueEntry::new(key_index, value);
        value_entry.previous_index = Some(map_entry.tail_index);
        let index = self.values.push_back(value_entry);
        self.values
            .get_mut(map_entry.tail_index)
            .unwrap()
            .next_index = Some(index);
        map_entry.length += 1;
        map_entry.tail_index = index;
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.get(), &"value");
    /// ```
    pub fn get(&self) -> &Value {
        let index = self.entry.get().head_index;
        &self.values.get(index).unwrap().value
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.get(), &mut "value");
    /// ```
    pub fn get_mut(&mut self) -> &mut Value {
        let index = self.entry.get().head_index;
        &mut self.values.get_mut(index).unwrap().value
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.insert("value2");
    ///
    /// assert_eq!(map.get(&"key"), Some(&"value2"));
    /// ```
    pub fn insert(&mut self, value: Value) -> Value {
        let key_index = *self.entry.key();
        let map_entry = self.entry.get_mut();
        let first_index = map_entry.head_index;
        let mut entry = self.values.remove(first_index).unwrap();
        let first_value = entry.value;

        while let Some(next_index) = entry.next_index {
            entry = self.values.remove(next_index).unwrap();
        }

        let value_entry = ValueEntry::new(key_index, value);
        let index = self.values.push_back(value_entry);
        map_entry.head_index = index;
        map_entry.length = 1;
        map_entry.tail_index = index;
        first_value
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let mut iter = entry.insert_all("value3");
    /// assert_eq!(iter.next(), Some("value1"));
    /// assert_eq!(iter.next(), Some("value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn insert_all(&mut self, value: Value) -> EntryValuesDrain<Key, Value> {
        let key_index = *self.entry.key();
        let map_entry = self.entry.get_mut();
        let value_entry = ValueEntry::new(key_index, value);
        let index = self.values.push_back(value_entry);
        let iter = EntryValuesDrain::from_map_entry(&mut self.values, &map_entry);
        map_entry.reset(index);
        iter
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.into_mut(), &mut "value");
    /// ```
    pub fn into_mut(mut self) -> &'map mut Value {
        let index = self.entry.get_mut().head_index;
        &mut self.values.get_mut(index).unwrap().value
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let mut iter = entry.iter();
    /// assert_eq!(iter.next(), Some(&"value1"));
    /// assert_eq!(iter.next(), Some(&"value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&self) -> EntryValues<Key, Value> {
        let map_entry = self.entry.get();
        EntryValues::from_map_entry(&self.values, &map_entry)
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let mut iter = entry.iter_mut();
    /// assert_eq!(iter.next(), Some(&mut "value1"));
    /// assert_eq!(iter.next(), Some(&mut "value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter_mut(&mut self) -> EntryValuesMut<Key, Value> {
        let map_entry = self.entry.get_mut();
        EntryValuesMut::from_map_entry(&mut self.values, &map_entry)
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.key(), &"key");
    /// ```
    pub fn key(&self) -> &Key {
        let key_index = self.entry.key();
        self.keys.get(*key_index).unwrap()
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.len(), 1);
    ///
    /// entry.append("value2");
    /// assert_eq!(entry.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.entry.get().length
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.remove(), "value");
    /// ```
    pub fn remove(self) -> Value {
        self.remove_entry().1
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let mut iter = entry.remove_all();
    /// assert_eq!(iter.next(), Some("value1"));
    /// assert_eq!(iter.next(), Some("value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn remove_all(self) -> EntryValuesDrain<'map, Key, Value> {
        self.remove_entry_all().1
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// assert_eq!(entry.remove_entry(), ("key", "value"));
    /// ```
    pub fn remove_entry(self) -> (Key, Value) {
        let (key_index, map_entry) = self.entry.remove_entry();
        let key = self.keys.remove(key_index).unwrap();
        let first_index = map_entry.head_index;
        let mut entry = self.values.remove(first_index).unwrap();
        let first_value = entry.value;

        while let Some(next_index) = entry.next_index {
            entry = self.values.remove(next_index).unwrap();
        }

        (key, first_value)
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    /// map.insert("key", "value1");
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Occupied(entry) => entry,
    ///     _ => panic!("expected occupied entry")
    /// };
    ///
    /// entry.append("value2");
    ///
    /// let (key, mut iter) = entry.remove_entry_all();
    /// assert_eq!(key, "key");
    /// assert_eq!(iter.next(), Some("value1"));
    /// assert_eq!(iter.next(), Some("value2"));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn remove_entry_all(self) -> (Key, EntryValuesDrain<'map, Key, Value>) {
        let (key_index, map_entry) = self.entry.remove_entry();
        let key = self.keys.remove(key_index).unwrap();
        let iter = EntryValuesDrain {
            head_index: Some(map_entry.head_index),
            remaining: map_entry.length,
            tail_index: Some(map_entry.tail_index),
            values: self.values,
        };
        (key, iter)
    }
}

impl<Key, Value> Debug for OccupiedEntry<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter
            .debug_struct("OccupiedEntry")
            .field("key", self.key())
            .field("values", &self.iter())
            .finish()
    }
}

/// A view into a vacant entry in the multimap.
pub struct VacantEntry<'map, Key, Value, State = RandomState> {
    /// The builder hasher for the map, kept separately for mutability concerns.
    build_hasher: &'map State,

    /// The hash of the key for the entry.
    hash: u64,

    /// The key for this entry for when it is to be inserted into the map.
    key: Key,

    keys: &'map mut VecList<Key>,

    /// Reference to the multimap.
    map: &'map mut HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,

    values: &'map mut VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value, State> VacantEntry<'map, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Vacant(entry) => entry,
    ///     _ => panic!("expected vacant entry")
    /// };
    ///
    /// assert_eq!(entry.insert("value"), &"value");
    /// ```
    pub fn insert(self, value: Value) -> &'map mut Value {
        let build_hasher = self.build_hasher;
        let entry = match raw_entry_mut(self.keys, self.map, self.hash, &self.key) {
            RawEntryMut::Vacant(entry) => entry,
            _ => panic!("expected vacant entry"),
        };
        let key_index = self.keys.push_back(self.key);
        let value_entry = ValueEntry::new(key_index, value);
        let index = self.values.push_back(value_entry);
        let map_entry = MapEntry::new(index);
        let keys = &self.keys;
        entry.insert_with_hasher(self.hash, key_index, map_entry, |&key_index| {
            let key = keys.get(key_index).unwrap();
            hash_key(build_hasher, key)
        });

        &mut self.values.get_mut(index).unwrap().value
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map = ListOrderedMultimap::new();
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Vacant(entry) => entry,
    ///     _ => panic!("expected vacant entry")
    /// };
    ///
    /// let mut entry = entry.insert_entry("value");
    /// assert_eq!(entry.get(), &"value");
    /// ```
    pub fn insert_entry(self, value: Value) -> OccupiedEntry<'map, Key, Value> {
        let build_hasher = self.build_hasher;
        let entry = match raw_entry_mut(self.keys, self.map, self.hash, &self.key) {
            RawEntryMut::Vacant(entry) => entry,
            _ => panic!("expected vacant entry"),
        };
        let key_index = self.keys.push_back(self.key);
        let value_entry = ValueEntry::new(key_index, value);
        let index = self.values.push_back(value_entry);
        let map_entry = MapEntry::new(index);
        let keys = &self.keys;
        entry.insert_with_hasher(self.hash, key_index, map_entry, |&key_index| {
            let key = keys.get(key_index).unwrap();
            hash_key(build_hasher, key)
        });

        let key = self.keys.get(key_index).unwrap();
        let entry = match raw_entry_mut(self.keys, self.map, self.hash, key) {
            RawEntryMut::Occupied(entry) => entry,
            _ => panic!("expected occupied entry"),
        };

        OccupiedEntry {
            entry,
            keys: self.keys,
            values: self.values,
        }
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Vacant(entry) => entry,
    ///     _ => panic!("expected vacant entry")
    /// };
    ///
    /// assert_eq!(entry.into_key(), "key");
    /// ```
    pub fn into_key(self) -> Key {
        self.key
    }

    /// # Examples
    ///
    /// ```
    /// use ordered_multimap::ListOrderedMultimap;
    /// use ordered_multimap::list_ordered_multimap::Entry;
    ///
    /// let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
    ///
    /// let mut entry = match map.entry("key") {
    ///     Entry::Vacant(entry) => entry,
    ///     _ => panic!("expected vacant entry")
    /// };
    ///
    /// assert_eq!(entry.key(), &"key");
    /// ```
    pub fn key(&self) -> &Key {
        &self.key
    }
}

impl<Key, Value, State> Debug for VacantEntry<'_, Key, Value, State>
where
    Key: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter
            .debug_tuple("VacantEntry")
            .field(&self.key)
            .finish()
    }
}

/// An iterator that yields immutable references to all values of a given key. The order of the
/// values is always in the order that they were inserted.
pub struct EntryValues<'map, Key, Value> {
    /// The first index of the values not yet yielded.
    head_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The remaining number of values to be yielded.
    remaining: usize,

    /// The last index of the values not yet yielded.
    tail_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: &'map VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value> EntryValues<'map, Key, Value> {
    /// Convenience function for creating an empty iterator.
    fn empty(values: &'map VecList<ValueEntry<Key, Value>>) -> Self {
        EntryValues {
            head_index: None,
            remaining: 0,
            tail_index: None,
            values,
        }
    }

    /// Convenience function for creating a new iterator from a map entry.
    fn from_map_entry(
        values: &'map VecList<ValueEntry<Key, Value>>,
        map_entry: &MapEntry<Key, Value>,
    ) -> Self {
        EntryValues {
            head_index: Some(map_entry.head_index),
            remaining: map_entry.length,
            tail_index: Some(map_entry.tail_index),
            values,
        }
    }
}

impl<'map, Key, Value> Clone for EntryValues<'map, Key, Value> {
    fn clone(&self) -> EntryValues<'map, Key, Value> {
        EntryValues {
            head_index: self.head_index,
            remaining: self.remaining,
            tail_index: self.tail_index,
            values: self.values,
        }
    }
}

impl<Key, Value> Debug for EntryValues<'_, Key, Value>
where
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("EntryValues(")?;
        formatter.debug_list().entries(self.clone()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for EntryValues<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.tail_index.map(|index| {
                let entry = self.values.get(index).unwrap();
                self.tail_index = entry.previous_index;
                self.remaining -= 1;
                &entry.value
            })
        }
    }
}

impl<Key, Value> ExactSizeIterator for EntryValues<'_, Key, Value> {}

impl<Key, Value> FusedIterator for EntryValues<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for EntryValues<'map, Key, Value> {
    type Item = &'map Value;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.head_index.map(|index| {
                let entry = self.values.get(index).unwrap();
                self.head_index = entry.next_index;
                self.remaining -= 1;
                &entry.value
            })
        }
    }

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

/// An iterator that moves all values of a given key out of a multimap but preserves the underlying
/// capacity. The order of the values is always in the order that they were inserted.
pub struct EntryValuesDrain<'map, Key, Value> {
    /// The first index of the values not yet yielded.
    head_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The remaining number of values to be yielded.
    remaining: usize,

    /// The last index of the values not yet yielded.
    tail_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: &'map mut VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value> EntryValuesDrain<'map, Key, Value> {
    /// Convenience function for creating an empty iterator.
    fn empty(values: &'map mut VecList<ValueEntry<Key, Value>>) -> Self {
        EntryValuesDrain {
            head_index: None,
            remaining: 0,
            tail_index: None,
            values,
        }
    }

    /// Convenience function for creating a new iterator from a map entry.
    fn from_map_entry(
        values: &'map mut VecList<ValueEntry<Key, Value>>,
        map_entry: &MapEntry<Key, Value>,
    ) -> Self {
        EntryValuesDrain {
            head_index: Some(map_entry.head_index),
            remaining: map_entry.length,
            tail_index: Some(map_entry.tail_index),
            values,
        }
    }

    /// Creates an iterator that yields immutable references to all values of a given key.
    pub fn iter(&self) -> EntryValues<Key, Value> {
        EntryValues {
            head_index: self.head_index,
            remaining: self.remaining,
            tail_index: self.tail_index,
            values: self.values,
        }
    }
}

impl<Key, Value> Debug for EntryValuesDrain<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("EntryValuesDrain(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for EntryValuesDrain<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.tail_index.map(|index| {
                let entry = self.values.remove(index).unwrap();
                self.tail_index = entry.previous_index;
                self.remaining -= 1;
                entry.value
            })
        }
    }
}

impl<Key, Value> Drop for EntryValuesDrain<'_, Key, Value> {
    fn drop(&mut self) {
        for _ in self {}
    }
}

impl<Key, Value> ExactSizeIterator for EntryValuesDrain<'_, Key, Value> {}

impl<Key, Value> FusedIterator for EntryValuesDrain<'_, Key, Value> {}

impl<Key, Value> Iterator for EntryValuesDrain<'_, Key, Value> {
    type Item = Value;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.head_index.map(|index| {
                let entry = self.values.remove(index).unwrap();
                self.head_index = entry.next_index;
                self.remaining -= 1;
                entry.value
            })
        }
    }

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

/// An iterator that yields mutable references to all values of a given key. The order of the values
/// is always in the order that they were inserted.
pub struct EntryValuesMut<'map, Key, Value> {
    /// The first index of the values not yet yielded.
    head_index: Option<Index<ValueEntry<Key, Value>>>,

    /// Because [`EntryValuesMut::values`] is a pointer, we need to have a phantom data here for the
    /// lifetime parameter.
    phantom: PhantomData<&'map mut VecList<ValueEntry<Key, Value>>>,

    /// The remaining number of values to be yielded.
    remaining: usize,

    /// The last index of the values not yet yielded.
    tail_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: *mut VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value> EntryValuesMut<'map, Key, Value> {
    /// Convenience function for creating an empty iterator.
    fn empty(values: &'map mut VecList<ValueEntry<Key, Value>>) -> Self {
        EntryValuesMut {
            head_index: None,
            phantom: PhantomData,
            remaining: 0,
            tail_index: None,
            values: values as *mut _,
        }
    }

    /// Convenience function for creating a new iterator from a map entry.
    fn from_map_entry(
        values: &'map mut VecList<ValueEntry<Key, Value>>,
        map_entry: &MapEntry<Key, Value>,
    ) -> Self {
        EntryValuesMut {
            head_index: Some(map_entry.head_index),
            phantom: PhantomData,
            remaining: map_entry.length,
            tail_index: Some(map_entry.tail_index),
            values: values as *mut _,
        }
    }

    /// Creates an iterator that yields immutable references to all values of a given key.
    pub fn iter(&self) -> EntryValues<Key, Value> {
        EntryValues {
            head_index: self.head_index,
            remaining: self.remaining,
            tail_index: self.tail_index,
            values: unsafe { &*self.values },
        }
    }
}

impl<Key, Value> Debug for EntryValuesMut<'_, Key, Value>
where
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("EntryValuesMut(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for EntryValuesMut<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.tail_index.map(|index| {
                let entry = unsafe { (*self.values).get_mut(index) }.unwrap();
                self.tail_index = entry.previous_index;
                self.remaining -= 1;
                &mut entry.value
            })
        }
    }
}

impl<Key, Value> ExactSizeIterator for EntryValuesMut<'_, Key, Value> {}

impl<Key, Value> FusedIterator for EntryValuesMut<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for EntryValuesMut<'map, Key, Value> {
    type Item = &'map mut Value;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.head_index.map(|index| {
                let entry = unsafe { (*self.values).get_mut(index) }.unwrap();
                self.head_index = entry.next_index;
                self.remaining -= 1;
                &mut entry.value
            })
        }
    }

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

unsafe impl<Key, Value> Send for EntryValuesMut<'_, Key, Value>
where
    Key: Send,
    Value: Send,
{
}

unsafe impl<Key, Value> Sync for EntryValuesMut<'_, Key, Value>
where
    Key: Sync,
    Value: Sync,
{
}

/// An iterator that owns and yields all key-value pairs in a multimap by cloning the keys for their
/// possibly multiple values. This is unnecessarily expensive whenever [`Iter`] or [`IterMut`] would
/// suit as well. The order of the yielded items is always in the order that they were inserted.
pub struct IntoIter<Key, Value> {
    // The list of the keys in the map. This is ordered by time of insertion.
    keys: VecList<Key>,

    /// The iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListIntoIter<ValueEntry<Key, Value>>,
}

impl<Key, Value> IntoIter<Key, Value> {
    /// Creates an iterator that yields immutable references to all key-value pairs in a multimap.
    pub fn iter(&self) -> Iter<Key, Value> {
        Iter {
            keys: &self.keys,
            iter: self.iter.iter(),
        }
    }
}

impl<Key, Value> Debug for IntoIter<Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("IntoIter(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for IntoIter<Key, Value>
where
    Key: Clone,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next_back()?;
        let key = self.keys.get(value_entry.key_index).cloned().unwrap();
        Some((key, value_entry.value))
    }
}

impl<Key, Value> ExactSizeIterator for IntoIter<Key, Value> where Key: Clone {}

impl<Key, Value> FusedIterator for IntoIter<Key, Value> where Key: Clone {}

impl<Key, Value> Iterator for IntoIter<Key, Value>
where
    Key: Clone,
{
    type Item = (Key, Value);

    fn next(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next()?;
        let key = self.keys.get(value_entry.key_index).cloned().unwrap();
        Some((key, value_entry.value))
    }

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

/// An iterator that yields immutable references to all key-value pairs in a multimap. The order of
/// the yielded items is always in the order that they were inserted.
pub struct Iter<'map, Key, Value> {
    // The list of the keys in the map. This is ordered by time of insertion.
    keys: &'map VecList<Key>,

    /// The iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListIter<'map, ValueEntry<Key, Value>>,
}

impl<'map, Key, Value> Clone for Iter<'map, Key, Value> {
    fn clone(&self) -> Iter<'map, Key, Value> {
        Iter {
            keys: self.keys,
            iter: self.iter.clone(),
        }
    }
}

impl<Key, Value> Debug for Iter<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("Iter(")?;
        formatter.debug_list().entries(self.clone()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for Iter<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next_back()?;
        let key = self.keys.get(value_entry.key_index).unwrap();
        Some((key, &value_entry.value))
    }
}

impl<Key, Value> ExactSizeIterator for Iter<'_, Key, Value> {}

impl<Key, Value> FusedIterator for Iter<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for Iter<'map, Key, Value> {
    type Item = (&'map Key, &'map Value);

    fn next(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next()?;
        let key = self.keys.get(value_entry.key_index).unwrap();
        Some((key, &value_entry.value))
    }

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

/// An iterator that yields mutable references to all key-value pairs in a multimap. The order of
/// the yielded items is always in the order that they were inserted.
pub struct IterMut<'map, Key, Value> {
    // The list of the keys in the map. This is ordered by time of insertion.
    keys: &'map VecList<Key>,

    /// The iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListIterMut<'map, ValueEntry<Key, Value>>,
}

impl<Key, Value> IterMut<'_, Key, Value> {
    /// Creates an iterator that yields immutable references to all key-value pairs in a multimap.
    pub fn iter(&self) -> Iter<Key, Value> {
        Iter {
            keys: self.keys,
            iter: self.iter.iter(),
        }
    }
}

impl<Key, Value> Debug for IterMut<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("IterMut(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for IterMut<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next_back()?;
        let key = self.keys.get(value_entry.key_index).unwrap();
        Some((key, &mut value_entry.value))
    }
}

impl<Key, Value> ExactSizeIterator for IterMut<'_, Key, Value> {}

impl<Key, Value> FusedIterator for IterMut<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for IterMut<'map, Key, Value> {
    type Item = (&'map Key, &'map mut Value);

    fn next(&mut self) -> Option<Self::Item> {
        let value_entry = self.iter.next()?;
        let key = self.keys.get(value_entry.key_index).unwrap();
        Some((key, &mut value_entry.value))
    }

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

/// An iterator that yields immutable references to all keys and their value iterators. The order of
/// the yielded items is always in the order the keys were first inserted.
pub struct KeyValues<'map, Key, Value, State = RandomState> {
    /// The builder hasher for the map, kept separately for mutability concerns.
    build_hasher: &'map State,

    // The list of the keys in the map. This is ordered by time of insertion.
    keys: &'map VecList<Key>,

    /// The iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListIter<'map, Key>,

    /// The internal mapping from key hashes to associated value indices.
    map: &'map HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: &'map VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value, State> Clone for KeyValues<'map, Key, Value, State> {
    fn clone(&self) -> KeyValues<'map, Key, Value, State> {
        KeyValues {
            build_hasher: self.build_hasher,
            keys: self.keys,
            iter: self.iter.clone(),
            map: self.map,
            values: self.values,
        }
    }
}

impl<Key, Value, State> Debug for KeyValues<'_, Key, Value, State>
where
    Key: Debug + Eq + Hash,
    State: BuildHasher,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("KeyValues(")?;
        formatter.debug_list().entries(self.clone()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value, State> DoubleEndedIterator for KeyValues<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        let key = self.iter.next_back()?;
        let hash = hash_key(self.build_hasher, key);
        let (_, map_entry) = raw_entry(&self.keys, self.map, hash, key).unwrap();
        let iter = EntryValues::from_map_entry(&self.values, &map_entry);
        Some((key, iter))
    }
}

impl<Key, Value, State> ExactSizeIterator for KeyValues<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<Key, Value, State> FusedIterator for KeyValues<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<'map, Key, Value, State> Iterator for KeyValues<'map, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    type Item = (&'map Key, EntryValues<'map, Key, Value>);

    fn next(&mut self) -> Option<Self::Item> {
        let key = self.iter.next()?;
        let hash = hash_key(self.build_hasher, key);
        let (_, map_entry) = raw_entry(&self.keys, self.map, hash, key).unwrap();
        let iter = EntryValues::from_map_entry(&self.values, &map_entry);
        Some((key, iter))
    }

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

/// An iterator that drains the multimap of all keys and their value drain iterators. The order of
/// the yielded items is always in the order the keys were first inserted.
pub struct KeyValuesDrain<'map, Key, Value, State = RandomState>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    /// The builder hasher for the map, kept separately for mutability concerns.
    build_hasher: &'map State,

    /// The number of keys whose value drain iterators have yet to have been fully consumed. This is
    /// needed to make this type thread-safe.
    dropped: Arc<AtomicUsize>,

    /// The drain iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListDrain<'map, Key>,

    // The list of the keys in the map. This is ordered by time of insertion.
    keys: *const VecList<Key>,

    /// The internal mapping from key hashes to associated value indices.
    map: &'map mut HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: *mut VecList<ValueEntry<Key, Value>>,
}

impl<Key, Value, State> KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    /// Creates an iterator that yields immutable references to all keys and their value iterators.
    pub fn iter(&self) -> KeyValues<Key, Value, State> {
        KeyValues {
            build_hasher: self.build_hasher,
            keys: unsafe { &*self.keys },
            iter: self.iter.iter(),
            map: self.map,
            values: unsafe { &*self.values },
        }
    }
}

impl<Key, Value, State> Debug for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Debug + Eq + Hash,
    State: BuildHasher,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("KeyValuesDrain(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value, State> DoubleEndedIterator for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        let key = self.iter.next_back()?;
        let hash = hash_key(self.build_hasher, &key);
        let entry = match raw_entry_mut_empty(unsafe { &*self.keys }, self.map, hash) {
            RawEntryMut::Occupied(entry) => entry,
            _ => panic!("expected occupied entry in internal map"),
        };
        let map_entry = entry.remove();
        let iter = KeyValuesEntryDrain::from_map_entry(
            unsafe { &mut *self.values },
            &map_entry,
            self.dropped.clone(),
        );
        Some((key, iter))
    }
}

impl<Key, Value, State> Drop for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    fn drop(&mut self) {
        for _ in self {}
    }
}

impl<Key, Value, State> ExactSizeIterator for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<Key, Value, State> FusedIterator for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<'map, Key, Value, State> Iterator for KeyValuesDrain<'map, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    type Item = (Key, KeyValuesEntryDrain<'map, Key, Value>);

    fn next(&mut self) -> Option<Self::Item> {
        let key = self.iter.next()?;
        let hash = hash_key(self.build_hasher, &key);
        let entry = match raw_entry_mut_empty(unsafe { &*self.keys }, self.map, hash) {
            RawEntryMut::Occupied(entry) => entry,
            _ => panic!("expected occupied entry in internal map"),
        };
        let map_entry = entry.remove();
        let iter = KeyValuesEntryDrain::from_map_entry(
            unsafe { &mut *self.values },
            &map_entry,
            self.dropped.clone(),
        );
        Some((key, iter))
    }

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

unsafe impl<Key, Value, State> Send for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash + Send,
    State: BuildHasher,
    Value: Send,
{
}

unsafe impl<Key, Value, State> Sync for KeyValuesDrain<'_, Key, Value, State>
where
    Key: Eq + Hash + Sync,
    State: BuildHasher,
    Value: Sync,
{
}

/// An iterator that drains all values for a given key. The order of the yielded items is always in
/// the order the values were first inserted.
///
/// This is only used with [`KeyValuesDrain`] to account for thread saftey.
pub struct KeyValuesEntryDrain<'map, Key, Value> {
    /// The number of keys whose value drain iterators have yet to have been fully consumed. This is
    /// needed to make this type thread-safe. This originates from [`KeyValuesDrain`].
    dropped: Arc<AtomicUsize>,

    /// The first index of the values not yet yielded.
    head_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The remaining number of values to be yielded.
    remaining: usize,

    /// The last index of the values not yet yielded.
    tail_index: Option<Index<ValueEntry<Key, Value>>>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: &'map mut VecList<ValueEntry<Key, Value>>,
}

impl<'map, Key, Value> KeyValuesEntryDrain<'map, Key, Value> {
    /// Convenience function for creating a new iterator from a map entry.
    fn from_map_entry(
        values: &'map mut VecList<ValueEntry<Key, Value>>,
        map_entry: &MapEntry<Key, Value>,
        dropped: Arc<AtomicUsize>,
    ) -> Self {
        KeyValuesEntryDrain {
            dropped,
            head_index: Some(map_entry.head_index),
            remaining: map_entry.length,
            tail_index: Some(map_entry.tail_index),
            values,
        }
    }

    /// Creates an iterator that yields immutable references to all values of a key.
    pub fn iter(&self) -> EntryValues<Key, Value> {
        EntryValues {
            head_index: self.head_index,
            remaining: self.remaining,
            tail_index: self.tail_index,
            values: self.values,
        }
    }
}

impl<Key, Value> Debug for KeyValuesEntryDrain<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("KeyValuesEntryDrain(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for KeyValuesEntryDrain<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.tail_index.map(|index| {
                let entry = unsafe { self.values.remove_sync(index) };
                self.tail_index = entry.previous_index;
                self.remaining -= 1;
                entry.value
            })
        }
    }
}

impl<Key, Value> Drop for KeyValuesEntryDrain<'_, Key, Value> {
    fn drop(&mut self) {
        while let Some(_) = self.next() {}

        let previous = self.dropped.fetch_sub(1, Ordering::SeqCst);

        if previous == 1 {
            self.values.clear()
        }
    }
}

impl<Key, Value> ExactSizeIterator for KeyValuesEntryDrain<'_, Key, Value> {}

impl<Key, Value> FusedIterator for KeyValuesEntryDrain<'_, Key, Value> {}

impl<Key, Value> Iterator for KeyValuesEntryDrain<'_, Key, Value> {
    type Item = Value;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining == 0 {
            None
        } else {
            self.head_index.map(|index| {
                let entry = unsafe { self.values.remove_sync(index) };
                self.head_index = entry.next_index;
                self.remaining -= 1;
                entry.value
            })
        }
    }

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

pub struct KeyValuesMut<'map, Key, Value, State = RandomState> {
    /// The builder hasher for the map, kept separately for mutability concerns.
    build_hasher: &'map State,

    // The list of the keys in the map. This is ordered by time of insertion.
    keys: &'map VecList<Key>,

    /// The iterator over the list of all values. This is ordered by time of insertion.
    iter: VecListIter<'map, Key>,

    /// The internal mapping from key hashes to associated value indices.
    map: &'map HashMap<Index<Key>, MapEntry<Key, Value>, DummyState>,

    /// The list of the values in the map. This is ordered by time of insertion.
    values: *mut VecList<ValueEntry<Key, Value>>,
}

impl<Key, Value, State> KeyValuesMut<'_, Key, Value, State> {
    /// Creates an iterator that yields mutable references to all key-value pairs of a multimap.
    pub fn iter(&self) -> KeyValues<Key, Value, State> {
        KeyValues {
            build_hasher: self.build_hasher,
            keys: self.keys,
            iter: self.iter.clone(),
            map: self.map,
            values: unsafe { &*self.values },
        }
    }
}

impl<Key, Value, State> Debug for KeyValuesMut<'_, Key, Value, State>
where
    Key: Debug + Eq + Hash,
    State: BuildHasher,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("KeyValuesMut(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value, State> DoubleEndedIterator for KeyValuesMut<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        let key = self.iter.next_back()?;
        let hash = hash_key(self.build_hasher, key);
        let (_, map_entry) = raw_entry(&self.keys, self.map, hash, key).unwrap();
        let iter = EntryValuesMut::from_map_entry(unsafe { &mut *self.values }, &map_entry);
        Some((key, iter))
    }
}

impl<Key, Value, State> ExactSizeIterator for KeyValuesMut<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<Key, Value, State> FusedIterator for KeyValuesMut<'_, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
}

impl<'map, Key, Value, State> Iterator for KeyValuesMut<'map, Key, Value, State>
where
    Key: Eq + Hash,
    State: BuildHasher,
{
    type Item = (&'map Key, EntryValuesMut<'map, Key, Value>);

    fn next(&mut self) -> Option<Self::Item> {
        let key = self.iter.next()?;
        let hash = hash_key(self.build_hasher, key);
        let (_, map_entry) = raw_entry(&self.keys, self.map, hash, key).unwrap();
        let iter = EntryValuesMut::from_map_entry(unsafe { &mut *self.values }, &map_entry);
        Some((key, iter))
    }

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

unsafe impl<Key, Value> Send for KeyValuesMut<'_, Key, Value>
where
    Key: Send,
    Value: Send,
{
}

unsafe impl<Key, Value> Sync for KeyValuesMut<'_, Key, Value>
where
    Key: Sync,
    Value: Sync,
{
}

/// An iterator that yields immutable references to all keys in the multimap. The order of the keys
/// is always in the order that they were first inserted.
pub struct Keys<'map, Key>(VecListIter<'map, Key>);

impl<'map, Key> Clone for Keys<'map, Key> {
    fn clone(&self) -> Keys<'map, Key> {
        Keys(self.0.clone())
    }
}

impl<Key> Debug for Keys<'_, Key>
where
    Key: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("Keys(")?;
        formatter.debug_list().entries(self.clone()).finish()?;
        formatter.write_str(")")
    }
}

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

impl<Key> ExactSizeIterator for Keys<'_, Key> {}

impl<Key> FusedIterator for Keys<'_, Key> {}

impl<'map, Key> Iterator for Keys<'map, Key> {
    type Item = &'map Key;

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

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

/// An iterator that yields immutable references to all values of a multimap. The order of the
/// values is always in the order that they were inserted.
pub struct Values<'map, Key, Value>(VecListIter<'map, ValueEntry<Key, Value>>);

impl<'map, Key, Value> Clone for Values<'map, Key, Value> {
    fn clone(&self) -> Values<'map, Key, Value> {
        Values(self.0.clone())
    }
}

impl<Key, Value> Debug for Values<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("Values(")?;
        formatter.debug_list().entries(self.clone()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for Values<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|entry| &entry.value)
    }
}

impl<Key, Value> ExactSizeIterator for Values<'_, Key, Value> {}

impl<Key, Value> FusedIterator for Values<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for Values<'map, Key, Value> {
    type Item = &'map Value;

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

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

/// An iterator that yields mutable references to all values of a multimap. The order of the values
/// is always in the order that they were inserted.
pub struct ValuesMut<'map, Key, Value>(VecListIterMut<'map, ValueEntry<Key, Value>>);

impl<Key, Value> ValuesMut<'_, Key, Value> {
    /// Creates an iterator that yields immutable references to all values of a multimap.
    pub fn iter(&self) -> Values<Key, Value> {
        Values(self.0.iter())
    }
}

impl<Key, Value> Debug for ValuesMut<'_, Key, Value>
where
    Key: Debug,
    Value: Debug,
{
    fn fmt(&self, formatter: &mut Formatter) -> fmt::Result {
        formatter.write_str("ValuesMut(")?;
        formatter.debug_list().entries(self.iter()).finish()?;
        formatter.write_str(")")
    }
}

impl<Key, Value> DoubleEndedIterator for ValuesMut<'_, Key, Value> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.0.next_back().map(|entry| &mut entry.value)
    }
}

impl<Key, Value> ExactSizeIterator for ValuesMut<'_, Key, Value> {}

impl<Key, Value> FusedIterator for ValuesMut<'_, Key, Value> {}

impl<'map, Key, Value> Iterator for ValuesMut<'map, Key, Value> {
    type Item = &'map mut Value;

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

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

/// Dummy builder hasher that is not meant to be used. It is simply a placeholder.
#[derive(Clone, Debug)]
struct DummyState;

impl BuildHasher for DummyState {
    type Hasher = DummyHasher;

    fn build_hasher(&self) -> Self::Hasher {
        DummyHasher
    }
}

/// Dummy hasher that is not meant to be used. It is simply a placeholder.
#[derive(Clone, Debug)]
struct DummyHasher;

impl Hasher for DummyHasher {
    fn finish(&self) -> u64 {
        unimplemented!();
    }

    fn write(&mut self, _: &[u8]) {
        unimplemented!();
    }
}

/// Computes the hash value of the given key.
fn hash_key<KeyQuery, State>(state: &State, key: &KeyQuery) -> u64
where
    KeyQuery: ?Sized + Eq + Hash,
    State: BuildHasher,
{
    let mut hasher = state.build_hasher();
    key.hash(&mut hasher);
    hasher.finish()
}

fn raw_entry<'map, Key, KeyQuery, Value, State>(
    keys: &VecList<Key>,
    map: &'map HashMap<Index<Key>, MapEntry<Key, Value>, State>,
    hash: u64,
    key: &KeyQuery,
) -> Option<(&'map Index<Key>, &'map MapEntry<Key, Value>)>
where
    Key: Borrow<KeyQuery> + Eq + Hash,
    KeyQuery: ?Sized + Eq + Hash,
    State: BuildHasher,
{
    // TODO(https://github.com/rust-lang/rust/issues/56158): Avoids segmentation fault.
    if map.capacity() == 0 {
        return None;
    }

    map.raw_entry().from_hash(hash, |&key_index| {
        let existing_key = keys.get(key_index).unwrap();
        key == existing_key.borrow()
    })
}

fn raw_entry_mut<'map, Key, KeyQuery, Value, State>(
    keys: &VecList<Key>,
    map: &'map mut HashMap<Index<Key>, MapEntry<Key, Value>, State>,
    hash: u64,
    key: &KeyQuery,
) -> RawEntryMut<'map, Index<Key>, MapEntry<Key, Value>, State>
where
    Key: Borrow<KeyQuery> + Eq + Hash,
    KeyQuery: ?Sized + Eq + Hash,
    State: BuildHasher,
{
    map.raw_entry_mut().from_hash(hash, |&key_index| {
        let existing_key = keys.get(key_index).unwrap();
        key == existing_key.borrow()
    })
}

fn raw_entry_mut_empty<'map, Key, KeyQuery, Value, State>(
    keys: &VecList<Key>,
    map: &'map mut HashMap<Index<Key>, MapEntry<Key, Value>, State>,
    hash: u64,
) -> RawEntryMut<'map, Index<Key>, MapEntry<Key, Value>, State>
where
    Key: Borrow<KeyQuery> + Eq + Hash,
    KeyQuery: ?Sized + Eq + Hash,
    State: BuildHasher,
{
    map.raw_entry_mut()
        .from_hash(hash, |&key_index| keys.get(key_index).is_none())
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_bounds() {
        fn check_bounds<Type: Send + Sync>() {}

        check_bounds::<EntryValues<'static, (), ()>>();
        check_bounds::<EntryValuesDrain<'static, (), ()>>();
        check_bounds::<EntryValuesMut<'static, (), ()>>();
        check_bounds::<IntoIter<(), ()>>();
        check_bounds::<Iter<'static, (), ()>>();
        check_bounds::<IterMut<'static, (), ()>>();
        check_bounds::<KeyValues<'static, (), ()>>();
        check_bounds::<KeyValuesDrain<'static, (), ()>>();
        check_bounds::<KeyValuesEntryDrain<'static, (), ()>>();
        check_bounds::<KeyValuesMut<'static, (), ()>>();
        check_bounds::<ListOrderedMultimap<(), ()>>();
        check_bounds::<Values<'static, (), ()>>();
        check_bounds::<ValuesMut<'static, (), ()>>();
    }

    #[test]
    fn test_collision() {
        struct TestBuildHasher;

        impl BuildHasher for TestBuildHasher {
            type Hasher = TestHasher;

            fn build_hasher(&self) -> Self::Hasher {
                TestHasher
            }
        }

        struct TestHasher;

        impl Hasher for TestHasher {
            fn finish(&self) -> u64 {
                0
            }

            fn write(&mut self, _: &[u8]) {}
        }

        let mut map = ListOrderedMultimap::with_hasher(TestBuildHasher);

        map.insert("key1", "value1");
        assert_eq!(map.get(&"key1"), Some(&"value1"));

        map.insert("key2", "value2");
        assert_eq!(map.get(&"key2"), Some(&"value2"));
    }

    #[test]
    fn test_entry_and_modify() {
        let mut map = ListOrderedMultimap::new();
        map.entry("key")
            .and_modify(|_| panic!("entry should be vacant"));

        map.insert("key", "value1");
        map.entry("key").and_modify(|value| *value = "value2");
        assert_eq!(map.get(&"key"), Some(&"value2"));
    }

    #[test]
    fn test_entry_or_insert() {
        let mut map = ListOrderedMultimap::new();
        let value = map.entry("key").or_insert("value1");
        assert_eq!(value, &"value1");

        let value = map.entry("key").or_insert("value2");
        assert_eq!(value, &"value1");
    }

    #[test]
    fn test_entry_or_insert_entry() {
        let mut map = ListOrderedMultimap::new();
        let entry = map.entry("key").or_insert_entry("value1");
        assert_eq!(entry.get(), &"value1");

        let entry = map.entry("key").or_insert_entry("value2");
        assert_eq!(entry.get(), &"value1");
    }

    #[test]
    fn test_entry_or_insert_with() {
        let mut map = ListOrderedMultimap::new();
        let value = map.entry("key").or_insert_with(|| "value1");
        assert_eq!(value, &"value1");

        let value = map.entry("key").or_insert_with(|| "value2");
        assert_eq!(value, &"value1");
    }

    #[test]
    fn test_entry_or_insert_with_entry() {
        let mut map = ListOrderedMultimap::new();
        let entry = map.entry("key").or_insert_with_entry(|| "value1");
        assert_eq!(entry.get(), &"value1");

        let entry = map.entry("key").or_insert_with_entry(|| "value2");
        assert_eq!(entry.get(), &"value1");
    }

    #[test]
    fn test_entry_values_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let iter = map.get_all(&"key");
        assert_eq!(
            format!("{:?}", iter),
            r#"EntryValues(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_entry_values_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.next(), Some("value1"));
        assert_eq!(iter.next_back(), Some("value4"));
        assert_eq!(iter.next(), Some("value2"));
        assert_eq!(iter.next_back(), Some("value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_drain_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let iter = map.remove_all(&"key");
        assert_eq!(
            format!("{:?}", iter),
            r#"EntryValuesDrain(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_entry_values_drain_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.next(), Some("value1"));
        assert_eq!(iter.next_back(), Some("value4"));
        assert_eq!(iter.next(), Some("value2"));
        assert_eq!(iter.next_back(), Some("value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_drain_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_drain_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.next(), Some("value"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_drain_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_entry_values_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next(), Some(&"value"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_mut_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let iter = map.get_all_mut(&"key");
        assert_eq!(
            format!("{:?}", iter),
            r#"EntryValuesMut(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_entry_values_mut_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.get_all_mut(&"key");
        assert_eq!(iter.next(), Some(&mut "value1"));
        assert_eq!(iter.next_back(), Some(&mut "value4"));
        assert_eq!(iter.next(), Some(&mut "value2"));
        assert_eq!(iter.next_back(), Some(&mut "value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_mut_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.get_all_mut(&"key");
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_mut_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.get_all_mut(&"key");
        assert_eq!(iter.next(), Some(&mut "value"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_entry_values_mut_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.get_all_mut(&"key");
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_entry_values_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_iter_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.iter();
        assert_eq!(
            format!("{:?}", iter),
            r#"Iter([("key1", "value1"), ("key2", "value2"), ("key2", "value3"), ("key1", "value4")])"#
        );
    }

    #[test]
    fn test_iter_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key1", &"value1")));
        assert_eq!(iter.next_back(), Some((&"key1", &"value4")));
        assert_eq!(iter.next(), Some((&"key2", &"value2")));
        assert_eq!(iter.next_back(), Some((&"key2", &"value3")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.iter();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key", &"value")));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_mut_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.iter_mut();
        assert_eq!(
            format!("{:?}", iter),
            r#"IterMut([("key1", "value1"), ("key2", "value2"), ("key2", "value3"), ("key1", "value4")])"#
        );
    }

    #[test]
    fn test_iter_mut_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter_mut();
        assert_eq!(iter.next(), Some((&"key1", &mut "value1")));
        assert_eq!(iter.next_back(), Some((&"key1", &mut "value4")));
        assert_eq!(iter.next(), Some((&"key2", &mut "value2")));
        assert_eq!(iter.next_back(), Some((&"key2", &mut "value3")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_mut_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.iter_mut();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_mut_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.iter_mut();
        assert_eq!(iter.next(), Some((&"key", &mut "value")));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_mut_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter_mut();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_iter_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_into_iter_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.into_iter();
        assert_eq!(
            format!("{:?}", iter),
            r#"IntoIter([("key1", "value1"), ("key2", "value2"), ("key2", "value3"), ("key1", "value4")])"#
        );
    }

    #[test]
    fn test_into_iter_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.into_iter();
        assert_eq!(iter.next(), Some(("key1", "value1")));
        assert_eq!(iter.next_back(), Some(("key1", "value4")));
        assert_eq!(iter.next(), Some(("key2", "value2")));
        assert_eq!(iter.next_back(), Some(("key2", "value3")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_into_iter_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.into_iter();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_into_iter_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.into_iter();
        assert_eq!(iter.next(), Some(("key", "value")));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_into_iter_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.into_iter();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_key_values_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.pairs();
        assert_eq!(
            format!("{:?}", iter),
            r#"KeyValues([("key1", EntryValues(["value1", "value4"])), ("key2", EntryValues(["value2", "value3"]))])"#
        );
    }

    #[test]
    fn test_key_values_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key1");
        assert_eq!(values.next(), Some(&"value1"));
        assert_eq!(values.next(), Some(&"value4"));
        assert_eq!(values.next(), None);

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key2");
        assert_eq!(values.next(), Some(&"value2"));
        assert_eq!(values.next(), Some(&"value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_drain_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.drain_pairs();
        assert_eq!(
            format!("{:?}", iter),
            r#"KeyValuesDrain([("key1", EntryValues(["value1", "value4"])), ("key2", EntryValues(["value2", "value3"]))])"#
        );
    }

    #[test]
    fn test_key_values_drain_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.drain_pairs();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, "key1");
        assert_eq!(values.next(), Some("value1"));
        assert_eq!(values.next(), Some("value4"));
        assert_eq!(values.next(), None);

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, "key2");
        assert_eq!(values.next(), Some("value2"));
        assert_eq!(values.next(), Some("value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_drain_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.drain_pairs();
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_drain_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.drain_pairs();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, "key");
        assert_eq!(values.next(), Some("value"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_drain_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.drain_pairs();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_key_values_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.pairs();
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_entry_drain_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.drain_pairs();
        let (_, values) = iter.next().unwrap();

        assert_eq!(
            format!("{:?}", values),
            r#"KeyValuesEntryDrain(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_key_values_entry_drain_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let mut iter = map.drain_pairs();
        let (_, mut values) = iter.next().unwrap();
        assert_eq!(values.next(), Some("value1"));
        assert_eq!(values.next_back(), Some("value4"));
        assert_eq!(values.next(), Some("value2"));
        assert_eq!(values.next_back(), Some("value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_entry_drain_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.drain_pairs();
        let (_, mut values) = iter.next().unwrap();
        assert_eq!(values.next(), Some("value"));
        assert_eq!(values.next(), None);
        assert_eq!(values.next_back(), None);
        assert_eq!(values.next(), None);
        assert_eq!(values.next_back(), None);
    }

    #[test]
    fn test_key_values_entry_drain_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.drain_pairs();
        let (_, mut values) = iter.next().unwrap();
        assert_eq!(values.size_hint(), (2, Some(2)));
        values.next();
        assert_eq!(values.size_hint(), (1, Some(1)));
        values.next();
        assert_eq!(values.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_key_values_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.pairs();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key");
        assert_eq!(values.next(), Some(&"value"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_mut_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.pairs_mut();
        assert_eq!(
            format!("{:?}", iter),
            r#"KeyValuesMut([("key1", EntryValues(["value1", "value4"])), ("key2", EntryValues(["value2", "value3"]))])"#
        );
    }

    #[test]
    fn test_key_values_mut_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs_mut();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key1");
        assert_eq!(values.next(), Some(&mut "value1"));
        assert_eq!(values.next(), Some(&mut "value4"));
        assert_eq!(values.next(), None);

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key2");
        assert_eq!(values.next(), Some(&mut "value2"));
        assert_eq!(values.next(), Some(&mut "value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_mut_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.pairs_mut();
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_mut_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.pairs_mut();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key");
        assert_eq!(values.next(), Some(&mut "value"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_key_values_mut_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs_mut();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_key_values_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_keys_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.keys();
        assert_eq!(format!("{:?}", iter), r#"Keys(["key1", "key2"])"#);
    }

    #[test]
    fn test_keys_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.keys();
        assert_eq!(iter.next(), Some(&"key1"));
        assert_eq!(iter.next_back(), Some(&"key2"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_keys_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.keys();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_keys_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.keys();
        assert_eq!(iter.next(), Some(&"key"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_keys_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.keys();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_list_ordered_multimap_append() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.entry_len(&"key"), 0);

        let already_exists = map.append("key", "value1");
        assert!(!already_exists);
        assert_eq!(map.entry_len(&"key"), 1);

        let already_exists = map.append("key", "value2");
        assert!(already_exists);
        assert_eq!(map.entry_len(&"key"), 2);

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_back() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.back(), None);

        map.insert("key1", "value1");
        assert_eq!(map.back(), Some((&"key1", &"value1")));

        map.append("key2", "value2");
        assert_eq!(map.back(), Some((&"key2", &"value2")));

        map.remove(&"key2");
        assert_eq!(map.back(), Some((&"key1", &"value1")));

        map.remove(&"key1");
        assert_eq!(map.back(), None);
    }

    #[test]
    fn test_list_ordered_multimap_back_mut() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.back(), None);

        map.insert("key1", "value1");
        assert_eq!(map.back(), Some((&"key1", &"value1")));

        map.append("key2", "value2");
        assert_eq!(map.back(), Some((&"key2", &"value2")));

        map.remove(&"key2");
        assert_eq!(map.back(), Some((&"key1", &"value1")));

        map.remove(&"key1");
        assert_eq!(map.back(), None);
    }

    #[test]
    fn test_list_ordered_multimap_clear() {
        let mut map = ListOrderedMultimap::new();
        map.insert("key", "value");
        map.insert("key2", "value");

        map.clear();

        assert!(map.is_empty());
        assert_eq!(map.get(&"key"), None);
        assert_eq!(map.get(&"key2"), None);
    }

    #[test]
    fn test_list_ordered_multimap_contains_key() {
        let mut map = ListOrderedMultimap::new();
        assert!(!map.contains_key(&"key"));

        map.insert("key", "value");
        assert!(map.contains_key(&"key"));
    }

    #[test]
    fn test_list_ordered_multimap_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        assert_eq!(
            format!("{:?}", map),
            r#"{"key1": "value1", "key2": "value2", "key2": "value3", "key1": "value4"}"#
        );
    }

    #[test]
    fn test_list_ordered_multimap_drain_pairs() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let prior_keys_capacity = map.keys_capacity();
        let prior_values_capacity = map.values_capacity();

        {
            let mut iter = map.drain_pairs();

            let (key, mut values) = iter.next().unwrap();
            assert_eq!(key, "key1");
            assert_eq!(values.next(), Some("value1"));
            assert_eq!(values.next(), Some("value4"));
            assert_eq!(values.next(), None);

            let (key, mut values) = iter.next().unwrap();
            assert_eq!(key, "key2");
            assert_eq!(values.next(), Some("value2"));
            assert_eq!(values.next(), Some("value3"));
            assert_eq!(values.next(), None);

            assert!(iter.next().is_none());
        }

        assert!(map.is_empty());
        assert_eq!(map.keys_capacity(), prior_keys_capacity);
        assert_eq!(map.values_capacity(), prior_values_capacity);
    }

    #[test]
    fn test_list_ordered_multimap_entry() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.get(&"key1"), None);

        let value = map.entry("key").or_insert("value1");
        assert_eq!(value, &"value1");
        assert_eq!(map.get(&"key"), Some(&"value1"));

        let value = map.entry("key").or_insert("value2");
        assert_eq!(value, &"value1");
        assert_eq!(map.get(&"key"), Some(&"value1"));
    }

    #[test]
    fn test_list_ordered_multimap_entry_len() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.entry_len(&"key1"), 0);

        map.insert("key", "value");
        assert_eq!(map.entry_len(&"key"), 1);

        map.insert("key", "value");
        assert_eq!(map.entry_len(&"key"), 1);

        map.append("key", "value");
        assert_eq!(map.entry_len(&"key"), 2);

        map.insert("key", "value");
        assert_eq!(map.entry_len(&"key"), 1);

        map.remove(&"key");
        assert_eq!(map.entry_len(&"key"), 0);
    }

    #[test]
    fn test_list_ordered_multimap_equality() {
        let mut map_1 = ListOrderedMultimap::new();

        map_1.insert("key1", "value1");
        map_1.insert("key2", "value2");
        map_1.append("key2", "value3");
        map_1.append("key1", "value4");

        let mut map_2 = map_1.clone();
        map_2.pop_back();

        assert_ne!(map_1, map_2);

        map_2.append("key1", "value4");
        assert_eq!(map_1, map_2);
    }

    #[test]
    fn test_list_ordered_multimap_extend() {
        let mut map = ListOrderedMultimap::new();
        map.extend(vec![("key1", "value1"), ("key2", "value2"), ("key2", "value3")].into_iter());

        let mut iter = map.get_all(&"key1");
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next(), None);

        let mut iter = map.get_all(&"key2");
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next(), Some(&"value3"));
        assert_eq!(iter.next(), None);

        let mut map = ListOrderedMultimap::new();
        map.extend(vec![(&1, &1), (&2, &1), (&2, &2)].into_iter());

        let mut iter = map.get_all(&1);
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), None);

        let mut iter = map.get_all(&2);
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_from_iterator() {
        let map: ListOrderedMultimap<_, _, RandomState> = ListOrderedMultimap::from_iter(
            vec![("key1", "value1"), ("key2", "value2"), ("key2", "value3")].into_iter(),
        );

        let mut iter = map.get_all(&"key1");
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next(), None);

        let mut iter = map.get_all(&"key2");
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next(), Some(&"value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_get() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.get(&"key"), None);

        map.insert("key", "value");
        assert_eq!(map.get(&"key"), Some(&"value"));
    }

    #[test]
    fn test_list_ordered_multimap_get_all() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next(), None);

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next(), Some(&"value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_get_all_mut() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.get_all(&"key");
        assert_eq!(iter.next(), None);

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");

        let mut iter = map.get_all_mut(&"key");
        assert_eq!(iter.next(), Some(&mut "value1"));
        assert_eq!(iter.next(), Some(&mut "value2"));
        assert_eq!(iter.next(), Some(&mut "value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_get_mut() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.get_mut(&"key"), None);

        map.insert("key", "value");
        assert_eq!(map.get_mut(&"key"), Some(&mut "value"));
    }

    #[test]
    fn test_list_ordered_multimap_insert() {
        let mut map = ListOrderedMultimap::new();
        assert!(!map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), None);

        let value = map.insert("key", "value1");
        assert_eq!(value, None);
        assert!(map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), Some(&"value1"));

        let value = map.insert("key", "value2");
        assert_eq!(value, Some("value1"));
        assert!(map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), Some(&"value2"));
    }

    #[test]
    fn test_list_ordered_multimap_insert_all() {
        let mut map = ListOrderedMultimap::new();
        assert!(!map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), None);

        {
            let mut iter = map.insert_all("key", "value1");
            assert_eq!(iter.next(), None);
        }

        assert!(map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), Some(&"value1"));

        {
            let mut iter = map.insert_all("key", "value2");
            assert_eq!(iter.next(), Some("value1"));
            assert_eq!(iter.next(), None);
        }

        assert!(map.contains_key(&"key"));
        assert_eq!(map.get(&"key"), Some(&"value2"));
    }

    #[test]
    fn test_list_ordered_multimap_is_empty() {
        let mut map = ListOrderedMultimap::new();
        assert!(map.is_empty());

        map.insert("key", "value");
        assert!(!map.is_empty());

        map.remove(&"key");
        assert!(map.is_empty());
    }

    #[test]
    fn test_list_ordered_multimap_iter() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.iter();
        assert_eq!(iter.next(), None);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key1", &"value1")));
        assert_eq!(iter.next(), Some((&"key2", &"value2")));
        assert_eq!(iter.next(), Some((&"key2", &"value3")));
        assert_eq!(iter.next(), Some((&"key1", &"value4")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_iter_mut() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.iter_mut();
        assert_eq!(iter.next(), None);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.iter_mut();
        assert_eq!(iter.next(), Some((&"key1", &mut "value1")));
        assert_eq!(iter.next(), Some((&"key2", &mut "value2")));
        assert_eq!(iter.next(), Some((&"key2", &mut "value3")));
        assert_eq!(iter.next(), Some((&"key1", &mut "value4")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_keys() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.keys();
        assert_eq!(iter.next(), None);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.insert("key1", "value3");
        map.insert("key3", "value4");

        let mut iter = map.keys();
        assert_eq!(iter.next(), Some(&"key1"));
        assert_eq!(iter.next(), Some(&"key2"));
        assert_eq!(iter.next(), Some(&"key3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_keys_capacity() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.keys_capacity(), 0);
        map.insert("key", "value");
        assert!(map.keys_capacity() > 0);
    }

    #[test]
    fn test_list_ordered_multimap_keys_len() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.keys_len(), 0);

        map.insert("key1", "value1");
        assert_eq!(map.keys_len(), 1);

        map.insert("key2", "value2");
        assert_eq!(map.keys_len(), 2);

        map.append("key1", "value3");
        assert_eq!(map.keys_len(), 2);

        map.remove(&"key1");
        assert_eq!(map.keys_len(), 1);

        map.remove(&"key2");
        assert_eq!(map.keys_len(), 0);
    }

    #[test]
    fn test_list_ordered_multimap_new() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        assert_eq!(map.keys_capacity(), 0);
        assert_eq!(map.keys_len(), 0);
        assert_eq!(map.values_capacity(), 0);
        assert_eq!(map.values_len(), 0);
    }

    #[test]
    fn test_list_ordered_multimap_pack_to() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(5, 5);
        map.pack_to_fit();
        assert_eq!(map.keys_capacity(), 0);
        assert_eq!(map.values_capacity(), 0);

        let mut map = ListOrderedMultimap::with_capacity(10, 10);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        map.pack_to(5, 5);

        assert_eq!(map.get(&"key1"), Some(&"value1"));
        assert_eq!(map.get(&"key2"), Some(&"value2"));

        assert_eq!(map.keys_capacity(), 5);
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_capacity(), 5);
        assert_eq!(map.values_len(), 4);

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key1", &"value1")));
        assert_eq!(iter.next(), Some((&"key2", &"value2")));
        assert_eq!(iter.next(), Some((&"key2", &"value3")));
        assert_eq!(iter.next(), Some((&"key1", &"value4")));
        assert_eq!(iter.next(), None);
    }

    #[should_panic]
    #[test]
    fn test_list_ordered_multimap_pack_to_panic_key_capacity() {
        let mut map = ListOrderedMultimap::new();
        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");
        map.pack_to(1, 5);
    }

    #[should_panic]
    #[test]
    fn test_list_ordered_multimap_pack_to_panic_value_capacity() {
        let mut map = ListOrderedMultimap::new();
        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");
        map.pack_to(5, 1);
    }

    #[test]
    fn test_list_ordered_multimap_pack_to_fit() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(5, 5);
        map.pack_to_fit();
        assert_eq!(map.keys_capacity(), 0);
        assert_eq!(map.values_capacity(), 0);

        let mut map = ListOrderedMultimap::with_capacity(5, 5);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        map.pack_to_fit();
        assert_eq!(map.keys_capacity(), 2);
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_capacity(), 4);
        assert_eq!(map.values_len(), 4);

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key1", &"value1")));
        assert_eq!(iter.next(), Some((&"key2", &"value2")));
        assert_eq!(iter.next(), Some((&"key2", &"value3")));
        assert_eq!(iter.next(), Some((&"key1", &"value4")));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_pairs() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key1");
        assert_eq!(values.next(), Some(&"value1"));
        assert_eq!(values.next(), Some(&"value4"));
        assert_eq!(values.next(), None);

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key2");
        assert_eq!(values.next(), Some(&"value2"));
        assert_eq!(values.next(), Some(&"value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_list_ordered_multimap_pairs_mut() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.pairs_mut();

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key1");
        assert_eq!(values.next(), Some(&mut "value1"));
        assert_eq!(values.next(), Some(&mut "value4"));
        assert_eq!(values.next(), None);

        let (key, mut values) = iter.next().unwrap();
        assert_eq!(key, &"key2");
        assert_eq!(values.next(), Some(&mut "value2"));
        assert_eq!(values.next(), Some(&mut "value3"));
        assert_eq!(values.next(), None);

        assert!(iter.next().is_none());
    }

    #[test]
    fn test_list_ordered_multimap_pop_back() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let (key, value) = map.pop_back().unwrap();
        assert_eq!(key, KeyWrapper::Borrowed(&"key1"));
        assert_eq!(&value, &"value4");
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_len(), 3);

        let (key, value) = map.pop_back().unwrap();
        assert_eq!(key, KeyWrapper::Borrowed(&"key2"));
        assert_eq!(&value, &"value3");
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_len(), 2);

        let (key, value) = map.pop_back().unwrap();
        assert_eq!(key, KeyWrapper::Owned("key2"));
        assert_eq!(&value, &"value2");
        assert_eq!(map.keys_len(), 1);
        assert_eq!(map.values_len(), 1);

        let (key, value) = map.pop_back().unwrap();
        assert_eq!(key, KeyWrapper::Owned("key1"));
        assert_eq!(&value, &"value1");
        assert_eq!(map.keys_len(), 0);
        assert_eq!(map.values_len(), 0);

        assert!(map.pop_back().is_none());
    }

    #[test]
    fn test_list_ordered_multimap_pop_front() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let (key, value) = map.pop_front().unwrap();
        assert_eq!(key, KeyWrapper::Borrowed(&"key1"));
        assert_eq!(&value, &"value1");
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_len(), 3);

        let (key, value) = map.pop_front().unwrap();
        assert_eq!(key, KeyWrapper::Borrowed(&"key2"));
        assert_eq!(&value, &"value2");
        assert_eq!(map.keys_len(), 2);
        assert_eq!(map.values_len(), 2);

        let (key, value) = map.pop_front().unwrap();
        assert_eq!(key, KeyWrapper::Owned("key2"));
        assert_eq!(&value, &"value3");
        assert_eq!(map.keys_len(), 1);
        assert_eq!(map.values_len(), 1);

        let (key, value) = map.pop_front().unwrap();
        assert_eq!(key, KeyWrapper::Owned("key1"));
        assert_eq!(&value, &"value4");
        assert_eq!(map.keys_len(), 0);
        assert_eq!(map.values_len(), 0);

        assert!(map.pop_front().is_none());
    }

    #[test]
    fn test_list_ordered_multimap_remove() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.remove(&"key"), None);

        map.insert("key", "value1");
        map.append("key", "value2");
        assert_eq!(map.remove(&"key"), Some("value1"));
        assert_eq!(map.remove(&"key"), None);
    }

    #[test]
    fn test_list_ordered_multimap_remove_all() {
        let mut map = ListOrderedMultimap::new();

        {
            let mut iter = map.remove_all(&"key");
            assert_eq!(iter.next(), None);
        }

        map.insert("key", "value1");
        map.append("key", "value2");

        {
            let mut iter = map.remove_all(&"key");
            assert_eq!(iter.next(), Some("value1"));
            assert_eq!(iter.next(), Some("value2"));
            assert_eq!(iter.next(), None);
        }

        let mut iter = map.remove_all(&"key");
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_remove_entry() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.remove_entry(&"key"), None);

        map.insert("key", "value1");
        map.append("key", "value2");
        assert_eq!(map.remove_entry(&"key"), Some(("key", "value1")));
        assert_eq!(map.remove_entry(&"key"), None);
    }

    #[test]
    fn test_list_ordered_multimap_remove_entry_all() {
        let mut map = ListOrderedMultimap::new();

        {
            let entry = map.remove_entry_all(&"key");
            assert!(entry.is_none());
        }

        map.insert("key", "value1");
        map.append("key", "value2");

        {
            let (key, mut iter) = map.remove_entry_all(&"key").unwrap();
            assert_eq!(key, "key");
            assert_eq!(iter.next(), Some("value1"));
            assert_eq!(iter.next(), Some("value2"));
            assert_eq!(iter.next(), None);
        }

        let entry = map.remove_entry_all(&"key");
        assert!(entry.is_none());
    }

    #[test]
    fn test_list_ordered_multimap_reserve_keys() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        assert_eq!(map.keys_capacity(), 0);

        map.reserve_keys(5);
        assert!(map.keys_capacity() >= 5);

        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(5, 5);
        assert_eq!(map.keys_capacity(), 5);

        map.reserve_keys(2);
        assert_eq!(map.keys_capacity(), 5);
    }

    #[test]
    fn test_list_ordered_multimap_reserve_values() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        assert_eq!(map.values_capacity(), 0);

        map.reserve_values(5);
        assert!(map.values_capacity() >= 5);

        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(5, 5);
        assert_eq!(map.values_capacity(), 5);

        map.reserve_values(2);
        assert_eq!(map.values_capacity(), 5);
    }

    #[test]
    fn test_list_ordered_multimap_retain() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", 1);
        map.insert("key2", 5);
        map.append("key1", -1);
        map.insert("key3", -10);
        map.insert("key4", 1);
        map.append("key4", -1);
        map.append("key4", 1);

        map.retain(|_, &mut value| value >= 0);

        let mut iter = map.iter();
        assert_eq!(iter.next(), Some((&"key1", &1)));
        assert_eq!(iter.next(), Some((&"key2", &5)));
        assert_eq!(iter.next(), Some((&"key4", &1)));
        assert_eq!(iter.next(), Some((&"key4", &1)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_values() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.iter();
        assert_eq!(iter.next(), None);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values();
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next(), Some(&"value3"));
        assert_eq!(iter.next(), Some(&"value4"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_values_mut() {
        let mut map = ListOrderedMultimap::new();

        let mut iter = map.iter();
        assert_eq!(iter.next(), None);

        map.insert("key1", "value1");
        map.insert("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values_mut();
        assert_eq!(iter.next(), Some(&mut "value1"));
        assert_eq!(iter.next(), Some(&mut "value2"));
        assert_eq!(iter.next(), Some(&mut "value3"));
        assert_eq!(iter.next(), Some(&mut "value4"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_list_ordered_multimap_values_capacity() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.values_capacity(), 0);
        map.insert("key", "value");
        assert!(map.values_capacity() > 0);
    }

    #[test]
    fn test_list_ordered_multimap_values_len() {
        let mut map = ListOrderedMultimap::new();
        assert_eq!(map.values_len(), 0);

        map.insert("key1", "value1");
        assert_eq!(map.values_len(), 1);

        map.insert("key2", "value2");
        assert_eq!(map.values_len(), 2);

        map.append("key1", "value3");
        assert_eq!(map.values_len(), 3);

        map.remove(&"key1");
        assert_eq!(map.values_len(), 1);

        map.remove(&"key2");
        assert_eq!(map.values_len(), 0);
    }

    #[test]
    fn test_list_ordered_multimap_with_capacity() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::with_capacity(1, 2);
        assert!(map.keys_capacity() >= 1);
        assert_eq!(map.keys_len(), 0);
        assert!(map.values_capacity() >= 2);
        assert_eq!(map.values_len(), 0);
    }

    #[test]
    fn test_list_ordered_multimap_with_capacity_and_hasher() {
        let state = RandomState::new();
        let map: ListOrderedMultimap<&str, &str> =
            ListOrderedMultimap::with_capacity_and_hasher(1, 2, state);
        assert!(map.keys_capacity() >= 1);
        assert_eq!(map.keys_len(), 0);
        assert!(map.values_capacity() >= 2);
        assert_eq!(map.values_len(), 0);
    }

    #[test]
    fn test_occupied_entry_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value1");
        map.append("key", "value2");
        map.append("key", "value3");
        map.append("key", "value4");

        let entry = match map.entry(&"key") {
            Entry::Occupied(entry) => entry,
            _ => panic!("expected occupied entry"),
        };

        assert_eq!(
            format!("{:?}", entry),
            "OccupiedEntry { \
             key: \"key\", \
             values: EntryValues([\"value1\", \"value2\", \"value3\", \"value4\"]) \
             }"
        );
    }

    #[test]
    fn test_vacant_entry_debug() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let entry = match map.entry(&"key") {
            Entry::Vacant(entry) => entry,
            _ => panic!("expected vacant entry"),
        };

        assert_eq!(format!("{:?}", entry), r#"VacantEntry("key")"#);
    }

    #[test]
    fn test_values_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.values();
        assert_eq!(
            format!("{:?}", iter),
            r#"Values(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_values_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values();
        assert_eq!(iter.next(), Some(&"value1"));
        assert_eq!(iter.next_back(), Some(&"value4"));
        assert_eq!(iter.next(), Some(&"value2"));
        assert_eq!(iter.next_back(), Some(&"value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_empty() {
        let map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.values();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.values();
        assert_eq!(iter.next(), Some(&"value"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_mut_debug() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let iter = map.values_mut();
        assert_eq!(
            format!("{:?}", iter),
            r#"ValuesMut(["value1", "value2", "value3", "value4"])"#
        );
    }

    #[test]
    fn test_values_mut_double_ended() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values_mut();
        assert_eq!(iter.next(), Some(&mut "value1"));
        assert_eq!(iter.next_back(), Some(&mut "value4"));
        assert_eq!(iter.next(), Some(&mut "value2"));
        assert_eq!(iter.next_back(), Some(&mut "value3"));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_mut_empty() {
        let mut map: ListOrderedMultimap<&str, &str> = ListOrderedMultimap::new();
        let mut iter = map.values_mut();
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_mut_fused() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key", "value");

        let mut iter = map.values_mut();
        assert_eq!(iter.next(), Some(&mut "value"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_values_mut_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values_mut();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }

    #[test]
    fn test_values_size_hint() {
        let mut map = ListOrderedMultimap::new();

        map.insert("key1", "value1");
        map.append("key2", "value2");
        map.append("key2", "value3");
        map.append("key1", "value4");

        let mut iter = map.values();
        assert_eq!(iter.size_hint(), (4, Some(4)));
        iter.next();
        assert_eq!(iter.size_hint(), (3, Some(3)));
        iter.next();
        assert_eq!(iter.size_hint(), (2, Some(2)));
        iter.next();
        assert_eq!(iter.size_hint(), (1, Some(1)));
        iter.next();
        assert_eq!(iter.size_hint(), (0, Some(0)));
    }
}