diff options
Diffstat (limited to 'src/Data')
-rw-r--r-- | src/Data/MinMaxPSQ.hs | 64 | ||||
-rw-r--r-- | src/Data/Wrapper/PSQ.hs | 6 |
2 files changed, 69 insertions, 1 deletions
diff --git a/src/Data/MinMaxPSQ.hs b/src/Data/MinMaxPSQ.hs new file mode 100644 index 00000000..96937604 --- /dev/null +++ b/src/Data/MinMaxPSQ.hs | |||
@@ -0,0 +1,64 @@ | |||
1 | {-# LANGUAGE BangPatterns #-} | ||
2 | module Data.MinMaxPSQ where | ||
3 | |||
4 | import Data.Ord | ||
5 | import qualified Data.Wrapper.PSQ as PSQ | ||
6 | ;import Data.Wrapper.PSQ as PSQ hiding (insert, null, size) | ||
7 | import Prelude hiding (null, take) | ||
8 | |||
9 | data MinMaxPSQ k p = MinMaxPSQ !(PSQ k p) !(PSQ k (Down p)) | ||
10 | |||
11 | empty :: MinMaxPSQ k p | ||
12 | empty = MinMaxPSQ PSQ.empty PSQ.empty | ||
13 | |||
14 | null :: MinMaxPSQ k p -> Bool | ||
15 | null (MinMaxPSQ nq xq) = PSQ.null nq | ||
16 | |||
17 | size :: MinMaxPSQ k p -> Int | ||
18 | size (MinMaxPSQ nq xq) = PSQ.size nq | ||
19 | |||
20 | toList :: (Ord k, Ord p) => MinMaxPSQ k p -> [Binding k p] | ||
21 | toList (MinMaxPSQ nq xq) = PSQ.toList nq | ||
22 | |||
23 | fromList :: (Ord k, Ord p) => [Binding k p] -> MinMaxPSQ k p | ||
24 | fromList kps = MinMaxPSQ (PSQ.fromList kps) | ||
25 | (PSQ.fromList $ map (\(k :-> p) -> (k :-> Down p)) kps) | ||
26 | |||
27 | findMin :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) | ||
28 | findMin (MinMaxPSQ nq xq) = PSQ.findMin nq | ||
29 | |||
30 | findMax :: (Ord k, Ord p) => MinMaxPSQ k p -> Maybe (Binding k p) | ||
31 | findMax (MinMaxPSQ nq xq) = fmap (\(k :-> Down p) -> k :-> p) $ PSQ.findMin xq | ||
32 | |||
33 | insert :: (Ord k, Ord p) => k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | ||
34 | insert k p (MinMaxPSQ nq xq) = MinMaxPSQ (PSQ.insert k p nq) | ||
35 | (PSQ.insert k (Down p) xq) | ||
36 | |||
37 | delete :: (Ord 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) | ||
39 | |||
40 | deleteMin :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p | ||
41 | deleteMin (MinMaxPSQ nq xq) = case PSQ.minView nq of | ||
42 | Just (k :-> _, nq') -> MinMaxPSQ nq' (PSQ.delete k xq) | ||
43 | Nothing -> MinMaxPSQ nq xq | ||
44 | |||
45 | deleteMax :: (Ord k, Ord p) => MinMaxPSQ k p -> MinMaxPSQ k p | ||
46 | deleteMax (MinMaxPSQ nq xq) = case PSQ.minView xq of | ||
47 | Just (k :-> _, xq') -> MinMaxPSQ (PSQ.delete k nq) xq' | ||
48 | Nothing -> MinMaxPSQ nq xq | ||
49 | |||
50 | minView :: (Ord 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))) | ||
52 | $ PSQ.minView nq | ||
53 | |||
54 | maxView :: (Ord 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')) | ||
56 | $ PSQ.minView xq | ||
57 | |||
58 | insertTake :: (Ord k, Ord p) => Int -> k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | ||
59 | insertTake n k p q = take n $ insert k p q | ||
60 | |||
61 | take :: (Ord k, Ord p) => Int -> MinMaxPSQ k p -> MinMaxPSQ k p | ||
62 | take !n !q | (size q <= n) = q | ||
63 | | null q = q | ||
64 | | otherwise = take n $ deleteMax q | ||
diff --git a/src/Data/Wrapper/PSQ.hs b/src/Data/Wrapper/PSQ.hs index e8fa2d98..2c08011b 100644 --- a/src/Data/Wrapper/PSQ.hs +++ b/src/Data/Wrapper/PSQ.hs | |||
@@ -15,10 +15,14 @@ type Binding k p = (k,p,()) | |||
15 | pattern (:->) :: k -> p -> Binding k p | 15 | pattern (:->) :: k -> p -> Binding k p |
16 | pattern k :-> p <- (k,p,()) where k :-> p = (k,p,()) | 16 | pattern k :-> p <- (k,p,()) where k :-> p = (k,p,()) |
17 | 17 | ||
18 | key :: Binding k v -> k | 18 | key :: Binding k p -> k |
19 | key (k,p,v) = k | 19 | key (k,p,v) = k |
20 | {-# INLINE key #-} | 20 | {-# INLINE key #-} |
21 | 21 | ||
22 | prio :: Binding k p -> p | ||
23 | prio (k,p,v) = p | ||
24 | {-# INLINE prio #-} | ||
25 | |||
22 | insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p | 26 | insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p |
23 | insert k p q = OrdPSQ.insert k p () q | 27 | insert k p q = OrdPSQ.insert k p () q |
24 | {-# INLINE insert #-} | 28 | {-# INLINE insert #-} |