/*!
# pour
[![crates.io](https://img.shields.io/crates/v/pour)](https://crates.io/crates/pour)
[![Downloads](https://img.shields.io/crates/d/pour)](https://crates.io/crates/pour)
[![Documentation](https://docs.rs/pour/badge.svg)](https://docs.rs/pour/)
[![Pipeline status](https://gitlab.com/tekne/pour/badges/master/pipeline.svg)](https://gitlab.com/tekne/pour)
[![codecov](https://codecov.io/gl/tekne/pour/branch/\x6d6173746572/graph/badge.svg?token=N7O4T3PAFA)](https://codecov.io/gl/tekne/pour/)
[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT)

`pour` is an implementation of an immutable `IdMap`: it maps bitvector IDs to values using a radix trie.

Since these `IdMap`s are immutable, they can share a *lot* of data between them, and hash-consing can be used to increase the
degree of sharing between `IdMap`s. More interestingly, this data structure is designed to support asymptotically fast set operations
on hash-consed `IdMaps`, including:
- Unions, intersections, (symmetric) differences, and complements
- Subset/superset checks

The best part is, the more memory shared, the faster these operations become in the general case (though the specialized `ptr`
variants of these operations may return *incorrect* values on non hash-consed, i.e. maximally shared, inputs!) To allow user
customized hash-consing strategies, the internal `Arc`s behind this data structure can be exposed as opaque objects which the
user may manipulate using the `ConsCtx` trait. Alternatively, `()` implements `SetCtx` with no consing, and there are helpers
to perform set operations without consing.

There are also some nice implementation details (which *may change*), including:
- `IdMap<K, V>` and hence `IdSet<K>` are the size of a pointer.
- `NonEmptyIdMap<K, V>` and hence `NonEmptyIdSet<K>` are the size of a pointer
*and* null-pointer optimized, i.e. `Option<NonEmptySet<T>>` is also the size of a pointer.

Right now, the feature-set is deliberately kept somewhat minimal, as `pour` has a particular use case (the `rain` intermediate
representation). But if I have time and/or anyone wants to contribute, all kinds of things can be added! Examples of potential
**future** features include
- Map not just from integer keys but from integer ranges, with similar efficiency
- Union maps of different types

`pour` is currently implemented without any `unsafe`, though that may change. We do, however use the non-standard `elysees` `Arc`
implementation (a fork of Servo's `triomphe` by the author) to avoid weak reference counts.

NOTE: "levels" are currently not yet supported! Returning a level number greater than 0 will cause a panic!

Contributions, questions, and issues are welcome! Please file issues at https://gitlab.com/tekne/pour, and contact the author at
jad.ghalayini@gtc.ox.ac.uk for any other queries.
*/
#![forbid(unsafe_code, missing_debug_implementations, missing_docs)]
use elysees::Arc;
use num_traits::{int::PrimInt, AsPrimitive, ToPrimitive};
use ref_cast::RefCast;
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::fmt::Debug;
use std::hash::{Hash, Hasher};
use std::iter::FromIterator;

mod inner;
mod map_impls;
mod util;

pub use inner::{IdMapIntoIter, IdMapIter, InnerMap};
pub use util::*;

pub mod map_ctx;
pub mod mutation;
use mutation::*;

/// An immutable, optionally hash-consed pointer-sized map from small integer keys to arbitrary data
#[derive(Debug, Clone)]
#[repr(transparent)]
pub struct IdMap<K: RadixKey, V: Clone>(Option<Arc<InnerMap<K, V>>>);

/// An immutable, optionally hash-consed pointer-sized set of small integer keys
pub type IdSet<K> = IdMap<K, ()>;

impl<K: RadixKey, V: Clone> IdMap<K, V> {
    /// A constant representing an empty map
    pub const EMPTY: IdMap<K, V> = IdMap(None);
    /// Create a new, empty map
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let empty = IdMap::<u64, u64>::new();
    /// assert!(empty.is_empty());
    /// assert_eq!(empty.len(), 0);
    /// assert_eq!(empty, IdMap::new());
    /// ```
    pub fn new() -> IdMap<K, V> {
        IdMap(None)
    }
    /// Clear this map, returning it's `InnerMap` if it was nonempty
    pub fn clear(&mut self) -> Option<Arc<InnerMap<K, V>>> {
        let mut result = None;
        std::mem::swap(&mut self.0, &mut result);
        result
    }
    /// Create a new mapping containing a single element in a given context
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// # use pour::map_ctx::MapCtx;
    /// let mut ctx1 = MapCtx::<u64, u64>::default();
    /// let mut ctx2 = MapCtx::<u64, u64>::default();
    /// let x = IdMap::singleton_in(5, 7, &mut ctx1);
    /// let y = IdMap::singleton_in(5, 7, &mut ctx2);
    /// let z = IdMap::singleton_in(5, 7, &mut ctx1);
    /// assert_eq!(x, y);
    /// assert_eq!(x, z);
    /// assert_ne!(x.as_ptr(), y.as_ptr());
    /// assert_eq!(x.as_ptr(), z.as_ptr());
    /// ```
    pub fn singleton_in<C: ConsCtx<K, V>>(key: K, value: V, ctx: &mut C) -> IdMap<K, V> {
        IdMap(Some(ctx.cons(InnerMap::singleton(key, value))))
    }
    /// Get the pointer underlying this map
    ///
    /// This pointer is guaranteed to be null if and only if the map is empty
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert_eq!(x.as_ptr(), std::ptr::null());
    /// x.try_insert(3, 5);
    /// assert_ne!(x.as_ptr(), std::ptr::null());
    /// let mut y = IdMap::singleton(3, 5);
    /// assert_ne!(y.as_ptr(), std::ptr::null());
    /// assert_ne!(x.as_ptr(), y.as_ptr());
    /// assert_eq!(x, y);
    /// ```
    pub fn as_ptr(&self) -> *const InnerMap<K, V> {
        self.0.as_ref().map(Arc::as_ptr).unwrap_or(std::ptr::null())
    }
    /// Check whether two `IdMap`s are pointer-equal, i.e. point to the same data
    pub fn ptr_eq(&self, other: &Self) -> bool {
        self.as_ptr() == other.as_ptr()
    }
    /// Create a new mapping containing a single element
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, "Hello");
    /// assert_eq!(x.len(), 1);
    /// assert_eq!(x.get(&3), Some(&"Hello"));
    /// assert_eq!(x.get(&2), None);
    /// ```
    pub fn singleton(key: K, value: V) -> IdMap<K, V> {
        Self::singleton_in(key, value, &mut ())
    }
    /// Check whether this map is empty
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert!(x.is_empty());
    /// x.try_insert(5, 33);
    /// assert!(!x.is_empty());
    /// x.remove(&5);
    /// assert!(x.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.0.is_none()
    }
    /// Get the number of entries in this map
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert_eq!(x.len(), 0);
    /// x.try_insert(7, 3);
    /// assert_eq!(x.len(), 1);
    /// x.try_insert(3, 2);
    /// assert_eq!(x.len(), 2);
    /// x.try_insert(2, 1);
    /// assert_eq!(x.len(), 3);
    /// x.remove(&2);
    /// assert_eq!(x.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.0.as_ref().map(|inner| inner.len()).unwrap_or(0)
    }
    /// Iterate over the entries in this map
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// x.try_insert(5, "what");
    /// x.try_insert(3, "buy");
    /// x.try_insert(7, "sell");
    /// let mut v: Vec<_> = x.iter().collect();
    /// v.sort_unstable();
    /// assert_eq!(&v[..], &[
    ///     (&3, &"buy"),
    ///     (&5, &"what"),
    ///     (&7, &"sell"),
    /// ])
    /// ```
    pub fn iter(&self) -> IdMapIter<K, V> {
        let mut result = IdMapIter::empty();
        if let Some(inner) = &self.0 {
            result.root(inner)
        }
        result
    }
    /// Lookup and mutate an entry of an `IdMap` in a given context. Return a new map if any changes were made.
    ///
    /// If it exists, the value is passed to the callback. If not, `None` is passed in it's place.
    /// The mutation returned from the callback is returned, along with the other result.
    pub fn mutate_in<B, M, R, C>(&self, key: B, action: M, ctx: &mut C) -> (Option<IdMap<K, V>>, R)
    where
        B: Borrow<K>,
        M: FnOnce(B, Option<&V>) -> (Mutation<K, V>, R),
        C: ConsCtx<K, V>,
    {
        if let Some(inner) = &self.0 {
            let (try_inner, result) = inner.mutate(inner, key, action, ctx);
            if let Some(inner) = try_inner {
                (Some(inner.into_idmap_in(ctx)), result)
            } else {
                (None, result)
            }
        } else {
            let (mutation, result) = action(key, None);
            let new_map = match mutation {
                Mutation::Null => None,
                Mutation::Remove => None,
                Mutation::Update(_) => None,
                Mutation::Insert(key, value) => Some(IdMap::singleton(key, value)),
            };
            (new_map, result)
        }
    }
    /// Lookup and mutate an entry of an `IdMap`. Return a new map if any changes were made.
    ///
    /// If it exists, the value is passed to the callback. If not, `None` is passed in it's place.
    /// The mutation returned from the callback is returned, along with the other result.
    pub fn mutate<B, M, R>(&self, key: B, action: M) -> (Option<IdMap<K, V>>, R)
    where
        B: Borrow<K>,
        M: FnOnce(B, Option<&V>) -> (Mutation<K, V>, R),
    {
        self.mutate_in(key, action, &mut ())
    }
    /// Remove an entry from an `IdMap` in a given context: return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 5);
    /// assert_eq!(x.removed_in(&3, &mut ()), Some(IdMap::new()));
    /// assert_eq!(x.removed_in(&5, &mut ()), None);
    /// ```
    pub fn removed_in<C: ConsCtx<K, V>>(&self, key: &K, ctx: &mut C) -> Option<IdMap<K, V>> {
        self.mutate_in(key, |_key, _value| (Mutation::Remove, ()), ctx)
            .0
    }
    /// Remove an entry from an `IdMap`: return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 5);
    /// assert_eq!(x.removed(&3), Some(IdMap::new()));
    /// assert_eq!(x.removed(&5), None);
    /// ```
    pub fn removed(&self, key: &K) -> Option<IdMap<K, V>> {
        self.removed_in(key, &mut ())
    }
    /// Remove an entry from an `IdMap` in a given context, *keeping the old value* if one was already there.
    /// Return whether any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::singleton(3, 5);
    /// let y = x.clone();
    /// assert!(!x.remove_in(&5, &mut ()));
    /// assert_eq!(x, y);
    /// assert!(x.remove_in(&3, &mut ()));
    /// assert_eq!(x, IdMap::new());
    /// ```
    pub fn remove_in<C: ConsCtx<K, V>>(&mut self, key: &K, ctx: &mut C) -> bool {
        if let Some(removed) = self.removed_in(key, ctx) {
            *self = removed;
            true
        } else {
            false
        }
    }
    /// Remove an entry from an `IdMap`, *keeping the old value* if one was already there.
    /// Return whether any changes were made
    ///  
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::singleton(3, 5);
    /// let y = x.clone();
    /// assert!(!x.remove(&5));
    /// assert_eq!(x, y);
    /// assert!(x.remove(&3));
    /// assert_eq!(x, IdMap::new());
    /// ```
    pub fn remove(&mut self, key: &K) -> bool {
        if let Some(removed) = self.removed(key) {
            *self = removed;
            true
        } else {
            false
        }
    }
    /// Insert an entry into an `IdMap` in a given context, *replacing the old value* if one was already there.
    /// Return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 2);
    /// assert_eq!(
    ///     x.inserted_in(3, 5, &mut ()),
    ///     Some(IdMap::singleton(3, 5))
    /// );
    /// let y = x.inserted_in(4, 5, &mut ()).unwrap();
    /// assert_ne!(x, y);
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert_eq!(x.get(&4), None);
    /// assert_eq!(y.get(&3), Some(&2));
    /// assert_eq!(y.get(&4), Some(&5));
    pub fn inserted_in<C: ConsCtx<K, V>>(
        &self,
        key: K,
        value: V,
        ctx: &mut C,
    ) -> Option<IdMap<K, V>> {
        self.mutate_in(
            key,
            |key, old_value| {
                (
                    if old_value.is_none() {
                        Mutation::Insert(key, value)
                    } else {
                        Mutation::Update(value)
                    },
                    (),
                )
            },
            ctx,
        )
        .0
    }
    /// Insert an entry into an `IdMap`, *replacing the old value* if one was already there.
    /// Return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 2);
    /// assert_eq!(
    ///     x.inserted(3, 5),
    ///     Some(IdMap::singleton(3, 5))
    /// );
    /// let y = x.inserted(4, 5).unwrap();
    /// assert_ne!(x, y);
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert_eq!(x.get(&4), None);
    /// assert_eq!(y.get(&3), Some(&2));
    /// assert_eq!(y.get(&4), Some(&5));
    /// ```
    pub fn inserted(&self, key: K, value: V) -> Option<IdMap<K, V>> {
        self.inserted_in(key, value, &mut ())
    }
    /// Insert an entry into an `IdMap` in a given context, *replacing the old value* if one was already there.
    /// Return whether any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert!(x.insert_in(3, 2, &mut ()));
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert!(x.insert_in(3, 5, &mut ()));
    /// assert_eq!(x.get(&3), Some(&5));
    /// ```
    pub fn insert_in<C: ConsCtx<K, V>>(&mut self, key: K, value: V, ctx: &mut C) -> bool {
        if let Some(inserted) = self.inserted_in(key, value, ctx) {
            *self = inserted;
            true
        } else {
            false
        }
    }
    /// Insert an entry into an `IdMap`, *replacing the old value* if one was already there.
    /// Return whether any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert!(x.insert(3, 2));
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert!(x.insert(3, 5));
    /// assert_eq!(x.get(&3), Some(&5));
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> bool {
        if let Some(inserted) = self.inserted(key, value) {
            *self = inserted;
            true
        } else {
            false
        }
    }
    /// Insert an entry into an `IdMap` in a given context, *keeping the old value* if one was already there.
    /// Return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 2);
    /// assert_eq!(x.try_inserted_in(3, 5, &mut ()), None);
    /// let y = x.try_inserted_in(4, 5, &mut ()).unwrap();
    /// assert_ne!(x, y);
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert_eq!(x.get(&4), None);
    /// assert_eq!(y.get(&3), Some(&2));
    /// assert_eq!(y.get(&4), Some(&5));
    pub fn try_inserted_in<C: ConsCtx<K, V>>(
        &self,
        key: K,
        value: V,
        ctx: &mut C,
    ) -> Option<IdMap<K, V>> {
        self.mutate_in(key, |key, _value| (Mutation::Insert(key, value), ()), ctx)
            .0
    }
    /// Insert an entry into an `IdMap`, *keeping the old value* if one was already there.
    /// Return a new map if any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(3, 2);
    /// assert_eq!(x.try_inserted(3, 5), None);
    /// let y = x.try_inserted(4, 5).unwrap();
    /// assert_ne!(x, y);
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert_eq!(x.get(&4), None);
    /// assert_eq!(y.get(&3), Some(&2));
    /// assert_eq!(y.get(&4), Some(&5));
    /// ```
    pub fn try_inserted(&self, key: K, value: V) -> Option<IdMap<K, V>> {
        self.try_inserted_in(key, value, &mut ())
    }
    /// Insert an entry into an `IdMap` in a given context, *keeping the old value* if one was already there.
    /// Return whether any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert!(x.try_insert_in(3, 2, &mut ()));
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert!(!x.try_insert_in(3, 5, &mut ()));
    /// assert_eq!(x.get(&3), Some(&2));
    /// ```
    pub fn try_insert_in<C: ConsCtx<K, V>>(&mut self, key: K, value: V, ctx: &mut C) -> bool {
        if let Some(inserted) = self.try_inserted_in(key, value, ctx) {
            *self = inserted;
            true
        } else {
            false
        }
    }
    /// Insert an entry into an `IdMap`, *keeping the old value* if one was already there.
    /// Return whether any changes were made
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::new();
    /// assert!(x.try_insert(3, 2));
    /// assert_eq!(x.get(&3), Some(&2));
    /// assert!(!x.try_insert(3, 5));
    /// assert_eq!(x.get(&3), Some(&2));
    /// ```
    pub fn try_insert(&mut self, key: K, value: V) -> bool {
        if let Some(inserted) = self.try_inserted(key, value) {
            *self = inserted;
            true
        } else {
            false
        }
    }
    /// Lookup an entry of an `IdMap`, returning the value associated with it, if any
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let mut x = IdMap::singleton(3, 5);
    /// assert_eq!(x.get(&3), Some(&5));
    /// assert_eq!(x.get(&2), None);
    /// x.try_insert(2, 4);
    /// assert_eq!(x.get(&2), Some(&4));
    /// x.insert_conservative(2, 2);
    /// assert_eq!(x.get(&2), Some(&2));
    /// ```
    pub fn get(&self, key: &K) -> Option<&V> {
        if let Some(inner) = &self.0 {
            inner.get(key)
        } else {
            None
        }
    }
    /// Lookup whether an item is contained in an `IdMap`.
    ///
    /// # Example
    /// ```rust
    /// # use pour::IdMap;
    /// let x = IdMap::singleton(7, 3);
    /// assert!(x.contains(&7));
    /// assert!(!x.contains(&3));
    /// ```
    pub fn contains(&self, key: &K) -> bool {
        self.get(key).is_some()
    }
    /// Mutate the values of a map in a given context. Return `Some` if something changed.
    ///
    /// # Example
    /// ```rust
    /// # use pour::{IdMap, mutation::FilterMap};
    /// let x = IdMap::singleton(3, 5);
    /// let mut mutator = FilterMap::new(
    ///     |key, value| if key == value { None } else { Some(key * value) }
    /// );
    /// let y = x.mutated_vals_in(&mut mutator, &mut ());
    /// assert_eq!(y, Some(IdMap::singleton(3, 15)));
    /// ```
    pub fn mutated_vals_in<M, C>(&self, mutator: &mut M, ctx: &mut C) -> Option<IdMap<K, V>>
    where
        M: UnaryMutator<K, V>,
        C: ConsCtx<K, V>,
    {
        match (mutator.kind(), &self.0) {
            (UnaryMutatorKind::Null, _) => None,
            (_, None) => None,
            (UnaryMutatorKind::Delete, Some(_)) => Some(IdMap::new()),
            (UnaryMutatorKind::General, Some(inner)) => {
                let inner = inner.mutate_vals_in(mutator, ctx)?;
                Some(inner.into_idmap_in(ctx))
            }
        }
    }
    /// Mutate the values of a map. Return `Some` if something changed.
    #[inline]
    pub fn mutated_vals<M>(&self, mutator: &mut M) -> Option<IdMap<K, V>>
    where
        M: UnaryMutator<K, V>,
    {
        self.mutated_vals_in(mutator, &mut ())
    }
    /// Mutate the values of a map. Return if something changed.
    #[inline]
    pub fn mutate_vals_in<M, C>(&mut self, mutator: &mut M, ctx: &mut C) -> bool
    where
        M: UnaryMutator<K, V>,
        C: ConsCtx<K, V>,
    {
        if let Some(mutated) = self.mutated_vals_in(mutator, ctx) {
            *self = mutated;
            true
        } else {
            false
        }
    }
    /// Mutate the values of a map. Return if something changed.
    ///
    /// # Examples
    /// ```rust
    /// # use pour::IdMap;
    /// # use pour::mutation::{NullMutator, DeleteMutator, FilterMap};
    /// let mut x = IdMap::new();
    /// for i in 0..100 {
    ///     x.try_insert(i, 3);
    /// }
    ///
    /// let mut y = x.clone();
    /// assert!(!y.mutate_vals(&mut NullMutator));
    /// assert_eq!(x.as_ptr(), y.as_ptr());
    ///
    /// let mut mutator = FilterMap::new(
    ///     |key, value| if *key < 30 { None } else { Some(*key * *value) }
    /// );
    /// assert!(y.mutate_vals(&mut mutator));
    /// assert_ne!(x, y);
    /// assert_eq!(y.len(), 70);
    /// assert_eq!(x.get(&4), Some(&3));
    /// assert_eq!(y.get(&4), None);
    /// assert_eq!(x.get(&40), Some(&3));
    /// assert_eq!(y.get(&40), Some(&120));
    ///
    /// assert!(x.mutate_vals(&mut mutator));
    /// assert_ne!(x.as_ptr(), y.as_ptr());
    /// assert_eq!(x, y);
    ///
    /// assert!(y.mutate_vals(&mut DeleteMutator));
    /// assert!(y.is_empty());
    /// ```
    #[inline]
    pub fn mutate_vals<M>(&mut self, mutator: &mut M) -> bool
    where
        M: UnaryMutator<K, V>,
    {
        if let Some(mutated) = self.mutated_vals_in(mutator, &mut ()) {
            *self = mutated;
            true
        } else {
            false
        }
    }
    /*
    /// Transform the values of a map in a given context.
    pub fn transformed_vals_in<T, O, C>(&self, transformer: &mut T, ctx: &mut C) -> IdMap<K, O>
    where
        O: Clone,
        T: UnaryTransformer<K, V, O>,
        C: ConsCtx<K, O>,
    {
        if let Some(inner) = &self.0 {
            unimplemented!("Inner transformation @ {:p}", inner)
        } else {
            // No keys to transform!
            IdMap::new()
        }
    }
    */
    /// Join-mutate two maps by applying a binary mutator to their key intersection and unary
    /// mutators to their left and right intersection. If `cons` is true, the maps are assumed to
    /// be consistently hash-consed (i.e. an `InnerMap` in one map is `rec_eq` to one in another map
    /// if and only if they are pointer-equal, i.e. compare equal with `==`), which can provide
    /// additional speedup. Return `Some` if something changed.
    pub fn join_mutate_in<IM, LM, RM, C>(
        &self,
        other: &Self,
        intersection_mutator: &mut IM,
        left_mutator: &mut LM,
        right_mutator: &mut RM,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>>
    where
        IM: BinaryMutator<K, V>,
        LM: UnaryMutator<K, V>,
        RM: UnaryMutator<K, V>,
        C: ConsCtx<K, V>,
    {
        let (this, other) = match (&self.0, &other.0) {
            (_, None) => return BinaryResult::or_left(self.mutated_vals_in(left_mutator, ctx)),
            (None, _) => return BinaryResult::or_right(other.mutated_vals_in(right_mutator, ctx)),
            (Some(this), Some(other)) => (this, other),
        };
        this.join_mutate_in(
            other,
            intersection_mutator,
            left_mutator,
            right_mutator,
            ctx,
        )
        .map(|inner| inner.into_idmap_in(ctx))
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn left_union_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut NullMutator,
            &mut NullMutator,
            ctx,
        )
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn left_intersect_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn left_union(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut NullMutator,
            &mut NullMutator,
            &mut (),
        )
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn left_intersect(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the right value
    pub fn right_union_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut NullMutator,
            &mut NullMutator,
            ctx,
        )
    }
    /// Take the intersection of two maps, taking the right value in case of conflict
    pub fn right_intersect_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the right value
    pub fn right_union(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut NullMutator,
            &mut NullMutator,
            &mut (),
        )
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn right_intersect(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, it is unspecified which of the two values is in the result
    pub fn union_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut NullMutator,
            &mut NullMutator,
            ctx,
        )
    }
    /// Take the intersection of two maps, taking an unspecified value in case of conflict
    pub fn intersect_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the symmetric difference of two maps
    pub fn sym_diff_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut DeleteMutator,
            &mut NullMutator,
            &mut NullMutator,
            ctx,
        )
    }
    /// Take the complement of this map's *entries* with respect to another's *keys*
    pub fn left_complement_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the complement of this map's *keys* with respect to another's *entries*
    pub fn right_complement_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the complement of this map' with another, arbitrarily returning this map's or the other's values on the intersection!
    pub fn complement_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            ctx,
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, it is unspecified which of the two values is in the result
    pub fn union(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut NullMutator,
            &mut NullMutator,
            &mut (),
        )
    }
    /// Take the intersection of two maps, taking an unspecified value in case of conflict
    pub fn intersect(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut DeleteMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the symmetric difference of two maps
    pub fn sym_diff(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut DeleteMutator,
            &mut NullMutator,
            &mut NullMutator,
            &mut (),
        )
    }
    /// Take the complement of this map's *entries* with respect to another's *keys*
    pub fn left_complement(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut LeftMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the complement of this map's *keys* with respect to another's *entries*
    pub fn right_complement(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut RightMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the complement of this map' with another, arbitrarily returning this map's or the other's values on the intersection!
    pub fn complement(&self, other: &IdMap<K, V>) -> BinaryResult<IdMap<K, V>> {
        self.join_mutate_in(
            other,
            &mut AmbiMutator,
            &mut NullMutator,
            &mut DeleteMutator,
            &mut (),
        )
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn left_unioned_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.left_union_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn left_intersected_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.left_intersect_in(other, ctx)
            .unwrap_or_clone(self, other)
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn left_unioned(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.left_union(other).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn left_intersected(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.left_intersect(other).unwrap_or_clone(self, other)
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn right_unioned_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.right_union_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn right_intersected_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.right_intersect_in(other, ctx)
            .unwrap_or_clone(self, other)
    }
    /// Take the union of two maps: if any keys are shared between two maps, always take the left value
    pub fn right_unioned(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.right_union(other).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking the left value in case of conflict
    pub fn right_intersected(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.right_intersect(other).unwrap_or_clone(self, other)
    }
    /// Take the union of two maps: if any keys are shared between two maps, it is unspecified which of the two values is in the result
    pub fn unioned_in<C: ConsCtx<K, V>>(&self, other: &IdMap<K, V>, ctx: &mut C) -> IdMap<K, V> {
        self.union_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking an unspecified value in case of conflict
    pub fn intersected_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.intersect_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the symmetric difference of two maps
    pub fn sym_diffed_in<C: ConsCtx<K, V>>(&self, other: &IdMap<K, V>, ctx: &mut C) -> IdMap<K, V> {
        self.sym_diff_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the symmetric difference of two maps
    pub fn left_complemented_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.left_complement_in(other, ctx)
            .unwrap_or_clone(self, other)
    }
    /// Take the symmetric difference of two maps
    pub fn right_complemented_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.right_complement_in(other, ctx)
            .unwrap_or_clone(self, other)
    }
    /// Take the symmetric difference of two maps
    pub fn complemented_in<C: ConsCtx<K, V>>(
        &self,
        other: &IdMap<K, V>,
        ctx: &mut C,
    ) -> IdMap<K, V> {
        self.complement_in(other, ctx).unwrap_or_clone(self, other)
    }
    /// Take the union of two maps: if any keys are shared between two maps, it is unspecified which of the two values is in the result
    pub fn unioned(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.union(other).unwrap_or_clone(self, other)
    }
    /// Take the intersection of two maps, taking an unspecified value in case of conflict
    pub fn intersected(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.intersect(other).unwrap_or_clone(self, other)
    }
    /// Take the symmetric difference of two maps
    pub fn sym_diffed(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.sym_diff(other).unwrap_or_clone(self, other)
    }
    /// Take the complement of this map's *entries* with respect to another's *keys*
    pub fn left_complemented(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.left_complement(other).unwrap_or_clone(self, other)
    }
    /// Take the complement of this map's *entries* with respect to another's *keys*
    pub fn complemented(&self, other: &IdMap<K, V>) -> IdMap<K, V> {
        self.complement(other).unwrap_or_clone(self, other)
    }
    /*
    /// Join-transform two maps by applying a binary transformer to their key intersection and
    /// unary transformers to their left and right intersection.
    pub fn join_transform_in<R, O, IT, LT, RT, C>(
        &self,
        other: &IdMap<K, R>,
        intersection_transformer: &mut IT,
        left_transformer: &mut LT,
        right_transformer: &mut RT,
        ctx: &mut C,
    ) -> IdMap<K, O>
    where
        O: Clone,
        R: Clone + Eq,
        IT: BinaryTransformer<K, V, R, O>,
        LT: UnaryTransformer<K, V, O>,
        RT: UnaryTransformer<K, R, O>,
        C: ConsCtx<K, O>,
    {
        let (this, other) = match (&self.0, &other.0) {
            (_, None) => return self.transformed_vals_in(left_transformer, ctx),
            (None, _) => return other.transformed_vals_in(right_transformer, ctx),
            (Some(this), Some(other)) => (this, other),
        };
        unimplemented!(
            "General transformation for this@{:p}, other@{:p}",
            this,
            other
        )
    }
    */
}

impl<K: RadixKey, V: Clone + Eq> IdMap<K, V> {
    /// Insert an entry of an `IdMap` in a given context, *updating the old value* if one was already there.
    /// Return a new map if any changes were made
    pub fn inserted_conservative_in<C: ConsCtx<K, V>>(
        &self,
        key: K,
        value: V,
        ctx: &mut C,
    ) -> Option<IdMap<K, V>> {
        self.mutate_in(
            key,
            |key, entry_value| {
                let mutation = match entry_value {
                    Some(entry_value) if *entry_value != value => Mutation::Update(value),
                    Some(_) => Mutation::Null,
                    None => Mutation::Insert(key, value),
                };
                (mutation, ())
            },
            ctx,
        )
        .0
    }
    /// Insert an entry of an `IdMap`, *updating the old value* if one was already there.
    /// Return a new map if any changes were made
    pub fn inserted_conservative(&self, key: K, value: V) -> Option<IdMap<K, V>> {
        self.inserted_conservative_in(key, value, &mut ())
    }
    /// Insert an entry into an `IdMap` in a given context, *updating the old value* if one was already there.
    /// Return whether any changes were made
    pub fn insert_conservative_in<C: ConsCtx<K, V>>(
        &mut self,
        key: K,
        value: V,
        ctx: &mut C,
    ) -> bool {
        if let Some(inserted_conservative) = self.inserted_conservative_in(key, value, ctx) {
            *self = inserted_conservative;
            true
        } else {
            false
        }
    }
    /// Insert an entry into an `IdMap`, *updating the old value* if one was already there.
    /// Return whether any changes were made
    pub fn insert_conservative(&mut self, key: K, value: V) -> bool {
        if let Some(inserted_conservative) = self.inserted_conservative(key, value) {
            *self = inserted_conservative;
            true
        } else {
            false
        }
    }
    /// Check whether this map is a submap of another. A map is considered to be a submap of itself.
    ///
    /// If `cons` is true, this map is assumed to be hash-consed with the other
    pub fn is_submap(&self, other: &IdMap<K, V>, cons: bool) -> bool {
        match (&self.0, &other.0) {
            (Some(this), Some(other)) => {
                if Arc::ptr_eq(this, other) {
                    true
                } else if cons && this.len() == other.len() {
                    false
                } else {
                    this.is_submap(other, cons)
                }
            }
            (Some(_), None) => false,
            (None, Some(_)) => true,
            (None, None) => true,
        }
    }
    /// Check whether this map's domain is a subset of another's.
    pub fn domain_is_subset<U: Clone + Eq>(&self, other: &IdMap<K, U>) -> bool {
        match (&self.0, &other.0) {
            (Some(this), Some(other)) => this.domain_is_subset(other),
            (Some(_), None) => false,
            (None, Some(_)) => true,
            (None, None) => true,
        }
    }
    /// Check whether this map's domain has a nonempty intersection with another map's
    ///
    /// # Example
    ///
    /// ```rust
    /// # use pour::{IdSet, IdMap};
    /// let mut a = IdSet::new();
    /// for i in 0..10 {
    ///     a.try_insert(i, ());
    /// }
    /// let mut b = IdSet::new();
    /// for i in 5..20 {
    ///     b.try_insert(i, ());
    /// }
    /// let mut c = IdMap::new();
    /// for i in 10..20 {
    ///     c.try_insert(i, 3*i);
    /// }
    /// assert!(a.domains_intersect(&a));
    /// assert!(b.domains_intersect(&b));
    /// assert!(c.domains_intersect(&c));
    /// assert!(a.domains_intersect(&b));
    /// assert!(b.domains_intersect(&a));
    /// assert!(b.domains_intersect(&c));
    /// assert!(c.domains_intersect(&b));
    /// assert!(!a.domains_intersect(&c));
    /// assert!(!c.domains_intersect(&a));
    /// ```
    pub fn domains_intersect<U: Clone + Eq>(&self, other: &IdMap<K, U>) -> bool {
        match (&self.0, &other.0) {
            (Some(this), Some(other)) => this.domains_intersect(other),
            _ => false,
        }
    }
    /// Check whether two maps have disjoint domains
    ///
    /// # Example
    ///
    /// ```rust
    /// # use pour::{IdSet, IdMap};
    /// let mut a = IdSet::new();
    /// for i in 100..1000 {
    ///     a.try_insert(i, ());
    /// }
    /// let mut b = IdMap::new();
    /// for i in 50..2000 {
    ///     b.try_insert(i, 2*i);
    /// }
    /// let mut c = IdSet::new();
    /// for i in 1500..2500 {
    ///     c.try_insert(i, ());
    /// }
    /// assert!(!a.domains_disjoint(&a));
    /// assert!(!b.domains_disjoint(&b));
    /// assert!(!c.domains_disjoint(&c));
    /// assert!(!a.domains_disjoint(&b));
    /// assert!(!b.domains_disjoint(&a));
    /// assert!(!b.domains_disjoint(&c));
    /// assert!(!c.domains_disjoint(&b));
    /// assert!(a.domains_disjoint(&c));
    /// assert!(c.domains_disjoint(&a));
    /// ```
    pub fn domains_disjoint<U: Clone + Eq>(&self, other: &IdMap<K, U>) -> bool {
        !self.domains_intersect(other)
    }
    /// Partially order maps based off the submap relation
    pub fn map_cmp(&self, other: &IdMap<K, V>, cons: bool) -> Option<Ordering> {
        use Ordering::*;
        match self.len().cmp(&other.len()) {
            Less if self.is_submap(other, cons) => Some(Less),
            Equal if !cons && self == other => Some(Equal),
            Equal if cons && self.ptr_eq(other) => Some(Equal),
            Greater if other.is_submap(self, cons) => Some(Greater),
            _ => None,
        }
    }
    /// Partially order the domains of maps based off the subset relation
    pub fn domain_cmp(&self, other: &IdMap<K, V>) -> Option<Ordering> {
        use Ordering::*;
        match self.len().cmp(&other.len()) {
            Greater if other.domain_is_subset(self) => Some(Greater),
            ord if self.domain_is_subset(other) => Some(ord),
            _ => None,
        }
    }
}

/// A trait implemented by objects which can perform hash-consing on a map's internal data
pub trait ConsCtx<K: RadixKey, V: Clone> {
    /// Return an `Arc<InnerMap>` with the same contents as the provided `Arc`
    ///
    /// # Correctness
    /// The resulting `Arc` should compare equal to `inner` if they are comparable.
    /// If not, being the result of `clone` is fine.
    fn cons_arc(&mut self, inner: &Arc<InnerMap<K, V>>) -> Arc<InnerMap<K, V>>;
    /// Return an `Arc<InnerMap>` with the same contents as the provided object.
    ///
    /// # Correctness
    /// The resulting `Arc` should compare equal to `inner` if they are comparable.
    /// If not, being the result of `new` is fine.
    fn cons(&mut self, inner: InnerMap<K, V>) -> Arc<InnerMap<K, V>>;
    /// Return an `Arc<InnerMap>` with the same contents as the provided `Arc`
    ///
    /// Note: this is provided as a separate function from `cons_arc` to allow the user the choice as
    /// to whether to perform deep or shallow hash-consing of mutated values: if shallow hash-consing
    /// is desired, this method should just clone the input `Arc`, whereas if deep hash-consing is
    /// desired, this method should return another, potentially hash-consed `Arc`. Deep hash-consing
    /// is the default, so `cons_arc` is called by the default implementation.
    ///
    /// # Correctness
    /// The resulting `Arc` should compare equal to `inner` if they are comparable.
    /// If not, being the result of `clone` is fine.
    fn cons_recursive(&mut self, inner: &Arc<InnerMap<K, V>>) -> Arc<InnerMap<K, V>> {
        self.cons_arc(inner)
    }
}

/// A key which can be used in a radix trie
pub trait RadixKey: Eq + Clone {
    /// The pattern type of this radix key
    type PatternType: Pattern<Self::DepthType>;
    /// The depth type of this radix key
    ///
    /// We assume this can be losslessly `as_` casted into `usize`, with all valid values casting back from usize
    type DepthType: PrimInt + Hash + AsPrimitive<usize>;
    /// A function to get the pattern of data for this key corresponding to a given bitdepth.
    fn pattern(&self, depth: Self::DepthType) -> Self::PatternType;
    /// Get the pattern number of a given bitdepth
    ///
    /// NOTE: "levels" are currently not yet supported! Returning a pattern number greater than 0 will cause a panic!
    fn pattern_no(depth: Self::DepthType) -> usize {
        let depth: usize = depth.as_();
        depth / Self::PatternType::MAX_BITS
    }
}

/// An n-bit pattern
pub trait Pattern<D>: Eq + Hash + Copy + Clone + Default {
    /// Get the maximum bitdepth of this pattern
    const MAX_BITS: usize;
    /// Get this pattern's max bits as a depth type
    fn max_bits() -> D;
    /// Get the nth byte of this pattern at a given bitdepth
    fn byte(self, n: D) -> u8;
    /// Get the bit difference between this pattern and another
    fn diff(self, other: Self) -> D;
}

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

    fn ordered_map_construction_in_ctx<C: ConsCtx<u64, u64>>(
        n: u64,
        ctx: &mut C,
    ) -> IdMap<u64, u64> {
        let mut x = IdMap::new();
        let mut v = Vec::with_capacity(n as usize);
        for i in 0..n {
            assert_eq!(
                x.get(&i),
                None,
                "{} has not already been inserted into {:#?}",
                i,
                x
            );
            assert!(
                x.try_insert_in(i, 2 * i, ctx),
                "{} has not already been inserted into {:#?}",
                i,
                x
            );
            assert_eq!(
                x.get(&i),
                Some(&(2 * i)),
                "{} has already been inserted into {:#?}",
                i,
                x
            );
            assert!(
                !x.try_insert_in(i, 3 * i, ctx),
                "{} has already had a value set in {:#?}",
                i,
                x
            );
            assert_eq!(
                x.get(&i),
                Some(&(2 * i)),
                "{} has already been inserted into {:#?}",
                i,
                x
            );
            assert!(
                x.insert_conservative_in(i, 3 * i, ctx) || i == 0,
                "{} can be inserted_conservative in {:#?}",
                i,
                x
            );
            assert_eq!(
                x.get(&i),
                Some(&(3 * i)),
                "{} has already been inserted into {:#?}",
                i,
                x
            );
            v.push((i, 3 * i));
        }
        let mut xv: Vec<_> = x.iter().map(|(k, v)| (*k, *v)).collect();
        xv.sort_unstable();
        assert_eq!(xv, v);
        xv = x.clone().into_iter().collect();
        xv.sort_unstable();
        assert_eq!(xv, v);
        x
    }

    #[test]
    fn medium_map_construction() {
        let x = ordered_map_construction_in_ctx(1000, &mut ());
        let y = ordered_map_construction_in_ctx(1000, &mut ());
        assert_ne!(x.as_ptr(), y.as_ptr());
        assert_eq!(x, y);
    }

    #[test]
    fn medium_map_construction_in_ctx() {
        let mut ctx = MapCtx::new();
        let x = ordered_map_construction_in_ctx(1000, &mut ctx);
        let y = ordered_map_construction_in_ctx(1000, &mut ctx);
        assert_eq!(x, y);
        assert_eq!(x.as_ptr(), y.as_ptr());
    }

    #[test]
    fn small_non_consed_map_set_ops() {
        let mut x = IdMap::new();
        x.try_insert(3, 6);
        x.try_insert(5, 7);
        x.try_insert(9, 2);
        let mut y = IdMap::new();
        y.try_insert(3, 5);
        y.try_insert(2, 42);
        y.try_insert(134, 23);
        let z = match x.left_union(&y) {
            BinaryResult::New(z) => z,
            r => panic!("New map not returned, got result {:?}", r),
        };
        assert_eq!(z, x.left_unioned(&y));
        assert_eq!(z.get(&2), Some(&42));
        assert_eq!(z.get(&3), Some(&6));
        assert_eq!(z.get(&4), None);
        assert_eq!(z.get(&5), Some(&7));
        assert_eq!(z.get(&134), Some(&23));
        assert_eq!(z.len(), 5);
        let w = match x.left_intersect(&y) {
            BinaryResult::New(w) => w,
            r => panic!("New map not returned, got result {:?}", r),
        };
        assert_eq!(w.get(&3), Some(&6));
        assert_eq!(w.len(), 1);
    }

    #[test]
    fn small_consed_set_ops() {
        let mut ctx = MapCtx::new();
        let mut x = IdMap::new();
        x.try_insert_in(3, 6, &mut ctx);
        x.try_insert_in(5, 7, &mut ctx);
        x.try_insert_in(9, 2, &mut ctx);
        let mut y = IdMap::new();
        y.try_insert_in(3, 5, &mut ctx);
        y.try_insert_in(2, 42, &mut ctx);
        y.try_insert_in(134, 23, &mut ctx);
        let z = match x.left_union_in(&y, &mut ctx) {
            BinaryResult::New(z) => z,
            r => panic!("New map not returned, got result {:?}", r),
        };
        assert_eq!(z.as_ptr(), x.left_unioned_in(&y, &mut ctx).as_ptr());
        assert_eq!(z, x.left_unioned(&y));
        assert_eq!(z.get(&2), Some(&42));
        assert_eq!(z.get(&3), Some(&6));
        assert_eq!(z.get(&4), None);
        assert_eq!(z.get(&5), Some(&7));
        assert_eq!(z.get(&134), Some(&23));
        assert_eq!(z.len(), 5);
        let w = match x.left_intersect_in(&y, &mut ctx) {
            BinaryResult::New(w) => w,
            r => panic!("New map not returned, got result {:?}", r),
        };
        assert_eq!(w.get(&3), Some(&6));
        assert_eq!(w.len(), 1);
    }

    #[test]
    fn mapping_set_op() {
        let mut x = IdMap::new();
        x.try_insert(3, 4);
        x.try_insert(4, 2);
        x.try_insert(6, 31);
        x.try_insert(9, 2);
        let mut y = IdMap::new();
        y.try_insert(1, 24);
        y.try_insert(3, 1);
        y.try_insert(7, 2);
        y.try_insert(8, 31);
        y.try_insert(9, 3);
        let j = x
            .join_mutate_in(
                &y,
                &mut LeftMutator,
                &mut FilterMap::new(|_key, value| {
                    if value % 2 == 0 {
                        Some(7 * value)
                    } else {
                        None
                    }
                }),
                &mut NullMutator,
                &mut (),
            )
            .unwrap();
        let mut jr = IdMap::new();
        jr.try_insert(1, 24);
        jr.try_insert(3, 4);
        jr.try_insert(4, 2 * 7);
        jr.try_insert(7, 2);
        jr.try_insert(8, 31);
        jr.try_insert(9, 2);
        assert_eq!(j, jr);
    }

    #[test]
    fn small_usize_insert() {
        let mut map = IdMap::<usize, String>::new();
        let ix = 3;
        map.insert(ix, "Hello".to_string());
        assert_eq!(map.get(&ix).unwrap(), "Hello");
        eprintln!("Inner = {:#?}", map.0);
        map.insert(ix, "Goodbye".to_string());
        eprintln!("Inner = {:#?}", map.0);
        assert_eq!(map.get(&ix).unwrap(), "Goodbye");
    }

    #[test]
    fn big_usize_insert() {
        let mut map = IdMap::<usize, String>::new();
        let ix = 140220213234856;
        map.insert(ix, "Hello".to_string());
        assert_eq!(map.get(&ix).unwrap(), "Hello");
        eprintln!("Inner = {:#?}", map.0);
        map.insert(ix, "Goodbye".to_string());
        eprintln!("Inner = {:#?}", map.0);
        assert_eq!(map.get(&ix).unwrap(), "Goodbye");
    }
}