use alloc::vec::Vec;
use core::{
    borrow::Borrow,
    cell::Cell,
    fmt,
    fmt::Formatter,
    hash::{BuildHasher, Hash, Hasher},
    iter::FromIterator,
    mem,
    num::NonZeroUsize,
    ops::{Index, IndexMut},
};

use crate::{FromIndex, Idx, IntoIndex, Key, NewIndex};

mod hasher;

use hasher::LuaBuildHasher;

mod iter;

pub use iter::{IntoIter, Iter, IterMut, Keys, Values, ValuesMut};

macro_rules! cp {
    ($T:ty => $U:ty, $v:ident => $field:ident) => {
        match $v {
            ref cell => {
                let cell: &Cell<$T> = cell;
                let ptr: *mut $T = cell.as_ptr();
                let member_ptr: *mut $U = unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) };
                let cell_ptr: *mut Cell<$U> = member_ptr.cast();
                unsafe { &*cell_ptr }
            }
        }
    };
}

mod node;

use node::Node;

mod entry;

pub use entry::{Entry, OccupiedEntry, VacantEntry};

#[inline]
const fn round_pow_2(x: usize) -> usize {
    if x == 0 {
        0
    } else {
        x.next_power_of_two()
    }
}

// Round x down to the next power of two
#[inline]
const fn round_down_pow_2(x: usize) -> usize {
    if x.is_power_of_two() {
        x
    } else {
        x.next_power_of_two() >> 1
    }
}

#[inline]
const fn ceil_log_2(x: NonZeroUsize) -> usize {
    // This function computes ceil(log2(i)).
    //
    // usize::MAX => usize::BITS,
    // usize::MAX >> 1 => usize::BITS - 1
    // ...
    // 4 => 2
    // 3 => 2
    // 2 => 1
    // 1 => 0
    (usize::BITS - (x.get() - 1).leading_zeros()) as usize
}

// #[test]
// fn test_ceil_log_2() {
//     let inputs = [
//         (1, 0),
//         (2, 1),
//         (3, 2),
//         (4, 2),
//         (5, 3),
//         (6, 3),
//         (7, 3),
//         (8, 3),
//         (9, 4),
//         (10, 4),
//         (usize::MAX, usize::BITS as usize),
//         (usize::MAX >> 1, usize::BITS as usize - 1),
//     ];
//     for (input, output) in inputs.iter().copied() {
//         assert_eq!(
//             ceil_log_2(NonZeroUsize::new(input).unwrap()),
//             output,
//             "input = {}. lz = {}",
//             input,
//             input.leading_zeros()
//         );
//     }
// }

const NUMS_LEN: usize = usize::BITS as usize;
type Nums = [usize; NUMS_LEN];

/// A hash map with an `array` part and a `hash` part, like [Lua]'s table structure.
///
/// [Lua]: https://www.lua.org/
///
/// This is most useful when you want to use the map like a sparse array, since
/// the hash part can store most of the sparse items, while the array part offers
/// better performance than `HashMap` for arrays that aren't very sparse.
///
/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
/// If you implement these yourself, it is important that the following
/// property holds:
///
/// ```text
/// k1 == k2 -> hash(k1) == hash(k2)
/// ```
///
/// In other words, if two keys are equal, their hashes must be equal.
///
/// Additionally, keys are required to implement the [`IntoIndex`] and [`FromIndex`]
/// traits that allow conversion to and from indices into the `array` part.
///
/// It is a logic error for a key to be modified in such a way that the key's
/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
/// the [`Eq`] trait, changes while it is in the map. This is normally only
/// possible through [`Cell`], [`RefCell`], global state, or I/O.
///
/// # Examples
///
/// ```
/// use hash_arr_map::Ham;
///
/// // Type inference lets us omit an explicit type signature (which
/// // would be `Ham<i32, i32>` in this example).
/// let mut squares = Ham::new();
///
/// // Square some numbers.
/// squares.insert(1, 1);
/// squares.insert(2, 4);
/// squares.insert(3, 8);
/// squares.insert(5, 25);
///
/// // Check for a specific square.
/// if !squares.contains_key(&4) {
///     println!(
///         "We've got {} squares, but not the square of 4.",
///         squares.len()
///     );
/// }
///
/// // oops, this square is incorrect. Let's delete it
/// squares.remove(&3);
///
/// // Iterate over everything.
/// for (number, square) in &squares {
///     println!("{}'s square is {}", number, square);
/// }
/// ```
///
/// `Ham` also implements an [`Entry API`](#method.entry), which allows
/// for more complex methods of getting, setting, updating and removing keys and
/// their values:
///
/// ```rust
/// use hash_arr_map::Ham;
///
/// let text = "Rust's strings are utf-8 \u{2764}";
///
/// // Type inference lets us not say what type of map this is.
/// // (`Ham<char, usize>` in this example)
/// let mut map = Ham::new();
///
/// for c in text.chars() {
///     map.entry(c).and_modify(|c| *c += 1).or_insert(1_usize);
/// }
///
/// assert_eq!(map[&'t'], 3);
/// assert_eq!(map[&'s'], 4);
/// assert_eq!(map[&'❤'], 1);
/// ```
///
/// The easiest way to use `Ham` with a custom key type is to derive [`Eq`] and [`Hash`],
/// then implement [`IntoIndex`] and [`FromIndex`] for it.
/// We must also derive [`PartialEq`].
///
/// [`RefCell`]: core::cell::RefCell
/// [`Cell`]: core::cell::Cell
/// [`with_hasher`]: Self::with_hasher
/// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
///
/// ```
/// use hash_arr_map::{FromIndex, Ham, Idx, IntoIndex};
///
/// #[derive(Hash, Eq, PartialEq, Debug)]
/// struct Item {
///     dollars: u8,
///     cents: u8,
/// }
///
/// impl Item {
///     /// Creates a new Item.
///     fn new(dollars: u8, cents: u8) -> Self {
///         Self { dollars, cents }
///     }
/// }
///
/// impl IntoIndex for Item {
///     fn into_index(&self) -> Option<Idx<Self>> {
///         unsafe { Idx::from_usize(((self.cents as usize) << 8) + self.dollars as usize) }
///     }
/// }
///
/// impl FromIndex for Item {
///     fn from_index(idx: Idx<Self>) -> Self {
///         Self {
///             dollars: idx.get().get() as u8,
///             cents: (idx.get().get() >> 8) as u8,
///         }
///     }
/// }
///
/// // Use a HashMap to store the item's quantity.
/// let mut items = Ham::new();
///
/// items.insert(Item::new(10, 0), 25);
/// items.insert(Item::new(5, 50), 24);
/// items.insert(Item::new(7, 75), 12);
///
/// let total: usize = items
///     .iter()
///     .map(|(item, qty)| {
///         let dollars: usize = item.dollars as usize;
///         let cents: usize = item.cents as usize;
///         (dollars * 100 + cents) * qty // In cents
///     })
///     .sum();
/// println!("Total is {}c", total);
///
/// // Use derived implementation to print the status of the items.
/// for (item, qty) in &items {
///     println!("{:?} has {} quantity", item, qty);
/// }
/// ```
///
/// A `HashMap` with fixed list of elements can be initialized from an array:
///
/// ```
/// use std::borrow::Cow;
///
/// use hash_arr_map::Ham;
///
/// let timber_resources: Ham<Cow<str>, u32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]
///     .iter()
///     .copied()
///     .map(|(k, v)| (Cow::Borrowed(k), v))
///     .collect();
/// // use the values stored in map
/// ```
///
/// References cannot be used as keys, as they cannot be easily converted to
/// indexes and back:
///
/// ```rust,compile_fail
/// use hash_arr_map::Ham;
///
/// // This is inferred as `Ham<&str, i32>`.
/// let mut h = Ham::new();
///
/// h.insert("test", 101);
/// ```
#[derive(Clone)]
pub struct Ham<K, V> {
    array: Vec<Option<V>>,
    hash: Vec<Node<K, V>>,

    // How many values are currently stored
    len: usize,

    // The last free node in the hash part.
    last_free: usize,

    // To build the hasher that is used to hash keys.
    hash_builder: LuaBuildHasher,
}

#[cfg(feature = "imm_gc")]
unsafe impl<K: imm_gc::Trace, V: imm_gc::Trace> imm_gc::Trace for Ham<K, V> {
    imm_gc::unsafe_field_trace! {
        array: Vec<Option<V>>,
        hash: Vec<Node<K, V>>,
    }
}

#[cfg(feature = "bacon_rajan_cc")]
impl<K: bacon_rajan_cc::Trace, V: bacon_rajan_cc::Trace> bacon_rajan_cc::Trace for Ham<K, V> {
    fn trace(&self, t: &mut bacon_rajan_cc::Tracer) {
        self.array.trace(t);
        self.hash.trace(t);
    }
}

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

#[cfg(feature = "std")]
impl<K, V> Default for Ham<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(feature = "std")]
impl<K, V> Ham<K, V> {
    /// Creates a new `Ham`.
    #[must_use]
    pub fn new() -> Self {
        Self {
            array: Vec::new(),
            len: 0,
            hash: Vec::new(),
            last_free: 0,
            hash_builder: LuaBuildHasher::new(),
        }
    }

    /// Creates a new `Ham` with a specific capacity.
    #[must_use]
    pub fn with_capacity(array_part: usize, hash_part: usize) -> Self {
        let mut array = Vec::with_capacity(array_part);
        array.resize_with(array_part, Option::default);

        // Round up to the next power of two.

        let hash_part = round_pow_2(hash_part);

        let mut hash = Vec::with_capacity(hash_part);
        hash.resize_with(hash_part, Node::default);

        Self {
            array,
            len: 0,
            hash,
            last_free: hash_part,
            hash_builder: LuaBuildHasher::new(),
        }
    }
}

impl<K, V> Ham<K, V> {
    /// Creates a new `Ham` with a specific seed.
    #[must_use]
    pub const fn with_seed(seed: u64) -> Self {
        Self {
            array: Vec::new(),
            len: 0,
            hash: Vec::new(),
            last_free: 0,
            hash_builder: LuaBuildHasher::with_seed(seed),
        }
    }

    /// Creates a new `Ham` with a specific capacity and a specific seed.
    #[must_use]
    pub fn with_capacity_and_seed(array_part: usize, hash_part: usize, seed: u64) -> Self {
        let mut array = Vec::with_capacity(array_part);
        array.resize_with(array_part, Option::default);

        let hash_part = round_pow_2(hash_part);

        let mut hash = Vec::with_capacity(hash_part);
        hash.resize_with(hash_part, Node::default);

        Self {
            array,
            len: 0,
            hash,
            last_free: hash_part,
            hash_builder: LuaBuildHasher::with_seed(seed),
        }
    }

    /// How many elements the `Ham` has eaten.
    #[must_use]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[must_use]
    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Returns the number of elements in both sections the `Ham` can eat
    /// without having to allocate.
    #[must_use]
    pub fn capacity(&self) -> (usize, usize) {
        (self.array.len(), self.hash.len())
    }

    /// Empties the `Ham`.
    pub fn clear(&mut self) {
        self.len = 0;

        for item in &mut self.array {
            *item = None;
        }

        for item in &mut self.hash {
            item.take();
            item.next = 0;
        }

        self.last_free = self.hash.len();
    }

    /// Whether `key` would be stored in the array part.
    ///
    /// Note: This method may be incorrect for some values once they are
    /// inserted
    ///
    /// > Example:
    /// >
    /// > Initial layout:
    /// > ```text
    /// > array_part: [0, 1, 2],
    /// > hash_part: {5}
    /// > ```
    /// >
    /// > `is_in_array(4)` would return false, likewise `is_in_array(3)`.
    /// >
    /// > If `4` or `3` were now inserted, the layout would then likely be
    /// > ```text
    /// > array_part: [0, 1, 2, _, 4, 5], // _ is none
    /// > hash_part: {}
    /// > ```
    /// > where 3 and 4 are now in the array.
    #[must_use]
    pub fn is_in_array<Q: ?Sized + IntoIndex>(&self, key: &Q) -> bool {
        self.get_array(key).is_some()
    }

    #[must_use]
    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        if let Some(v) = self.get_array(key) {
            v.as_ref()
        } else {
            self.get_hash(key)
                .and_then(|v| v.value().as_ref().map(|p| &p.1))
        }
    }

    #[must_use]
    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        self.get(key).is_some()
    }

    #[must_use]
    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        if let Some(idx) = self.get_array_idx_only(key) {
            // To get it past the borrow checker...
            unsafe { self.array.get_unchecked_mut(idx) }.as_mut()
        } else {
            self.get_hash_mut(key)
                .and_then(|v| v.value_mut().as_mut().map(|p| &mut p.1))
        }
    }

    pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        let v = self
            .get_array_take(key)
            .or_else(|| self.get_hash_take(key).map(|v| v.1));

        if v.is_some() {
            self.len -= 1;
        }

        v
    }
}

impl<K: FromIndex, V> Ham<K, V> {
    pub fn iter(&self) -> Iter<'_, K, V> {
        Iter {
            array: self.array.iter().enumerate(),
            hash: self.hash.iter(),
            len: self.len,
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut {
            array: self.array.iter_mut().enumerate(),
            hash: self.hash.iter_mut(),
            len: self.len,
        }
    }

    pub fn keys(&self) -> Keys<'_, K, V> {
        Keys { inner: self.iter() }
    }

    pub fn values(&self) -> Values<'_, K, V> {
        Values {
            array: self.array.iter(),
            hash: self.hash.iter(),
            len: self.len,
        }
    }

    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
        ValuesMut {
            array: self.array.iter_mut(),
            hash: self.hash.iter_mut(),
            len: self.len,
        }
    }
}

impl<K: FromIndex + Hash + Eq, V> Ham<K, V> {
    #[must_use]
    pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(Key<'_, K>, &V)>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        if let Some((idx, v)) = self.get_array_idx(key) {
            v.as_ref()
                .map(|v| (Key::Owned(idx.cast_safe().into_value()), v))
        } else {
            self.get_hash(key)
                .and_then(|v| v.value().as_ref().map(|(k, v)| (Key::Borrowed(k), v)))
        }
    }

    /// Removes a key from the map, returning the stored key and value if the
    /// key was previously in the map.
    ///
    /// The key may be any borrowed form of the map's key type, but Hash and Eq
    /// on the borrowed form must match those for the key type.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use hash_arr_map::Ham;
    ///
    /// let mut map = Ham::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
    /// assert_eq!(map.remove(&1), None);
    /// ```
    #[must_use]
    pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
    where
        K: Borrow<Q>,
        Q: IntoIndex + Hash + Eq,
    {
        let v = if let Some((idx, v)) = self.get_array_idx_mut(key) {
            v.take().map(|v| (idx.cast_safe().into_value(), v))
        } else {
            self.get_hash_take(key)
        };

        if v.is_some() {
            self.len -= 1;
        }

        v
    }
}

impl<K: NewIndex + Hash + Eq, V> Ham<K, V> {
    /// This function finds a boundary in the `table`, such that `table.get(n)`
    /// is `Some(_)`, and `table.get(n + 1)` is `None`.
    pub fn get_n(&self) -> Option<usize> {
        // Binary search for a border. Entry at max must be empty, min must be 0
        // or entry at min must be non-empty.
        fn binary_search(
            mut min: usize,
            mut max: usize,
            is_empty: impl Fn(usize) -> Option<bool>,
        ) -> Option<usize> {
            while max - min > 1 {
                let mid = min + (max - min) / 2;
                if is_empty(mid)? {
                    max = mid;
                } else {
                    min = mid;
                }
            }
            Some(min)
        }

        let array_len = self.array.len();

        if let Some(&None) = self.array.last() {
            // It ends with a none, meaning that there is a border inside
            binary_search(0, array_len, |i| Some(self.array[i].is_none()))
        } else if self.array.is_empty() {
            None
        } else if self.hash.is_empty() {
            // If there is no border in the array and no hash, the end of the
            // array is the border.
            Some(array_len)
        } else {
            // Otherwise, we check the hash part.
            // First we find a None value as the max for a binary search.
            let min = array_len;
            let mut max = array_len + 1;

            while self
                .get_hash(&Idx::try_new_usize(max)?.into_value())
                .is_some()
            {
                if max == usize::MAX {
                    return Some(usize::MAX);
                }
                max = max.saturating_mul(2);
            }

            binary_search(min, max, |i| {
                Some(
                    self.get_hash(&Idx::try_new_usize(i)?.into_value())
                        .is_some(),
                )
            })
        }
    }
}

impl<K: IntoIndex + FromIndex + Hash + Eq, V> Ham<K, V> {
    /// Gets the given key’s corresponding entry in the map for in-place manipulation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use hash_arr_map::Ham;
    ///
    /// let mut letters = Ham::new();
    ///
    /// for ch in "a short treatise on fungi".chars() {
    ///     let counter = letters.entry(ch).or_insert(0);
    ///     *counter += 1;
    /// }
    ///
    /// assert_eq!(letters[&'s'], 2);
    /// assert_eq!(letters[&'t'], 3);
    /// assert_eq!(letters[&'u'], 1);
    /// assert_eq!(letters.get(&'y'), None);
    /// ```
    #[must_use]
    pub fn entry(&mut self, k: K) -> Entry<'_, K, V> {
        Entry::make_new(self, k) // Private helper
    }

    /// Feed the `Ham` with a key-value pair.
    ///
    /// If the map did not have this key present, [`None`] is returned.
    ///
    /// If the map did have this key present, the value is updated, and the old
    /// value is returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use hash_arr_map::Ham;
    ///
    /// let mut map = Ham::new();
    /// assert_eq!(map.insert(37, "a"), None);
    /// assert_eq!(map.is_empty(), false);
    ///
    /// map.insert(37, "b");
    /// assert_eq!(map.insert(37, "c"), Some("b"));
    /// assert_eq!(map[&37], "c");
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        if let Some(slot) = self.get_array_mut(&key) {
            let v = mem::replace(slot, Some(value));

            if v.is_none() {
                self.len += 1;
            }

            v
        } else if let Some(node) = self.get_hash_mut(&key) {
            if let Some((_, ref mut v)) = *node.value_mut() {
                Some(mem::replace(v, value))
            } else {
                *node.value_mut() = Some((key, value));
                self.len += 1;
                None
            }
        } else {
            self.new_key(key, value);
            None
        }
    }

    /// Shrinks the capacity of the map as much as possible.
    ///
    /// Both the hash part and the array part will be at least half full.
    ///
    /// Note that this does not mean there will not be extra capacity. Due to
    /// internal requirements, the length of the array part and the length of
    /// the hash part are required to be powers of two.
    pub fn shrink_to_fit(&mut self) {
        self.do_rehash(None, true);
    }

    /// Rehashes the whole table, meaning that some entries might get moved to
    /// the array part, or vice-versa.
    pub fn force_rehash(&mut self) {
        self.do_rehash(None, false);
    }
}

impl<K: IntoIndex + FromIndex + Hash + Eq, V> Ham<K, V> {
    fn insert_and_get_mut(&mut self, key: K, value: V) -> &mut V {
        if let Some(idx) = self.get_array_idx_only(&key) {
            // To get it past the borrow checker...
            let slot = &mut self.array[idx];

            if slot.is_none() {
                self.len += 1;
            }

            slot.insert(value)
        } else if let Some(idx) = self.get_hash_idx_only(&key) {
            // To get it past the borrow checker...
            let node = &mut self.hash[idx];

            let entry = node.value_mut().take();

            if entry.is_none() {
                self.len += 1;
            }

            let key = if let Some((key, _)) = entry { key } else { key };

            &mut node.value_mut().insert((key, value)).1
        } else {
            self.new_key(key, value)
        }
    }

    // @@@   @@  @@@@@@  @@    @@  @@  @@  @@@@@@  @@  @@
    // @@@@  @@  @@      @@    @@  @@ @@   @@      @@  @@
    // @@ @@ @@  @@@@    @@ @@ @@  @@@@    @@@@    @@  @@
    // @@  @@@@  @@      @@ @@ @@  @@ @@   @@        @@
    // @@   @@@  @@@@@@   @@  @@   @@  @@  @@@@@@    @@
    /// This function shouldn't be called if `key` can fit in the array part.
    fn new_key(&mut self, key: K, value: V) -> &mut V {
        if self.hash.is_empty() {
            self.do_rehash(Some(&key), false);

            return self.insert_and_get_mut(key, value);
        }

        // A cell is used so that we can have multiple pointers without borrow conflicts.

        let main_pos = Self::main_position_cell(self as *mut _, &key);

        let mut emplaced = main_pos;

        if let Some((ref colliding_key, _)) = *unsafe { &*main_pos.as_ptr() }.value() {
            if let Some(free) = Self::get_free_pos_cell(self as *mut _) {
                // Make sure that free isn't already part of a chain, otherwise it
                // would be broken.
                // E.g:
                //
                // main_pos -> mp_next -> ...; free -> other -> ...
                //
                // Turns into
                //
                // main_pos -> free -> mp_next -> ...; !! -> other -> ...
                debug_assert_eq!(Node::next(free) as *const _, free as *const _);

                let mut other_main_pos = Self::main_position_cell(self as *mut _, colliding_key);

                if main_pos as *const _ != other_main_pos {
                    // Colliding node is out of its main position
                    // We move the colliding node into the free position
                    // then remove the main_pos from the chain.

                    // omp -> ... -> main_pos -> next -> ...

                    // We find the node that points to main_pos

                    while main_pos as *const _ != Node::next(other_main_pos) {
                        // debug_assert_ne!((&mut *other_main_pos).next_mut(), other_main_pos);

                        other_main_pos = Node::next(other_main_pos);
                    }

                    // omp -> main_pos -> next -> ...

                    Node::set_next(other_main_pos, free);

                    // omp -> free; main_pos -> next -> ...

                    let next = Node::next(main_pos);

                    free.set(main_pos.replace(Node {
                        inner: Some((key, value)),
                        next: 0,
                    }));

                    if next as *const _ != main_pos {
                        Node::set_next(free, next);
                    }

                    // omp -> ... -> free -> next -> ...; main_pos
                } else {
                    // Colliding node is in its main position
                    // New node goes into the free position and
                    // the chain is updated.

                    // main_pos -> mp_next -> ...; free

                    if Node::next(main_pos) as *const _ != main_pos {
                        Node::set_next(free, Node::next(main_pos));
                    }

                    Node::set_next(main_pos, free);

                    *unsafe { &mut *free.as_ptr() }.value_mut() = Some((key, value));

                    // main_pos -> free -> mp_next -> ...

                    emplaced = free;
                }
            } else {
                // If there isn't a free place, we rehash, then go through inserting normally.
                self.do_rehash(Some(&key), false);

                return self.insert_and_get_mut(key, value);
            }
        } else {
            // Not colliding => just insert
            *unsafe { &mut *main_pos.as_ptr() }.value_mut() = Some((key, value));
        }

        self.len += 1;

        &mut unsafe {
            (&mut *emplaced.as_ptr())
                .value_mut()
                .as_mut()
                .unwrap_unchecked()
        }
        .1
    }

    // @@@@    @@@@@@  @@  @@    @@    @@@@@@  @@  @@
    // @@  @@  @@      @@  @@  @@  @@  @@      @@  @@
    // @@@@    @@@@    @@@@@@  @@@@@@  @@@@@@  @@@@@@
    // @@  @@  @@      @@  @@  @@  @@      @@  @@  @@
    // @@  @@  @@@@@@  @@  @@  @@  @@  @@@@@@  @@  @@
    fn count_int(key: &K, nums: &mut Nums) -> bool {
        key.into_index()
            .map(|v| nums[ceil_log_2(v.get())] += 1)
            .is_some()
    }

    // The number of items that can be in an array that are in the hash part.
    //
    // returns (total_items, array_items)

    fn num_use_hash(&self, nums: &mut Nums) -> (usize, usize) {
        let mut total = 0;
        let mut a_use = 0;
        for v in &self.hash {
            if let Some((key, _)) = v.value().as_ref() {
                if Self::count_int(key, nums) {
                    a_use += 1;
                }
                total += 1;
            }
        }
        (total, a_use)
    }

    fn num_use_array(&self, nums: &mut Nums) -> usize {
        let mut a_use: usize = 0; // summation of nums

        let mut i = 0; // Current index

        for (lg, num) in nums.iter_mut().enumerate() {
            let ttlg = 1 << lg;

            let limit = core::cmp::min(ttlg, self.array.len());

            if i >= limit {
                break;
            }

            // count elements in range (2 ^ (lg - 1), 2 ^ lg)
            let count = self.array[i..limit]
                .iter()
                .filter_map(Option::as_ref)
                .count();

            i = limit;

            *num += count;
            a_use += count;
        }

        a_use
    }

    fn do_rehash(&mut self, key: Option<&K>, shrink: bool) {
        let mut nums: Nums = [0; NUMS_LEN];
        let mut na = self.num_use_array(&mut nums);

        let mut total_use = na;
        {
            let (total_add, na_add) = self.num_use_hash(&mut nums);
            total_use += total_add;
            na += na_add;
        }

        if let Some(key) = key {
            if Self::count_int(key, &mut nums) {
                na += 1;
            }
            total_use += 1;
        }

        let (asize, na) = compute_sizes(&nums, na);

        // pna is the total number of integer keys in the table.
        // nums is an array of keys in sections of 2^i

        // return is (new_arr_size, num_keys_in_arr)

        fn compute_sizes(nums: &Nums, pna: usize) -> (usize, usize) {
            let mut a = 0; // no. of elements < 2^i

            let mut na = 0; // no. of elements to go to array part

            let mut optimal = 0; // optimal size for array part.

            // loop while keys can fill more than half of total size

            for (two_to_i, num) in nums
                .iter()
                .copied()
                .enumerate()
                .map(|(i, num)| (1 << i, num))
            {
                if pna <= two_to_i / 2 {
                    break;
                }

                a += num;

                // more than half elements present?
                if a > two_to_i / 2 {
                    optimal = two_to_i; // optimal size (till now)
                    na = a; // all elements up to optimal will go in array part
                }
            }

            debug_assert!(
                (optimal == 0 || optimal / 2 < na) && na <= optimal,
                "optimal = {optimal}; na = {na}",
                optimal = optimal,
                na = na,
            );

            (optimal, na)
        }

        self.resize(asize, total_use - na, shrink);
    }

    // @@@@    @@@@@@  @@@@@@  @@@@@@  @@@@@@  @@@@@@
    // @@  @@  @@      @@        @@       @@   @@
    // @@@@    @@@@    @@@@@@    @@      @@    @@@@
    // @@  @@  @@          @@    @@     @@     @@
    // @@  @@  @@@@@@  @@@@@@  @@@@@@  @@@@@@  @@@@@@
    fn resize(&mut self, array_part: usize, hash_part: usize, shrink: bool) {
        // Make sure we don't break the invariant
        let mut hash_part = round_pow_2(hash_part);

        let old_hash = mem::replace(&mut self.hash, {
            let mut v = Vec::with_capacity(hash_part);
            let c = round_down_pow_2(v.capacity());
            if c > hash_part {
                // Use any excess capacity
                hash_part = c;
            }
            v.resize_with(hash_part, Node::default);
            v
        });
        let hash_part = hash_part; // Make immut

        self.last_free = hash_part;

        let mut array_part = array_part;

        let array_grew = if array_part > self.array.len() {
            self.array.resize_with(array_part, Option::default);
            let c = round_down_pow_2(self.array.capacity());
            if c > array_part {
                // Use any excess capacity
                array_part = c;
                self.array.resize_with(array_part, Option::default);
            }
            true
        } else {
            false
        };

        let array_part = array_part;

        let len = self.len;

        if array_part < self.array.len() {
            // We replace the arrays so that the borrow checker doesn't complain
            // when we insert new keys below.
            let mut array = mem::take(&mut self.array);

            for (i, item) in array.drain(array_part..).enumerate() {
                if let Some(item) = item {
                    self.new_key(
                        K::from_index(unsafe { Idx::new_unchecked(array_part + i + 1) }),
                        item,
                    ); // Insert into the hash part.
                }
            }

            if shrink {
                array.shrink_to_fit();
            }

            self.array = array;
        }

        for node in old_hash {
            if let Some((k, v)) = node.into_inner() {
                if array_grew {
                    // Insert into the new table.
                    // This could go into the array, so we use self.insert
                    self.insert(k, v);
                } else {
                    // Insert into the new hash part.
                    self.new_key(k, v);
                }
            }
        }

        self.len = len; // Fix up the length
    }
}

impl<K, V> Ham<K, V> {
    // @@@@@@  @@@@@@  @@@@@@  @@@@@@  @@@@@@  @@@@    @@@@@@
    // @@      @@        @@      @@    @@      @@  @@  @@
    // @@ @@@  @@@@      @@      @@    @@@@    @@@@    @@@@@@
    // @@  @@  @@        @@      @@    @@      @@  @@      @@
    // @@@@@@  @@@@@@    @@      @@    @@@@@@  @@  @@  @@@@@@
    fn get_array_idx_only<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<usize> {
        let v = key.into_index()?.get().get() - 1;

        self.array.get(v).map(|_| v)
    }

    fn get_array_idx<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<(Idx<Q>, &Option<V>)> {
        key.into_index()
            .and_then(|v| Some((v.clone(), self.array.get(v.get().get() - 1)?)))
    }

    fn get_array_idx_mut<Q: ?Sized + IntoIndex>(
        &mut self,
        key: &Q,
    ) -> Option<(Idx<Q>, &mut Option<V>)> {
        key.into_index()
            .and_then(move |v| Some((v.clone(), self.array.get_mut(v.get().get() - 1)?)))
    }

    fn get_array<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<&Option<V>> {
        key.into_index()
            .and_then(|v| self.array.get(v.get().get() - 1))
    }

    fn get_array_mut<Q: ?Sized + IntoIndex>(&mut self, key: &Q) -> Option<&mut Option<V>> {
        key.into_index()
            .and_then(move |v| self.array.get_mut(v.get().get() - 1))
    }

    fn get_array_take<Q: ?Sized + IntoIndex>(&mut self, key: &Q) -> Option<V> {
        self.get_array_mut(key).and_then(Option::take)
    }

    fn get_hash_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Node<K, V>>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        if self.hash.is_empty() {
            None
        } else {
            let mut v = Self::main_position_cell(self as *mut _, key);
            while !Node::matches(v, key) {
                let new_v = Node::next(v);
                if new_v as *const _ == v {
                    return None; // There wasn't a chain.
                }
                v = new_v;
            }
            Some(unsafe { &mut *v.as_ptr() })
        }
    }

    fn get_hash_mut_for_take<Q: ?Sized>(&mut self, key: &Q) -> Option<(&mut Node<K, V>, bool)>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        if self.hash.is_empty() {
            None
        } else {
            let mut v = Self::main_position_cell(self as *mut _, key);

            let mut prev_v = None;
            while !Node::matches(v, key) {
                let new_v = Node::next(v);
                if new_v as *const _ == v {
                    return None; // There wasn't a chain.
                }
                prev_v = Some(v);
                v = new_v;
            }

            Some(if let Some(prev) = prev_v {
                (unsafe { &mut *prev.as_ptr() }, true)
            } else {
                (unsafe { &mut *v.as_ptr() }, false)
            })
        }
    }

    fn get_hash_take<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        if self.hash.is_empty() {
            None
        } else {
            let mut v = Self::main_position_cell(self as *mut _, key);
            let mut prev_v = None;

            // Follow the chain around
            while !Node::matches(v, key) {
                let new_v = Node::next(v);
                if new_v as *const _ == v {
                    // v -> v -> v ...
                    return None; // There wasn't a chain.
                }
                prev_v = Some(v);
                v = new_v;
            }

            let v_next = Node::next(v);

            {
                #[allow(clippy::cast_sign_loss)]
                let num = unsafe { v.as_ptr().offset_from(self.hash.as_ptr()) } as usize;
                if num > self.last_free {
                    self.last_free = num;
                }
            }

            let out = if let Some(prev_v) = prev_v {
                if v_next as *const _ == v {
                    // prev_v -> v
                    Node::set_next(prev_v, prev_v);
                    // prev_v; v
                } else {
                    // prev_v -> v -> v_next -> ...
                    Node::set_next(prev_v, v_next);
                    // prev_v -> v_next -> ...; v -> v_next -> ...
                }

                unsafe { &mut *v.as_ptr() }.value_mut().take()
            } else if v_next as *const _ != v {
                // INVARIANT: All the keys in the chain hash to `v`

                // v -> v_next -> v_next_next -> ...

                // We move v_next into v and return the value of v

                let v_next_next = Node::next(v_next);

                let v_next_value = v_next.replace(Node::default());

                let v_value = v.replace(v_next_value);

                // We now fix the pointer in v_next_value

                // If there was something after v_next, then set it
                if v_next_next as *const _ != v_next {
                    Node::set_next(v, v_next_next);
                }

                // v_next (in *v) -> v_next_next -> ...

                v_value.into_inner()
            } else {
                // v doesn't point to anything.

                unsafe { &mut *v.as_ptr() }.value_mut().take()
            };

            Node::set_next(v, v);

            out
        }
    }

    fn get_hash<Q: ?Sized>(&self, key: &Q) -> Option<&Node<K, V>>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        if self.hash.is_empty() {
            None
        } else {
            let mut v = self.main_position(key);
            while !v.matches_ref(key) {
                let new_v = v.next_ref();
                if new_v as *const _ == v {
                    return None; // There wasn't a chain.
                }
                v = new_v;
            }
            Some(v)
        }
    }

    fn get_hash_idx_only<Q: ?Sized>(&self, key: &Q) -> Option<usize>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        self.get_hash_idx(key).map(|v| v.0)
    }

    fn get_hash_idx<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &Node<K, V>)>
    where
        Q: Hash + Eq,
        K: Borrow<Q>,
    {
        if self.hash.is_empty() {
            None
        } else {
            let mut v = self.main_position(key);
            while !v.matches_ref(key) {
                let new_v = v.next_ref();
                if new_v as *const _ == v {
                    return None; // There wasn't a chain.
                }
                v = new_v;
            }
            #[allow(clippy::cast_sign_loss)]
            Some((
                unsafe { (v as *const Node<K, V>).offset_from(self.hash.as_ptr()) } as usize,
                v,
            ))
        }
    }

    // @@      @@    @@    @@@@@@  @@@   @@  @@@@    @@@@@@  @@@@@@
    // @@@@  @@@@  @@  @@    @@    @@@@  @@  @@  @@  @@  @@  @@
    // @@  @@  @@  @@@@@@    @@    @@ @@ @@  @@@@    @@  @@  @@@@@@
    // @@      @@  @@  @@    @@    @@  @@@@  @@      @@  @@      @@
    // @@      @@  @@  @@  @@@@@@  @@   @@@  @@      @@@@@@  @@@@@@
    /// Returns a reference to the position of a key in the table
    fn main_position<Q: ?Sized + Hash>(&self, key: &Q) -> &Node<K, V> {
        let mut hasher = self.hash_builder.build_hasher();
        key.hash(&mut hasher);

        debug_assert!(self.hash.len().is_power_of_two());

        let idx = (hasher.finish() as usize) % self.hash.len();

        &self.hash[idx]
    }

    /// Returns a reference to the position of a key in the table
    fn main_position_cell<'a, Q: ?Sized + Hash>(this: *mut Self, key: &Q) -> &'a Cell<Node<K, V>> {
        let mut hasher = unsafe { (*this).hash_builder }.build_hasher();

        key.hash(&mut hasher);

        // debug_assert!(self.hash.len().is_power_of_two());

        let h = unsafe { &mut (*this).hash };

        let idx = (hasher.finish() as usize) % h.len();

        // Don't make any references into the buffer

        // SAFETY: idx < self.hash.len()
        unsafe { &*h.as_mut_ptr().add(idx).cast::<Cell<Node<K, V>>>() }
    }

    fn get_free_pos_cell<'a>(this: *mut Self) -> Option<&'a Cell<Node<K, V>>> {
        // self.last_free = self.hash.len();
        for i in (0..unsafe { (*this).last_free }).rev() {
            // Don't make any references into the buffer

            // SAFETY: idx < self.hash.len()
            let node = unsafe { &*(*this).hash.as_mut_ptr().add(i).cast::<Cell<Node<K, V>>>() };

            if unsafe { &*node.as_ptr() }.value().is_none() {
                unsafe {
                    (*this).last_free = i;
                } // It is actually last free + 1
                return Some(node);
            }
        }
        None
    }
}

impl<K, Q: ?Sized, V> Index<&Q> for Ham<K, V>
where
    K: Hash + Eq + Borrow<Q>,
    Q: IntoIndex + Hash + Eq,
{
    type Output = V;

    fn index(&self, key: &Q) -> &V {
        self.get(key).expect("no entry found for key")
    }
}

impl<K, Q: ?Sized, V> IndexMut<&Q> for Ham<K, V>
where
    K: Hash + Eq + Borrow<Q>,
    Q: IntoIndex + Hash + Eq,
{
    fn index_mut(&mut self, key: &Q) -> &mut V {
        self.get_mut(key).expect("no entry found for key")
    }
}

#[cfg(feature = "std")]
impl<K, V> FromIterator<(K, V)> for Ham<K, V>
where
    K: IntoIndex + FromIndex + Hash + Eq,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = (K, V)>,
    {
        let mut map = Self::new();
        map.extend(iter);
        map
    }
}

impl<K, V> Extend<(K, V)> for Ham<K, V>
where
    K: IntoIndex + FromIndex + Hash + Eq,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = (K, V)>,
    {
        for (k, v) in iter {
            self.insert(k, v);
        }
    }
}

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

    const SIZE: usize = 1000;

    #[test]
    fn test_insert() {
        let mut hash_map = Ham::with_seed(0);

        for i in 0..SIZE {
            hash_map.insert(i, i);
        }
    }

    #[test]
    fn test_insert_remove() {
        let mut hash_map = Ham::with_seed(0);

        for i in 0..SIZE {
            hash_map.insert(i, i);
        }

        for i in 0..SIZE {
            hash_map.insert(i + SIZE, i);
            hash_map.remove(&i);
            hash_map.shrink_to_fit();
        }
    }

    #[test]
    fn test_insert_remove_2() {
        let mut hash_map = Ham::with_seed(0);

        for i in 0..100 {
            hash_map.insert(i, i);
        }

        for i in 0..100 {
            hash_map.insert(i + 100, i);
            hash_map.remove(&i);
        }
    }
}