    {-# 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 k m. Monoid m => PSQ k m -> m
    forall m a. Monoid m => (a -> m) -> PSQ k a -> 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)