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

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

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

  -- * Construction
  , singleton
  , fromSet

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

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

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

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

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

  -- ** Size
  , size

  -- * Combine

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

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

  -- ** Intersection
  , intersection
  , intersectionWith
  , intersectionWithKey

  -- -- ** Universal combining function
  -- , mergeWithKey

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

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

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

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

  -- ** Lists
  , toList

  -- ** Ordered lists
  , toAscList
  , toDescList

  -- * Filter
  , filter
  , filterWithKey
  , restrictKeys
  , withoutKeys
  , partition
  , partitionWithKey

  , mapMaybe
  , mapMaybeWithKey
  , mapEither
  , mapEitherWithKey

  , split
  , splitLookup
  , splitRoot

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

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

  -- * Debugging
  , valid
  ) where

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

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

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

{-# COMPLETE IsNonEmpty, IsEmpty #-}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

infixl 9 !?
infixl 9 !

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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