{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
module Distribution.Solver.Modular.PSQ
    ( PSQ(..)  -- Unit test needs constructor access
    , casePSQ
    , cons
    , length
    , lookup
    , filter
    , filterIfAny
    , filterIfAnyByKeys
    , filterKeys
    , firstOnly
    , fromList
    , isZeroOrOne
    , keys
    , map
    , mapKeys
    , mapWithKey
    , maximumBy
    , minimumBy
    , null
    , prefer
    , preferByKeys
    , snoc
    , sortBy
    , sortByKeys
    , toList
    , union
    ) where

-- Priority search queues.
--
-- I am not yet sure what exactly is needed. But we need a data structure with
-- key-based lookup that can be sorted. We're using a sequence right now with
-- (inefficiently implemented) lookup, because I think that queue-based
-- operations and sorting turn out to be more efficiency-critical in practice.

import Control.Arrow (first, second)

import qualified Data.Foldable as F
import Data.Function
import qualified Data.List as S
import Data.Ord (comparing)
import Data.Traversable
import Prelude hiding (foldr, length, lookup, filter, null, map)

newtype PSQ k v = PSQ [(k, v)]
  deriving (PSQ k v -> PSQ k v -> Bool
(PSQ k v -> PSQ k v -> Bool)
-> (PSQ k v -> PSQ k v -> Bool) -> Eq (PSQ k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => PSQ k v -> PSQ k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => PSQ k v -> PSQ k v -> Bool
== :: PSQ k v -> PSQ k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => PSQ k v -> PSQ k v -> Bool
/= :: PSQ k v -> PSQ k v -> Bool
Eq, Int -> PSQ k v -> ShowS
[PSQ k v] -> ShowS
PSQ k v -> String
(Int -> PSQ k v -> ShowS)
-> (PSQ k v -> String) -> ([PSQ k v] -> ShowS) -> Show (PSQ k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> PSQ k v -> ShowS
forall k v. (Show k, Show v) => [PSQ k v] -> ShowS
forall k v. (Show k, Show v) => PSQ k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> PSQ k v -> ShowS
showsPrec :: Int -> PSQ k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => PSQ k v -> String
show :: PSQ k v -> String
$cshowList :: forall k v. (Show k, Show v) => [PSQ k v] -> ShowS
showList :: [PSQ k v] -> ShowS
Show, (forall a b. (a -> b) -> PSQ k a -> PSQ k b)
-> (forall a b. a -> PSQ k b -> PSQ k a) -> Functor (PSQ k)
forall a b. a -> PSQ k b -> PSQ k a
forall a b. (a -> b) -> PSQ k a -> PSQ k b
forall k a b. a -> PSQ k b -> PSQ k a
forall k a b. (a -> b) -> PSQ k a -> PSQ k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k a b. (a -> b) -> PSQ k a -> PSQ k b
fmap :: forall a b. (a -> b) -> PSQ k a -> PSQ k b
$c<$ :: forall k a b. a -> PSQ k b -> PSQ k a
<$ :: forall a b. a -> PSQ k b -> PSQ k a
Functor, (forall m. Monoid m => PSQ k m -> m)
-> (forall m a. Monoid m => (a -> m) -> PSQ k a -> m)
-> (forall m a. Monoid m => (a -> m) -> PSQ k a -> m)
-> (forall a b. (a -> b -> b) -> b -> PSQ k a -> b)
-> (forall a b. (a -> b -> b) -> b -> PSQ k a -> b)
-> (forall b a. (b -> a -> b) -> b -> PSQ k a -> b)
-> (forall b a. (b -> a -> b) -> b -> PSQ k a -> b)
-> (forall a. (a -> a -> a) -> PSQ k a -> a)
-> (forall a. (a -> a -> a) -> PSQ k a -> a)
-> (forall a. PSQ k a -> [a])
-> (forall a. PSQ k a -> Bool)
-> (forall a. PSQ k a -> Int)
-> (forall a. Eq a => a -> PSQ k a -> Bool)
-> (forall a. Ord a => PSQ k a -> a)
-> (forall a. Ord a => PSQ k a -> a)
-> (forall a. Num a => PSQ k a -> a)
-> (forall a. Num a => PSQ k a -> a)
-> Foldable (PSQ k)
forall a. Eq a => a -> PSQ k a -> Bool
forall a. Num a => PSQ k a -> a
forall a. Ord a => PSQ k a -> a
forall m. Monoid m => PSQ k m -> m
forall a. PSQ k a -> Bool
forall a. PSQ k a -> Int
forall a. PSQ k a -> [a]
forall a. (a -> a -> a) -> PSQ k a -> a
forall k a. Eq a => a -> PSQ k a -> Bool
forall k a. Num a => PSQ k a -> a
forall k a. Ord a => PSQ k a -> a
forall m a. Monoid m => (a -> m) -> PSQ k a -> m
forall k m. Monoid m => PSQ k m -> m
forall k a. PSQ k a -> Bool
forall k a. PSQ k a -> Int
forall k a. PSQ k a -> [a]
forall b a. (b -> a -> b) -> b -> PSQ k a -> b
forall a b. (a -> b -> b) -> b -> PSQ k a -> b
forall k a. (a -> a -> a) -> PSQ k a -> a
forall k m a. Monoid m => (a -> m) -> PSQ k a -> m
forall k b a. (b -> a -> b) -> b -> PSQ k a -> b
forall k a b. (a -> b -> b) -> b -> PSQ k a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall k m. Monoid m => PSQ k m -> m
fold :: forall m. Monoid m => PSQ k m -> m
$cfoldMap :: forall k m a. Monoid m => (a -> m) -> PSQ k a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> PSQ k a -> m
$cfoldMap' :: forall k m a. Monoid m => (a -> m) -> PSQ k a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> PSQ k a -> m
$cfoldr :: forall k a b. (a -> b -> b) -> b -> PSQ k a -> b
foldr :: forall a b. (a -> b -> b) -> b -> PSQ k a -> b
$cfoldr' :: forall k a b. (a -> b -> b) -> b -> PSQ k a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> PSQ k a -> b
$cfoldl :: forall k b a. (b -> a -> b) -> b -> PSQ k a -> b
foldl :: forall b a. (b -> a -> b) -> b -> PSQ k a -> b
$cfoldl' :: forall k b a. (b -> a -> b) -> b -> PSQ k a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> PSQ k a -> b
$cfoldr1 :: forall k a. (a -> a -> a) -> PSQ k a -> a
foldr1 :: forall a. (a -> a -> a) -> PSQ k a -> a
$cfoldl1 :: forall k a. (a -> a -> a) -> PSQ k a -> a
foldl1 :: forall a. (a -> a -> a) -> PSQ k a -> a
$ctoList :: forall k a. PSQ k a -> [a]
toList :: forall a. PSQ k a -> [a]
$cnull :: forall k a. PSQ k a -> Bool
null :: forall a. PSQ k a -> Bool
$clength :: forall k a. PSQ k a -> Int
length :: forall a. PSQ k a -> Int
$celem :: forall k a. Eq a => a -> PSQ k a -> Bool
elem :: forall a. Eq a => a -> PSQ k a -> Bool
$cmaximum :: forall k a. Ord a => PSQ k a -> a
maximum :: forall a. Ord a => PSQ k a -> a
$cminimum :: forall k a. Ord a => PSQ k a -> a
minimum :: forall a. Ord a => PSQ k a -> a
$csum :: forall k a. Num a => PSQ k a -> a
sum :: forall a. Num a => PSQ k a -> a
$cproduct :: forall k a. Num a => PSQ k a -> a
product :: forall a. Num a => PSQ k a -> a
F.Foldable, Functor (PSQ k)
Foldable (PSQ k)
(Functor (PSQ k), Foldable (PSQ k)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> PSQ k a -> f (PSQ k b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    PSQ k (f a) -> f (PSQ k a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> PSQ k a -> m (PSQ k b))
-> (forall (m :: * -> *) a. Monad m => PSQ k (m a) -> m (PSQ k a))
-> Traversable (PSQ k)
forall k. Functor (PSQ k)
forall k. Foldable (PSQ k)
forall k (m :: * -> *) a. Monad m => PSQ k (m a) -> m (PSQ k a)
forall k (f :: * -> *) a.
Applicative f =>
PSQ k (f a) -> f (PSQ k a)
forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> PSQ k a -> m (PSQ k b)
forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PSQ k a -> f (PSQ k b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => PSQ k (m a) -> m (PSQ k a)
forall (f :: * -> *) a. Applicative f => PSQ k (f a) -> f (PSQ k a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> PSQ k a -> m (PSQ k b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PSQ k a -> f (PSQ k b)
$ctraverse :: forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PSQ k a -> f (PSQ k b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> PSQ k a -> f (PSQ k b)
$csequenceA :: forall k (f :: * -> *) a.
Applicative f =>
PSQ k (f a) -> f (PSQ k a)
sequenceA :: forall (f :: * -> *) a. Applicative f => PSQ k (f a) -> f (PSQ k a)
$cmapM :: forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> PSQ k a -> m (PSQ k b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> PSQ k a -> m (PSQ k b)
$csequence :: forall k (m :: * -> *) a. Monad m => PSQ k (m a) -> m (PSQ k a)
sequence :: forall (m :: * -> *) a. Monad m => PSQ k (m a) -> m (PSQ k a)
Traversable) -- Qualified Foldable to avoid issues with FTP

keys :: PSQ k v -> [k]
keys :: forall k v. PSQ k v -> [k]
keys (PSQ [(k, v)]
xs) = ((k, v) -> k) -> [(k, v)] -> [k]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, v) -> k
forall a b. (a, b) -> a
fst [(k, v)]
xs

lookup :: Eq k => k -> PSQ k v -> Maybe v
lookup :: forall k v. Eq k => k -> PSQ k v -> Maybe v
lookup k
k (PSQ [(k, v)]
xs) = k -> [(k, v)] -> Maybe v
forall a b. Eq a => a -> [(a, b)] -> Maybe b
S.lookup k
k [(k, v)]
xs

map :: (v1 -> v2) -> PSQ k v1 -> PSQ k v2
map :: forall v1 v2 k. (v1 -> v2) -> PSQ k v1 -> PSQ k v2
map v1 -> v2
f (PSQ [(k, v1)]
xs) = [(k, v2)] -> PSQ k v2
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, v1) -> (k, v2)) -> [(k, v1)] -> [(k, v2)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((v1 -> v2) -> (k, v1) -> (k, v2)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second v1 -> v2
f) [(k, v1)]
xs)

mapKeys :: (k1 -> k2) -> PSQ k1 v -> PSQ k2 v
mapKeys :: forall k1 k2 v. (k1 -> k2) -> PSQ k1 v -> PSQ k2 v
mapKeys k1 -> k2
f (PSQ [(k1, v)]
xs) = [(k2, v)] -> PSQ k2 v
forall k v. [(k, v)] -> PSQ k v
PSQ (((k1, v) -> (k2, v)) -> [(k1, v)] -> [(k2, v)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((k1 -> k2) -> (k1, v) -> (k2, v)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k1 -> k2
f) [(k1, v)]
xs)

mapWithKey :: (k -> a -> b) -> PSQ k a -> PSQ k b
mapWithKey :: forall k a b. (k -> a -> b) -> PSQ k a -> PSQ k b
mapWithKey k -> a -> b
f (PSQ [(k, a)]
xs) = [(k, b)] -> PSQ k b
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, a) -> (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\ (k
k, a
v) -> (k
k, k -> a -> b
f k
k a
v)) [(k, a)]
xs)

fromList :: [(k, a)] -> PSQ k a
fromList :: forall k v. [(k, v)] -> PSQ k v
fromList = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ

cons :: k -> a -> PSQ k a -> PSQ k a
cons :: forall k a. k -> a -> PSQ k a -> PSQ k a
cons k
k a
x (PSQ [(k, a)]
xs) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ ((k
k, a
x) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
xs)

snoc :: PSQ k a -> k -> a -> PSQ k a
snoc :: forall k a. PSQ k a -> k -> a -> PSQ k a
snoc (PSQ [(k, a)]
xs) k
k a
x = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ ([(k, a)]
xs [(k, a)] -> [(k, a)] -> [(k, a)]
forall a. [a] -> [a] -> [a]
++ [(k
k, a
x)])

casePSQ :: PSQ k a -> r -> (k -> a -> PSQ k a -> r) -> r
casePSQ :: forall k a r. PSQ k a -> r -> (k -> a -> PSQ k a -> r) -> r
casePSQ (PSQ [(k, a)]
xs) r
n k -> a -> PSQ k a -> r
c =
  case [(k, a)]
xs of
    []          -> r
n
    (k
k, a
v) : [(k, a)]
ys -> k -> a -> PSQ k a -> r
c k
k a
v ([(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)]
ys)

sortBy :: (a -> a -> Ordering) -> PSQ k a -> PSQ k a
sortBy :: forall a k. (a -> a -> Ordering) -> PSQ k a -> PSQ k a
sortBy a -> a -> Ordering
cmp (PSQ [(k, a)]
xs) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, a) -> (k, a) -> Ordering) -> [(k, a)] -> [(k, a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
S.sortBy (a -> a -> Ordering
cmp (a -> a -> Ordering)
-> ((k, a) -> a) -> (k, a) -> (k, a) -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (k, a) -> a
forall a b. (a, b) -> b
snd) [(k, a)]
xs)

sortByKeys :: (k -> k -> Ordering) -> PSQ k a -> PSQ k a
sortByKeys :: forall k a. (k -> k -> Ordering) -> PSQ k a -> PSQ k a
sortByKeys k -> k -> Ordering
cmp (PSQ [(k, a)]
xs) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, a) -> (k, a) -> Ordering) -> [(k, a)] -> [(k, a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
S.sortBy (k -> k -> Ordering
cmp (k -> k -> Ordering)
-> ((k, a) -> k) -> (k, a) -> (k, a) -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
xs)

maximumBy :: (k -> Int) -> PSQ k a -> (k, a)
maximumBy :: forall k a. (k -> Int) -> PSQ k a -> (k, a)
maximumBy k -> Int
sel (PSQ [(k, a)]
xs) =
  ((k, a) -> (k, a) -> Ordering) -> [(k, a)] -> (k, a)
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
S.minimumBy (((k, a) -> (k, a) -> Ordering) -> (k, a) -> (k, a) -> Ordering
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((k, a) -> Int) -> (k, a) -> (k, a) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (k -> Int
sel (k -> Int) -> ((k, a) -> k) -> (k, a) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst))) [(k, a)]
xs

minimumBy :: (a -> Int) -> PSQ k a -> PSQ k a
minimumBy :: forall a k. (a -> Int) -> PSQ k a -> PSQ k a
minimumBy a -> Int
sel (PSQ [(k, a)]
xs) =
  [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(Int, (k, a)) -> (k, a)
forall a b. (a, b) -> b
snd (((Int, (k, a)) -> (Int, (k, a)) -> Ordering)
-> [(Int, (k, a))] -> (Int, (k, a))
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
S.minimumBy (((Int, (k, a)) -> Int)
-> (Int, (k, a)) -> (Int, (k, a)) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (Int, (k, a)) -> Int
forall a b. (a, b) -> a
fst) (((k, a) -> (Int, (k, a))) -> [(k, a)] -> [(Int, (k, a))]
forall a b. (a -> b) -> [a] -> [b]
S.map (\ (k, a)
x -> (a -> Int
sel ((k, a) -> a
forall a b. (a, b) -> b
snd (k, a)
x), (k, a)
x)) [(k, a)]
xs))]

-- | Sort the list so that values satisfying the predicate are first.
prefer :: (a -> Bool) -> PSQ k a -> PSQ k a
prefer :: forall a k. (a -> Bool) -> PSQ k a -> PSQ k a
prefer a -> Bool
p = (a -> a -> Ordering) -> PSQ k a -> PSQ k a
forall a k. (a -> a -> Ordering) -> PSQ k a -> PSQ k a
sortBy ((a -> a -> Ordering) -> PSQ k a -> PSQ k a)
-> (a -> a -> Ordering) -> PSQ k a -> PSQ k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> Ordering) -> a -> a -> Ordering
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> Bool) -> a -> a -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing a -> Bool
p)

-- | Sort the list so that keys satisfying the predicate are first.
preferByKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
preferByKeys :: forall k a. (k -> Bool) -> PSQ k a -> PSQ k a
preferByKeys k -> Bool
p = (k -> k -> Ordering) -> PSQ k a -> PSQ k a
forall k a. (k -> k -> Ordering) -> PSQ k a -> PSQ k a
sortByKeys ((k -> k -> Ordering) -> PSQ k a -> PSQ k a)
-> (k -> k -> Ordering) -> PSQ k a -> PSQ k a
forall a b. (a -> b) -> a -> b
$ (k -> k -> Ordering) -> k -> k -> Ordering
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((k -> Bool) -> k -> k -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing k -> Bool
p)

-- | Will partition the list according to the predicate. If
-- there is any element that satisfies the predicate, then only
-- the elements satisfying the predicate are returned.
-- Otherwise, the rest is returned.
--
filterIfAny :: (a -> Bool) -> PSQ k a -> PSQ k a
filterIfAny :: forall a k. (a -> Bool) -> PSQ k a -> PSQ k a
filterIfAny a -> Bool
p (PSQ [(k, a)]
xs) =
  let
    ([(k, a)]
pro, [(k, a)]
con) = ((k, a) -> Bool) -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
S.partition (a -> Bool
p (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) [(k, a)]
xs
  in
    if [(k, a)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
S.null [(k, a)]
pro then [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)]
con else [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)]
pro

-- | Variant of 'filterIfAny' that takes a predicate on the keys
-- rather than on the values.
--
filterIfAnyByKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
filterIfAnyByKeys :: forall k a. (k -> Bool) -> PSQ k a -> PSQ k a
filterIfAnyByKeys k -> Bool
p (PSQ [(k, a)]
xs) =
  let
    ([(k, a)]
pro, [(k, a)]
con) = ((k, a) -> Bool) -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
S.partition (k -> Bool
p (k -> Bool) -> ((k, a) -> k) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
xs
  in
    if [(k, a)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
S.null [(k, a)]
pro then [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)]
con else [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)]
pro

filterKeys :: (k -> Bool) -> PSQ k a -> PSQ k a
filterKeys :: forall k a. (k -> Bool) -> PSQ k a -> PSQ k a
filterKeys k -> Bool
p (PSQ [(k, a)]
xs) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, a) -> Bool) -> [(k, a)] -> [(k, a)]
forall a. (a -> Bool) -> [a] -> [a]
S.filter (k -> Bool
p (k -> Bool) -> ((k, a) -> k) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
xs)

filter :: (a -> Bool) -> PSQ k a -> PSQ k a
filter :: forall a k. (a -> Bool) -> PSQ k a -> PSQ k a
filter a -> Bool
p (PSQ [(k, a)]
xs) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ (((k, a) -> Bool) -> [(k, a)] -> [(k, a)]
forall a. (a -> Bool) -> [a] -> [a]
S.filter (a -> Bool
p (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) [(k, a)]
xs)

length :: PSQ k a -> Int
length :: forall k a. PSQ k a -> Int
length (PSQ [(k, a)]
xs) = [(k, a)] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
S.length [(k, a)]
xs

null :: PSQ k a -> Bool
null :: forall k a. PSQ k a -> Bool
null (PSQ [(k, a)]
xs) = [(k, a)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
S.null [(k, a)]
xs

isZeroOrOne :: PSQ k a -> Bool
isZeroOrOne :: forall k a. PSQ k a -> Bool
isZeroOrOne (PSQ [])  = Bool
True
isZeroOrOne (PSQ [(k, a)
_]) = Bool
True
isZeroOrOne PSQ k a
_         = Bool
False

firstOnly :: PSQ k a -> PSQ k a
firstOnly :: forall k a. PSQ k a -> PSQ k a
firstOnly (PSQ [])      = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ []
firstOnly (PSQ ((k, a)
x : [(k, a)]
_)) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ [(k, a)
x]

toList :: PSQ k a -> [(k, a)]
toList :: forall k a. PSQ k a -> [(k, a)]
toList (PSQ [(k, a)]
xs) = [(k, a)]
xs

union :: PSQ k a -> PSQ k a -> PSQ k a
union :: forall k a. PSQ k a -> PSQ k a -> PSQ k a
union (PSQ [(k, a)]
xs) (PSQ [(k, a)]
ys) = [(k, a)] -> PSQ k a
forall k v. [(k, v)] -> PSQ k v
PSQ ([(k, a)]
xs [(k, a)] -> [(k, a)] -> [(k, a)]
forall a. [a] -> [a] -> [a]
++ [(k, a)]
ys)