-- |
--   Module      :  Data.Edison.Coll.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 collection methods.  The functions
--   in this module are used to fill out collection implementations and are not intended to be
--   used directly by end users.

module Data.Edison.Coll.Defaults where

import Prelude hiding (null,foldr,foldl,foldr1,foldl1,foldl',lookup,filter)
import qualified Control.Monad.Fail as Fail

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

insertSeqUsingUnion :: (CollX c a,S.Sequence seq) => seq a -> c -> c
insertSeqUsingUnion :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingUnion seq a
xs c
c = c -> c -> c
forall c a. CollX c a => c -> c -> c
union (seq a -> c
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
forall (seq :: * -> *). Sequence seq => seq a -> c
fromSeq seq a
xs) c
c

insertSeqUsingFoldr :: (CollX c a,S.Sequence seq) => seq a -> c -> c
insertSeqUsingFoldr :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingFoldr seq a
xs c
c = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr a -> c -> c
forall c a. CollX c a => a -> c -> c
insert c
c seq a
xs

memberUsingFold :: Coll c a => c -> a -> Bool
memberUsingFold :: forall c a. Coll c a => c -> a -> Bool
memberUsingFold c
h a
x = (a -> Bool -> Bool) -> Bool -> c -> Bool
forall b. (a -> b -> b) -> b -> c -> b
forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
fold (\a
y Bool
ans -> (a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y) Bool -> Bool -> Bool
|| Bool
ans) Bool
False c
h

countUsingMember :: SetX c a => a -> c -> Int
countUsingMember :: forall c a. SetX c a => a -> c -> Int
countUsingMember a
x c
xs = if a -> c -> Bool
forall c a. CollX c a => a -> c -> Bool
member a
x c
xs then Int
1 else Int
0

lookupAllUsingLookupM :: (Set c a,S.Sequence seq) => a -> c -> seq a
lookupAllUsingLookupM :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
a -> c -> seq a
lookupAllUsingLookupM a
x c
xs =
  case a -> c -> Maybe a
forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
forall (m :: * -> *). MonadFail m => a -> c -> m a
lookupM a
x c
xs of
    Maybe a
Nothing -> seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty
    Just a
y  -> a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
y

deleteSeqUsingDelete :: (CollX c a,S.Sequence seq) => seq a -> c -> c
deleteSeqUsingDelete :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete seq a
xs c
c = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr a -> c -> c
forall c a. CollX c a => a -> c -> c
delete c
c seq a
xs

unionSeqUsingFoldl :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingFoldl :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingFoldl = (c -> c -> c) -> c -> seq c -> c
forall b a. (b -> a -> b) -> b -> seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl c -> c -> c
forall c a. CollX c a => c -> c -> c
union c
forall c a. CollX c a => c
empty

unionSeqUsingFoldl' :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingFoldl' :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingFoldl' = (c -> c -> c) -> c -> seq c -> c
forall b a. (b -> a -> b) -> b -> seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl' c -> c -> c
forall c a. CollX c a => c -> c -> c
union c
forall c a. CollX c a => c
empty

unionSeqUsingReduce :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingReduce :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingReduce = (c -> c -> c) -> c -> seq c -> c
forall a. (a -> a -> a) -> a -> seq a -> a
forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducel c -> c -> c
forall c a. CollX c a => c -> c -> c
union c
forall c a. CollX c a => c
empty

fromSeqUsingFoldr :: (CollX c a,S.Sequence seq) => seq a -> c
fromSeqUsingFoldr :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingFoldr = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr a -> c -> c
forall c a. CollX c a => a -> c -> c
insert c
forall c a. CollX c a => c
empty

fromSeqUsingUnionSeq :: (CollX c a,S.Sequence seq) => seq a -> c
fromSeqUsingUnionSeq :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingUnionSeq = [c] -> c
forall c a. CollX c a => [c] -> c
unionList ([c] -> c) -> (seq a -> [c]) -> seq a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([c] -> a -> [c]) -> [c] -> seq a -> [c]
forall b a. (b -> a -> b) -> b -> seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl [c] -> a -> [c]
forall {s :: * -> *} {a} {a}.
(Sequence s, CollX a a) =>
s a -> a -> s a
singleCons []
  where singleCons :: s a -> a -> s a
singleCons s a
xs a
x = a -> s a -> s a
forall a. a -> s a -> s a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons (a -> a
forall c a. CollX c a => a -> c
singleton a
x) s a
xs

toSeqUsingFold :: (Coll c a,S.Sequence seq) => c -> seq a
toSeqUsingFold :: forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
toSeqUsingFold = (a -> seq a -> seq a) -> seq a -> c -> seq a
forall b. (a -> b -> b) -> b -> c -> b
forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
fold a -> seq a -> seq a
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty

unsafeInsertMaxUsingUnsafeAppend :: OrdCollX c a => a -> c -> c
unsafeInsertMaxUsingUnsafeAppend :: forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMaxUsingUnsafeAppend a
x c
c = c -> c -> c
forall c a. OrdCollX c a => c -> c -> c
unsafeAppend c
c (a -> c
forall c a. CollX c a => a -> c
singleton a
x)

toOrdSeqUsingFoldr :: (OrdColl c a,S.Sequence seq) => c -> seq a
toOrdSeqUsingFoldr :: forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
toOrdSeqUsingFoldr = (a -> seq a -> seq a) -> seq a -> c -> seq a
forall b. (a -> b -> b) -> b -> c -> b
forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
foldr a -> seq a -> seq a
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty

unsafeFromOrdSeqUsingUnsafeInsertMin ::
    (OrdCollX c a,S.Sequence seq) => seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin :: forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr a -> c -> c
forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMin c
forall c a. CollX c a => c
empty

disjointUsingToOrdList :: OrdColl c a => c -> c -> Bool
disjointUsingToOrdList :: forall c a. OrdColl c a => c -> c -> Bool
disjointUsingToOrdList c
xs c
ys = [a] -> [a] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
disj (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)
  where disj :: [a] -> [a] -> Bool
disj a :: [a]
a@(a
c:[a]
cs) b :: [a]
b@(a
d:[a]
ds) =
          case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
c a
d of
            Ordering
LT -> [a] -> [a] -> Bool
disj [a]
cs [a]
b
            Ordering
EQ -> Bool
False
            Ordering
GT -> [a] -> [a] -> Bool
disj [a]
a [a]
ds
        disj [a]
_ [a]
_ = Bool
True

intersectWitnessUsingToOrdList ::
        (OrdColl c a, Fail.MonadFail m) => c -> c -> m (a,a)
intersectWitnessUsingToOrdList :: forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> c -> m (a, a)
intersectWitnessUsingToOrdList c
as c
bs = [a] -> [a] -> m (a, a)
forall {b} {m :: * -> *}.
(Ord b, MonadFail m) =>
[b] -> [b] -> m (b, b)
witness (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where witness :: [b] -> [b] -> m (b, b)
witness a :: [b]
a@(b
x:[b]
xs) b :: [b]
b@(b
y:[b]
ys) =
          case b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare b
x b
y of
            Ordering
LT -> [b] -> [b] -> m (b, b)
witness [b]
xs [b]
b
            Ordering
EQ -> (b, b) -> m (b, b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (b
x, b
y)
            Ordering
GT -> [b] -> [b] -> m (b, b)
witness [b]
a [b]
ys
        -- XXX
        witness [b]
_ [b]
_ = String -> m (b, b)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (b, b)) -> String -> m (b, b)
forall a b. (a -> b) -> a -> b
$ c -> String
forall c a. CollX c a => c -> String
instanceName c
as String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
".intersect: failed"

lookupUsingLookupM :: Coll c a => a -> c -> a
lookupUsingLookupM :: forall c a. Coll c a => a -> c -> a
lookupUsingLookupM a
x c
ys = Fail a -> a
forall a. Fail a -> a
runFail_ (a -> c -> Fail a
forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
forall (m :: * -> *). MonadFail m => a -> c -> m a
lookupM a
x c
ys)

lookupUsingLookupAll :: Coll c a => a -> c -> a
lookupUsingLookupAll :: forall c a. Coll c a => a -> c -> a
lookupUsingLookupAll a
x c
ys =
  case a -> c -> [a]
forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
forall (seq :: * -> *). Sequence seq => a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> a
y
    [] -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ c -> String
forall c a. CollX c a => c -> String
instanceName c
ys String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
".lookup: lookup failed"

lookupMUsingLookupAll :: (Coll c a, Fail.MonadFail m) => a -> c -> m a
lookupMUsingLookupAll :: forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupMUsingLookupAll a
x c
ys =
  case a -> c -> [a]
forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
forall (seq :: * -> *). Sequence seq => a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
y
    []    -> String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m a) -> String -> m a
forall a b. (a -> b) -> a -> b
$ c -> String
forall c a. CollX c a => c -> String
instanceName c
ys String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
".lookupM: lookup failed"

lookupWithDefaultUsingLookupAll :: Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll :: forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll a
dflt a
x c
ys =
  case a -> c -> [a]
forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
forall (seq :: * -> *). Sequence seq => a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> a
y
    [] -> a
dflt

lookupWithDefaultUsingLookupM :: Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupM :: forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupM a
dflt a
x c
ys =
  case a -> c -> Maybe a
forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
forall (m :: * -> *). MonadFail m => a -> c -> m a
lookupM a
x c
ys of
    Just a
y  -> a
y
    Maybe a
Nothing -> a
dflt

deleteMaxUsingMaxView :: OrdColl c a => c -> c
deleteMaxUsingMaxView :: forall c a. OrdColl c a => c -> c
deleteMaxUsingMaxView c
c =
  case c -> Maybe (a, c)
forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
forall (m :: * -> *). MonadFail m => c -> m (a, c)
maxView c
c of
    Just (a
_,c
c') -> c
c'
    Maybe (a, c)
Nothing     -> c
c

fromSeqWithUsingInsertWith :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith a -> a -> a
c = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr ((a -> a -> a) -> a -> c -> c
forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith a -> a -> a
c) c
forall c a. CollX c a => c
empty

insertUsingInsertWith :: Set c a => a -> c -> c
insertUsingInsertWith :: forall c a. Set c a => a -> c -> c
insertUsingInsertWith = (a -> a -> a) -> a -> c -> c
forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith (\a
x a
_ -> a
x)

unionUsingUnionWith :: Set c a => c -> c -> c
unionUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionUsingUnionWith = (a -> a -> a) -> c -> c -> c
forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
x a
_ -> a
x)

filterUsingOrdLists :: OrdColl c a => (a -> Bool) -> c -> c
filterUsingOrdLists :: forall c a. OrdColl c a => (a -> Bool) -> c -> c
filterUsingOrdLists a -> Bool
p = [a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList ([a] -> c) -> (c -> [a]) -> c -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter a -> Bool
p ([a] -> [a]) -> (c -> [a]) -> c -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList

partitionUsingOrdLists :: OrdColl c a => (a -> Bool) -> c -> (c,c)
partitionUsingOrdLists :: forall c a. OrdColl c a => (a -> Bool) -> c -> (c, c)
partitionUsingOrdLists a -> Bool
p c
xs = ([a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList [a]
ys,[a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList [a]
zs)
  where ([a]
ys,[a]
zs) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
L.partition a -> Bool
p (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
xs)

intersectionUsingIntersectionWith :: Set c a => c -> c -> c
intersectionUsingIntersectionWith :: forall c a. Set c a => c -> c -> c
intersectionUsingIntersectionWith = (a -> a -> a) -> c -> c -> c
forall c a. Set c a => (a -> a -> a) -> c -> c -> c
intersectionWith (\a
x a
_ -> a
x)

differenceUsingOrdLists :: OrdSet c a => c -> c -> c
differenceUsingOrdLists :: forall c a. OrdSet c a => c -> c -> c
differenceUsingOrdLists c
as c
bs = [a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList ([a] -> c) -> [a] -> c
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [a]
forall {a}. Ord a => [a] -> [a] -> [a]
diff (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where diff :: [a] -> [a] -> [a]
diff a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
diff [a]
xs [a]
b
            Ordering
EQ -> [a] -> [a] -> [a]
diff [a]
xs [a]
ys
            Ordering
GT -> [a] -> [a] -> [a]
diff [a]
a [a]
ys
        diff [a]
a [a]
_ = [a]
a

symmetricDifferenceUsingDifference :: SetX c a => c -> c -> c
symmetricDifferenceUsingDifference :: forall c a. SetX c a => c -> c -> c
symmetricDifferenceUsingDifference c
xs c
ys = c -> c -> c
forall c a. CollX c a => c -> c -> c
union (c -> c -> c
forall c a. SetX c a => c -> c -> c
difference c
xs c
ys) (c -> c -> c
forall c a. SetX c a => c -> c -> c
difference c
ys c
xs)

properSubsetUsingOrdLists :: OrdSet c a => c -> c -> Bool
properSubsetUsingOrdLists :: forall c a. OrdSet c a => c -> c -> Bool
properSubsetUsingOrdLists c
xs c
ys = [a] -> [a] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)

subsetUsingOrdLists :: OrdSet c a => c -> c -> Bool
subsetUsingOrdLists :: forall c a. OrdSet c a => c -> c -> Bool
subsetUsingOrdLists c
xs c
ys = [a] -> [a] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)

properSubsetOnOrdLists :: (Ord t) => [t] -> [t] -> Bool
properSubsetOnOrdLists :: forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists [] [] = Bool
False
properSubsetOnOrdLists [] (t
_:[t]
_) = Bool
True
properSubsetOnOrdLists (t
_:[t]
_) [] = Bool
False
properSubsetOnOrdLists a :: [t]
a@(t
x:[t]
xs) (t
y:[t]
ys) =
  case t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
x t
y of
    Ordering
LT -> Bool
False
    Ordering
EQ -> [t] -> [t] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists [t]
xs [t]
ys
    Ordering
GT -> [t] -> [t] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
a [t]
ys

subsetOnOrdLists :: (Ord t) => [t] -> [t] -> Bool
subsetOnOrdLists :: forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [] [t]
_ = Bool
True
subsetOnOrdLists (t
_:[t]
_) [] = Bool
False
subsetOnOrdLists a :: [t]
a@(t
x:[t]
xs) (t
y:[t]
ys) =
  case t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
x t
y of
    Ordering
LT -> Bool
False
    Ordering
EQ -> [t] -> [t] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
xs [t]
ys
    Ordering
GT -> [t] -> [t] -> Bool
forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
a [t]
ys

insertSeqWithUsingInsertWith :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith a -> a -> a
c seq a
xs c
s = (a -> c -> c) -> c -> seq a -> c
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr ((a -> a -> a) -> a -> c -> c
forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith a -> a -> a
c) c
s seq a
xs

unionlUsingUnionWith :: Set c a => c -> c -> c
unionlUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionlUsingUnionWith c
xs c
ys = (a -> a -> a) -> c -> c -> c
forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
x a
_ -> a
x) c
xs c
ys

unionrUsingUnionWith :: Set c a => c -> c -> c
unionrUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionrUsingUnionWith c
xs c
ys = (a -> a -> a) -> c -> c -> c
forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
_ a
y -> a
y) c
xs c
ys

unionWithUsingOrdLists :: OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists :: forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists a -> a -> a
c c
as c
bs = [a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList ([a] -> c) -> [a] -> c
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [a]
merge (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where merge :: [a] -> [a] -> [a]
merge a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
xs [a]
b
            Ordering
EQ -> a -> a -> a
c a
x a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
xs [a]
ys
            Ordering
GT -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
a [a]
ys
        merge [a]
a [] = [a]
a
        merge [] [a]
b = [a]
b

unionSeqWithUsingReducer :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer a -> a -> a
c = (c -> c -> c) -> c -> seq c -> c
forall a. (a -> a -> a) -> a -> seq a -> a
forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducer ((a -> a -> a) -> c -> c -> c
forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith a -> a -> a
c) c
forall c a. CollX c a => c
empty

intersectionWithUsingOrdLists :: OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists :: forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists a -> a -> a
c c
as c
bs = [a] -> c
forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList ([a] -> c) -> [a] -> c
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [a]
inter (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where inter :: [a] -> [a] -> [a]
inter a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> [a] -> [a] -> [a]
inter [a]
xs [a]
b
            Ordering
EQ -> a -> a -> a
c a
x a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
inter [a]
xs [a]
ys
            Ordering
GT -> [a] -> [a] -> [a]
inter [a]
a [a]
ys
        inter [a]
_ [a]
_ = []


unsafeMapMonotonicUsingFoldr :: (OrdColl cin a, OrdCollX cout b) => (a -> b) -> (cin -> cout)
unsafeMapMonotonicUsingFoldr :: forall cin a cout b.
(OrdColl cin a, OrdCollX cout b) =>
(a -> b) -> cin -> cout
unsafeMapMonotonicUsingFoldr a -> b
f cin
xs = (a -> cout -> cout) -> cout -> cin -> cout
forall b. (a -> b -> b) -> b -> cin -> b
forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
foldr (b -> cout -> cout
forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMin (b -> cout -> cout) -> (a -> b) -> a -> cout -> cout
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) cout
forall c a. CollX c a => c
empty cin
xs

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

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

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

    in [(c, String)]
result

compareUsingToOrdList :: OrdColl c a => c -> c -> Ordering
compareUsingToOrdList :: forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList c
as c
bs = [a] -> [a] -> Ordering
forall {a}. Ord a => [a] -> [a] -> Ordering
cmp (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (c -> [a]
forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
 where
  cmp :: [a] -> [a] -> Ordering
cmp [] [] = Ordering
EQ
  cmp [] [a]
_  = Ordering
LT
  cmp [a]
_  [] = Ordering
GT
  cmp (a
x:[a]
xs) (a
y:[a]
ys) =
      case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
         Ordering
EQ -> [a] -> [a] -> Ordering
cmp [a]
xs [a]
ys
         Ordering
c -> Ordering
c