{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE EmptyCase #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE PatternSynonyms #-}
{-# 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 qualified Data.Foldable as F
import Data.Function
import Data.Functor.Apply
import Data.Functor.Identity
import Data.List.NonEmpty (NonEmpty (..))
import qualified Data.List.NonEmpty as NE
import Data.Map (Map)
import qualified Data.Map as M
import Data.Map.NonEmpty.Internal
import Data.Maybe hiding (mapMaybe)
import qualified Data.Maybe as Maybe
import Data.Semigroup.Foldable (Foldable1)
import qualified Data.Semigroup.Foldable as F1
import Data.Set (Set)
import qualified Data.Set as S
import Data.Set.NonEmpty.Internal (NESet (..))
import Data.These
import Data.Void
import Prelude hiding (Foldable (..), drop, filter, lookup, map, splitAt, take)

-- | /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 $mIsNonEmpty :: forall {r} {k} {a}.
Map k a -> (NEMap k a -> r) -> ((# #) -> r) -> r
$bIsNonEmpty :: forall k a. NEMap k a -> Map k a
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 $mIsEmpty :: forall {r} {k} {a}. Map k a -> ((# #) -> r) -> ((# #) -> r) -> r
$bIsEmpty :: forall k a. Map k a
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 :: forall k a. 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 :: forall k a. (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 :: forall k a. Ord k => 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
!? :: forall k a. Ord k => 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
! :: forall k 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 :: forall k a. Ord k => 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 :: forall k a. Ord k => 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 :: forall k a. Ord k => 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 :: forall k a. Ord k => 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 a. Maybe a -> Maybe a -> Maybe 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 :: forall k a. Ord k => 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 :: forall k a. Ord k => 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 a. Maybe a -> Maybe a -> Maybe 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 :: forall k a. Ord k => 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 :: forall k a.
Ord k =>
(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 :: forall k a.
Ord k =>
(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 :: forall (f :: * -> *) k a.
(Foldable1 f, Ord k) =>
(a -> a -> a) -> f (NEMap k a) -> NEMap k a
unionsWith a -> a -> a
f (f (NEMap k a) -> NonEmpty (NEMap k a)
forall a. f a -> NonEmpty 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 b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' ((a -> a -> a) -> 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 :: forall k a b. Ord k => 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
\\ :: forall k a b. Ord k => 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 :: forall k a b.
Ord k =>
(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 :: forall k a b.
Ord k =>
(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)
-> (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) (k -> a -> b -> Maybe a
f k
k1 a
v1 b
v2) ((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)
  -- 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 :: forall k a b. Ord k => 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 :: forall k a b c.
Ord k =>
(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 :: forall k a b c.
Ord k =>
(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' :: forall a k. (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' :: forall a k. (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 :: forall k a b. (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' :: forall k a b. (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 :: forall a k b. (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' :: forall a k b. (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 :: forall k a. 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 :: forall k a. 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 :: forall k a. 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 :: forall k a b. (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 :: forall k a. 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 :: forall k a. 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 :: forall k a. Ord k => 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 :: forall k a.
Ord k =>
(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 :: forall k a.
Ord k =>
(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 :: forall k a. 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 :: forall k a. 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 :: forall k a. Ord k => 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 :: 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 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 :: forall k a.
Ord k =>
(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 :: forall k a. Ord k => (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 :: forall k a.
Ord k =>
(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 b a. (b -> a -> b) -> b -> [a] -> b
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 :: forall k a. Eq k => 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 :: forall k a. Eq k => (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 :: forall k a.
Eq k =>
(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 :: forall k a. 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 :: forall k a. Eq k => 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 :: forall k a. Eq k => (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 :: forall k a.
Eq k =>
(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 :: forall k a. 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 :: forall k a. Ord k => 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 :: forall k a. Ord k => (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 :: forall k a. Ord k => (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 :: forall k a. Ord k => (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 :: forall k a.
Ord k =>
(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 :: forall k a.
Ord k =>
(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 a. 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 a b. (a -> b) -> (Maybe a, a) -> (Maybe a, b)
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 :: forall k a.
Ord k =>
(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)
-> (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 -> Maybe a
f 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 -> (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 -> Maybe a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
v)) 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
. (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 :: forall k (f :: * -> *) a.
(Ord k, Functor f) =>
(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 -> (Maybe a -> Map k a -> Map k a) -> Map k a -> Maybe a -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((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)) (NEMap k a -> Map k a
forall k a. NEMap k a -> Map k a
toMap NEMap k a
n) (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 -> (Maybe a -> Map k a -> Map k a) -> Map k a -> Maybe a -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((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)) Map k a
m (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
{-# INLINEABLE [2] alterF #-}

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

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

-- | /O(log n)/. Variant of 'alter' that disallows deletion.  Allows us to
-- guarantee that the result is also a non-empty Map.
alter' ::
  Ord k =>
  (Maybe a -> a) ->
  k ->
  NEMap k a ->
  NEMap k a
alter' :: forall k a. Ord k => (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
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' :: forall k (f :: * -> *) a.
(Ord k, Functor f) =>
(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 a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> Maybe a
forall a. a -> Maybe a
Just (f a -> f (Maybe a)) -> (Maybe a -> f a) -> Maybe a -> f (Maybe a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe a -> f a
f) k
k Map k a
m
{-# INLINEABLE [2] alterF' #-}

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

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

-- | /O(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 :: forall (t :: * -> *) k a b.
Applicative t =>
(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 a b. t (a -> b) -> t a -> t 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 :: forall (t :: * -> *) k a b.
Apply t =>
(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 a b. t (a -> b) -> t a -> t 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 :: forall a b c k.
(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 :: forall a k b c.
(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 :: forall a k b c.
(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 :: forall k2 k1 a. Ord k2 => (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
{-# INLINEABLE mapKeys #-}

-- | /O(n*log n)/.
-- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
--
-- The size of the result may be smaller if @f@ maps two or more distinct
-- keys to the same new key.  In this case the associated values will be
-- combined using @c@. The value at the greater of the two original keys
-- is used as the first argument to @c@.
--
-- While the size of the result map may be smaller than the input map, the
-- output map is still guaranteed to be non-empty if the input map is
-- non-empty.
--
-- > mapKeysWith (++) (\ _ -> 1) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 1 "cdab"
-- > mapKeysWith (++) (\ _ -> 3) (fromList ((1,"b") :| [(2,"a"), (3,"d"), (4,"c")])) == singleton 3 "cdab"
mapKeysWith ::
  Ord k2 =>
  (a -> a -> a) ->
  (k1 -> k2) ->
  NEMap k1 a ->
  NEMap k2 a
mapKeysWith :: forall k2 a k1.
Ord k2 =>
(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
{-# INLINEABLE mapKeysWith #-}

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

-- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
-- like 'split' but also returns @'lookup' k map@, as the first field in
-- the 'These':
--
-- > splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That      (That  (fromList ((3,"b") :| [(5,"a")])))
-- > splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That  (singleton 5 "a"))
-- > splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That      (These (singleton 3 "b") (singleton 5 "a"))
-- > splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This  (singleton 3 "b"))
-- > splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That      (This  (fromList ((3,"b") :| [(5,"a")])))
-- > splitLookup 5 (singleton 5 "a")                 == This  "a"
splitLookup ::
  Ord k =>
  k ->
  NEMap k a ->
  These a (These (NEMap k a) (NEMap k a))
splitLookup :: forall k a.
Ord k =>
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
{-# INLINEABLE splitLookup #-}

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

-- | /O(1)/. A version of 'adjustMaxWithKey' that disallows deletion,
-- allowing us to guarantee that the result is also non-empty.  Note that
-- it also is able to have better asymptotics than 'updateMinWithKey' in
-- general.
adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMinWithKey :: forall k a. (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 :: forall a k. (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 :: forall a k. (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 :: forall k a. (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 :: forall k a. (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 :: forall k a. NEMap k a -> (a, Map k a)
minView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (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 :: forall k a. 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 :: forall k a. NEMap k a -> (a, Map k a)
maxView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (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 :: forall k a. 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 b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (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 :: forall a b. 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 :: forall a b. Eq a => 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
kx a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
kz = (a, b) -> [(a, b)] -> NonEmpty (a, b)
go (a
kx, b
xx) [(a, b)]
xs'
      | Bool
otherwise = (a, b)
z (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
forall a. a -> NonEmpty a -> NonEmpty a
NE.<| (a, b) -> [(a, b)] -> NonEmpty (a, b)
go (a, b)
x [(a, b)]
xs'

combineEqWith ::
  Eq a =>
  (a -> b -> b -> b) ->
  NonEmpty (a, b) ->
  NonEmpty (a, b)
combineEqWith :: forall a b.
Eq a =>
(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
kx a -> 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'