diff options
author | James Crayne <jim.crayne@gmail.com> | 2019-09-28 13:43:29 -0400 |
---|---|---|
committer | Joe Crayne <joe@jerkface.net> | 2020-01-01 19:27:53 -0500 |
commit | 11987749fc6e6d3e53ea737d46d5ab13a16faeb8 (patch) | |
tree | 5716463275c2d3e902889db619908ded2a73971c /src/Data/MinMaxPSQ.hs | |
parent | add2c76bced51fde5e9917e7449ef52be70faf87 (diff) |
Factor out some new libraries
word64-map:
Data.Word64Map
network-addr:
Network.Address
tox-crypto:
Crypto.Tox
lifted-concurrent:
Control.Concurrent.Lifted.Instrument
Control.Concurrent.Async.Lifted.Instrument
psq-wrap:
Data.Wrapper.PSQInt
Data.Wrapper.PSQ
minmax-psq:
Data.MinMaxPSQ
tasks:
Control.Concurrent.Tasks
kad:
Network.Kademlia
Network.Kademlia.Bootstrap
Network.Kademlia.Routing
Network.Kademlia.CommonAPI
Network.Kademlia.Persistence
Network.Kademlia.Search
Diffstat (limited to 'src/Data/MinMaxPSQ.hs')
-rw-r--r-- | src/Data/MinMaxPSQ.hs | 112 |
1 files changed, 0 insertions, 112 deletions
diff --git a/src/Data/MinMaxPSQ.hs b/src/Data/MinMaxPSQ.hs deleted file mode 100644 index e7d7c760..00000000 --- a/src/Data/MinMaxPSQ.hs +++ /dev/null | |||
@@ -1,112 +0,0 @@ | |||
1 | {-# LANGUAGE BangPatterns, PatternSynonyms #-} | ||
2 | module Data.MinMaxPSQ | ||
3 | ( module Data.MinMaxPSQ | ||
4 | , Binding' | ||
5 | , pattern Binding | ||
6 | ) where | ||
7 | |||
8 | import Data.Ord | ||
9 | import qualified Data.Wrapper.PSQ as PSQ | ||
10 | ;import Data.Wrapper.PSQ as PSQ hiding (insert, insert', null, size) | ||
11 | import Prelude hiding (null, take) | ||
12 | |||
13 | data MinMaxPSQ' k p v = MinMaxPSQ !Int !(PSQ' k p v) !(PSQ' k (Down p) v) | ||
14 | type MinMaxPSQ k p = MinMaxPSQ' k p () | ||
15 | |||
16 | empty :: MinMaxPSQ' k p v | ||
17 | empty = MinMaxPSQ 0 PSQ.empty PSQ.empty | ||
18 | |||
19 | singleton' :: (PSQKey k, Ord p) => k -> v -> p -> MinMaxPSQ' k p v | ||
20 | singleton' k v p = MinMaxPSQ 1 (PSQ.singleton' k v p) (PSQ.singleton' k v (Down p)) | ||
21 | |||
22 | null :: MinMaxPSQ' k p v -> Bool | ||
23 | null (MinMaxPSQ sz _ _) = sz==0 | ||
24 | {-# INLINE null #-} | ||
25 | |||
26 | size :: MinMaxPSQ' k p v -> Int | ||
27 | size (MinMaxPSQ sz _ _) = sz | ||
28 | {-# INLINE size #-} | ||
29 | |||
30 | toList :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> [Binding' k p v] | ||
31 | toList (MinMaxPSQ _ nq xq) = PSQ.toList nq | ||
32 | |||
33 | fromList :: (PSQKey k, Ord p) => [Binding' k p v] -> MinMaxPSQ' k p v | ||
34 | fromList kps = let nq = PSQ.fromList kps | ||
35 | xq = PSQ.fromList $ map (\(Binding k v p) -> Binding k v (Down p)) kps | ||
36 | in MinMaxPSQ (PSQ.size nq) nq xq | ||
37 | |||
38 | findMin :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> Maybe (Binding' k p v) | ||
39 | findMin (MinMaxPSQ _ nq xq) = PSQ.findMin nq | ||
40 | |||
41 | findMax :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> Maybe (Binding' k p v) | ||
42 | findMax (MinMaxPSQ _ nq xq) = fmap (\(Binding k v (Down p)) -> Binding k v p) $ PSQ.findMin xq | ||
43 | |||
44 | insert :: (PSQKey k, Ord p) => k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | ||
45 | insert k p (MinMaxPSQ sz nq xq) = case PSQ.insertView k p () nq of | ||
46 | (Just _ ,nq') -> MinMaxPSQ sz nq' (PSQ.insert k (Down p) xq) | ||
47 | (Nothing,nq') -> MinMaxPSQ (sz+1) nq' (PSQ.insert k (Down p) xq) | ||
48 | |||
49 | insert' :: (PSQKey k, Ord p) => k -> v -> p -> MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
50 | insert' k v p (MinMaxPSQ sz nq xq) = case PSQ.insertView k p v nq of | ||
51 | (Just _ ,nq') -> MinMaxPSQ sz nq' (PSQ.insert' k v (Down p) xq) | ||
52 | (Nothing,nq') -> MinMaxPSQ (sz+1) nq' (PSQ.insert' k v (Down p) xq) | ||
53 | |||
54 | delete :: (PSQKey k, Ord p) => k -> MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
55 | delete k q@(MinMaxPSQ sz nq xq) = case PSQ.deleteView k nq of | ||
56 | Just (_,_,nq') -> MinMaxPSQ (sz - 1) nq' (PSQ.delete k xq) | ||
57 | Nothing -> q | ||
58 | |||
59 | deleteMin :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
60 | deleteMin q@(MinMaxPSQ sz nq xq) = case PSQ.minView nq of | ||
61 | Just (Binding k _ _, nq') -> MinMaxPSQ (sz - 1) nq' (PSQ.delete k xq) | ||
62 | Nothing -> q | ||
63 | |||
64 | deleteMax :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
65 | deleteMax q@(MinMaxPSQ sz nq xq) = case PSQ.minView xq of | ||
66 | Just (Binding k _ _, xq') -> MinMaxPSQ (sz - 1) (PSQ.delete k nq) xq' | ||
67 | Nothing -> q | ||
68 | |||
69 | minView :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> Maybe (Binding' k p v, MinMaxPSQ' k p v) | ||
70 | minView (MinMaxPSQ sz nq xq) = fmap (\(Binding k v p, nq') -> (Binding k v p, MinMaxPSQ (sz-1) nq' (PSQ.delete k xq))) | ||
71 | $ PSQ.minView nq | ||
72 | |||
73 | maxView :: (PSQKey k, Ord p) => MinMaxPSQ' k p v -> Maybe (Binding' k p v, MinMaxPSQ' k p v) | ||
74 | maxView (MinMaxPSQ sz nq xq) = fmap (\(Binding k v (Down p), xq') -> (Binding k v p, MinMaxPSQ (sz-1) (PSQ.delete k nq) xq')) | ||
75 | $ PSQ.minView xq | ||
76 | |||
77 | -- | Maintains a bounded 'MinMaxPSQ' by deleting the maximum element if the | ||
78 | -- insertion would cause the queue to have too many elements. | ||
79 | insertTake :: (PSQKey k, Ord p) => Int -> k -> p -> MinMaxPSQ k p -> MinMaxPSQ k p | ||
80 | insertTake n k p q | ||
81 | | size q < n = insert k p q | ||
82 | | size q == n = insert k p $ deleteMax q | ||
83 | | otherwise = take n $ insert k p q | ||
84 | |||
85 | -- | Maintains a bounded 'MinMaxPSQ\'' by deleting the maximum element if the | ||
86 | -- insertion would cause the queue to have too many elements. | ||
87 | insertTake' :: (PSQKey k, Ord p) => Int -> k -> v -> p -> MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
88 | insertTake' n k v p q | ||
89 | | size q < n = insert' k v p q | ||
90 | | size q == n = insert' k v p $ deleteMax q | ||
91 | | otherwise = take n $ insert' k v p q | ||
92 | |||
93 | |||
94 | -- | Truncate the 'MinMaxPSQ' to the given number of lowest priority elements. | ||
95 | take :: (PSQKey k, Ord p) => Int -> MinMaxPSQ' k p v -> MinMaxPSQ' k p v | ||
96 | take !n !q | (size q <= n) = q | ||
97 | | null q = q | ||
98 | | otherwise = take n $ deleteMax q | ||
99 | |||
100 | -- | Like 'take', except it provides a list deleted bindings. | ||
101 | takeView :: (PSQKey k, Ord p) => Int -> MinMaxPSQ' k p v -> ( [Binding' k p v], MinMaxPSQ' k p v ) | ||
102 | takeView !n !q | (size q <= n) = ([], q) | ||
103 | | null q = ([], q) | ||
104 | | otherwise = let Just (x,q') = maxView q | ||
105 | (xs,q'') = takeView n q' | ||
106 | ys = x:xs | ||
107 | in (ys, ys `seq` q'') | ||
108 | |||
109 | |||
110 | |||
111 | lookup' :: (PSQKey k, Ord p) => k -> MinMaxPSQ' k p v -> Maybe (p, v) | ||
112 | lookup' k (MinMaxPSQ _ q _) = PSQ.lookup k q | ||