{-# LANGUAGE DataKinds #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}

-- |
-- Copyright: © 2018-2020 IOHK
-- License: Apache-2.0
--
-- Provides a strict implementation of a non-empty map.
--
-- This implementation is based on the implementation of 'Data.Map.Strict'
-- provided by the 'containers' package, but provides an extra guarantee
-- that the map contains at least one entry at all times.
--
module Data.Map.Strict.NonEmptyMap.Internal
    (
    -- * Map type

      -- Important:
      --
      -- The default data constructor for 'NonEmptyMap' is not exported, by
      -- design, as the internal data structure has an invariant that must be
      -- preserved across all operations.
      --
      -- Exporting the default constructor would make it possible for functions
      -- outside this module to break the invariant, opening the door to subtle
      -- regressions.
      --
      -- See the definition of 'NonEmptyMap' for more details of the invariant.
      --
      -- To construct a 'NonEmptyMap', use one of the provided constructors,
      -- all of which are tested to check that they respect the invariant.
      --
      NonEmptyMap

    -- * Construction
    , fromList
    , fromMap
    , singleton

    -- * Deconstruction
    , toList
    , toMap

    -- * Insertion
    , insert

    -- * Deletion
    , delete

    -- * Lookup
    , lookup

    -- * Combination
    , unionWith

    -- * Internal functions
    , invariantHolds

    ) where

import Prelude hiding
    ( lookup )

import Control.DeepSeq
    ( NFData )
import Data.Hashable
    ( Hashable (..), hashUsing )
import Data.List.NonEmpty
    ( NonEmpty (..) )
import Data.Map.Strict
    ( Map )
import GHC.Generics
    ( Generic (..) )

import qualified Data.Foldable as F
import qualified Data.Map.Strict as Map

-- | A non-empty map from keys of type 'k' to values of type 'v'.
--
data NonEmptyMap k v = NonEmptyMap
    { NonEmptyMap k v -> (k, v)
least
        :: !(k, v)
      -- ^ Invariant: this key must be less than than all the keys in 'rest'.
    , NonEmptyMap k v -> Map k v
rest
        :: !(Map.Map k v)
    }
    deriving (NonEmptyMap k v -> NonEmptyMap k v -> Bool
(NonEmptyMap k v -> NonEmptyMap k v -> Bool)
-> (NonEmptyMap k v -> NonEmptyMap k v -> Bool)
-> Eq (NonEmptyMap k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v.
(Eq k, Eq v) =>
NonEmptyMap k v -> NonEmptyMap k v -> Bool
/= :: NonEmptyMap k v -> NonEmptyMap k v -> Bool
$c/= :: forall k v.
(Eq k, Eq v) =>
NonEmptyMap k v -> NonEmptyMap k v -> Bool
== :: NonEmptyMap k v -> NonEmptyMap k v -> Bool
$c== :: forall k v.
(Eq k, Eq v) =>
NonEmptyMap k v -> NonEmptyMap k v -> Bool
Eq, NonEmptyMap k a -> Bool
(a -> m) -> NonEmptyMap k a -> m
(a -> b -> b) -> b -> NonEmptyMap k a -> b
(forall m. Monoid m => NonEmptyMap k m -> m)
-> (forall m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m)
-> (forall m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m)
-> (forall a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b)
-> (forall a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b)
-> (forall b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b)
-> (forall b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b)
-> (forall a. (a -> a -> a) -> NonEmptyMap k a -> a)
-> (forall a. (a -> a -> a) -> NonEmptyMap k a -> a)
-> (forall a. NonEmptyMap k a -> [a])
-> (forall a. NonEmptyMap k a -> Bool)
-> (forall a. NonEmptyMap k a -> Int)
-> (forall a. Eq a => a -> NonEmptyMap k a -> Bool)
-> (forall a. Ord a => NonEmptyMap k a -> a)
-> (forall a. Ord a => NonEmptyMap k a -> a)
-> (forall a. Num a => NonEmptyMap k a -> a)
-> (forall a. Num a => NonEmptyMap k a -> a)
-> Foldable (NonEmptyMap k)
forall a. Eq a => a -> NonEmptyMap k a -> Bool
forall a. Num a => NonEmptyMap k a -> a
forall a. Ord a => NonEmptyMap k a -> a
forall m. Monoid m => NonEmptyMap k m -> m
forall a. NonEmptyMap k a -> Bool
forall a. NonEmptyMap k a -> Int
forall a. NonEmptyMap k a -> [a]
forall a. (a -> a -> a) -> NonEmptyMap k a -> a
forall k a. Eq a => a -> NonEmptyMap k a -> Bool
forall k a. Num a => NonEmptyMap k a -> a
forall k a. Ord a => NonEmptyMap k a -> a
forall m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m
forall k m. Monoid m => NonEmptyMap k m -> m
forall k a. NonEmptyMap k a -> Bool
forall k a. NonEmptyMap k a -> Int
forall k a. NonEmptyMap k a -> [a]
forall b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b
forall a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b
forall k a. (a -> a -> a) -> NonEmptyMap k a -> a
forall k m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m
forall k b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b
forall k a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: NonEmptyMap k a -> a
$cproduct :: forall k a. Num a => NonEmptyMap k a -> a
sum :: NonEmptyMap k a -> a
$csum :: forall k a. Num a => NonEmptyMap k a -> a
minimum :: NonEmptyMap k a -> a
$cminimum :: forall k a. Ord a => NonEmptyMap k a -> a
maximum :: NonEmptyMap k a -> a
$cmaximum :: forall k a. Ord a => NonEmptyMap k a -> a
elem :: a -> NonEmptyMap k a -> Bool
$celem :: forall k a. Eq a => a -> NonEmptyMap k a -> Bool
length :: NonEmptyMap k a -> Int
$clength :: forall k a. NonEmptyMap k a -> Int
null :: NonEmptyMap k a -> Bool
$cnull :: forall k a. NonEmptyMap k a -> Bool
toList :: NonEmptyMap k a -> [a]
$ctoList :: forall k a. NonEmptyMap k a -> [a]
foldl1 :: (a -> a -> a) -> NonEmptyMap k a -> a
$cfoldl1 :: forall k a. (a -> a -> a) -> NonEmptyMap k a -> a
foldr1 :: (a -> a -> a) -> NonEmptyMap k a -> a
$cfoldr1 :: forall k a. (a -> a -> a) -> NonEmptyMap k a -> a
foldl' :: (b -> a -> b) -> b -> NonEmptyMap k a -> b
$cfoldl' :: forall k b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b
foldl :: (b -> a -> b) -> b -> NonEmptyMap k a -> b
$cfoldl :: forall k b a. (b -> a -> b) -> b -> NonEmptyMap k a -> b
foldr' :: (a -> b -> b) -> b -> NonEmptyMap k a -> b
$cfoldr' :: forall k a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b
foldr :: (a -> b -> b) -> b -> NonEmptyMap k a -> b
$cfoldr :: forall k a b. (a -> b -> b) -> b -> NonEmptyMap k a -> b
foldMap' :: (a -> m) -> NonEmptyMap k a -> m
$cfoldMap' :: forall k m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m
foldMap :: (a -> m) -> NonEmptyMap k a -> m
$cfoldMap :: forall k m a. Monoid m => (a -> m) -> NonEmptyMap k a -> m
fold :: NonEmptyMap k m -> m
$cfold :: forall k m. Monoid m => NonEmptyMap k m -> m
Foldable, a -> NonEmptyMap k b -> NonEmptyMap k a
(a -> b) -> NonEmptyMap k a -> NonEmptyMap k b
(forall a b. (a -> b) -> NonEmptyMap k a -> NonEmptyMap k b)
-> (forall a b. a -> NonEmptyMap k b -> NonEmptyMap k a)
-> Functor (NonEmptyMap k)
forall a b. a -> NonEmptyMap k b -> NonEmptyMap k a
forall a b. (a -> b) -> NonEmptyMap k a -> NonEmptyMap k b
forall k a b. a -> NonEmptyMap k b -> NonEmptyMap k a
forall k a b. (a -> b) -> NonEmptyMap k a -> NonEmptyMap k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> NonEmptyMap k b -> NonEmptyMap k a
$c<$ :: forall k a b. a -> NonEmptyMap k b -> NonEmptyMap k a
fmap :: (a -> b) -> NonEmptyMap k a -> NonEmptyMap k b
$cfmap :: forall k a b. (a -> b) -> NonEmptyMap k a -> NonEmptyMap k b
Functor, (forall x. NonEmptyMap k v -> Rep (NonEmptyMap k v) x)
-> (forall x. Rep (NonEmptyMap k v) x -> NonEmptyMap k v)
-> Generic (NonEmptyMap k v)
forall x. Rep (NonEmptyMap k v) x -> NonEmptyMap k v
forall x. NonEmptyMap k v -> Rep (NonEmptyMap k v) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k v x. Rep (NonEmptyMap k v) x -> NonEmptyMap k v
forall k v x. NonEmptyMap k v -> Rep (NonEmptyMap k v) x
$cto :: forall k v x. Rep (NonEmptyMap k v) x -> NonEmptyMap k v
$cfrom :: forall k v x. NonEmptyMap k v -> Rep (NonEmptyMap k v) x
Generic, ReadPrec [NonEmptyMap k v]
ReadPrec (NonEmptyMap k v)
Int -> ReadS (NonEmptyMap k v)
ReadS [NonEmptyMap k v]
(Int -> ReadS (NonEmptyMap k v))
-> ReadS [NonEmptyMap k v]
-> ReadPrec (NonEmptyMap k v)
-> ReadPrec [NonEmptyMap k v]
-> Read (NonEmptyMap k v)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall k v. (Read k, Read v, Ord k) => ReadPrec [NonEmptyMap k v]
forall k v. (Read k, Read v, Ord k) => ReadPrec (NonEmptyMap k v)
forall k v.
(Read k, Read v, Ord k) =>
Int -> ReadS (NonEmptyMap k v)
forall k v. (Read k, Read v, Ord k) => ReadS [NonEmptyMap k v]
readListPrec :: ReadPrec [NonEmptyMap k v]
$creadListPrec :: forall k v. (Read k, Read v, Ord k) => ReadPrec [NonEmptyMap k v]
readPrec :: ReadPrec (NonEmptyMap k v)
$creadPrec :: forall k v. (Read k, Read v, Ord k) => ReadPrec (NonEmptyMap k v)
readList :: ReadS [NonEmptyMap k v]
$creadList :: forall k v. (Read k, Read v, Ord k) => ReadS [NonEmptyMap k v]
readsPrec :: Int -> ReadS (NonEmptyMap k v)
$creadsPrec :: forall k v.
(Read k, Read v, Ord k) =>
Int -> ReadS (NonEmptyMap k v)
Read, Int -> NonEmptyMap k v -> ShowS
[NonEmptyMap k v] -> ShowS
NonEmptyMap k v -> String
(Int -> NonEmptyMap k v -> ShowS)
-> (NonEmptyMap k v -> String)
-> ([NonEmptyMap k v] -> ShowS)
-> Show (NonEmptyMap k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> NonEmptyMap k v -> ShowS
forall k v. (Show k, Show v) => [NonEmptyMap k v] -> ShowS
forall k v. (Show k, Show v) => NonEmptyMap k v -> String
showList :: [NonEmptyMap k v] -> ShowS
$cshowList :: forall k v. (Show k, Show v) => [NonEmptyMap k v] -> ShowS
show :: NonEmptyMap k v -> String
$cshow :: forall k v. (Show k, Show v) => NonEmptyMap k v -> String
showsPrec :: Int -> NonEmptyMap k v -> ShowS
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> NonEmptyMap k v -> ShowS
Show, Functor (NonEmptyMap k)
Foldable (NonEmptyMap k)
Functor (NonEmptyMap k)
-> Foldable (NonEmptyMap k)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    NonEmptyMap k (f a) -> f (NonEmptyMap k a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> NonEmptyMap k a -> m (NonEmptyMap k b))
-> (forall (m :: * -> *) a.
    Monad m =>
    NonEmptyMap k (m a) -> m (NonEmptyMap k a))
-> Traversable (NonEmptyMap k)
(a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b)
forall k. Functor (NonEmptyMap k)
forall k. Foldable (NonEmptyMap k)
forall k (m :: * -> *) a.
Monad m =>
NonEmptyMap k (m a) -> m (NonEmptyMap k a)
forall k (f :: * -> *) a.
Applicative f =>
NonEmptyMap k (f a) -> f (NonEmptyMap k a)
forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NonEmptyMap k a -> m (NonEmptyMap k b)
forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
NonEmptyMap k (m a) -> m (NonEmptyMap k a)
forall (f :: * -> *) a.
Applicative f =>
NonEmptyMap k (f a) -> f (NonEmptyMap k a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NonEmptyMap k a -> m (NonEmptyMap k b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b)
sequence :: NonEmptyMap k (m a) -> m (NonEmptyMap k a)
$csequence :: forall k (m :: * -> *) a.
Monad m =>
NonEmptyMap k (m a) -> m (NonEmptyMap k a)
mapM :: (a -> m b) -> NonEmptyMap k a -> m (NonEmptyMap k b)
$cmapM :: forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> NonEmptyMap k a -> m (NonEmptyMap k b)
sequenceA :: NonEmptyMap k (f a) -> f (NonEmptyMap k a)
$csequenceA :: forall k (f :: * -> *) a.
Applicative f =>
NonEmptyMap k (f a) -> f (NonEmptyMap k a)
traverse :: (a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b)
$ctraverse :: forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> NonEmptyMap k a -> f (NonEmptyMap k b)
$cp2Traversable :: forall k. Foldable (NonEmptyMap k)
$cp1Traversable :: forall k. Functor (NonEmptyMap k)
Traversable)

instance (NFData k, NFData v) => NFData (NonEmptyMap k v)
instance (Hashable k, Hashable v) => Hashable (NonEmptyMap k v) where
    hashWithSalt :: Int -> NonEmptyMap k v -> Int
hashWithSalt = (NonEmptyMap k v -> NonEmpty (k, v))
-> Int -> NonEmptyMap k v -> Int
forall b a. Hashable b => (a -> b) -> Int -> a -> Int
hashUsing NonEmptyMap k v -> NonEmpty (k, v)
forall k v. NonEmptyMap k v -> NonEmpty (k, v)
toList

-- | Builds a non-empty map from a list of key-value pairs.
--
-- If the list contains more than one value for the same key, the last value
-- for the key is retained.
--
fromList :: Ord k => NonEmpty (k, v) -> NonEmptyMap k v
fromList :: NonEmpty (k, v) -> NonEmptyMap k v
fromList ((k, v)
x :| [(k, v)]
xs) =
    (NonEmptyMap k v -> (k, v) -> NonEmptyMap k v)
-> NonEmptyMap k v -> [(k, v)] -> NonEmptyMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' (\NonEmptyMap k v
m (k
k, v
v) -> k -> v -> NonEmptyMap k v -> NonEmptyMap k v
forall k v. Ord k => k -> v -> NonEmptyMap k v -> NonEmptyMap k v
insert k
k v
v NonEmptyMap k v
m) ((k -> v -> NonEmptyMap k v) -> (k, v) -> NonEmptyMap k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> NonEmptyMap k v
forall k v. Ord k => k -> v -> NonEmptyMap k v
singleton (k, v)
x) [(k, v)]
xs

-- | Builds a non-empty map from the given map.
--
-- If the given map is empty, this function returns 'Nothing'.
--
fromMap :: Map k v -> Maybe (NonEmptyMap k v)
fromMap :: Map k v -> Maybe (NonEmptyMap k v)
fromMap = (((k, v), Map k v) -> NonEmptyMap k v)
-> Maybe ((k, v), Map k v) -> Maybe (NonEmptyMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (((k, v) -> Map k v -> NonEmptyMap k v)
-> ((k, v), Map k v) -> NonEmptyMap k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap) (Maybe ((k, v), Map k v) -> Maybe (NonEmptyMap k v))
-> (Map k v -> Maybe ((k, v), Map k v))
-> Map k v
-> Maybe (NonEmptyMap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Maybe ((k, v), Map k v)
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.minViewWithKey

-- | Converts a non-empty map to a list of key-value pairs.
--
toList :: NonEmptyMap k v -> NonEmpty (k, v)
toList :: NonEmptyMap k v -> NonEmpty (k, v)
toList NonEmptyMap k v
m = NonEmptyMap k v -> (k, v)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k v
m (k, v) -> [(k, v)] -> NonEmpty (k, v)
forall a. a -> [a] -> NonEmpty a
:| Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toList (NonEmptyMap k v -> Map k v
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k v
m)

-- | Converts a non-empty map to an ordinary map.
--
toMap :: Ord k => NonEmptyMap k v -> Map k v
toMap :: NonEmptyMap k v -> Map k v
toMap NonEmptyMap k v
m = (k -> v -> Map k v -> Map k v) -> (k, v) -> Map k v -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v -> Map k v
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert (NonEmptyMap k v -> (k, v)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k v
m) (NonEmptyMap k v -> Map k v
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k v
m)

-- | Inserts 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 :: Ord k => k -> v -> NonEmptyMap k v -> NonEmptyMap k v
insert :: k -> v -> NonEmptyMap k v -> NonEmptyMap k v
insert k
k v
v NonEmptyMap k v
m
    | k
k k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< (k, v) -> k
forall a b. (a, b) -> a
fst (NonEmptyMap k v -> (k, v)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k v
m) =
        (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k, v
v) ((k -> v -> Map k v -> Map k v) -> (k, v) -> Map k v -> Map k v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> v -> Map k v -> Map k v
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert (NonEmptyMap k v -> (k, v)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k v
m) (NonEmptyMap k v -> Map k v
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k v
m))
    | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== (k, v) -> k
forall a b. (a, b) -> a
fst (NonEmptyMap k v -> (k, v)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k v
m) =
        (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k, v
v) (NonEmptyMap k v -> Map k v
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k v
m)
    | Bool
otherwise =
        NonEmptyMap k v
m {rest :: Map k v
rest = k -> v -> Map k v -> Map k v
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k v
v (NonEmptyMap k v -> Map k v
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k v
m)}

-- | Deletes a key and its value from the map.
--
-- When the key is not a member of the map, the original map is returned.
--
-- This function returns 'Nothing' if the delete operation reduces the number
-- of elements to zero.
--
delete :: Ord k => k -> NonEmptyMap k a -> Maybe (NonEmptyMap k a)
delete :: k -> NonEmptyMap k a -> Maybe (NonEmptyMap k a)
delete k
k NonEmptyMap k a
m
    | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== (k, a) -> k
forall a b. (a, b) -> a
fst (NonEmptyMap k a -> (k, a)
forall k v. NonEmptyMap k v -> (k, v)
least NonEmptyMap k a
m) = Map k a -> Maybe (NonEmptyMap k a)
forall k v. Map k v -> Maybe (NonEmptyMap k v)
fromMap (Map k a -> Maybe (NonEmptyMap k a))
-> Map k a -> Maybe (NonEmptyMap k a)
forall a b. (a -> b) -> a -> b
$ NonEmptyMap k a -> Map k a
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k a
m
    | Bool
otherwise = NonEmptyMap k a -> Maybe (NonEmptyMap k a)
forall a. a -> Maybe a
Just NonEmptyMap k a
m { rest :: Map k a
rest = k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ NonEmptyMap k a -> Map k a
forall k v. NonEmptyMap k v -> Map k v
rest NonEmptyMap k a
m }

-- | Looks up the value of a key in the map.
--
-- This function will return the corresponding value as '(Just value)',
-- or 'Nothing' if the key isn't in the map.
--
lookup :: Ord k => k -> NonEmptyMap k v -> Maybe v
lookup :: k -> NonEmptyMap k v -> Maybe v
lookup k
k (NonEmptyMap (k
k1, v
v1) Map k v
r)
    | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k1 = v -> Maybe v
forall a. a -> Maybe a
Just v
v1
    | Bool
otherwise = k -> Map k v -> Maybe v
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup k
k Map k v
r

-- | Creates a map with a single element.
--
singleton :: Ord k => k -> v -> NonEmptyMap k v
singleton :: k -> v -> NonEmptyMap k v
singleton k
k v
v = (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k, v
v) Map k v
forall a. Monoid a => a
mempty

-- | Finds the union of two maps, with the given combining function.
--
unionWith
    :: Ord k
    => (v -> v -> v)
    -> NonEmptyMap k v
    -> NonEmptyMap k v
    -> NonEmptyMap k v
unionWith :: (v -> v -> v)
-> NonEmptyMap k v -> NonEmptyMap k v -> NonEmptyMap k v
unionWith v -> v -> v
combine (NonEmptyMap (k
k1, v
v1) Map k v
r1) (NonEmptyMap (k
k2, v
v2) Map k v
r2)
    | k
k1 k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k2 =
        (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k1, v
v1) ((v -> v -> v) -> k -> v -> Map k v -> Map k v
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith v -> v -> v
combine k
k2 v
v2 Map k v
r)
    | k
k1 k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k2 =
        (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k2, v
v2) ((v -> v -> v) -> k -> v -> Map k v -> Map k v
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith v -> v -> v
combine k
k1 v
v1 Map k v
r)
    | Bool
otherwise =
        (k, v) -> Map k v -> NonEmptyMap k v
forall k v. (k, v) -> Map k v -> NonEmptyMap k v
NonEmptyMap (k
k1, v -> v -> v
combine v
v1 v
v2) Map k v
r
  where
    r :: Map k v
r = (v -> v -> v) -> Map k v -> Map k v -> Map k v
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith v -> v -> v
combine Map k v
r1 Map k v
r2

--------------------------------------------------------------------------------
-- Internal functions
--------------------------------------------------------------------------------

-- | Returns true if and only if the invariant holds for the given map.
--
invariantHolds :: Ord k => NonEmptyMap k v -> Bool
invariantHolds :: NonEmptyMap k v -> Bool
invariantHolds NonEmptyMap {(k, v)
least :: (k, v)
least :: forall k v. NonEmptyMap k v -> (k, v)
least, Map k v
rest :: Map k v
rest :: forall k v. NonEmptyMap k v -> Map k v
rest} =
    case Map k v -> Maybe (k, v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin Map k v
rest  of
        Maybe (k, v)
Nothing ->
            Bool
True
        Just (k, v)
nextSmallest ->
            (k, v) -> k
forall a b. (a, b) -> a
fst (k, v)
least k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< (k, v) -> k
forall a b. (a, b) -> a
fst (k, v)
nextSmallest