-- |
--   Module      :  Data.Edison.Assoc.Defaults
--   Copyright   :  Copyright (c) 1998, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  internal (unstable)
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   This module provides default implementations of many of the associative
--   collection operations.  These function are used to fill in collection
--   implementations and are not intended to be used directly by end users.

module Data.Edison.Assoc.Defaults where

import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,filter)

import qualified Control.Monad.Fail as Fail

import Data.Edison.Assoc
import qualified Data.Edison.Seq as S
import qualified Data.Edison.Seq.ListSeq as L
import Data.Edison.Seq.Defaults (tokenMatch,maybeParens)

singletonUsingInsert :: (Assoc m k) => k -> a -> m a
singletonUsingInsert :: forall (m :: * -> *) k a. Assoc m k => k -> a -> m a
singletonUsingInsert k
k a
v = forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k a
v forall (m :: * -> *) k a. AssocX m k => m a
empty

fromSeqUsingInsertSeq :: (AssocX m k,S.Sequence seq) => seq (k,a) -> m a
fromSeqUsingInsertSeq :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a
fromSeqUsingInsertSeq seq (k, a)
kvs = forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a -> m a
insertSeq seq (k, a)
kvs forall (m :: * -> *) k a. AssocX m k => m a
empty

insertSeqUsingFoldr ::
    (AssocX m k,S.Sequence seq) => seq (k,a) -> m a -> m a
insertSeqUsingFoldr :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a -> m a
insertSeqUsingFoldr seq (k, a)
kvs m a
m = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert) m a
m seq (k, a)
kvs

unionSeqUsingReduce :: (AssocX m k,S.Sequence seq) => seq (m a) -> m a
unionSeqUsingReduce :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (m a) -> m a
unionSeqUsingReduce seq (m a)
ms = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducel forall (m :: * -> *) k a. AssocX m k => m a -> m a -> m a
union forall (m :: * -> *) k a. AssocX m k => m a
empty seq (m a)
ms

deleteSeqUsingFoldr :: (AssocX m k,S.Sequence seq) => seq k -> m a -> m a
deleteSeqUsingFoldr :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq k -> m a -> m a
deleteSeqUsingFoldr seq k
ks m a
m = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr forall (m :: * -> *) k a. AssocX m k => k -> m a -> m a
delete m a
m seq k
ks

memberUsingLookupM :: (AssocX m k) => k -> m a -> Bool
memberUsingLookupM :: forall (m :: * -> *) k a. AssocX m k => k -> m a -> Bool
memberUsingLookupM k
k m a
m
  = case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
        Just a
_  -> Bool
True
        Maybe a
Nothing -> Bool
False

countUsingMember :: AssocX m k => k -> m a -> Int
countUsingMember :: forall (m :: * -> *) k a. AssocX m k => k -> m a -> Int
countUsingMember k
k m a
m = if forall (m :: * -> *) k a. AssocX m k => k -> m a -> Bool
member k
k m a
m then Int
1 else Int
0

lookupAllUsingLookupM :: (AssocX m k,S.Sequence seq) => k -> m a -> seq a
lookupAllUsingLookupM :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
k -> m a -> seq a
lookupAllUsingLookupM k
k m a
m = case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
                              Just a
x -> forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
x
                              Maybe a
Nothing -> forall (s :: * -> *) a. Sequence s => s a
S.empty

lookupWithDefaultUsingLookupM :: AssocX m k => a -> k -> m a -> a
lookupWithDefaultUsingLookupM :: forall (m :: * -> *) k a. AssocX m k => a -> k -> m a -> a
lookupWithDefaultUsingLookupM a
d k
k m a
m = case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
                                        Just a
x -> a
x
                                        Maybe a
Nothing -> a
d

partitionUsingFilter :: AssocX m k => (a -> Bool) -> m a -> (m a,m a)
partitionUsingFilter :: forall (m :: * -> *) k a.
AssocX m k =>
(a -> Bool) -> m a -> (m a, m a)
partitionUsingFilter a -> Bool
f m a
m = (forall (m :: * -> *) k a. AssocX m k => (a -> Bool) -> m a -> m a
filter a -> Bool
f m a
m, forall (m :: * -> *) k a. AssocX m k => (a -> Bool) -> m a -> m a
filter (Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f) m a
m)

fold1UsingElements :: (AssocX m k) => (a -> a -> a) -> m a -> a
fold1UsingElements :: forall (m :: * -> *) k a. AssocX m k => (a -> a -> a) -> m a -> a
fold1UsingElements a -> a -> a
op m a
m = forall a. (a -> a -> a) -> [a] -> a
L.foldr1 a -> a -> a
op (forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
m a -> seq a
elements m a
m)

elementsUsingFold :: (AssocX m k,S.Sequence seq) => m a -> seq a
elementsUsingFold :: forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
m a -> seq a
elementsUsingFold = forall (m :: * -> *) k a b.
AssocX m k =>
(a -> b -> b) -> b -> m a -> b
fold forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons forall (s :: * -> *) a. Sequence s => s a
S.empty

nullUsingElements :: (AssocX m k) => m a -> Bool
nullUsingElements :: forall (m :: * -> *) k a. AssocX m k => m a -> Bool
nullUsingElements m a
m
  = case forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
m a -> seq a
elements m a
m of
        [] -> Bool
True
        [a]
_  -> Bool
False

insertWithUsingLookupM ::
    FiniteMapX m k => (a -> a -> a) -> k -> a -> m a -> m a
insertWithUsingLookupM :: forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> k -> a -> m a -> m a
insertWithUsingLookupM a -> a -> a
f k
k a
x m a
m =
    case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
      Maybe a
Nothing -> forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k a
x m a
m
      Just a
y  -> forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k (a -> a -> a
f a
x a
y) m a
m

fromSeqWithUsingInsertSeqWith ::
    (FiniteMapX m k,S.Sequence seq) => (a -> a -> a) -> seq (k,a) -> m a
fromSeqWithUsingInsertSeqWith :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a
fromSeqWithUsingInsertSeqWith a -> a -> a
f seq (k, a)
kvs = forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWith a -> a -> a
f seq (k, a)
kvs forall (m :: * -> *) k a. AssocX m k => m a
empty

fromSeqWithKeyUsingInsertSeqWithKey ::
    (FiniteMapX m k,S.Sequence seq) => (k -> a -> a -> a) -> seq (k,a) -> m a
fromSeqWithKeyUsingInsertSeqWithKey :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a
fromSeqWithKeyUsingInsertSeqWithKey k -> a -> a -> a
f seq (k, a)
kvs = forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKey k -> a -> a -> a
f seq (k, a)
kvs forall (m :: * -> *) k a. AssocX m k => m a
empty

insertWithKeyUsingInsertWith ::
    FiniteMapX m k => (k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKeyUsingInsertWith :: forall (m :: * -> *) k a.
FiniteMapX m k =>
(k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKeyUsingInsertWith k -> a -> a -> a
f k
k = forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> k -> a -> m a -> m a
insertWith (k -> a -> a -> a
f k
k) k
k

insertSeqWithUsingInsertWith ::
    (FiniteMapX m k,S.Sequence seq) =>
      (a -> a -> a) -> seq (k,a) -> m a -> m a
insertSeqWithUsingInsertWith :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithUsingInsertWith a -> a -> a
f seq (k, a)
kvs m a
m =
    forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> k -> a -> m a -> m a
insertWith a -> a -> a
f)) m a
m seq (k, a)
kvs

insertSeqWithKeyUsingInsertWithKey ::
    (FiniteMapX m k,S.Sequence seq) =>
      (k -> a -> a -> a) -> seq (k,a) -> m a -> m a
insertSeqWithKeyUsingInsertWithKey :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKeyUsingInsertWithKey k -> a -> a -> a
f seq (k, a)
kvs m a
m =
    forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (forall (m :: * -> *) k a.
FiniteMapX m k =>
(k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKey k -> a -> a -> a
f)) m a
m seq (k, a)
kvs

unionSeqWithUsingReduce ::
    (FiniteMapX m k,S.Sequence seq) => (a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingReduce :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingReduce a -> a -> a
f seq (m a)
ms = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducel (forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> m a -> m a -> m a
unionWith a -> a -> a
f) forall (m :: * -> *) k a. AssocX m k => m a
empty seq (m a)
ms

unionSeqWithUsingFoldr ::
    (FiniteMapX m k,S.Sequence seq) => (a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingFoldr :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingFoldr a -> a -> a
f seq (m a)
ms = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> m a -> m a -> m a
unionWith a -> a -> a
f) forall (m :: * -> *) k a. AssocX m k => m a
empty seq (m a)
ms

toSeqUsingFoldWithKey :: (Assoc m k,S.Sequence seq) => m a -> seq (k,a)
toSeqUsingFoldWithKey :: forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq (k, a)
toSeqUsingFoldWithKey = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {s :: * -> *} {a} {b}.
Sequence s =>
a -> b -> s (a, b) -> s (a, b)
conspair forall (s :: * -> *) a. Sequence s => s a
S.empty
  where conspair :: a -> b -> s (a, b) -> s (a, b)
conspair a
k b
v s (a, b)
kvs = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons (a
k,b
v) s (a, b)
kvs

keysUsingFoldWithKey :: (Assoc m k,S.Sequence seq) => m a -> seq k
keysUsingFoldWithKey :: forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq k
keysUsingFoldWithKey = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {s :: * -> *} {a} {p}. Sequence s => a -> p -> s a -> s a
conskey forall (s :: * -> *) a. Sequence s => s a
S.empty
  where conskey :: a -> p -> s a -> s a
conskey a
k p
_ s a
ks = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
k s a
ks

unionWithUsingInsertWith ::
    FiniteMap m k => (a -> a -> a) -> m a -> m a -> m a
unionWithUsingInsertWith :: forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> a) -> m a -> m a -> m a
unionWithUsingInsertWith a -> a -> a
f m a
m1 m a
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey (forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> k -> a -> m a -> m a
insertWith a -> a -> a
f) m a
m2 m a
m1

unionWithKeyUsingInsertWithKey ::
    FiniteMap m k => (k -> a -> a -> a) -> m a -> m a -> m a
unionWithKeyUsingInsertWithKey :: forall (m :: * -> *) k a.
FiniteMap m k =>
(k -> a -> a -> a) -> m a -> m a -> m a
unionWithKeyUsingInsertWithKey k -> a -> a -> a
f m a
m1 m a
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey (forall (m :: * -> *) k a.
FiniteMapX m k =>
(k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKey k -> a -> a -> a
f) m a
m2 m a
m1

unionSeqWithKeyUsingReduce ::
    (FiniteMap m k,S.Sequence seq) =>
      (k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingReduce :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMap m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingReduce k -> a -> a -> a
f seq (m a)
ms = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducel (forall (m :: * -> *) k a.
FiniteMap m k =>
(k -> a -> a -> a) -> m a -> m a -> m a
unionWithKey k -> a -> a -> a
f) forall (m :: * -> *) k a. AssocX m k => m a
empty seq (m a)
ms

unionSeqWithKeyUsingFoldr ::
    (FiniteMap m k,S.Sequence seq) =>
      (k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingFoldr :: forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMap m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingFoldr k -> a -> a -> a
f seq (m a)
ms = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall (m :: * -> *) k a.
FiniteMap m k =>
(k -> a -> a -> a) -> m a -> m a -> m a
unionWithKey k -> a -> a -> a
f) forall (m :: * -> *) k a. AssocX m k => m a
empty seq (m a)
ms

intersectionWithUsingLookupM ::
    FiniteMap m k => (a -> b -> c) -> m a -> m b -> m c
intersectionWithUsingLookupM :: forall (m :: * -> *) k a b c.
FiniteMap m k =>
(a -> b -> c) -> m a -> m b -> m c
intersectionWithUsingLookupM a -> b -> c
f m a
m1 m b
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {k} {m :: * -> *}.
(AssocX m k, AssocX m k) =>
k -> a -> m c -> m c
ins forall (m :: * -> *) k a. AssocX m k => m a
empty m a
m1
  where ins :: k -> a -> m c -> m c
ins k
k a
x m c
m = case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m b
m2 of
                      Maybe b
Nothing -> m c
m
                      Just b
y  -> forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k (a -> b -> c
f a
x b
y) m c
m

intersectionWithKeyUsingLookupM ::
    FiniteMap m k => (k -> a -> b -> c) -> m a -> m b -> m c
intersectionWithKeyUsingLookupM :: forall (m :: * -> *) k a b c.
FiniteMap m k =>
(k -> a -> b -> c) -> m a -> m b -> m c
intersectionWithKeyUsingLookupM k -> a -> b -> c
f m a
m1 m b
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {m :: * -> *}. AssocX m k => k -> a -> m c -> m c
ins forall (m :: * -> *) k a. AssocX m k => m a
empty m a
m1
  where ins :: k -> a -> m c -> m c
ins k
k a
x m c
m = case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m b
m2 of
                      Maybe b
Nothing -> m c
m
                      Just b
y  -> forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k (k -> a -> b -> c
f k
k a
x b
y) m c
m

differenceUsingDelete :: FiniteMap m k => m a -> m b -> m a
differenceUsingDelete :: forall (m :: * -> *) k a b. FiniteMap m k => m a -> m b -> m a
differenceUsingDelete m a
m1 m b
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {m :: * -> *} {k} {p} {a}.
AssocX m k =>
k -> p -> m a -> m a
del m a
m1 m b
m2
  where del :: k -> p -> m a -> m a
del k
k p
_ m a
m = forall (m :: * -> *) k a. AssocX m k => k -> m a -> m a
delete k
k m a
m

properSubsetUsingSubset :: FiniteMapX m k => m a -> m b -> Bool
properSubsetUsingSubset :: forall (m :: * -> *) k a b. FiniteMapX m k => m a -> m b -> Bool
properSubsetUsingSubset m a
m1 m b
m2 = forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m1 forall a. Ord a => a -> a -> Bool
< forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m b
m2 Bool -> Bool -> Bool
&& forall (m :: * -> *) k a b. FiniteMapX m k => m a -> m b -> Bool
subset m a
m1 m b
m2

subsetUsingMember :: FiniteMap m k => m a -> m b -> Bool
subsetUsingMember :: forall (m :: * -> *) k a b. FiniteMap m k => m a -> m b -> Bool
subsetUsingMember m a
m1 m b
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {k} {p}. AssocX m k => k -> p -> Bool -> Bool
mem Bool
True m a
m1
  where mem :: k -> p -> Bool -> Bool
mem k
k p
_ Bool
b = forall (m :: * -> *) k a. AssocX m k => k -> m a -> Bool
member k
k m b
m2 Bool -> Bool -> Bool
&& Bool
b

submapByUsingLookupM :: FiniteMap m k
                     => (a -> a -> Bool) -> m a -> m a -> Bool
submapByUsingLookupM :: forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapByUsingLookupM  a -> a -> Bool
f m a
m1 m a
m2 = forall (m :: * -> *) k a b.
Assoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldWithKey forall {k}. AssocX m k => k -> a -> Bool -> Bool
aux Bool
True m a
m1
  where aux :: k -> a -> Bool -> Bool
aux k
k a
x Bool
b =
          case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m2 of
             Maybe a
Nothing -> Bool
False
             Just a
y  -> a -> a -> Bool
f a
x a
y Bool -> Bool -> Bool
&& Bool
b

properSubmapByUsingSubmapBy :: FiniteMapX m k
                            => (a -> a -> Bool) -> m a -> m a -> Bool
properSubmapByUsingSubmapBy :: forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
properSubmapByUsingSubmapBy a -> a -> Bool
f m a
m1 m a
m2 = forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m1 forall a. Ord a => a -> a -> Bool
< forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m2 Bool -> Bool -> Bool
&& forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapBy a -> a -> Bool
f m a
m1 m a
m2

sameMapByUsingOrdLists :: OrdFiniteMap m k
                       => (a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingOrdLists :: forall (m :: * -> *) k a.
OrdFiniteMap m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingOrdLists a -> a -> Bool
f m a
m1 m a
m2 =
   let comp :: (a, a) -> (a, a) -> Bool
comp (a
k1,a
x1) (a
k2,a
x2) = a
k1 forall a. Eq a => a -> a -> Bool
== a
k2 Bool -> Bool -> Bool
&& a -> a -> Bool
f a
x1 a
x2
   in forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr Bool -> Bool -> Bool
(&&) (forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m1 forall a. Eq a => a -> a -> Bool
== forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m2) (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
L.zipWith forall {a}. Eq a => (a, a) -> (a, a) -> Bool
comp (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
m1) (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
m2))


sameMapByUsingSubmapBy :: FiniteMapX m k
                       => (a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingSubmapBy :: forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingSubmapBy a -> a -> Bool
f m a
m1 m a
m2 = forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m1 forall a. Eq a => a -> a -> Bool
== forall (m :: * -> *) k a. AssocX m k => m a -> Int
size m a
m2 Bool -> Bool -> Bool
&& forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapBy a -> a -> Bool
f m a
m1 m a
m2


lookupAndDeleteDefault :: AssocX m k => k -> m a -> (a, m a)
lookupAndDeleteDefault :: forall (m :: * -> *) k a. AssocX m k => k -> m a -> (a, m a)
lookupAndDeleteDefault k
k m a
m =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
     Maybe a
Nothing -> forall a. HasCallStack => [Char] -> a
error (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
m forall a. [a] -> [a] -> [a]
++ [Char]
".lookupAndDelete: lookup failed")
     Just a
x  -> (a
x, forall (m :: * -> *) k a. AssocX m k => k -> m a -> m a
delete k
k m a
m)

lookupAndDeleteMDefault :: (Fail.MonadFail rm, AssocX m k) => k -> m a -> rm (a, m a)
lookupAndDeleteMDefault :: forall (rm :: * -> *) (m :: * -> *) k a.
(MonadFail rm, AssocX m k) =>
k -> m a -> rm (a, m a)
lookupAndDeleteMDefault k
k m a
m =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm a
lookupM k
k m a
m of
     Maybe a
Nothing -> forall (m :: * -> *) a. MonadFail m => [Char] -> m a
fail (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
m forall a. [a] -> [a] -> [a]
++ [Char]
".lookupAndDelete: lookup failed")
     Just a
x  -> forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, forall (m :: * -> *) k a. AssocX m k => k -> m a -> m a
delete k
k m a
m)

lookupAndDeleteAllDefault :: (S.Sequence seq, AssocX m k) => k -> m a -> (seq a,m a)
lookupAndDeleteAllDefault :: forall (seq :: * -> *) (m :: * -> *) k a.
(Sequence seq, AssocX m k) =>
k -> m a -> (seq a, m a)
lookupAndDeleteAllDefault k
k m a
m = (forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
k -> m a -> seq a
lookupAll k
k m a
m,forall (m :: * -> *) k a. AssocX m k => k -> m a -> m a
deleteAll k
k m a
m)

adjustOrInsertUsingMember :: AssocX m k => (a -> a) -> a -> k -> m a -> m a
adjustOrInsertUsingMember :: forall (m :: * -> *) k a.
AssocX m k =>
(a -> a) -> a -> k -> m a -> m a
adjustOrInsertUsingMember a -> a
f a
z k
k m a
m =
  if forall (m :: * -> *) k a. AssocX m k => k -> m a -> Bool
member k
k m a
m
     then forall (m :: * -> *) k a. AssocX m k => (a -> a) -> k -> m a -> m a
adjust a -> a
f k
k m a
m
     else forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k a
z m a
m

adjustOrDeleteDefault :: AssocX m k => (a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteDefault :: forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteDefault a -> Maybe a
f k
k m a
m =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(AssocX m k, MonadFail rm) =>
k -> m a -> rm (a, m a)
lookupAndDeleteM k
k m a
m of
    Maybe (a, m a)
Nothing -> m a
m
    Just (a
element,m a
m') ->
      case a -> Maybe a
f a
element of
         Maybe a
Nothing -> m a
m'
         Just a
x  -> forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k a
x m a
m'

adjustOrDeleteAllDefault :: AssocX m k => (a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteAllDefault :: forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteAllDefault a -> Maybe a
f k
k m a
m =
  let ([a]
elems,m a
m') = forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
k -> m a -> (seq a, m a)
lookupAndDeleteAll k
k m a
m
      adjSeq :: [Maybe a]
adjSeq = forall (s :: * -> *) a b. Sequence s => (a -> b) -> s a -> s b
S.map a -> Maybe a
f [a]
elems
      ins :: Maybe a -> m a -> m a
ins Maybe a
Nothing  m a
n = m a
n
      ins (Just a
x) m a
n = forall (m :: * -> *) k a. AssocX m k => k -> a -> m a -> m a
insert k
k a
x m a
n
  in forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr forall {m :: * -> *} {a}. AssocX m k => Maybe a -> m a -> m a
ins m a
m' [Maybe a]
adjSeq

minElemUsingMinView :: OrdAssocX m k => m a -> a
minElemUsingMinView :: forall (m :: * -> *) k a. OrdAssocX m k => m a -> a
minElemUsingMinView m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssocX m k, MonadFail rm) =>
m a -> rm (a, m a)
minView m a
fm of
     Maybe (a, m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".minElem: empty map"
     Just (a
x,m a
_) -> a
x

deleteMinUsingMinView :: OrdAssocX m k => m a -> m a
deleteMinUsingMinView :: forall (m :: * -> *) k a. OrdAssocX m k => m a -> m a
deleteMinUsingMinView m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssocX m k, MonadFail rm) =>
m a -> rm (a, m a)
minView m a
fm of
     Maybe (a, m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".deleteMin: empty map"
     Just (a
_,m a
m) -> m a
m

minElemWithKeyUsingMinViewWithKey :: OrdAssoc m k => m a -> (k,a)
minElemWithKeyUsingMinViewWithKey :: forall (m :: * -> *) k a. OrdAssoc m k => m a -> (k, a)
minElemWithKeyUsingMinViewWithKey m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssoc m k, MonadFail rm) =>
m a -> rm ((k, a), m a)
minViewWithKey m a
fm of
     Maybe ((k, a), m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".minElemWithKey: empty map"
     Just ((k, a)
x,m a
_) -> (k, a)
x

maxElemUsingMaxView :: OrdAssocX m k => m a -> a
maxElemUsingMaxView :: forall (m :: * -> *) k a. OrdAssocX m k => m a -> a
maxElemUsingMaxView m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssocX m k, MonadFail rm) =>
m a -> rm (a, m a)
maxView m a
fm of
     Maybe (a, m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".maxElem: empty map"
     Just (a
x,m a
_) -> a
x

deleteMaxUsingMaxView :: OrdAssocX m k => m a -> m a
deleteMaxUsingMaxView :: forall (m :: * -> *) k a. OrdAssocX m k => m a -> m a
deleteMaxUsingMaxView m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssocX m k, MonadFail rm) =>
m a -> rm (a, m a)
maxView m a
fm of
     Maybe (a, m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".deleteMax: empty map"
     Just (a
_,m a
m) -> m a
m

maxElemWithKeyUsingMaxViewWithKey :: OrdAssoc m k => m a -> (k,a)
maxElemWithKeyUsingMaxViewWithKey :: forall (m :: * -> *) k a. OrdAssoc m k => m a -> (k, a)
maxElemWithKeyUsingMaxViewWithKey m a
fm =
  case forall (m :: * -> *) k (rm :: * -> *) a.
(OrdAssoc m k, MonadFail rm) =>
m a -> rm ((k, a), m a)
maxViewWithKey m a
fm of
     Maybe ((k, a), m a)
Nothing    -> forall a. HasCallStack => [Char] -> a
error forall a b. (a -> b) -> a -> b
$ (forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
fm)forall a. [a] -> [a] -> [a]
++[Char]
".maxElemWithKey: empty map"
     Just ((k, a)
x,m a
_) -> (k, a)
x

toOrdSeqUsingFoldrWithKey :: (OrdAssoc m k,S.Sequence seq) => m a -> seq (k,a)
toOrdSeqUsingFoldrWithKey :: forall (m :: * -> *) k (seq :: * -> *) a.
(OrdAssoc m k, Sequence seq) =>
m a -> seq (k, a)
toOrdSeqUsingFoldrWithKey = forall (m :: * -> *) k a b.
OrdAssoc m k =>
(k -> a -> b -> b) -> b -> m a -> b
foldrWithKey (\k
k a
x seq (k, a)
z -> forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons (k
k,a
x) seq (k, a)
z) forall (s :: * -> *) a. Sequence s => s a
S.empty

showsPrecUsingToList :: (Show k, Show a, Assoc m k) => Int -> m a -> ShowS
showsPrecUsingToList :: forall k a (m :: * -> *).
(Show k, Show a, Assoc m k) =>
Int -> m a -> ShowS
showsPrecUsingToList Int
i m a
xs [Char]
rest
   | Int
i forall a. Eq a => a -> a -> Bool
== Int
0    = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [    forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
xs,[Char]
".fromSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall (m :: * -> *) k a. Assoc m k => m a -> [(k, a)]
toList m a
xs) [Char]
rest]
   | Bool
otherwise = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Char]
"(",forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
xs,[Char]
".fromSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall (m :: * -> *) k a. Assoc m k => m a -> [(k, a)]
toList m a
xs) (Char
')'forall a. a -> [a] -> [a]
:[Char]
rest)]

readsPrecUsingFromList :: (Read k, Read a, AssocX m k) => Int -> ReadS (m a)
readsPrecUsingFromList :: forall k a (m :: * -> *).
(Read k, Read a, AssocX m k) =>
Int -> ReadS (m a)
readsPrecUsingFromList Int
_ [Char]
xs =
   let result :: [(m a, [Char])]
result = forall a. ReadS a -> ReadS a
maybeParens ReadS (m a)
p [Char]
xs
       p :: ReadS (m a)
p [Char]
ys = forall (m :: * -> *). MonadPlus m => [Char] -> [Char] -> m [Char]
tokenMatch ((forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
x)forall a. [a] -> [a] -> [a]
++[Char]
".fromSeq") [Char]
ys
                forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Read a => Int -> ReadS a
readsPrec Int
10
                forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \([(k, a)]
l,[Char]
rest) -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall (m :: * -> *) k a. AssocX m k => [(k, a)] -> m a
fromList [(k, a)]
l,[Char]
rest)

       -- play games with the typechecker so we don't have to use
       -- extensions for scoped type variables
       ~[(m a
x,[Char]
_)] = [(m a, [Char])]
result

   in [(m a, [Char])]
result

showsPrecUsingToOrdList :: (Show k,Show a,OrdAssoc m k) => Int -> m a -> ShowS
showsPrecUsingToOrdList :: forall k a (m :: * -> *).
(Show k, Show a, OrdAssoc m k) =>
Int -> m a -> ShowS
showsPrecUsingToOrdList Int
i m a
xs [Char]
rest
   | Int
i forall a. Eq a => a -> a -> Bool
== Int
0    = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [    forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
xs,[Char]
".unsafeFromOrdSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
xs) [Char]
rest]
   | Bool
otherwise = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Char]
"(",forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
xs,[Char]
".unsafeFromOrdSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
xs) (Char
')'forall a. a -> [a] -> [a]
:[Char]
rest)]

readsPrecUsingUnsafeFromOrdSeq :: (Read k,Read a,OrdAssoc m k) => Int -> ReadS (m a)
readsPrecUsingUnsafeFromOrdSeq :: forall k a (m :: * -> *).
(Read k, Read a, OrdAssoc m k) =>
Int -> ReadS (m a)
readsPrecUsingUnsafeFromOrdSeq Int
i [Char]
xs =
   let result :: [(m a, [Char])]
result = forall a. ReadS a -> ReadS a
maybeParens ReadS (m a)
p [Char]
xs
       p :: ReadS (m a)
p [Char]
ys = forall (m :: * -> *). MonadPlus m => [Char] -> [Char] -> m [Char]
tokenMatch ((forall (m :: * -> *) k a. AssocX m k => m a -> [Char]
instanceName m a
x)forall a. [a] -> [a] -> [a]
++[Char]
".unsafeFromOrdSeq") [Char]
ys
                forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Read a => Int -> ReadS a
readsPrec Int
i
                forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \([(k, a)]
l,[Char]
rest) -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall (m :: * -> *) k a. OrdAssocX m k => [(k, a)] -> m a
unsafeFromOrdList [(k, a)]
l,[Char]
rest)

       -- play games with the typechecker so we don't have to use
       -- extensions for scoped type variables
       ~[(m a
x,[Char]
_)] = [(m a, [Char])]
result

   in [(m a, [Char])]
result

compareUsingToOrdList :: (Ord a, OrdAssoc m k) => m a -> m a -> Ordering
compareUsingToOrdList :: forall a (m :: * -> *) k.
(Ord a, OrdAssoc m k) =>
m a -> m a -> Ordering
compareUsingToOrdList m a
xs m a
ys = forall {a}. Ord a => [a] -> [a] -> Ordering
cmp (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
xs) (forall (m :: * -> *) k a. OrdAssoc m k => m a -> [(k, a)]
toOrdList m a
ys)
 where
  cmp :: [a] -> [a] -> Ordering
cmp [] [] = Ordering
EQ
  cmp [] [a]
_  = Ordering
LT
  cmp [a]
_  [] = Ordering
GT
  cmp (a
v:[a]
vs) (a
z:[a]
zs) =
      case forall a. Ord a => a -> a -> Ordering
compare a
v a
z of
         Ordering
EQ -> [a] -> [a] -> Ordering
cmp [a]
vs [a]
zs
         Ordering
c -> Ordering
c