    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE LambdaCase #-}
    {-# LANGUAGE PatternSynonyms #-}
    {-# LANGUAGE ViewPatterns #-}

    -- |
    -- Module      : Data.IntMap.NonEmpty
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- = Non-Empty Finite Integer-Indexed Maps (lazy interface)
    --
    -- The @'NEIntMap' v@ type represents a non-empty finite map (sometimes
    -- called a dictionary) from integer keys to values of type @v@.
    -- An 'NEIntMap' is strict in its keys but lazy in its values.
    --
    -- See documentation for 'NEIntMap' for information on how to convert and
    -- manipulate such non-empty maps.
    --
    -- This module essentially re-imports the API of "Data.IntMap.Lazy" and its
    -- 'IntMap' type, along with semantics and asymptotics.  In most
    -- situations, asymptotics are different only by a constant factor.  In
    -- some situations, asmyptotics are even better (constant-time instead of
    -- log-time).
    --
    -- Because 'NEIntMap' is implemented using 'IntMap', all of the caveats of using
    -- 'IntMap' apply (such as the limitation of the maximum size of maps).
    --
    -- All functions take non-empty maps as inputs.  In situations where their
    -- results can be guarunteed to also be non-empty, they also return
    -- non-empty maps.  In situations where their results could potentially be
    -- empty, 'IntMap' is returned instead.
    --
    -- Some variants of functions (like 'alter'', 'alterF'', 'adjustMin',
    -- 'adjustMax', 'adjustMinWithKey', 'adjustMaxWithKey') are provided in
    -- a way restructured to preserve guaruntees of non-empty maps being
    -- returned.
    --
    -- Some functions (like 'mapEither', 'partition', 'split')
    -- have modified return types to account for possible configurations of
    -- non-emptiness.
    --
    -- This module is intended to be imported qualified, to avoid name clashes with
    -- "Prelude" and "Data.IntMap" functions:
    --
    -- > import qualified Data.IntMap.NonEmpty as NEIM
    --
    -- Note that all asmyptotics /O(f(n))/ in this module are actually
    -- /O(min(W, f(n)))/, where @W@ is the number of bits in an 'Int' (32 or
    -- 64).  That is, if @f(n)@ is greater than @W@, all operations are
    -- constant-time.
    --
    -- At the moment, this package does not provide a variant strict on values
    -- for these functions, like /containers/ does.  This is a planned future
    -- implementation (PR's are appreciated).  For now, you can simulate
    -- a strict interface by manually forcing values before returning results.
    module Data.IntMap.NonEmpty (
      -- * Non-Empty IntMap Type
      NEIntMap,
      Key,

      -- ** Conversions between empty and non-empty maps
      pattern IsNonEmpty,
      pattern IsEmpty,
      nonEmptyMap,
      toMap,
      withNonEmpty,
      insertMap,
      insertMapWith,
      insertMapWithKey,
      insertMapMin,
      insertMapMax,
      unsafeFromMap,

      -- * Construction
      singleton,
      fromSet,

      -- ** From Unordered Lists
      fromList,
      fromListWith,
      fromListWithKey,

      -- ** From Ascending Lists
      fromAscList,
      fromAscListWith,
      fromAscListWithKey,
      fromDistinctAscList,

      -- * Insertion
      insert,
      insertWith,
      insertWithKey,
      insertLookupWithKey,

      -- * Deletion\/Update
      delete,
      adjust,
      adjustWithKey,
      update,
      updateWithKey,
      updateLookupWithKey,
      alter,
      alterF,
      alter',
      alterF',

      -- * Query

      -- ** Lookup
      lookup,
      (!?),
      (!),
      findWithDefault,
      member,
      notMember,
      lookupLT,
      lookupGT,
      lookupLE,
      lookupGE,

      -- ** Size
      size,

      -- * Combine

      -- ** Union
      union,
      unionWith,
      unionWithKey,
      unions,
      unionsWith,

      -- ** Difference
      difference,
      (\\),
      differenceWith,
      differenceWithKey,

      -- ** Intersection
      intersection,
      intersectionWith,
      intersectionWithKey,
      -- -- ** Universal combining function
      -- , mergeWithKey

      -- * Traversal

      -- ** Map
      map,
      mapWithKey,
      traverseWithKey1,
      traverseWithKey,
      mapAccum,
      mapAccumWithKey,
      mapAccumRWithKey,
      mapKeys,
      mapKeysWith,
      mapKeysMonotonic,

      -- * Folds
      foldr,
      foldl,
      foldr1,
      foldl1,
      foldrWithKey,
      foldlWithKey,
      foldMapWithKey,

      -- ** Strict folds
      foldr',
      foldr1',
      foldl',
      foldl1',
      foldrWithKey',
      foldlWithKey',

      -- * Conversion
      elems,
      keys,
      assocs,
      keysSet,

      -- ** Lists
      toList,

      -- ** Ordered lists
      toAscList,
      toDescList,

      -- * Filter
      filter,
      filterWithKey,
      restrictKeys,
      withoutKeys,
      partition,
      partitionWithKey,
      mapMaybe,
      mapMaybeWithKey,
      mapEither,
      mapEitherWithKey,
      split,
      splitLookup,
      splitRoot,

      -- * Submap
      isSubmapOf,
      isSubmapOfBy,
      isProperSubmapOf,
      isProperSubmapOfBy,

      -- * Min\/Max
      findMin,
      findMax,
      deleteMin,
      deleteMax,
      deleteFindMin,
      deleteFindMax,
      updateMin,
      updateMax,
      adjustMin,
      adjustMax,
      updateMinWithKey,
      updateMaxWithKey,
      adjustMinWithKey,
      adjustMaxWithKey,
      minView,
      maxView,

      -- * Debugging
      valid,
    ) where

    import Control.Applicative
    import Data.Bifunctor
    import qualified Data.Foldable as F
    import Data.Functor.Identity
    import qualified Data.IntMap as M
    import Data.IntMap.Internal (IntMap (..))
    import Data.IntMap.NonEmpty.Internal
    import Data.IntSet (IntSet)
    import qualified Data.IntSet as S
    import Data.IntSet.NonEmpty.Internal (NEIntSet (..))
    import Data.List.NonEmpty (NonEmpty (..))
    import qualified Data.List.NonEmpty as NE
    import Data.Maybe hiding (mapMaybe)
    import qualified Data.Maybe as Maybe
    import Data.Semigroup.Foldable (Foldable1)
    import qualified Data.Semigroup.Foldable as F1
    import Data.These
    import Prelude hiding (Foldable (..), filter, lookup, map)

    -- | /O(1)/ match, /O(log n)/ usage of contents. The 'IsNonEmpty' and
    -- 'IsEmpty' patterns allow you to treat a 'IntMap' as if it were either
    -- a @'IsNonEmpty' n@ (where @n@ is a 'NEIntMap') or an 'IsEmpty'.
    --
    -- For example, you can pattern match on a 'IntMap':
    --
    -- @
    -- myFunc :: 'IntMap' K X -> Y
    -- myFunc ('IsNonEmpty' n) =  -- here, the user provided a non-empty map, and @n@ is the 'NEIntMap'
    -- myFunc 'IsEmpty'        =  -- here, the user provided an empty map.
    -- @
    --
    -- Matching on @'IsNonEmpty' n@ means that the original 'IntMap' was /not/
    -- empty, and you have a verified-non-empty 'NEIntMap' @n@ to use.
    --
    -- Note that patching on this pattern is /O(1)/.  However, using the
    -- contents requires a /O(log n)/ cost that is deferred until after the
    -- pattern is matched on (and is not incurred at all if the contents are
    -- never used).
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsNonEmpty' to convert
    -- a 'NEIntMap' back into a 'IntMap', obscuring its non-emptiness (see 'toMap').
    pattern IsNonEmpty :: NEIntMap a -> IntMap a
    pattern $mIsNonEmpty :: forall {r} {a}. IntMap a -> (NEIntMap a -> r) -> ((# #) -> r) -> r
    $bIsNonEmpty :: forall a. NEIntMap a -> IntMap a
    IsNonEmpty n <- (nonEmptyMap -> Just n)
      where
        IsNonEmpty NEIntMap a
    n = NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n

    -- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
    -- a 'IntMap' as if it were either a @'IsNonEmpty' n@ (where @n@ is
    -- a 'NEIntMap') or an 'IsEmpty'.
    --
    -- Matching on 'IsEmpty' means that the original 'IntMap' was empty.
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsEmpty' as an
    -- expression, and it will be interpreted as 'Data.IntMap.empty'.
    --
    -- See 'IsNonEmpty' for more information.
    pattern IsEmpty :: IntMap a
    pattern $mIsEmpty :: forall {r} {a}. IntMap a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bIsEmpty :: forall a. IntMap a
    IsEmpty <- (M.null -> True)
      where
        IsEmpty = IntMap a
    forall a. IntMap a
    M.empty

    {-# COMPLETE IsNonEmpty, IsEmpty #-}

    -- | /O(log n)/. Unsafe version of 'nonEmptyMap'.  Coerces a 'IntMap' into an
    -- 'NEIntMap', but is undefined (throws a runtime exception when evaluation is
    -- attempted) for an empty 'IntMap'.
    unsafeFromMap ::
      IntMap a ->
      NEIntMap a
    unsafeFromMap :: forall a. IntMap a -> NEIntMap a
    unsafeFromMap = NEIntMap a -> (NEIntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty NEIntMap a
    forall {a}. a
    e NEIntMap a -> NEIntMap a
    forall a. a -> a
    id
      where
        e :: a
    e = [Char] -> a
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "NEIntMap.unsafeFromMap: empty map"
    {-# INLINE unsafeFromMap #-}

    -- | /O(log n)/. Convert a 'IntMap' into an 'NEIntMap' by adding a key-value
    -- pair.  Because of this, we know that the map must have at least one
    -- element, and so therefore cannot be empty. If key is already present,
    -- will overwrite the original value.
    --
    -- See 'insertMapMin' for a version that is constant-time if the new key is
    -- /strictly smaller than/ all keys in the original map.
    --
    -- > insertMap 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
    -- > insertMap 4 "c" Data.IntMap.empty == singleton 4 "c"
    insertMap :: Key -> a -> IntMap a -> NEIntMap a
    insertMap :: forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMap Key
    k a
    v = NEIntMap a -> (NEIntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v) (Key -> a -> NEIntMap a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a -> NEIntMap a
    insert Key
    k a
    v)
    {-# INLINE insertMap #-}

    -- | /O(log n)/. Convert a 'IntMap' into an 'NEIntMap' by adding a key-value
    -- pair.  Because of this, we know that the map must have at least one
    -- element, and so therefore cannot be empty. Uses a combining function
    -- with the new value as the first argument if the key is already present.
    --
    -- > insertMapWith (++) 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
    -- > insertMapWith (++) 5 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])
    insertMapWith ::
      (a -> a -> a) ->
      Key ->
      a ->
      IntMap a ->
      NEIntMap a
    insertMapWith :: forall a. (a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a
    insertMapWith a -> a -> a
    f Key
    k a
    v = NEIntMap a -> (NEIntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v) ((a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    forall a. (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    insertWith a -> a -> a
    f Key
    k a
    v)
    {-# INLINE insertMapWith #-}

    -- | /O(log n)/. Convert a 'IntMap' into an 'NEIntMap' by adding a key-value
    -- pair.  Because of this, we know that the map must have at least one
    -- element, and so therefore cannot be empty. Uses a combining function
    -- with the key and new value as the first and second arguments if the key
    -- is already present.
    --
    -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    -- > insertWithKey f 5 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")])
    -- > insertWithKey f 7 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
    -- > insertWithKey f 5 "xxx" Data.IntMap.empty                         == singleton 5 "xxx"
    insertMapWithKey ::
      (Key -> a -> a -> a) ->
      Key ->
      a ->
      IntMap a ->
      NEIntMap a
    insertMapWithKey :: forall a.
    (Key -> a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a
    insertMapWithKey Key -> a -> a -> a
    f Key
    k a
    v = NEIntMap a -> (NEIntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v) ((Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    forall a.
    (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    insertWithKey Key -> a -> a -> a
    f Key
    k a
    v)
    {-# INLINE insertMapWithKey #-}

    -- | /O(1)/ Convert a 'IntMap' into an 'NEIntMap' by adding a key-value pair
    -- where the key is /strictly less than/ all keys in the input map.  The
    -- keys in the original map must all be /strictly greater than/ the new
    -- key.  /The precondition is not checked./
    --
    -- > insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")])
    -- > valid (insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == True
    -- > valid (insertMapMin 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False
    -- > valid (insertMapMin 3 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False
    insertMapMin ::
      Key ->
      a ->
      IntMap a ->
      NEIntMap a
    insertMapMin :: forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap
    {-# INLINE insertMapMin #-}

    -- | /O(log n)/ Convert a 'IntMap' into an 'NEIntMap' by adding a key-value pair
    -- where the key is /strictly greater than/ all keys in the input map.  The
    -- keys in the original map must all be /strictly less than/ the new
    -- key.  /The precondition is not checked./
    --
    -- At the current moment, this is identical simply 'insertMap'; however,
    -- it is left both for consistency and as a placeholder for a future
    -- version where optimizations are implemented to allow for a faster
    -- implementation.
    --
    -- > insertMap 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")])

    -- these currently are all valid, but shouldn't be
    -- > valid (insertMap 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == True
    -- > valid (insertMap 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False
    -- > valid (insertMap 5 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False
    insertMapMax ::
      Key ->
      a ->
      IntMap a ->
      NEIntMap a
    insertMapMax :: forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMax Key
    k a
    v = NEIntMap a -> (NEIntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v) NEIntMap a -> NEIntMap a
    go
      where
        go :: NEIntMap a -> NEIntMap a
    go (NEIntMap Key
    k0 a
    v0 IntMap a
    m0) = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v0 (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMaxMap Key
    k a
    v (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m0
    {-# INLINE insertMapMax #-}

    -- | /O(n)/. Build a non-empty map from a non-empty set of keys and
    -- a function which for each key computes its value.
    --
    -- > fromSet (\k -> replicate k 'a') (Data.Set.NonEmpty.fromList (3 :| [5])) == fromList ((5,"aaaaa") :| [(3,"aaa")])
    fromSet ::
      (Key -> a) ->
      NEIntSet ->
      NEIntMap a
    fromSet :: forall a. (Key -> a) -> NEIntSet -> NEIntMap a
    fromSet Key -> a
    f (NEIntSet Key
    k IntSet
    ks) = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Key -> a
    f Key
    k) ((Key -> a) -> IntSet -> IntMap a
    forall a. (Key -> a) -> IntSet -> IntMap a
    M.fromSet Key -> a
    f IntSet
    ks)
    {-# INLINE fromSet #-}

    -- | /O(n*log n)/. Build a map from a non-empty list of key\/value pairs
    -- with a combining function. See also 'fromAscListWith'.
    --
    -- > fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")])
    fromListWith ::
      (a -> a -> a) ->
      NonEmpty (Key, a) ->
      NEIntMap a
    fromListWith :: forall a. (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromListWith a -> a -> a
    f = (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    forall a. (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromListWithKey ((a -> a -> a) -> Key -> a -> a -> a
    forall a b. a -> b -> a
    const a -> a -> a
    f)
    {-# INLINE fromListWith #-}

    -- | /O(n*log n)/. Build a map from a non-empty list of key\/value pairs
    -- with a combining function. See also 'fromAscListWithKey'.
    --
    -- > let f k a1 a2 = (show k) ++ a1 ++ a2
    -- > fromListWithKey f ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "3ab") :| [(5, "5a5ba")])
    fromListWithKey ::
      (Key -> a -> a -> a) ->
      NonEmpty (Key, a) ->
      NEIntMap a
    fromListWithKey :: forall a. (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromListWithKey Key -> a -> a -> a
    f ((Key
    k0, a
    v0) :| [(Key, a)]
    xs) = (NEIntMap a -> (Key, a) -> NEIntMap a)
    -> NEIntMap a -> [(Key, a)] -> NEIntMap a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    F.foldl' NEIntMap a -> (Key, a) -> NEIntMap a
    go (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k0 a
    v0) [(Key, a)]
    xs
      where
        go :: NEIntMap a -> (Key, a) -> NEIntMap a
    go NEIntMap a
    m (Key
    k, a
    v) = (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    forall a.
    (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    insertWithKey Key -> a -> a -> a
    f Key
    k a
    v NEIntMap a
    m
        {-# INLINE go #-}
    {-# INLINE fromListWithKey #-}

    -- | /O(n)/. Build a map from an ascending non-empty list in linear time.
    -- /The precondition (input list is ascending) is not checked./
    --
    -- > fromAscList ((3,"b") :| [(5,"a")])          == fromList ((3, "b") :| [(5, "a")])
    -- > fromAscList ((3,"b") :| [(5,"a"), (5,"b")]) == fromList ((3, "b") :| [(5, "b")])
    -- > valid (fromAscList ((3,"b") :| [(5,"a"), (5,"b")])) == True
    -- > valid (fromAscList ((5,"a") :| [(3,"b"), (5,"b")])) == False
    fromAscList ::
      NonEmpty (Key, a) ->
      NEIntMap a
    fromAscList :: forall a. NonEmpty (Key, a) -> NEIntMap a
    fromAscList = NonEmpty (Key, a) -> NEIntMap a
    forall a. NonEmpty (Key, a) -> NEIntMap a
    fromDistinctAscList (NonEmpty (Key, a) -> NEIntMap a)
    -> (NonEmpty (Key, a) -> NonEmpty (Key, a))
    -> NonEmpty (Key, a)
    -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty (Key, a) -> NonEmpty (Key, a)
    forall b. NonEmpty (Key, b) -> NonEmpty (Key, b)
    combineEq
    {-# INLINE fromAscList #-}

    -- | /O(n)/. Build a map from an ascending non-empty list in linear time
    -- with a combining function for equal keys. /The precondition (input list
    -- is ascending) is not checked./
    --
    -- > fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b")]) == fromList ((3, "b") :| [(5, "ba")])
    -- > valid (fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b"))]) == True
    -- > valid (fromAscListWith (++) ((5,"a") :| [(3,"b"), (5,"b"))]) == False
    fromAscListWith ::
      (a -> a -> a) ->
      NonEmpty (Key, a) ->
      NEIntMap a
    fromAscListWith :: forall a. (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromAscListWith a -> a -> a
    f = (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    forall a. (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromAscListWithKey ((a -> a -> a) -> Key -> a -> a -> a
    forall a b. a -> b -> a
    const a -> a -> a
    f)
    {-# INLINE fromAscListWith #-}

    -- | /O(n)/. Build a map from an ascending non-empty list in linear time
    -- with a combining function for equal keys. /The precondition (input list
    -- is ascending) is not checked./
    --
    -- > let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
    -- > fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")]) == fromList ((3, "b") :| [(5, "5:b5:ba")])
    -- > valid (fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")])) == True
    -- > valid (fromAscListWithKey f ((5,"a") :| [(3,"b"), (5,"b"), (5,"b")])) == False
    fromAscListWithKey ::
      (Key -> a -> a -> a) ->
      NonEmpty (Key, a) ->
      NEIntMap a
    fromAscListWithKey :: forall a. (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromAscListWithKey Key -> a -> a -> a
    f = NonEmpty (Key, a) -> NEIntMap a
    forall a. NonEmpty (Key, a) -> NEIntMap a
    fromDistinctAscList (NonEmpty (Key, a) -> NEIntMap a)
    -> (NonEmpty (Key, a) -> NonEmpty (Key, a))
    -> NonEmpty (Key, a)
    -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NonEmpty (Key, a)
    forall b.
    (Key -> b -> b -> b) -> NonEmpty (Key, b) -> NonEmpty (Key, b)
    combineEqWith Key -> a -> a -> a
    f
    {-# INLINE fromAscListWithKey #-}

    -- | /O(n)/. Build a map from an ascending non-empty list of distinct
    -- elements in linear time. /The precondition is not checked./
    --
    -- > fromDistinctAscList ((3,"b") :| [(5,"a")]) == fromList ((3, "b") :| [(5, "a")])
    -- > valid (fromDistinctAscList ((3,"b") :| [(5,"a")]))          == True
    -- > valid (fromDistinctAscList ((3,"b") :| [(5,"a"), (5,"b")])) == False
    fromDistinctAscList :: NonEmpty (Key, a) -> NEIntMap a
    fromDistinctAscList :: forall a. NonEmpty (Key, a) -> NEIntMap a
    fromDistinctAscList ((Key
    k, a
    v) :| [(Key, a)]
    xs) =
      Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k a
    v
        (IntMap a -> NEIntMap a)
    -> ([(Key, a)] -> IntMap a) -> [(Key, a)] -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(Key, a)] -> IntMap a
    forall a. [(Key, a)] -> IntMap a
    M.fromDistinctAscList
        ([(Key, a)] -> NEIntMap a) -> [(Key, a)] -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ [(Key, a)]
    xs
    {-# INLINE fromDistinctAscList #-}

    -- | /O(log n)/. Insert a new key and value in the map.
    -- If the key is already present in the map, the associated value is
    -- replaced with the supplied value. 'insert' is equivalent to
    -- @'insertWith' 'const'@.
    --
    -- See 'insertMap' for a version where the first argument is a 'IntMap'.
    --
    -- > insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')])
    -- > insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')])
    insert ::
      Key ->
      a ->
      NEIntMap a ->
      NEIntMap a
    insert :: forall a. Key -> a -> NEIntMap a -> NEIntMap a
    insert Key
    k a
    v n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v0 IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v0 (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    M.insert Key
    k a
    v (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE insert #-}

    -- | /O(log n)/. Insert with a function, combining key, new value and old
    -- value. @'insertWithKey' f key value mp@ will insert the pair (key,
    -- value) into @mp@ if key does not exist in the map. If the key does
    -- exist, the function will insert the pair @(key,f key new_value
    -- old_value)@. Note that the key passed to f is the same key passed to
    -- 'insertWithKey'.
    --
    -- See 'insertMapWithKey' for a version where the first argument is a 'IntMap'.
    --
    -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    -- > insertWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:xxx|a")])
    -- > insertWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
    insertWithKey ::
      (Key -> a -> a -> a) ->
      Key ->
      a ->
      NEIntMap a ->
      NEIntMap a
    insertWithKey :: forall a.
    (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    insertWithKey Key -> a -> a -> a
    f Key
    k a
    v n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v0 IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Key -> a -> a -> a
    f Key
    k a
    v a
    v0) IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v0 (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
    forall a. (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
    M.insertWithKey Key -> a -> a -> a
    f Key
    k a
    v IntMap a
    m
    {-# INLINE insertWithKey #-}

    -- | /O(log n)/. Combines insert operation with old value retrieval. The
    -- expression (@'insertLookupWithKey' f k x map@) is a pair where the first
    -- element is equal to (@'lookup' k map@) and the second element equal to
    -- (@'insertWithKey' f k x map@).
    --
    -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
    -- > insertLookupWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "5:xxx|a")]))
    -- > insertLookupWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "xxx")]))
    --
    -- This is how to define @insertLookup@ using @insertLookupWithKey@:
    --
    -- > let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
    -- > insertLookup 5 "x" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "x")]))
    -- > insertLookup 7 "x" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "x")]))
    insertLookupWithKey ::
      (Key -> a -> a -> a) ->
      Key ->
      a ->
      NEIntMap a ->
      (Maybe a, NEIntMap a)
    insertLookupWithKey :: forall a.
    (Key -> a -> a -> a)
    -> Key -> a -> NEIntMap a -> (Maybe a, NEIntMap a)
    insertLookupWithKey Key -> a -> a -> a
    f Key
    k a
    v n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v0 IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (Maybe a
    forall a. Maybe a
    Nothing, Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n)
      Ordering
    EQ -> (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v, Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Key -> a -> a -> a
    f Key
    k a
    v a
    v0) IntMap a
    m)
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v0 (IntMap a -> NEIntMap a)
    -> (Maybe a, IntMap a) -> (Maybe a, NEIntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
    forall a.
    (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
    M.insertLookupWithKey Key -> a -> a -> a
    f Key
    k a
    v IntMap a
    m
    {-# INLINE insertLookupWithKey #-}

    -- | /O(log n)/. Delete a key and its value from the non-empty map.
    -- A potentially empty map ('IntMap') is returned, since this might delete the
    -- last item in the 'NEIntMap'.  When the key is not a member of the map, is
    -- equivalent to 'toMap'.
    --
    -- > delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    -- > delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.Singleton [(3, "b"), (5, "a")]
    delete :: Key -> NEIntMap a -> IntMap a
    delete :: forall a. Key -> NEIntMap a -> IntMap a
    delete Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n
      Ordering
    EQ -> IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0 a
    v (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> IntMap a -> IntMap a
    forall a. Key -> IntMap a -> IntMap a
    M.delete Key
    k (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE delete #-}

    -- | /O(log n)/. Update a value at a specific key with the result of the
    -- provided function. When the key is not a member of the map, the original
    -- map is returned.
    --
    -- > adjust ("new " ++) 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "new a")])
    -- > adjust ("new " ++) 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])
    adjust ::
      (a -> a) ->
      Key ->
      NEIntMap a ->
      NEIntMap a
    adjust :: forall a. (a -> a) -> Key -> NEIntMap a -> NEIntMap a
    adjust a -> a
    f = (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a
    forall a. (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a
    adjustWithKey ((a -> a) -> Key -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjust #-}

    -- | /O(log n)/. Adjust a value at a specific key. When the key is not
    -- a member of the map, the original map is returned.
    --
    -- > let f key x = (show key) ++ ":new " ++ x
    -- > adjustWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:new a")])
    -- > adjustWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])
    adjustWithKey ::
      (Key -> a -> a) ->
      Key ->
      NEIntMap a ->
      NEIntMap a
    adjustWithKey :: forall a. (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a
    adjustWithKey Key -> a -> a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> NEIntMap a
    n
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 (Key -> a -> a
    f Key
    k0 a
    v) IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> a) -> Key -> IntMap a -> IntMap a
    forall a. (Key -> a -> a) -> Key -> IntMap a -> IntMap a
    M.adjustWithKey Key -> a -> a
    f Key
    k (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE adjustWithKey #-}

    -- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@
    -- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
    -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
    --
    -- Returns a potentially empty map ('IntMap'), because we can't know ahead of
    -- time if the function returns 'Nothing' and deletes the final item in the
    -- 'NEIntMap'.
    --
    -- > let f x = if x == "a" then Just "new a" else Nothing
    -- > update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "new a")]
    -- > update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    -- > update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    update ::
      (a -> Maybe a) ->
      Key ->
      NEIntMap a ->
      IntMap a
    update :: forall a. (a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
    update a -> Maybe a
    f = (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
    updateWithKey ((a -> Maybe a) -> Key -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE update #-}

    -- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the
    -- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing',
    -- the element is deleted. If it is (@'Just' y@), the key @k@ is bound
    -- to the new value @y@.
    --
    -- Returns a potentially empty map ('IntMap'), because we can't know ahead of
    -- time if the function returns 'Nothing' and deletes the final item in the
    -- 'NEIntMap'.
    --
    -- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
    -- > updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "5:new a")]
    -- > updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    -- > updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    updateWithKey ::
      (Key -> a -> Maybe a) ->
      Key ->
      NEIntMap a ->
      IntMap a
    updateWithKey :: forall a. (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
    updateWithKey Key -> a -> Maybe a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n
      Ordering
    EQ -> IntMap a -> (a -> IntMap a) -> Maybe a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a
    m ((a -> IntMap a -> IntMap a) -> IntMap a -> a -> IntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0) IntMap a
    m) (Maybe a -> IntMap a) -> (a -> Maybe a) -> a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> a -> Maybe a
    f Key
    k0 (a -> IntMap a) -> a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ a
    v
      Ordering
    GT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0 a
    v (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
    M.updateWithKey Key -> a -> Maybe a
    f Key
    k (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE updateWithKey #-}

    -- | /O(min(n,W))/. Lookup and update.
    -- The function returns original value, if it is updated.
    -- This is different behavior than @Data.Map.NonEmpty.updateLookupWithKey@.
    -- Returns the original key value if the map entry is deleted.
    --
    -- Returns a potentially empty map ('IntMap') in the case that we delete
    -- the final key of a singleton map.
    --
    -- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
    -- > updateLookupWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "5:new a", Data.IntMap.fromList ((3, "b") :| [(5, "5:new a")]))
    -- > updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  Data.IntMap.fromList ((3, "b") :| [(5, "a")]))
    -- > updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.IntMap.singleton 5 "a")
    updateLookupWithKey ::
      (Key -> a -> Maybe a) ->
      Key ->
      NEIntMap a ->
      (Maybe a, IntMap a)
    updateLookupWithKey :: forall a.
    (Key -> a -> Maybe a) -> Key -> NEIntMap a -> (Maybe a, IntMap a)
    updateLookupWithKey Key -> a -> Maybe a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (Maybe a
    forall a. Maybe a
    Nothing, NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n)
      Ordering
    EQ ->
        let u :: Maybe a
    u = Key -> a -> Maybe a
    f Key
    k0 a
    v
         in (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v, IntMap a -> (a -> IntMap a) -> Maybe a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a
    m ((a -> IntMap a -> IntMap a) -> IntMap a -> a -> IntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0) IntMap a
    m) Maybe a
    u)
      Ordering
    GT -> (IntMap a -> IntMap a)
    -> (Maybe a, IntMap a) -> (Maybe a, IntMap a)
    forall a b. (a -> b) -> (Maybe a, a) -> (Maybe a, b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0 a
    v) ((Maybe a, IntMap a) -> (Maybe a, IntMap a))
    -> (IntMap a -> (Maybe a, IntMap a))
    -> IntMap a
    -> (Maybe a, IntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)
    forall a.
    (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a)
    M.updateLookupWithKey Key -> a -> Maybe a
    f Key
    k (IntMap a -> (Maybe a, IntMap a))
    -> IntMap a -> (Maybe a, IntMap a)
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE updateLookupWithKey #-}

    -- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at
    -- @k@, or absence thereof. 'alter' can be used to insert, delete, or
    -- update a value in a 'IntMap'. In short : @Data.IntMap.lookup k ('alter'
    -- f k m) = f ('lookup' k m)@.
    --
    -- Returns a potentially empty map ('IntMap'), because we can't know ahead of
    -- time if the function returns 'Nothing' and deletes the final item in the
    -- 'NEIntMap'.
    --
    -- See 'alterF'' for a version that disallows deletion, and so therefore
    -- can return 'NEIntMap'.
    --
    -- > let f _ = Nothing
    -- > alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
    -- > alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    -- >
    -- > let f _ = Just "c"
    -- > alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a"), (7, "c")]
    -- > alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "c")]
    alter ::
      (Maybe a -> Maybe a) ->
      Key ->
      NEIntMap a ->
      IntMap a
    alter :: forall a. (Maybe a -> Maybe a) -> Key -> NEIntMap a -> IntMap a
    alter Maybe a -> Maybe a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k) (Maybe a -> Maybe a
    f Maybe a
    forall a. Maybe a
    Nothing) (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n)
      Ordering
    EQ -> (IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0) (Maybe a -> Maybe a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)) IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0 a
    v (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
    forall a. (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
    M.alter Maybe a -> Maybe a
    f Key
    k (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE alter #-}

    -- | /O(log n)/. The expression (@'alterF' f k map@) alters the value @x@
    -- at @k@, or absence thereof.  'alterF' can be used to inspect, insert,
    -- delete, or update a value in a 'IntMap'.  In short: @Data.IntMap.lookup
    -- k \<$\> 'alterF' f k m = f ('lookup' k m)@.
    --
    -- Example:
    --
    -- @
    -- interactiveAlter :: Int -> NEIntMap Int String -> IO (IntMap Int String)
    -- interactiveAlter k m = alterF f k m where
    --   f Nothing = do
    --      putStrLn $ show k ++
    --          " was not found in the map. Would you like to add it?"
    --      getUserResponse1 :: IO (Maybe String)
    --   f (Just old) = do
    --      putStrLn $ "The key is currently bound to " ++ show old ++
    --          ". Would you like to change or delete it?"
    --      getUserResponse2 :: IO (Maybe String)
    -- @
    --
    -- Like @Data.IntMap.alterF@ for 'IntMap', 'alterF' can be considered
    -- to be a unifying generalization of 'lookup' and 'delete'; however, as
    -- a constrast, it cannot be used to implement 'insert', because it must
    -- return a 'IntMap' instead of an 'NEIntMap' (because the function might delete
    -- the final item in the 'NEIntMap').  When used with trivial functors like
    -- 'Identity' and 'Const', it is often slightly slower than
    -- specialized 'lookup' and 'delete'. However, when the functor is
    -- non-trivial and key comparison is not particularly cheap, it is the
    -- fastest way.
    --
    -- See 'alterF'' for a version that disallows deletion, and so therefore
    -- can return 'NEIntMap' and be used to implement 'insert'
    --
    -- Note on rewrite rules:
    --
    -- This module includes GHC rewrite rules to optimize 'alterF' for
    -- the 'Const' and 'Identity' functors. In general, these rules
    -- improve performance. The sole exception is that when using
    -- 'Identity', deleting a key that is already absent takes longer
    -- than it would without the rules. If you expect this to occur
    -- a very large fraction of the time, you might consider using a
    -- private copy of the 'Identity' type.
    --
    -- Note: Unlike @Data.IntMap.alterF@ for 'IntMap', 'alterF' is /not/ a flipped
    -- version of the 'Control.Lens.At.at' combinator from "Control.Lens.At".
    -- However, it match the shape expected from most functions expecting
    -- lenses, getters, and setters, so can be thought of as a "psuedo-lens",
    -- with virtually the same practical applications as a legitimate lens.
    alterF ::
      Functor f =>
      (Maybe a -> f (Maybe a)) ->
      Key ->
      NEIntMap a ->
      f (IntMap a)
    alterF :: forall (f :: * -> *) a.
    Functor f =>
    (Maybe a -> f (Maybe a)) -> Key -> NEIntMap a -> f (IntMap a)
    alterF Maybe a -> f (Maybe a)
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (Maybe a -> IntMap a -> IntMap a)
    -> IntMap a -> Maybe a -> IntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k)) (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n) (Maybe a -> IntMap a) -> f (Maybe a) -> f (IntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f (Maybe a)
    f Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (Maybe a -> IntMap a -> IntMap a)
    -> IntMap a -> Maybe a -> IntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0)) IntMap a
    m (Maybe a -> IntMap a) -> f (Maybe a) -> f (IntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f (Maybe a)
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)
      Ordering
    GT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k0 a
    v (IntMap a -> IntMap a) -> f (IntMap a) -> f (IntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
    forall (f :: * -> *) a.
    Functor f =>
    (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
    M.alterF Maybe a -> f (Maybe a)
    f Key
    k IntMap a
    m
    {-# INLINEABLE [2] alterF #-}

    -- if f ~ Const b, it's a lookup
    {-# RULES
    "alterF/Const" forall k (f :: Maybe a -> Const b (Maybe a)).
      alterF f k =
        Const . getConst . f . lookup k
      #-}

    -- if f ~ Identity, it's an 'alter'
    {-# RULES
    "alterF/Identity" forall k (f :: Maybe a -> Identity (Maybe a)).
      alterF f k =
        Identity . alter (runIdentity . f) k
      #-}

    -- | /O(log n)/. Variant of 'alter' that disallows deletion.  Allows us to
    -- guarantee that the result is also a non-empty IntMap.
    alter' ::
      (Maybe a -> a) ->
      Key ->
      NEIntMap a ->
      NEIntMap a
    alter' :: forall a. (Maybe a -> a) -> Key -> NEIntMap a -> NEIntMap a
    alter' Maybe a -> a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Maybe a -> a
    f Maybe a
    forall a. Maybe a
    Nothing) (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 (Maybe a -> a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)) IntMap a
    m
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
    forall a. (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
    M.alter (a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> (Maybe a -> a) -> Maybe a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe a -> a
    f) Key
    k (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE alter' #-}

    -- | /O(log n)/. Variant of 'alterF' that disallows deletion.  Allows us to
    -- guarantee that the result is also a non-empty IntMap.
    --
    -- Like @Data.IntMap.alterF@ for 'IntMap', can be used to generalize and unify
    -- 'lookup' and 'insert'.  However, because it disallows deletion, it
    -- cannot be used to implement 'delete'.
    --
    -- See 'alterF' for usage information and caveats.
    --
    -- Note: Neither 'alterF' nor 'alterF'' can be considered flipped versions
    -- of the 'Control.Lens.At.at' combinator from "Control.Lens.At".  However,
    -- this can match the shape expected from most functions expecting lenses,
    -- getters, and setters, so can be thought of as a "psuedo-lens", with
    -- virtually the same practical applications as a legitimate lens.
    --
    -- __WARNING__: The rewrite rule for 'Identity' exposes an inconsistency in
    -- undefined behavior for "Data.IntMap".  @Data.IntMap.alterF@ will actually
    -- /maintain/ the original key in the map when used with 'Identity';
    -- however, @Data.IntMap.insertWith@ will /replace/ the orginal key in the
    -- map.  The rewrite rule for 'alterF'' has chosen to be faithful to
    -- @Data.IntMap.insertWith@, and /not/ @Data.IntMap.alterF@, for the sake of
    -- a cleaner implementation.
    alterF' ::
      Functor f =>
      (Maybe a -> f a) ->
      Key ->
      NEIntMap a ->
      f (NEIntMap a)
    alterF' :: forall (f :: * -> *) a.
    Functor f =>
    (Maybe a -> f a) -> Key -> NEIntMap a -> f (NEIntMap a)
    alterF' Maybe a -> f a
    f Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (a -> IntMap a -> NEIntMap a) -> IntMap a -> a -> NEIntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k) (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n) (a -> NEIntMap a) -> f a -> f (NEIntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f a
    f Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (a -> IntMap a -> NEIntMap a) -> IntMap a -> a -> NEIntMap a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0) IntMap a
    m (a -> NEIntMap a) -> f a -> f (NEIntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 a
    v (IntMap a -> NEIntMap a) -> f (IntMap a) -> f (NEIntMap a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
    forall (f :: * -> *) a.
    Functor f =>
    (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
    M.alterF ((a -> Maybe a) -> f a -> f (Maybe a)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Maybe a
    forall a. a -> Maybe a
    Just (f a -> f (Maybe a)) -> (Maybe a -> f a) -> Maybe a -> f (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe a -> f a
    f) Key
    k IntMap a
    m
    {-# INLINEABLE [2] alterF' #-}

    -- if f ~ Const b, it's a lookup
    {-# RULES
    "alterF'/Const" forall k (f :: Maybe a -> Const b a).
      alterF' f k =
        Const . getConst . f . lookup k
      #-}

    -- if f ~ Identity, it's an insertWith
    {-# RULES
    "alterF'/Identity" forall k (f :: Maybe a -> Identity a).
      alterF' f k =
        Identity . insertWith (\_ -> runIdentity . f . Just) k (runIdentity (f Nothing))
      #-}

    -- | /O(log n)/. Lookup the value at a key in the map.
    --
    -- The function will return the corresponding value as @('Just' value)@,
    -- or 'Nothing' if the key isn't in the map.
    --
    -- An example of using @lookup@:
    --
    -- > import Prelude hiding (lookup)
    -- > import Data.Map.NonEmpty
    -- >
    -- > employeeDept = fromList (("John","Sales") :| [("Bob","IT")])
    -- > deptCountry = fromList (("IT","USA") :| [("Sales","France")])
    -- > countryCurrency = fromList (("USA", "Dollar") :| [("France", "Euro")])
    -- >
    -- > employeeCurrency :: String -> Maybe String
    -- > employeeCurrency name = do
    -- >     dept <- lookup name employeeDept
    -- >     country <- lookup dept deptCountry
    -- >     lookup country countryCurrency
    -- >
    -- > main = do
    -- >     putStrLn $ "John's currency: " ++ (show (employeeCurrency "John"))
    -- >     putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))
    --
    -- The output of this program:
    --
    -- >   John's currency: Just "Euro"
    -- >   Pete's currency: Nothing
    lookup ::
      Key ->
      NEIntMap a ->
      Maybe a
    lookup :: forall a. Key -> NEIntMap a -> Maybe a
    lookup Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v
      Ordering
    GT -> Key -> IntMap a -> Maybe a
    forall a. Key -> IntMap a -> Maybe a
    M.lookup Key
    k IntMap a
    m
    {-# INLINE lookup #-}

    -- | /O(log n)/. Find the value at a key. Returns 'Nothing' when the
    -- element can not be found.
    --
    -- prop> fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing
    -- prop> fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a'
    (!?) :: NEIntMap a -> Key -> Maybe a
    !? :: forall a. NEIntMap a -> Key -> Maybe a
    (!?) = (Key -> NEIntMap a -> Maybe a) -> NEIntMap a -> Key -> Maybe a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Key -> NEIntMap a -> Maybe a
    forall a. Key -> NEIntMap a -> Maybe a
    lookup
    {-# INLINE (!?) #-}

    -- | /O(log n)/. Find the value at a key. Calls 'error' when the element
    -- can not be found.
    --
    -- > fromList ((5,'a') :| [(3,'b')]) ! 1    Error: element not in the map
    -- > fromList ((5,'a') :| [(3,'b')]) ! 5 == 'a'
    (!) :: NEIntMap a -> Key -> a
    ! :: forall a. NEIntMap a -> Key -> a
    (!) NEIntMap a
    m Key
    k = a -> Maybe a -> a
    forall a. a -> Maybe a -> a
    fromMaybe a
    forall {a}. a
    e (Maybe a -> a) -> Maybe a -> a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    m NEIntMap a -> Key -> Maybe a
    forall a. NEIntMap a -> Key -> Maybe a
    !? Key
    k
      where
        e :: a
    e = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NEIntMap.!: given key is not an element in the map"
    {-# INLINE (!) #-}

    infixl 9 !?
    infixl 9 !

    -- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns
    -- the value at key @k@ or returns default value @def@
    -- when the key is not in the map.
    --
    -- > findWithDefault 'x' 1 (fromList ((5,'a') :| [(3,'b')])) == 'x'
    -- > findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a'
    findWithDefault ::
      a ->
      Key ->
      NEIntMap a ->
      a
    findWithDefault :: forall a. a -> Key -> NEIntMap a -> a
    findWithDefault a
    def Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> a
    def
      Ordering
    EQ -> a
    v
      Ordering
    GT -> a -> Key -> IntMap a -> a
    forall a. a -> Key -> IntMap a -> a
    M.findWithDefault a
    def Key
    k IntMap a
    m
    {-# INLINE findWithDefault #-}

    -- | /O(log n)/. Is the key a member of the map? See also 'notMember'.
    --
    -- > member 5 (fromList ((5,'a') :| [(3,'b')])) == True
    -- > member 1 (fromList ((5,'a') :| [(3,'b')])) == False
    member :: Key -> NEIntMap a -> Bool
    member :: forall a. Key -> NEIntMap a -> Bool
    member Key
    k (NEIntMap Key
    k0 a
    _ IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Bool
    False
      Ordering
    EQ -> Bool
    True
      Ordering
    GT -> Key -> IntMap a -> Bool
    forall a. Key -> IntMap a -> Bool
    M.member Key
    k IntMap a
    m
    {-# INLINE member #-}

    -- | /O(log n)/. Is the key not a member of the map? See also 'member'.
    --
    -- > notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False
    -- > notMember 1 (fromList ((5,'a') :| [(3,'b')])) == True
    notMember :: Key -> NEIntMap a -> Bool
    notMember :: forall a. Key -> NEIntMap a -> Bool
    notMember Key
    k (NEIntMap Key
    k0 a
    _ IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Bool
    True
      Ordering
    EQ -> Bool
    False
      Ordering
    GT -> Key -> IntMap a -> Bool
    forall a. Key -> IntMap a -> Bool
    M.notMember Key
    k IntMap a
    m
    {-# INLINE notMember #-}

    -- | /O(log n)/. Find largest key smaller than the given one and return the
    -- corresponding (key, value) pair.
    --
    -- > lookupLT 3 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    -- > lookupLT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
    lookupLT :: Key -> NEIntMap a -> Maybe (Key, a)
    lookupLT :: forall a. Key -> NEIntMap a -> Maybe (Key, a)
    lookupLT Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Maybe (Key, a)
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Maybe (Key, a)
    forall a. Maybe a
    Nothing
      Ordering
    GT -> Key -> IntMap a -> Maybe (Key, a)
    forall a. Key -> IntMap a -> Maybe (Key, a)
    M.lookupLT Key
    k IntMap a
    m Maybe (Key, a) -> Maybe (Key, a) -> Maybe (Key, a)
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
    {-# INLINE lookupLT #-}

    -- | /O(log n)/. Find smallest key greater than the given one and return the
    -- corresponding (key, value) pair.
    --
    -- > lookupGT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
    -- > lookupGT 5 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    lookupGT :: Key -> NEIntMap a -> Maybe (Key, a)
    lookupGT :: forall a. Key -> NEIntMap a -> Maybe (Key, a)
    lookupGT Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
      Ordering
    EQ -> IntMap a -> Maybe (Key, a)
    forall a. IntMap a -> Maybe (Key, a)
    M.lookupMin IntMap a
    m
      Ordering
    GT -> Key -> IntMap a -> Maybe (Key, a)
    forall a. Key -> IntMap a -> Maybe (Key, a)
    M.lookupGT Key
    k IntMap a
    m
    {-# INLINE lookupGT #-}

    -- | /O(log n)/. Find largest key smaller or equal to the given one and return
    -- the corresponding (key, value) pair.
    --
    -- > lookupLE 2 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    -- > lookupLE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
    -- > lookupLE 5 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
    lookupLE :: Key -> NEIntMap a -> Maybe (Key, a)
    lookupLE :: forall a. Key -> NEIntMap a -> Maybe (Key, a)
    lookupLE Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> Maybe (Key, a)
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
      Ordering
    GT -> Key -> IntMap a -> Maybe (Key, a)
    forall a. Key -> IntMap a -> Maybe (Key, a)
    M.lookupLE Key
    k IntMap a
    m Maybe (Key, a) -> Maybe (Key, a) -> Maybe (Key, a)
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
    {-# INLINE lookupLE #-}

    -- | /O(log n)/. Find smallest key greater or equal to the given one and return
    -- the corresponding (key, value) pair.
    --
    -- > lookupGE 3 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
    -- > lookupGE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
    -- > lookupGE 6 (fromList ((3,'a') :| [(5,'b')])) == Nothing
    lookupGE :: Key -> NEIntMap a -> Maybe (Key, a)
    lookupGE :: forall a. Key -> NEIntMap a -> Maybe (Key, a)
    lookupGE Key
    k (NEIntMap Key
    k0 a
    v IntMap a
    m) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
      Ordering
    EQ -> (Key, a) -> Maybe (Key, a)
    forall a. a -> Maybe a
    Just (Key
    k0, a
    v)
      Ordering
    GT -> Key -> IntMap a -> Maybe (Key, a)
    forall a. Key -> IntMap a -> Maybe (Key, a)
    M.lookupGE Key
    k IntMap a
    m
    {-# INLINE lookupGE #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Union with a combining function.
    --
    -- > unionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "aA"), (7, "C")])
    unionWith ::
      (a -> a -> a) ->
      NEIntMap a ->
      NEIntMap a ->
      NEIntMap a
    unionWith :: forall a. (a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
    unionWith a -> a -> a
    f n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap a
    n2@(NEIntMap Key
    k2 a
    v2 IntMap a
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      Ordering
    LT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k1 a
    v1 (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWith a -> a -> a
    f IntMap a
    m1 (IntMap a -> IntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n2
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k1 (a -> a -> a
    f a
    v1 a
    v2) (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWith a -> a -> a
    f IntMap a
    m1 (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m2
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k2 a
    v2 (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWith a -> a -> a
    f (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1) (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m2
    {-# INLINE unionWith #-}

    -- | /O(m*log(n\/m + 1)), m <= n/.
    -- Union with a combining function, given the matching key.
    --
    -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
    -- > unionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "5:a|A"), (7, "C")])
    unionWithKey ::
      (Key -> a -> a -> a) ->
      NEIntMap a ->
      NEIntMap a ->
      NEIntMap a
    unionWithKey :: forall a.
    (Key -> a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
    unionWithKey Key -> a -> a -> a
    f n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap a
    n2@(NEIntMap Key
    k2 a
    v2 IntMap a
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      Ordering
    LT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k1 a
    v1 (IntMap a -> NEIntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWithKey Key -> a -> a -> a
    f IntMap a
    m1 (IntMap a -> IntMap a)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap a -> NEIntMap a) -> NEIntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n2
      Ordering
    EQ -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k1 (Key -> a -> a -> a
    f Key
    k1 a
    v1 a
    v2) (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWithKey Key -> a -> a -> a
    f IntMap a
    m1 (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m2
      Ordering
    GT -> Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k2 a
    v2 (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    forall a. (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    M.unionWithKey Key -> a -> a -> a
    f (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1) (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m2
    {-# INLINE unionWithKey #-}

    -- | The union of a non-empty list of maps, with a combining operation:
    --   (@'unionsWith' f == 'Data.Foldable.foldl1' ('unionWith' f)@).
    --
    -- > unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])])
    -- >     == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")])
    unionsWith ::
      Foldable1 f =>
      (a -> a -> a) ->
      f (NEIntMap a) ->
      NEIntMap a
    unionsWith :: forall (f :: * -> *) a.
    Foldable1 f =>
    (a -> a -> a) -> f (NEIntMap a) -> NEIntMap a
    unionsWith a -> a -> a
    f (f (NEIntMap a) -> NonEmpty (NEIntMap a)
    forall a. f a -> NonEmpty a
    forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
    F1.toNonEmpty -> (NEIntMap a
    m :| [NEIntMap a]
    ms)) = (NEIntMap a -> NEIntMap a -> NEIntMap a)
    -> NEIntMap a -> [NEIntMap a] -> NEIntMap a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    F.foldl' ((a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
    forall a. (a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a
    unionWith a -> a -> a
    f) NEIntMap a
    m [NEIntMap a]
    ms
    {-# INLINE unionsWith #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Difference of two maps.
    -- Return elements of the first map not existing in the second map.
    --
    -- Returns a potentially empty map ('IntMap'), in case the first map is
    -- a subset of the second map.
    --
    -- > difference (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 3 "b"
    difference ::
      NEIntMap a ->
      NEIntMap b ->
      IntMap a
    difference :: forall a b. NEIntMap a -> NEIntMap b -> IntMap a
    difference n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap b
    n2@(NEIntMap Key
    k2 b
    _ IntMap b
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      -- k1 is not in n2, so cannot be deleted
      Ordering
    LT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k1 a
    v1 (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.difference` NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap b
    n2
      -- k2 deletes k1, and only k1
      Ordering
    EQ -> IntMap a
    m1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.difference` IntMap b
    m2
      -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
      Ordering
    GT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.difference` IntMap b
    m2
    {-# INLINE difference #-}

    -- | Same as 'difference'.
    (\\) ::
      NEIntMap a ->
      NEIntMap b ->
      IntMap a
    \\ :: forall a b. NEIntMap a -> NEIntMap b -> IntMap a
    (\\) = NEIntMap a -> NEIntMap b -> IntMap a
    forall a b. NEIntMap a -> NEIntMap b -> IntMap a
    difference
    {-# INLINE (\\) #-}

    -- | /O(n+m)/. Difference with a combining function.
    -- When two equal keys are
    -- encountered, the combining function is applied to the values of these keys.
    -- If it returns 'Nothing', the element is discarded (proper set difference). If
    -- it returns (@'Just' y@), the element is updated with a new value @y@.
    --
    -- Returns a potentially empty map ('IntMap'), in case the first map is
    -- a subset of the second map and the function returns 'Nothing' for every
    -- pair.
    --
    -- > let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
    -- > differenceWith f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(3, "B"), (7, "C")]))
    -- >     == Data.IntMap.singleton 3 "b:B"
    differenceWith ::
      (a -> b -> Maybe a) ->
      NEIntMap a ->
      NEIntMap b ->
      IntMap a
    differenceWith :: forall a b.
    (a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
    differenceWith a -> b -> Maybe a
    f = (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
    forall a b.
    (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
    differenceWithKey ((a -> b -> Maybe a) -> Key -> a -> b -> Maybe a
    forall a b. a -> b -> a
    const a -> b -> Maybe a
    f)
    {-# INLINE differenceWith #-}

    -- | /O(n+m)/. Difference with a combining function. When two equal keys are
    -- encountered, the combining function is applied to the key and both values.
    -- If it returns 'Nothing', the element is discarded (proper set difference). If
    -- it returns (@'Just' y@), the element is updated with a new value @y@.
    --
    -- Returns a potentially empty map ('IntMap'), in case the first map is
    -- a subset of the second map and the function returns 'Nothing' for every
    -- pair.
    --
    -- > let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
    -- > differenceWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(3, "B"), (10, "C")]))
    -- >     == Data.IntMap.singleton 3 "3:b|B"
    differenceWithKey ::
      (Key -> a -> b -> Maybe a) ->
      NEIntMap a ->
      NEIntMap b ->
      IntMap a
    differenceWithKey :: forall a b.
    (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a
    differenceWithKey Key -> a -> b -> Maybe a
    f n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap b
    n2@(NEIntMap Key
    k2 b
    v2 IntMap b
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      -- k1 is not in n2, so cannot be deleted
      Ordering
    LT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k1 a
    v1 (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    forall a b.
    (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    M.differenceWithKey Key -> a -> b -> Maybe a
    f IntMap a
    m1 (NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap b
    n2)
      -- k2 deletes k1, and only k1
      Ordering
    EQ -> (IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k1) (Key -> a -> b -> Maybe a
    f Key
    k1 a
    v1 b
    v2) ((Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    forall a b.
    (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    M.differenceWithKey Key -> a -> b -> Maybe a
    f IntMap a
    m1 IntMap b
    m2)
      -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
      Ordering
    GT -> (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    forall a b.
    (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
    M.differenceWithKey Key -> a -> b -> Maybe a
    f (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1) IntMap b
    m2
    {-# INLINE differenceWithKey #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Intersection of two maps.
    -- Return data in the first map for the keys existing in both maps.
    -- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@).
    --
    -- Returns a potentially empty map ('IntMap'), in case the two maps share no
    -- keys in common.
    --
    -- > intersection (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "a"
    intersection ::
      NEIntMap a ->
      NEIntMap b ->
      IntMap a
    intersection :: forall a b. NEIntMap a -> NEIntMap b -> IntMap a
    intersection n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap b
    n2@(NEIntMap Key
    k2 b
    _ IntMap b
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      -- k1 is not in n2
      Ordering
    LT -> IntMap a
    m1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.intersection` NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap b
    n2
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k1 a
    v1 (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.intersection` IntMap b
    m2
      -- k2 is not in n1
      Ordering
    GT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1 IntMap a -> IntMap b -> IntMap a
    forall a b. IntMap a -> IntMap b -> IntMap a
    `M.intersection` IntMap b
    m2
    {-# INLINE intersection #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.
    --
    -- Returns a potentially empty map ('IntMap'), in case the two maps share no
    -- keys in common.
    --
    -- > intersectionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "aA"
    intersectionWith ::
      (a -> b -> c) ->
      NEIntMap a ->
      NEIntMap b ->
      IntMap c
    intersectionWith :: forall a b c. (a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
    intersectionWith a -> b -> c
    f = (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
    forall a b c.
    (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
    intersectionWithKey ((a -> b -> c) -> Key -> a -> b -> c
    forall a b. a -> b -> a
    const a -> b -> c
    f)
    {-# INLINE intersectionWith #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Intersection with a combining function.
    --
    -- Returns a potentially empty map ('IntMap'), in case the two maps share no
    -- keys in common.
    --
    -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
    -- > intersectionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "5:a|A"
    intersectionWithKey ::
      (Key -> a -> b -> c) ->
      NEIntMap a ->
      NEIntMap b ->
      IntMap c
    intersectionWithKey :: forall a b c.
    (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c
    intersectionWithKey Key -> a -> b -> c
    f n1 :: NEIntMap a
    n1@(NEIntMap Key
    k1 a
    v1 IntMap a
    m1) n2 :: NEIntMap b
    n2@(NEIntMap Key
    k2 b
    v2 IntMap b
    m2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k1 Key
    k2 of
      -- k1 is not in n2
      Ordering
    LT -> (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    forall a b c.
    (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    M.intersectionWithKey Key -> a -> b -> c
    f IntMap a
    m1 (NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap b
    n2)
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> Key -> c -> IntMap c -> IntMap c
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k1 (Key -> a -> b -> c
    f Key
    k1 a
    v1 b
    v2) (IntMap c -> IntMap c) -> IntMap c -> IntMap c
    forall a b. (a -> b) -> a -> b
    $ (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    forall a b c.
    (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    M.intersectionWithKey Key -> a -> b -> c
    f IntMap a
    m1 IntMap b
    m2
      -- k2 is not in n1
      Ordering
    GT -> (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    forall a b c.
    (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
    M.intersectionWithKey Key -> a -> b -> c
    f (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n1) IntMap b
    m2
    {-# INLINE intersectionWithKey #-}

    -- | /O(n)/. IntMap a function over all values in the map.
    --
    -- > let f key x = (show key) ++ ":" ++ x
    -- > mapWithKey f (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "3:b") :| [(5, "5:a")])
    mapWithKey :: (Key -> a -> b) -> NEIntMap a -> NEIntMap b
    mapWithKey :: forall a b. (Key -> a -> b) -> NEIntMap a -> NEIntMap b
    mapWithKey Key -> a -> b
    f (NEIntMap Key
    k a
    v IntMap a
    m) = Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Key -> a -> b
    f Key
    k a
    v) ((Key -> a -> b) -> IntMap a -> IntMap b
    forall a b. (Key -> a -> b) -> IntMap a -> IntMap b
    M.mapWithKey Key -> a -> b
    f IntMap a
    m)
    {-# NOINLINE [1] mapWithKey #-}

    {-# RULES
    "mapWithKey/mapWithKey" forall f g xs.
      mapWithKey f (mapWithKey g xs) =
        mapWithKey (\k a -> f k (g k a)) xs
    "mapWithKey/map" forall f g xs.
      mapWithKey f (map g xs) =
        mapWithKey (\k a -> f k (g a)) xs
    "map/mapWithKey" forall f g xs.
      map f (mapWithKey g xs) =
        mapWithKey (\k a -> f (g k a)) xs
      #-}

    -- | /O(n)/. The function 'mapAccum' threads an accumulating argument
    -- through the map in ascending order of keys.
    --
    -- > let f a b = (a ++ b, b ++ "X")
    -- > mapAccum f "Everything: " (fromList ((5,"a") :| [(3,"b")])) == ("Everything: ba", fromList ((3, "bX") :| [(5, "aX")]))
    mapAccum ::
      (a -> b -> (a, c)) ->
      a ->
      NEIntMap b ->
      (a, NEIntMap c)
    mapAccum :: forall a b c.
    (a -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
    mapAccum a -> b -> (a, c)
    f = (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
    forall a b c.
    (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
    mapAccumWithKey (\a
    x Key
    _ -> a -> b -> (a, c)
    f a
    x)
    {-# INLINE mapAccum #-}

    -- | /O(n)/. The function 'mapAccumWithKey' threads an accumulating
    -- argument through the map in ascending order of keys.
    --
    -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
    -- > mapAccumWithKey f "Everything:" (fromList ((5,"a") :| [(3,"b")])) == ("Everything: 3-b 5-a", fromList ((3, "bX") :| [(5, "aX")]))
    mapAccumWithKey ::
      (a -> Key -> b -> (a, c)) ->
      a ->
      NEIntMap b ->
      (a, NEIntMap c)
    mapAccumWithKey :: forall a b c.
    (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
    mapAccumWithKey a -> Key -> b -> (a, c)
    f a
    z0 (NEIntMap Key
    k b
    v IntMap b
    m) = (a
    z2, Key -> c -> IntMap c -> NEIntMap c
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k c
    v' IntMap c
    m')
      where
        ~(a
    z1, c
    v') = a -> Key -> b -> (a, c)
    f a
    z0 Key
    k b
    v
        ~(a
    z2, IntMap c
    m') = (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
    forall a b c.
    (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
    M.mapAccumWithKey a -> Key -> b -> (a, c)
    f a
    z1 IntMap b
    m
    {-# INLINE mapAccumWithKey #-}

    -- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating
    -- argument through the map in descending order of keys.
    mapAccumRWithKey ::
      (a -> Key -> b -> (a, c)) ->
      a ->
      NEIntMap b ->
      (a, NEIntMap c)
    mapAccumRWithKey :: forall a b c.
    (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
    mapAccumRWithKey a -> Key -> b -> (a, c)
    f a
    z0 (NEIntMap Key
    k b
    v IntMap b
    m) = (a
    z2, Key -> c -> IntMap c -> NEIntMap c
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k c
    v' IntMap c
    m')
      where
        ~(a
    z1, IntMap c
    m') = (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
    forall a b c.
    (a -> Key -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
    M.mapAccumRWithKey a -> Key -> b -> (a, c)
    f a
    z0 IntMap b
    m
        ~(a
    z2, c
    v') = a -> Key -> b -> (a, c)
    f a
    z1 Key
    k b
    v
    {-# INLINE mapAccumRWithKey #-}

    -- | /O(n*log n)/.
    -- @'mapKeys' f s@ is the map obtained by applying @f@ to each key of @s@.
    --
    -- The size of the result may be smaller if @f@ maps two or more distinct
    -- keys to the same new key.  In this case the value at the greatest of the
    -- original keys is retained.
    --
    -- While the size of the result map may be smaller than the input map, the
    -- output map is still guaranteed to be non-empty if the input map is
    -- non-empty.
    --
    -- > mapKeys (+ 1) (fromList ((5,"a") :| [(3,"b")]))                        == fromList ((4, "b") :| [(6, "a")])
    -- > mapKeys (\ _ -> 1) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 1 "c"
    -- > mapKeys (\ _ -> 3) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 3 "c"
    mapKeys ::
      (Key -> Key) ->
      NEIntMap a ->
      NEIntMap a
    mapKeys :: forall a. (Key -> Key) -> NEIntMap a -> NEIntMap a
    mapKeys Key -> Key
    f (NEIntMap Key
    k0 a
    v0 IntMap a
    m) =
      (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    forall a. (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromListWith a -> a -> a
    forall a b. a -> b -> a
    const
        (NonEmpty (Key, a) -> NEIntMap a)
    -> (IntMap a -> NonEmpty (Key, a)) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Key -> Key
    f Key
    k0, a
    v0) (Key, a) -> [(Key, a)] -> NonEmpty (Key, a)
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([(Key, a)] -> NonEmpty (Key, a))
    -> (IntMap a -> [(Key, a)]) -> IntMap a -> NonEmpty (Key, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> [(Key, a)] -> [(Key, a)])
    -> [(Key, a)] -> IntMap a -> [(Key, a)]
    forall a b. (Key -> a -> b -> b) -> b -> IntMap a -> b
    M.foldrWithKey (\Key
    k a
    v [(Key, a)]
    kvs -> (Key -> Key
    f Key
    k, a
    v) (Key, a) -> [(Key, a)] -> [(Key, a)]
    forall a. a -> [a] -> [a]
    : [(Key, a)]
    kvs) []
        (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINEABLE mapKeys #-}

    -- | /O(n*log n)/.
    -- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
    --
    -- The size of the result may be smaller if @f@ maps two or more distinct
    -- keys to the same new key.  In this case the associated values will be
    -- combined using @c@. The value at the greater of the two original keys
    -- is used as the first argument to @c@.
    --
    -- While the size of the result map may be smaller than the input map, the
    -- output map is still guaranteed to be non-empty if the input map is
    -- non-empty.
    --
    -- > mapKeysWith (++) (\ _ -> 1) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 1 "cdab"
    -- > mapKeysWith (++) (\ _ -> 3) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 3 "cdab"
    mapKeysWith ::
      (a -> a -> a) ->
      (Key -> Key) ->
      NEIntMap a ->
      NEIntMap a
    mapKeysWith :: forall a. (a -> a -> a) -> (Key -> Key) -> NEIntMap a -> NEIntMap a
    mapKeysWith a -> a -> a
    c Key -> Key
    f (NEIntMap Key
    k0 a
    v0 IntMap a
    m) =
      (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    forall a. (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a
    fromListWith a -> a -> a
    c
        (NonEmpty (Key, a) -> NEIntMap a)
    -> (IntMap a -> NonEmpty (Key, a)) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Key -> Key
    f Key
    k0, a
    v0) (Key, a) -> [(Key, a)] -> NonEmpty (Key, a)
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([(Key, a)] -> NonEmpty (Key, a))
    -> (IntMap a -> [(Key, a)]) -> IntMap a -> NonEmpty (Key, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> [(Key, a)] -> [(Key, a)])
    -> [(Key, a)] -> IntMap a -> [(Key, a)]
    forall a b. (Key -> a -> b -> b) -> b -> IntMap a -> b
    M.foldrWithKey (\Key
    k a
    v [(Key, a)]
    kvs -> (Key -> Key
    f Key
    k, a
    v) (Key, a) -> [(Key, a)] -> [(Key, a)]
    forall a. a -> [a] -> [a]
    : [(Key, a)]
    kvs) []
        (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINEABLE mapKeysWith #-}

    -- | /O(n)/.
    -- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@
    -- is strictly monotonic.
    -- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
    -- /The precondition is not checked./
    -- Semi-formally, we have:
    --
    -- > and [x < y ==> f x < f y | x <- ls, y <- ls]
    -- >                     ==> mapKeysMonotonic f s == mapKeys f s
    -- >     where ls = keys s
    --
    -- This means that @f@ maps distinct original keys to distinct resulting keys.
    -- This function has better performance than 'mapKeys'.
    --
    -- While the size of the result map may be smaller than the input map, the
    -- output map is still guaranteed to be non-empty if the input map is
    -- non-empty.
    --
    -- > mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")])) == fromList ((6, "b") :| [(10, "a")])
    -- > valid (mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")]))) == True
    -- > valid (mapKeysMonotonic (\ _ -> 1)     (fromList ((5,"a") :| [(3,"b")]))) == False
    mapKeysMonotonic ::
      (Key -> Key) ->
      NEIntMap a ->
      NEIntMap a
    mapKeysMonotonic :: forall a. (Key -> Key) -> NEIntMap a -> NEIntMap a
    mapKeysMonotonic Key -> Key
    f (NEIntMap Key
    k a
    v IntMap a
    m) =
      Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap (Key -> Key
    f Key
    k) a
    v
        (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> Key) -> IntMap a -> IntMap a
    forall a. (Key -> Key) -> IntMap a -> IntMap a
    M.mapKeysMonotonic Key -> Key
    f
        (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE mapKeysMonotonic #-}

    -- | /O(n)/. Fold the keys and values in the map using the given right-associative
    -- binary operator, such that
    -- @'foldrWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
    --
    -- For example,
    --
    -- > keysList map = foldrWithKey (\k x ks -> k:ks) [] map
    foldrWithKey :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b
    foldrWithKey :: forall a b. (Key -> a -> b -> b) -> b -> NEIntMap a -> b
    foldrWithKey Key -> a -> b -> b
    f b
    z (NEIntMap Key
    k a
    v IntMap a
    m) = Key -> a -> b -> b
    f Key
    k a
    v (b -> b) -> (IntMap a -> b) -> IntMap a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> b -> b) -> b -> IntMap a -> b
    forall a b. (Key -> a -> b -> b) -> b -> IntMap a -> b
    M.foldrWithKey Key -> a -> b -> b
    f b
    z (IntMap a -> b) -> IntMap a -> b
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE foldrWithKey #-}

    -- | /O(n)/. Fold the keys and values in the map using the given left-associative
    -- binary operator, such that
    -- @'foldlWithKey' f z == 'Prelude.foldl' (\\z' (kx, x) -> f z' kx x) z . 'toAscList'@.
    --
    -- For example,
    --
    -- > keysList = reverse . foldlWithKey (\ks k x -> k:ks) []
    foldlWithKey :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a
    foldlWithKey :: forall a b. (a -> Key -> b -> a) -> a -> NEIntMap b -> a
    foldlWithKey a -> Key -> b -> a
    f a
    z (NEIntMap Key
    k b
    v IntMap b
    m) = (a -> Key -> b -> a) -> a -> IntMap b -> a
    forall a b. (a -> Key -> b -> a) -> a -> IntMap b -> a
    M.foldlWithKey a -> Key -> b -> a
    f (a -> Key -> b -> a
    f a
    z Key
    k b
    v) IntMap b
    m
    {-# INLINE foldlWithKey #-}

    -- | /O(n)/. A strict version of 'foldr1'. Each application of the operator
    -- is evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldr1' :: (a -> a -> a) -> NEIntMap a -> a
    foldr1' :: forall a. (a -> a -> a) -> NEIntMap a -> a
    foldr1' a -> a -> a
    f (NEIntMap Key
    _ a
    v IntMap a
    m) = case IntMap a -> Maybe (a, IntMap a)
    forall a. IntMap a -> Maybe (a, IntMap a)
    M.maxView IntMap a
    m of
      Maybe (a, IntMap a)
    Nothing -> a
    v
      Just (a
    y, IntMap a
    m') -> let !z :: a
    z = (a -> a -> a) -> a -> IntMap a -> a
    forall a b. (a -> b -> b) -> b -> IntMap a -> b
    M.foldr' a -> a -> a
    f a
    y IntMap a
    m' in a
    v a -> a -> a
    `f` a
    z
    {-# INLINE foldr1' #-}

    -- | /O(n)/. A strict version of 'foldl1'. Each application of the operator
    -- is evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldl1' :: (a -> a -> a) -> NEIntMap a -> a
    foldl1' :: forall a. (a -> a -> a) -> NEIntMap a -> a
    foldl1' a -> a -> a
    f (NEIntMap Key
    _ a
    v IntMap a
    m) = (a -> a -> a) -> a -> IntMap a -> a
    forall a b. (a -> b -> a) -> a -> IntMap b -> a
    M.foldl' a -> a -> a
    f a
    v IntMap a
    m
    {-# INLINE foldl1' #-}

    -- | /O(n)/. A strict version of 'foldrWithKey'. Each application of the operator is
    -- evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldrWithKey' :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b
    foldrWithKey' :: forall a b. (Key -> a -> b -> b) -> b -> NEIntMap a -> b
    foldrWithKey' Key -> a -> b -> b
    f b
    z (NEIntMap Key
    k a
    v IntMap a
    m) = Key -> a -> b -> b
    f Key
    k a
    v b
    y
      where
        !y :: b
    y = (Key -> a -> b -> b) -> b -> IntMap a -> b
    forall a b. (Key -> a -> b -> b) -> b -> IntMap a -> b
    M.foldrWithKey Key -> a -> b -> b
    f b
    z IntMap a
    m
    {-# INLINE foldrWithKey' #-}

    -- | /O(n)/. A strict version of 'foldlWithKey'. Each application of the operator is
    -- evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldlWithKey' :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a
    foldlWithKey' :: forall a b. (a -> Key -> b -> a) -> a -> NEIntMap b -> a
    foldlWithKey' a -> Key -> b -> a
    f a
    z (NEIntMap Key
    k b
    v IntMap b
    m) = (a -> Key -> b -> a) -> a -> IntMap b -> a
    forall a b. (a -> Key -> b -> a) -> a -> IntMap b -> a
    M.foldlWithKey' a -> Key -> b -> a
    f a
    x IntMap b
    m
      where
        !x :: a
    x = a -> Key -> b -> a
    f a
    z Key
    k b
    v
    {-# INLINE foldlWithKey' #-}

    -- | /O(n)/. Return all keys of the map in ascending order.
    --
    -- > keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])
    keys :: NEIntMap a -> NonEmpty Key
    keys :: forall a. NEIntMap a -> NonEmpty Key
    keys (NEIntMap Key
    k a
    _ IntMap a
    m) = Key
    k Key -> [Key] -> NonEmpty Key
    forall a. a -> [a] -> NonEmpty a
    :| IntMap a -> [Key]
    forall a. IntMap a -> [Key]
    M.keys IntMap a
    m
    {-# INLINE keys #-}

    -- | /O(n)/. An alias for 'toAscList'. Return all key\/value pairs in the map
    -- in ascending key order.
    --
    -- > assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])
    assocs :: NEIntMap a -> NonEmpty (Key, a)
    assocs :: forall a. NEIntMap a -> NonEmpty (Key, a)
    assocs = NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
    {-# INLINE assocs #-}

    -- | /O(n)/. The non-empty set of all keys of the map.
    --
    -- > keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5])
    keysSet :: NEIntMap a -> NEIntSet
    keysSet :: forall a. NEIntMap a -> NEIntSet
    keysSet (NEIntMap Key
    k a
    _ IntMap a
    m) = Key -> IntSet -> NEIntSet
    NEIntSet Key
    k (IntMap a -> IntSet
    forall a. IntMap a -> IntSet
    M.keysSet IntMap a
    m)
    {-# INLINE keysSet #-}

    -- | /O(n)/. Convert the map to a list of key\/value pairs where the keys are
    -- in ascending order.
    --
    -- > toAscList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])
    toAscList :: NEIntMap a -> NonEmpty (Key, a)
    toAscList :: forall a. NEIntMap a -> NonEmpty (Key, a)
    toAscList = NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
    {-# INLINE toAscList #-}

    -- | /O(n)/. Convert the map to a list of key\/value pairs where the keys
    -- are in descending order.
    --
    -- > toDescList (fromList ((5,"a") :| [(3,"b")])) == ((5,"a") :| [(3,"b")])
    toDescList :: NEIntMap a -> NonEmpty (Key, a)
    toDescList :: forall a. NEIntMap a -> NonEmpty (Key, a)
    toDescList (NEIntMap Key
    k0 a
    v0 IntMap a
    m) = (NonEmpty (Key, a) -> Key -> a -> NonEmpty (Key, a))
    -> NonEmpty (Key, a) -> IntMap a -> NonEmpty (Key, a)
    forall a b. (a -> Key -> b -> a) -> a -> IntMap b -> a
    M.foldlWithKey' NonEmpty (Key, a) -> Key -> a -> NonEmpty (Key, a)
    forall {a} {b}. NonEmpty (a, b) -> a -> b -> NonEmpty (a, b)
    go ((Key
    k0, a
    v0) (Key, a) -> [(Key, a)] -> NonEmpty (Key, a)
    forall a. a -> [a] -> NonEmpty a
    :| []) IntMap a
    m
      where
        go :: NonEmpty (a, b) -> a -> b -> NonEmpty (a, b)
    go NonEmpty (a, b)
    xs a
    k b
    v = (a
    k, b
    v) (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| NonEmpty (a, b)
    xs
    {-# INLINE toDescList #-}

    -- | /O(n)/. Filter all values that satisfy the predicate.
    --
    -- Returns a potentially empty map ('IntMap'), because we could
    -- potentailly filter out all items in the original 'NEIntMap'.
    --
    -- > filter (> "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    -- > filter (> "x") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty
    -- > filter (< "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty
    filter ::
      (a -> Bool) ->
      NEIntMap a ->
      IntMap a
    filter :: forall a. (a -> Bool) -> NEIntMap a -> IntMap a
    filter a -> Bool
    f (NEIntMap Key
    k a
    v IntMap a
    m)
      | a -> Bool
    f a
    v = Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Bool) -> IntMap a -> IntMap a
    forall a. (a -> Bool) -> IntMap a -> IntMap a
    M.filter a -> Bool
    f (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
      | Bool
    otherwise = (a -> Bool) -> IntMap a -> IntMap a
    forall a. (a -> Bool) -> IntMap a -> IntMap a
    M.filter a -> Bool
    f IntMap a
    m
    {-# INLINE filter #-}

    -- | /O(n)/. Filter all keys\/values that satisfy the predicate.
    --
    -- Returns a potentially empty map ('IntMap'), because we could
    -- potentailly filter out all items in the original 'NEIntMap'.
    --
    -- > filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    filterWithKey ::
      (Key -> a -> Bool) ->
      NEIntMap a ->
      IntMap a
    filterWithKey :: forall a. (Key -> a -> Bool) -> NEIntMap a -> IntMap a
    filterWithKey Key -> a -> Bool
    f (NEIntMap Key
    k a
    v IntMap a
    m)
      | Key -> a -> Bool
    f Key
    k a
    v = Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> Bool) -> IntMap a -> IntMap a
    forall a. (Key -> a -> Bool) -> IntMap a -> IntMap a
    M.filterWithKey Key -> a -> Bool
    f (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
      | Bool
    otherwise = (Key -> a -> Bool) -> IntMap a -> IntMap a
    forall a. (Key -> a -> Bool) -> IntMap a -> IntMap a
    M.filterWithKey Key -> a -> Bool
    f IntMap a
    m
    {-# INLINE filterWithKey #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Restrict an 'NEIntMap' to only those keys
    -- found in a 'Data.Set.Set'.
    --
    -- @
    -- m \`restrictKeys\` s = 'filterWithKey' (\k _ -> k ``Set.member`` s) m
    -- m \`restrictKeys\` s = m ``intersection`` 'fromSet' (const ()) s
    -- @
    restrictKeys ::
      NEIntMap a ->
      IntSet ->
      IntMap a
    restrictKeys :: forall a. NEIntMap a -> IntSet -> IntMap a
    restrictKeys n :: NEIntMap a
    n@(NEIntMap Key
    k a
    v IntMap a
    m) IntSet
    xs = case IntSet -> Maybe (Key, IntSet)
    S.minView IntSet
    xs of
      Maybe (Key, IntSet)
    Nothing -> IntMap a
    forall a. IntMap a
    M.empty
      Just (Key
    y, IntSet
    ys) -> case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    y of
        -- k is not in xs
        Ordering
    LT -> IntMap a
    m IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.restrictKeys` IntSet
    xs
        -- k and y are a part of the result
        Ordering
    EQ -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.restrictKeys` IntSet
    ys
        -- y is not in m
        Ordering
    GT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.restrictKeys` IntSet
    ys
    {-# INLINE restrictKeys #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Remove all keys in a 'Data.Set.Set' from
    -- an 'NEIntMap'.
    --
    -- @
    -- m \`withoutKeys\` s = 'filterWithKey' (\k _ -> k ``Set.notMember`` s) m
    -- m \`withoutKeys\` s = m ``difference`` 'fromSet' (const ()) s
    -- @
    withoutKeys ::
      NEIntMap a ->
      IntSet ->
      IntMap a
    withoutKeys :: forall a. NEIntMap a -> IntSet -> IntMap a
    withoutKeys n :: NEIntMap a
    n@(NEIntMap Key
    k a
    v IntMap a
    m) IntSet
    xs = case IntSet -> Maybe (Key, IntSet)
    S.minView IntSet
    xs of
      Maybe (Key, IntSet)
    Nothing -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n
      Just (Key
    y, IntSet
    ys) -> case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    y of
        -- k is not in xs, so cannot be deleted
        Ordering
    LT -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.withoutKeys` IntSet
    xs
        -- y deletes k, and only k
        Ordering
    EQ -> IntMap a
    m IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.withoutKeys` IntSet
    ys
        -- y is not in n, so cannot delete anything, so we can just difference n and ys
        Ordering
    GT -> NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap NEIntMap a
    n IntMap a -> IntSet -> IntMap a
    forall a. IntMap a -> IntSet -> IntMap a
    `M.withoutKeys` IntSet
    ys
    {-# INLINE withoutKeys #-}

    -- | /O(n)/. Partition the map according to a predicate.
    --
    -- Returns a 'These' with potentially two non-empty maps:
    --
    -- *   @'This' n1@ means that the predicate was true for all items.
    -- *   @'That' n2@ means that the predicate was false for all items.
    -- *   @'These' n1 n2@ gives @n1@ (all of the items that were true for the
    --     predicate) and @n2@ (all of the items that were false for the
    --     predicate).
    --
    -- See also 'split'.
    --
    -- > partition (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a")
    -- > partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
    -- > partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))
    partition ::
      (a -> Bool) ->
      NEIntMap a ->
      These (NEIntMap a) (NEIntMap a)
    partition :: forall a.
    (a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    partition a -> Bool
    f = (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a.
    (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    partitionWithKey ((a -> Bool) -> Key -> a -> Bool
    forall a b. a -> b -> a
    const a -> Bool
    f)
    {-# INLINE partition #-}

    -- | /O(n)/. Partition the map according to a predicate.
    --
    -- Returns a 'These' with potentially two non-empty maps:
    --
    -- *   @'This' n1@ means that the predicate was true for all items,
    --     returning the original map.
    -- *   @'That' n2@ means that the predicate was false for all items,
    --     returning the original map.
    -- *   @'These' n1 n2@ gives @n1@ (all of the items that were true for the
    --     predicate) and @n2@ (all of the items that were false for the
    --     predicate).
    --
    -- See also 'split'.
    --
    -- > partitionWithKey (\ k _ -> k > 3) (fromList ((5,"a") :| [(3,"b")])) == These (singleton 5 "a") (singleton 3 "b")
    -- > partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
    -- > partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))
    partitionWithKey ::
      (Key -> a -> Bool) ->
      NEIntMap a ->
      These (NEIntMap a) (NEIntMap a)
    partitionWithKey :: forall a.
    (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    partitionWithKey Key -> a -> Bool
    f n :: NEIntMap a
    n@(NEIntMap Key
    k a
    v IntMap a
    m0) = case (IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m1, IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m2) of
      (Maybe (NEIntMap a)
    Nothing, Maybe (NEIntMap a)
    Nothing)
        | Key -> a -> Bool
    f Key
    k a
    v -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This NEIntMap a
    n
        | Bool
    otherwise -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That NEIntMap a
    n
      (Just NEIntMap a
    n1, Maybe (NEIntMap a)
    Nothing)
        | Key -> a -> Bool
    f Key
    k a
    v -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This NEIntMap a
    n
        | Bool
    otherwise -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These NEIntMap a
    n1 (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v)
      (Maybe (NEIntMap a)
    Nothing, Just NEIntMap a
    n2)
        | Key -> a -> Bool
    f Key
    k a
    v -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v) NEIntMap a
    n2
        | Bool
    otherwise -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That NEIntMap a
    n
      (Just NEIntMap a
    n1, Just NEIntMap a
    n2)
        | Key -> a -> Bool
    f Key
    k a
    v -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k a
    v IntMap a
    m1) NEIntMap a
    n2
        | Bool
    otherwise -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These NEIntMap a
    n1 (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k a
    v IntMap a
    m2)
      where
        (IntMap a
    m1, IntMap a
    m2) = (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
    forall a. (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)
    M.partitionWithKey Key -> a -> Bool
    f IntMap a
    m0
    {-# INLINEABLE partitionWithKey #-}

    -- | /O(n)/. Map values and collect the 'Just' results.
    --
    -- Returns a potentially empty map ('IntMap'), because the function could
    -- potentially return 'Nothing' on all items in the 'NEIntMap'.
    --
    -- > let f x = if x == "a" then Just "new a" else Nothing
    -- > mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "new a"
    mapMaybe ::
      (a -> Maybe b) ->
      NEIntMap a ->
      IntMap b
    mapMaybe :: forall a b. (a -> Maybe b) -> NEIntMap a -> IntMap b
    mapMaybe a -> Maybe b
    f = (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b
    forall a b. (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b
    mapMaybeWithKey ((a -> Maybe b) -> Key -> a -> Maybe b
    forall a b. a -> b -> a
    const a -> Maybe b
    f)
    {-# INLINE mapMaybe #-}

    -- | /O(n)/. Map keys\/values and collect the 'Just' results.
    --
    -- Returns a potentially empty map ('IntMap'), because the function could
    -- potentially return 'Nothing' on all items in the 'NEIntMap'.
    --
    -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
    -- > mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "key : 3"
    mapMaybeWithKey ::
      (Key -> a -> Maybe b) ->
      NEIntMap a ->
      IntMap b
    mapMaybeWithKey :: forall a b. (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b
    mapMaybeWithKey Key -> a -> Maybe b
    f (NEIntMap Key
    k a
    v IntMap a
    m) = (IntMap b -> IntMap b)
    -> (b -> IntMap b -> IntMap b) -> Maybe b -> IntMap b -> IntMap b
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap b -> IntMap b
    forall a. a -> a
    id (Key -> b -> IntMap b -> IntMap b
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k) (Key -> a -> Maybe b
    f Key
    k a
    v) ((Key -> a -> Maybe b) -> IntMap a -> IntMap b
    forall a b. (Key -> a -> Maybe b) -> IntMap a -> IntMap b
    M.mapMaybeWithKey Key -> a -> Maybe b
    f IntMap a
    m)
    {-# INLINE mapMaybeWithKey #-}

    -- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
    --
    -- Returns a 'These' with potentially two non-empty maps:
    --
    -- *   @'This' n1@ means that the results were all 'Left'.
    -- *   @'That' n2@ means that the results were all 'Right'.
    -- *   @'These' n1 n2@ gives @n1@ (the map where the results were 'Left')
    --     and @n2@ (the map where the results were 'Right')
    --
    -- > let f a = if a < "c" then Left a else Right a
    -- > mapEither f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    -- >     == These (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")]))
    -- >
    -- > mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    -- >     == That (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    mapEither ::
      (a -> Either b c) ->
      NEIntMap a ->
      These (NEIntMap b) (NEIntMap c)
    mapEither :: forall a b c.
    (a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
    mapEither a -> Either b c
    f = (Key -> a -> Either b c)
    -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
    forall a b c.
    (Key -> a -> Either b c)
    -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
    mapEitherWithKey ((a -> Either b c) -> Key -> a -> Either b c
    forall a b. a -> b -> a
    const a -> Either b c
    f)
    {-# INLINE mapEither #-}

    -- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
    --
    -- Returns a 'These' with potentially two non-empty maps:
    --
    -- *   @'This' n1@ means that the results were all 'Left'.
    -- *   @'That' n2@ means that the results were all 'Right'.
    -- *   @'These' n1 n2@ gives @n1@ (the map where the results were 'Left')
    --     and @n2@ (the map where the results were 'Right')
    --
    -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
    -- > mapEitherWithKey f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    -- >     == These (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")]))
    -- >
    -- > mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    -- >     == That (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))
    mapEitherWithKey ::
      (Key -> a -> Either b c) ->
      NEIntMap a ->
      These (NEIntMap b) (NEIntMap c)
    mapEitherWithKey :: forall a b c.
    (Key -> a -> Either b c)
    -> NEIntMap a -> These (NEIntMap b) (NEIntMap c)
    mapEitherWithKey Key -> a -> Either b c
    f (NEIntMap Key
    k a
    v IntMap a
    m0) = case (IntMap b -> Maybe (NEIntMap b)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap b
    m1, IntMap c -> Maybe (NEIntMap c)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap c
    m2) of
      (Maybe (NEIntMap b)
    Nothing, Maybe (NEIntMap c)
    Nothing) -> case Key -> a -> Either b c
    f Key
    k a
    v of
        Left b
    v' -> NEIntMap b -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> These a b
    This (Key -> b -> NEIntMap b
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k b
    v')
        Right c
    v' -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. b -> These a b
    That (Key -> c -> NEIntMap c
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k c
    v')
      (Just NEIntMap b
    n1, Maybe (NEIntMap c)
    Nothing) -> case Key -> a -> Either b c
    f Key
    k a
    v of
        Left b
    v' -> NEIntMap b -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> These a b
    This (Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k b
    v' IntMap b
    m1)
        Right c
    v' -> NEIntMap b -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> b -> These a b
    These NEIntMap b
    n1 (Key -> c -> NEIntMap c
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k c
    v')
      (Maybe (NEIntMap b)
    Nothing, Just NEIntMap c
    n2) -> case Key -> a -> Either b c
    f Key
    k a
    v of
        Left b
    v' -> NEIntMap b -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> b -> These a b
    These (Key -> b -> NEIntMap b
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k b
    v') NEIntMap c
    n2
        Right c
    v' -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. b -> These a b
    That (Key -> c -> IntMap c -> NEIntMap c
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k c
    v' IntMap c
    m2)
      (Just NEIntMap b
    n1, Just NEIntMap c
    n2) -> case Key -> a -> Either b c
    f Key
    k a
    v of
        Left b
    v' -> NEIntMap b -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> b -> These a b
    These (Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k b
    v' IntMap b
    m1) NEIntMap c
    n2
        Right c
    v' -> NEIntMap b -> NEIntMap c -> These (NEIntMap b) (NEIntMap c)
    forall a b. a -> b -> These a b
    These NEIntMap b
    n1 (Key -> c -> IntMap c -> NEIntMap c
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k c
    v' IntMap c
    m2)
      where
        (IntMap b
    m1, IntMap c
    m2) = (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
    forall a b c.
    (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
    M.mapEitherWithKey Key -> a -> Either b c
    f IntMap a
    m0
    {-# INLINEABLE mapEitherWithKey #-}

    -- | /O(log n)/. The expression (@'split' k map@) is potentially a 'These'
    -- containing up to two 'NEIntMap's based on splitting the map into maps
    -- containing items before and after the given key @k@.  It will never
    -- return a map that contains @k@ itself.
    --
    -- *   'Nothing' means that @k@ was the only key in the the original map,
    --     and so there are no items before or after it.
    -- *   @'Just' ('This' n1)@ means @k@ was larger than or equal to all items
    --     in the map, and @n1@ is the entire original map (minus @k@, if it was
    --     present)
    -- *   @'Just' ('That' n2)@ means @k@ was smaller than or equal to all
    --     items in the map, and @n2@ is the entire original map (minus @k@, if
    --     it was present)
    -- *   @'Just' ('These' n1 n2)@ gives @n1@ (the map of all keys from the
    --     original map less than @k@) and @n2@ (the map of all keys from the
    --     original map greater than @k@)
    --
    -- > split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (fromList ((3,"b") :| [(5,"a")]))  )
    -- > split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (singleton 5 "a")                  )
    -- > split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a"))
    -- > split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (singleton 3 "b")                  )
    -- > split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (fromList ((3,"b") :| [(5,"a")]))  )
    -- > split 5 (singleton 5 "a")                 == Nothing
    split ::
      Key ->
      NEIntMap a ->
      Maybe (These (NEIntMap a) (NEIntMap a))
    split :: forall a.
    Key -> NEIntMap a -> Maybe (These (NEIntMap a) (NEIntMap a))
    split Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v IntMap a
    m0) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> These (NEIntMap a) (NEIntMap a)
    -> Maybe (These (NEIntMap a) (NEIntMap a))
    forall a. a -> Maybe a
    Just (These (NEIntMap a) (NEIntMap a)
     -> Maybe (These (NEIntMap a) (NEIntMap a)))
    -> These (NEIntMap a) (NEIntMap a)
    -> Maybe (These (NEIntMap a) (NEIntMap a))
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That NEIntMap a
    n
      Ordering
    EQ -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That (NEIntMap a -> These (NEIntMap a) (NEIntMap a))
    -> Maybe (NEIntMap a) -> Maybe (These (NEIntMap a) (NEIntMap a))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m0
      Ordering
    GT -> These (NEIntMap a) (NEIntMap a)
    -> Maybe (These (NEIntMap a) (NEIntMap a))
    forall a. a -> Maybe a
    Just (These (NEIntMap a) (NEIntMap a)
     -> Maybe (These (NEIntMap a) (NEIntMap a)))
    -> These (NEIntMap a) (NEIntMap a)
    -> Maybe (These (NEIntMap a) (NEIntMap a))
    forall a b. (a -> b) -> a -> b
    $ case (IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m1, IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m2) of
        (Maybe (NEIntMap a)
    Nothing, Maybe (NEIntMap a)
    Nothing) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k0 a
    v)
        (Just NEIntMap a
    _, Maybe (NEIntMap a)
    Nothing) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k0 a
    v IntMap a
    m1)
        (Maybe (NEIntMap a)
    Nothing, Just NEIntMap a
    n2) -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k0 a
    v) NEIntMap a
    n2
        (Just NEIntMap a
    _, Just NEIntMap a
    n2) -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k0 a
    v IntMap a
    m1) NEIntMap a
    n2
      where
        (IntMap a
    m1, IntMap a
    m2) = Key -> IntMap a -> (IntMap a, IntMap a)
    forall a. Key -> IntMap a -> (IntMap a, IntMap a)
    M.split Key
    k IntMap a
    m0
    {-# INLINEABLE split #-}

    -- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
    -- like 'split' but also returns @'lookup' k map@, as the first field in
    -- the 'These':
    --
    -- > splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That      (That  (fromList ((3,"b") :| [(5,"a")])))
    -- > splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That  (singleton 5 "a"))
    -- > splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That      (These (singleton 3 "b") (singleton 5 "a"))
    -- > splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This  (singleton 3 "b"))
    -- > splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That      (This  (fromList ((3,"b") :| [(5,"a")])))
    -- > splitLookup 5 (singleton 5 "a")                 == This  "a"
    splitLookup ::
      Key ->
      NEIntMap a ->
      These a (These (NEIntMap a) (NEIntMap a))
    splitLookup :: forall a.
    Key -> NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a))
    splitLookup Key
    k n :: NEIntMap a
    n@(NEIntMap Key
    k0 a
    v0 IntMap a
    m0) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    k Key
    k0 of
      Ordering
    LT -> These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. b -> These a b
    That (These (NEIntMap a) (NEIntMap a)
     -> These a (These (NEIntMap a) (NEIntMap a)))
    -> (NEIntMap a -> These (NEIntMap a) (NEIntMap a))
    -> NEIntMap a
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That (NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a)))
    -> NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. (a -> b) -> a -> b
    $ NEIntMap a
    n
      Ordering
    EQ -> These a (These (NEIntMap a) (NEIntMap a))
    -> (NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a)))
    -> Maybe (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (a -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. a -> These a b
    This a
    v0) (a
    -> These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. a -> b -> These a b
    These a
    v0 (These (NEIntMap a) (NEIntMap a)
     -> These a (These (NEIntMap a) (NEIntMap a)))
    -> (NEIntMap a -> These (NEIntMap a) (NEIntMap a))
    -> NEIntMap a
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. b -> These a b
    That) (Maybe (NEIntMap a) -> These a (These (NEIntMap a) (NEIntMap a)))
    -> (IntMap a -> Maybe (NEIntMap a))
    -> IntMap a
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap (IntMap a -> These a (These (NEIntMap a) (NEIntMap a)))
    -> IntMap a -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m0
      Ordering
    GT -> (These (NEIntMap a) (NEIntMap a)
     -> These a (These (NEIntMap a) (NEIntMap a)))
    -> (a
        -> These (NEIntMap a) (NEIntMap a)
        -> These a (These (NEIntMap a) (NEIntMap a)))
    -> Maybe a
    -> These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. b -> These a b
    That a
    -> These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. a -> b -> These a b
    These Maybe a
    v (These (NEIntMap a) (NEIntMap a)
     -> These a (These (NEIntMap a) (NEIntMap a)))
    -> These (NEIntMap a) (NEIntMap a)
    -> These a (These (NEIntMap a) (NEIntMap a))
    forall a b. (a -> b) -> a -> b
    $ case (IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m1, IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap IntMap a
    m2) of
        (Maybe (NEIntMap a)
    Nothing, Maybe (NEIntMap a)
    Nothing) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k0 a
    v0)
        (Just NEIntMap a
    _, Maybe (NEIntMap a)
    Nothing) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> These a b
    This (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k0 a
    v0 IntMap a
    m1)
        (Maybe (NEIntMap a)
    Nothing, Just NEIntMap a
    n2) -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k0 a
    v0) NEIntMap a
    n2
        (Just NEIntMap a
    _, Just NEIntMap a
    n2) -> NEIntMap a -> NEIntMap a -> These (NEIntMap a) (NEIntMap a)
    forall a b. a -> b -> These a b
    These (Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k0 a
    v0 IntMap a
    m1) NEIntMap a
    n2
      where
        (IntMap a
    m1, Maybe a
    v, IntMap a
    m2) = Key -> IntMap a -> (IntMap a, Maybe a, IntMap a)
    forall a. Key -> IntMap a -> (IntMap a, Maybe a, IntMap a)
    M.splitLookup Key
    k IntMap a
    m0
    {-# INLINEABLE splitLookup #-}

    -- | /O(1)/.  Decompose a map into pieces based on the structure of the
    -- underlying tree.  This function is useful for consuming a map in
    -- parallel.
    --
    -- No guarantee is made as to the sizes of the pieces; an internal, but
    -- deterministic process determines this.  However, it is guaranteed that
    -- the pieces returned will be in ascending order (all elements in the
    -- first submap less than all elements in the second, and so on).
    --
    -- Note that the current implementation does not return more than four
    -- submaps, but you should not depend on this behaviour because it can
    -- change in the future without notice.
    splitRoot ::
      NEIntMap a ->
      NonEmpty (NEIntMap a)
    splitRoot :: forall a. NEIntMap a -> NonEmpty (NEIntMap a)
    splitRoot (NEIntMap Key
    k a
    v IntMap a
    m) =
      Key -> a -> NEIntMap a
    forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v
        NEIntMap a -> [NEIntMap a] -> NonEmpty (NEIntMap a)
    forall a. a -> [a] -> NonEmpty a
    :| (IntMap a -> Maybe (NEIntMap a)) -> [IntMap a] -> [NEIntMap a]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    Maybe.mapMaybe IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap (IntMap a -> [IntMap a]
    forall a. IntMap a -> [IntMap a]
    M.splitRoot IntMap a
    m)
    {-# INLINE splitRoot #-}

    -- | /O(m*log(n\/m + 1)), m <= n/.
    -- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@).
    isSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool
    isSubmapOf :: forall a. Eq a => NEIntMap a -> NEIntMap a -> Bool
    isSubmapOf = (a -> a -> Bool) -> NEIntMap a -> NEIntMap a -> Bool
    forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    isSubmapOfBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)
    {-# INLINE isSubmapOf #-}

    -- | /O(m*log(n\/m + 1)), m <= n/.
    -- The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if
    -- all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when
    -- applied to their respective values. For example, the following
    -- expressions are all 'True':
    --
    -- > isSubmapOfBy (==) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    -- > isSubmapOfBy (<=) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    -- > isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (fromList (('a',1) :| [('b',2)]))
    --
    -- But the following are all 'False':
    --
    -- > isSubmapOfBy (==) (singleton 'a' 2) (fromList (('a',1) :| [('b',2)]))
    -- > isSubmapOfBy (<)  (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
    -- > isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (singleton 'a' 1)
    isSubmapOfBy ::
      (a -> b -> Bool) ->
      NEIntMap a ->
      NEIntMap b ->
      Bool
    isSubmapOfBy :: forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    isSubmapOfBy a -> b -> Bool
    f (NEIntMap Key
    k a
    v IntMap a
    m0) (NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    toMap -> IntMap b
    m1) =
      Bool
    kvSub
        Bool -> Bool -> Bool
    && (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
    forall a b. (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
    M.isSubmapOfBy a -> b -> Bool
    f IntMap a
    m0 IntMap b
    m1
      where
        kvSub :: Bool
    kvSub = case Key -> IntMap b -> Maybe b
    forall a. Key -> IntMap a -> Maybe a
    M.lookup Key
    k IntMap b
    m1 of
          Just b
    v0 -> a -> b -> Bool
    f a
    v b
    v0
          Maybe b
    Nothing -> Bool
    False
    {-# INLINE isSubmapOfBy #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Is this a proper submap? (ie. a submap
    -- but not equal). Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy'
    -- (==)@).
    isProperSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool
    isProperSubmapOf :: forall a. Eq a => NEIntMap a -> NEIntMap a -> Bool
    isProperSubmapOf = (a -> a -> Bool) -> NEIntMap a -> NEIntMap a -> Bool
    forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    isProperSubmapOfBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)
    {-# INLINE isProperSubmapOf #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Is this a proper submap? (ie. a submap
    -- but not equal). The expression (@'isProperSubmapOfBy' f m1 m2@) returns
    -- 'True' when @m1@ and @m2@ are not equal, all keys in @m1@ are in @m2@,
    -- and when @f@ returns 'True' when applied to their respective values. For
    -- example, the following expressions are all 'True':
    --
    --  > isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))
    --  > isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))
    --
    -- But the following are all 'False':
    --
    --  > isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (fromList ((1,1) :| [(2,2)]))
    --  > isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (singleton 1 1))
    --  > isProperSubmapOfBy (<)  (singleton 1 1)               (fromList ((1,1) :| [(2,2)]))
    isProperSubmapOfBy ::
      (a -> b -> Bool) ->
      NEIntMap a ->
      NEIntMap b ->
      Bool
    isProperSubmapOfBy :: forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    isProperSubmapOfBy a -> b -> Bool
    f NEIntMap a
    m1 NEIntMap b
    m2 =
      IntMap a -> Key
    forall a. IntMap a -> Key
    M.size (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    neimIntMap NEIntMap a
    m1) Key -> Key -> Bool
    forall a. Ord a => a -> a -> Bool
    < IntMap b -> Key
    forall a. IntMap a -> Key
    M.size (NEIntMap b -> IntMap b
    forall a. NEIntMap a -> IntMap a
    neimIntMap NEIntMap b
    m2)
        Bool -> Bool -> Bool
    && (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    isSubmapOfBy a -> b -> Bool
    f NEIntMap a
    m1 NEIntMap b
    m2
    {-# INLINE isProperSubmapOfBy #-}

    -- | /O(1)/. The minimal key of the map.  Note that this is total, making
    -- 'Data.IntMap.lookupMin' obsolete.  It is constant-time, so has better
    -- asymptotics than @Data.IntMap.lookupMin@ and @Data.IntMap.findMin@, as well.
    --
    -- > findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b")
    findMin :: NEIntMap a -> (Key, a)
    findMin :: forall a. NEIntMap a -> (Key, a)
    findMin (NEIntMap Key
    k a
    v IntMap a
    _) = (Key
    k, a
    v)
    {-# INLINE findMin #-}

    -- | /O(log n)/. The maximal key of the map.  Note that this is total, making
    -- 'Data.IntMap.lookupMin' obsolete.
    --
    -- > findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")
    findMax :: NEIntMap a -> (Key, a)
    findMax :: forall a. NEIntMap a -> (Key, a)
    findMax (NEIntMap Key
    k a
    v IntMap a
    m) = (Key, a) -> Maybe (Key, a) -> (Key, a)
    forall a. a -> Maybe a -> a
    fromMaybe (Key
    k, a
    v) (Maybe (Key, a) -> (Key, a))
    -> (IntMap a -> Maybe (Key, a)) -> IntMap a -> (Key, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> Maybe (Key, a)
    forall a. IntMap a -> Maybe (Key, a)
    M.lookupMax (IntMap a -> (Key, a)) -> IntMap a -> (Key, a)
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE findMax #-}

    -- | /O(1)/. Delete the minimal key. Returns a potentially empty map
    -- ('IntMap'), because we might end up deleting the final key in a singleton
    -- map.  It is constant-time, so has better asymptotics than
    -- 'Data.IntMap.deleteMin'.
    --
    -- > deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(5,"a"), (7,"c")]
    -- > deleteMin (singleton 5 "a") == Data.IntMap.empty
    deleteMin :: NEIntMap a -> IntMap a
    deleteMin :: forall a. NEIntMap a -> IntMap a
    deleteMin (NEIntMap Key
    _ a
    _ IntMap a
    m) = IntMap a
    m
    {-# INLINE deleteMin #-}

    -- | /O(log n)/. Delete the maximal key. Returns a potentially empty map
    -- ('IntMap'), because we might end up deleting the final key in a singleton
    -- map.
    --
    -- > deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(3,"b"), (5,"a")]
    -- > deleteMax (singleton 5 "a") == Data.IntMap.empty
    deleteMax :: NEIntMap a -> IntMap a
    deleteMax :: forall a. NEIntMap a -> IntMap a
    deleteMax (NEIntMap Key
    k a
    v IntMap a
    m) = case IntMap a -> Maybe (a, IntMap a)
    forall a. IntMap a -> Maybe (a, IntMap a)
    M.maxView IntMap a
    m of
      Maybe (a, IntMap a)
    Nothing -> IntMap a
    forall a. IntMap a
    M.empty
      Just (a
    _, IntMap a
    m') -> Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v IntMap a
    m'
    {-# INLINE deleteMax #-}

    -- | /O(1)/ if delete, /O(log n)/ otherwise. Update the value at the
    -- minimal key.  Returns a potentially empty map ('IntMap'), because we might
    -- end up deleting the final key in the map if the function returns
    -- 'Nothing'.  See 'adjustMin' for a version that can guaruntee that we
    -- return a non-empty map.
    --
    -- > updateMin (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "Xb"), (5, "a")]
    -- > updateMin (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    updateMin :: (a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMin :: forall a. (a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMin a -> Maybe a
    f = (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMinWithKey ((a -> Maybe a) -> Key -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE updateMin #-}

    -- | /O(1)/. A version of 'updateMin' that disallows deletion, allowing us
    -- to guarantee that the result is also non-empty.
    adjustMin :: (a -> a) -> NEIntMap a -> NEIntMap a
    adjustMin :: forall a. (a -> a) -> NEIntMap a -> NEIntMap a
    adjustMin a -> a
    f = (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    forall a. (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMinWithKey ((a -> a) -> Key -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjustMin #-}

    -- | /O(1)/ if delete, /O(log n)/ otherwise. Update the value at the
    -- minimal key.  Returns a potentially empty map ('IntMap'), because we might
    -- end up deleting the final key in the map if the function returns
    -- 'Nothing'.  See 'adjustMinWithKey' for a version that guaruntees
    -- a non-empty map.
    --
    -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
    -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    updateMinWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMinWithKey :: forall a. (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMinWithKey Key -> a -> Maybe a
    f (NEIntMap Key
    k a
    v IntMap a
    m) = (IntMap a -> IntMap a)
    -> (a -> IntMap a -> IntMap a) -> Maybe a -> IntMap a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a -> IntMap a
    forall a. a -> a
    id (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k) (Key -> a -> Maybe a
    f Key
    k a
    v) IntMap a
    m
    {-# INLINE updateMinWithKey #-}

    -- | /O(1)/. A version of 'adjustMaxWithKey' that disallows deletion,
    -- allowing us to guarantee that the result is also non-empty.  Note that
    -- it also is able to have better asymptotics than 'updateMinWithKey' in
    -- general.
    adjustMinWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMinWithKey :: forall a. (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMinWithKey Key -> a -> a
    f (NEIntMap Key
    k a
    v IntMap a
    m) = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k (Key -> a -> a
    f Key
    k a
    v) IntMap a
    m
    {-# INLINE adjustMinWithKey #-}

    -- | /O(log n)/. Update the value at the maximal key.  Returns
    -- a potentially empty map ('IntMap'), because we might end up deleting the
    -- final key in the map if the function returns 'Nothing'.  See 'adjustMax'
    -- for a version that can guarantee that we return a non-empty map.
    --
    -- > updateMax (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "Xa")]
    -- > updateMax (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
    updateMax :: (a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMax :: forall a. (a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMax a -> Maybe a
    f = (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMaxWithKey ((a -> Maybe a) -> Key -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE updateMax #-}

    -- | /O(log n)/. A version of 'updateMax' that disallows deletion, allowing
    -- us to guarantee that the result is also non-empty.
    adjustMax :: (a -> a) -> NEIntMap a -> NEIntMap a
    adjustMax :: forall a. (a -> a) -> NEIntMap a -> NEIntMap a
    adjustMax a -> a
    f = (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    forall a. (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMaxWithKey ((a -> a) -> Key -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjustMax #-}

    -- | /O(log n)/. Update the value at the maximal key.  Returns
    -- a potentially empty map ('IntMap'), because we might end up deleting the
    -- final key in the map if the function returns 'Nothing'. See
    -- 'adjustMaxWithKey' for a version that guaruntees a non-empty map.
    --
    -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
    -- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"
    updateMaxWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMaxWithKey :: forall a. (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a
    updateMaxWithKey Key -> a -> Maybe a
    f (NEIntMap Key
    k a
    v IntMap a
    m)
      | IntMap a -> Bool
    forall a. IntMap a -> Bool
    M.null IntMap a
    m = IntMap a -> (a -> IntMap a) -> Maybe a -> IntMap a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe IntMap a
    m (Key -> a -> IntMap a
    forall a. Key -> a -> IntMap a
    M.singleton Key
    k) (Maybe a -> IntMap a) -> Maybe a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ Key -> a -> Maybe a
    f Key
    k a
    v
      | Bool
    otherwise =
          Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v
            (IntMap a -> IntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> Maybe a) -> IntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> IntMap a -> IntMap a
    M.updateMaxWithKey Key -> a -> Maybe a
    f
            (IntMap a -> IntMap a) -> IntMap a -> IntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE updateMaxWithKey #-}

    -- | /O(log n)/. A version of 'updateMaxWithKey' that disallows deletion,
    -- allowing us to guarantee that the result is also non-empty.
    adjustMaxWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMaxWithKey :: forall a. (Key -> a -> a) -> NEIntMap a -> NEIntMap a
    adjustMaxWithKey Key -> a -> a
    f (NEIntMap Key
    k0 a
    v IntMap a
    m)
      | IntMap a -> Bool
    forall a. IntMap a -> Bool
    M.null IntMap a
    m = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 (Key -> a -> a
    f Key
    k0 a
    v) IntMap a
    m
      | Bool
    otherwise =
          Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    insertMapMin Key
    k0 a
    v
            (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> Maybe a) -> IntMap a -> IntMap a
    forall a. (Key -> a -> Maybe a) -> IntMap a -> IntMap a
    M.updateMaxWithKey (\Key
    k -> a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> (a -> a) -> a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> a -> a
    f Key
    k)
            (IntMap a -> NEIntMap a) -> IntMap a -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE adjustMaxWithKey #-}

    -- | /O(1)/. Retrieves the value associated with minimal key of the
    -- map, and the map stripped of that element.  It is constant-time, so has
    -- better asymptotics than @Data.IntMap.minView@ for 'IntMap'.
    --
    -- Note that unlike @Data.IntMap.minView@ for 'IntMap', this cannot ever fail,
    -- so doesn't need to return in a 'Maybe'.  However, the result 'IntMap' is
    -- potentially empty, since the original map might have contained just
    -- a single item.
    --
    -- > minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.IntMap.singleton 5 "a")
    minView :: NEIntMap a -> (a, IntMap a)
    minView :: forall a. NEIntMap a -> (a, IntMap a)
    minView = ((Key, a) -> a) -> ((Key, a), IntMap a) -> (a, IntMap a)
    forall a b c. (a -> b) -> (a, c) -> (b, c)
    forall (p :: * -> * -> *) a b c.
    Bifunctor p =>
    (a -> b) -> p a c -> p b c
    first (Key, a) -> a
    forall a b. (a, b) -> b
    snd (((Key, a), IntMap a) -> (a, IntMap a))
    -> (NEIntMap a -> ((Key, a), IntMap a))
    -> NEIntMap a
    -> (a, IntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> ((Key, a), IntMap a)
    forall a. NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMin
    {-# INLINE minView #-}

    -- | /O(1)/. Delete and find the minimal key-value pair.  It is
    -- constant-time, so has better asymptotics that @Data.IntMap.minView@ for
    -- 'IntMap'.
    --
    -- Note that unlike @Data.IntMap.deleteFindMin@ for 'IntMap', this cannot ever
    -- fail, and so is a total function. However, the result 'IntMap' is
    -- potentially empty, since the original map might have contained just
    -- a single item.
    --
    -- > deleteFindMin (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((3,"b"), Data.IntMap.fromList [(5,"a"), (10,"c")])
    deleteFindMin :: NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMin :: forall a. NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMin (NEIntMap Key
    k a
    v IntMap a
    m) = ((Key
    k, a
    v), IntMap a
    m)
    {-# INLINE deleteFindMin #-}

    -- | /O(log n)/. Retrieves the value associated with maximal key of the
    -- map, and the map stripped of that element.
    --
    -- Note that unlike @Data.IntMap.maxView@ from 'IntMap', this cannot ever fail,
    -- so doesn't need to return in a 'Maybe'.  However, the result 'IntMap' is
    -- potentially empty, since the original map might have contained just
    -- a single item.
    --
    -- > maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.IntMap.singleton 3 "b")
    maxView :: NEIntMap a -> (a, IntMap a)
    maxView :: forall a. NEIntMap a -> (a, IntMap a)
    maxView = ((Key, a) -> a) -> ((Key, a), IntMap a) -> (a, IntMap a)
    forall a b c. (a -> b) -> (a, c) -> (b, c)
    forall (p :: * -> * -> *) a b c.
    Bifunctor p =>
    (a -> b) -> p a c -> p b c
    first (Key, a) -> a
    forall a b. (a, b) -> b
    snd (((Key, a), IntMap a) -> (a, IntMap a))
    -> (NEIntMap a -> ((Key, a), IntMap a))
    -> NEIntMap a
    -> (a, IntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> ((Key, a), IntMap a)
    forall a. NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMax
    {-# INLINE maxView #-}

    -- | /O(log n)/. Delete and find the minimal key-value pair.
    --
    -- Note that unlike @Data.IntMap.deleteFindMax@ for 'IntMap', this cannot ever
    -- fail, and so is a total function. However, the result 'IntMap' is
    -- potentially empty, since the original map might have contained just
    -- a single item.
    --
    -- > deleteFindMax (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((10,"c"), Data.IntMap.fromList [(3,"b"), (5,"a")])
    deleteFindMax :: NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMax :: forall a. NEIntMap a -> ((Key, a), IntMap a)
    deleteFindMax (NEIntMap Key
    k a
    v IntMap a
    m) =
      ((Key, a), IntMap a)
    -> (((Key, a), IntMap a) -> ((Key, a), IntMap a))
    -> Maybe ((Key, a), IntMap a)
    -> ((Key, a), IntMap a)
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe ((Key
    k, a
    v), IntMap a
    forall a. IntMap a
    M.empty) ((IntMap a -> IntMap a)
    -> ((Key, a), IntMap a) -> ((Key, a), IntMap a)
    forall b c a. (b -> c) -> (a, b) -> (a, c)
    forall (p :: * -> * -> *) b c a.
    Bifunctor p =>
    (b -> c) -> p a b -> p a c
    second (Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap Key
    k a
    v))
        (Maybe ((Key, a), IntMap a) -> ((Key, a), IntMap a))
    -> (IntMap a -> Maybe ((Key, a), IntMap a))
    -> IntMap a
    -> ((Key, a), IntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> Maybe ((Key, a), IntMap a)
    forall a. IntMap a -> Maybe ((Key, a), IntMap a)
    M.maxViewWithKey
        (IntMap a -> ((Key, a), IntMap a))
    -> IntMap a -> ((Key, a), IntMap a)
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE deleteFindMax #-}

    -- ---------------------------
    -- Combining functions
    -- ---------------------------
    --
    -- Code comes from "Data.Map.Internal" from containers, modified slightly
    -- to work with NonEmpty
    --
    -- Copyright   :  (c) Daan Leijen 2002
    --                (c) Andriy Palamarchuk 2008

    combineEq :: NonEmpty (Key, b) -> NonEmpty (Key, b)
    combineEq :: forall b. NonEmpty (Key, b) -> NonEmpty (Key, b)
    combineEq = \case
      (Key, b)
    x :| [] -> (Key, b)
    x (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
      (Key, b)
    x :| xx :: [(Key, b)]
    xx@((Key, b)
    _ : [(Key, b)]
    _) -> (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    forall {a} {b}. Eq a => (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (Key, b)
    x [(Key, b)]
    xx
      where
        go :: (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    z [] = (a, b)
    z (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
        go z :: (a, b)
    z@(a
    kz, b
    _) (x :: (a, b)
    x@(a
    kx, b
    xx) : [(a, b)]
    xs')
          | a
    kx a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    kz = (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a
    kx, b
    xx) [(a, b)]
    xs'
          | Bool
    otherwise = (a, b)
    z (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    x [(a, b)]
    xs'

    combineEqWith ::
      (Key -> b -> b -> b) ->
      NonEmpty (Key, b) ->
      NonEmpty (Key, b)
    combineEqWith :: forall b.
    (Key -> b -> b -> b) -> NonEmpty (Key, b) -> NonEmpty (Key, b)
    combineEqWith Key -> b -> b -> b
    f = \case
      (Key, b)
    x :| [] -> (Key, b)
    x (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
      (Key, b)
    x :| xx :: [(Key, b)]
    xx@((Key, b)
    _ : [(Key, b)]
    _) -> (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    go (Key, b)
    x [(Key, b)]
    xx
      where
        go :: (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    go (Key, b)
    z [] = (Key, b)
    z (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
        go z :: (Key, b)
    z@(Key
    kz, b
    zz) (x :: (Key, b)
    x@(Key
    kx, b
    xx) : [(Key, b)]
    xs')
          | Key
    kx Key -> Key -> Bool
    forall a. Eq a => a -> a -> Bool
    == Key
    kz = let yy :: b
    yy = Key -> b -> b -> b
    f Key
    kx b
    xx b
    zz in (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    go (Key
    kx, b
    yy) [(Key, b)]
    xs'
          | Bool
    otherwise = (Key, b)
    z (Key, b) -> NonEmpty (Key, b) -> NonEmpty (Key, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| (Key, b) -> [(Key, b)] -> NonEmpty (Key, b)
    go (Key, b)
    x [(Key, b)]
    xs'