{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
module Distribution.Solver.Modular.WeightedPSQ (
    WeightedPSQ
  , fromList
  , toList
  , keys
  , weights
  , isZeroOrOne
  , filter
  , lookup
  , mapWithKey
  , mapWeightsWithKey
  , traverseWithKey
  , union
  , takeUntil
  ) where

import qualified Data.Foldable as F
import qualified Data.List as L
import Data.Ord (comparing)
import qualified Data.Traversable as T
import Prelude hiding (filter, lookup)

-- | An association list that is sorted by weight.
--
-- Each element has a key ('k'), value ('v'), and weight ('w'). All operations
-- that add elements or modify weights stably sort the elements by weight.
newtype WeightedPSQ w k v = WeightedPSQ [(w, k, v)]
  deriving (WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
(WeightedPSQ w k v -> WeightedPSQ w k v -> Bool)
-> (WeightedPSQ w k v -> WeightedPSQ w k v -> Bool)
-> Eq (WeightedPSQ w k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall w k v.
(Eq w, Eq k, Eq v) =>
WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
$c== :: forall w k v.
(Eq w, Eq k, Eq v) =>
WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
== :: WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
$c/= :: forall w k v.
(Eq w, Eq k, Eq v) =>
WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
/= :: WeightedPSQ w k v -> WeightedPSQ w k v -> Bool
Eq, Int -> WeightedPSQ w k v -> ShowS
[WeightedPSQ w k v] -> ShowS
WeightedPSQ w k v -> String
(Int -> WeightedPSQ w k v -> ShowS)
-> (WeightedPSQ w k v -> String)
-> ([WeightedPSQ w k v] -> ShowS)
-> Show (WeightedPSQ w k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall w k v.
(Show w, Show k, Show v) =>
Int -> WeightedPSQ w k v -> ShowS
forall w k v.
(Show w, Show k, Show v) =>
[WeightedPSQ w k v] -> ShowS
forall w k v.
(Show w, Show k, Show v) =>
WeightedPSQ w k v -> String
$cshowsPrec :: forall w k v.
(Show w, Show k, Show v) =>
Int -> WeightedPSQ w k v -> ShowS
showsPrec :: Int -> WeightedPSQ w k v -> ShowS
$cshow :: forall w k v.
(Show w, Show k, Show v) =>
WeightedPSQ w k v -> String
show :: WeightedPSQ w k v -> String
$cshowList :: forall w k v.
(Show w, Show k, Show v) =>
[WeightedPSQ w k v] -> ShowS
showList :: [WeightedPSQ w k v] -> ShowS
Show, (forall a b. (a -> b) -> WeightedPSQ w k a -> WeightedPSQ w k b)
-> (forall a b. a -> WeightedPSQ w k b -> WeightedPSQ w k a)
-> Functor (WeightedPSQ w k)
forall a b. a -> WeightedPSQ w k b -> WeightedPSQ w k a
forall a b. (a -> b) -> WeightedPSQ w k a -> WeightedPSQ w k b
forall w k a b. a -> WeightedPSQ w k b -> WeightedPSQ w k a
forall w k a b. (a -> b) -> WeightedPSQ w k a -> WeightedPSQ w 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 w k a b. (a -> b) -> WeightedPSQ w k a -> WeightedPSQ w k b
fmap :: forall a b. (a -> b) -> WeightedPSQ w k a -> WeightedPSQ w k b
$c<$ :: forall w k a b. a -> WeightedPSQ w k b -> WeightedPSQ w k a
<$ :: forall a b. a -> WeightedPSQ w k b -> WeightedPSQ w k a
Functor, (forall m. Monoid m => WeightedPSQ w k m -> m)
-> (forall m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m)
-> (forall m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m)
-> (forall a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b)
-> (forall a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b)
-> (forall b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b)
-> (forall b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b)
-> (forall a. (a -> a -> a) -> WeightedPSQ w k a -> a)
-> (forall a. (a -> a -> a) -> WeightedPSQ w k a -> a)
-> (forall a. WeightedPSQ w k a -> [a])
-> (forall a. WeightedPSQ w k a -> Bool)
-> (forall a. WeightedPSQ w k a -> Int)
-> (forall a. Eq a => a -> WeightedPSQ w k a -> Bool)
-> (forall a. Ord a => WeightedPSQ w k a -> a)
-> (forall a. Ord a => WeightedPSQ w k a -> a)
-> (forall a. Num a => WeightedPSQ w k a -> a)
-> (forall a. Num a => WeightedPSQ w k a -> a)
-> Foldable (WeightedPSQ w k)
forall a. Eq a => a -> WeightedPSQ w k a -> Bool
forall a. Num a => WeightedPSQ w k a -> a
forall a. Ord a => WeightedPSQ w k a -> a
forall m. Monoid m => WeightedPSQ w k m -> m
forall a. WeightedPSQ w k a -> Bool
forall a. WeightedPSQ w k a -> Int
forall a. WeightedPSQ w k a -> [a]
forall a. (a -> a -> a) -> WeightedPSQ w k a -> a
forall m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
forall b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
forall a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b
forall w k a. Eq a => a -> WeightedPSQ w k a -> Bool
forall w k a. Num a => WeightedPSQ w k a -> a
forall w k a. Ord a => WeightedPSQ w k a -> a
forall w k m. Monoid m => WeightedPSQ w k m -> m
forall w k a. WeightedPSQ w k a -> Bool
forall w k a. WeightedPSQ w k a -> Int
forall w k a. WeightedPSQ w k a -> [a]
forall w k a. (a -> a -> a) -> WeightedPSQ w k a -> a
forall w k m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
forall w k b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
forall w k a b. (a -> b -> b) -> b -> WeightedPSQ w 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 w k m. Monoid m => WeightedPSQ w k m -> m
fold :: forall m. Monoid m => WeightedPSQ w k m -> m
$cfoldMap :: forall w k m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
$cfoldMap' :: forall w k m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> WeightedPSQ w k a -> m
$cfoldr :: forall w k a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b
foldr :: forall a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b
$cfoldr' :: forall w k a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> WeightedPSQ w k a -> b
$cfoldl :: forall w k b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
foldl :: forall b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
$cfoldl' :: forall w k b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> WeightedPSQ w k a -> b
$cfoldr1 :: forall w k a. (a -> a -> a) -> WeightedPSQ w k a -> a
foldr1 :: forall a. (a -> a -> a) -> WeightedPSQ w k a -> a
$cfoldl1 :: forall w k a. (a -> a -> a) -> WeightedPSQ w k a -> a
foldl1 :: forall a. (a -> a -> a) -> WeightedPSQ w k a -> a
$ctoList :: forall w k a. WeightedPSQ w k a -> [a]
toList :: forall a. WeightedPSQ w k a -> [a]
$cnull :: forall w k a. WeightedPSQ w k a -> Bool
null :: forall a. WeightedPSQ w k a -> Bool
$clength :: forall w k a. WeightedPSQ w k a -> Int
length :: forall a. WeightedPSQ w k a -> Int
$celem :: forall w k a. Eq a => a -> WeightedPSQ w k a -> Bool
elem :: forall a. Eq a => a -> WeightedPSQ w k a -> Bool
$cmaximum :: forall w k a. Ord a => WeightedPSQ w k a -> a
maximum :: forall a. Ord a => WeightedPSQ w k a -> a
$cminimum :: forall w k a. Ord a => WeightedPSQ w k a -> a
minimum :: forall a. Ord a => WeightedPSQ w k a -> a
$csum :: forall w k a. Num a => WeightedPSQ w k a -> a
sum :: forall a. Num a => WeightedPSQ w k a -> a
$cproduct :: forall w k a. Num a => WeightedPSQ w k a -> a
product :: forall a. Num a => WeightedPSQ w k a -> a
F.Foldable, Functor (WeightedPSQ w k)
Foldable (WeightedPSQ w k)
Functor (WeightedPSQ w k)
-> Foldable (WeightedPSQ w k)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> WeightedPSQ w k a -> f (WeightedPSQ w k b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    WeightedPSQ w k (f a) -> f (WeightedPSQ w k a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> WeightedPSQ w k a -> m (WeightedPSQ w k b))
-> (forall (m :: * -> *) a.
    Monad m =>
    WeightedPSQ w k (m a) -> m (WeightedPSQ w k a))
-> Traversable (WeightedPSQ w k)
forall w k. Functor (WeightedPSQ w k)
forall w k. Foldable (WeightedPSQ w k)
forall w k (m :: * -> *) a.
Monad m =>
WeightedPSQ w k (m a) -> m (WeightedPSQ w k a)
forall w k (f :: * -> *) a.
Applicative f =>
WeightedPSQ w k (f a) -> f (WeightedPSQ w k a)
forall w k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> WeightedPSQ w k a -> m (WeightedPSQ w k b)
forall w k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WeightedPSQ w k a -> f (WeightedPSQ w 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 =>
WeightedPSQ w k (m a) -> m (WeightedPSQ w k a)
forall (f :: * -> *) a.
Applicative f =>
WeightedPSQ w k (f a) -> f (WeightedPSQ w k a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> WeightedPSQ w k a -> m (WeightedPSQ w k b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WeightedPSQ w k a -> f (WeightedPSQ w k b)
$ctraverse :: forall w k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WeightedPSQ w k a -> f (WeightedPSQ w k b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WeightedPSQ w k a -> f (WeightedPSQ w k b)
$csequenceA :: forall w k (f :: * -> *) a.
Applicative f =>
WeightedPSQ w k (f a) -> f (WeightedPSQ w k a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
WeightedPSQ w k (f a) -> f (WeightedPSQ w k a)
$cmapM :: forall w k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> WeightedPSQ w k a -> m (WeightedPSQ w k b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> WeightedPSQ w k a -> m (WeightedPSQ w k b)
$csequence :: forall w k (m :: * -> *) a.
Monad m =>
WeightedPSQ w k (m a) -> m (WeightedPSQ w k a)
sequence :: forall (m :: * -> *) a.
Monad m =>
WeightedPSQ w k (m a) -> m (WeightedPSQ w k a)
T.Traversable)

-- | /O(N)/.
filter :: (v -> Bool) -> WeightedPSQ k w v -> WeightedPSQ k w v
filter :: forall v k w. (v -> Bool) -> WeightedPSQ k w v -> WeightedPSQ k w v
filter v -> Bool
p (WeightedPSQ [(k, w, v)]
xs) = [(k, w, v)] -> WeightedPSQ k w v
forall w k v. [(w, k, v)] -> WeightedPSQ w k v
WeightedPSQ (((k, w, v) -> Bool) -> [(k, w, v)] -> [(k, w, v)]
forall a. (a -> Bool) -> [a] -> [a]
L.filter (v -> Bool
p (v -> Bool) -> ((k, w, v) -> v) -> (k, w, v) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, w, v) -> v
forall x y z. (x, y, z) -> z
triple_3) [(k, w, v)]
xs)

-- | /O(1)/. Return @True@ if the @WeightedPSQ@ contains zero or one elements.
isZeroOrOne :: WeightedPSQ w k v -> Bool
isZeroOrOne :: forall w k a. WeightedPSQ w k a -> Bool
isZeroOrOne (WeightedPSQ [])  = Bool
True
isZeroOrOne (WeightedPSQ [(w, k, v)
_]) = Bool
True
isZeroOrOne WeightedPSQ w k v
_                 = Bool
False

-- | /O(1)/. Return the elements in order.
toList :: WeightedPSQ w k v -> [(w, k, v)]
toList :: forall w k v. WeightedPSQ w k v -> [(w, k, v)]
toList (WeightedPSQ [(w, k, v)]
xs) = [(w, k, v)]
xs

-- | /O(N log N)/.
fromList :: Ord w => [(w, k, v)] -> WeightedPSQ w k v
fromList :: forall w k v. Ord w => [(w, k, v)] -> WeightedPSQ w k v
fromList = [(w, k, v)] -> WeightedPSQ w k v
forall w k v. [(w, k, v)] -> WeightedPSQ w k v
WeightedPSQ ([(w, k, v)] -> WeightedPSQ w k v)
-> ([(w, k, v)] -> [(w, k, v)]) -> [(w, k, v)] -> WeightedPSQ w k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((w, k, v) -> (w, k, v) -> Ordering) -> [(w, k, v)] -> [(w, k, v)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
L.sortBy (((w, k, v) -> w) -> (w, k, v) -> (w, k, v) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (w, k, v) -> w
forall x y z. (x, y, z) -> x
triple_1)

-- | /O(N)/. Return the weights in order.
weights :: WeightedPSQ w k v -> [w]
weights :: forall w k v. WeightedPSQ w k v -> [w]
weights (WeightedPSQ [(w, k, v)]
xs) = ((w, k, v) -> w) -> [(w, k, v)] -> [w]
forall a b. (a -> b) -> [a] -> [b]
L.map (w, k, v) -> w
forall x y z. (x, y, z) -> x
triple_1 [(w, k, v)]
xs

-- | /O(N)/. Return the keys in order.
keys :: WeightedPSQ w k v -> [k]
keys :: forall w k v. WeightedPSQ w k v -> [k]
keys (WeightedPSQ [(w, k, v)]
xs) = ((w, k, v) -> k) -> [(w, k, v)] -> [k]
forall a b. (a -> b) -> [a] -> [b]
L.map (w, k, v) -> k
forall x y z. (x, y, z) -> y
triple_2 [(w, k, v)]
xs

-- | /O(N)/. Return the value associated with the first occurrence of the give
-- key, if it exists.
lookup :: Eq k => k -> WeightedPSQ w k v -> Maybe v
lookup :: forall k w v. Eq k => k -> WeightedPSQ w k v -> Maybe v
lookup k
k (WeightedPSQ [(w, k, v)]
xs) = (w, k, v) -> v
forall x y z. (x, y, z) -> z
triple_3 ((w, k, v) -> v) -> Maybe (w, k, v) -> Maybe v
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` ((w, k, v) -> Bool) -> [(w, k, v)] -> Maybe (w, k, v)
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a
L.find ((k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
==) (k -> Bool) -> ((w, k, v) -> k) -> (w, k, v) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (w, k, v) -> k
forall x y z. (x, y, z) -> y
triple_2) [(w, k, v)]
xs

-- | /O(N log N)/. Update the weights.
mapWeightsWithKey :: Ord w2
                  => (k -> w1 -> w2)
                  -> WeightedPSQ w1 k v
                  -> WeightedPSQ w2 k v
mapWeightsWithKey :: forall w2 k w1 v.
Ord w2 =>
(k -> w1 -> w2) -> WeightedPSQ w1 k v -> WeightedPSQ w2 k v
mapWeightsWithKey k -> w1 -> w2
f (WeightedPSQ [(w1, k, v)]
xs) = [(w2, k, v)] -> WeightedPSQ w2 k v
forall w k v. Ord w => [(w, k, v)] -> WeightedPSQ w k v
fromList ([(w2, k, v)] -> WeightedPSQ w2 k v)
-> [(w2, k, v)] -> WeightedPSQ w2 k v
forall a b. (a -> b) -> a -> b
$
                                       ((w1, k, v) -> (w2, k, v)) -> [(w1, k, v)] -> [(w2, k, v)]
forall a b. (a -> b) -> [a] -> [b]
L.map (\ (w1
w, k
k, v
v) -> (k -> w1 -> w2
f k
k w1
w, k
k, v
v)) [(w1, k, v)]
xs

-- | /O(N)/. Update the values.
mapWithKey :: (k -> v1 -> v2) -> WeightedPSQ w k v1 -> WeightedPSQ w k v2
mapWithKey :: forall k v1 v2 w.
(k -> v1 -> v2) -> WeightedPSQ w k v1 -> WeightedPSQ w k v2
mapWithKey k -> v1 -> v2
f (WeightedPSQ [(w, k, v1)]
xs) = [(w, k, v2)] -> WeightedPSQ w k v2
forall w k v. [(w, k, v)] -> WeightedPSQ w k v
WeightedPSQ ([(w, k, v2)] -> WeightedPSQ w k v2)
-> [(w, k, v2)] -> WeightedPSQ w k v2
forall a b. (a -> b) -> a -> b
$
                                ((w, k, v1) -> (w, k, v2)) -> [(w, k, v1)] -> [(w, k, v2)]
forall a b. (a -> b) -> [a] -> [b]
L.map (\ (w
w, k
k, v1
v) -> (w
w, k
k, k -> v1 -> v2
f k
k v1
v)) [(w, k, v1)]
xs

-- | /O(N)/. Traverse and update values in some applicative functor.
traverseWithKey
  :: Applicative f
  => (k -> v -> f v')
  -> WeightedPSQ w k v
  -> f (WeightedPSQ w k v')
traverseWithKey :: forall (f :: * -> *) k v v' w.
Applicative f =>
(k -> v -> f v') -> WeightedPSQ w k v -> f (WeightedPSQ w k v')
traverseWithKey k -> v -> f v'
f (WeightedPSQ [(w, k, v)]
q) = [(w, k, v')] -> WeightedPSQ w k v'
forall w k v. [(w, k, v)] -> WeightedPSQ w k v
WeightedPSQ ([(w, k, v')] -> WeightedPSQ w k v')
-> f [(w, k, v')] -> f (WeightedPSQ w k v')
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
  ((w, k, v) -> f (w, k, v')) -> [(w, k, v)] -> f [(w, k, v')]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse (\(w
w,k
k,v
v) -> (w
w,k
k,) (v' -> (w, k, v')) -> f v' -> f (w, k, v')
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v -> f v'
f k
k v
v) [(w, k, v)]
q

-- | /O((N + M) log (N + M))/. Combine two @WeightedPSQ@s, preserving all
-- elements. Elements from the first @WeightedPSQ@ come before elements in the
-- second when they have the same weight.
union :: Ord w => WeightedPSQ w k v -> WeightedPSQ w k v -> WeightedPSQ w k v
union :: forall w k v.
Ord w =>
WeightedPSQ w k v -> WeightedPSQ w k v -> WeightedPSQ w k v
union (WeightedPSQ [(w, k, v)]
xs) (WeightedPSQ [(w, k, v)]
ys) = [(w, k, v)] -> WeightedPSQ w k v
forall w k v. Ord w => [(w, k, v)] -> WeightedPSQ w k v
fromList ([(w, k, v)]
xs [(w, k, v)] -> [(w, k, v)] -> [(w, k, v)]
forall a. [a] -> [a] -> [a]
++ [(w, k, v)]
ys)

-- | /O(N)/. Return the prefix of values ending with the first element that
-- satisfies p, or all elements if none satisfy p.
takeUntil :: forall w k v. (v -> Bool) -> WeightedPSQ w k v -> WeightedPSQ w k v
takeUntil :: forall w k v. (v -> Bool) -> WeightedPSQ w k v -> WeightedPSQ w k v
takeUntil v -> Bool
p (WeightedPSQ [(w, k, v)]
xs) = [(w, k, v)] -> WeightedPSQ w k v
forall w k v. [(w, k, v)] -> WeightedPSQ w k v
WeightedPSQ ([(w, k, v)] -> [(w, k, v)]
go [(w, k, v)]
xs)
  where
    go :: [(w, k, v)] -> [(w, k, v)]
    go :: [(w, k, v)] -> [(w, k, v)]
go []       = []
    go ((w, k, v)
y : [(w, k, v)]
ys) = (w, k, v)
y (w, k, v) -> [(w, k, v)] -> [(w, k, v)]
forall a. a -> [a] -> [a]
: if v -> Bool
p ((w, k, v) -> v
forall x y z. (x, y, z) -> z
triple_3 (w, k, v)
y) then [] else [(w, k, v)] -> [(w, k, v)]
go [(w, k, v)]
ys

triple_1 :: (x, y, z) -> x
triple_1 :: forall x y z. (x, y, z) -> x
triple_1 (x
x, y
_, z
_) = x
x

triple_2 :: (x, y, z) -> y
triple_2 :: forall x y z. (x, y, z) -> y
triple_2 (x
_, y
y, z
_) = y
y

triple_3 :: (x, y, z) -> z
triple_3 :: forall x y z. (x, y, z) -> z
triple_3 (x
_, y
_, z
z) = z
z