ff849b1d27fa90aff5d0df7601c0a12218ec29af
[packages/containers.git] / benchmarks / LookupGE / LookupGE_IntMap.hs
1 {-# LANGUAGE CPP #-}
2 module LookupGE_IntMap where
3
4 import Prelude hiding (null)
5 import Data.IntMap.Internal
6
7 lookupGE1 :: Key -> IntMap a -> Maybe (Key,a)
8 lookupGE1 k m =
9 case splitLookup k m of
10 (_,Just v,_) -> Just (k,v)
11 (_,Nothing,r) -> findMinMaybe r
12
13 lookupGE2 :: Key -> IntMap a -> Maybe (Key,a)
14 lookupGE2 k t = case t of
15 Bin _ m l r | m < 0 -> if k >= 0
16 then go l
17 else case go r of
18 Nothing -> Just $ findMin l
19 justx -> justx
20 _ -> go t
21 where
22 go (Bin p m l r)
23 | nomatch k p m = if k < p
24 then Just $ findMin l
25 else Nothing
26 | zero k m = case go l of
27 Nothing -> Just $ findMin r
28 justx -> justx
29 | otherwise = go r
30 go (Tip ky y)
31 | k > ky = Nothing
32 | otherwise = Just (ky, y)
33 go Nil = Nothing
34
35 lookupGE3 :: Key -> IntMap a -> Maybe (Key,a)
36 lookupGE3 k t = k `seq` case t of
37 Bin _ m l r | m < 0 -> if k >= 0
38 then go Nothing l
39 else go (Just (findMin l)) r
40 _ -> go Nothing t
41 where
42 go def (Bin p m l r)
43 | nomatch k p m = if k < p then Just $ findMin l else def
44 | zero k m = go (Just $ findMin r) l
45 | otherwise = go def r
46 go def (Tip ky y)
47 | k > ky = def
48 | otherwise = Just (ky, y)
49 go def Nil = def
50
51 lookupGE4 :: Key -> IntMap a -> Maybe (Key,a)
52 lookupGE4 k t = k `seq` case t of
53 Bin _ m l r | m < 0 -> if k >= 0 then go Nil l
54 else go l r
55 _ -> go Nil t
56 where
57 go def (Bin p m l r)
58 | nomatch k p m = if k < p then fMin l else fMin def
59 | zero k m = go r l
60 | otherwise = go def r
61 go def (Tip ky y)
62 | k > ky = fMin def
63 | otherwise = Just (ky, y)
64 go def Nil = fMin def
65
66 fMin :: IntMap a -> Maybe (Key, a)
67 fMin Nil = Nothing
68 fMin (Tip ky y) = Just (ky, y)
69 fMin (Bin _ _ l _) = fMin l
70
71 -------------------------------------------------------------------------------
72 -- Utilities
73 -------------------------------------------------------------------------------
74
75 -- | /O(log n)/. The minimal key of the map.
76 findMinMaybe :: IntMap a -> Maybe (Key, a)
77 findMinMaybe m
78 | null m = Nothing
79 | otherwise = Just (findMin m)
80
81 #ifdef TESTING
82 -------------------------------------------------------------------------------
83 -- Properties:
84 -------------------------------------------------------------------------------
85
86 prop_lookupGE12 :: Int -> [Int] -> Bool
87 prop_lookupGE12 x xs = case fromList $ zip xs xs of m -> lookupGE1 x m == lookupGE2 x m
88
89 prop_lookupGE13 :: Int -> [Int] -> Bool
90 prop_lookupGE13 x xs = case fromList $ zip xs xs of m -> lookupGE1 x m == lookupGE3 x m
91
92 prop_lookupGE14 :: Int -> [Int] -> Bool
93 prop_lookupGE14 x xs = case fromList $ zip xs xs of m -> lookupGE1 x m == lookupGE4 x m
94 #endif