diff options
author | joe <joe@jerkface.net> | 2017-07-20 00:01:29 -0400 |
---|---|---|
committer | joe <joe@jerkface.net> | 2017-07-20 00:01:29 -0400 |
commit | fbd053967c814697ad21fde2dc8e95f7a4683302 (patch) | |
tree | 5aa07550819aedb74c4a806bd4fc3147d5cb4da4 /src/Data | |
parent | b3c832ebd86281bfaa4fe6bb88aaacacbed0eadc (diff) |
Update MinMaxPSQ to use HashPSQ.
Diffstat (limited to 'src/Data')
-rw-r--r-- | src/Data/MinMaxPSQ.hs | 24 |
1 files changed, 12 insertions, 12 deletions
diff --git a/src/Data/MinMaxPSQ.hs b/src/Data/MinMaxPSQ.hs index 96937604..f41da4a4 100644 --- a/src/Data/MinMaxPSQ.hs +++ b/src/Data/MinMaxPSQ.hs | |||
@@ -17,48 +17,48 @@ null (MinMaxPSQ nq xq) = PSQ.null nq | |||
17 | size :: MinMaxPSQ k p -> Int | 17 | size :: MinMaxPSQ k p -> Int |
18 | size (MinMaxPSQ nq xq) = PSQ.size nq | 18 | size (MinMaxPSQ nq xq) = PSQ.size nq |
19 | 19 | ||
20 | toList :: (Ord k, Ord p) => MinMaxPSQ k p -> [Binding k p] | 20 | toList :: (PSQKey k, Ord p) => MinMaxPSQ k p -> [Binding k p] |
21 | toList (MinMaxPSQ nq xq) = PSQ.toList nq | 21 | toList (MinMaxPSQ nq xq) = PSQ.toList nq |
22 | 22 | ||
23 | fromList :: (Ord k, Ord p) => [Binding k p] -> MinMaxPSQ k p | 23 | fromList :: (PSQKey k, Ord p) => [Binding k p] -> MinMaxPSQ k p |
24 | fromList kps = MinMaxPSQ (PSQ.fromList kps) | 24 | fromList kps = MinMaxPSQ (PSQ.fromList kps) |
25 | (PSQ.fromList $ map (\(k :-> p) -> (k :-> Down p)) kps) | 25 | (PSQ.fromList $ map (\(k :-> p) -> (k :-> Down p)) kps) |
26 | 26 | ||
27 | findMin :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) | 27 | findMin :: (PSQKey k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) |
28 | findMin (MinMaxPSQ nq xq) = PSQ.findMin nq | 28 | findMin (MinMaxPSQ nq xq) = PSQ.findMin nq |
29 | 29 | ||
30 | findMax :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) | 30 | findMax :: (PSQKey k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) |
31 | findMax (MinMaxPSQ nq xq) = fmap (\(k :-> Down p) -> k :-> p) $ PSQ.findMin xq | 31 | findMax (MinMaxPSQ nq xq) = fmap (\(k :-> Down p) -> k :-> p) $ PSQ.findMin xq |
32 | 32 | ||
33 | insert :: (Ord k, Ord p) => k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | 33 | insert :: (PSQKey k, Ord p) => k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p |
34 | insert k p (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.insert k p nq) | 34 | insert k p (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.insert k p nq) |
35 | (PSQ.insert k (Down p) xq) | 35 | (PSQ.insert k (Down p) xq) |
36 | 36 | ||
37 | delete :: (Ord k, Ord p) => k -> MinMaxPSQ k p -> MinMaxPSQ k p | 37 | delete :: (PSQKey k, Ord p) => k -> MinMaxPSQ k p -> MinMaxPSQ k p |
38 | delete k (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.delete k nq) (PSQ.delete k xq) | 38 | delete k (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.delete k nq) (PSQ.delete k xq) |
39 | 39 | ||
40 | deleteMin :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p | 40 | deleteMin :: (PSQKey k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p |
41 | deleteMin (MinMaxPSQ nq xq) = case PSQ.minView nq of | 41 | deleteMin (MinMaxPSQ nq xq) = case PSQ.minView nq of |
42 | Just (k :-> _, nq') -> MinMaxPSQ nq' (PSQ.delete k xq) | 42 | Just (k :-> _, nq') -> MinMaxPSQ nq' (PSQ.delete k xq) |
43 | Nothing -> MinMaxPSQ nq xq | 43 | Nothing -> MinMaxPSQ nq xq |
44 | 44 | ||
45 | deleteMax :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p | 45 | deleteMax :: (PSQKey k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p |
46 | deleteMax (MinMaxPSQ nq xq) = case PSQ.minView xq of | 46 | deleteMax (MinMaxPSQ nq xq) = case PSQ.minView xq of |
47 | Just (k :-> _, xq') -> MinMaxPSQ (PSQ.delete k nq) xq' | 47 | Just (k :-> _, xq') -> MinMaxPSQ (PSQ.delete k nq) xq' |
48 | Nothing -> MinMaxPSQ nq xq | 48 | Nothing -> MinMaxPSQ nq xq |
49 | 49 | ||
50 | minView :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p) | 50 | minView :: (PSQKey k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p) |
51 | minView (MinMaxPSQ nq xq) = fmap (\(k :-> p, nq') -> (k :-> p, MinMaxPSQ nq' (PSQ.delete k xq))) | 51 | minView (MinMaxPSQ nq xq) = fmap (\(k :-> p, nq') -> (k :-> p, MinMaxPSQ nq' (PSQ.delete k xq))) |
52 | $ PSQ.minView nq | 52 | $ PSQ.minView nq |
53 | 53 | ||
54 | maxView :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p) | 54 | maxView :: (PSQKey k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p, MinMaxPSQ k p) |
55 | maxView (MinMaxPSQ nq xq) = fmap (\(k :-> Down p, xq') -> (k :-> p, MinMaxPSQ (PSQ.delete k nq) xq')) | 55 | maxView (MinMaxPSQ nq xq) = fmap (\(k :-> Down p, xq') -> (k :-> p, MinMaxPSQ (PSQ.delete k nq) xq')) |
56 | $ PSQ.minView xq | 56 | $ PSQ.minView xq |
57 | 57 | ||
58 | insertTake :: (Ord k, Ord p) => Int -> k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | 58 | insertTake :: (PSQKey k, Ord p) => Int -> k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p |
59 | insertTake n k p q = take n $ insert k p q | 59 | insertTake n k p q = take n $ insert k p q |
60 | 60 | ||
61 | take :: (Ord k, Ord p) => Int -> MinMaxPSQ k p -> MinMaxPSQ k p | 61 | take :: (PSQKey k, Ord p) => Int -> MinMaxPSQ k p -> MinMaxPSQ k p |
62 | take !n !q | (size q <= n) = q | 62 | take !n !q | (size q <= n) = q |
63 | | null q = q | 63 | | null q = q |
64 | | otherwise = take n $ deleteMax q | 64 | | otherwise = take n $ deleteMax q |