1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
{-# LANGUAGE BangPatterns #-}
module Data.MinMaxPSQ where
import Data.Ord
import qualified Data.Wrapper.PSQ as PSQ
;import Data.Wrapper.PSQ as PSQ hiding (insert, null, size)
import Prelude hiding (null, take)
data MinMaxPSQ k p = MinMaxPSQ !(PSQ k p) !(PSQ k (Down p))
empty :: MinMaxPSQ k p
empty = MinMaxPSQ PSQ.empty PSQ.empty
null :: MinMaxPSQ k p -> Bool
null (MinMaxPSQ nq xq) = PSQ.null nq
size :: MinMaxPSQ k p -> Int
size (MinMaxPSQ nq xq) = PSQ.size nq
toList :: (Ord k, Ord p) => MinMaxPSQ k p -> [Binding k p]
toList (MinMaxPSQ nq xq) = PSQ.toList nq
fromList :: (Ord k, Ord p) => [Binding k p] -> MinMaxPSQ k p
fromList kps = MinMaxPSQ (PSQ.fromList kps)
(PSQ.fromList $ map (\(k :-> p) -> (k :-> Down p)) kps)
findMin :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p)
findMin (MinMaxPSQ nq xq) = PSQ.findMin nq
findMax :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p)
findMax (MinMaxPSQ nq xq) = fmap (\(k :-> Down p) -> k :-> p) $ PSQ.findMin xq
insert :: (Ord k, Ord p) => k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p
insert k p (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.insert k p nq)
(PSQ.insert k (Down p) xq)
delete :: (Ord k, Ord p) => k -> MinMaxPSQ k p -> MinMaxPSQ k p
delete k (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.delete k nq) (PSQ.delete k xq)
deleteMin :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p
deleteMin (MinMaxPSQ nq xq) = case PSQ.minView nq of
Just (k :-> _, nq') -> MinMaxPSQ nq' (PSQ.delete k xq)
Nothing -> MinMaxPSQ nq xq
deleteMax :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p
deleteMax (MinMaxPSQ nq xq) = case PSQ.minView xq of
Just (k :-> _, xq') -> MinMaxPSQ (PSQ.delete k nq) xq'
Nothing -> MinMaxPSQ nq xq
minView :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p)
minView (MinMaxPSQ nq xq) = fmap (\(k :-> p, nq') -> (k :-> p, MinMaxPSQ nq' (PSQ.delete k xq)))
$ PSQ.minView nq
maxView :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p)
maxView (MinMaxPSQ nq xq) = fmap (\(k :-> Down p, xq') -> (k :-> p, MinMaxPSQ (PSQ.delete k nq) xq'))
$ PSQ.minView xq
insertTake :: (Ord k, Ord p) => Int -> k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p
insertTake n k p q = take n $ insert k p q
take :: (Ord k, Ord p) => Int -> MinMaxPSQ k p -> MinMaxPSQ k p
take !n !q | (size q <= n) = q
| null q = q
| otherwise = take n $ deleteMax q
|
