    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE CPP #-}
    {-# LANGUAGE DeriveDataTypeable #-}
    {-# LANGUAGE ViewPatterns #-}
    {-# OPTIONS_HADDOCK not-home #-}

    -- |
    -- Module      : Data.IntMap.NonEmpty.Internal
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- Unsafe internal-use functions used in the implementation of
    -- "Data.IntMap.NonEmpty".  These functions can potentially be used to
    -- break the abstraction of 'NEIntMap' and produce unsound maps, so be
    -- wary!
    module Data.IntMap.NonEmpty.Internal (
      -- * Non-Empty IntMap type
      NEIntMap (..),
      Key,
      singleton,
      nonEmptyMap,
      withNonEmpty,
      fromList,
      toList,
      map,
      insertWith,
      union,
      unions,
      elems,
      size,
      toMap,

      -- * Folds
      foldr,
      foldr',
      foldr1,
      foldl,
      foldl',
      foldl1,

      -- * Traversals
      traverseWithKey,
      traverseWithKey1,
      foldMapWithKey,

      -- * Unsafe IntMap Functions
      insertMinMap,
      insertMaxMap,

      -- * Debug
      valid,
    ) where

    import Control.Applicative
    import Control.Comonad
    import Control.DeepSeq
    import Control.Monad
    import qualified Data.Aeson as A
    import Data.Coerce
    import Data.Data
    import qualified Data.Foldable as F
    import Data.Function
    import Data.Functor.Alt
    import Data.Functor.Classes
    import Data.Functor.Invariant
    import qualified Data.IntMap as M
    import Data.IntMap.Internal (IntMap (..), Key)
    import qualified Data.List as L
    import Data.List.NonEmpty (NonEmpty (..))
    import Data.Maybe
    import Data.Semigroup
    import Data.Semigroup.Foldable (Foldable1 (fold1))
    import qualified Data.Semigroup.Foldable as F1
    import Data.Semigroup.Traversable (Traversable1 (..))
    import Text.Read
    import Prelude hiding (Foldable (..), map)

    -- | A non-empty (by construction) map from integer keys to values @a@.  At
    -- least one key-value pair exists in an @'NEIntMap' v@ at all times.
    --
    -- Functions that /take/ an 'NEIntMap' can safely operate on it with the
    -- assumption that it has at least one key-value pair.
    --
    -- Functions that /return/ an 'NEIntMap' provide an assurance that the result
    -- has at least one key-value pair.
    --
    -- "Data.IntMap.NonEmpty" re-exports the API of "Data.IntMap", faithfully
    -- reproducing asymptotics, typeclass constraints, and semantics.
    -- Functions that ensure that input and output maps are both non-empty
    -- (like 'Data.IntMap.NonEmpty.insert') return 'NEIntMap', but functions that
    -- might potentially return an empty map (like 'Data.IntMap.NonEmpty.delete')
    -- return a 'IntMap' instead.
    --
    -- You can directly construct an 'NEIntMap' with the API from
    -- "Data.IntMap.NonEmpty"; it's more or less the same as constructing a normal
    -- 'IntMap', except you don't have access to 'Data.IntMap.empty'.  There are also
    -- a few ways to construct an 'NEIntMap' from a 'IntMap':
    --
    -- 1.  The 'nonEmptyMap' smart constructor will convert a @'IntMap' k a@ into
    --     a @'Maybe' ('NEIntMap' k a)@, returning 'Nothing' if the original 'IntMap'
    --     was empty.
    -- 2.  You can use the 'Data.IntMap.NonEmpty.insertIntMap' family of functions to
    --     insert a value into a 'IntMap' to create a guaranteed 'NEIntMap'.
    -- 3.  You can use the 'Data.IntMap.NonEmpty.IsNonEmpty' and
    --     'Data.IntMap.NonEmpty.IsEmpty' patterns to "pattern match" on a 'IntMap'
    --     to reveal it as either containing a 'NEIntMap' or an empty map.
    -- 4.  'withNonEmpty' offers a continuation-based interface for
    --     deconstructing a 'IntMap' and treating it as if it were an
    --     'NEIntMap'.
    --
    -- You can convert an 'NEIntMap' into a 'IntMap' with 'toMap' or
    -- 'Data.IntMap.NonEmpty.IsNonEmpty', essentially "obscuring" the non-empty
    -- property from the type.
    data NEIntMap a
      = NEIntMap
      { forall a. NEIntMap a -> Key
    neimK0 :: !Key
      -- ^ invariant: must be smaller than smallest key in map
      , forall a. NEIntMap a -> a
    neimV0 :: a
      , forall a. NEIntMap a -> IntMap a
    neimIntMap :: !(IntMap a)
      }
      deriving (Typeable)

    instance Eq a => Eq (NEIntMap a) where
      NEIntMap a
    t1 == :: NEIntMap a -> NEIntMap a -> Bool
    == NEIntMap a
    t2 =
        IntMap a -> Key
    forall a. IntMap a -> Key
    M.size (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    neimIntMap NEIntMap a
    t1) Key -> Key -> Bool
    forall a. Eq a => a -> a -> Bool
    == IntMap a -> Key
    forall a. IntMap a -> Key
    M.size (NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    neimIntMap NEIntMap a
    t2)
          Bool -> Bool -> Bool
    && NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    t1 NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool
    forall a. Eq a => a -> a -> Bool
    == NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    t2

    instance Ord a => Ord (NEIntMap a) where
      compare :: NEIntMap a -> NEIntMap a -> Ordering
    compare = NonEmpty (Key, a) -> NonEmpty (Key, a) -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (NonEmpty (Key, a) -> NonEmpty (Key, a) -> Ordering)
    -> (NEIntMap a -> NonEmpty (Key, a))
    -> NEIntMap a
    -> NEIntMap a
    -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
      < :: NEIntMap a -> NEIntMap a -> Bool
    (<) = NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool
    forall a. Ord a => a -> a -> Bool
    (<) (NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool)
    -> (NEIntMap a -> NonEmpty (Key, a))
    -> NEIntMap a
    -> NEIntMap a
    -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
      > :: NEIntMap a -> NEIntMap a -> Bool
    (>) = NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool
    forall a. Ord a => a -> a -> Bool
    (>) (NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool)
    -> (NEIntMap a -> NonEmpty (Key, a))
    -> NEIntMap a
    -> NEIntMap a
    -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
      <= :: NEIntMap a -> NEIntMap a -> Bool
    (<=) = NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool
    forall a. Ord a => a -> a -> Bool
    (<=) (NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool)
    -> (NEIntMap a -> NonEmpty (Key, a))
    -> NEIntMap a
    -> NEIntMap a
    -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
      >= :: NEIntMap a -> NEIntMap a -> Bool
    (>=) = NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool
    forall a. Ord a => a -> a -> Bool
    (>=) (NonEmpty (Key, a) -> NonEmpty (Key, a) -> Bool)
    -> (NEIntMap a -> NonEmpty (Key, a))
    -> NEIntMap a
    -> NEIntMap a
    -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList

    instance Eq1 NEIntMap where
      liftEq :: forall a b. (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
    liftEq a -> b -> Bool
    eq 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. Eq 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
    && ((Key, a) -> (Key, b) -> Bool)
    -> NonEmpty (Key, a) -> NonEmpty (Key, b) -> Bool
    forall a b. (a -> b -> Bool) -> NonEmpty a -> NonEmpty b -> Bool
    forall (f :: * -> *) a b.
    Eq1 f =>
    (a -> b -> Bool) -> f a -> f b -> Bool
    liftEq ((a -> b -> Bool) -> (Key, a) -> (Key, b) -> Bool
    forall a b. (a -> b -> Bool) -> (Key, a) -> (Key, b) -> Bool
    forall (f :: * -> *) a b.
    Eq1 f =>
    (a -> b -> Bool) -> f a -> f b -> Bool
    liftEq a -> b -> Bool
    eq) (NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    m1) (NEIntMap b -> NonEmpty (Key, b)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap b
    m2)

    instance Ord1 NEIntMap where
      liftCompare :: forall a b.
    (a -> b -> Ordering) -> NEIntMap a -> NEIntMap b -> Ordering
    liftCompare a -> b -> Ordering
    cmp NEIntMap a
    m NEIntMap b
    n =
        ((Key, a) -> (Key, b) -> Ordering)
    -> NonEmpty (Key, a) -> NonEmpty (Key, b) -> Ordering
    forall a b.
    (a -> b -> Ordering) -> NonEmpty a -> NonEmpty b -> Ordering
    forall (f :: * -> *) a b.
    Ord1 f =>
    (a -> b -> Ordering) -> f a -> f b -> Ordering
    liftCompare ((a -> b -> Ordering) -> (Key, a) -> (Key, b) -> Ordering
    forall a b.
    (a -> b -> Ordering) -> (Key, a) -> (Key, b) -> Ordering
    forall (f :: * -> *) a b.
    Ord1 f =>
    (a -> b -> Ordering) -> f a -> f b -> Ordering
    liftCompare a -> b -> Ordering
    cmp) (NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    m) (NEIntMap b -> NonEmpty (Key, b)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap b
    n)

    instance Show1 NEIntMap where
      liftShowsPrec :: forall a.
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> NEIntMap a -> ShowS
    liftShowsPrec Key -> a -> ShowS
    sp [a] -> ShowS
    sl Key
    d NEIntMap a
    m =
        (Key -> NonEmpty (Key, a) -> ShowS)
    -> String -> Key -> NonEmpty (Key, a) -> ShowS
    forall a. (Key -> a -> ShowS) -> String -> Key -> a -> ShowS
    showsUnaryWith ((Key -> (Key, a) -> ShowS)
    -> ([(Key, a)] -> ShowS) -> Key -> NonEmpty (Key, a) -> ShowS
    forall a.
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> NonEmpty a -> ShowS
    forall (f :: * -> *) a.
    Show1 f =>
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> f a -> ShowS
    liftShowsPrec Key -> (Key, a) -> ShowS
    sp' [(Key, a)] -> ShowS
    sl') String
    "fromList" Key
    d (NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    m)
        where
          sp' :: Key -> (Key, a) -> ShowS
    sp' = (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> (Key, a) -> ShowS
    forall a.
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> (Key, a) -> ShowS
    forall (f :: * -> *) a.
    Show1 f =>
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> Key -> f a -> ShowS
    liftShowsPrec Key -> a -> ShowS
    sp [a] -> ShowS
    sl
          sl' :: [(Key, a)] -> ShowS
    sl' = (Key -> a -> ShowS) -> ([a] -> ShowS) -> [(Key, a)] -> ShowS
    forall a.
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> [(Key, a)] -> ShowS
    forall (f :: * -> *) a.
    Show1 f =>
    (Key -> a -> ShowS) -> ([a] -> ShowS) -> [f a] -> ShowS
    liftShowList Key -> a -> ShowS
    sp [a] -> ShowS
    sl

    instance Read1 NEIntMap where
      liftReadsPrec :: forall a.
    (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (NEIntMap a)
    liftReadsPrec Key -> ReadS a
    rp ReadS [a]
    rl =
        (String -> ReadS (NEIntMap a)) -> Key -> ReadS (NEIntMap a)
    forall a. (String -> ReadS a) -> Key -> ReadS a
    readsData ((String -> ReadS (NEIntMap a)) -> Key -> ReadS (NEIntMap a))
    -> (String -> ReadS (NEIntMap a)) -> Key -> ReadS (NEIntMap a)
    forall a b. (a -> b) -> a -> b
    $
          (Key -> ReadS (NonEmpty (Key, a)))
    -> String
    -> (NonEmpty (Key, a) -> NEIntMap a)
    -> String
    -> ReadS (NEIntMap a)
    forall a t.
    (Key -> ReadS a) -> String -> (a -> t) -> String -> ReadS t
    readsUnaryWith ((Key -> ReadS (Key, a))
    -> ReadS [(Key, a)] -> Key -> ReadS (NonEmpty (Key, a))
    forall a.
    (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (NonEmpty a)
    forall (f :: * -> *) a.
    Read1 f =>
    (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (f a)
    liftReadsPrec Key -> ReadS (Key, a)
    rp' ReadS [(Key, a)]
    rl') String
    "fromList" NonEmpty (Key, a) -> NEIntMap a
    forall a. NonEmpty (Key, a) -> NEIntMap a
    fromList
        where
          rp' :: Key -> ReadS (Key, a)
    rp' = (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (Key, a)
    forall a. (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (Key, a)
    forall (f :: * -> *) a.
    Read1 f =>
    (Key -> ReadS a) -> ReadS [a] -> Key -> ReadS (f a)
    liftReadsPrec Key -> ReadS a
    rp ReadS [a]
    rl
          rl' :: ReadS [(Key, a)]
    rl' = (Key -> ReadS a) -> ReadS [a] -> ReadS [(Key, a)]
    forall a. (Key -> ReadS a) -> ReadS [a] -> ReadS [(Key, a)]
    forall (f :: * -> *) a.
    Read1 f =>
    (Key -> ReadS a) -> ReadS [a] -> ReadS [f a]
    liftReadList Key -> ReadS a
    rp ReadS [a]
    rl

    instance Read e => Read (NEIntMap e) where
      readPrec :: ReadPrec (NEIntMap e)
    readPrec = ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e)
    forall a. ReadPrec a -> ReadPrec a
    parens (ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e))
    -> ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e)
    forall a b. (a -> b) -> a -> b
    $ Key -> ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e)
    forall a. Key -> ReadPrec a -> ReadPrec a
    prec Key
    10 (ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e))
    -> ReadPrec (NEIntMap e) -> ReadPrec (NEIntMap e)
    forall a b. (a -> b) -> a -> b
    $ do
        Ident "fromList" <- ReadPrec Lexeme
    lexP
        xs <- parens . prec 10 $ readPrec
        return (fromList xs)
      readListPrec :: ReadPrec [NEIntMap e]
    readListPrec = ReadPrec [NEIntMap e]
    forall a. Read a => ReadPrec [a]
    readListPrecDefault

    instance Show a => Show (NEIntMap a) where
      showsPrec :: Key -> NEIntMap a -> ShowS
    showsPrec Key
    d NEIntMap a
    m =
        Bool -> ShowS -> ShowS
    showParen (Key
    d Key -> Key -> Bool
    forall a. Ord a => a -> a -> Bool
    > Key
    10) (ShowS -> ShowS) -> ShowS -> ShowS
    forall a b. (a -> b) -> a -> b
    $
          String -> ShowS
    showString String
    "fromList (" ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty (Key, a) -> ShowS
    forall a. Show a => a -> ShowS
    shows (NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    m) ShowS -> ShowS -> ShowS
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . String -> ShowS
    showString String
    ")"

    instance NFData a => NFData (NEIntMap a) where
      rnf :: NEIntMap a -> ()
    rnf (NEIntMap Key
    k a
    v IntMap a
    a) = Key -> ()
    forall a. NFData a => a -> ()
    rnf Key
    k () -> () -> ()
    forall a b. a -> b -> b
    `seq` a -> ()
    forall a. NFData a => a -> ()
    rnf a
    v () -> () -> ()
    forall a b. a -> b -> b
    `seq` IntMap a -> ()
    forall a. NFData a => a -> ()
    rnf IntMap a
    a

    -- Data instance code from Data.IntMap.Internal
    --
    -- Copyright   :  (c) Daan Leijen 2002
    --                (c) Andriy Palamarchuk 2008
    --                (c) wren romano 2016
    #if MIN_VERSION_base(4,16,0)
    instance Data a => Data (NEIntMap a) where
      gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> NEIntMap a -> c (NEIntMap a)
    gfoldl forall d b. Data d => c (d -> b) -> d -> c b
    f forall g. g -> c g
    z NEIntMap a
    im = (NonEmpty (Key, a) -> NEIntMap a)
    -> c (NonEmpty (Key, a) -> NEIntMap a)
    forall g. g -> c g
    z NonEmpty (Key, a) -> NEIntMap a
    forall a. NonEmpty (Key, a) -> NEIntMap a
    fromList c (NonEmpty (Key, a) -> NEIntMap a)
    -> NonEmpty (Key, a) -> c (NEIntMap a)
    forall d b. Data d => c (d -> b) -> d -> c b
    `f` NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList NEIntMap a
    im
      toConstr :: NEIntMap a -> Constr
    toConstr NEIntMap a
    _ = Constr
    fromListConstr
      gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (NEIntMap a)
    gunfold forall b r. Data b => c (b -> r) -> c r
    k forall r. r -> c r
    z Constr
    c = case Constr -> Key
    constrIndex Constr
    c of
        Key
    1 -> c (NonEmpty (Key, a) -> NEIntMap a) -> c (NEIntMap a)
    forall b r. Data b => c (b -> r) -> c r
    k ((NonEmpty (Key, a) -> NEIntMap a)
    -> c (NonEmpty (Key, a) -> NEIntMap a)
    forall r. r -> c r
    z NonEmpty (Key, a) -> NEIntMap a
    forall a. NonEmpty (Key, a) -> NEIntMap a
    fromList)
        Key
    _ -> String -> c (NEIntMap a)
    forall a. HasCallStack => String -> a
    error String
    "gunfold"
      dataTypeOf :: NEIntMap a -> DataType
    dataTypeOf NEIntMap a
    _ = DataType
    intMapDataType
      dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (NEIntMap a))
    dataCast1 = c (t a) -> Maybe (c (NEIntMap a))
    (forall d. Data d => c (t d)) -> Maybe (c (NEIntMap a))
    forall {k1} {k2} (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
           (a :: k2).
    (Typeable t, Typeable t') =>
    c (t a) -> Maybe (c (t' a))
    gcast1
    #else
    #ifndef __HLINT__
    instance Data a => Data (NEIntMap a) where
      gfoldl f z im = z fromList `f` toList im
      toConstr _ = fromListConstr
      gunfold k z c = case constrIndex c of
        1 -> k (z fromList)
        _ -> error "gunfold"
      dataTypeOf _ = intMapDataType
      dataCast1 f = gcast1 f
    #endif
    #endif

    fromListConstr :: Constr
    fromListConstr :: Constr
    fromListConstr = DataType -> String -> [String] -> Fixity -> Constr
    mkConstr DataType
    intMapDataType String
    "fromList" [] Fixity
    Prefix

    intMapDataType :: DataType
    intMapDataType :: DataType
    intMapDataType = String -> [Constr] -> DataType
    mkDataType String
    "Data.IntMap.NonEmpty.Internal.NEIntMap" [Constr
    fromListConstr]

    instance A.ToJSON a => A.ToJSON (NEIntMap a) where
      toJSON :: NEIntMap a -> Value
    toJSON = IntMap a -> Value
    forall a. ToJSON a => a -> Value
    A.toJSON (IntMap a -> Value)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> Value
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap
      toEncoding :: NEIntMap a -> Encoding
    toEncoding = IntMap a -> Encoding
    forall a. ToJSON a => a -> Encoding
    A.toEncoding (IntMap a -> Encoding)
    -> (NEIntMap a -> IntMap a) -> NEIntMap a -> Encoding
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> IntMap a
    forall a. NEIntMap a -> IntMap a
    toMap

    instance A.FromJSON a => A.FromJSON (NEIntMap a) where
      parseJSON :: Value -> Parser (NEIntMap a)
    parseJSON =
        Parser (NEIntMap a)
    -> (NEIntMap a -> Parser (NEIntMap a))
    -> IntMap a
    -> Parser (NEIntMap a)
    forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty (String -> Parser (NEIntMap a)
    forall a. String -> Parser a
    forall (m :: * -> *) a. MonadFail m => String -> m a
    fail String
    err) NEIntMap a -> Parser (NEIntMap a)
    forall a. a -> Parser a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
          (IntMap a -> Parser (NEIntMap a))
    -> (Value -> Parser (IntMap a)) -> Value -> Parser (NEIntMap a)
    forall (m :: * -> *) b c a.
    Monad m =>
    (b -> m c) -> (a -> m b) -> a -> m c
    <=< Value -> Parser (IntMap a)
    forall a. FromJSON a => Value -> Parser a
    A.parseJSON
        where
          err :: String
    err = String
    "NEIntMap: Non-empty map expected, but empty map found"

    -- | @since 0.3.4.4
    instance Alt NEIntMap where
      <!> :: forall a. NEIntMap a -> NEIntMap a -> NEIntMap a
    (<!>) = NEIntMap a -> NEIntMap a -> NEIntMap a
    forall a. NEIntMap a -> NEIntMap a -> NEIntMap a
    union

    -- | /O(n)/. Fold the values in the map using the given right-associative
    -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'elems'@.
    --
    -- > elemsList map = foldr (:) [] map
    --
    -- > let f a len = len + (length a)
    -- > foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4
    foldr :: (a -> b -> b) -> b -> NEIntMap a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> NEIntMap a -> b
    foldr a -> b -> b
    f b
    z (NEIntMap Key
    _ a
    v IntMap a
    m) = a
    v a -> b -> b
    `f` (a -> b -> b) -> b -> IntMap a -> b
    forall a b. (a -> b -> b) -> b -> IntMap a -> b
    M.foldr a -> b -> b
    f b
    z IntMap a
    m
    {-# INLINE foldr #-}

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

    -- | /O(n)/. A version of 'foldr' that uses the value at the maximal key in
    -- the map as the starting value.
    --
    -- Note that, unlike 'Data.Foldable.foldr1' for 'IntMap', this function is
    -- total if the input function is total.
    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) =
      a -> ((a, IntMap a) -> a) -> Maybe (a, IntMap a) -> a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe a
    v (a -> a -> a
    f a
    v (a -> a) -> ((a, IntMap a) -> a) -> (a, IntMap a) -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> IntMap a -> a) -> (a, IntMap a) -> a
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry ((a -> a -> a) -> a -> IntMap a -> a
    forall a b. (a -> b -> b) -> b -> IntMap a -> b
    M.foldr a -> a -> a
    f))
        (Maybe (a, IntMap a) -> a)
    -> (IntMap a -> Maybe (a, IntMap a)) -> IntMap a -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> Maybe (a, IntMap a)
    forall a. IntMap a -> Maybe (a, IntMap a)
    M.maxView
        (IntMap a -> a) -> IntMap a -> a
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m
    {-# INLINE foldr1 #-}

    -- | /O(n)/. Fold the values in the map using the given left-associative
    -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'elems'@.
    --
    -- > elemsList = reverse . foldl (flip (:)) []
    --
    -- > let f len a = len + (length a)
    -- > foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4
    foldl :: (a -> b -> a) -> a -> NEIntMap b -> a
    foldl :: forall a b. (a -> b -> a) -> a -> NEIntMap b -> a
    foldl a -> b -> a
    f a
    z (NEIntMap Key
    _ b
    v IntMap b
    m) = (a -> b -> a) -> a -> IntMap b -> a
    forall a b. (a -> b -> a) -> a -> IntMap b -> a
    M.foldl a -> b -> a
    f (a -> b -> a
    f a
    z b
    v) IntMap b
    m
    {-# INLINE foldl #-}

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

    -- | /O(n)/. A version of 'foldl' that uses the value at the minimal key in
    -- the map as the starting value.
    --
    -- Note that, unlike 'Data.Foldable.foldl1' for 'IntMap', this function is
    -- total if the input function is total.
    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)/. Fold the keys and values in the map using the given semigroup,
    -- such that
    --
    -- @'foldMapWithKey' f = 'Data.Semigroup.Foldable.fold1' . 'Data.IntMap.NonEmpty.mapWithKey' f@
    --
    -- __WARNING__: Differs from @Data.IntMap.foldMapWithKey@, which traverses
    -- positive items first, then negative items.
    --
    -- This can be an asymptotically faster than
    -- 'Data.IntMap.NonEmpty.foldrWithKey' or 'Data.IntMap.NonEmpty.foldlWithKey' for
    -- some monoids.

    -- TODO: benchmark against maxView method
    foldMapWithKey ::
      Semigroup m =>
      (Key -> a -> m) ->
      NEIntMap a ->
      m
    foldMapWithKey :: forall m a. Semigroup m => (Key -> a -> m) -> NEIntMap a -> m
    foldMapWithKey Key -> a -> m
    f = ((Key, a) -> m) -> NonEmpty (Key, a) -> m
    forall m a. Semigroup m => (a -> m) -> NonEmpty a -> m
    forall (t :: * -> *) m a.
    (Foldable1 t, Semigroup m) =>
    (a -> m) -> t a -> m
    F1.foldMap1 ((Key -> a -> m) -> (Key, a) -> m
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry Key -> a -> m
    f) (NonEmpty (Key, a) -> m)
    -> (NEIntMap a -> NonEmpty (Key, a)) -> NEIntMap a -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> NonEmpty (Key, a)
    forall a. NEIntMap a -> NonEmpty (Key, a)
    toList
    {-# INLINE foldMapWithKey #-}

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

    {-# RULES
    "map/map" forall f g xs. map f (map g xs) = map (f . g) xs
      #-}
    {-# RULES
    "map/coerce" map coerce = coerce
      #-}

    -- | /O(m*log(n\/m + 1)), m <= n/.
    -- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and
    -- @t2@. It prefers @t1@ when duplicate keys are encountered, i.e.
    -- (@'union' == 'Data.IntMap.NonEmpty.unionWith' 'const'@).
    --
    -- > union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")])
    union ::
      NEIntMap a ->
      NEIntMap a ->
      NEIntMap a
    union :: forall a. NEIntMap a -> NEIntMap a -> NEIntMap a
    union 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
    . IntMap a -> IntMap a -> IntMap a
    forall a. IntMap a -> IntMap a -> IntMap a
    M.union 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
    v1 (IntMap a -> NEIntMap a)
    -> (IntMap a -> IntMap a) -> IntMap a -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> IntMap a -> IntMap a
    forall a. IntMap a -> IntMap a -> IntMap a
    M.union 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
    . IntMap a -> IntMap a -> IntMap a
    forall a. IntMap a -> IntMap a -> IntMap a
    M.union (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 union #-}

    -- | The left-biased union of a non-empty list of maps.
    --
    -- > unions (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])])
    -- >     == fromList [(3, "b"), (5, "a"), (7, "C")]
    -- > unions (fromList ((5, "A3") :| [(3, "B3")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "a") :| [(3, "b")])])
    -- >     == fromList ((3, "B3") :| [(5, "A3"), (7, "C")])
    unions ::
      Foldable1 f =>
      f (NEIntMap a) ->
      NEIntMap a
    unions :: forall (f :: * -> *) a. Foldable1 f => f (NEIntMap a) -> NEIntMap a
    unions (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' NEIntMap a -> NEIntMap a -> NEIntMap a
    forall a. NEIntMap a -> NEIntMap a -> NEIntMap a
    union NEIntMap a
    m [NEIntMap a]
    ms
    {-# INLINE unions #-}

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

    -- | /O(1)/. The number of elements in the map.  Guaranteed to be greater
    -- than zero.
    --
    -- > size (singleton 1 'a')                          == 1
    -- > size (fromList ((1,'a') :| [(2,'c'), (3,'b')])) == 3
    size :: NEIntMap a -> Int
    size :: forall a. NEIntMap a -> Key
    size (NEIntMap Key
    _ a
    _ IntMap a
    m) = Key
    1 Key -> Key -> Key
    forall a. Num a => a -> a -> a
    + IntMap a -> Key
    forall a. IntMap a -> Key
    M.size IntMap a
    m
    {-# INLINE size #-}

    -- | /O(log n)/.
    -- Convert a non-empty map back into a normal possibly-empty map, for usage
    -- with functions that expect 'IntMap'.
    --
    -- Can be thought of as "obscuring" the non-emptiness of the map in its
    -- type.  See the 'Data.IntMap.NonEmpty.IsNotEmpty' pattern.
    --
    -- 'nonEmptyMap' and @'maybe' 'Data.IntMap.empty' 'toMap'@ form an isomorphism: they
    -- are perfect structure-preserving inverses of eachother.
    --
    -- > toMap (fromList ((3,"a") :| [(5,"b")])) == Data.IntMap.fromList [(3,"a"), (5,"b")]
    toMap :: NEIntMap a -> IntMap a
    toMap :: forall a. NEIntMap a -> IntMap a
    toMap (NEIntMap Key
    k a
    v 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 toMap #-}

    -- | /O(n)/.
    -- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
    -- That is, behaves exactly like a regular 'traverse' except that the traversing
    -- function also has access to the key associated with a value.
    --
    -- /Use 'traverseWithKey1'/ whenever possible (if your 'Applicative'
    -- also has 'Apply' instance).  This version is provided only for types
    -- that do not have 'Apply' instance, since 'Apply' is not at the moment
    -- (and might not ever be) an official superclass of 'Applicative'.
    --
    -- __WARNING__: Differs from @Data.IntMap.traverseWithKey@, which traverses
    -- positive items first, then negative items.
    --
    -- @
    -- 'traverseWithKey' f = 'unwrapApplicative' . 'traverseWithKey1' (\\k -> WrapApplicative . f k)
    -- @
    traverseWithKey ::
      Applicative t =>
      (Key -> a -> t b) ->
      NEIntMap a ->
      t (NEIntMap b)
    traverseWithKey :: forall (t :: * -> *) a b.
    Applicative t =>
    (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
    traverseWithKey Key -> a -> t b
    f (NEIntMap Key
    k a
    v IntMap a
    m0) =
      Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k
        (b -> IntMap b -> NEIntMap b) -> t b -> t (IntMap b -> NEIntMap b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Key -> a -> t b
    f Key
    k a
    v
        t (IntMap b -> NEIntMap b) -> t (IntMap b) -> t (NEIntMap b)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Key -> a -> t b) -> IntMap a -> t (IntMap b)
    forall (t :: * -> *) a b.
    Applicative t =>
    (Key -> a -> t b) -> IntMap a -> t (IntMap b)
    M.traverseWithKey Key -> a -> t b
    f IntMap a
    m0
    {-# INLINE traverseWithKey #-}

    -- | /O(n)/.
    -- @'traverseWithKey1' f m == 'fromList' <$> 'traverse1' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
    --
    -- That is, behaves exactly like a regular 'traverse1' except that the traversing
    -- function also has access to the key associated with a value.
    --
    -- __WARNING__: Differs from @Data.IntMap.traverseWithKey@, which traverses
    -- positive items first, then negative items.
    --
    -- Is more general than 'traverseWithKey', since works with all 'Apply',
    -- and not just 'Applicative'.

    -- TODO: benchmark against maxView-based methods
    traverseWithKey1 ::
      Apply t =>
      (Key -> a -> t b) ->
      NEIntMap a ->
      t (NEIntMap b)
    traverseWithKey1 :: forall (t :: * -> *) a b.
    Apply t =>
    (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
    traverseWithKey1 Key -> a -> t b
    f (NEIntMap Key
    k0 a
    v IntMap a
    m0) = case MaybeApply t (IntMap b) -> Either (t (IntMap b)) (IntMap b)
    forall (f :: * -> *) a. MaybeApply f a -> Either (f a) a
    runMaybeApply MaybeApply t (IntMap b)
    m1 of
      Left t (IntMap b)
    m2 -> Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 (b -> IntMap b -> NEIntMap b) -> t b -> t (IntMap b -> NEIntMap b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Key -> a -> t b
    f Key
    k0 a
    v t (IntMap b -> NEIntMap b) -> t (IntMap b) -> t (NEIntMap b)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    <.> t (IntMap b)
    m2
      Right IntMap b
    m2 -> (b -> IntMap b -> NEIntMap b) -> IntMap b -> b -> NEIntMap b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (Key -> b -> IntMap b -> NEIntMap b
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0) IntMap b
    m2 (b -> NEIntMap b) -> t b -> t (NEIntMap b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Key -> a -> t b
    f Key
    k0 a
    v
      where
        m1 :: MaybeApply t (IntMap b)
    m1 = (Key -> a -> MaybeApply t b) -> IntMap a -> MaybeApply t (IntMap b)
    forall (t :: * -> *) a b.
    Applicative t =>
    (Key -> a -> t b) -> IntMap a -> t (IntMap b)
    M.traverseWithKey (\Key
    k -> Either (t b) b -> MaybeApply t b
    forall (f :: * -> *) a. Either (f a) a -> MaybeApply f a
    MaybeApply (Either (t b) b -> MaybeApply t b)
    -> (a -> Either (t b) b) -> a -> MaybeApply t b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . t b -> Either (t b) b
    forall a b. a -> Either a b
    Left (t b -> Either (t b) b) -> (a -> t b) -> a -> Either (t b) b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> a -> t b
    f Key
    k) IntMap a
    m0
    {-# INLINEABLE traverseWithKey1 #-}

    -- | /O(n)/. Convert the map to a non-empty list of key\/value pairs.
    --
    -- > toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])
    toList :: NEIntMap a -> NonEmpty (Key, a)
    toList :: forall a. NEIntMap a -> NonEmpty (Key, a)
    toList (NEIntMap Key
    k a
    v IntMap a
    m) = (Key
    k, a
    v) (Key, a) -> [(Key, a)] -> NonEmpty (Key, a)
    forall a. a -> [a] -> NonEmpty a
    :| IntMap a -> [(Key, a)]
    forall a. IntMap a -> [(Key, a)]
    M.toList IntMap a
    m
    {-# INLINE toList #-}

    -- | /O(log n)/. Smart constructor for an 'NEIntMap' from a 'IntMap'.  Returns
    -- 'Nothing' if the 'IntMap' was originally actually empty, and @'Just' n@
    -- with an 'NEIntMap', if the 'IntMap' was not empty.
    --
    -- 'nonEmptyMap' and @'maybe' 'Data.IntMap.empty' 'toMap'@ form an
    -- isomorphism: they are perfect structure-preserving inverses of
    -- eachother.
    --
    -- See 'Data.IntMap.NonEmpty.IsNonEmpty' for a pattern synonym that lets you
    -- "match on" the possiblity of a 'IntMap' being an 'NEIntMap'.
    --
    -- > nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")]))
    nonEmptyMap :: IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap :: forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap = ((((Key, a), IntMap a) -> NEIntMap a)
    -> Maybe ((Key, a), IntMap a) -> Maybe (NEIntMap a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((((Key, a), IntMap a) -> NEIntMap a)
     -> Maybe ((Key, a), IntMap a) -> Maybe (NEIntMap a))
    -> ((Key -> a -> IntMap a -> NEIntMap a)
        -> ((Key, a), IntMap a) -> NEIntMap a)
    -> (Key -> a -> IntMap a -> NEIntMap a)
    -> Maybe ((Key, a), IntMap a)
    -> Maybe (NEIntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Key, a) -> IntMap a -> NEIntMap a)
    -> ((Key, a), IntMap a) -> NEIntMap a
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry (((Key, a) -> IntMap a -> NEIntMap a)
     -> ((Key, a), IntMap a) -> NEIntMap a)
    -> ((Key -> a -> IntMap a -> NEIntMap a)
        -> (Key, a) -> IntMap a -> NEIntMap a)
    -> (Key -> a -> IntMap a -> NEIntMap a)
    -> ((Key, a), IntMap a)
    -> NEIntMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> a -> IntMap a -> NEIntMap a)
    -> (Key, a) -> IntMap a -> NEIntMap a
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry) Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap (Maybe ((Key, a), IntMap a) -> Maybe (NEIntMap a))
    -> (IntMap a -> Maybe ((Key, a), IntMap a))
    -> IntMap a
    -> Maybe (NEIntMap 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.minViewWithKey
    {-# INLINE nonEmptyMap #-}

    -- | /O(log n)/. A general continuation-based way to consume a 'IntMap' as if
    -- it were an 'NEIntMap'. @'withNonEmpty' def f@ will take a 'IntMap'.  If map is
    -- empty, it will evaluate to @def@.  Otherwise, a non-empty map 'NEIntMap'
    -- will be fed to the function @f@ instead.
    --
    -- @'nonEmptyMap' == 'withNonEmpty' 'Nothing' 'Just'@
    withNonEmpty ::
      -- | value to return if map is empty
      r ->
      -- | function to apply if map is not empty
      (NEIntMap a -> r) ->
      IntMap a ->
      r
    withNonEmpty :: forall r a. r -> (NEIntMap a -> r) -> IntMap a -> r
    withNonEmpty r
    def NEIntMap a -> r
    f = r -> (NEIntMap a -> r) -> Maybe (NEIntMap a) -> r
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe r
    def NEIntMap a -> r
    f (Maybe (NEIntMap a) -> r)
    -> (IntMap a -> Maybe (NEIntMap a)) -> IntMap a -> r
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> Maybe (NEIntMap a)
    forall a. IntMap a -> Maybe (NEIntMap a)
    nonEmptyMap
    {-# INLINE withNonEmpty #-}

    -- | /O(n*log n)/. Build a non-empty map from a non-empty list of
    -- key\/value pairs. See also 'Data.IntMap.NonEmpty.fromAscList'. If the list
    -- contains more than one value for the same key, the last value for the
    -- key is retained.
    --
    -- > fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")])
    -- > fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")])

    -- TODO: write manually and optimize to be equivalent to
    -- 'fromDistinctAscList' if items are ordered, just like the actual
    -- 'M.fromList'.
    fromList :: NonEmpty (Key, a) -> NEIntMap a
    fromList :: forall a. NonEmpty (Key, a) -> NEIntMap a
    fromList ((Key
    k, a
    v) :| [(Key, a)]
    xs) =
      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 -> a -> a
    forall a b. a -> b -> a
    const a -> a
    forall a. a -> a
    id) 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.fromList
        ([(Key, a)] -> NEIntMap a) -> [(Key, a)] -> NEIntMap a
    forall a b. (a -> b) -> a -> b
    $ [(Key, a)]
    xs
    {-# INLINE fromList #-}

    -- | /O(1)/. A map with a single element.
    --
    -- > singleton 1 'a'        == fromList ((1, 'a') :| [])
    -- > size (singleton 1 'a') == 1
    singleton :: Key -> a -> NEIntMap a
    singleton :: forall a. Key -> a -> NEIntMap a
    singleton Key
    k a
    v = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v IntMap a
    forall a. IntMap a
    M.empty
    {-# INLINE singleton #-}

    -- | /O(log n)/. Insert with a function, combining new value and old value.
    -- @'insertWith' 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 new_value old_value)@.
    --
    -- See 'Data.IntMap.NonEmpty.insertIntMapWith' for a version where the first
    -- argument is a 'IntMap'.
    --
    -- > insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")])
    -- > insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
    insertWith ::
      (a -> a -> a) ->
      Key ->
      a ->
      NEIntMap a ->
      NEIntMap a
    insertWith :: forall a. (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a
    insertWith 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 (a -> a -> a
    f 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
    $ (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
    forall a. (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
    M.insertWith a -> a -> a
    f Key
    k a
    v IntMap a
    m
    {-# INLINE insertWith #-}

    -- | Left-biased union
    instance Semigroup (NEIntMap a) where
      <> :: NEIntMap a -> NEIntMap a -> NEIntMap a
    (<>) = NEIntMap a -> NEIntMap a -> NEIntMap a
    forall a. NEIntMap a -> NEIntMap a -> NEIntMap a
    union
      {-# INLINE (<>) #-}
      sconcat :: NonEmpty (NEIntMap a) -> NEIntMap a
    sconcat = NonEmpty (NEIntMap a) -> NEIntMap a
    forall (f :: * -> *) a. Foldable1 f => f (NEIntMap a) -> NEIntMap a
    unions
      {-# INLINE sconcat #-}

    instance Functor NEIntMap where
      fmap :: forall a b. (a -> b) -> NEIntMap a -> NEIntMap b
    fmap = (a -> b) -> NEIntMap a -> NEIntMap b
    forall a b. (a -> b) -> NEIntMap a -> NEIntMap b
    map
      {-# INLINE fmap #-}
      a
    x <$ :: forall a b. a -> NEIntMap b -> NEIntMap a
    <$ NEIntMap Key
    k b
    _ IntMap b
    m = Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    x (a
    x a -> IntMap b -> IntMap a
    forall a b. a -> IntMap b -> IntMap a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ IntMap b
    m)
      {-# INLINE (<$) #-}

    -- | @since 0.3.4.4
    instance Invariant NEIntMap where
      invmap :: forall a b. (a -> b) -> (b -> a) -> NEIntMap a -> NEIntMap b
    invmap a -> b
    f b -> a
    _ = (a -> b) -> NEIntMap a -> NEIntMap b
    forall a b. (a -> b) -> NEIntMap a -> NEIntMap b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f
      {-# INLINE invmap #-}

    -- | Traverses elements in order of ascending keys.
    --
    -- __WARNING:__ 'F.fold' and 'F.foldMap' are different than for the
    -- 'IntMap' instance.  They traverse elements in order of ascending keys,
    -- while 'IntMap' traverses positive keys first, then negative keys.
    --
    -- 'Data.Foldable.foldr1', 'Data.Foldable.foldl1', 'Data.Foldable.minimum',
    -- 'Data.Foldable.maximum' are all total.
    #if MIN_VERSION_base(4,11,0)
    instance F.Foldable NEIntMap where
        fold :: forall m. Monoid m => NEIntMap m -> m
    fold      (NEIntMap Key
    _ m
    v IntMap m
    m) = m
    v m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <> [m] -> m
    forall m. Monoid m => [m] -> m
    forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
    F.fold (IntMap m -> [m]
    forall a. IntMap a -> [a]
    M.elems IntMap m
    m)
        {-# INLINE fold #-}
        foldMap :: forall m a. Monoid m => (a -> m) -> NEIntMap a -> m
    foldMap a -> m
    f (NEIntMap Key
    _ a
    v IntMap a
    m) = a -> m
    f a
    v m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <> (a -> m) -> [a] -> m
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    F.foldMap a -> m
    f (IntMap a -> [a]
    forall a. IntMap a -> [a]
    M.elems IntMap a
    m)
        {-# INLINE foldMap #-}
        foldr :: forall a b. (a -> b -> b) -> b -> NEIntMap a -> b
    foldr   = (a -> b -> b) -> b -> NEIntMap a -> b
    forall a b. (a -> b -> b) -> b -> NEIntMap a -> b
    foldr
        {-# INLINE foldr #-}
        foldr' :: forall a b. (a -> b -> b) -> b -> NEIntMap a -> b
    foldr'  = (a -> b -> b) -> b -> NEIntMap a -> b
    forall a b. (a -> b -> b) -> b -> NEIntMap a -> b
    foldr'
        {-# INLINE foldr' #-}
        foldr1 :: forall a. (a -> a -> a) -> NEIntMap a -> a
    foldr1  = (a -> a -> a) -> NEIntMap a -> a
    forall a. (a -> a -> a) -> NEIntMap a -> a
    foldr1
        {-# INLINE foldr1 #-}
        foldl :: forall a b. (a -> b -> a) -> a -> NEIntMap b -> a
    foldl   = (b -> a -> b) -> b -> NEIntMap a -> b
    forall a b. (a -> b -> a) -> a -> NEIntMap b -> a
    foldl
        {-# INLINE foldl #-}
        foldl' :: forall a b. (a -> b -> a) -> a -> NEIntMap b -> a
    foldl'  = (b -> a -> b) -> b -> NEIntMap a -> b
    forall a b. (a -> b -> a) -> a -> NEIntMap b -> a
    foldl'
        {-# INLINE foldl' #-}
        foldl1 :: forall a. (a -> a -> a) -> NEIntMap a -> a
    foldl1  = (a -> a -> a) -> NEIntMap a -> a
    forall a. (a -> a -> a) -> NEIntMap a -> a
    foldl1
        {-# INLINE foldl1 #-}
        null :: forall a. NEIntMap a -> Bool
    null NEIntMap a
    _  = Bool
    False
        {-# INLINE null #-}
        length :: forall a. NEIntMap a -> Key
    length  = NEIntMap a -> Key
    forall a. NEIntMap a -> Key
    size
        {-# INLINE length #-}
        elem :: forall a. Eq a => a -> NEIntMap a -> Bool
    elem a
    x (NEIntMap Key
    _ a
    v IntMap a
    m) = a -> IntMap a -> Bool
    forall a. Eq a => a -> IntMap a -> Bool
    forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
    F.elem a
    x IntMap a
    m
                               Bool -> Bool -> Bool
    || a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    v
        {-# INLINE elem #-}
        -- TODO: use build
        toList :: forall a. NEIntMap a -> [a]
    toList  = NonEmpty a -> [a]
    forall a. NonEmpty a -> [a]
    forall (t :: * -> *) a. Foldable t => t a -> [a]
    F.toList (NonEmpty a -> [a])
    -> (NEIntMap a -> NonEmpty a) -> NEIntMap a -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEIntMap a -> NonEmpty a
    forall a. NEIntMap a -> NonEmpty a
    elems
        {-# INLINE toList #-}
    #else
    instance F.Foldable NEIntMap where
        fold      (NEIntMap _ v m) = v `mappend` F.fold (M.elems m)
        {-# INLINE fold #-}
        foldMap f (NEIntMap _ v m) = f v `mappend` F.foldMap f (M.elems m)
        {-# INLINE foldMap #-}
        foldr   = foldr
        {-# INLINE foldr #-}
        foldr'  = foldr'
        {-# INLINE foldr' #-}
        foldr1  = foldr1
        {-# INLINE foldr1 #-}
        foldl   = foldl
        {-# INLINE foldl #-}
        foldl'  = foldl'
        {-# INLINE foldl' #-}
        foldl1  = foldl1
        {-# INLINE foldl1 #-}
        null _  = False
        {-# INLINE null #-}
        length  = size
        {-# INLINE length #-}
        elem x (NEIntMap _ v m) = F.elem x m
                               || x == v
        {-# INLINE elem #-}
        -- TODO: use build
        toList  = F.toList . elems
        {-# INLINE toList #-}
    #endif

    -- | Traverses elements in order of ascending keys
    --
    -- __WARNING:__ Different than for the 'IntMap' instance.  They traverse
    -- elements in order of ascending keys, while 'IntMap' traverses positive
    -- keys first, then negative keys.
    instance Traversable NEIntMap where
      traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> NEIntMap a -> f (NEIntMap b)
    traverse a -> f b
    f = (Key -> a -> f b) -> NEIntMap a -> f (NEIntMap b)
    forall (t :: * -> *) a b.
    Applicative t =>
    (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
    traverseWithKey ((a -> f b) -> Key -> a -> f b
    forall a b. a -> b -> a
    const a -> f b
    f)
      {-# INLINE traverse #-}

    -- | Traverses elements in order of ascending keys
    --
    -- __WARNING:__ 'F1.fold1' and 'F1.foldMap1' are different than 'F.fold' and
    -- 'F.foldMap' for the 'IntMap' instance of 'Foldable'.  They traverse
    -- elements in order of ascending keys, while 'IntMap' traverses positive
    -- keys first, then negative keys.
    #if MIN_VERSION_base(4,11,0)
    instance Foldable1 NEIntMap where
        fold1 :: forall m. Semigroup m => NEIntMap m -> m
    fold1 (NEIntMap Key
    _ m
    v IntMap m
    m) = m -> (m -> m) -> Maybe m -> m
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe m
    v (m
    v m -> m -> m
    forall a. Semigroup a => a -> a -> a
    <>)
                               (Maybe m -> m) -> (IntMap m -> Maybe m) -> IntMap m -> m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (m -> Maybe m) -> [m] -> Maybe m
    forall m a. Monoid m => (a -> m) -> [a] -> m
    forall (t :: * -> *) m a.
    (Foldable t, Monoid m) =>
    (a -> m) -> t a -> m
    F.foldMap m -> Maybe m
    forall a. a -> Maybe a
    Just
                               ([m] -> Maybe m) -> (IntMap m -> [m]) -> IntMap m -> Maybe m
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap m -> [m]
    forall a. IntMap a -> [a]
    M.elems
                               (IntMap m -> m) -> IntMap m -> m
    forall a b. (a -> b) -> a -> b
    $ IntMap m
    m
        {-# INLINE fold1 #-}
        foldMap1 :: forall m a. Semigroup m => (a -> m) -> NEIntMap a -> m
    foldMap1 a -> m
    f = (Key -> a -> m) -> NEIntMap a -> m
    forall m a. Semigroup m => (Key -> a -> m) -> NEIntMap a -> m
    foldMapWithKey ((a -> m) -> Key -> a -> m
    forall a b. a -> b -> a
    const a -> m
    f)
        {-# INLINE foldMap1 #-}
        toNonEmpty :: forall a. NEIntMap a -> NonEmpty a
    toNonEmpty = NEIntMap a -> NonEmpty a
    forall a. NEIntMap a -> NonEmpty a
    elems
        {-# INLINE toNonEmpty #-}
    #else
    instance Foldable1 NEIntMap where
        fold1 (NEIntMap _ v m) = option v (v <>)
                               . F.foldMap (Option . Just)
                               . M.elems
                               $ m
        {-# INLINE fold1 #-}
        foldMap1 f = foldMapWithKey (const f)
        {-# INLINE foldMap1 #-}
        toNonEmpty = elems
        {-# INLINE toNonEmpty #-}
    #endif

    -- | Traverses elements in order of ascending keys
    --
    -- __WARNING:__ 'traverse1' and 'sequence1' are different 'traverse' and
    -- 'sequence' for the 'IntMap' instance of 'Traversable'.  They traverse
    -- elements in order of ascending keys, while 'IntMap' traverses positive
    -- keys first, then negative keys.
    instance Traversable1 NEIntMap where
      traverse1 :: forall (f :: * -> *) a b.
    Apply f =>
    (a -> f b) -> NEIntMap a -> f (NEIntMap b)
    traverse1 a -> f b
    f = (Key -> a -> f b) -> NEIntMap a -> f (NEIntMap b)
    forall (t :: * -> *) a b.
    Apply t =>
    (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b)
    traverseWithKey1 ((a -> f b) -> Key -> a -> f b
    forall a b. a -> b -> a
    const a -> f b
    f)
      {-# INLINE traverse1 #-}

    -- | 'extract' gets the value at the minimal key, and 'duplicate' produces
    -- a map of maps comprised of all keys from the original map greater than
    -- or equal to the current key.
    --
    -- @since 0.1.1.0
    instance Comonad NEIntMap where
      extract :: forall a. NEIntMap a -> a
    extract = NEIntMap a -> a
    forall a. NEIntMap a -> a
    neimV0
      {-# INLINE extract #-}

      -- We'd like to use 'M.mapAccumWithKey', but it traverses things in the
      -- wrong order.
      duplicate :: forall a. NEIntMap a -> NEIntMap (NEIntMap a)
    duplicate n0 :: NEIntMap a
    n0@(NEIntMap Key
    k0 a
    _ IntMap a
    m0) =
        Key -> NEIntMap a -> IntMap (NEIntMap a) -> NEIntMap (NEIntMap a)
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k0 NEIntMap a
    n0
          (IntMap (NEIntMap a) -> NEIntMap (NEIntMap a))
    -> (IntMap a -> IntMap (NEIntMap a))
    -> IntMap a
    -> NEIntMap (NEIntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(Key, NEIntMap a)] -> IntMap (NEIntMap a)
    forall a. [(Key, a)] -> IntMap a
    M.fromDistinctAscList
          ([(Key, NEIntMap a)] -> IntMap (NEIntMap a))
    -> (IntMap a -> [(Key, NEIntMap a)])
    -> IntMap a
    -> IntMap (NEIntMap a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (IntMap a, [(Key, NEIntMap a)]) -> [(Key, NEIntMap a)]
    forall a b. (a, b) -> b
    snd
          ((IntMap a, [(Key, NEIntMap a)]) -> [(Key, NEIntMap a)])
    -> (IntMap a -> (IntMap a, [(Key, NEIntMap a)]))
    -> IntMap a
    -> [(Key, NEIntMap a)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (IntMap a -> (Key, a) -> (IntMap a, (Key, NEIntMap a)))
    -> IntMap a -> [(Key, a)] -> (IntMap a, [(Key, NEIntMap a)])
    forall (t :: * -> *) s a b.
    Traversable t =>
    (s -> a -> (s, b)) -> s -> t a -> (s, t b)
    L.mapAccumL IntMap a -> (Key, a) -> (IntMap a, (Key, NEIntMap a))
    forall {a}. IntMap a -> (Key, a) -> (IntMap a, (Key, NEIntMap a))
    go IntMap a
    m0
          ([(Key, a)] -> (IntMap a, [(Key, NEIntMap a)]))
    -> (IntMap a -> [(Key, a)])
    -> IntMap a
    -> (IntMap a, [(Key, NEIntMap a)])
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntMap a -> [(Key, a)]
    forall a. IntMap a -> [(Key, a)]
    M.toList
          (IntMap a -> NEIntMap (NEIntMap a))
    -> IntMap a -> NEIntMap (NEIntMap a)
    forall a b. (a -> b) -> a -> b
    $ IntMap a
    m0
        where
          go :: IntMap a -> (Key, a) -> (IntMap a, (Key, NEIntMap a))
    go IntMap a
    m (Key
    k, a
    v) = (IntMap a
    m', (Key
    k, Key -> a -> IntMap a -> NEIntMap a
    forall a. Key -> a -> IntMap a -> NEIntMap a
    NEIntMap Key
    k a
    v IntMap a
    m'))
            where
              !m' :: IntMap a
    m' = IntMap a -> IntMap a
    forall a. IntMap a -> IntMap a
    M.deleteMin IntMap a
    m
      {-# INLINE duplicate #-}

    -- | /O(n)/. Test if the internal map structure is valid.
    valid :: NEIntMap a -> Bool
    valid :: forall a. NEIntMap a -> Bool
    valid (NEIntMap Key
    k a
    _ IntMap a
    m) = (((Key, a), IntMap a) -> Bool)
    -> Maybe ((Key, a), IntMap a) -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    all ((Key
    k Key -> Key -> Bool
    forall a. Ord a => a -> a -> Bool
    <) (Key -> Bool)
    -> (((Key, a), IntMap a) -> Key) -> ((Key, a), IntMap a) -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key, a) -> Key
    forall a b. (a, b) -> a
    fst ((Key, a) -> Key)
    -> (((Key, a), IntMap a) -> (Key, a))
    -> ((Key, a), IntMap a)
    -> Key
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((Key, a), IntMap a) -> (Key, a)
    forall a b. (a, b) -> a
    fst) (IntMap a -> Maybe ((Key, a), IntMap a)
    forall a. IntMap a -> Maybe ((Key, a), IntMap a)
    M.minViewWithKey IntMap a
    m)

    -- | /O(log n)/. Insert new key and value into a map where keys are
    -- /strictly greater than/ the new key.  That is, the new key must be
    -- /strictly less than/ all keys present in the 'IntMap'.  /The precondition
    -- is not checked./
    --
    -- At the moment this is simply an alias for @Data.IntSet.insert@, but it's
    -- left here as a placeholder in case this eventually gets implemented in
    -- a more efficient way.

    -- TODO: implementation
    insertMinMap :: Key -> a -> IntMap a -> IntMap a
    insertMinMap :: forall a. Key -> a -> IntMap a -> IntMap a
    insertMinMap = Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    M.insert
    {-# INLINEABLE insertMinMap #-}

    -- | /O(log n)/. Insert new key and value into a map where keys are
    -- /strictly less than/ the new key.  That is, the new key must be
    -- /strictly greater than/ all keys present in the 'IntMap'.  /The
    -- precondition is not checked./
    --
    -- At the moment this is simply an alias for @Data.IntSet.insert@, but it's
    -- left here as a placeholder in case this eventually gets implemented in
    -- a more efficient way.

    -- TODO: implementation
    insertMaxMap :: Key -> a -> IntMap a -> IntMap a
    insertMaxMap :: forall a. Key -> a -> IntMap a -> IntMap a
    insertMaxMap = Key -> a -> IntMap a -> IntMap a
    forall a. Key -> a -> IntMap a -> IntMap a
    M.insert
    {-# INLINEABLE insertMaxMap #-}