{-# 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 String
"fromList" <- ReadPrec Lexeme
lexP
    NonEmpty (Key, e)
xs <- ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e))
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e)))
-> (ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e)))
-> ReadPrec (NonEmpty (Key, e))
-> ReadPrec (NonEmpty (Key, e))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Key -> ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e))
forall a. Key -> ReadPrec a -> ReadPrec a
prec Key
10 (ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e)))
-> ReadPrec (NonEmpty (Key, e)) -> ReadPrec (NonEmpty (Key, e))
forall a b. (a -> b) -> a -> b
$ ReadPrec (NonEmpty (Key, e))
forall a. Read a => ReadPrec a
readPrec
    NEIntMap e -> ReadPrec (NEIntMap e)
forall a. a -> ReadPrec a
forall (m :: * -> *) a. Monad m => a -> m a
return (NonEmpty (Key, e) -> NEIntMap e
forall a. NonEmpty (Key, a) -> NEIntMap a
fromList NonEmpty (Key, e)
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 #-}