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

-- |
-- Module      : Data.Map.NonEmpty
-- Copyright   : (c) Justin Le 2018
-- License     : BSD3
--
-- Maintainer  : justin@jle.im
-- Stability   : experimental
-- Portability : non-portable
--
-- = Non-Empty Finite Maps (lazy interface)
--
-- The @'NEMap' k v@ type represents a non-empty finite map (sometimes
-- called a dictionary) from keys of type @k@ to values of type @v@.
-- An 'NEMap' is strict in its keys but lazy in its values.
--
-- See documentation for 'NEMap' for information on how to convert and
-- manipulate such non-empty maps.
--
-- This module essentially re-imports the API of "Data.Map.Lazy" and its
-- 'Map' 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).  All typeclass constraints are identical to their "Data.Map"
-- counterparts.
--
-- Because 'NEMap' is implemented using 'Map', all of the caveats of using
-- 'Map' 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, 'Map' is returned instead.
--
-- Some variants of functions (like 'alter'', 'alterF'', 'adjustAt',
-- 'adjustMin', 'adjustMax', 'adjustMinWithKey', 'adjustMaxWithKey') are
-- provided in a way restructured to preserve guaruntees of non-empty maps
-- being returned.
--
-- Some functions (like 'mapEither', 'partition', 'spanAntitone', '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.Map" functions:
--
-- > import qualified Data.Map.NonEmpty as NEM
--
-- 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.Map.NonEmpty (
  -- * Non-Empty Map type
    NEMap
  -- ** 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

  -- ** From Descending Lists
  , fromDescList
  , fromDescListWith
  , fromDescListWithKey
  , fromDistinctDescList

  -- * 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
  , absurdNEMap

  -- ** Size
  , size

  -- * Combine

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

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

  -- ** Intersection
  , intersection
  , intersectionWith
  , intersectionWithKey

  -- -- ** Unsafe general combining function
  -- , mergeWithKey

  -- * Traversal
  -- ** Map
  , map
  , mapWithKey
  , traverseWithKey1
  , traverseWithKey
  , traverseMaybeWithKey1
  , traverseMaybeWithKey
  , 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
  , takeWhileAntitone
  , dropWhileAntitone
  , spanAntitone

  , mapMaybe
  , mapMaybeWithKey
  , mapEither
  , mapEitherWithKey

  , split
  , splitLookup
  , splitRoot

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

  -- * Indexed
  , lookupIndex
  , findIndex
  , elemAt
  , updateAt
  , adjustAt
  , deleteAt
  , take
  , drop
  , splitAt

  -- * 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.Function
import           Data.Functor.Apply
import           Data.Functor.Identity
import           Data.List.NonEmpty         (NonEmpty(..))
import           Data.Map                   (Map)
import           Data.Map.NonEmpty.Internal
import           Data.Maybe hiding          (mapMaybe)
import           Data.Semigroup.Foldable    (Foldable1)
import           Data.Set                   (Set)
import           Data.Set.NonEmpty.Internal (NESet(..))
import           Data.These
import           Data.Void
import           Prelude hiding             (lookup, foldr1, foldl1, foldr, foldl, filter, map, take, drop, splitAt)
import qualified Data.Foldable              as F
import qualified Data.List.NonEmpty         as NE
import qualified Data.Map                   as M
import qualified Data.Maybe                 as Maybe
import qualified Data.Semigroup.Foldable    as F1
import qualified Data.Set                   as S

-- | /O(1)/ match, /O(log n)/ usage of contents. The 'IsNonEmpty' and
-- 'IsEmpty' patterns allow you to treat a 'Map' as if it were either
-- a @'IsNonEmpty' n@ (where @n@ is a 'NEMap') or an 'IsEmpty'.
--
-- For example, you can pattern match on a 'Map':
--
-- @
-- myFunc :: 'Map' K X -> Y
-- myFunc ('IsNonEmpty' n) =  -- here, the user provided a non-empty map, and @n@ is the 'NEMap'
-- myFunc 'IsEmpty'        =  -- here, the user provided an empty map.
-- @
--
-- Matching on @'IsNonEmpty' n@ means that the original 'Map' was /not/
-- empty, and you have a verified-non-empty 'NEMap' @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 'NEMap' back into a 'Map', obscuring its non-emptiness (see 'toMap').
pattern IsNonEmpty :: NEMap k a -> Map k a
pattern $bIsNonEmpty :: NEMap k a -> Map k a
$mIsNonEmpty :: forall r k a. Map k a -> (NEMap k a -> r) -> (Void# -> r) -> r
IsNonEmpty n <- (nonEmptyMap->Just n)
  where
    IsNonEmpty NEMap k a
n = NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n

-- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
-- a 'Map' as if it were either a @'IsNonEmpty' n@ (where @n@ is
-- a 'NEMap') or an 'IsEmpty'.
--
-- Matching on 'IsEmpty' means that the original 'Map' 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.Map.empty'.
--
-- See 'IsNonEmpty' for more information.
pattern IsEmpty :: Map k a
pattern $bIsEmpty :: Map k a
$mIsEmpty :: forall r k a. Map k a -> (Void# -> r) -> (Void# -> r) -> r
IsEmpty <- (M.null->True)
  where
    IsEmpty = Map k a
forall k a. Map k a
M.empty

{-# COMPLETE IsNonEmpty, IsEmpty #-}

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

-- | /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
    :: (k -> a)
    -> NESet k
    -> NEMap k a
fromSet :: (k -> a) -> NESet k -> NEMap k a
fromSet k -> a
f (NESet k
k Set k
ks) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k (k -> a
f k
k) ((k -> a) -> Set k -> Map k a
forall k a. (k -> a) -> Set k -> Map k a
M.fromSet k -> a
f Set k
ks)
{-# INLINE fromSet #-}

-- | /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
    :: Ord k
    => k
    -> NEMap k a
    -> Maybe a
lookup :: k -> NEMap k a -> Maybe a
lookup k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
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 -> k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup k
k Map k 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'
(!?) :: Ord k => NEMap k a -> k -> Maybe a
!? :: NEMap k a -> k -> Maybe a
(!?) = (k -> NEMap k a -> Maybe a) -> NEMap k a -> k -> Maybe a
forall a b c. (a -> b -> c) -> b -> a -> c
flip k -> NEMap k a -> Maybe a
forall k a. Ord k => k -> NEMap k 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'
(!) :: Ord k => NEMap k a -> k -> a
(!) NEMap k a
m k
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
$ NEMap k a
m NEMap k a -> k -> Maybe a
forall k a. Ord k => NEMap k a -> k -> Maybe a
!? k
k
  where
    e :: a
e = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"NEMap.!: 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
    :: Ord k
    => a
    -> k
    -> NEMap k a
    -> a
findWithDefault :: a -> k -> NEMap k a -> a
findWithDefault a
def k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> a
def
    Ordering
EQ -> a
v
    Ordering
GT -> a -> k -> Map k a -> a
forall k a. Ord k => a -> k -> Map k a -> a
M.findWithDefault a
def k
k Map k 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 :: Ord k => k -> NEMap k a -> Bool
member :: k -> NEMap k a -> Bool
member k
k (NEMap k
k0 a
_ Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Bool
False
    Ordering
EQ -> Bool
True
    Ordering
GT -> k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.member k
k Map k 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 :: Ord k => k -> NEMap k a -> Bool
notMember :: k -> NEMap k a -> Bool
notMember k
k (NEMap k
k0 a
_ Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Bool
True
    Ordering
EQ -> Bool
False
    Ordering
GT -> k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.notMember k
k Map k 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 :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupLT :: k -> NEMap k a -> Maybe (k, a)
lookupLT k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, a)
forall a. Maybe a
Nothing
    Ordering
EQ -> Maybe (k, a)
forall a. Maybe a
Nothing
    Ordering
GT -> k -> Map k a -> Maybe (k, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
M.lookupLT k
k Map k a
m Maybe (k, a) -> Maybe (k, a) -> Maybe (k, a)
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
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 :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupGT :: k -> NEMap k a -> Maybe (k, a)
lookupGT k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k0, a
v)
    Ordering
EQ -> Map k a -> Maybe (k, a)
forall k a. Map k a -> Maybe (k, a)
M.lookupMin Map k a
m
    Ordering
GT -> k -> Map k a -> Maybe (k, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
M.lookupGT k
k Map k 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 :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupLE :: k -> NEMap k a -> Maybe (k, a)
lookupLE k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe (k, a)
forall a. Maybe a
Nothing
    Ordering
EQ -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k0, a
v)
    Ordering
GT -> k -> Map k a -> Maybe (k, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
M.lookupLE k
k Map k a
m Maybe (k, a) -> Maybe (k, a) -> Maybe (k, a)
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
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 :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupGE :: k -> NEMap k a -> Maybe (k, a)
lookupGE k
k (NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k0, a
v)
    Ordering
EQ -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k0, a
v)
    Ordering
GT -> k -> Map k a -> Maybe (k, a)
forall k v. Ord k => k -> Map k v -> Maybe (k, v)
M.lookupGE k
k Map k 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
    :: Ord k
    => (a -> a -> a)
    -> NEMap k a
    -> NEMap k a
    -> NEMap k a
unionWith :: (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
unionWith a -> a -> a
f n1 :: NEMap k a
n1@(NEMap k
k1 a
v1 Map k a
m1) n2 :: NEMap k a
n2@(NEMap k
k2 a
v2 Map k a
m2) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2 of
    Ordering
LT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k1 a
v1        (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith a -> a -> a
f Map k a
m1 (Map k a -> Map k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n2
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k1 (a -> a -> a
f a
v1 a
v2) (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith a -> a -> a
f Map k a
m1         (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k a
m2
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k2 a
v2        (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith a -> a -> a
f (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n1) (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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
    :: Ord k
    => (k -> a -> a -> a)
    -> NEMap k a
    -> NEMap k a
    -> NEMap k a
unionWithKey :: (k -> a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
unionWithKey k -> a -> a -> a
f n1 :: NEMap k a
n1@(NEMap k
k1 a
v1 Map k a
m1) n2 :: NEMap k a
n2@(NEMap k
k2 a
v2 Map k a
m2) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2 of
    Ordering
LT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k1 a
v1           (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWithKey k -> a -> a -> a
f Map k a
m1 (Map k a -> Map k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n2
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k1 (k -> a -> a -> a
f k
k1 a
v1 a
v2) (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWithKey k -> a -> a -> a
f Map k a
m1         (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k a
m2
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k2 a
v2           (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWithKey k -> a -> a -> a
f (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n1) (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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, Ord k)
    => (a -> a -> a)
    -> f (NEMap k a)
    -> NEMap k a
unionsWith :: (a -> a -> a) -> f (NEMap k a) -> NEMap k a
unionsWith a -> a -> a
f (f (NEMap k a) -> NonEmpty (NEMap k a)
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
F1.toNonEmpty->(NEMap k a
m :| [NEMap k a]
ms)) = (NEMap k a -> NEMap k a -> NEMap k a)
-> NEMap k a -> [NEMap k a] -> NEMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' ((a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
forall k a.
Ord k =>
(a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
unionWith a -> a -> a
f) NEMap k a
m [NEMap k 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 ('Map'), in case the first map is
-- a subset of the second map.
--
-- > difference (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 3 "b"
difference
    :: Ord k
    => NEMap k a
    -> NEMap k b
    -> Map k a
difference :: NEMap k a -> NEMap k b -> Map k a
difference n1 :: NEMap k a
n1@(NEMap k
k1 a
v1 Map k a
m1) n2 :: NEMap k b
n2@(NEMap k
k2 b
_ Map k b
m2) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2 of
    -- k1 is not in n2, so cannot be deleted
    Ordering
LT -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k1 a
v1 (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.difference` NEMap k b -> Map k b
forall k a. NEMap k a -> Map k a
toMap NEMap k b
n2
    -- k2 deletes k1, and only k1
    Ordering
EQ -> Map k a
m1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.difference` Map k b
m2
    -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
    Ordering
GT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.difference` Map k b
m2
{-# INLINE difference #-}

-- | Same as 'difference'.
(\\)
    :: Ord k
    => NEMap k a
    -> NEMap k b
    -> Map k a
\\ :: NEMap k a -> NEMap k b -> Map k a
(\\) = NEMap k a -> NEMap k b -> Map k a
forall k a b. Ord k => NEMap k a -> NEMap k b -> Map k 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 ('Map'), 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.Map.singleton 3 "b:B"
differenceWith
    :: Ord k
    => (a -> b -> Maybe a)
    -> NEMap k a
    -> NEMap k b
    -> Map k a
differenceWith :: (a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
differenceWith a -> b -> Maybe a
f = (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
differenceWithKey ((a -> b -> Maybe a) -> k -> 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 ('Map'), 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.Map.singleton 3 "3:b|B"
differenceWithKey
    :: Ord k
    => (k -> a -> b -> Maybe a)
    -> NEMap k a
    -> NEMap k b
    -> Map k a
differenceWithKey :: (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
differenceWithKey k -> a -> b -> Maybe a
f n1 :: NEMap k a
n1@(NEMap k
k1 a
v1 Map k a
m1) n2 :: NEMap k b
n2@(NEMap k
k2 b
v2 Map k b
m2) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2 of
    -- k1 is not in n2, so cannot be deleted
    Ordering
LT -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k1 a
v1 (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
M.differenceWithKey k -> a -> b -> Maybe a
f Map k a
m1 (NEMap k b -> Map k b
forall k a. NEMap k a -> Map k a
toMap NEMap k b
n2)
    -- k2 deletes k1, and only k1
    Ordering
EQ -> ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
M.differenceWithKey k -> a -> b -> Maybe a
f Map k a
m1 Map k b
m2) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k1) (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> b -> Maybe a
f k
k1 a
v1 b
v2
    -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
    Ordering
GT -> (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
M.differenceWithKey k -> a -> b -> Maybe a
f (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n1) Map k 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 ('Map'), in case the two maps share no
-- keys in common.
--
-- > intersection (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 5 "a"
intersection
    :: Ord k
    => NEMap k a
    -> NEMap k b
    -> Map k a
intersection :: NEMap k a -> NEMap k b -> Map k a
intersection n1 :: NEMap k a
n1@(NEMap k
k1 a
v1 Map k a
m1) n2 :: NEMap k b
n2@(NEMap k
k2 b
_ Map k b
m2) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k1 k
k2 of
    -- k1 is not in n2
    Ordering
LT -> Map k a
m1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.intersection` NEMap k b -> Map k b
forall k a. NEMap k a -> Map k a
toMap NEMap k b
n2
    -- k1 and k2 are a part of the result
    Ordering
EQ -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k1 a
v1 (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.intersection` Map k b
m2
    -- k2 is not in n1
    Ordering
GT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n1 Map k a -> Map k b -> Map k a
forall k a b. Ord k => Map k a -> Map k b -> Map k a
`M.intersection` Map k b
m2
{-# INLINE intersection #-}

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

-- | /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) -> NEMap k a -> a
foldr1' :: (a -> a -> a) -> NEMap k a -> a
foldr1' a -> a -> a
f (NEMap k
_ a
v Map k a
m) = case Map k a -> Maybe (a, Map k a)
forall k a. Map k a -> Maybe (a, Map k a)
M.maxView Map k a
m of
    Maybe (a, Map k a)
Nothing      -> a
v
    Just (a
y, Map k a
m') -> let !z :: a
z = (a -> a -> a) -> a -> Map k a -> a
forall a b k. (a -> b -> b) -> b -> Map k a -> b
M.foldr' a -> a -> a
f a
y Map k 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) -> NEMap k a -> a
foldl1' :: (a -> a -> a) -> NEMap k a -> a
foldl1' a -> a -> a
f (NEMap k
_ a
v Map k a
m) = (a -> a -> a) -> a -> Map k a -> a
forall a b k. (a -> b -> a) -> a -> Map k b -> a
M.foldl' a -> a -> a
f a
v Map k a
m
{-# INLINE foldl1' #-}

-- | /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 :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldrWithKey :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldrWithKey k -> a -> b -> b
f b
z (NEMap k
k a
v Map k a
m) = k -> a -> b -> b
f k
k a
v (b -> b) -> (Map k a -> b) -> Map k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
M.foldrWithKey k -> a -> b -> b
f b
z (Map k a -> b) -> Map k a -> b
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINE foldrWithKey #-}

-- | /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' :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldrWithKey' :: (k -> a -> b -> b) -> b -> NEMap k a -> b
foldrWithKey' k -> a -> b -> b
f b
z (NEMap k
k a
v Map k a
m) = k -> a -> b -> b
f k
k a
v b
y
  where
    !y :: b
y = (k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
M.foldrWithKey k -> a -> b -> b
f b
z Map k 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 -> k -> b -> a) -> a -> NEMap k b -> a
foldlWithKey :: (a -> k -> b -> a) -> a -> NEMap k b -> a
foldlWithKey a -> k -> b -> a
f a
z (NEMap k
k b
v Map k b
m) = (a -> k -> b -> a) -> a -> Map k b -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
M.foldlWithKey a -> k -> b -> a
f (a -> k -> b -> a
f a
z k
k b
v) Map k b
m
{-# INLINE foldlWithKey #-}

-- | /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 -> k -> b -> a) -> a -> NEMap k b -> a
foldlWithKey' :: (a -> k -> b -> a) -> a -> NEMap k b -> a
foldlWithKey' a -> k -> b -> a
f a
z (NEMap k
k b
v Map k b
m) = (a -> k -> b -> a) -> a -> Map k b -> a
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
M.foldlWithKey' a -> k -> b -> a
f a
x Map k b
m
  where
    !x :: a
x = a -> k -> b -> a
f a
z k
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 :: NEMap k a -> NonEmpty k
keys :: NEMap k a -> NonEmpty k
keys (NEMap k
k a
_ Map k a
m) = k
k k -> [k] -> NonEmpty k
forall a. a -> [a] -> NonEmpty a
:| Map k a -> [k]
forall k a. Map k a -> [k]
M.keys Map k 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 :: NEMap k a -> NonEmpty (k, a)
assocs :: NEMap k a -> NonEmpty (k, a)
assocs = NEMap k a -> NonEmpty (k, a)
forall k a. NEMap k a -> NonEmpty (k, 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 :: NEMap k a -> NESet k
keysSet :: NEMap k a -> NESet k
keysSet (NEMap k
k a
_ Map k a
m) = k -> Set k -> NESet k
forall a. a -> Set a -> NESet a
NESet k
k (Map k a -> Set k
forall k a. Map k a -> Set k
M.keysSet Map k a
m)
{-# INLINE keysSet #-}

-- | /O(n)/. Map 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 :: (k -> a -> b) -> NEMap k a -> NEMap k b
mapWithKey :: (k -> a -> b) -> NEMap k a -> NEMap k b
mapWithKey k -> a -> b
f (NEMap k
k a
v Map k a
m) = k -> b -> Map k b -> NEMap k b
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k (k -> a -> b
f k
k a
v) ((k -> a -> b) -> Map k a -> Map k b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
M.mapWithKey k -> a -> b
f Map k 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)/. 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 :: NEMap k a -> NonEmpty (k, a)
toAscList :: NEMap k a -> NonEmpty (k, a)
toAscList = NEMap k a -> NonEmpty (k, a)
forall k a. NEMap k a -> NonEmpty (k, 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 :: NEMap k a -> NonEmpty (k, a)
toDescList :: NEMap k a -> NonEmpty (k, a)
toDescList (NEMap k
k0 a
v0 Map k a
m) = (NonEmpty (k, a) -> k -> a -> NonEmpty (k, a))
-> NonEmpty (k, a) -> Map k a -> NonEmpty (k, a)
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
M.foldlWithKey' NonEmpty (k, a) -> k -> a -> NonEmpty (k, a)
forall a b. NonEmpty (a, b) -> a -> b -> NonEmpty (a, b)
go ((k
k0, a
v0) (k, a) -> [(k, a)] -> NonEmpty (k, a)
forall a. a -> [a] -> NonEmpty a
:| []) Map k 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(log n)/. Convert a 'Map' into an 'NEMap' 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
-- > insertMap 4 "c" Data.Map.empty == singleton 4 "c"
insertMap :: Ord k => k -> a -> Map k a -> NEMap k a
insertMap :: k -> a -> Map k a -> NEMap k a
insertMap k
k a
v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
withNonEmpty (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v) (k -> a -> NEMap k a -> NEMap k a
forall k a. Ord k => k -> a -> NEMap k a -> NEMap k a
insert k
k a
v)
{-# INLINE insertMap #-}

-- | /O(log n)/. Convert a 'Map' into an 'NEMap' 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")])
-- > insertMapWith (++) 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])
insertMapWith
    :: Ord k
    => (a -> a -> a)
    -> k
    -> a
    -> Map k a
    -> NEMap k a
insertMapWith :: (a -> a -> a) -> k -> a -> Map k a -> NEMap k a
insertMapWith a -> a -> a
f k
k a
v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
withNonEmpty (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v) ((a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
forall k a.
Ord k =>
(a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertWith a -> a -> a
f k
k a
v)
{-# INLINE insertMapWith #-}

-- | /O(log n)/. Convert a 'Map' into an 'NEMap' 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")])
-- > insertWithKey f 7 "xxx" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])
-- > insertWithKey f 5 "xxx" Data.Map.empty                         == singleton 5 "xxx"
insertMapWithKey
    :: Ord k
    => (k -> a -> a -> a)
    -> k
    -> a
    -> Map k a
    -> NEMap k a
insertMapWithKey :: (k -> a -> a -> a) -> k -> a -> Map k a -> NEMap k a
insertMapWithKey k -> a -> a -> a
f k
k a
v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
withNonEmpty (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v) ((k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertWithKey k -> a -> a -> a
f k
k a
v)
{-# INLINE insertMapWithKey #-}

-- | /O(1)/ Convert a 'Map' into an 'NEMap' 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.Map.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")])
-- > valid (insertMapMin 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True
-- > valid (insertMapMin 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
-- > valid (insertMapMin 3 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
insertMapMin
    :: k
    -> a
    -> Map k a
    -> NEMap k a
insertMapMin :: k -> a -> Map k a -> NEMap k a
insertMapMin = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap
{-# INLINE insertMapMin #-}

-- | /O(log n)/ Convert a 'Map' into an 'NEMap' 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./
--
-- While this has the same asymptotics as 'insertMap', it saves a constant
-- factor for key comparison (so may be helpful if comparison is expensive)
-- and also does not require an 'Ord' instance for the key type.
--
-- > insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")])
-- > valid (insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True
-- > valid (insertMap 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
-- > valid (insertMap 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
insertMapMax
    :: k
    -> a
    -> Map k a
    -> NEMap k a
insertMapMax :: k -> a -> Map k a -> NEMap k a
insertMapMax k
k a
v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
withNonEmpty (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v) NEMap k a -> NEMap k a
go
  where
    go :: NEMap k a -> NEMap k a
go (NEMap k
k0 a
v0 Map k a
m0) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v0 (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMaxMap k
k a
v (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k a
m0
{-# INLINE insertMapMax #-}


-- | /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 'Map'.
--
-- > 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
    :: Ord k
    => k
    -> a
    -> NEMap k a
    -> NEMap k a
insert :: k -> a -> NEMap k a -> NEMap k a
insert k
k a
v n :: NEMap k a
n@(NEMap k
k0 a
v0 Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  a
v  (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap        (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  a
v  Map k a
m
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v0 (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert k
k a
v (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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 'Map'.
--
-- > 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
    :: Ord k
    => (k -> a -> a -> a)
    -> k
    -> a
    -> NEMap k a
    -> NEMap k a
insertWithKey :: (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertWithKey k -> a -> a -> a
f k
k a
v n :: NEMap k a
n@(NEMap k
k0 a
v0 Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  a
v          (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap               (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  (k -> a -> a -> a
f k
k a
v a
v0) Map k a
m
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v0         (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWithKey k -> a -> a -> a
f k
k a
v Map k 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
    :: Ord k
    => (k -> a -> a -> a)
    -> k
    -> a
    -> NEMap k a
    -> (Maybe a, NEMap k a)
insertLookupWithKey :: (k -> a -> a -> a) -> k -> a -> NEMap k a -> (Maybe a, NEMap k a)
insertLookupWithKey k -> a -> a -> a
f k
k a
v n :: NEMap k a
n@(NEMap k
k0 a
v0 Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> (Maybe a
forall a. Maybe a
Nothing, k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  a
v (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n )
    Ordering
EQ -> (a -> Maybe a
forall a. a -> Maybe a
Just a
v , k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  (k -> a -> a -> a
f k
k a
v a
v0)  Map k a
m )
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v0 (Map k a -> NEMap k a)
-> (Maybe a, Map k a) -> (Maybe a, NEMap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
M.insertLookupWithKey k -> a -> a -> a
f k
k a
v Map k a
m
{-# INLINE insertLookupWithKey #-}

-- | /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
    :: Ord k
    => (a -> a -> a)
    -> NonEmpty (k, a)
    -> NEMap k a
fromListWith :: (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWith a -> a -> a
f = (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWithKey ((a -> a -> a) -> k -> 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
    :: Ord k
    => (k -> a -> a -> a)
    -> NonEmpty (k, a)
    -> NEMap k a
fromListWithKey :: (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWithKey k -> a -> a -> a
f ((k
k0, a
v0) :| [(k, a)]
xs) = (NEMap k a -> (k, a) -> NEMap k a)
-> NEMap k a -> [(k, a)] -> NEMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' NEMap k a -> (k, a) -> NEMap k a
go (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k0 a
v0) [(k, a)]
xs
  where
    go :: NEMap k a -> (k, a) -> NEMap k a
go NEMap k a
m (k
k, a
v) = (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
insertWithKey k -> a -> a -> a
f k
k a
v NEMap k 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
    :: Eq k
    => NonEmpty (k, a)
    -> NEMap k a
fromAscList :: NonEmpty (k, a) -> NEMap k a
fromAscList = NonEmpty (k, a) -> NEMap k a
forall k a. NonEmpty (k, a) -> NEMap k a
fromDistinctAscList (NonEmpty (k, a) -> NEMap k a)
-> (NonEmpty (k, a) -> NonEmpty (k, a))
-> NonEmpty (k, a)
-> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty (k, a) -> NonEmpty (k, a)
forall a b. Eq a => NonEmpty (a, b) -> NonEmpty (a, 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
    :: Eq k
    => (a -> a -> a)
    -> NonEmpty (k, a)
    -> NEMap k a
fromAscListWith :: (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromAscListWith a -> a -> a
f = (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromAscListWithKey ((a -> a -> a) -> k -> 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
    :: Eq k
    => (k -> a -> a -> a)
    -> NonEmpty (k, a)
    -> NEMap k a
fromAscListWithKey :: (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromAscListWithKey k -> a -> a -> a
f = NonEmpty (k, a) -> NEMap k a
forall k a. NonEmpty (k, a) -> NEMap k a
fromDistinctAscList (NonEmpty (k, a) -> NEMap k a)
-> (NonEmpty (k, a) -> NonEmpty (k, a))
-> NonEmpty (k, a)
-> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a -> a) -> NonEmpty (k, a) -> NonEmpty (k, a)
forall a b.
Eq a =>
(a -> b -> b -> b) -> NonEmpty (a, b) -> NonEmpty (a, b)
combineEqWith k -> 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 (k, a) -> NEMap k a
fromDistinctAscList :: NonEmpty (k, a) -> NEMap k a
fromDistinctAscList ((k
k, a
v) :| [(k, a)]
xs) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k a
v
                                   (Map k a -> NEMap k a)
-> ([(k, a)] -> Map k a) -> [(k, a)] -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
M.fromDistinctAscList
                                   ([(k, a)] -> NEMap k a) -> [(k, a)] -> NEMap k a
forall a b. (a -> b) -> a -> b
$ [(k, a)]
xs
{-# INLINE fromDistinctAscList #-}

-- | /O(n)/. Build a map from a descending non-empty list in linear time.
-- /The precondition (input list is descending) is not checked./
--
-- > fromDescList ((5,"a") :| [(3,"b")])          == fromList ((3, "b") :| [(5, "a")])
-- > fromDescList ((5,"a") :| [(5,"b"), (3,"b")]) == fromList ((3, "b") :| [(5, "b")])
-- > valid (fromDescList ((5,"a") :| [(5,"b"), (3,"b")])) == True
-- > valid (fromDescList ((5,"a") :| [(3,"b"), (5,"b")])) == False
fromDescList
    :: Eq k
    => NonEmpty (k, a)
    -> NEMap k a
fromDescList :: NonEmpty (k, a) -> NEMap k a
fromDescList = NonEmpty (k, a) -> NEMap k a
forall k a. NonEmpty (k, a) -> NEMap k a
fromDistinctDescList (NonEmpty (k, a) -> NEMap k a)
-> (NonEmpty (k, a) -> NonEmpty (k, a))
-> NonEmpty (k, a)
-> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty (k, a) -> NonEmpty (k, a)
forall a b. Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
combineEq
{-# INLINE fromDescList #-}

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

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

-- | /O(n)/. Build a map from a descending list of distinct elements in linear time.
-- /The precondition is not checked./
--
-- > fromDistinctDescList ((5,"a") :| [(3,"b")]) == fromList ((3, "b") :| [(5, "a")])
-- > valid (fromDistinctDescList ((5,"a") :| [(3,"b")]))          == True
-- > valid (fromDistinctDescList ((5,"a") :| [(5,"b"), (3,"b")])) == False
--
-- @since 0.5.8
fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a
fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a
fromDistinctDescList ((k
k, a
v) :| [(k, a)]
xs) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMax k
k a
v
                                    (Map k a -> NEMap k a)
-> ([(k, a)] -> Map k a) -> [(k, a)] -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
M.fromDistinctDescList
                                    ([(k, a)] -> NEMap k a) -> [(k, a)] -> NEMap k a
forall a b. (a -> b) -> a -> b
$ [(k, a)]
xs
{-# INLINE fromDistinctDescList #-}

-- | /O(log n)/. Delete a key and its value from the non-empty map.
-- A potentially empty map ('Map') is returned, since this might delete the
-- last item in the 'NEMap'.  When the key is not a member of the map, is
-- equivalent to 'toMap'.
--
-- > delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
-- > delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.Singleton [(3, "b"), (5, "a")]
delete :: Ord k => k -> NEMap k a -> Map k a
delete :: k -> NEMap k a -> Map k a
delete k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n
    Ordering
EQ -> Map k a
m
    Ordering
GT -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
M.delete k
k (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k 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
    :: Ord k
    => (a -> a)
    -> k
    -> NEMap k a
    -> NEMap k a
adjust :: (a -> a) -> k -> NEMap k a -> NEMap k a
adjust a -> a
f = (k -> a -> a) -> k -> NEMap k a -> NEMap k a
forall k a. Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k a
adjustWithKey ((a -> a) -> k -> 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
    :: Ord k
    => (k -> a -> a)
    -> k
    -> NEMap k a
    -> NEMap k a
adjustWithKey :: (k -> a -> a) -> k -> NEMap k a -> NEMap k a
adjustWithKey k -> a -> a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> NEMap k a
n
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 (k -> a -> a
f k
k0 a
v) Map k a
m
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> a) -> k -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
M.adjustWithKey k -> a -> a
f k
k (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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 ('Map'), because we can't know ahead of
-- time if the function returns 'Nothing' and deletes the final item in the
-- 'NEMap'.
--
-- > let f x = if x == "a" then Just "new a" else Nothing
-- > update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "new a")]
-- > update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")]
-- > update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
update
    :: Ord k
    => (a -> Maybe a)
    -> k
    -> NEMap k a
    -> Map k a
update :: (a -> Maybe a) -> k -> NEMap k a -> Map k a
update a -> Maybe a
f = (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
forall k a.
Ord k =>
(k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
updateWithKey ((a -> Maybe a) -> k -> 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 ('Map'), because we can't know ahead of
-- time if the function returns 'Nothing' and deletes the final item in the
-- 'NEMap'.
--
-- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
-- > updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "5:new a")]
-- > updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")]
-- > updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
updateWithKey
    :: Ord k
    => (k -> a -> Maybe a)
    -> k
    -> NEMap k a
    -> Map k a
updateWithKey :: (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
updateWithKey k -> a -> Maybe a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n
    Ordering
EQ -> Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0) Map k a
m) (Maybe a -> Map k a) -> (a -> Maybe a) -> a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> Maybe a
f k
k0 (a -> Map k a) -> a -> Map k a
forall a b. (a -> b) -> a -> b
$ a
v
    Ordering
GT -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> k -> Map k a -> Map k a
forall k a. Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
M.updateWithKey k -> a -> Maybe a
f k
k   (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINE updateWithKey #-}

-- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
-- The function returns changed value, if it is updated.
-- Returns the original key value if the map entry is deleted.
--
-- Returns a potentially empty map ('Map') 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.Map.fromList ((3, "b") :| [(5, "5:new a")]))
-- > updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  Data.Map.fromList ((3, "b") :| [(5, "a")]))
-- > updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.Map.singleton 5 "a")
updateLookupWithKey
    :: Ord k
    => (k -> a -> Maybe a)
    -> k
    -> NEMap k a
    -> (Maybe a, Map k a)
updateLookupWithKey :: (k -> a -> Maybe a) -> k -> NEMap k a -> (Maybe a, Map k a)
updateLookupWithKey k -> a -> Maybe a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> (Maybe a
forall a. Maybe a
Nothing, NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n)
    Ordering
EQ -> let u :: Maybe a
u = k -> a -> Maybe a
f k
k0 a
v
          in  (Maybe a
u Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> a -> Maybe a
forall a. a -> Maybe a
Just a
v, Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0) Map k a
m) Maybe a
u)
    Ordering
GT -> (Map k a -> Map k a) -> (Maybe a, Map k a) -> (Maybe a, Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v) ((Maybe a, Map k a) -> (Maybe a, Map k a))
-> (Map k a -> (Maybe a, Map k a)) -> Map k a -> (Maybe a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
forall k a.
Ord k =>
(k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
M.updateLookupWithKey k -> a -> Maybe a
f k
k (Map k a -> (Maybe a, Map k a)) -> Map k a -> (Maybe a, Map k a)
forall a b. (a -> b) -> a -> b
$ Map k 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 'Map'. In short : @Data.Map.lookup k ('alter'
-- f k m) = f ('lookup' k m)@.
--
-- Returns a potentially empty map ('Map'), because we can't know ahead of
-- time if the function returns 'Nothing' and deletes the final item in the
-- 'NEMap'.
--
-- See 'alterF'' for a version that disallows deletion, and so therefore
-- can return 'NEMap'.
--
-- > let f _ = Nothing
-- > alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")]
-- > alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
-- >
-- > let f _ = Just "c"
-- > alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a"), (7, "c")]
-- > alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "c")]
alter
    :: Ord k
    => (Maybe a -> Maybe a)
    -> k
    -> NEMap k a
    -> Map k a
alter :: (Maybe a -> Maybe a) -> k -> NEMap k a -> Map k a
alter Maybe a -> Maybe a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k ) (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing
    Ordering
EQ -> ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m      ) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0) (Maybe a -> Map k a) -> Maybe a -> Map k 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 -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
M.alter Maybe a -> Maybe a
f k
k (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k 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 'Map'.  In short: @Data.Map.lookup
-- k \<$\> 'alterF' f k m = f ('lookup' k m)@.
--
-- Example:
--
-- @
-- interactiveAlter :: Int -> NEMap Int String -> IO (Map 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.Map.alterF@ for 'Map', '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 'Map' instead of an 'NEMap' (because the function might delete
-- the final item in the 'NEMap').  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 'NEMap' 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.Map.alterF@ for 'Map', '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
    :: (Ord k, Functor f)
    => (Maybe a -> f (Maybe a))
    -> k
    -> NEMap k a
    -> f (Map k a)
alterF :: (Maybe a -> f (Maybe a)) -> k -> NEMap k a -> f (Map k a)
alterF Maybe a -> f (Maybe a)
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k ) (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k 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 -> ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m      ) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0) (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k 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 -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v (Map k a -> Map k a) -> f (Map k a) -> f (Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
forall (f :: * -> *) k a.
(Functor f, Ord k) =>
(Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
M.alterF Maybe a -> f (Maybe a)
f k
k Map k 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 Map.
alter'
    :: Ord k
    => (Maybe a -> a)
    -> k
    -> NEMap k a
    -> NEMap k a
alter' :: (Maybe a -> a) -> k -> NEMap k a -> NEMap k a
alter' Maybe a -> a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k  (Maybe a -> a
f Maybe a
forall a. Maybe a
Nothing) (Map k a -> NEMap k a)
-> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap      (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ NEMap k a
n
    Ordering
EQ -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 (Maybe a -> a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
v))             (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
    Ordering
GT -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k 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) k
k (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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 Map.
--
-- Like @Data.Map.alterF@ for 'Map', 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.Map".  @Data.Map.alterF@ will actually
-- /maintain/ the original key in the map when used with 'Identity';
-- however, @Data.Map.insertWith@ will /replace/ the orginal key in the
-- map.  The rewrite rule for 'alterF'' has chosen to be faithful to
-- @Data.Map.insertWith@, and /not/ @Data.Map.alterF@, for the sake of
-- a cleaner implementation.
alterF'
    :: (Ord k, Functor f)
    => (Maybe a -> f a)
    -> k
    -> NEMap k a
    -> f (NEMap k a)
alterF' :: (Maybe a -> f a) -> k -> NEMap k a -> f (NEMap k a)
alterF' Maybe a -> f a
f k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> (a -> Map k a -> NEMap k a) -> Map k a -> a -> NEMap k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k ) (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n) (a -> NEMap k a) -> f a -> f (NEMap k 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 -> Map k a -> NEMap k a) -> Map k a -> a -> NEMap k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0) Map k a
m         (a -> NEMap k a) -> f a -> f (NEMap k 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 -> k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v (Map k a -> NEMap k a) -> f (Map k a) -> f (NEMap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
forall (f :: * -> *) k a.
(Functor f, Ord k) =>
(Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k 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) k
k Map k 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(n)/. Traverse keys\/values and collect the 'Just' results.
--
-- Returns a potentially empty map ('Map'), our function might return
-- 'Nothing' on every item in the 'NEMap'.
--
-- /Use 'traverseMaybeWithKey1'/ whenever possible (if your 'Applicative'
-- also has 'Apply' instance).  This version is provided only for types
-- that do not have 'Apply' instance, since 'Apply' is not at the moment
-- (and might not ever be) an official superclass of 'Applicative'.
traverseMaybeWithKey
    :: Applicative t
    => (k -> a -> t (Maybe b))
    -> NEMap k a
    -> t (Map k b)
traverseMaybeWithKey :: (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
traverseMaybeWithKey k -> a -> t (Maybe b)
f (NEMap k
k0 a
v Map k a
m0) =
    Maybe b -> Map k b -> Map k b
forall a. Maybe a -> Map k a -> Map k a
combine (Maybe b -> Map k b -> Map k b)
-> t (Maybe b) -> t (Map k b -> Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> t (Maybe b)
f k
k0 a
v t (Map k b -> Map k b) -> t (Map k b) -> t (Map k b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (k -> a -> t (Maybe b)) -> Map k a -> t (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
M.traverseMaybeWithKey k -> a -> t (Maybe b)
f Map k a
m0
  where
    combine :: Maybe a -> Map k a -> Map k a
combine Maybe a
Nothing   = Map k a -> Map k a
forall a. a -> a
id
    combine (Just a
v') = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v'
{-# INLINE traverseMaybeWithKey #-}

-- | /O(n)/. Traverse keys\/values and collect the 'Just' results.
--
-- Returns a potentially empty map ('Map'), our function might return
-- 'Nothing' on every item in the 'NEMap'.
--
-- Is more general than 'traverseWithKey', since works with all 'Apply',
-- and not just 'Applicative'.

-- TODO: benchmark against M.maxView version
traverseMaybeWithKey1
    :: Apply t
    => (k -> a -> t (Maybe b))
    -> NEMap k a
    -> t (Map k b)
traverseMaybeWithKey1 :: (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
traverseMaybeWithKey1 k -> a -> t (Maybe b)
f (NEMap k
k0 a
v Map k a
m0) = case MaybeApply t (Map k b) -> Either (t (Map k b)) (Map k b)
forall (f :: * -> *) a. MaybeApply f a -> Either (f a) a
runMaybeApply MaybeApply t (Map k b)
m1 of
    Left  t (Map k b)
m2 -> Maybe b -> Map k b -> Map k b
forall a. Maybe a -> Map k a -> Map k a
combine (Maybe b -> Map k b -> Map k b)
-> t (Maybe b) -> t (Map k b -> Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> t (Maybe b)
f k
k0 a
v t (Map k b -> Map k b) -> t (Map k b) -> t (Map k b)
forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
<.> t (Map k b)
m2
    Right Map k b
m2 -> (Maybe b -> Map k b -> Map k b
forall a. Maybe a -> Map k a -> Map k a
`combine` Map k b
m2) (Maybe b -> Map k b) -> t (Maybe b) -> t (Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> t (Maybe b)
f k
k0 a
v
  where
    m1 :: MaybeApply t (Map k b)
m1 = (k -> a -> MaybeApply t (Maybe b))
-> Map k a -> MaybeApply t (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
M.traverseMaybeWithKey (\k
k -> Either (t (Maybe b)) (Maybe b) -> MaybeApply t (Maybe b)
forall (f :: * -> *) a. Either (f a) a -> MaybeApply f a
MaybeApply (Either (t (Maybe b)) (Maybe b) -> MaybeApply t (Maybe b))
-> (a -> Either (t (Maybe b)) (Maybe b))
-> a
-> MaybeApply t (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t (Maybe b) -> Either (t (Maybe b)) (Maybe b)
forall a b. a -> Either a b
Left (t (Maybe b) -> Either (t (Maybe b)) (Maybe b))
-> (a -> t (Maybe b)) -> a -> Either (t (Maybe b)) (Maybe b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> a -> t (Maybe b)
f k
k) Map k a
m0
    combine :: Maybe a -> Map k a -> Map k a
combine Maybe a
Nothing   = Map k a -> Map k a
forall a. a -> a
id
    combine (Just a
v') = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k0 a
v'
{-# INLINE traverseMaybeWithKey1 #-}

-- | /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
    -> NEMap k b
    -> (a, NEMap k c)
mapAccum :: (a -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccum a -> b -> (a, c)
f = (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccumWithKey (\a
x k
_ -> 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 -> k -> b -> (a, c))
    -> a
    -> NEMap k b
    -> (a, NEMap k c)
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccumWithKey a -> k -> b -> (a, c)
f a
z0 (NEMap k
k b
v Map k b
m) = (a
z2, k -> c -> Map k c -> NEMap k c
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k c
v' Map k c
m')
  where
    ~(a
z1, c
v') = a -> k -> b -> (a, c)
f a
z0 k
k b
v
    ~(a
z2, Map k c
m') = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccumWithKey a -> k -> b -> (a, c)
f a
z1 Map k b
m
{-# INLINE mapAccumWithKey #-}

-- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating
-- argument through the map in descending order of keys.
mapAccumRWithKey
    :: (a -> k -> b -> (a, c))
    -> a
    -> NEMap k b
    -> (a, NEMap k c)
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
mapAccumRWithKey a -> k -> b -> (a, c)
f a
z0 (NEMap k
k b
v Map k b
m) = (a
z2, k -> c -> Map k c -> NEMap k c
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k c
v' Map k c
m')
  where
    ~(a
z1, Map k c
m') = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccumRWithKey a -> k -> b -> (a, c)
f a
z0 Map k b
m
    ~(a
z2, c
v') = a -> k -> b -> (a, c)
f a
z1 k
k b
v
{-# INLINE mapAccumRWithKey #-}
-- TODO: what other situations can we take advantage of lazy tuple pattern
-- matching?

-- | /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
    :: Ord k2
    => (k1 -> k2)
    -> NEMap k1 a
    -> NEMap k2 a
mapKeys :: (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
mapKeys k1 -> k2
f (NEMap k1
k0 a
v0 Map k1 a
m) = (a -> a -> a) -> NonEmpty (k2, a) -> NEMap k2 a
forall k a. Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWith a -> a -> a
forall a b. a -> b -> a
const
                          (NonEmpty (k2, a) -> NEMap k2 a)
-> (Map k1 a -> NonEmpty (k2, a)) -> Map k1 a -> NEMap k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1 -> k2
f k1
k0, a
v0) (k2, a) -> [(k2, a)] -> NonEmpty (k2, a)
forall a. a -> [a] -> NonEmpty a
:|)
                          ([(k2, a)] -> NonEmpty (k2, a))
-> (Map k1 a -> [(k2, a)]) -> Map k1 a -> NonEmpty (k2, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k1 -> a -> [(k2, a)] -> [(k2, a)])
-> [(k2, a)] -> Map k1 a -> [(k2, a)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
M.foldrWithKey (\k1
k a
v [(k2, a)]
kvs -> (k1 -> k2
f k1
k, a
v) (k2, a) -> [(k2, a)] -> [(k2, a)]
forall a. a -> [a] -> [a]
: [(k2, a)]
kvs) []
                          (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
forall a b. (a -> b) -> a -> b
$ Map k1 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
    :: Ord k2
    => (a -> a -> a)
    -> (k1 -> k2)
    -> NEMap k1 a
    -> NEMap k2 a
mapKeysWith :: (a -> a -> a) -> (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
mapKeysWith a -> a -> a
c k1 -> k2
f (NEMap k1
k0 a
v0 Map k1 a
m) = (a -> a -> a) -> NonEmpty (k2, a) -> NEMap k2 a
forall k a. Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
fromListWith a -> a -> a
c
                                (NonEmpty (k2, a) -> NEMap k2 a)
-> (Map k1 a -> NonEmpty (k2, a)) -> Map k1 a -> NEMap k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1 -> k2
f k1
k0, a
v0) (k2, a) -> [(k2, a)] -> NonEmpty (k2, a)
forall a. a -> [a] -> NonEmpty a
:|)
                                ([(k2, a)] -> NonEmpty (k2, a))
-> (Map k1 a -> [(k2, a)]) -> Map k1 a -> NonEmpty (k2, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k1 -> a -> [(k2, a)] -> [(k2, a)])
-> [(k2, a)] -> Map k1 a -> [(k2, a)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
M.foldrWithKey (\k1
k a
v [(k2, a)]
kvs -> (k1 -> k2
f k1
k, a
v) (k2, a) -> [(k2, a)] -> [(k2, a)]
forall a. a -> [a] -> [a]
: [(k2, a)]
kvs) []
                                (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
forall a b. (a -> b) -> a -> b
$ Map k1 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
    :: (k1 -> k2)
    -> NEMap k1 a
    -> NEMap k2 a
mapKeysMonotonic :: (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
mapKeysMonotonic k1 -> k2
f (NEMap k1
k a
v Map k1 a
m) = k2 -> a -> Map k2 a -> NEMap k2 a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap (k1 -> k2
f k1
k) a
v
                                 (Map k2 a -> NEMap k2 a)
-> (Map k1 a -> Map k2 a) -> Map k1 a -> NEMap k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k1 -> k2) -> Map k1 a -> Map k2 a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic k1 -> k2
f
                                 (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
forall a b. (a -> b) -> a -> b
$ Map k1 a
m
{-# INLINE mapKeysMonotonic #-}

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

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

-- | /O(m*log(n\/m + 1)), m <= n/. Restrict an 'NEMap' 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
    :: Ord k
    => NEMap k a
    -> Set k
    -> Map k a
restrictKeys :: NEMap k a -> Set k -> Map k a
restrictKeys n :: NEMap k a
n@(NEMap k
k a
v Map k a
m) Set k
xs = case Set k -> Maybe (k, Set k)
forall a. Set a -> Maybe (a, Set a)
S.minView Set k
xs of
    Maybe (k, Set k)
Nothing      -> Map k a
forall k a. Map k a
M.empty
    Just (k
y, Set k
ys) -> case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
y of
      -- k is not in xs
      Ordering
LT -> Map k a
m Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.restrictKeys` Set k
xs
      -- k and y are a part of the result
      Ordering
EQ -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.restrictKeys` Set k
ys
      -- y is not in m
      Ordering
GT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.restrictKeys` Set k
ys
{-# INLINE restrictKeys #-}

-- | /O(m*log(n\/m + 1)), m <= n/. Remove all keys in a 'Data.Set.Set' from
-- an 'NEMap'.
--
-- @
-- m \`withoutKeys\` s = 'filterWithKey' (\k _ -> k ``Set.notMember`` s) m
-- m \`withoutKeys\` s = m ``difference`` 'fromSet' (const ()) s
-- @
withoutKeys
    :: Ord k
    => NEMap k a
    -> Set k
    -> Map k a
withoutKeys :: NEMap k a -> Set k -> Map k a
withoutKeys n :: NEMap k a
n@(NEMap k
k a
v Map k a
m) Set k
xs = case Set k -> Maybe (k, Set k)
forall a. Set a -> Maybe (a, Set a)
S.minView Set k
xs of
    Maybe (k, Set k)
Nothing      -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n
    Just (k
y, Set k
ys) -> case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
y of
      -- k is not in xs, so cannot be deleted
      Ordering
LT -> k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.withoutKeys` Set k
xs
      -- y deletes k, and only k
      Ordering
EQ -> Map k a
m Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.withoutKeys` Set k
ys
      -- y is not in n, so cannot delete anything, so we can just difference n and ys
      Ordering
GT -> NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n Map k a -> Set k -> Map k a
forall k a. Ord k => Map k a -> Set k -> Map k a
`M.withoutKeys` Set k
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)
    -> NEMap k a
    -> These (NEMap k a) (NEMap k a)
partition :: (a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
partition a -> Bool
f = (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall k a.
(k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
partitionWithKey ((a -> Bool) -> k -> 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
    :: (k -> a -> Bool)
    -> NEMap k a
    -> These (NEMap k a) (NEMap k a)
partitionWithKey :: (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
partitionWithKey k -> a -> Bool
f n :: NEMap k a
n@(NEMap k
k a
v Map k a
m0) = case (Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m1, Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m2) of
    (Maybe (NEMap k a)
Nothing, Maybe (NEMap k a)
Nothing)
      | k -> a -> Bool
f k
k a
v     -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  NEMap k a
n
      | Bool
otherwise -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That                        NEMap k a
n
    (Just NEMap k a
n1, Maybe (NEMap k a)
Nothing)
      | k -> a -> Bool
f k
k a
v     -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  NEMap k a
n
      | Bool
otherwise -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These NEMap k a
n1                    (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v)
    (Maybe (NEMap k a)
Nothing, Just NEMap k a
n2)
      | k -> a -> Bool
f k
k a
v     -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v)       NEMap k a
n2
      | Bool
otherwise -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That                        NEMap k a
n
    (Just NEMap k a
n1, Just NEMap k a
n2)
      | k -> a -> Bool
f k
k a
v     -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k a
v Map k a
m1) NEMap k a
n2
      | Bool
otherwise -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These NEMap k a
n1                    (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k a
v Map k a
m2)
  where
    (Map k a
m1, Map k a
m2) = (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
M.partitionWithKey k -> a -> Bool
f Map k a
m0
{-# INLINABLE partitionWithKey #-}

-- | /O(log n)/. Take while a predicate on the keys holds.
-- The user is responsible for ensuring that for all keys @j@ and @k@ in the map,
-- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
--
-- Returns a potentially empty map ('Map'), because the predicate might
-- fail on the first input.
--
-- @
-- takeWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.takeWhile (p . fst) . Data.Foldable.toList
-- takeWhileAntitone p = 'filterWithKey' (\k _ -> p k)
-- @
takeWhileAntitone
    :: (k -> Bool)
    -> NEMap k a
    -> Map k a
takeWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a
takeWhileAntitone k -> Bool
f (NEMap k
k a
v Map k a
m)
    | k -> Bool
f k
k       = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> Bool) -> Map k a -> Map k a
forall k a. (k -> Bool) -> Map k a -> Map k a
M.takeWhileAntitone k -> Bool
f (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
    | Bool
otherwise = Map k a
forall k a. Map k a
M.empty
{-# INLINE takeWhileAntitone #-}

-- | /O(log n)/. Drop while a predicate on the keys holds.
-- The user is responsible for ensuring that for all keys @j@ and @k@ in the map,
-- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
--
-- @
-- dropWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.dropWhile (p . fst) . Data.Foldable.toList
-- dropWhileAntitone p = 'filterWithKey' (\k -> not (p k))
-- @
dropWhileAntitone
    :: (k -> Bool)
    -> NEMap k a
    -> Map k a
dropWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a
dropWhileAntitone k -> Bool
f n :: NEMap k a
n@(NEMap k
k a
_ Map k a
m)
    | k -> Bool
f k
k       = (k -> Bool) -> Map k a -> Map k a
forall k a. (k -> Bool) -> Map k a -> Map k a
M.dropWhileAntitone k -> Bool
f Map k a
m
    | Bool
otherwise = NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n
{-# INLINE dropWhileAntitone #-}

-- | /O(log n)/. Divide a map at the point where a predicate on the keys stops holding.
-- The user is responsible for ensuring that for all keys @j@ and @k@ in the map,
-- @j \< k ==\> p j \>= p k@.
--
-- Returns a 'These' with potentially two non-empty maps:
--
-- *   @'This' n1@ means that the predicate never failed for any item,
--     returning the original map.
-- *   @'That' n2@ means that the predicate failed for the first item,
--     returning the original map.
-- *   @'These' n1 n2@ gives @n1@ (the map up to the point where the
--     predicate on the keys stops holding) and @n2@ (the map starting from
--     the point where the predicate stops holding)
--
-- @
-- spanAntitone p xs = partitionWithKey (\k _ -> p k) xs
-- @
--
-- Note: if @p@ is not actually antitone, then @spanAntitone@ will split the map
-- at some /unspecified/ point where the predicate switches from holding to not
-- holding (where the predicate is seen to hold before the first key and to fail
-- after the last key).
spanAntitone
    :: (k -> Bool)
    -> NEMap k a
    -> These (NEMap k a) (NEMap k a)
spanAntitone :: (k -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
spanAntitone k -> Bool
f n :: NEMap k a
n@(NEMap k
k a
v Map k a
m0)
    | k -> Bool
f k
k       = case (Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m1, Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m2) of
        (Maybe (NEMap k a)
Nothing, Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  NEMap k a
n
        (Just NEMap k a
_ , Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  NEMap k a
n
        (Maybe (NEMap k a)
Nothing, Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v)       NEMap k a
n2
        (Just NEMap k a
_ , Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k a
v Map k a
m1) NEMap k a
n2
    | Bool
otherwise = NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That NEMap k a
n
  where
    (Map k a
m1, Map k a
m2) = (k -> Bool) -> Map k a -> (Map k a, Map k a)
forall k a. (k -> Bool) -> Map k a -> (Map k a, Map k a)
M.spanAntitone k -> Bool
f Map k a
m0
{-# INLINABLE spanAntitone #-}

-- | /O(n)/. Map values and collect the 'Just' results.
--
-- Returns a potentially empty map ('Map'), because the function could
-- potentially return 'Nothing' on all items in the 'NEMap'.
--
-- > let f x = if x == "a" then Just "new a" else Nothing
-- > mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "new a"
mapMaybe
    :: (a -> Maybe b)
    -> NEMap k a
    -> Map k b
mapMaybe :: (a -> Maybe b) -> NEMap k a -> Map k b
mapMaybe a -> Maybe b
f = (k -> a -> Maybe b) -> NEMap k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> NEMap k a -> Map k b
mapMaybeWithKey ((a -> Maybe b) -> k -> 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 ('Map'), because the function could
-- potentially return 'Nothing' on all items in the 'NEMap'.
--
-- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- > mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "key : 3"
mapMaybeWithKey
    :: (k -> a -> Maybe b)
    -> NEMap k a
    -> Map k b
mapMaybeWithKey :: (k -> a -> Maybe b) -> NEMap k a -> Map k b
mapMaybeWithKey k -> a -> Maybe b
f (NEMap k
k a
v Map k a
m) = ((Map k b -> Map k b) -> Map k b -> Map k b
forall a b. (a -> b) -> a -> b
$ (k -> a -> Maybe b) -> Map k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
M.mapMaybeWithKey k -> a -> Maybe b
f Map k a
m)
                                ((Map k b -> Map k b) -> Map k b)
-> (Maybe b -> Map k b -> Map k b) -> Maybe b -> Map k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k b -> Map k b)
-> (b -> Map k b -> Map k b) -> Maybe b -> Map k b -> Map k b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k b -> Map k b
forall a. a -> a
id (k -> b -> Map k b -> Map k b
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k)
                                (Maybe b -> Map k b) -> Maybe b -> Map k b
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe b
f k
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)
    -> NEMap k a
    -> These (NEMap k b) (NEMap k c)
mapEither :: (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c)
mapEither a -> Either b c
f = (k -> a -> Either b c)
-> NEMap k a -> These (NEMap k b) (NEMap k c)
forall k a b c.
(k -> a -> Either b c)
-> NEMap k a -> These (NEMap k b) (NEMap k c)
mapEitherWithKey ((a -> Either b c) -> k -> 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
    :: (k -> a -> Either b c)
    -> NEMap k a
    -> These (NEMap k b) (NEMap k c)
mapEitherWithKey :: (k -> a -> Either b c)
-> NEMap k a -> These (NEMap k b) (NEMap k c)
mapEitherWithKey k -> a -> Either b c
f (NEMap k
k a
v Map k a
m0) = case (Map k b -> Maybe (NEMap k b)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k b
m1, Map k c -> Maybe (NEMap k c)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k c
m2) of
    (Maybe (NEMap k b)
Nothing, Maybe (NEMap k c)
Nothing) -> case k -> a -> Either b c
f k
k a
v of
      Left  b
v' -> NEMap k b -> These (NEMap k b) (NEMap k c)
forall a b. a -> These a b
This  (k -> b -> NEMap k b
forall k a. k -> a -> NEMap k a
singleton k
k b
v')
      Right c
v' -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. b -> These a b
That                         (k -> c -> NEMap k c
forall k a. k -> a -> NEMap k a
singleton k
k c
v')
    (Just NEMap k b
n1, Maybe (NEMap k c)
Nothing) -> case k -> a -> Either b c
f k
k a
v of
      Left  b
v' -> NEMap k b -> These (NEMap k b) (NEMap k c)
forall a b. a -> These a b
This  (k -> b -> Map k b -> NEMap k b
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k b
v' Map k b
m1)
      Right c
v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. a -> b -> These a b
These NEMap k b
n1                     (k -> c -> NEMap k c
forall k a. k -> a -> NEMap k a
singleton k
k c
v')
    (Maybe (NEMap k b)
Nothing, Just NEMap k c
n2) -> case k -> a -> Either b c
f k
k a
v of
      Left  b
v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. a -> b -> These a b
These (k -> b -> NEMap k b
forall k a. k -> a -> NEMap k a
singleton k
k b
v')       NEMap k c
n2
      Right c
v' -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. b -> These a b
That                         (k -> c -> Map k c -> NEMap k c
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k c
v' Map k c
m2)
    (Just NEMap k b
n1, Just NEMap k c
n2) -> case k -> a -> Either b c
f k
k a
v of
      Left  b
v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. a -> b -> These a b
These (k -> b -> Map k b -> NEMap k b
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k b
v' Map k b
m1) NEMap k c
n2
      Right c
v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
forall a b. a -> b -> These a b
These NEMap k b
n1                     (k -> c -> Map k c -> NEMap k c
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k c
v' Map k c
m2)
  where
    (Map k b
m1, Map k c
m2) = (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
M.mapEitherWithKey k -> a -> Either b c
f Map k a
m0
{-# INLINABLE mapEitherWithKey #-}

-- | /O(log n)/. The expression (@'split' k map@) is potentially a 'These'
-- containing up to two 'NEMap'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
    :: Ord k
    => k
    -> NEMap k a
    -> Maybe (These (NEMap k a) (NEMap k a))
split :: k -> NEMap k a -> Maybe (These (NEMap k a) (NEMap k a))
split k
k n :: NEMap k a
n@(NEMap k
k0 a
v Map k a
m0) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> These (NEMap k a) (NEMap k a)
-> Maybe (These (NEMap k a) (NEMap k a))
forall a. a -> Maybe a
Just (These (NEMap k a) (NEMap k a)
 -> Maybe (These (NEMap k a) (NEMap k a)))
-> These (NEMap k a) (NEMap k a)
-> Maybe (These (NEMap k a) (NEMap k a))
forall a b. (a -> b) -> a -> b
$ NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That NEMap k a
n
    Ordering
EQ -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That (NEMap k a -> These (NEMap k a) (NEMap k a))
-> Maybe (NEMap k a) -> Maybe (These (NEMap k a) (NEMap k a))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m0
    Ordering
GT -> These (NEMap k a) (NEMap k a)
-> Maybe (These (NEMap k a) (NEMap k a))
forall a. a -> Maybe a
Just (These (NEMap k a) (NEMap k a)
 -> Maybe (These (NEMap k a) (NEMap k a)))
-> These (NEMap k a) (NEMap k a)
-> Maybe (These (NEMap k a) (NEMap k a))
forall a b. (a -> b) -> a -> b
$ case (Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m1, Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m2) of
      (Maybe (NEMap k a)
Nothing, Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k0 a
v)
      (Just NEMap k a
_ , Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k0 a
v Map k a
m1)
      (Maybe (NEMap k a)
Nothing, Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k0 a
v)       NEMap k a
n2
      (Just NEMap k a
_ , Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k0 a
v Map k a
m1) NEMap k a
n2
  where
    (Map k a
m1, Map k a
m2) = k -> Map k a -> (Map k a, Map k a)
forall k a. Ord k => k -> Map k a -> (Map k a, Map k a)
M.split k
k Map k 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
    :: Ord k
    => k
    -> NEMap k a
    -> These a (These (NEMap k a) (NEMap k a))
splitLookup :: k -> NEMap k a -> These a (These (NEMap k a) (NEMap k a))
splitLookup k
k n :: NEMap k a
n@(NEMap k
k0 a
v0 Map k a
m0) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall a b. b -> These a b
That (These (NEMap k a) (NEMap k a)
 -> These a (These (NEMap k a) (NEMap k a)))
-> (NEMap k a -> These (NEMap k a) (NEMap k a))
-> NEMap k a
-> These a (These (NEMap k a) (NEMap k a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That (NEMap k a -> These a (These (NEMap k a) (NEMap k a)))
-> NEMap k a -> These a (These (NEMap k a) (NEMap k a))
forall a b. (a -> b) -> a -> b
$ NEMap k a
n
    Ordering
EQ -> These a (These (NEMap k a) (NEMap k a))
-> (NEMap k a -> These a (These (NEMap k a) (NEMap k a)))
-> Maybe (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (a -> These a (These (NEMap k a) (NEMap k a))
forall a b. a -> These a b
This a
v0) (a
-> These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall a b. a -> b -> These a b
These a
v0 (These (NEMap k a) (NEMap k a)
 -> These a (These (NEMap k a) (NEMap k a)))
-> (NEMap k a -> These (NEMap k a) (NEMap k a))
-> NEMap k a
-> These a (These (NEMap k a) (NEMap k a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That) (Maybe (NEMap k a) -> These a (These (NEMap k a) (NEMap k a)))
-> (Map k a -> Maybe (NEMap k a))
-> Map k a
-> These a (These (NEMap k a) (NEMap k a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap (Map k a -> These a (These (NEMap k a) (NEMap k a)))
-> Map k a -> These a (These (NEMap k a) (NEMap k a))
forall a b. (a -> b) -> a -> b
$ Map k a
m0
    Ordering
GT -> (These (NEMap k a) (NEMap k a)
 -> These a (These (NEMap k a) (NEMap k a)))
-> (a
    -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a)))
-> Maybe a
-> These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall b a. b -> (a -> b) -> Maybe a -> b
maybe These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall a b. b -> These a b
That a
-> These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall a b. a -> b -> These a b
These Maybe a
v (These (NEMap k a) (NEMap k a)
 -> These a (These (NEMap k a) (NEMap k a)))
-> These (NEMap k a) (NEMap k a)
-> These a (These (NEMap k a) (NEMap k a))
forall a b. (a -> b) -> a -> b
$ case (Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m1, Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m2) of
      (Maybe (NEMap k a)
Nothing, Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k0 a
v0)
      (Just NEMap k a
_ , Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k0 a
v0 Map k a
m1)
      (Maybe (NEMap k a)
Nothing, Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k0 a
v0)       NEMap k a
n2
      (Just NEMap k a
_ , Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k0 a
v0 Map k a
m1) NEMap k a
n2
  where
    (Map k a
m1, Maybe a
v, Map k a
m2) = k -> Map k a -> (Map k a, Maybe a, Map k a)
forall k a. Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
M.splitLookup k
k Map k 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
    :: NEMap k a
    -> NonEmpty (NEMap k a)
splitRoot :: NEMap k a -> NonEmpty (NEMap k a)
splitRoot (NEMap k
k a
v Map k a
m) = k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v
                       NEMap k a -> [NEMap k a] -> NonEmpty (NEMap k a)
forall a. a -> [a] -> NonEmpty a
:| (Map k a -> Maybe (NEMap k a)) -> [Map k a] -> [NEMap k a]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap (Map k a -> [Map k a]
forall k b. Map k b -> [Map k b]
M.splitRoot Map k a
m)
{-# INLINE splitRoot #-}

-- | /O(m*log(n\/m + 1)), m <= n/.
-- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@).
isSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
isSubmapOf :: NEMap k a -> NEMap k a -> Bool
isSubmapOf = (a -> a -> Bool) -> NEMap k a -> NEMap k a -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> NEMap k a -> NEMap k 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
    :: Ord k
    => (a -> b -> Bool)
    -> NEMap k a
    -> NEMap k b
    -> Bool
isSubmapOfBy :: (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
isSubmapOfBy a -> b -> Bool
f (NEMap k
k a
v Map k a
m0) (NEMap k b -> Map k b
forall k a. NEMap k a -> Map k a
toMap->Map k b
m1) = Bool
kvSub
                                         Bool -> Bool -> Bool
&& (a -> b -> Bool) -> Map k a -> Map k b -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
M.isSubmapOfBy a -> b -> Bool
f Map k a
m0 Map k b
m1
  where
    kvSub :: Bool
kvSub = case k -> Map k b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup k
k Map k 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 :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
isProperSubmapOf :: NEMap k a -> NEMap k a -> Bool
isProperSubmapOf = (a -> a -> Bool) -> NEMap k a -> NEMap k a -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> NEMap k a -> NEMap k 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
    :: Ord k
    => (a -> b -> Bool)
    -> NEMap k a
    -> NEMap k b
    -> Bool
isProperSubmapOfBy :: (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
isProperSubmapOfBy a -> b -> Bool
f NEMap k a
m1 NEMap k b
m2 = Map k a -> Int
forall k a. Map k a -> Int
M.size (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
nemMap NEMap k a
m1) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Map k b -> Int
forall k a. Map k a -> Int
M.size (NEMap k b -> Map k b
forall k a. NEMap k a -> Map k a
nemMap NEMap k b
m2)
                          Bool -> Bool -> Bool
&& (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
isSubmapOfBy a -> b -> Bool
f NEMap k a
m1 NEMap k b
m2
{-# INLINE isProperSubmapOfBy #-}

-- | /O(log n)/. Lookup the /index/ of a key, which is its zero-based index
-- in the sequence sorted by keys. The index is a number from /0/ up to,
-- but not including, the 'size' of the map.
--
-- > isJust (lookupIndex 2 (fromList ((5,"a") :| [(3,"b")])))   == False
-- > fromJust (lookupIndex 3 (fromList ((5,"a") :| [(3,"b")]))) == 0
-- > fromJust (lookupIndex 5 (fromList ((5,"a") :| [(3,"b")]))) == 1
-- > isJust (lookupIndex 6 (fromList ((5,"a") :| [(3,"b")])))   == False
lookupIndex
    :: Ord k
    => k
    -> NEMap k a
    -> Maybe Int
lookupIndex :: k -> NEMap k a -> Maybe Int
lookupIndex k
k (NEMap k
k0 a
_ Map k a
m) = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k0 of
    Ordering
LT -> Maybe Int
forall a. Maybe a
Nothing
    Ordering
EQ -> Int -> Maybe Int
forall a. a -> Maybe a
Just Int
0
    Ordering
GT -> (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (Int -> Int) -> Maybe Int -> Maybe Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> Map k a -> Maybe Int
forall k a. Ord k => k -> Map k a -> Maybe Int
M.lookupIndex k
k Map k a
m
{-# INLINE lookupIndex #-}

-- | /O(log n)/. Return the /index/ of a key, which is its zero-based index
-- in the sequence sorted by keys. The index is a number from /0/ up to,
-- but not including, the 'size' of the map. Calls 'error' when the key is
-- not a 'member' of the map.
--
-- > findIndex 2 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map
-- > findIndex 3 (fromList ((5,"a") :| [(3,"b")])) == 0
-- > findIndex 5 (fromList ((5,"a") :| [(3,"b")])) == 1
-- > findIndex 6 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map
findIndex
    :: Ord k
    => k
    -> NEMap k a
    -> Int
findIndex :: k -> NEMap k a -> Int
findIndex k
k = Int -> Maybe Int -> Int
forall a. a -> Maybe a -> a
fromMaybe Int
forall a. a
e (Maybe Int -> Int) -> (NEMap k a -> Maybe Int) -> NEMap k a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> NEMap k a -> Maybe Int
forall k a. Ord k => k -> NEMap k a -> Maybe Int
lookupIndex k
k
  where
    e :: a
e = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"NEMap.findIndex: element is not in the map"
{-# INLINE findIndex #-}

-- | /O(log n)/. Retrieve an element by its /index/, i.e. by its zero-based
-- index in the sequence sorted by keys. If the /index/ is out of range
-- (less than zero, greater or equal to 'size' of the map), 'error' is
-- called.
--
-- > elemAt 0 (fromList ((5,"a") :| [(3,"b")])) == (3,"b")
-- > elemAt 1 (fromList ((5,"a") :| [(3,"b")])) == (5, "a")
-- > elemAt 2 (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
elemAt
    :: Int
    -> NEMap k a
    -> (k, a)
elemAt :: Int -> NEMap k a -> (k, a)
elemAt Int
0 (NEMap k
k a
v Map k a
_) = (k
k, a
v)
elemAt Int
i (NEMap k
_ a
_ Map k a
m) = Int -> Map k a -> (k, a)
forall k a. Int -> Map k a -> (k, a)
M.elemAt (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Map k a
m
{-# INLINABLE elemAt #-}

-- | /O(log n)/. Update the element at /index/, i.e. by its zero-based index in
-- the sequence sorted by keys. If the /index/ is out of range (less than zero,
-- greater or equal to 'size' of the map), 'error' is called.
--
-- Returns a possibly empty map ('Map'), because the function might end up
-- deleting the last key in the map.  See 'adjustAt' for a version that
-- disallows deletion, guaranteeing that the result is also a non-empty
-- Map.
--
-- > updateAt (\ _ _ -> Just "x") 0    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "x"), (5, "a")]
-- > updateAt (\ _ _ -> Just "x") 1    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "x")]
-- > updateAt (\ _ _ -> Just "x") 2    (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
-- > updateAt (\ _ _ -> Just "x") (-1) (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
-- > updateAt (\_ _  -> Nothing)  0    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
-- > updateAt (\_ _  -> Nothing)  1    (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
-- > updateAt (\_ _  -> Nothing)  2    (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
-- > updateAt (\_ _  -> Nothing)  (-1) (fromList ((5,"a") :| [(3,"b")]))    Error: index out of range
updateAt
    :: (k -> a -> Maybe a)
    -> Int
    -> NEMap k a
    -> Map k a
updateAt :: (k -> a -> Maybe a) -> Int -> NEMap k a -> Map k a
updateAt k -> a -> Maybe a
f Int
0 (NEMap k
k a
v Map k a
m) = Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k) Map k a
m) (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe a
f k
k a
v
updateAt k -> a -> Maybe a
f Int
i (NEMap k
k a
v Map k a
m) = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
forall k a. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
M.updateAt k -> a -> Maybe a
f (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINABLE updateAt #-}

-- | /O(log n)/. Variant of 'updateAt' that disallows deletion.  Allows us
-- to guarantee that the result is also a non-empty Map.
adjustAt
    :: (k -> a -> a)
    -> Int
    -> NEMap k a
    -> NEMap k a
adjustAt :: (k -> a -> a) -> Int -> NEMap k a -> NEMap k a
adjustAt k -> a -> a
f Int
0 (NEMap k
k0 a
v Map k a
m) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 (k -> a -> a
f k
k0 a
v) Map k a
m
adjustAt k -> a -> a
f Int
i (NEMap k
k0 a
v Map k a
m) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 a
v
                            (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
forall k a. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
M.updateAt (\k
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
. k -> a -> a
f k
k) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
                            (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINABLE adjustAt #-}

-- | /O(log n)/. Delete the element at /index/, i.e. by its zero-based
-- index in the sequence sorted by keys. If the /index/ is out of range
-- (less than zero, greater or equal to 'size' of the map), 'error' is
-- called.
--
-- Returns a potentially empty map ('Map') because of the possibility of
-- deleting the last item in a map.
--
-- > deleteAt 0  (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
-- > deleteAt 1  (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
-- > deleteAt 2 (fromList ((5,"a") :| [(3,"b")]))     Error: index out of range
-- > deleteAt (-1) (fromList ((5,"a") :| [(3,"b")]))  Error: index out of range
deleteAt
    :: Int
    -> NEMap k a
    -> Map k a
deleteAt :: Int -> NEMap k a -> Map k a
deleteAt Int
0 (NEMap k
_ a
_ Map k a
m) = Map k a
m
deleteAt Int
i (NEMap k
k a
v Map k a
m) = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Map k a -> Map k a
forall k a. Int -> Map k a -> Map k a
M.deleteAt (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINABLE deleteAt #-}

-- | Take a given number of entries in key order, beginning with the
-- smallest keys.
--
-- Returns a possibly empty map ('Map'), which can only happen if we call
-- @take 0@.
--
-- @
-- take n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.take n . 'toList'
-- @
take
    :: Int
    -> NEMap k a
    -> Map k a
take :: Int -> NEMap k a -> Map k a
take Int
0 NEMap{}       = Map k a
forall k a. Map k a
M.empty
take Int
i (NEMap k
k a
v Map k a
m) = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Map k a -> Map k a
forall k a. Int -> Map k a -> Map k a
M.take (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINABLE take #-}

-- | Drop a given number of entries in key order, beginning
-- with the smallest keys.
--
-- Returns a possibly empty map ('Map'), in case we drop all of the
-- elements (which can happen if we drop a number greater than or equal to
-- the number of items in the map)
--
-- @
-- drop n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.drop' n . 'toList'
-- @
drop
    :: Int
    -> NEMap k a
    -> Map k a
drop :: Int -> NEMap k a -> Map k a
drop Int
0 NEMap k a
n             = NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n
drop Int
i (NEMap k
_ a
_ Map k a
m) = Int -> Map k a -> Map k a
forall k a. Int -> Map k a -> Map k a
M.drop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Map k a
m
{-# INLINABLE drop #-}

-- | /O(log n)/. Split a map at a particular index @i@.
--
-- *   @'This' n1@ means that there are less than @i@ items in the map, and
--     @n1@ is the original map.
-- *   @'That' n2@ means @i@ was 0; we dropped 0 items, so @n2@ is the
--     original map.
-- *   @'These' n1 n2@ gives @n1@ (taking @i@ items from the original map)
--     and @n2@ (dropping @i@ items from the original map))
splitAt
    :: Int
    -> NEMap k a
    -> These (NEMap k a) (NEMap k a)
splitAt :: Int -> NEMap k a -> These (NEMap k a) (NEMap k a)
splitAt Int
0 NEMap k a
n                = NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. b -> These a b
That NEMap k a
n
splitAt Int
i n :: NEMap k a
n@(NEMap k
k a
v Map k a
m0) = case (Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m1, Map k a -> Maybe (NEMap k a)
forall k a. Map k a -> Maybe (NEMap k a)
nonEmptyMap Map k a
m2) of
    (Maybe (NEMap k a)
Nothing, Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v)
    (Just NEMap k a
_ , Maybe (NEMap k a)
Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> These a b
This  NEMap k a
n
    (Maybe (NEMap k a)
Nothing, Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> NEMap k a
forall k a. k -> a -> NEMap k a
singleton k
k a
v)       NEMap k a
n2
    (Just NEMap k a
_ , Just NEMap k a
n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
forall a b. a -> b -> These a b
These (k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k a
v Map k a
m1) NEMap k a
n2
  where
    (Map k a
m1, Map k a
m2) = Int -> Map k a -> (Map k a, Map k a)
forall k a. Int -> Map k a -> (Map k a, Map k a)
M.splitAt (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Map k a
m0
{-# INLINABLE splitAt #-}

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

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

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

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

-- | /O(1)/ if delete, /O(log n)/ otherwise. Update the value at the
-- minimal key.  Returns a potentially empty map ('Map'), 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.Map.fromList [(3, "Xb"), (5, "a")]
-- > updateMin (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
updateMin :: (a -> Maybe a) -> NEMap k a -> Map k a
updateMin :: (a -> Maybe a) -> NEMap k a -> Map k a
updateMin a -> Maybe a
f = (k -> a -> Maybe a) -> NEMap k a -> Map k a
forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMinWithKey ((a -> Maybe a) -> k -> 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) -> NEMap k a -> NEMap k a
adjustMin :: (a -> a) -> NEMap k a -> NEMap k a
adjustMin a -> a
f = (k -> a -> a) -> NEMap k a -> NEMap k a
forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMinWithKey ((a -> a) -> k -> 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 ('Map'), 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.Map.fromList [(3,"3:b"), (5,"a")]
-- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
updateMinWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMinWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMinWithKey k -> a -> Maybe a
f (NEMap k
k a
v Map k a
m) = ((Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m) ((Map k a -> Map k a) -> Map k a)
-> (Maybe a -> Map k a -> Map k a) -> Maybe a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> Map k a)
-> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a -> Map k a
forall a. a -> a
id (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k) (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe a
f k
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 :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMinWithKey k -> a -> a
f (NEMap k
k a
v Map k a
m) = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k (k -> a -> a
f k
k a
v) Map k a
m
{-# INLINE adjustMinWithKey #-}

-- | /O(log n)/. Update the value at the maximal key.  Returns
-- a potentially empty map ('Map'), 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.Map.fromList [(3, "b"), (5, "Xa")]
-- > updateMax (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
updateMax :: (a -> Maybe a) -> NEMap k a -> Map k a
updateMax :: (a -> Maybe a) -> NEMap k a -> Map k a
updateMax a -> Maybe a
f = (k -> a -> Maybe a) -> NEMap k a -> Map k a
forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMaxWithKey ((a -> Maybe a) -> k -> 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) -> NEMap k a -> NEMap k a
adjustMax :: (a -> a) -> NEMap k a -> NEMap k a
adjustMax a -> a
f = (k -> a -> a) -> NEMap k a -> NEMap k a
forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMaxWithKey ((a -> a) -> k -> 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 ('Map'), 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.Map.fromList [(3,"3:b"), (5,"a")]
-- > updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"
updateMaxWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMaxWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a
updateMaxWithKey k -> a -> Maybe a
f (NEMap k
k a
v Map k a
m)
    | Map k a -> Bool
forall k a. Map k a -> Bool
M.null Map k a
m  = Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k a
m (k -> a -> Map k a
forall k a. k -> a -> Map k a
M.singleton k
k) (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Maybe a
f k
k a
v
    | Bool
otherwise = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v
                (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> Map k a -> Map k a
forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
M.updateMaxWithKey k -> a -> Maybe a
f
                (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k 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 :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMaxWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMaxWithKey k -> a -> a
f (NEMap k
k0 a
v Map k a
m)
    | Map k a -> Bool
forall k a. Map k a -> Bool
M.null Map k a
m  = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
NEMap k
k0 (k -> a -> a
f k
k0 a
v) Map k a
m
    | Bool
otherwise = k -> a -> Map k a -> NEMap k a
forall k a. k -> a -> Map k a -> NEMap k a
insertMapMin k
k0 a
v
                (Map k a -> NEMap k a)
-> (Map k a -> Map k a) -> Map k a -> NEMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> a -> Maybe a) -> Map k a -> Map k a
forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
M.updateMaxWithKey (\k
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
. k -> a -> a
f k
k)
                (Map k a -> NEMap k a) -> Map k a -> NEMap k a
forall a b. (a -> b) -> a -> b
$ Map k 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.Map.minView@ for 'Map'.
--
-- Note that unlike @Data.Map.minView@ for 'Map', this cannot ever fail,
-- so doesn't need to return in a 'Maybe'.  However, the result 'Map' is
-- potentially empty, since the original map might have contained just
-- a single item.
--
-- > minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.Map.singleton 5 "a")
minView :: NEMap k a -> (a, Map k a)
minView :: NEMap k a -> (a, Map k a)
minView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (k, a) -> a
forall a b. (a, b) -> b
snd (((k, a), Map k a) -> (a, Map k a))
-> (NEMap k a -> ((k, a), Map k a)) -> NEMap k a -> (a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> ((k, a), Map k a)
forall k a. NEMap k a -> ((k, a), Map k a)
deleteFindMin
{-# INLINE minView #-}

-- | /O(1)/. Delete and find the minimal key-value pair.  It is
-- constant-time, so has better asymptotics that @Data.Map.minView@ for
-- 'Map'.
--
-- Note that unlike @Data.Map.deleteFindMin@ for 'Map', this cannot ever
-- fail, and so is a total function. However, the result 'Map' 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.Map.fromList [(5,"a"), (10,"c")])
deleteFindMin :: NEMap k a -> ((k, a), Map k a)
deleteFindMin :: NEMap k a -> ((k, a), Map k a)
deleteFindMin (NEMap k
k a
v Map k a
m) = ((k
k, a
v), Map k 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.Map.maxView@ from 'Map', this cannot ever fail,
-- so doesn't need to return in a 'Maybe'.  However, the result 'Map' is
-- potentially empty, since the original map might have contained just
-- a single item.
--
-- > maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.Map.singleton 3 "b")
maxView :: NEMap k a -> (a, Map k a)
maxView :: NEMap k a -> (a, Map k a)
maxView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (k, a) -> a
forall a b. (a, b) -> b
snd (((k, a), Map k a) -> (a, Map k a))
-> (NEMap k a -> ((k, a), Map k a)) -> NEMap k a -> (a, Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NEMap k a -> ((k, a), Map k a)
forall k a. NEMap k a -> ((k, a), Map k a)
deleteFindMax
{-# INLINE maxView #-}

-- | /O(log n)/. Delete and find the minimal key-value pair.
--
-- Note that unlike @Data.Map.deleteFindMax@ for 'Map', this cannot ever
-- fail, and so is a total function. However, the result 'Map' 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.Map.fromList [(3,"b"), (5,"a")])
deleteFindMax :: NEMap k a -> ((k, a), Map k a)
deleteFindMax :: NEMap k a -> ((k, a), Map k a)
deleteFindMax (NEMap k
k a
v Map k a
m) = ((k, a), Map k a)
-> (((k, a), Map k a) -> ((k, a), Map k a))
-> Maybe ((k, a), Map k a)
-> ((k, a), Map k a)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ((k
k, a
v), Map k a
forall k a. Map k a
M.empty) ((Map k a -> Map k a) -> ((k, a), Map k a) -> ((k, a), Map k a)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insertMinMap k
k a
v))
                            (Maybe ((k, a), Map k a) -> ((k, a), Map k a))
-> (Map k a -> Maybe ((k, a), Map k a))
-> Map k a
-> ((k, a), Map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k a -> Maybe ((k, a), Map k a)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.maxViewWithKey
                            (Map k a -> ((k, a), Map k a)) -> Map k a -> ((k, a), Map k a)
forall a b. (a -> b) -> a -> b
$ Map k a
m
{-# INLINE deleteFindMax #-}

-- | Special property of non-empty maps: The type of non-empty maps over
-- uninhabited keys is itself uninhabited.
--
-- This property also exists for /values/ inside a non-empty container
-- (like for 'NESet', 'NESeq', and 'NEIntMap'); this can be witnessed using
-- the function @'absurd' . 'fold1'@.
--
-- @since 0.3.1.0
absurdNEMap :: NEMap Void a -> b
absurdNEMap :: NEMap Void a -> b
absurdNEMap = \case {}

-- ---------------------------
-- 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 :: Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
combineEq :: NonEmpty (a, b) -> NonEmpty (a, b)
combineEq = \case
    (a, b)
x :| []       -> (a, b)
x (a, b) -> [(a, b)] -> NonEmpty (a, b)
forall a. a -> [a] -> NonEmpty a
:| []
    (a, b)
x :| xx :: [(a, b)]
xx@((a, b)
_:[(a, b)]
_) -> (a, b) -> [(a, b)] -> NonEmpty (a, b)
forall a b. Eq a => (a, b) -> [(a, b)] -> NonEmpty (a, b)
go (a, b)
x [(a, 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
    :: Eq a
    => (a -> b -> b -> b)
    -> NonEmpty (a, b)
    -> NonEmpty (a, b)
combineEqWith :: (a -> b -> b -> b) -> NonEmpty (a, b) -> NonEmpty (a, b)
combineEqWith a -> b -> b -> b
f = \case
    (a, b)
x :| []       -> (a, b)
x (a, b) -> [(a, b)] -> NonEmpty (a, b)
forall a. a -> [a] -> NonEmpty a
:| []
    (a, b)
x :| xx :: [(a, b)]
xx@((a, b)
_:[(a, b)]
_) -> (a, b) -> [(a, b)] -> NonEmpty (a, b)
go (a, b)
x [(a, 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
zz) (x :: (a, b)
x@(a
kx,b
xx):[(a, b)]
xs')
      | a
kxa -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
kz    = let yy :: b
yy = a -> b -> b -> b
f a
kx b
xx b
zz in (a, b) -> [(a, b)] -> NonEmpty (a, b)
go (a
kx,b
yy) [(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'