{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE DataKinds           #-}
{-# LANGUAGE DeriveFunctor       #-}
{-# LANGUAGE GADTs               #-}
{-# LANGUAGE LambdaCase          #-}
{-# LANGUAGE MagicHash           #-}
{-# LANGUAGE MonadComprehensions #-}
{-# LANGUAGE RoleAnnotations     #-}
{-# LANGUAGE TypeFamilies        #-}

-- | This module doesn't respect the PVP!
-- Breaking changes may happen at any minor version (>= *.*.m.*)

module Data.POMap.Internal where

import           Algebra.PartialOrd
import           Control.Arrow      (first, second, (***))
import           Control.DeepSeq    (NFData (rnf))
import qualified Data.List          as List
import           Data.List.NonEmpty      (NonEmpty (..))
import qualified Data.List.NonEmpty      as NonEmpty
import           Data.Map.Internal  (AreWeStrict (..), Map (..))
import qualified Data.Map.Internal  as Map
import qualified Data.Map.Lazy      as Map.Lazy
import qualified Data.Map.Strict    as Map.Strict
import           Data.Maybe         (fromMaybe)
import qualified Data.Maybe         as Maybe
import           Data.Monoid        (Alt (..), Any (..))
import           GHC.Exts           (Proxy#, inline, proxy#)
import qualified GHC.Exts
import           GHC.Magic          (oneShot)
import           Prelude            hiding (filter, lookup, map)
import           Text.Read          (Lexeme (Ident), Read (..), lexP, parens,
                                     prec, readListPrecDefault)

-- $setup
-- This is some setup code for @doctest@.
-- >>> :set -XGeneralizedNewtypeDeriving
-- >>> import           Algebra.PartialOrd
-- >>> import           Data.POMap.Lazy
-- >>> import           Data.POMap.Internal
-- >>> :{
--   newtype Divisibility
--     = Div Int
--     deriving (Eq, Num)
--   instance Show Divisibility where
--     show (Div a) = show a
--   instance PartialOrd Divisibility where
--     Div a `leq` Div b = b `mod` a == 0
--   type DivMap a = POMap Divisibility a
--   default (Divisibility, DivMap String)
-- :}

-- | Allows us to abstract over value-strictness in a zero-cost manner.
-- GHC should always be able to specialise the two instances of this and
-- consequently inline 'areWeStrict'.
--
-- It's a little sad we can't just use regular singletons, for reasons
-- outlined [here](https://stackoverflow.com/questions/45734362/specialization-of-singleton-parameters).
class SingIAreWeStrict (s :: AreWeStrict) where
  areWeStrict :: Proxy# s -> AreWeStrict

instance SingIAreWeStrict 'Strict where
  areWeStrict :: Proxy# 'Strict -> AreWeStrict
areWeStrict Proxy# 'Strict
_ = AreWeStrict
Strict

instance SingIAreWeStrict 'Lazy where
  areWeStrict :: Proxy# 'Lazy -> AreWeStrict
areWeStrict Proxy# 'Lazy
_ = AreWeStrict
Lazy

-- | Should be inlined and specialised at all call sites.
seq' :: SingIAreWeStrict s => Proxy# s -> a -> b -> b
seq' :: Proxy# s -> a -> b -> b
seq' Proxy# s
p a
a b
b
  | AreWeStrict
Lazy <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
p = b
b
  | Bool
otherwise = a -> b -> b
seq a
a b
b
{-# INLINE seq' #-}

seqList :: [a] -> [a]
seqList :: [a] -> [a]
seqList [a]
xs = (a -> [a] -> [a]) -> [a] -> [a] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> [a] -> [a]
seq [a]
xs [a]
xs

-- | A map from partially-ordered keys @k@ to values @v@.
data POMap k v = POMap !Int ![Map k v]

type role POMap nominal representational

-- | Internal smart constructor so that we can be sure that we are always
-- spine-strict, discard empty maps and have appropriate size information.
mkPOMap :: [Map k v] -> POMap k v
mkPOMap :: [Map k v] -> POMap k v
mkPOMap [Map k v]
decomp = Int -> [Map k v] -> POMap k v
forall k v. Int -> [Map k v] -> POMap k v
POMap ((Map k v -> Int -> Int) -> Int -> [Map k v] -> Int
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Int -> Int -> Int) -> (Map k v -> Int) -> Map k v -> Int -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Int
forall k a. Map k a -> Int
Map.size) Int
0 [Map k v]
decomp') [Map k v]
decomp'
  where
    decomp' :: [Map k v]
decomp' = [Map k v] -> [Map k v]
forall a. [a] -> [a]
seqList ((Map k v -> Bool) -> [Map k v] -> [Map k v]
forall a. (a -> Bool) -> [a] -> [a]
List.filter (Bool -> Bool
not (Bool -> Bool) -> (Map k v -> Bool) -> Map k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map k v -> Bool
forall k a. Map k a -> Bool
Map.null) [Map k v]
decomp)
{-# INLINE mkPOMap #-}

chainDecomposition :: POMap k v -> [Map k v]
chainDecomposition :: POMap k v -> [Map k v]
chainDecomposition (POMap Int
_ [Map k v]
cd) = [Map k v]
cd
{-# INLINE chainDecomposition #-}

--
-- * Instances
--

instance (Show k, Show v) => Show (POMap k v) where
  showsPrec :: Int -> POMap k v -> ShowS
showsPrec Int
d POMap k v
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (POMap k v -> [(k, v)]
forall k v. POMap k v -> [(k, v)]
toList POMap k v
m)

instance (PartialOrd k, Read k, Read e) => Read (POMap k e) where
  readPrec :: ReadPrec (POMap k e)
readPrec = ReadPrec (POMap k e) -> ReadPrec (POMap k e)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (POMap k e) -> ReadPrec (POMap k e))
-> ReadPrec (POMap k e) -> ReadPrec (POMap k e)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (POMap k e) -> ReadPrec (POMap k e)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (POMap k e) -> ReadPrec (POMap k e))
-> ReadPrec (POMap k e) -> ReadPrec (POMap k e)
forall a b. (a -> b) -> a -> b
$ do
    Ident String
"fromList" <- ReadPrec Lexeme
lexP
    Proxy# 'Lazy -> [(k, e)] -> POMap k e
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> [(k, v)] -> POMap k v
fromListImpl (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) ([(k, e)] -> POMap k e)
-> ReadPrec [(k, e)] -> ReadPrec (POMap k e)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReadPrec [(k, e)]
forall a. Read a => ReadPrec a
readPrec

  readListPrec :: ReadPrec [POMap k e]
readListPrec = ReadPrec [POMap k e]
forall a. Read a => ReadPrec [a]
readListPrecDefault

-- | \(\mathcal{O}(wn\log n)\), where \(w=\max(w_1,w_2)), n=\max(n_1,n_2)\).
instance (PartialOrd k, Eq v) => Eq (POMap k v) where
  POMap k v
a == :: POMap k v -> POMap k v -> Bool
== POMap k v
b
    | POMap k v -> Int
forall k v. POMap k v -> Int
size POMap k v
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= POMap k v -> Int
forall k v. POMap k v -> Int
size POMap k v
b = Bool
False
    | Bool
otherwise = POMap k v -> POMap k v -> Bool
forall k v. (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
isSubmapOf POMap k v
a POMap k v
b Bool -> Bool -> Bool
&& POMap k v -> POMap k v -> Bool
forall k v. (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
isSubmapOf POMap k v
b POMap k v
a

-- | \(\mathcal{O}(wn\log n)\), where \(w=\max(w_1,w_2)), n=\max(n_1,n_2)\).
instance (PartialOrd k, PartialOrd v) => PartialOrd (POMap k v) where
  POMap k v
a leq :: POMap k v -> POMap k v -> Bool
`leq` POMap k v
b = (v -> v -> Bool) -> POMap k v -> POMap k v -> Bool
forall k a b.
PartialOrd k =>
(a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isSubmapOfBy v -> v -> Bool
forall a. PartialOrd a => a -> a -> Bool
leq POMap k v
a POMap k v
b

instance (NFData k, NFData v) => NFData (POMap k v) where
  rnf :: POMap k v -> ()
rnf (POMap Int
_ [Map k v]
d) = [Map k v] -> ()
forall a. NFData a => a -> ()
rnf [Map k v]
d

instance PartialOrd k => GHC.Exts.IsList (POMap k v) where
  type Item (POMap k v) = (k, v)
  fromList :: [Item (POMap k v)] -> POMap k v
fromList = Proxy# 'Lazy -> [(k, v)] -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> [(k, v)] -> POMap k v
fromListImpl (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy)
  toList :: POMap k v -> [Item (POMap k v)]
toList = POMap k v -> [Item (POMap k v)]
forall k v. POMap k v -> [(k, v)]
toList

instance Functor (POMap k) where
  fmap :: (a -> b) -> POMap k a -> POMap k b
fmap = Proxy# 'Lazy -> (a -> b) -> POMap k a -> POMap k b
forall (s :: AreWeStrict) a b k.
SingIAreWeStrict s =>
Proxy# s -> (a -> b) -> POMap k a -> POMap k b
map (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy)
  a
a <$ :: a -> POMap k b -> POMap k a
<$ (POMap Int
_ [Map k b]
d) = [Map k a] -> POMap k a
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k b -> Map k a) -> [Map k b] -> [Map k a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a
a a -> Map k b -> Map k a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$) [Map k b]
d)

instance Foldable (POMap k) where
  foldr :: (a -> b -> b) -> b -> POMap k a -> b
foldr a -> b -> b
f b
acc = (Map k a -> b -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr ((b -> Map k a -> b) -> Map k a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> b) -> b -> Map k a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr a -> b -> b
f)) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
  {-# INLINE foldr #-}
  foldl :: (b -> a -> b) -> b -> POMap k a -> b
foldl b -> a -> b
f b
acc = (b -> Map k a -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl ((b -> a -> b) -> b -> Map k a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl b -> a -> b
f) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
  {-# INLINE foldl #-}
  foldMap :: (a -> m) -> POMap k a -> m
foldMap a -> m
f (POMap Int
_ [Map k a]
d) = (Map k a -> m) -> [Map k a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((a -> m) -> Map k a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f) [Map k a]
d
  {-# INLINE foldMap #-}
  null :: POMap k a -> Bool
null POMap k a
m = POMap k a -> Int
forall k v. POMap k v -> Int
size POMap k a
m Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0
  {-# INLINE null #-}
  length :: POMap k a -> Int
length = POMap k a -> Int
forall k v. POMap k v -> Int
size
  {-# INLINE length #-}

instance Traversable (POMap k) where
  traverse :: (a -> f b) -> POMap k a -> f (POMap k b)
traverse a -> f b
f = Proxy# 'Lazy -> (k -> a -> f b) -> POMap k a -> f (POMap k b)
forall (t :: * -> *) (s :: AreWeStrict) k a b.
(Applicative t, SingIAreWeStrict s) =>
Proxy# s -> (k -> a -> t b) -> POMap k a -> t (POMap k b)
traverseWithKey (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) ((a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const a -> f b
f)
  {-# INLINE traverse #-}

--
-- * Query
--

-- | \(\mathcal{O}(1)\). The number of elements in this map.
size :: POMap k v -> Int
size :: POMap k v -> Int
size (POMap Int
s [Map k v]
_) = Int
s
{-# INLINE size #-}

-- | \(\mathcal{O}(w)\).
-- The width \(w\) of the chain decomposition in the internal
-- data structure.
-- This is always at least as big as the size of the biggest possible
-- anti-chain.
width :: POMap k v -> Int
width :: POMap k v -> Int
width = [Map k v] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([Map k v] -> Int) -> (POMap k v -> [Map k v]) -> POMap k v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE width #-}

foldEntry :: (Monoid m, PartialOrd k) => k -> (v -> m) -> POMap k v -> m
foldEntry :: k -> (v -> m) -> POMap k v -> m
foldEntry !k
k !v -> m
f = (Map k v -> m) -> [Map k v] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Map k v -> m
find ([Map k v] -> m) -> (POMap k v -> [Map k v]) -> POMap k v -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
  where
    find :: Map k v -> m
find Map k v
Tip = m
forall a. Monoid a => a
mempty
    find (Bin Int
_ k
k' v
v Map k v
l Map k v
r) =
      case (k
k k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k', k
k' k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k) of
        (Bool
True, Bool
True)   -> v -> m
f v
v
        (Bool
True, Bool
False)  -> Map k v -> m
find Map k v
l
        (Bool
False, Bool
True)  -> Map k v -> m
find Map k v
r
        (Bool
False, Bool
False) -> m
forall a. Monoid a => a
mempty
{-# INLINE foldEntry #-}

-- | \(\mathcal{O}(w\log n)\).
-- Is the key a member of the map?
lookup :: PartialOrd k => k -> POMap k v -> Maybe v
lookup :: k -> POMap k v -> Maybe v
lookup !k
k = Alt Maybe v -> Maybe v
forall k (f :: k -> *) (a :: k). Alt f a -> f a
getAlt (Alt Maybe v -> Maybe v)
-> (POMap k v -> Alt Maybe v) -> POMap k v -> Maybe v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> (v -> Alt Maybe v) -> POMap k v -> Alt Maybe v
forall m k v.
(Monoid m, PartialOrd k) =>
k -> (v -> m) -> POMap k v -> m
foldEntry k
k v -> Alt Maybe v
forall (f :: * -> *) a. Applicative f => a -> f a
pure
{-# INLINABLE lookup #-}

-- | \(\mathcal{O}(w\log n)\).
-- Is the key a member of the map? See also 'notMember'.
--
-- >>> member 5 (fromList [(5,'a'), (3,'b')]) == True
-- True
-- >>> member 1 (fromList [(5,'a'), (3,'b')]) == False
-- True
member :: PartialOrd k => k -> POMap k v -> Bool
member :: k -> POMap k v -> Bool
member !k
k = Any -> Bool
getAny (Any -> Bool) -> (POMap k v -> Any) -> POMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> (v -> Any) -> POMap k v -> Any
forall m k v.
(Monoid m, PartialOrd k) =>
k -> (v -> m) -> POMap k v -> m
foldEntry k
k (Any -> v -> Any
forall a b. a -> b -> a
const (Bool -> Any
Any Bool
True))
{-# INLINABLE member #-}

-- | \(\mathcal{O}(w\log n)\).
-- Is the key not a member of the map? See also 'member'.
--
-- >>> notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- True
-- >>> notMember 1 (fromList [(5,'a'), (3,'b')]) == True
-- True
notMember :: PartialOrd k => k -> POMap k v -> Bool
notMember :: k -> POMap k v -> Bool
notMember k
k = Bool -> Bool
not (Bool -> Bool) -> (POMap k v -> Bool) -> POMap k v -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> POMap k v -> Bool
forall k v. PartialOrd k => k -> POMap k v -> Bool
member k
k
{-# INLINABLE notMember #-}

-- | \(\mathcal{O}(w\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'
-- True
-- >>> findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
-- True
findWithDefault :: PartialOrd k => v -> k -> POMap k v -> v
findWithDefault :: v -> k -> POMap k v -> v
findWithDefault v
def k
k = v -> Maybe v -> v
forall a. a -> Maybe a -> a
fromMaybe v
def (Maybe v -> v) -> (POMap k v -> Maybe v) -> POMap k v -> v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> POMap k v -> Maybe v
forall k v. PartialOrd k => k -> POMap k v -> Maybe v
lookup k
k
{-# INLINABLE findWithDefault #-}

data RelationalOperator
  = LessThan
  | LessEqual
  | Equal
  | GreaterEqual
  | GreaterThan
  deriving (RelationalOperator -> RelationalOperator -> Bool
(RelationalOperator -> RelationalOperator -> Bool)
-> (RelationalOperator -> RelationalOperator -> Bool)
-> Eq RelationalOperator
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: RelationalOperator -> RelationalOperator -> Bool
$c/= :: RelationalOperator -> RelationalOperator -> Bool
== :: RelationalOperator -> RelationalOperator -> Bool
$c== :: RelationalOperator -> RelationalOperator -> Bool
Eq, Eq RelationalOperator
Eq RelationalOperator
-> (RelationalOperator -> RelationalOperator -> Ordering)
-> (RelationalOperator -> RelationalOperator -> Bool)
-> (RelationalOperator -> RelationalOperator -> Bool)
-> (RelationalOperator -> RelationalOperator -> Bool)
-> (RelationalOperator -> RelationalOperator -> Bool)
-> (RelationalOperator -> RelationalOperator -> RelationalOperator)
-> (RelationalOperator -> RelationalOperator -> RelationalOperator)
-> Ord RelationalOperator
RelationalOperator -> RelationalOperator -> Bool
RelationalOperator -> RelationalOperator -> Ordering
RelationalOperator -> RelationalOperator -> RelationalOperator
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: RelationalOperator -> RelationalOperator -> RelationalOperator
$cmin :: RelationalOperator -> RelationalOperator -> RelationalOperator
max :: RelationalOperator -> RelationalOperator -> RelationalOperator
$cmax :: RelationalOperator -> RelationalOperator -> RelationalOperator
>= :: RelationalOperator -> RelationalOperator -> Bool
$c>= :: RelationalOperator -> RelationalOperator -> Bool
> :: RelationalOperator -> RelationalOperator -> Bool
$c> :: RelationalOperator -> RelationalOperator -> Bool
<= :: RelationalOperator -> RelationalOperator -> Bool
$c<= :: RelationalOperator -> RelationalOperator -> Bool
< :: RelationalOperator -> RelationalOperator -> Bool
$c< :: RelationalOperator -> RelationalOperator -> Bool
compare :: RelationalOperator -> RelationalOperator -> Ordering
$ccompare :: RelationalOperator -> RelationalOperator -> Ordering
$cp1Ord :: Eq RelationalOperator
Ord, Int -> RelationalOperator -> ShowS
[RelationalOperator] -> ShowS
RelationalOperator -> String
(Int -> RelationalOperator -> ShowS)
-> (RelationalOperator -> String)
-> ([RelationalOperator] -> ShowS)
-> Show RelationalOperator
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [RelationalOperator] -> ShowS
$cshowList :: [RelationalOperator] -> ShowS
show :: RelationalOperator -> String
$cshow :: RelationalOperator -> String
showsPrec :: Int -> RelationalOperator -> ShowS
$cshowsPrec :: Int -> RelationalOperator -> ShowS
Show)

flipRelationalOperator :: RelationalOperator -> RelationalOperator
flipRelationalOperator :: RelationalOperator -> RelationalOperator
flipRelationalOperator RelationalOperator
op =
  case RelationalOperator
op of
    RelationalOperator
LessThan     -> RelationalOperator
GreaterThan
    RelationalOperator
GreaterThan  -> RelationalOperator
LessThan
    RelationalOperator
LessEqual    -> RelationalOperator
GreaterEqual
    RelationalOperator
GreaterEqual -> RelationalOperator
LessEqual
    RelationalOperator
_            -> RelationalOperator
op

containsOrdering :: Ordering -> RelationalOperator -> Bool
containsOrdering :: Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
LessThan     = Bool
True
containsOrdering Ordering
LT RelationalOperator
LessEqual    = Bool
True
containsOrdering Ordering
LT RelationalOperator
_            = Bool
False
containsOrdering Ordering
GT RelationalOperator
GreaterThan  = Bool
True
containsOrdering Ordering
GT RelationalOperator
GreaterEqual = Bool
True
containsOrdering Ordering
GT RelationalOperator
_            = Bool
False
containsOrdering Ordering
EQ RelationalOperator
LessThan     = Bool
False
containsOrdering Ordering
EQ RelationalOperator
GreaterThan  = Bool
False
containsOrdering Ordering
EQ RelationalOperator
_            = Bool
True

comparePartial :: PartialOrd k => k -> k -> Maybe Ordering
comparePartial :: k -> k -> Maybe Ordering
comparePartial k
a k
b =
  case (k
a k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
b, k
b k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
a) of
    (Bool
True, Bool
True)   -> Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
EQ
    (Bool
True, Bool
False)  -> Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
LT
    (Bool
False, Bool
True)  -> Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just Ordering
GT
    (Bool
False, Bool
False) -> Maybe Ordering
forall a. Maybe a
Nothing
{-# INLINE comparePartial #-}

addToAntichain :: PartialOrd k => RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]
addToAntichain :: RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]
addToAntichain !RelationalOperator
op entry :: (k, v)
entry@(k
k, v
_) [(k, v)]
chain = [(k, v)] -> ([(k, v)] -> [(k, v)]) -> Maybe [(k, v)] -> [(k, v)]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [(k, v)]
chain ((k, v)
entry(k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
:) (((k, v) -> Maybe [(k, v)] -> Maybe [(k, v)])
-> Maybe [(k, v)] -> [(k, v)] -> Maybe [(k, v)]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (k, v) -> Maybe [(k, v)] -> Maybe [(k, v)]
weedOut ([(k, v)] -> Maybe [(k, v)]
forall a. a -> Maybe a
Just []) [(k, v)]
chain)
  where
    weedOut :: (k, v) -> Maybe [(k, v)] -> Maybe [(k, v)]
weedOut e' :: (k, v)
e'@(k
k', v
_) Maybe [(k, v)]
mayChain' =
      case k -> k -> Maybe Ordering
forall k. PartialOrd k => k -> k -> Maybe Ordering
comparePartial k
k k
k' of
        Just Ordering
LT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Maybe [(k, v)]
mayChain' -- don't need e'
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Maybe [(k, v)]
forall a. Maybe a
Nothing
        Just Ordering
GT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Maybe [(k, v)]
forall a. Maybe a
Nothing
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Maybe [(k, v)]
mayChain' -- don't need e'
        Just Ordering
EQ -> Maybe [(k, v)]
forall a. Maybe a
Nothing -- should never happen
        Maybe Ordering
_ -> ((k, v)
e' (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
:) ([(k, v)] -> [(k, v)]) -> Maybe [(k, v)] -> Maybe [(k, v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe [(k, v)]
mayChain' -- still need e'
{-# INLINE addToAntichain #-}

dedupAntichain :: PartialOrd k => RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain :: RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain !RelationalOperator
op = ((k, v) -> [(k, v)] -> [(k, v)])
-> [(k, v)] -> [(k, v)] -> [(k, v)]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]
addToAntichain RelationalOperator
op) []

-- If inlined, this optimizes to the equivalent hand-written variants.
lookupX :: PartialOrd k => RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX :: RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX !RelationalOperator
op !k
k
  -- we bias comparable elements in the opposite direction
  = RelationalOperator -> [(k, v)] -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain (RelationalOperator -> RelationalOperator
flipRelationalOperator RelationalOperator
op)
  ([(k, v)] -> [(k, v)])
-> (POMap k v -> [(k, v)]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Maybe (k, v)) -> [Map k v] -> [(k, v)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe Map k v -> Maybe (k, v)
findNothing
  ([Map k v] -> [(k, v)])
-> (POMap k v -> [Map k v]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
  where
    findNothing :: Map k v -> Maybe (k, v)
findNothing Map k v
Tip = Maybe (k, v)
forall a. Maybe a
Nothing
    findNothing (Bin Int
_ k
k' v
v' Map k v
l Map k v
r) =
      case k -> k -> Maybe Ordering
forall k. PartialOrd k => k -> k -> Maybe Ordering
comparePartial k
k k
k' of
        Just Ordering
EQ
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
EQ RelationalOperator
op -> (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k', v
v')
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> Maybe (k, v)
findNothing Map k v
r
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Map k v -> Maybe (k, v)
findNothing Map k v
l
          | Bool
otherwise -> String -> Maybe (k, v)
forall a. HasCallStack => String -> a
error String
"lookupX.findNothing: inexhaustive match"
        Just Ordering
LT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
l k
k' v
v'
          | Bool
otherwise -> Map k v -> Maybe (k, v)
findNothing Map k v
l
        Just Ordering
GT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
r k
k' v
v'
          | Bool
otherwise -> Map k v -> Maybe (k, v)
findNothing Map k v
r
        Maybe Ordering
Nothing -- Incomparable, only the min or max element might not be
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Map k v -> Maybe (k, v)
findNothing Map k v
l
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> Maybe (k, v)
findNothing Map k v
r
          | Bool
otherwise -> Maybe (k, v)
forall a. Maybe a
Nothing
    findJust :: Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
Tip k
k'' v
v'' = (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k'', v
v'')
    findJust (Bin Int
_ k
k' v
v' Map k v
l Map k v
r) k
k'' v
v'' =
      case k -> k -> Maybe Ordering
forall k. PartialOrd k => k -> k -> Maybe Ordering
comparePartial k
k k
k' of
        Just Ordering
EQ
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
EQ RelationalOperator
op -> (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k', v
v')
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
r k
k'' v
v''
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
l k
k'' v
v''
          | Bool
otherwise -> String -> Maybe (k, v)
forall a. HasCallStack => String -> a
error String
"lookupX.findJust: inexhaustive match"
        Just Ordering
LT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
l k
k' v
v'
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
GT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
l k
k' v
v'
          | Bool
otherwise -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
l k
k'' v
v''
        Just Ordering
GT
          | Ordering -> RelationalOperator -> Bool
containsOrdering Ordering
LT RelationalOperator
op -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
r k
k' v
v'
          | Bool
otherwise -> Map k v -> k -> v -> Maybe (k, v)
findJust Map k v
r k
k'' v
v''
        Maybe Ordering
Nothing -> (k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k'', v
v'')
{-# INLINE lookupX #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the largest set of keys smaller than the given one and
-- return the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupLT 3  (fromList [(3,'a'), (5,'b')])
-- []
-- >>> lookupLT 9 (fromList [(3,'a'), (5,'b')])
-- [(3,'a')]
lookupLT :: PartialOrd k => k -> POMap k v -> [(k, v)]
lookupLT :: k -> POMap k v -> [(k, v)]
lookupLT = (RelationalOperator -> k -> POMap k v -> [(k, v)])
-> RelationalOperator -> k -> POMap k v -> [(k, v)]
forall a. a -> a
inline RelationalOperator -> k -> POMap k v -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX RelationalOperator
LessThan
{-# INLINABLE lookupLT #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the largest key smaller or equal to the given one and return
-- the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupLE 2 (fromList [(3,'a'), (5,'b')])
-- []
-- >>> lookupLE 3 (fromList [(3,'a'), (5,'b')])
-- [(3,'a')]
-- >>> lookupLE 10 (fromList [(3,'a'), (5,'b')])
-- [(5,'b')]
lookupLE :: PartialOrd k => k -> POMap k v -> [(k, v)]
lookupLE :: k -> POMap k v -> [(k, v)]
lookupLE = (RelationalOperator -> k -> POMap k v -> [(k, v)])
-> RelationalOperator -> k -> POMap k v -> [(k, v)]
forall a. a -> a
inline RelationalOperator -> k -> POMap k v -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX RelationalOperator
LessEqual
{-# INLINABLE lookupLE #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the smallest key greater or equal to the given one and return
-- the corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupGE 3 (fromList [(3,'a'), (5,'b')])
-- [(3,'a')]
-- >>> lookupGE 5 (fromList [(3,'a'), (10,'b')])
-- [(10,'b')]
-- >>> lookupGE 6 (fromList [(3,'a'), (5,'b')])
-- []
lookupGE :: PartialOrd k => k -> POMap k v -> [(k, v)]
lookupGE :: k -> POMap k v -> [(k, v)]
lookupGE = (RelationalOperator -> k -> POMap k v -> [(k, v)])
-> RelationalOperator -> k -> POMap k v -> [(k, v)]
forall a. a -> a
inline RelationalOperator -> k -> POMap k v -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX RelationalOperator
GreaterEqual
{-# INLINABLE lookupGE #-}

-- | \(\mathcal{O}(w\log n)\).
-- Find the smallest key greater than the given one and return the
-- corresponding list of (key, value) pairs.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupGT 5 (fromList [(3,'a'), (10,'b')])
-- [(10,'b')]
-- >>> lookupGT 5 (fromList [(3,'a'), (5,'b')])
-- []
lookupGT :: PartialOrd k => k -> POMap k v -> [(k, v)]
lookupGT :: k -> POMap k v -> [(k, v)]
lookupGT = (RelationalOperator -> k -> POMap k v -> [(k, v)])
-> RelationalOperator -> k -> POMap k v -> [(k, v)]
forall a. a -> a
inline RelationalOperator -> k -> POMap k v -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> k -> POMap k v -> [(k, v)]
lookupX RelationalOperator
GreaterThan
{-# INLINABLE lookupGT #-}


--
-- * Construction
--

-- | \(\mathcal{O}(1)\). The empty map.
--
-- >>> empty
-- fromList []
-- >>> size empty
-- 0
empty :: POMap k v
empty :: POMap k v
empty = Int -> [Map k v] -> POMap k v
forall k v. Int -> [Map k v] -> POMap k v
POMap Int
0 []
{-# INLINE empty #-}

singleton :: SingIAreWeStrict s => Proxy# s -> k -> v -> POMap k v
singleton :: Proxy# s -> k -> v -> POMap k v
singleton Proxy# s
s k
k v
v = Proxy# s -> v -> POMap k v -> POMap k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (POMap k v -> POMap k v) -> POMap k v -> POMap k v
forall a b. (a -> b) -> a -> b
$ Int -> [Map k v] -> POMap k v
forall k v. Int -> [Map k v] -> POMap k v
POMap Int
1 [k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v]
{-# INLINE singleton #-}
-- INLINE means we don't need to SPECIALIZE

--
-- * Insertion
--

insert :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> k -> v -> POMap k v -> POMap k v
insert :: Proxy# s -> k -> v -> POMap k v -> POMap k v
insert Proxy# s
s = (Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v)
-> Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall a. a -> a
inline Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWith Proxy# s
s v -> v -> v
forall a b. a -> b -> a
const
{-# INLINABLE insert #-}
{-# SPECIALIZE insert :: PartialOrd k => Proxy# 'Strict -> k -> v -> POMap k v -> POMap k v #-}
{-# SPECIALIZE insert :: PartialOrd k => Proxy# 'Lazy -> k -> v -> POMap k v -> POMap k v #-}

insertWith
  :: (PartialOrd k, SingIAreWeStrict s)
  => Proxy# s
  -> (v -> v -> v)
  -> k
  -> v
  -> POMap k v
  -> POMap k v
insertWith :: Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWith Proxy# s
s v -> v -> v
f = (Proxy# s
 -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v)
-> Proxy# s
-> (k -> v -> v -> v)
-> k
-> v
-> POMap k v
-> POMap k v
forall a. a -> a
inline Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey Proxy# s
s ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE insertWith #-}
{-# SPECIALIZE insertWith :: PartialOrd k => Proxy# 'Strict -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v #-}
{-# SPECIALIZE insertWith :: PartialOrd k => Proxy# 'Lazy -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v #-}

insertWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey :: Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey Proxy# s
s k -> v -> v -> v
f k
k v
v = (Proxy# s
 -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> POMap k v
forall a. a -> a
inline Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey Proxy# s
s ((k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
forall k v. (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
keyedInsertAsAlter k -> v -> v -> v
f v
v) k
k
{-# INLINABLE insertWithKey #-}
{-# SPECIALIZE insertWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v #-}
{-# SPECIALIZE insertWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v #-}

insertLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v)
insertLookupWithKey :: Proxy# s
-> (k -> v -> v -> v)
-> k
-> v
-> POMap k v
-> (Maybe v, POMap k v)
insertLookupWithKey Proxy# s
s k -> v -> v -> v
f k
k v
v = (Proxy# s
 -> (k -> Maybe v -> Maybe v)
 -> k
 -> POMap k v
 -> (Maybe v, POMap k v))
-> Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall a. a -> a
inline Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
alterLookupWithKey Proxy# s
s ((k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
forall k v. (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
keyedInsertAsAlter k -> v -> v -> v
f v
v) k
k
{-# INLINABLE insertLookupWithKey #-}
{-# SPECIALIZE insertLookupWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v) #-}
{-# SPECIALIZE insertLookupWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v) #-}

keyedInsertAsAlter :: (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
keyedInsertAsAlter :: (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
keyedInsertAsAlter k -> v -> v -> v
_ v
v k
_ Maybe v
Nothing   = v -> Maybe v
forall a. a -> Maybe a
Just v
v
keyedInsertAsAlter k -> v -> v -> v
f v
v k
k (Just v
v') = v -> Maybe v
forall a. a -> Maybe a
Just (k -> v -> v -> v
f k
k v
v v
v')
{-# INLINE keyedInsertAsAlter #-}

--
-- * Deletion
--

data LookupResult a
  = Incomparable
  | NotFound a
  | Found a
  deriving (LookupResult a -> LookupResult a -> Bool
(LookupResult a -> LookupResult a -> Bool)
-> (LookupResult a -> LookupResult a -> Bool)
-> Eq (LookupResult a)
forall a. Eq a => LookupResult a -> LookupResult a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: LookupResult a -> LookupResult a -> Bool
$c/= :: forall a. Eq a => LookupResult a -> LookupResult a -> Bool
== :: LookupResult a -> LookupResult a -> Bool
$c== :: forall a. Eq a => LookupResult a -> LookupResult a -> Bool
Eq, Int -> LookupResult a -> ShowS
[LookupResult a] -> ShowS
LookupResult a -> String
(Int -> LookupResult a -> ShowS)
-> (LookupResult a -> String)
-> ([LookupResult a] -> ShowS)
-> Show (LookupResult a)
forall a. Show a => Int -> LookupResult a -> ShowS
forall a. Show a => [LookupResult a] -> ShowS
forall a. Show a => LookupResult a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [LookupResult a] -> ShowS
$cshowList :: forall a. Show a => [LookupResult a] -> ShowS
show :: LookupResult a -> String
$cshow :: forall a. Show a => LookupResult a -> String
showsPrec :: Int -> LookupResult a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> LookupResult a -> ShowS
Show, a -> LookupResult b -> LookupResult a
(a -> b) -> LookupResult a -> LookupResult b
(forall a b. (a -> b) -> LookupResult a -> LookupResult b)
-> (forall a b. a -> LookupResult b -> LookupResult a)
-> Functor LookupResult
forall a b. a -> LookupResult b -> LookupResult a
forall a b. (a -> b) -> LookupResult a -> LookupResult b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> LookupResult b -> LookupResult a
$c<$ :: forall a b. a -> LookupResult b -> LookupResult a
fmap :: (a -> b) -> LookupResult a -> LookupResult b
$cfmap :: forall a b. (a -> b) -> LookupResult a -> LookupResult b
Functor)

instance Ord a => Ord (LookupResult a) where
  compare :: LookupResult a -> LookupResult a -> Ordering
compare LookupResult a
a LookupResult a
b =
    case (LookupResult a
a, LookupResult a
b) of
      (LookupResult a
Incomparable, LookupResult a
Incomparable) -> Ordering
EQ
      (LookupResult a
Incomparable, LookupResult a
_)            -> Ordering
GT
      (NotFound a
n, NotFound a
m)     -> a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
n a
m
      (NotFound{}, Found{})        -> Ordering
GT
      (Found a
n, Found a
m)           -> a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
n a
m
      (LookupResult a, LookupResult a)
_                            -> Ordering
LT

overChains
  :: (Map k v -> LookupResult a)
  -> (Map k v -> b -> b)
  -> (a -> [Map k v] -> b)
  -> ([Map k v] -> b)
  -> POMap k v
  -> b
overChains :: (Map k v -> LookupResult a)
-> (Map k v -> b -> b)
-> (a -> [Map k v] -> b)
-> ([Map k v] -> b)
-> POMap k v
-> b
overChains Map k v -> LookupResult a
handleChain Map k v -> b -> b
oldWon a -> [Map k v] -> b
newWon [Map k v] -> b
incomparable POMap k v
pomap
  = LookupResult b -> b
unwrapResult
  (LookupResult b -> b)
-> ([Map k v] -> LookupResult b) -> [Map k v] -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, b) -> b) -> LookupResult (Int, b) -> LookupResult b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int, b) -> b
forall a b. (a, b) -> b
snd
  (LookupResult (Int, b) -> LookupResult b)
-> ([Map k v] -> LookupResult (Int, b))
-> [Map k v]
-> LookupResult b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (([Map k v], LookupResult a)
 -> LookupResult (Int, b) -> LookupResult (Int, b))
-> LookupResult (Int, b)
-> [([Map k v], LookupResult a)]
-> LookupResult (Int, b)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ([Map k v], LookupResult a)
-> LookupResult (Int, b) -> LookupResult (Int, b)
improve LookupResult (Int, b)
forall a. LookupResult a
Incomparable
  ([([Map k v], LookupResult a)] -> LookupResult (Int, b))
-> ([Map k v] -> [([Map k v], LookupResult a)])
-> [Map k v]
-> LookupResult (Int, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Map k v]] -> [LookupResult a] -> [([Map k v], LookupResult a)]
forall a b. [a] -> [b] -> [(a, b)]
zip ([Map k v] -> [[Map k v]]
forall a. [a] -> [[a]]
List.tails [Map k v]
decomp)
  ([LookupResult a] -> [([Map k v], LookupResult a)])
-> ([Map k v] -> [LookupResult a])
-> [Map k v]
-> [([Map k v], LookupResult a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> LookupResult a) -> [Map k v] -> [LookupResult a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map k v -> LookupResult a
handleChain
  ([Map k v] -> b) -> [Map k v] -> b
forall a b. (a -> b) -> a -> b
$ [Map k v]
decomp
  where
    decomp :: [Map k v]
decomp = POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition POMap k v
pomap
    improve :: ([Map k v], LookupResult a)
-> LookupResult (Int, b) -> LookupResult (Int, b)
improve ([], LookupResult a
_) LookupResult (Int, b)
_ = String -> LookupResult (Int, b)
forall a. HasCallStack => String -> a
error String
"List.tails was empty"
    improve (Map k v
chain:[Map k v]
chains, LookupResult a
candidate) LookupResult (Int, b)
winner =
      -- We want to minimize the score: Prefer Found over NotFound and
      -- Incomparability (which means we have to add a new chain to the
      -- composition)
      case LookupResult Int -> LookupResult Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Map k v -> Int
forall k a. Map k a -> Int
Map.size Map k v
chain Int -> LookupResult a -> LookupResult Int
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ LookupResult a
candidate) ((Int, b) -> Int
forall a b. (a, b) -> a
fst ((Int, b) -> Int) -> LookupResult (Int, b) -> LookupResult Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> LookupResult (Int, b)
winner) of
        Ordering
GT -> (b -> b) -> (Int, b) -> (Int, b)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second (Map k v -> b -> b
oldWon Map k v
chain) ((Int, b) -> (Int, b))
-> LookupResult (Int, b) -> LookupResult (Int, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> LookupResult (Int, b)
winner
        Ordering
_  -> (\a
chain' -> (Map k v -> Int
forall k a. Map k a -> Int
Map.size Map k v
chain, a -> [Map k v] -> b
newWon a
chain' [Map k v]
chains)) (a -> (Int, b)) -> LookupResult a -> LookupResult (Int, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> LookupResult a
candidate
    unwrapResult :: LookupResult b -> b
unwrapResult LookupResult b
res =
      case LookupResult b
res of
        LookupResult b
Incomparable    -> [Map k v] -> b
incomparable [Map k v]
decomp
        NotFound b
chains -> b
chains
        Found b
chains    -> b
chains
{-# INLINE overChains #-}

-- | \(\mathcal{O}(w\log n)\).
-- Delete a key and its value from the map. When the key is not
-- a member of the map, the original map is returned.
--
-- >>> delete 5 (fromList [(5,"a"), (3,"b")])
-- fromList [(3,"b")]
-- >>> delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- True
-- >>> delete 5 empty
-- fromList []
delete :: PartialOrd k => k -> POMap k v -> POMap k v
delete :: k -> POMap k v -> POMap k v
delete = (Proxy# 'Lazy -> (v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# 'Lazy -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
forall a. a -> a
inline Proxy# 'Lazy -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
update (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) (Maybe v -> v -> Maybe v
forall a b. a -> b -> a
const Maybe v
forall a. Maybe a
Nothing)
{-# INLINABLE delete #-}

-- | \(\mathcal{O}(w\log n)\). Simultaneous 'delete' and 'lookup'.
deleteLookup :: PartialOrd k => k -> POMap k v -> (Maybe v, POMap k v)
deleteLookup :: k -> POMap k v -> (Maybe v, POMap k v)
deleteLookup = (Proxy# 'Lazy
 -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v))
-> Proxy# 'Lazy
-> (k -> v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall a. a -> a
inline Proxy# 'Lazy
-> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
updateLookupWithKey (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) (\k
_ v
_ -> Maybe v
forall a. Maybe a
Nothing)
{-# INLINABLE deleteLookup #-}

adjust :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v) -> k -> POMap k v -> POMap k v
adjust :: Proxy# s -> (v -> v) -> k -> POMap k v -> POMap k v
adjust Proxy# s
s v -> v
f = (Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
forall a. a -> a
inline Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
update Proxy# s
s (v -> Maybe v
forall a. a -> Maybe a
Just (v -> Maybe v) -> (v -> v) -> v -> Maybe v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> v
f)
{-# INLINABLE adjust #-}
{-# SPECIALIZE adjust :: PartialOrd k => Proxy# 'Strict -> (v -> v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE adjust :: PartialOrd k => Proxy# 'Lazy -> (v -> v) -> k -> POMap k v -> POMap k v #-}


adjustWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> POMap k v
adjustWithKey :: Proxy# s -> (k -> v -> v) -> k -> POMap k v -> POMap k v
adjustWithKey Proxy# s
s k -> v -> v
f = (Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
forall a. a -> a
inline Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
updateWithKey Proxy# s
s (\k
k v
v -> v -> Maybe v
forall a. a -> Maybe a
Just (k -> v -> v
f k
k v
v))
{-# INLINABLE adjustWithKey #-}
{-# SPECIALIZE adjustWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE adjustWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> v) -> k -> POMap k v -> POMap k v #-}

adjustLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)
adjustLookupWithKey :: Proxy# s -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)
adjustLookupWithKey Proxy# s
s k -> v -> v
f = (Proxy# s
 -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v))
-> Proxy# s
-> (k -> v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall a. a -> a
inline Proxy# s
-> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
updateLookupWithKey Proxy# s
s (\k
k v
v -> v -> Maybe v
forall a. a -> Maybe a
Just (k -> v -> v
f k
k v
v))
{-# INLINABLE adjustLookupWithKey #-}
{-# SPECIALIZE adjustLookupWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}
{-# SPECIALIZE adjustLookupWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}

update :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
update :: Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
update Proxy# s
s v -> Maybe v
f = (Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
forall a. a -> a
inline Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alter Proxy# s
s (Maybe v -> (v -> Maybe v) -> Maybe v
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= v -> Maybe v
f)
{-# INLINABLE update #-}
{-# SPECIALIZE update :: PartialOrd k => Proxy# 'Strict -> (v -> Maybe v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE update :: PartialOrd k => Proxy# 'Lazy -> (v -> Maybe v) -> k -> POMap k v -> POMap k v #-}

updateWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
updateWithKey :: Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
updateWithKey Proxy# s
s k -> v -> Maybe v
f = (Proxy# s
 -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> POMap k v
forall a. a -> a
inline Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey Proxy# s
s (\k
k Maybe v
mv -> Maybe v
mv Maybe v -> (v -> Maybe v) -> Maybe v
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= k -> v -> Maybe v
f k
k)
{-# INLINABLE updateWithKey #-}
{-# SPECIALIZE updateWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE updateWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v #-}

updateLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
updateLookupWithKey :: Proxy# s
-> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
updateLookupWithKey Proxy# s
s k -> v -> Maybe v
f = (Proxy# s
 -> (k -> Maybe v -> Maybe v)
 -> k
 -> POMap k v
 -> (Maybe v, POMap k v))
-> Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall a. a -> a
inline Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
alterLookupWithKey Proxy# s
s (\k
k Maybe v
mv -> Maybe v
mv Maybe v -> (v -> Maybe v) -> Maybe v
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= k -> v -> Maybe v
f k
k)
{-# INLINABLE updateLookupWithKey #-}
{-# SPECIALIZE updateLookupWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}
{-# SPECIALIZE updateLookupWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}

alter :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alter :: Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alter Proxy# s
s Maybe v -> Maybe v
f = (Proxy# s
 -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v)
-> Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> POMap k v
forall a. a -> a
inline Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey Proxy# s
s ((Maybe v -> Maybe v) -> k -> Maybe v -> Maybe v
forall a b. a -> b -> a
const Maybe v -> Maybe v
f)
{-# INLINABLE alter #-}
{-# SPECIALIZE alter :: PartialOrd k => Proxy# 'Strict -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE alter :: PartialOrd k => Proxy# 'Lazy -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v #-}

alterWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey :: Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey Proxy# s
s k -> Maybe v -> Maybe v
f !k
k = [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k v] -> POMap k v)
-> (POMap k v -> [Map k v]) -> POMap k v -> POMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> LookupResult (Map k v))
-> (Map k v -> [Map k v] -> [Map k v])
-> (Map k v -> [Map k v] -> [Map k v])
-> ([Map k v] -> [Map k v])
-> POMap k v
-> [Map k v]
forall k v a b.
(Map k v -> LookupResult a)
-> (Map k v -> b -> b)
-> (a -> [Map k v] -> b)
-> ([Map k v] -> b)
-> POMap k v
-> b
overChains Map k v -> LookupResult (Map k v)
handleChain Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
oldWon Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
newWon [Map k v] -> [Map k v]
incomparable
  where
    handleChain :: Map k v -> LookupResult (Map k v)
handleChain = Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Map k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Map k v)
alterChain Proxy# s
s k -> Maybe v -> Maybe v
f k
k
    oldWon :: a -> [a] -> [a]
oldWon a
chain [a]
chains' = a
chain a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
chains'
    newWon :: a -> [a] -> [a]
newWon a
chain' [a]
chains = a
chain' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
chains
    incomparable :: [Map k v] -> [Map k v]
incomparable [Map k v]
decomp =
      case k -> Maybe v -> Maybe v
f k
k Maybe v
forall a. Maybe a
Nothing of
        Maybe v
Nothing -> [Map k v]
decomp
        Just v
v  -> Proxy# s -> v -> [Map k v] -> [Map k v]
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
: [Map k v]
decomp)
{-# INLINABLE alterWithKey #-}
{-# SPECIALIZE alterWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v #-}
{-# SPECIALIZE alterWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v #-}

alterChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Map k v)
alterChain :: Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Map k v)
alterChain Proxy# s
s k -> Maybe v -> Maybe v
f k
k = Map k v -> LookupResult (Map k v)
go
  where
    go :: Map k v -> LookupResult (Map k v)
go Map k v
Tip = Map k v -> LookupResult (Map k v)
forall a. a -> LookupResult a
NotFound (Map k v -> LookupResult (Map k v))
-> Map k v -> LookupResult (Map k v)
forall a b. (a -> b) -> a -> b
$ case k -> Maybe v -> Maybe v
f k
k Maybe v
forall a. Maybe a
Nothing of
      Just v
v  -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
      Maybe v
Nothing -> Map k v
forall k a. Map k a
Tip
    go (Bin Int
n k
k' v
v' Map k v
l Map k v
r) =
      case (k
k k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k', k
k' k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k) of
        (Bool
True, Bool
True) -> Map k v -> LookupResult (Map k v)
forall a. a -> LookupResult a
Found (Map k v -> LookupResult (Map k v))
-> Map k v -> LookupResult (Map k v)
forall a b. (a -> b) -> a -> b
$ case k -> Maybe v -> Maybe v
f k
k (v -> Maybe v
forall a. a -> Maybe a
Just v
v') of
          Just v
v  -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (Int -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. Int -> k -> a -> Map k a -> Map k a -> Map k a
Bin Int
n k
k' v
v Map k v
l Map k v
r)
          Maybe v
Nothing -> Map k v -> Map k v -> Map k v
forall k a. Map k a -> Map k a -> Map k a
Map.link2 Map k v
l Map k v
r
        (Bool
True, Bool
False)  -> (Map k v -> Map k v) -> Map k v -> Map k v
oneShot (\Map k v
l' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceL k
k' v
v' Map k v
l' Map k v
r) (Map k v -> Map k v)
-> LookupResult (Map k v) -> LookupResult (Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k v -> LookupResult (Map k v)
go Map k v
l
        (Bool
False, Bool
True)  -> (Map k v -> Map k v) -> Map k v -> Map k v
oneShot (\Map k v
r' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceR k
k' v
v' Map k v
l Map k v
r') (Map k v -> Map k v)
-> LookupResult (Map k v) -> LookupResult (Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k v -> LookupResult (Map k v)
go Map k v
r
        (Bool
False, Bool
False) -> LookupResult (Map k v)
forall a. LookupResult a
Incomparable
{-# INLINE alterChain #-}

alterLookupWithKey
  :: (PartialOrd k, SingIAreWeStrict s)
  => Proxy# s
  -> (k -> Maybe v -> Maybe v)
  -> k
  -> POMap k v
  -> (Maybe v, POMap k v)
alterLookupWithKey :: Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> POMap k v
-> (Maybe v, POMap k v)
alterLookupWithKey Proxy# s
s k -> Maybe v -> Maybe v
f !k
k
  = ([Map k v] -> POMap k v)
-> (Maybe v, [Map k v]) -> (Maybe v, POMap k v)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap
  ((Maybe v, [Map k v]) -> (Maybe v, POMap k v))
-> (POMap k v -> (Maybe v, [Map k v]))
-> POMap k v
-> (Maybe v, POMap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> LookupResult (Maybe v, Map k v))
-> (Map k v -> (Maybe v, [Map k v]) -> (Maybe v, [Map k v]))
-> ((Maybe v, Map k v) -> [Map k v] -> (Maybe v, [Map k v]))
-> ([Map k v] -> (Maybe v, [Map k v]))
-> POMap k v
-> (Maybe v, [Map k v])
forall k v a b.
(Map k v -> LookupResult a)
-> (Map k v -> b -> b)
-> (a -> [Map k v] -> b)
-> ([Map k v] -> b)
-> POMap k v
-> b
overChains Map k v -> LookupResult (Maybe v, Map k v)
handleChain Map k v -> (Maybe v, [Map k v]) -> (Maybe v, [Map k v])
forall a a. a -> (a, [a]) -> (a, [a])
oldWon (Maybe v, Map k v) -> [Map k v] -> (Maybe v, [Map k v])
forall a a. (a, a) -> [a] -> (a, [a])
newWon [Map k v] -> (Maybe v, [Map k v])
incomparable
  where
    handleChain :: Map k v -> LookupResult (Maybe v, Map k v)
handleChain = Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Maybe v, Map k v)
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Maybe v, Map k v)
alterLookupChain Proxy# s
s k -> Maybe v -> Maybe v
f k
k
    oldWon :: a -> (a, [a]) -> (a, [a])
oldWon a
chain (a
v, [a]
chains') = (a
v, a
chain a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
chains')
    newWon :: (a, a) -> [a] -> (a, [a])
newWon (a
v', a
chain') [a]
chains = (a
v', a
chain' a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
chains)
    incomparable :: [Map k v] -> (Maybe v, [Map k v])
incomparable [Map k v]
decomp =
      (Maybe v
forall a. Maybe a
Nothing, case k -> Maybe v -> Maybe v
f k
k Maybe v
forall a. Maybe a
Nothing of
        Maybe v
Nothing -> [Map k v]
decomp
        Just v
v  -> Proxy# s -> v -> [Map k v] -> [Map k v]
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
: [Map k v]
decomp))
{-# INLINABLE alterLookupWithKey #-}
{-# SPECIALIZE alterLookupWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}
{-# SPECIALIZE alterLookupWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v) #-}

alterLookupChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Maybe v, Map k v)
alterLookupChain :: Proxy# s
-> (k -> Maybe v -> Maybe v)
-> k
-> Map k v
-> LookupResult (Maybe v, Map k v)
alterLookupChain Proxy# s
s k -> Maybe v -> Maybe v
f k
k = Map k v -> LookupResult (Maybe v, Map k v)
go
  where
    go :: Map k v -> LookupResult (Maybe v, Map k v)
go Map k v
Tip = (Maybe v, Map k v) -> LookupResult (Maybe v, Map k v)
forall a. a -> LookupResult a
NotFound (Maybe v
forall a. Maybe a
Nothing, case k -> Maybe v -> Maybe v
f k
k Maybe v
forall a. Maybe a
Nothing of
      Just v
v  -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
      Maybe v
Nothing -> Map k v
forall k a. Map k a
Tip)
    go (Bin Int
n k
k' v
v' Map k v
l Map k v
r) =
      case (k
k k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k', k
k' k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k) of
        (Bool
True, Bool
True) -> (Maybe v, Map k v) -> LookupResult (Maybe v, Map k v)
forall a. a -> LookupResult a
Found (v -> Maybe v
forall a. a -> Maybe a
Just v
v', case k -> Maybe v -> Maybe v
f k
k (v -> Maybe v
forall a. a -> Maybe a
Just v
v') of
          Just v
v  -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (Int -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. Int -> k -> a -> Map k a -> Map k a -> Map k a
Bin Int
n k
k' v
v Map k v
l Map k v
r)
          Maybe v
Nothing -> Map k v -> Map k v -> Map k v
forall k a. Map k a -> Map k a -> Map k a
Map.link2 Map k v
l Map k v
r)
        (Bool
True, Bool
False)  -> (Map k v -> Map k v) -> (Maybe v, Map k v) -> (Maybe v, Map k v)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second ((Map k v -> Map k v) -> Map k v -> Map k v
oneShot (\Map k v
l' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceL k
k' v
v' Map k v
l' Map k v
r)) ((Maybe v, Map k v) -> (Maybe v, Map k v))
-> LookupResult (Maybe v, Map k v)
-> LookupResult (Maybe v, Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k v -> LookupResult (Maybe v, Map k v)
go Map k v
l
        (Bool
False, Bool
True)  -> (Map k v -> Map k v) -> (Maybe v, Map k v) -> (Maybe v, Map k v)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second ((Map k v -> Map k v) -> Map k v -> Map k v
oneShot (\Map k v
r' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceR k
k' v
v' Map k v
l Map k v
r')) ((Maybe v, Map k v) -> (Maybe v, Map k v))
-> LookupResult (Maybe v, Map k v)
-> LookupResult (Maybe v, Map k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k v -> LookupResult (Maybe v, Map k v)
go Map k v
r
        (Bool
False, Bool
False) -> LookupResult (Maybe v, Map k v)
forall a. LookupResult a
Incomparable
{-# INLINE alterLookupChain #-}

alterF
  :: (Functor f, PartialOrd k, SingIAreWeStrict s)
  => Proxy# s
  -> (Maybe v -> f (Maybe v))
  -> k
  -> POMap k v
  -> f (POMap k v)
alterF :: Proxy# s
-> (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)
alterF Proxy# s
s Maybe v -> f (Maybe v)
f !k
k = ([Map k v] -> POMap k v) -> f [Map k v] -> f (POMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap (f [Map k v] -> f (POMap k v))
-> (POMap k v -> f [Map k v]) -> POMap k v -> f (POMap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> (Map k v -> f [Map k v] -> f [Map k v])
-> (((Maybe v -> f (Maybe v)) -> f (Map k v))
    -> [Map k v] -> f [Map k v])
-> ([Map k v] -> f [Map k v])
-> POMap k v
-> f [Map k v]
forall k v a b.
(Map k v -> LookupResult a)
-> (Map k v -> b -> b)
-> (a -> [Map k v] -> b)
-> ([Map k v] -> b)
-> POMap k v
-> b
overChains Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
handleChain Map k v -> f [Map k v] -> f [Map k v]
forall (f :: * -> *) a. Functor f => a -> f [a] -> f [a]
oldWon ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> [Map k v] -> f [Map k v]
newWon [Map k v] -> f [Map k v]
incomparable
  where
    handleChain :: Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
handleChain = Proxy# s
-> k
-> Map k v
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall (f :: * -> *) k (s :: AreWeStrict) v.
(Functor f, PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> k
-> Map k v
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
alterFChain Proxy# s
s k
k
    -- prepends the unaltered chain to the altered tail
    oldWon :: a -> f [a] -> f [a]
oldWon a
chain f [a]
altered = ([a] -> [a]) -> f [a] -> f [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a
chaina -> [a] -> [a]
forall a. a -> [a] -> [a]
:) f [a]
altered
    -- prepends the altered chain to the unaltered tail
    newWon :: ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> [Map k v] -> f [Map k v]
newWon (Maybe v -> f (Maybe v)) -> f (Map k v)
alt [Map k v]
chains = (Map k v -> [Map k v]) -> f (Map k v) -> f [Map k v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
:[Map k v]
chains) ((Maybe v -> f (Maybe v)) -> f (Map k v)
alt Maybe v -> f (Maybe v)
f)
    <#> :: f a -> (a -> b) -> f b
(<#>) = ((a -> b) -> f a -> f b) -> f a -> (a -> b) -> f b
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
(<$>)
    -- prepends a new chain in the incomparable case if
    -- the alteration function produces a value
    incomparable :: [Map k v] -> f [Map k v]
incomparable [Map k v]
decomp = Maybe v -> f (Maybe v)
f Maybe v
forall a. Maybe a
Nothing f (Maybe v) -> (Maybe v -> [Map k v]) -> f [Map k v]
forall a b. f a -> (a -> b) -> f b
<#> \case
      Maybe v
Nothing -> [Map k v]
decomp
      Just v
v  -> Proxy# s -> v -> [Map k v] -> [Map k v]
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v Map k v -> [Map k v] -> [Map k v]
forall a. a -> [a] -> [a]
: [Map k v]
decomp)
{-# INLINABLE alterF #-}
{-# SPECIALIZE alterF :: (Functor f, PartialOrd k) => Proxy# 'Strict -> (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v) #-}
{-# SPECIALIZE alterF :: (Functor f, PartialOrd k) => Proxy# 'Lazy -> (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v) #-}

alterFChain
  -- `f` should potentially be pulled into the result type, but not willing
  -- to complicate this right now
  :: (Functor f, PartialOrd k, SingIAreWeStrict s)
  => Proxy# s
  -> k
  -> Map k v
  -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
alterFChain :: Proxy# s
-> k
-> Map k v
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
alterFChain Proxy# s
s k
k = Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
go
  where
    -- This is going to be reaaally crazy. Maybe we could use some ContT for
    -- this, I don't know...
    -- So, we always lift the outer functor LookupResult.
    -- That functor contains the logic for actually doing the adjustment,
    -- which takes the function that does the actual adjustment as an argument
    -- and maps into an arbitrary functor `f` which we have to map through.
    ret :: (((t -> f a) -> f b) -> t) -> t -> (a -> b) -> t
ret ((t -> f a) -> f b) -> t
res t
val a -> b
cont = ((t -> f a) -> f b) -> t
res (((t -> f a) -> f b) -> (t -> f a) -> f b
oneShot (\t -> f a
f -> a -> b
cont (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t -> f a
f t
val))
    lift :: f (t -> f a) -> (a -> b) -> f (t -> f b)
lift f (t -> f a)
sub a -> b
cont = ((t -> f a) -> t -> f b) -> (t -> f a) -> t -> f b
oneShot (\t -> f a
a t
f -> a -> b
cont (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> t -> f a
a t
f) ((t -> f a) -> t -> f b) -> f (t -> f a) -> f (t -> f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (t -> f a)
sub
    go :: Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
go Map k v
Tip =
      (((Maybe v -> f (Maybe v)) -> f (Map k v))
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> Maybe v
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall (f :: * -> *) t a b t.
Functor f =>
(((t -> f a) -> f b) -> t) -> t -> (a -> b) -> t
ret ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a. a -> LookupResult a
NotFound Maybe v
forall a. Maybe a
Nothing ((Maybe v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> ((Maybe v -> Map k v) -> Maybe v -> Map k v)
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe v -> Map k v) -> Maybe v -> Map k v
oneShot ((Maybe v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a b. (a -> b) -> a -> b
$ \case
        Just v
v  -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v (k -> v -> Map k v
forall k a. k -> a -> Map k a
Map.singleton k
k v
v)
        Maybe v
Nothing -> Map k v
forall k a. Map k a
Tip
    go (Bin Int
n k
k' v
v Map k v
l Map k v
r) =
      case (k
k k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k', k
k' k -> k -> Bool
forall a. PartialOrd a => a -> a -> Bool
`leq` k
k) of
        (Bool
True, Bool
True)   ->
          (((Maybe v -> f (Maybe v)) -> f (Map k v))
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> Maybe v
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall (f :: * -> *) t a b t.
Functor f =>
(((t -> f a) -> f b) -> t) -> t -> (a -> b) -> t
ret ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a. a -> LookupResult a
Found (v -> Maybe v
forall a. a -> Maybe a
Just v
v) ((Maybe v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> ((Maybe v -> Map k v) -> Maybe v -> Map k v)
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Maybe v -> Map k v) -> Maybe v -> Map k v
oneShot ((Maybe v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> (Maybe v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a b. (a -> b) -> a -> b
$ \case
            Just v
v' -> Proxy# s -> v -> Map k v -> Map k v
forall (s :: AreWeStrict) a b.
SingIAreWeStrict s =>
Proxy# s -> a -> b -> b
seq' Proxy# s
s v
v' (Int -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. Int -> k -> a -> Map k a -> Map k a -> Map k a
Bin Int
n k
k v
v' Map k v
l Map k v
r)
            Maybe v
Nothing -> Map k v -> Map k v -> Map k v
forall k a. Map k a -> Map k a -> Map k a
Map.link2 Map k v
l Map k v
r
        (Bool
True, Bool
False)  -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall (f :: * -> *) (f :: * -> *) t a b.
(Functor f, Functor f) =>
f (t -> f a) -> (a -> b) -> f (t -> f b)
lift (Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
go Map k v
l) ((Map k v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> ((Map k v -> Map k v) -> Map k v -> Map k v)
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Map k v) -> Map k v -> Map k v
oneShot ((Map k v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a b. (a -> b) -> a -> b
$ \Map k v
l' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceL k
k' v
v Map k v
l' Map k v
r
        (Bool
False, Bool
True)  -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall (f :: * -> *) (f :: * -> *) t a b.
(Functor f, Functor f) =>
f (t -> f a) -> (a -> b) -> f (t -> f b)
lift (Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
go Map k v
r) ((Map k v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> ((Map k v -> Map k v) -> Map k v -> Map k v)
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Map k v) -> Map k v -> Map k v
oneShot ((Map k v -> Map k v)
 -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v)))
-> (Map k v -> Map k v)
-> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a b. (a -> b) -> a -> b
$ \Map k v
r' -> k -> v -> Map k v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a -> Map k a
Map.balanceL k
k' v
v Map k v
l Map k v
r'
        (Bool
False, Bool
False) -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))
forall a. LookupResult a
Incomparable

--
-- * Combine
--

-- ** Union

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@.
-- It prefers @t1@ when duplicate keys are encountered,
-- i.e. (@'union' == 'unionWith' 'const'@).
--
-- >>> union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
-- True
union :: PartialOrd k => POMap k v -> POMap k v -> POMap k v
union :: POMap k v -> POMap k v -> POMap k v
union = ((v -> v -> v) -> POMap k v -> POMap k v -> POMap k v)
-> (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
forall a. a -> a
inline (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
forall k v.
PartialOrd k =>
(v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINABLE union #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Union with a combining function.
--
-- >>> unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
-- True
unionWith :: PartialOrd k => (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWith :: (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWith v -> v -> v
f = ((k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v)
-> (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
forall a. a -> a
inline (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
forall k v.
PartialOrd k =>
(k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE unionWith #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Union with a combining function.
--
-- >>> 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")]
-- True
unionWithKey :: PartialOrd k => (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWithKey :: (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWithKey k -> v -> v -> v
f POMap k v
l POMap k v
r = (POMap k v -> (k, v) -> POMap k v)
-> POMap k v -> [(k, v)] -> POMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\POMap k v
m (k
k, v
v) -> (Proxy# 'Lazy
 -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v)
-> Proxy# 'Lazy
-> (k -> v -> v -> v)
-> k
-> v
-> POMap k v
-> POMap k v
forall a. a -> a
inline Proxy# 'Lazy
-> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) k -> v -> v -> v
f k
k v
v POMap k v
m) POMap k v
r (POMap k v -> [(k, v)]
forall k v. POMap k v -> [(k, v)]
toList POMap k v
l)
{-# INLINABLE unionWithKey #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\).
-- The union of a list of maps:
--   (@'unions' == 'Prelude.foldl' 'union' 'empty'@).
--
-- >>> :{
--   unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--      == fromList [(3, "b"), (5, "a"), (7, "C")]
-- :}
-- True
--
-- >>> :{
--  unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
--      == fromList [(3, "B3"), (5, "A3"), (7, "C")]
-- :}
-- True
unions :: PartialOrd k => [POMap k v] -> POMap k v
unions :: [POMap k v] -> POMap k v
unions = ((v -> v -> v) -> [POMap k v] -> POMap k v)
-> (v -> v -> v) -> [POMap k v] -> POMap k v
forall a. a -> a
inline (v -> v -> v) -> [POMap k v] -> POMap k v
forall k v.
PartialOrd k =>
(v -> v -> v) -> [POMap k v] -> POMap k v
unionsWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINABLE unions #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max_i n_i\) and \(w=\max_i w_i\).
-- The union of a list of maps, with a combining operation:
--   (@'unionsWith' f == 'Prelude.foldl' ('unionWith' f) 'empty'@).
--
-- >>> :{
--  unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--      == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
-- :}
-- True
unionsWith :: PartialOrd k => (v -> v -> v) -> [POMap k v] -> POMap k v
unionsWith :: (v -> v -> v) -> [POMap k v] -> POMap k v
unionsWith v -> v -> v
f = (POMap k v -> POMap k v -> POMap k v)
-> POMap k v -> [POMap k v] -> POMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ((v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
forall k v.
PartialOrd k =>
(v -> v -> v) -> POMap k v -> POMap k v -> POMap k v
unionWith v -> v -> v
f) POMap k v
forall k v. POMap k v
empty
{-# INLINABLE unionsWith #-}

-- * Difference

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Difference of two maps.
-- Return elements of the first map not existing in the second map.
--
-- >>> difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
-- fromList [(3,"b")]
difference :: PartialOrd k => POMap k a -> POMap k b -> POMap k a
difference :: POMap k a -> POMap k b -> POMap k a
difference = ((a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a)
-> (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
forall a. a -> a
inline (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
forall k a b.
PartialOrd k =>
(a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWith (\a
_ b
_ -> Maybe a
forall a. Maybe a
Nothing)
{-# INLINABLE difference #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- 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@.
--
-- >>> 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")])
-- fromList [(3,"b:B")]
differenceWith :: PartialOrd k => (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWith :: (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWith a -> b -> Maybe a
f = ((k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a)
-> (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
forall a. a -> a
inline (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
forall k a b.
PartialOrd k =>
(k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWithKey ((a -> b -> Maybe a) -> k -> a -> b -> Maybe a
forall a b. a -> b -> a
const a -> b -> Maybe a
f)
{-# INLINABLE differenceWith #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- 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@.
--
-- >>> 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")])
-- fromList [(3,"3:b|B")]
differenceWithKey :: PartialOrd k => (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWithKey :: (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a
differenceWithKey k -> a -> b -> Maybe a
f POMap k a
l
  = (POMap k a -> (k, b) -> POMap k a)
-> POMap k a -> [(k, b)] -> POMap k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\POMap k a
m (k
k, b
v) -> (Proxy# 'Lazy
 -> (k -> Maybe a -> Maybe a) -> k -> POMap k a -> POMap k a)
-> Proxy# 'Lazy
-> (k -> Maybe a -> Maybe a)
-> k
-> POMap k a
-> POMap k a
forall a. a -> a
inline Proxy# 'Lazy
-> (k -> Maybe a -> Maybe a) -> k -> POMap k a -> POMap k a
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s
-> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) (b -> k -> Maybe a -> Maybe a
f' b
v) k
k POMap k a
m) POMap k a
l
  ([(k, b)] -> POMap k a)
-> (POMap k b -> [(k, b)]) -> POMap k b -> POMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k b -> [(k, b)]
forall k v. POMap k v -> [(k, v)]
toList
  where
    f' :: b -> k -> Maybe a -> Maybe a
f' b
_ k
_ Maybe a
Nothing   = Maybe a
forall a. Maybe a
Nothing
    f' b
v k
k (Just a
v') = k -> a -> b -> Maybe a
f k
k a
v' b
v
{-# INLINABLE differenceWithKey #-}

-- ** Intersection

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Intersection of two maps.
-- Return data in the first map for the keys existing in both maps.
-- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@).
--
-- >>> intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
-- fromList [(5,"a")]
intersection :: PartialOrd k => POMap k a -> POMap k b -> POMap k a
intersection :: POMap k a -> POMap k b -> POMap k a
intersection = ((a -> b -> a) -> POMap k a -> POMap k b -> POMap k a)
-> (a -> b -> a) -> POMap k a -> POMap k b -> POMap k a
forall a. a -> a
inline (a -> b -> a) -> POMap k a -> POMap k b -> POMap k a
forall k a b c.
PartialOrd k =>
(a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWith a -> b -> a
forall a b. a -> b -> a
const
{-# INLINABLE intersection #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Intersection with a combining function.
--
-- >>> intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
-- fromList [(5,"aA")]
intersectionWith :: PartialOrd k => (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWith :: (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWith a -> b -> c
f = ((k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c)
-> (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
forall a. a -> a
inline (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
forall k a b c.
PartialOrd k =>
(k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWithKey ((a -> b -> c) -> k -> a -> b -> c
forall a b. a -> b -> a
const a -> b -> c
f)
{-# INLINABLE intersectionWith #-}

-- | \(\mathcal{O}(wn\log n)\), where \(n=\max(n_1,n_2)\) and \(w=\max(w_1,w_2)\).
-- Intersection with a combining function.
--
-- >>> let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
-- >>> intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
-- fromList [(5,"5:a|A")]
intersectionWithKey :: PartialOrd k => (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWithKey :: (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
intersectionWithKey k -> a -> b -> c
f POMap k a
l POMap k b
r
  = Proxy# 'Lazy -> [(k, c)] -> POMap k c
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> [(k, v)] -> POMap k v
fromListImpl (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy)
  ([(k, c)] -> POMap k c)
-> (POMap k a -> [(k, c)]) -> POMap k a -> POMap k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> Maybe (k, c)) -> [(k, a)] -> [(k, c)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe (\(k
k,a
a) -> [(k
k, k -> a -> b -> c
f k
k a
a b
b) | b
b <- k -> POMap k b -> Maybe b
forall k v. PartialOrd k => k -> POMap k v -> Maybe v
lookup k
k POMap k b
r])
  ([(k, a)] -> [(k, c)])
-> (POMap k a -> [(k, a)]) -> POMap k a -> [(k, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [(k, a)]
forall k v. POMap k v -> [(k, v)]
toList
  (POMap k a -> POMap k c) -> POMap k a -> POMap k c
forall a b. (a -> b) -> a -> b
$ POMap k a
l
{-# INLINABLE intersectionWithKey #-}


-- * Traversals

map :: SingIAreWeStrict s => Proxy# s -> (a -> b) -> POMap k a -> POMap k b
map :: Proxy# s -> (a -> b) -> POMap k a -> POMap k b
map Proxy# s
s a -> b
f (POMap Int
_ [Map k a]
chains)
  | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> Map k a -> Map k b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.Strict.map a -> b
f) [Map k a]
chains)
  | Bool
otherwise = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> Map k a -> Map k b
forall a b k. (a -> b) -> Map k a -> Map k b
Map.Lazy.map a -> b
f) [Map k a]
chains)
{-# NOINLINE [1] map #-}
{-# RULES
"map/map" forall s f g xs . map s f (map s g xs) = map s (f . g) xs
 #-}
{-# SPECIALIZE map :: Proxy# 'Strict -> (a -> b) -> POMap k a -> POMap k b #-}
{-# SPECIALIZE map :: Proxy# 'Lazy -> (a -> b) -> POMap k a -> POMap k b #-}

mapWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> b) -> POMap k a -> POMap k b
mapWithKey :: Proxy# s -> (k -> a -> b) -> POMap k a -> POMap k b
mapWithKey Proxy# s
s k -> a -> b
f (POMap Int
_ [Map k a]
d)
  | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> a -> b) -> Map k a -> Map k b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.Strict.mapWithKey k -> a -> b
f) [Map k a]
d)
  | Bool
otherwise = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> a -> b) -> Map k a -> Map k b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
Map.Lazy.mapWithKey k -> a -> b
f) [Map k a]
d)
{-# NOINLINE [1] mapWithKey #-}
{-# RULES
"mapWithKey/mapWithKey" forall s f g xs . mapWithKey s f (mapWithKey s g xs) =
  mapWithKey s (\k a -> f k (g k a)) xs
"mapWithKey/map" forall s f g xs . mapWithKey s f (map s g xs) =
  mapWithKey s (\k a -> f k (g a)) xs
"map/mapWithKey" forall s f g xs . map s f (mapWithKey s g xs) =
  mapWithKey s (\k a -> f (g k a)) xs
 #-}
{-# SPECIALIZE mapWithKey :: Proxy# 'Strict -> (k -> a -> b) -> POMap k a -> POMap k b #-}
{-# SPECIALIZE mapWithKey :: Proxy# 'Lazy -> (k -> a -> b) -> POMap k a -> POMap k b #-}

traverseWithKey :: (Applicative t, SingIAreWeStrict s) => Proxy# s -> (k -> a -> t b) -> POMap k a -> t (POMap k b)
traverseWithKey :: Proxy# s -> (k -> a -> t b) -> POMap k a -> t (POMap k b)
traverseWithKey Proxy# s
s k -> a -> t b
f (POMap Int
_ [Map k a]
d)
  | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k b] -> POMap k b) -> t [Map k b] -> t (POMap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Map k a -> t (Map k b)) -> [Map k a] -> t [Map k b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((k -> a -> t b) -> Map k a -> t (Map k b)
forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.Strict.traverseWithKey k -> a -> t b
f) [Map k a]
d
  | Bool
otherwise = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k b] -> POMap k b) -> t [Map k b] -> t (POMap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Map k a -> t (Map k b)) -> [Map k a] -> t [Map k b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((k -> a -> t b) -> Map k a -> t (Map k b)
forall (t :: * -> *) k a b.
Applicative t =>
(k -> a -> t b) -> Map k a -> t (Map k b)
Map.Lazy.traverseWithKey k -> a -> t b
f) [Map k a]
d
{-# INLINABLE traverseWithKey #-}
{-# SPECIALIZE traverseWithKey :: Applicative t => Proxy# 'Strict -> (k -> a -> t b) -> POMap k a -> t (POMap k b) #-}
{-# SPECIALIZE traverseWithKey :: Applicative t => Proxy# 'Lazy -> (k -> a -> t b) -> POMap k a -> t (POMap k b) #-}

mapAccum :: SingIAreWeStrict s => Proxy# s -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccum :: Proxy# s -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccum Proxy# s
s a -> b -> (a, c)
f = (Proxy# s
 -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c))
-> Proxy# s
-> (a -> k -> b -> (a, c))
-> a
-> POMap k b
-> (a, POMap k c)
forall a. a -> a
inline Proxy# s
-> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
forall (s :: AreWeStrict) a k b c.
SingIAreWeStrict s =>
Proxy# s
-> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccumWithKey Proxy# s
s (\a
a k
_ b
b -> a -> b -> (a, c)
f a
a b
b)
{-# INLINABLE mapAccum #-}
{-# SPECIALIZE mapAccum :: Proxy# 'Strict -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c) #-}
{-# SPECIALIZE mapAccum :: Proxy# 'Lazy -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c) #-}

mapAccumWithKey :: SingIAreWeStrict s => Proxy# s -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccumWithKey :: Proxy# s
-> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccumWithKey Proxy# s
s a -> k -> b -> (a, c)
f a
acc (POMap Int
_ [Map k b]
chains) = (a
acc', [Map k c] -> POMap k c
forall k v. [Map k v] -> POMap k v
mkPOMap [Map k c]
chains')
  where
    (a
acc', [Map k c]
chains')
      | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = (a -> Map k b -> (a, Map k c)) -> a -> [Map k b] -> (a, [Map k c])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
List.mapAccumL ((a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
Map.Strict.mapAccumWithKey a -> k -> b -> (a, c)
f) a
acc [Map k b]
chains
      | Bool
otherwise = (a -> Map k b -> (a, Map k c)) -> a -> [Map k b] -> (a, [Map k c])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
List.mapAccumL ((a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
Map.Lazy.mapAccumWithKey a -> k -> b -> (a, c)
f) a
acc [Map k b]
chains
{-# INLINABLE mapAccumWithKey #-}
{-# SPECIALIZE mapAccumWithKey :: Proxy# 'Strict -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c) #-}
{-# SPECIALIZE mapAccumWithKey :: Proxy# 'Lazy -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c) #-}

-- | \(\mathcal{O}(wn\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.
--
-- >>> mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
-- True
-- >>> mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
-- fromList [(1,"c")]
-- >>> mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
-- fromList [(3,"c")]
mapKeys :: PartialOrd k2 => (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeys :: (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeys k1 -> k2
f = Proxy# 'Lazy -> [(k2, v)] -> POMap k2 v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> [(k, v)] -> POMap k v
fromListImpl (Proxy# 'Lazy
forall k (a :: k). Proxy# a
proxy# :: Proxy# 'Lazy) ([(k2, v)] -> POMap k2 v)
-> (POMap k1 v -> [(k2, v)]) -> POMap k1 v -> POMap k2 v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1, v) -> (k2, v)) -> [(k1, v)] -> [(k2, v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k1 -> k2) -> (k1, v) -> (k2, v)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k1 -> k2
f) ([(k1, v)] -> [(k2, v)])
-> (POMap k1 v -> [(k1, v)]) -> POMap k1 v -> [(k2, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k1 v -> [(k1, v)]
forall k v. POMap k v -> [(k, v)]
toList

mapKeysWith :: (PartialOrd k2, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeysWith :: Proxy# s -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeysWith Proxy# s
s v -> v -> v
c k1 -> k2
f = Proxy# s -> (v -> v -> v) -> [(k2, v)] -> POMap k2 v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (v -> v -> v) -> [(k, v)] -> POMap k v
fromListWith Proxy# s
s v -> v -> v
c ([(k2, v)] -> POMap k2 v)
-> (POMap k1 v -> [(k2, v)]) -> POMap k1 v -> POMap k2 v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k1, v) -> (k2, v)) -> [(k1, v)] -> [(k2, v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k1 -> k2) -> (k1, v) -> (k2, v)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k1 -> k2
f) ([(k1, v)] -> [(k2, v)])
-> (POMap k1 v -> [(k1, v)]) -> POMap k1 v -> [(k2, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k1 v -> [(k1, v)]
forall k v. POMap k v -> [(k, v)]
toList
{-# INLINABLE mapKeysWith #-}
{-# SPECIALIZE mapKeysWith :: PartialOrd k2 => Proxy# 'Strict -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v #-}
{-# SPECIALIZE mapKeysWith :: PartialOrd k2 => Proxy# 'Lazy -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v #-}

-- | \(\mathcal{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, for every chain @ls@ in @s@ we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapKeysMonotonic f s == mapKeys f s
--
-- This means that @f@ maps distinct original keys to distinct resulting keys.
-- This function has better performance than 'mapKeys'.
--
-- >>> mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
-- True
mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeysMonotonic k1 -> k2
f (POMap Int
_ [Map k1 v]
d) = [Map k2 v] -> POMap k2 v
forall k v. [Map k v] -> POMap k v
mkPOMap ((Map k1 v -> Map k2 v) -> [Map k1 v] -> [Map k2 v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k1 -> k2) -> Map k1 v -> Map k2 v
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysMonotonic k1 -> k2
f) [Map k1 v]
d)

--
-- * Folds
--

-- | \(\mathcal{O}(n)\).
-- A strict version of 'foldr'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POMap k a -> b
foldr' :: (a -> b -> b) -> b -> POMap k a -> b
foldr' a -> b -> b
f b
acc = (Map k a -> b -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr ((b -> Map k a -> b) -> Map k a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b -> b) -> b -> Map k a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr' a -> b -> b
f)) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldr' #-}

-- | \(\mathcal{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,
--
-- >>> keys map = foldrWithKey (\k x ks -> k:ks) [] map
--
-- >>> let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
-- >>> foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
-- True
foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b
foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b
foldrWithKey k -> a -> b -> b
f b
acc = (Map k a -> b -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr ((b -> Map k a -> b) -> Map k a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey k -> a -> b -> b
f)) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldrWithKey #-}

-- | \(\mathcal{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 -> POMap k a -> b
foldrWithKey' :: (k -> a -> b -> b) -> b -> POMap k a -> b
foldrWithKey' k -> a -> b -> b
f b
acc = (Map k a -> b -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr ((b -> Map k a -> b) -> Map k a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
Map.foldrWithKey' k -> a -> b -> b
f)) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldrWithKey' #-}

-- | \(\mathcal{O}(n)\).
-- A strict version of 'foldl'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POMap k a -> b
foldl' :: (b -> a -> b) -> b -> POMap k a -> b
foldl' b -> a -> b
f b
acc = (b -> Map k a -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ((b -> a -> b) -> b -> Map k a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl' b -> a -> b
f) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldl' #-}

-- | \(\mathcal{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'@.
--
-- >>> keys = reverse . foldlWithKey (\ks k x -> k:ks) []
--
-- >>> let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
-- >>> foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
-- True
foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b
foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b
foldlWithKey b -> k -> a -> b
f b
acc = (b -> Map k a -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl ((b -> k -> a -> b) -> b -> Map k a -> b
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey b -> k -> a -> b
f) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldlWithKey #-}

-- | \(\mathcal{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' :: (b -> k -> a -> b) -> b -> POMap k a -> b
foldlWithKey' :: (b -> k -> a -> b) -> b -> POMap k a -> b
foldlWithKey' b -> k -> a -> b
f b
acc = (b -> Map k a -> b) -> b -> [Map k a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' ((b -> k -> a -> b) -> b -> Map k a -> b
forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
Map.foldlWithKey' b -> k -> a -> b
f) b
acc ([Map k a] -> b) -> (POMap k a -> [Map k a]) -> POMap k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldlWithKey' #-}

-- | \(\mathcal{O}(n)\).
-- Fold the keys and values in the map using the given monoid, such that
--
-- @'foldMapWithKey' f = 'Prelude.fold' . 'mapWithKey' f@
foldMapWithKey :: Monoid m => (k -> a -> m) -> POMap k a -> m
foldMapWithKey :: (k -> a -> m) -> POMap k a -> m
foldMapWithKey k -> a -> m
f = (Map k a -> m) -> [Map k a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((k -> a -> m) -> Map k a -> m
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey k -> a -> m
f ) ([Map k a] -> m) -> (POMap k a -> [Map k a]) -> POMap k a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [Map k a]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINE foldMapWithKey #-}

-- * Conversion

-- | \(\mathcal{O}(n)\).
-- Return all elements of the map in unspecified order.
--
-- >>> elems (fromList [(5,"a"), (3,"b")])
-- ["b","a"]
-- >>> elems empty
-- []
elems :: POMap k v -> [v]
elems :: POMap k v -> [v]
elems = (Map k v -> [v]) -> [Map k v] -> [v]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Map k v -> [v]
forall k a. Map k a -> [a]
Map.elems ([Map k v] -> [v]) -> (POMap k v -> [Map k v]) -> POMap k v -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

-- | \(\mathcal{O}(n)\).
-- Return all keys of the map in unspecified order.
--
-- >>> keys (fromList [(5,"a"), (3,"b")])
-- [3,5]
-- >>> keys empty
-- []
keys :: POMap k v -> [k]
keys :: POMap k v -> [k]
keys = (Map k v -> [k]) -> [Map k v] -> [k]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Map k v -> [k]
forall k a. Map k a -> [k]
Map.keys ([Map k v] -> [k]) -> (POMap k v -> [Map k v]) -> POMap k v -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

-- | \(\mathcal{O}(n)\).
-- Return all key\/value pairs in the map
-- in unspecified order.
--
-- >>> assocs (fromList [(5,"a"), (3,"b")])
-- [(3,"b"),(5,"a")]
-- >>> assocs empty
-- []
assocs :: POMap k v -> [(k, v)]
assocs :: POMap k v -> [(k, v)]
assocs = (Map k v -> [(k, v)]) -> [Map k v] -> [(k, v)]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toList ([Map k v] -> [(k, v)])
-> (POMap k v -> [Map k v]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

-- | \(\mathcal{O}(n)\).
-- Return all key\/value pairs in the map
-- in unspecified order.
--
-- Currently, @toList = 'assocs'@.
toList :: POMap k v -> [(k, v)]
toList :: POMap k v -> [(k, v)]
toList = POMap k v -> [(k, v)]
forall k v. POMap k v -> [(k, v)]
assocs

-- | \(\mathcal{O}(w^2n)\).
-- Return all key\/value pairs in the map such that
-- @map fst (toLinearisation m)@ is a /linearisation/ of the all keys present in
-- the map.
-- E.g., for any key @k1@ occuring before @k2@ in the linearisation, it
-- cannot happen that @k1@ is strictly greater than @k2@ (so they are either
-- incomparable or @k1 <= k2@).
toLinearisation :: PartialOrd k => POMap k v -> [(k, v)]
-- TODO: fusion? I'm not sure it's possible due to @dedupAntichain@
toLinearisation :: POMap k v -> [(k, v)]
toLinearisation = [[(k, v)]] -> [(k, v)]
forall a b. PartialOrd a => [[(a, b)]] -> [(a, b)]
concatLevels ([[(k, v)]] -> [(k, v)])
-> (POMap k v -> [[(k, v)]]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> [(k, v)]) -> [Map k v] -> [[(k, v)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toAscList ([Map k v] -> [[(k, v)]])
-> (POMap k v -> [Map k v]) -> POMap k v -> [[(k, v)]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
  where
    concatLevels :: [[(a, b)]] -> [(a, b)]
concatLevels [] = []
    concatLevels [[(a, b)]]
chains
      | ([(a, b)]
sinks, [[(a, b)]]
chains') <- [[(a, b)]] -> ([(a, b)], [[(a, b)]])
forall a b. PartialOrd a => [[(a, b)]] -> ([(a, b)], [[(a, b)]])
findSinks [[(a, b)]]
chains
      = [(a, b)]
sinks [(a, b)] -> [(a, b)] -> [(a, b)]
forall a. [a] -> [a] -> [a]
++ [[(a, b)]] -> [(a, b)]
concatLevels [[(a, b)]]
chains'

    findSinks :: [[(a, b)]] -> ([(a, b)], [[(a, b)]])
findSinks [[(a, b)]]
chains =
      let nonEmpties :: [NonEmpty (a, b)]
nonEmpties = ([(a, b)] -> Maybe (NonEmpty (a, b)))
-> [[(a, b)]] -> [NonEmpty (a, b)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe [(a, b)] -> Maybe (NonEmpty (a, b))
forall a. [a] -> Maybe (NonEmpty a)
NonEmpty.nonEmpty [[(a, b)]]
chains
          heads :: [(a, b)]
heads = NonEmpty (a, b) -> (a, b)
forall a. NonEmpty a -> a
NonEmpty.head (NonEmpty (a, b) -> (a, b)) -> [NonEmpty (a, b)] -> [(a, b)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [NonEmpty (a, b)]
nonEmpties
          sinks :: [(a, b)]
sinks = RelationalOperator -> [(a, b)] -> [(a, b)]
forall k v.
PartialOrd k =>
RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain RelationalOperator
LessThan [(a, b)]
heads
          chains' :: [[(a, b)]]
chains' = [(a, b)] -> NonEmpty (a, b) -> [(a, b)]
forall a b b. Eq a => [(a, b)] -> NonEmpty (a, b) -> [(a, b)]
deleteHead [(a, b)]
sinks (NonEmpty (a, b) -> [(a, b)]) -> [NonEmpty (a, b)] -> [[(a, b)]]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [NonEmpty (a, b)]
nonEmpties
      in ([(a, b)]
sinks, [[(a, b)]]
chains')

    deleteHead :: [(a, b)] -> NonEmpty (a, b) -> [(a, b)]
deleteHead [(a, b)]
sinks (cur :: (a, b)
cur@(a
k, b
_) :| [(a, b)]
chain)
      | Just b
_ <- a -> [(a, b)] -> Maybe b
forall a b. Eq a => a -> [(a, b)] -> Maybe b
List.lookup a
k [(a, b)]
sinks = [(a, b)]
chain
      | Bool
otherwise = (a, b)
cur(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
chain
{-# INLINABLE toLinearisation #-}

fromLinearisation :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> [(k, v)] -> POMap k v
-- TODO: We could possibly take advantage by using fromAscList to construct the
-- chains in O(wn), but I don't know of a good way to split into anti-chains
-- before.
fromLinearisation :: Proxy# s -> [(k, v)] -> POMap k v
fromLinearisation = Proxy# s -> [(k, v)] -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> [(k, v)] -> POMap k v
fromListImpl
{-# INLINABLE fromLinearisation #-}
{-# SPECIALIZE fromLinearisation :: PartialOrd k => Proxy# 'Strict -> [(k, v)] -> POMap k v #-}
{-# SPECIALIZE fromLinearisation :: PartialOrd k => Proxy# 'Lazy -> [(k, v)] -> POMap k v #-}

-- TODO: keysSet, fromSet

-- | Intentionally named this way, to disambiguate it from 'fromList'.
-- This is so that we can doctest this module.
fromListImpl :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> [(k, v)] -> POMap k v
fromListImpl :: Proxy# s -> [(k, v)] -> POMap k v
fromListImpl Proxy# s
s = (POMap k v -> (k, v) -> POMap k v)
-> POMap k v -> [(k, v)] -> POMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\POMap k v
m (k
k,v
v) -> Proxy# s -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> k -> v -> POMap k v -> POMap k v
insert Proxy# s
s k
k v
v POMap k v
m) POMap k v
forall k v. POMap k v
empty
{-# INLINABLE fromListImpl #-}
{-# SPECIALIZE fromListImpl :: PartialOrd k => Proxy# 'Strict -> [(k, v)] -> POMap k v #-}
{-# SPECIALIZE fromListImpl :: PartialOrd k => Proxy# 'Lazy -> [(k, v)] -> POMap k v #-}

fromListWith :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> [(k, v)] -> POMap k v
fromListWith :: Proxy# s -> (v -> v -> v) -> [(k, v)] -> POMap k v
fromListWith Proxy# s
s v -> v -> v
f = (POMap k v -> (k, v) -> POMap k v)
-> POMap k v -> [(k, v)] -> POMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\POMap k v
m (k
k,v
v) -> Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWith Proxy# s
s v -> v -> v
f k
k v
v POMap k v
m) POMap k v
forall k v. POMap k v
empty
{-# INLINABLE fromListWith #-}
{-# SPECIALIZE fromListWith :: PartialOrd k => Proxy# 'Strict -> (v -> v -> v) -> [(k, v)] -> POMap k v #-}
{-# SPECIALIZE fromListWith :: PartialOrd k => Proxy# 'Lazy -> (v -> v -> v) -> [(k, v)] -> POMap k v #-}

fromListWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v
fromListWithKey :: Proxy# s -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v
fromListWithKey Proxy# s
s k -> v -> v -> v
f = (POMap k v -> (k, v) -> POMap k v)
-> POMap k v -> [(k, v)] -> POMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\POMap k v
m (k
k,v
v) -> Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
forall k (s :: AreWeStrict) v.
(PartialOrd k, SingIAreWeStrict s) =>
Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey Proxy# s
s k -> v -> v -> v
f k
k v
v POMap k v
m) POMap k v
forall k v. POMap k v
empty
{-# INLINABLE fromListWithKey #-}
{-# SPECIALIZE fromListWithKey :: PartialOrd k => Proxy# 'Strict -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v #-}
{-# SPECIALIZE fromListWithKey :: PartialOrd k => Proxy# 'Lazy -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v #-}

--
-- * Filter
--

-- | \(\mathcal{O}(n)\).
-- Filter all values that satisfy the predicate.
--
-- >>> filter (> "a") (fromList [(5,"a"), (3,"b")])
-- fromList [(3,"b")]
-- >>> filter (> "x") (fromList [(5,"a"), (3,"b")])
-- fromList []
-- >>> filter (< "a") (fromList [(5,"a"), (3,"b")])
-- fromList []
filter :: (v -> Bool) -> POMap k v -> POMap k v
filter :: (v -> Bool) -> POMap k v -> POMap k v
filter v -> Bool
p = (k -> v -> Bool) -> POMap k v -> POMap k v
forall k v. (k -> v -> Bool) -> POMap k v -> POMap k v
filterWithKey ((v -> Bool) -> k -> v -> Bool
forall a b. a -> b -> a
const v -> Bool
p)

-- | \(\mathcal{O}(n)\).
-- Filter all keys\/values that satisfy the predicate.
--
-- >>> filterWithKey (\(Div k) _ -> k > 4) (fromList [(5,"a"), (3,"b")])
-- fromList [(5,"a")]
filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v
filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v
filterWithKey k -> v -> Bool
p (POMap Int
_ [Map k v]
d) = [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ((k -> v -> Bool) -> Map k v -> Map k v
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
Map.filterWithKey k -> v -> Bool
p (Map k v -> Map k v) -> [Map k v] -> [Map k v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Map k v]
d)

-- TODO: restrictKeys, withoutKeys

-- | \(\mathcal{O}(n)\).
-- Partition the map according to a predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 'split'.
--
-- >>> partition (> "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
-- True
-- >>> partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
-- True
-- >>> partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
-- True
partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
partition v -> Bool
p = (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
forall k v. (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
partitionWithKey ((v -> Bool) -> k -> v -> Bool
forall a b. a -> b -> a
const v -> Bool
p)

-- | \(\mathcal{O}(n)\).
-- Partition the map according to a predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 'split'.
--
-- >>> partitionWithKey (\ (Div k) _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
-- True
-- >>> partitionWithKey (\ (Div k) _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
-- True
-- >>> partitionWithKey (\ (Div k) _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
-- True
partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)
partitionWithKey k -> v -> Bool
p (POMap Int
_ [Map k v]
d)
  = ([Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k v] -> POMap k v)
-> ([Map k v] -> POMap k v)
-> ([Map k v], [Map k v])
-> (POMap k v, POMap k v)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap)
  (([Map k v], [Map k v]) -> (POMap k v, POMap k v))
-> ([Map k v] -> ([Map k v], [Map k v]))
-> [Map k v]
-> (POMap k v, POMap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Map k v, Map k v)] -> ([Map k v], [Map k v])
forall a b. [(a, b)] -> ([a], [b])
unzip
  ([(Map k v, Map k v)] -> ([Map k v], [Map k v]))
-> ([Map k v] -> [(Map k v, Map k v)])
-> [Map k v]
-> ([Map k v], [Map k v])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> (Map k v, Map k v))
-> [Map k v] -> [(Map k v, Map k v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> v -> Bool) -> Map k v -> (Map k v, Map k v)
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
Map.partitionWithKey k -> v -> Bool
p)
  ([Map k v] -> (POMap k v, POMap k v))
-> [Map k v] -> (POMap k v, POMap k v)
forall a b. (a -> b) -> a -> b
$ [Map k v]
d

-- | \(\mathcal{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'.
--
-- @
-- takeWhileAntitone p = 'filterWithKey' (\k _ -> p k)
-- @
--
-- @since 0.0.1.0
takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v
takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v
takeWhileAntitone k -> Bool
p = [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k v] -> POMap k v)
-> (POMap k v -> [Map k v]) -> POMap k v -> POMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Map k v) -> [Map k v] -> [Map k v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> Bool) -> Map k v -> Map k v
forall k a. (k -> Bool) -> Map k a -> Map k a
Map.Strict.takeWhileAntitone k -> Bool
p) ([Map k v] -> [Map k v])
-> (POMap k v -> [Map k v]) -> POMap k v -> [Map k v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

-- | \(\mathcal{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 = 'filterWithKey' (\k -> not (p k))
-- @
--
-- @since 0.0.1.0
dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v
dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v
dropWhileAntitone k -> Bool
p = [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k v] -> POMap k v)
-> (POMap k v -> [Map k v]) -> POMap k v -> POMap k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Map k v) -> [Map k v] -> [Map k v]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> Bool) -> Map k v -> Map k v
forall k a. (k -> Bool) -> Map k a -> Map k a
Map.Strict.dropWhileAntitone k -> Bool
p) ([Map k v] -> [Map k v])
-> (POMap k v -> [Map k v]) -> POMap k v -> [Map k v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

-- | \(\mathcal{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@.
--
-- @
-- 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).
--
-- @since 0.0.1.0
spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)
spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)
spanAntitone k -> Bool
p = ([Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k v] -> POMap k v)
-> ([Map k v] -> POMap k v)
-> ([Map k v], [Map k v])
-> (POMap k v, POMap k v)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Map k v] -> POMap k v
forall k v. [Map k v] -> POMap k v
mkPOMap) (([Map k v], [Map k v]) -> (POMap k v, POMap k v))
-> (POMap k v -> ([Map k v], [Map k v]))
-> POMap k v
-> (POMap k v, POMap k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Map k v, Map k v)] -> ([Map k v], [Map k v])
forall a b. [(a, b)] -> ([a], [b])
unzip ([(Map k v, Map k v)] -> ([Map k v], [Map k v]))
-> (POMap k v -> [(Map k v, Map k v)])
-> POMap k v
-> ([Map k v], [Map k v])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> (Map k v, Map k v))
-> [Map k v] -> [(Map k v, Map k v)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> Bool) -> Map k v -> (Map k v, Map k v)
forall k a. (k -> Bool) -> Map k a -> (Map k a, Map k a)
Map.Strict.spanAntitone k -> Bool
p) ([Map k v] -> [(Map k v, Map k v)])
-> (POMap k v -> [Map k v]) -> POMap k v -> [(Map k v, Map k v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition

mapMaybe :: SingIAreWeStrict s => Proxy# s -> (a -> Maybe b) -> POMap k a -> POMap k b
mapMaybe :: Proxy# s -> (a -> Maybe b) -> POMap k a -> POMap k b
mapMaybe Proxy# s
s a -> Maybe b
f = Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b
forall (s :: AreWeStrict) k a b.
SingIAreWeStrict s =>
Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b
mapMaybeWithKey Proxy# s
s ((a -> Maybe b) -> k -> a -> Maybe b
forall a b. a -> b -> a
const a -> Maybe b
f)
{-# INLINABLE mapMaybe #-}
{-# SPECIALIZE mapMaybe :: Proxy# 'Strict -> (a -> Maybe b) -> POMap k a -> POMap k b #-}
{-# SPECIALIZE mapMaybe :: Proxy# 'Lazy -> (a -> Maybe b) -> POMap k a -> POMap k b #-}

mapMaybeWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b
mapMaybeWithKey :: Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b
mapMaybeWithKey Proxy# s
s k -> a -> Maybe b
f (POMap Int
_ [Map k a]
d)
  | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((k -> a -> Maybe b) -> Map k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.Strict.mapMaybeWithKey k -> a -> Maybe b
f (Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Map k a]
d)
  | Bool
otherwise = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ((k -> a -> Maybe b) -> Map k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
Map.Lazy.mapMaybeWithKey k -> a -> Maybe b
f (Map k a -> Map k b) -> [Map k a] -> [Map k b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [Map k a]
d)
{-# INLINABLE mapMaybeWithKey #-}
{-# SPECIALIZE mapMaybeWithKey :: Proxy# 'Strict -> (k -> a -> Maybe b) -> POMap k a -> POMap k b #-}
{-# SPECIALIZE mapMaybeWithKey :: Proxy# 'Lazy -> (k -> a -> Maybe b) -> POMap k a -> POMap k b #-}

traverseMaybeWithKey :: (Applicative f, SingIAreWeStrict s) => Proxy# s -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b)
traverseMaybeWithKey :: Proxy# s -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b)
traverseMaybeWithKey Proxy# s
s k -> a -> f (Maybe b)
f (POMap Int
_ [Map k a]
d)
  | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k b] -> POMap k b) -> f [Map k b] -> f (POMap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Map k a -> f (Map k b)) -> [Map k a] -> f [Map k b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.Strict.traverseMaybeWithKey k -> a -> f (Maybe b)
f) [Map k a]
d
  | Bool
otherwise = [Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k b] -> POMap k b) -> f [Map k b] -> f (POMap k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Map k a -> f (Map k b)) -> [Map k a] -> f [Map k b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
Map.Lazy.traverseMaybeWithKey k -> a -> f (Maybe b)
f) [Map k a]
d
{-# INLINABLE traverseMaybeWithKey #-}
{-# SPECIALIZE traverseMaybeWithKey :: Applicative f => Proxy# 'Strict -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b) #-}
{-# SPECIALIZE traverseMaybeWithKey :: Applicative f => Proxy# 'Lazy -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b) #-}

mapEither :: SingIAreWeStrict s => Proxy# s -> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEither :: Proxy# s
-> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEither Proxy# s
s a -> Either b c
p = Proxy# s
-> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
forall (s :: AreWeStrict) k a b c.
SingIAreWeStrict s =>
Proxy# s
-> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEitherWithKey Proxy# s
s ((a -> Either b c) -> k -> a -> Either b c
forall a b. a -> b -> a
const a -> Either b c
p)
{-# INLINABLE mapEither #-}
{-# SPECIALIZE mapEither :: Proxy# 'Strict -> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c) #-}
{-# SPECIALIZE mapEither :: Proxy# 'Lazy -> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c) #-}

mapEitherWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEitherWithKey :: Proxy# s
-> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEitherWithKey Proxy# s
s k -> a -> Either b c
p (POMap Int
_ [Map k a]
d)
  = ([Map k b] -> POMap k b
forall k v. [Map k v] -> POMap k v
mkPOMap ([Map k b] -> POMap k b)
-> ([Map k c] -> POMap k c)
-> ([Map k b], [Map k c])
-> (POMap k b, POMap k c)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Map k c] -> POMap k c
forall k v. [Map k v] -> POMap k v
mkPOMap)
  (([Map k b], [Map k c]) -> (POMap k b, POMap k c))
-> ([Map k a] -> ([Map k b], [Map k c]))
-> [Map k a]
-> (POMap k b, POMap k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Map k b, Map k c)] -> ([Map k b], [Map k c])
forall a b. [(a, b)] -> ([a], [b])
unzip
  ([(Map k b, Map k c)] -> ([Map k b], [Map k c]))
-> ([Map k a] -> [(Map k b, Map k c)])
-> [Map k a]
-> ([Map k b], [Map k c])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k a -> (Map k b, Map k c))
-> [Map k a] -> [(Map k b, Map k c)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
mewk k -> a -> Either b c
p)
  ([Map k a] -> (POMap k b, POMap k c))
-> [Map k a] -> (POMap k b, POMap k c)
forall a b. (a -> b) -> a -> b
$ [Map k a]
d
  where
    mewk :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
mewk
      | AreWeStrict
Strict <- Proxy# s -> AreWeStrict
forall (s :: AreWeStrict).
SingIAreWeStrict s =>
Proxy# s -> AreWeStrict
areWeStrict Proxy# s
s = (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
Map.Strict.mapEitherWithKey
      | Bool
otherwise = (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
Map.Lazy.mapEitherWithKey
{-# INLINABLE mapEitherWithKey #-}
{-# SPECIALIZE mapEitherWithKey :: Proxy# 'Strict -> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c) #-}
{-# SPECIALIZE mapEitherWithKey :: Proxy# 'Lazy -> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c) #-}

-- TODO: Maybe `split*` variants, returning a triple, but that would
-- be rather inefficient anyway.

--
-- * Submap
--

-- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
-- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' (==)@).
isSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
isSubmapOf :: POMap k v -> POMap k v -> Bool
isSubmapOf = (v -> v -> Bool) -> POMap k v -> POMap k v -> Bool
forall k a b.
PartialOrd k =>
(a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isSubmapOfBy v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINABLE isSubmapOf #-}

{- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
 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 (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
 True
 >>> isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
 True
 >>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
 True

 But the following are all 'False':

 >>> isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
 False
 >>> isSubmapOfBy (<)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
 False
 >>> isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
 False
-}
isSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isSubmapOfBy :: (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isSubmapOfBy a -> b -> Bool
f POMap k a
s POMap k b
m
  = ((k, a) -> Bool) -> [(k, a)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (\(k
k, a
v) -> (b -> Bool) -> Maybe b -> Maybe Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a -> b -> Bool
f a
v) (k -> POMap k b -> Maybe b
forall k v. PartialOrd k => k -> POMap k v -> Maybe v
lookup k
k POMap k b
m) Maybe Bool -> Maybe Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bool -> Maybe Bool
forall a. a -> Maybe a
Just Bool
True)
  ([(k, a)] -> Bool) -> (POMap k a -> [(k, a)]) -> POMap k a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k a -> [(k, a)]
forall k v. POMap k v -> [(k, v)]
toList
  (POMap k a -> Bool) -> POMap k a -> Bool
forall a b. (a -> b) -> a -> b
$ POMap k a
s
{-# INLINABLE isSubmapOfBy #-}

-- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
-- Is this a proper submap? (ie. a submap but not equal).
-- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' (==)@).
isProperSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool
isProperSubmapOf :: POMap k v -> POMap k v -> Bool
isProperSubmapOf = (v -> v -> Bool) -> POMap k v -> POMap k v -> Bool
forall k a b.
PartialOrd k =>
(a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isProperSubmapOfBy v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINABLE isProperSubmapOf #-}

{- | \(\mathcal{O}(n_2 w_1 n_1 \log n_1)\).
 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 (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
  True
  >>> isProperSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
  True

 But the following are all 'False':

  >>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
  False
  >>> isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
  False
  >>> isProperSubmapOfBy (<)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
  False
-}
isProperSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isProperSubmapOfBy :: (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isProperSubmapOfBy a -> b -> Bool
f POMap k a
s POMap k b
m = POMap k a -> Int
forall k v. POMap k v -> Int
size POMap k a
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< POMap k b -> Int
forall k v. POMap k v -> Int
size POMap k b
m Bool -> Bool -> Bool
&& (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
forall k a b.
PartialOrd k =>
(a -> b -> Bool) -> POMap k a -> POMap k b -> Bool
isSubmapOfBy a -> b -> Bool
f POMap k a
s POMap k b
m
{-# INLINABLE isProperSubmapOfBy #-}

--
-- * Min/Max
--

-- | \(\mathcal{O}(w\log n)\).
-- The minimal keys of the map.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupMin (fromList [(6,"a"), (3,"b")])
-- [(3,"b")]
-- >>> lookupMin empty
-- []
lookupMin :: PartialOrd k => POMap k v -> [(k, v)]
lookupMin :: POMap k v -> [(k, v)]
lookupMin = RelationalOperator -> [(k, v)] -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain RelationalOperator
LessThan ([(k, v)] -> [(k, v)])
-> (POMap k v -> [(k, v)]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Maybe (k, v)) -> [Map k v] -> [(k, v)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe Map k v -> Maybe (k, v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin ([Map k v] -> [(k, v)])
-> (POMap k v -> [Map k v]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINABLE lookupMin #-}

-- | \(\mathcal{O}(w\log n)\).
-- The maximal keys of the map.
--
-- Note that the following examples assume the @Divisibility@
-- partial order defined at the top.
--
-- >>> lookupMax (fromList [(6,"a"), (3,"b")])
-- [(6,"a")]
-- >>> lookupMax empty
-- []
lookupMax :: PartialOrd k => POMap k v -> [(k, v)]
lookupMax :: POMap k v -> [(k, v)]
lookupMax = RelationalOperator -> [(k, v)] -> [(k, v)]
forall k v.
PartialOrd k =>
RelationalOperator -> [(k, v)] -> [(k, v)]
dedupAntichain RelationalOperator
GreaterThan ([(k, v)] -> [(k, v)])
-> (POMap k v -> [(k, v)]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map k v -> Maybe (k, v)) -> [Map k v] -> [(k, v)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe Map k v -> Maybe (k, v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMax ([Map k v] -> [(k, v)])
-> (POMap k v -> [Map k v]) -> POMap k v -> [(k, v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. POMap k v -> [Map k v]
forall k v. POMap k v -> [Map k v]
chainDecomposition
{-# INLINABLE lookupMax #-}