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

-- |
-- Module      : Data.Map.NonEmpty
-- Copyright   : (c) Justin Le 2018
-- License     : BSD3
--
-- Maintainer  : justin@jle.im
-- Stability   : experimental
-- Portability : non-portable
--
-- = Non-Empty Finite Maps (lazy interface)
--
-- The @'NEMap' k v@ type represents a non-empty finite map (sometimes
-- called a dictionary) from keys of type @k@ to values of type @v@.
-- An 'NEMap' is strict in its keys but lazy in its values.
--
-- See documentation for 'NEMap' for information on how to convert and
-- manipulate such non-empty maps.
--
-- This module essentially re-imports the API of "Data.Map.Lazy" and its
-- 'Map' type, along with semantics and asymptotics.  In most situations,
-- asymptotics are different only by a constant factor.  In some
-- situations, asmyptotics are even better (constant-time instead of
-- log-time).  All typeclass constraints are identical to their "Data.Map"
-- counterparts.
--
-- Because 'NEMap' is implemented using 'Map', all of the caveats of using
-- 'Map' apply (such as the limitation of the maximum size of maps).
--
-- All functions take non-empty maps as inputs.  In situations where their
-- results can be guarunteed to also be non-empty, they also return
-- non-empty maps.  In situations where their results could potentially be
-- empty, 'Map' is returned instead.
--
-- Some variants of functions (like 'alter'', 'alterF'', 'adjustAt',
-- 'adjustMin', 'adjustMax', 'adjustMinWithKey', 'adjustMaxWithKey') are
-- provided in a way restructured to preserve guaruntees of non-empty maps
-- being returned.
--
-- Some functions (like 'mapEither', 'partition', 'spanAntitone', 'split')
-- have modified return types to account for possible configurations of
-- non-emptiness.
--
-- This module is intended to be imported qualified, to avoid name clashes with
-- "Prelude" and "Data.Map" functions:
--
-- > import qualified Data.Map.NonEmpty as NEM
--
-- At the moment, this package does not provide a variant strict on values
-- for these functions, like /containers/ does.  This is a planned future
-- implementation (PR's are appreciated).  For now, you can simulate
-- a strict interface by manually forcing values before returning results.
module Data.Map.NonEmpty (
  -- * Non-Empty Map type
    NEMap
  -- ** Conversions between empty and non-empty maps
  , pattern IsNonEmpty
  , pattern IsEmpty
  , nonEmptyMap
  , toMap
  , withNonEmpty
  , insertMap
  , insertMapWith
  , insertMapWithKey
  , insertMapMin
  , insertMapMax
  , unsafeFromMap

  -- * Construction
  , singleton
  , fromSet

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

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

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

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

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

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

  -- ** 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.Or                    (Or(..))
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           Prelude                    hiding
    (drop, filter, foldl, foldl1, foldr, foldr1, 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 IsNonEmpty n <- (nonEmptyMap->Just n)
  where
    IsNonEmpty n = toMap 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 IsEmpty <- (M.null->True)
  where
    IsEmpty = 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 = withNonEmpty e id
  where
    e = errorWithoutStackTrace "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 f (NESet k ks) = NEMap k (f k) (M.fromSet f ks)
{-# INLINE fromSet #-}

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

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

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

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

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

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

-- | /O(log n)/. Find smallest key greater or equal to the given one and return
-- the corresponding (key, value) pair.
--
-- > lookupGE 3 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')
-- > lookupGE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')
-- > lookupGE 6 (fromList ((3,'a') :| [(5,'b')])) == Nothing
lookupGE :: Ord k => k -> NEMap k a -> Maybe (k, a)
lookupGE k (NEMap k0 v m) = case compare k k0 of
    LT -> Just (k0, v)
    EQ -> Just (k0, v)
    GT -> M.lookupGE k 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 f n1@(NEMap k1 v1 m1) n2@(NEMap k2 v2 m2) = case compare k1 k2 of
    LT -> NEMap k1 v1        . M.unionWith f m1 . toMap $ n2
    EQ -> NEMap k1 (f v1 v2) . M.unionWith f m1         $ m2
    GT -> NEMap k2 v2        . M.unionWith f (toMap n1) $ 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 f n1@(NEMap k1 v1 m1) n2@(NEMap k2 v2 m2) = case compare k1 k2 of
    LT -> NEMap k1 v1           . M.unionWithKey f m1 . toMap $ n2
    EQ -> NEMap k1 (f k1 v1 v2) . M.unionWithKey f m1         $ m2
    GT -> NEMap k2 v2           . M.unionWithKey f (toMap n1) $ 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 f (F1.toNonEmpty->(m :| ms)) = F.foldl' (unionWith f) m 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 n1@(NEMap k1 v1 m1) n2@(NEMap k2 _ m2) = case compare k1 k2 of
    -- k1 is not in n2, so cannot be deleted
    LT -> insertMinMap k1 v1 $ m1 `M.difference` toMap n2
    -- k2 deletes k1, and only k1
    EQ -> m1 `M.difference` m2
    -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
    GT -> toMap n1 `M.difference` m2
{-# INLINE difference #-}

-- | Same as 'difference'.
(\\)
    :: 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 f = differenceWithKey (const 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 f n1@(NEMap k1 v1 m1) n2@(NEMap k2 v2 m2) = case compare k1 k2 of
    -- k1 is not in n2, so cannot be deleted
    LT -> insertMinMap k1 v1 $ M.differenceWithKey f m1 (toMap n2)
    -- k2 deletes k1, and only k1
    EQ -> ($ M.differenceWithKey f m1 m2) . maybe id (insertMinMap k1) $ f k1 v1 v2
    -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
    GT -> M.differenceWithKey f (toMap n1) 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 n1@(NEMap k1 v1 m1) n2@(NEMap k2 _ m2) = case compare k1 k2 of
    -- k1 is not in n2
    LT -> m1 `M.intersection` toMap n2
    -- k1 and k2 are a part of the result
    EQ -> insertMinMap k1 v1 $ m1 `M.intersection` m2
    -- k2 is not in n1
    GT -> toMap n1 `M.intersection` 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 f = intersectionWithKey (const 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 f n1@(NEMap k1 v1 m1) n2@(NEMap k2 v2 m2) = case compare k1 k2 of
    -- k1 is not in n2
    LT -> M.intersectionWithKey f m1 (toMap n2)
    -- k1 and k2 are a part of the result
    EQ -> insertMinMap k1 (f k1 v1 v2) $ M.intersectionWithKey f m1 m2
    -- k2 is not in n1
    GT -> M.intersectionWithKey f (toMap n1) 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' f (NEMap _ v m) = case M.maxView m of
    Nothing      -> v
    Just (y, m') -> let !z = M.foldr' f y m' in v `f` 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' f (NEMap _ v m) = M.foldl' f v 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 f z (NEMap k v m) = f k v . M.foldrWithKey f z $ 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' f z (NEMap k v m) = f k v y
  where
    !y = M.foldrWithKey f z 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 f z (NEMap k v m) = M.foldlWithKey f (f z k v) 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' f z (NEMap k v m) = M.foldlWithKey' f x m
  where
    !x = f z k v
{-# INLINE foldlWithKey' #-}

-- | /O(n)/. Return all keys of the map in ascending order.
--
-- > keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])
keys :: NEMap k a -> NonEmpty k
keys (NEMap k _ m) = k :| M.keys 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 = toList
{-# INLINE assocs #-}

-- | /O(n)/. The non-empty set of all keys of the map.
--
-- > keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5])
keysSet :: NEMap k a -> NESet k
keysSet (NEMap k _ m) = NESet k (M.keysSet 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 f (NEMap k v m) = NEMap k (f k v) (M.mapWithKey f 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 = toList
{-# INLINE toAscList #-}

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

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

-- | /O(log n)/ Convert a 'Map' into an 'NEMap' by adding a key-value pair
-- where the key is /strictly greater than/ all keys in the input map.  The
-- keys in the original map must all be /strictly less than/ the new
-- key.  /The precondition is not checked./
--
-- While this has the same asymptotics as 'insertMap', it saves a constant
-- factor for key comparison (so may be helpful if comparison is expensive)
-- and also does not require an 'Ord' instance for the key type.
--
-- > insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")])
-- > valid (insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True
-- > valid (insertMap 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
-- > valid (insertMap 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False
insertMapMax
    :: k
    -> a
    -> Map k a
    -> NEMap k a
insertMapMax k v = withNonEmpty (singleton k v) go
  where
    go (NEMap k0 v0 m0) = NEMap k0 v0 . insertMaxMap k v $ m0
{-# INLINE insertMapMax #-}


-- | /O(log n)/. Insert a new key and value in the map.
-- If the key is already present in the map, the associated value is
-- replaced with the supplied value. 'insert' is equivalent to
-- @'insertWith' 'const'@.
--
-- See 'insertMap' for a version where the first argument is a 'Map'.
--
-- > insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')])
-- > insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')])
insert
    :: Ord k
    => k
    -> a
    -> NEMap k a
    -> NEMap k a
insert k v n@(NEMap k0 v0 m) = case compare k k0 of
    LT -> NEMap k  v  . toMap        $ n
    EQ -> NEMap k  v  m
    GT -> NEMap k0 v0 . M.insert k v $ 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 f k v n@(NEMap k0 v0 m) = case compare k k0 of
    LT -> NEMap k  v          . toMap               $ n
    EQ -> NEMap k  (f k v v0) m
    GT -> NEMap k0 v0         $ M.insertWithKey f k v 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 f k v n@(NEMap k0 v0 m) = case compare k k0 of
    LT -> (Nothing, NEMap k  v . toMap $ n )
    EQ -> (Just v , NEMap k  (f k v v0)  m )
    GT -> NEMap k0 v0 <$> M.insertLookupWithKey f k v 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 f = fromListWithKey (const 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 f ((k0, v0) :| xs) = F.foldl' go (singleton k0 v0) xs
  where
    go m (k, v) = insertWithKey f k v 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 = fromDistinctAscList . 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 f = fromAscListWithKey (const 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 f = fromDistinctAscList . combineEqWith 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 ((k, v) :| xs) = insertMapMin k v
                                   . M.fromDistinctAscList
                                   $ 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 = fromDistinctDescList . 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 f = fromDescListWithKey (const 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 f = fromDistinctDescList . combineEqWith 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 ((k, v) :| xs) = insertMapMax k v
                                    . M.fromDistinctDescList
                                    $ xs
{-# INLINE fromDistinctDescList #-}

-- | /O(log n)/. Delete a key and its value from the non-empty map.
-- A potentially empty map ('Map') is returned, since this might delete the
-- last item in the 'NEMap'.  When the key is not a member of the map, is
-- equivalent to 'toMap'.
--
-- > delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"
-- > delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.Singleton [(3, "b"), (5, "a")]
delete :: Ord k => k -> NEMap k a -> Map k a
delete k n@(NEMap k0 v m) = case compare k k0 of
    LT -> toMap n
    EQ -> m
    GT -> insertMinMap k0 v . M.delete k $ 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 f = adjustWithKey (const 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 f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> n
    EQ -> NEMap k0 (f k0 v) m
    GT -> NEMap k0 v . M.adjustWithKey f k $ 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 f = updateWithKey (const 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 f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> toMap n
    EQ -> maybe m (flip (insertMinMap k0) m) . f k0 $ v
    GT -> insertMinMap k0 v . M.updateWithKey f k   $ 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 f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> (Nothing, toMap n)
    EQ -> let u = f k0 v
          in  (u <|> Just v, maybe m (flip (insertMinMap k0) m) u)
    GT -> fmap (insertMinMap k0 v) . M.updateLookupWithKey f k $ 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 f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> ($ toMap n) . maybe id (insertMinMap k ) $ f Nothing
    EQ -> ($ m      ) . maybe id (insertMinMap k0) $ f (Just v)
    GT -> insertMinMap k0 v . M.alter f k $ 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 f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> ($ toMap n) . maybe id (insertMinMap k ) <$> f Nothing
    EQ -> ($ m      ) . maybe id (insertMinMap k0) <$> f (Just v)
    GT -> insertMinMap k0 v <$> M.alterF f k m
{-# INLINABLE [2] alterF #-}

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

-- | /O(log n)/. Variant of 'alter' that disallows deletion.  Allows us to
-- guarantee that the result is also a non-empty Map.
alter'
    :: Ord k
    => (Maybe a -> a)
    -> k
    -> NEMap k a
    -> NEMap k a
alter' f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> NEMap k  (f Nothing) . toMap      $ n
    EQ -> NEMap k0 (f (Just v))             $ m
    GT -> NEMap k0 v . M.alter (Just . f) k $ 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' f k n@(NEMap k0 v m) = case compare k k0 of
    LT -> flip (NEMap k ) (toMap n) <$> f Nothing
    EQ -> flip (NEMap k0) m         <$> f (Just v)
    GT -> NEMap k0 v <$> M.alterF (fmap Just . f) k m
{-# INLINABLE [2] alterF' #-}

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

-- | /O(n)/. Traverse keys\/values and collect the 'Just' results.
--
-- Returns a potentially empty map ('Map'), our function might return
-- 'Nothing' on every item in the 'NEMap'.
--
-- /Use 'traverseMaybeWithKey1'/ whenever possible (if your 'Applicative'
-- also has 'Apply' instance).  This version is provided only for types
-- that do not have 'Apply' instance, since 'Apply' is not at the moment
-- (and might not ever be) an official superclass of 'Applicative'.
traverseMaybeWithKey
    :: Applicative t
    => (k -> a -> t (Maybe b))
    -> NEMap k a
    -> t (Map k b)
traverseMaybeWithKey f (NEMap k0 v m0) =
    combine <$> f k0 v <*> M.traverseMaybeWithKey f m0
  where
    combine Nothing   = id
    combine (Just v') = insertMinMap k0 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 f (NEMap k0 v m0) = case runMaybeApply m1 of
    Left  m2 -> combine <$> f k0 v <.> m2
    Right m2 -> (`combine` m2) <$> f k0 v
  where
    m1 = M.traverseMaybeWithKey (\k -> MaybeApply . Left . f k) m0
    combine Nothing   = id
    combine (Just v') = insertMinMap k0 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 f = mapAccumWithKey (\x _ -> f 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 f z0 (NEMap k v m) = (z2, NEMap k v' m')
  where
    ~(z1, v') = f z0 k v
    ~(z2, m') = M.mapAccumWithKey f z1 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 f z0 (NEMap k v m) = (z2, NEMap k v' m')
  where
    ~(z1, m') = M.mapAccumRWithKey f z0 m
    ~(z2, v') = f z1 k 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 f (NEMap k0 v0 m) = fromListWith const
                          . ((f k0, v0) :|)
                          . M.foldrWithKey (\k v kvs -> (f k, v) : kvs) []
                          $ m
{-# INLINABLE mapKeys #-}

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

-- | /O(n)/.
-- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@
-- is strictly monotonic.
-- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
-- /The precondition is not checked./
-- Semi-formally, we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapKeysMonotonic f s == mapKeys f s
-- >     where ls = keys s
--
-- This means that @f@ maps distinct original keys to distinct resulting keys.
-- This function has better performance than 'mapKeys'.
--
-- While the size of the result map may be smaller than the input map, the
-- output map is still guaranteed to be non-empty if the input map is
-- non-empty.
--
-- > mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")])) == fromList ((6, "b") :| [(10, "a")])
-- > valid (mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")]))) == True
-- > valid (mapKeysMonotonic (\ _ -> 1)     (fromList ((5,"a") :| [(3,"b")]))) == False
mapKeysMonotonic
    :: (k1 -> k2)
    -> NEMap k1 a
    -> NEMap k2 a
mapKeysMonotonic f (NEMap k v m) = NEMap (f k) v
                                 . M.mapKeysMonotonic f
                                 $ 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 f (NEMap k v m)
    | f v       = insertMinMap k v . M.filter f $ m
    | otherwise = M.filter f 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 f (NEMap k v m)
    | f k v     = insertMinMap k v . M.filterWithKey f $ m
    | otherwise = M.filterWithKey f 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 n@(NEMap k v m) xs = case S.minView xs of
    Nothing      -> M.empty
    Just (y, ys) -> case compare k y of
      -- k is not in xs
      LT -> m `M.restrictKeys` xs
      -- k and y are a part of the result
      EQ -> insertMinMap k v $ m `M.restrictKeys` ys
      -- y is not in m
      GT -> toMap n `M.restrictKeys` 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 n@(NEMap k v m) xs = case S.minView xs of
    Nothing      -> toMap n
    Just (y, ys) -> case compare k y of
      -- k is not in xs, so cannot be deleted
      LT -> insertMinMap k v $ m `M.withoutKeys` xs
      -- y deletes k, and only k
      EQ -> m `M.withoutKeys` ys
      -- y is not in n, so cannot delete anything, so we can just difference n and ys
      GT -> toMap n `M.withoutKeys` ys
{-# INLINE withoutKeys #-}

-- | /O(n)/. Partition the map according to a predicate.
--
-- Returns an 'Or' with potentially two non-empty maps:
--
-- *   @'Fst' n1@ means that the predicate was true for all items.
-- *   @'Snd' n2@ means that the predicate was false for all items.
-- *   @'Both' 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")])) == Both (singleton 3 "b") (singleton 5 "a")
-- > partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == Fst  (fromList ((3, "b") :| [(5, "a")]))
-- > partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == Snd  (fromList ((3, "b") :| [(5, "a")]))
partition
    :: (a -> Bool)
    -> NEMap k a
    -> Or (NEMap k a) (NEMap k a)
partition f = partitionWithKey (const f)
{-# INLINE partition #-}

-- | /O(n)/. Partition the map according to a predicate.
--
-- Returns an 'Or' with potentially two non-empty maps:
--
-- *   @'Fst' n1@ means that the predicate was true for all items,
--     returning the original map.
-- *   @'Snd' n2@ means that the predicate was false for all items,
--     returning the original map.
-- *   @'Both' 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")])) == Both (singleton 5 "a") (singleton 3 "b")
-- > partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == Fst  (fromList ((3, "b") :| [(5, "a")]))
-- > partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == Snd  (fromList ((3, "b") :| [(5, "a")]))
partitionWithKey
    :: (k -> a -> Bool)
    -> NEMap k a
    -> Or (NEMap k a) (NEMap k a)
partitionWithKey f n@(NEMap k v m0) = case (nonEmptyMap m1, nonEmptyMap m2) of
    (Nothing, Nothing)
      | f k v     -> Fst  n
      | otherwise -> Snd                        n
    (Just n1, Nothing)
      | f k v     -> Fst  n
      | otherwise -> Both n1                    (singleton k v)
    (Nothing, Just n2)
      | f k v     -> Both (singleton k v)       n2
      | otherwise -> Snd                        n
    (Just n1, Just n2)
      | f k v     -> Both (insertMapMin k v m1) n2
      | otherwise -> Both n1                    (insertMapMin k v m2)
  where
    (m1, m2) = M.partitionWithKey f m0
{-# INLINABLE partitionWithKey #-}

-- | /O(log n)/. Take while a predicate on the keys holds.
-- The user is responsible for ensuring that for all keys @j@ and @k@ in the map,
-- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
--
-- Returns a potentially empty map ('Map'), because the predicate might
-- fail on the first input.
--
-- @
-- takeWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.takeWhile (p . fst) . Data.Foldable.toList
-- takeWhileAntitone p = 'filterWithKey' (\k _ -> p k)
-- @
takeWhileAntitone
    :: (k -> Bool)
    -> NEMap k a
    -> Map k a
takeWhileAntitone f (NEMap k v m)
    | f k       = insertMinMap k v . M.takeWhileAntitone f $ m
    | otherwise = 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 f n@(NEMap k _ m)
    | f k       = M.dropWhileAntitone f m
    | otherwise = toMap 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 an 'Or' with potentially two non-empty maps:
--
-- *   @'Fst' n1@ means that the predicate never failed for any item,
--     returning the original map.
-- *   @'Snd' n2@ means that the predicate failed for the first item,
--     returning the original map.
-- *   @'Both' 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
    -> Or (NEMap k a) (NEMap k a)
spanAntitone f n@(NEMap k v m0)
    | f k       = case (nonEmptyMap m1, nonEmptyMap m2) of
        (Nothing, Nothing) -> Fst  n
        (Just _ , Nothing) -> Fst  n
        (Nothing, Just n2) -> Both (singleton k v)       n2
        (Just _ , Just n2) -> Both (insertMapMin k v m1) n2
    | otherwise = Snd n
  where
    (m1, m2) = M.spanAntitone f m0
{-# INLINABLE spanAntitone #-}

-- | /O(n)/. Map values and collect the 'Just' results.
--
-- Returns a potentially empty map ('Map'), because the function could
-- potentially return 'Nothing' on all items in the 'NEMap'.
--
-- > let f x = if x == "a" then Just "new a" else Nothing
-- > mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "new a"
mapMaybe
    :: (a -> Maybe b)
    -> NEMap k a
    -> Map k b
mapMaybe f = mapMaybeWithKey (const 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 f (NEMap k v m) = ($ M.mapMaybeWithKey f m)
                                . maybe id (insertMinMap k)
                                $ f k v
{-# INLINE mapMaybeWithKey #-}

-- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
--
-- Returns an 'Or' with potentially two non-empty maps:
--
-- *   @'Fst' n1@ means that the results were all 'Left'.
-- *   @'Snd' n2@ means that the results were all 'Right'.
-- *   @'Both' 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")]))
-- >     == Both (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")]))
-- >
-- > mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
-- >     == Snd (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
mapEither
    :: (a -> Either b c)
    -> NEMap k a
    -> Or (NEMap k b) (NEMap k c)
mapEither f = mapEitherWithKey (const f)
{-# INLINE mapEither #-}

-- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
--
-- Returns an 'Or' with potentially two non-empty maps:
--
-- *   @'Fst' n1@ means that the results were all 'Left'.
-- *   @'Snd' n2@ means that the results were all 'Right'.
-- *   @'Both' 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")]))
-- >     == Both (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")]))
-- >
-- > mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
-- >     == Snd (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))
mapEitherWithKey
    :: (k -> a -> Either b c)
    -> NEMap k a
    -> Or (NEMap k b) (NEMap k c)
mapEitherWithKey f (NEMap k v m0) = case (nonEmptyMap m1, nonEmptyMap m2) of
    (Nothing, Nothing) -> case f k v of
      Left  v' -> Fst  (singleton k v')
      Right v' -> Snd                         (singleton k v')
    (Just n1, Nothing) -> case f k v of
      Left  v' -> Fst  (insertMapMin k v' m1)
      Right v' -> Both n1                     (singleton k v')
    (Nothing, Just n2) -> case f k v of
      Left  v' -> Both (singleton k v')       n2
      Right v' -> Snd                         (insertMapMin k v' m2)
    (Just n1, Just n2) -> case f k v of
      Left  v' -> Both (insertMapMin k v' m1) n2
      Right v' -> Both n1                     (insertMapMin k v' m2)
  where
    (m1, m2) = M.mapEitherWithKey f m0
{-# INLINABLE mapEitherWithKey #-}

-- | /O(log n)/. The expression (@'split' k map@) is potentially a 'Both'
-- 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' ('Fst' 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' ('Snd' 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' ('Both' 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 (Snd  (fromList ((3,"b") :| [(5,"a")]))  )
-- > split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (Snd  (singleton 5 "a")                  )
-- > split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (Both (singleton 3 "b") (singleton 5 "a"))
-- > split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (Fst  (singleton 3 "b")                  )
-- > split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (Fst  (fromList ((3,"b") :| [(5,"a")]))  )
-- > split 5 (singleton 5 "a")                 == Nothing
split
    :: Ord k
    => k
    -> NEMap k a
    -> Maybe (Or (NEMap k a) (NEMap k a))
split k n@(NEMap k0 v m0) = case compare k k0 of
    LT -> Just $ Snd n
    EQ -> Snd <$> nonEmptyMap m0
    GT -> case (nonEmptyMap m1, nonEmptyMap m2) of
      (Nothing, Nothing) -> Just $ Fst  (singleton k0 v)
      (Just _ , Nothing) -> Just $ Fst  (insertMapMin k0 v m1)
      (Nothing, Just n2) -> Just $ Both (singleton k0 v)       n2
      (Just _ , Just n2) -> Just $ Both (insertMapMin k0 v m1) n2
  where
    (m1, m2) = M.split k m0
{-# INLINABLE split #-}

-- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
-- like 'split' but also returns @'lookup' k map@, as a @'Maybe' a@.
--
-- > splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == (Nothing , Just (Snd  (fromList ((3,"b") :| [(5,"a")]))))
-- > splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Just (Snd  (singleton 5 "a")))
-- > splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == (Nothing , Just (Both (singleton 3 "b") (singleton 5 "a")))
-- > splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "a", Just (Fst  (singleton 3 "b"))
-- > splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == (Nothing , Just (Fst  (fromList ((3,"b") :| [(5,"a")])))
-- > splitLookup 5 (singleton 5 "a")                 == (Just "a", Nothing)
splitLookup
    :: Ord k
    => k
    -> NEMap k a
    -> (Maybe a, Maybe (Or (NEMap k a) (NEMap k a)))
splitLookup k n@(NEMap k0 v0 m0) = case compare k k0 of
    LT -> (Nothing, Just $ Snd n)
    EQ -> (Just v0, Snd <$> nonEmptyMap m0)
    GT -> (v      ,) $ case (nonEmptyMap m1, nonEmptyMap m2) of
      (Nothing, Nothing) -> Just $ Fst  (singleton k0 v0)
      (Just _ , Nothing) -> Just $ Fst  (insertMapMin k0 v0 m1)
      (Nothing, Just n2) -> Just $ Both (singleton k0 v0)       n2
      (Just _ , Just n2) -> Just $ Both (insertMapMin k0 v0 m1) n2
  where
    (m1, v, m2) = M.splitLookup k m0
{-# INLINABLE splitLookup #-}

-- | /O(1)/.  Decompose a map into pieces based on the structure of the
-- underlying tree.  This function is useful for consuming a map in
-- parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this.  However, it is guaranteed that
-- the pieces returned will be in ascending order (all elements in the
-- first submap less than all elements in the second, and so on).
--
-- Note that the current implementation does not return more than four
-- submaps, but you should not depend on this behaviour because it can
-- change in the future without notice.
splitRoot
    :: NEMap k a
    -> NonEmpty (NEMap k a)
splitRoot (NEMap k v m) = singleton k v
                       :| Maybe.mapMaybe nonEmptyMap (M.splitRoot 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 = isSubmapOfBy (==)
{-# 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 f (NEMap k v m0) (toMap->m1) = kvSub
                                         && M.isSubmapOfBy f m0 m1
  where
    kvSub = case M.lookup k m1 of
      Just v0 -> f v v0
      Nothing -> 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 = isProperSubmapOfBy (==)
{-# 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 f m1 m2 = M.size (nemMap m1) < M.size (nemMap m2)
                          && isSubmapOfBy f m1 m2
{-# INLINE isProperSubmapOfBy #-}

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

-- | /O(log n)/. Return the /index/ of a key, which is its zero-based index
-- in the sequence sorted by keys. The index is a number from /0/ up to,
-- but not including, the 'size' of the map. Calls 'error' when the key is
-- not a 'member' of the map.
--
-- > findIndex 2 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map
-- > findIndex 3 (fromList ((5,"a") :| [(3,"b")])) == 0
-- > findIndex 5 (fromList ((5,"a") :| [(3,"b")])) == 1
-- > findIndex 6 (fromList ((5,"a") :| [(3,"b")]))    Error: element is not in the map
findIndex
    :: Ord k
    => k
    -> NEMap k a
    -> Int
findIndex k = fromMaybe e . lookupIndex k
  where
    e = error "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 0 (NEMap k v _) = (k, v)
elemAt i (NEMap _ _ m) = M.elemAt (i - 1) m
{-# INLINABLE elemAt #-}

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

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

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

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

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

-- | /O(log n)/. Split a map at a particular index @i@.
--
-- *   @'Fst' n1@ means that there are less than @i@ items in the map, and
--     @n1@ is the original map.
-- *   @'Snd' n2@ means @i@ was 0; we dropped 0 items, so @n2@ is the
--     original map.
-- *   @'Both' 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
    -> Or (NEMap k a) (NEMap k a)
splitAt 0 n                = Snd n
splitAt i n@(NEMap k v m0) = case (nonEmptyMap m1, nonEmptyMap m2) of
    (Nothing, Nothing) -> Fst  (singleton k v)
    (Just _ , Nothing) -> Fst  n
    (Nothing, Just n2) -> Both (singleton k v)       n2
    (Just _ , Just n2) -> Both (insertMapMin k v m1) n2
  where
    (m1, m2) = M.splitAt (i - 1) m0
{-# INLINABLE splitAt #-}

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

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

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

-- | /O(log n)/. Delete the maximal key. Returns a potentially empty map
-- ('Map'), because we might end up deleting the final key in a singleton
-- map.
--
-- > deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.Map.fromList [(3,"b"), (5,"a")]
-- > deleteMax (singleton 5 "a") == Data.Map.empty
deleteMax :: NEMap k a -> Map k a
deleteMax (NEMap k v m) = insertMinMap k v . M.deleteMax $ 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 f = updateMinWithKey (const 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 f = adjustMinWithKey (const 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 f (NEMap k v m) = ($ m) . maybe id (insertMinMap k) $ f k v
{-# INLINE updateMinWithKey #-}

-- | /O(1)/. A version of 'adjustMaxWithKey' that disallows deletion,
-- allowing us to guarantee that the result is also non-empty.  Note that
-- it also is able to have better asymptotics than 'updateMinWithKey' in
-- general.
adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a
adjustMinWithKey f (NEMap k v m) = NEMap k (f k v) 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 f = updateMaxWithKey (const 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 f = adjustMaxWithKey (const 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 f (NEMap k v m)
    | M.null m  = maybe m (M.singleton k) $ f k v
    | otherwise = insertMinMap k v
                . M.updateMaxWithKey f
                $ 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 f (NEMap k0 v m)
    | M.null m  = NEMap k0 (f k0 v) m
    | otherwise = insertMapMin k0 v
                . M.updateMaxWithKey (\k -> Just . f k)
                $ 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 = first snd . deleteFindMin
{-# INLINE minView #-}

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

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

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

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

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