IntMap lookupMin and lookupMax (#437)
authorbwroga <bwroga@users.noreply.github.com>
Mon, 18 Dec 2017 05:53:06 +0000 (00:53 -0500)
committerDavid Feuer <David.Feuer@gmail.com>
Mon, 18 Dec 2017 05:53:06 +0000 (00:53 -0500)
Add `lookupMin` and `lookupMax` to `Data.IntMap` to match the ones in `Data.Map`.

Data/IntMap/Internal.hs
Data/IntMap/Lazy.hs
Data/IntMap/Strict.hs
tests/intmap-properties.hs

index c7d1180..6251a33 100644 (file)
@@ -1,5 +1,6 @@
 {-# LANGUAGE CPP #-}
 {-# LANGUAGE BangPatterns #-}
+{-# LANGUAGE PatternGuards #-}
 #if __GLASGOW_HASKELL__
 {-# LANGUAGE MagicHash, DeriveDataTypeable, StandaloneDeriving #-}
 {-# LANGUAGE ScopedTypeVariables #-}
@@ -231,6 +232,8 @@ module Data.IntMap.Internal (
     , isProperSubmapOf, isProperSubmapOfBy
 
     -- * Min\/Max
+    , lookupMin
+    , lookupMax
     , findMin
     , findMax
     , deleteMin
@@ -2091,27 +2094,39 @@ deleteFindMax = fromMaybe (error "deleteFindMax: empty map has no maximal elemen
 deleteFindMin :: IntMap a -> ((Key, a), IntMap a)
 deleteFindMin = fromMaybe (error "deleteFindMin: empty map has no minimal element") . minViewWithKey
 
--- | /O(min(n,W))/. The minimal key of the map.
-findMin :: IntMap a -> (Key, a)
-findMin Nil = error $ "findMin: empty map has no minimal element"
-findMin (Tip k v) = (k,v)
-findMin (Bin _ m l r)
+-- | /O(min(n,W))/. The minimal key of the map. Returns 'Nothing' if the map is empty.
+lookupMin :: IntMap a -> Maybe (Key, a)
+lookupMin Nil = Nothing
+lookupMin (Tip k v) = Just (k,v)
+lookupMin (Bin _ m l r)
   | m < 0     = go r
   | otherwise = go l
-    where go (Tip k v)      = (k,v)
+    where go (Tip k v)      = Just (k,v)
           go (Bin _ _ l' _) = go l'
-          go Nil            = error "findMax Nil"
+          go Nil            = Nothing
 
--- | /O(min(n,W))/. The maximal key of the map.
-findMax :: IntMap a -> (Key, a)
-findMax Nil = error $ "findMax: empty map has no maximal element"
-findMax (Tip k v) = (k,v)
-findMax (Bin _ m l r)
+-- | /O(min(n,W))/. The minimal key of the map. Calls 'error' if the map is empty.
+findMin :: IntMap a -> (Key, a)
+findMin t
+  | Just r <- lookupMin t = r
+  | otherwise = error "findMin: empty map has no minimal element"
+  
+-- | /O(min(n,W))/. The maximal key of the map. Returns 'Nothing' if the map is empty.
+lookupMax :: IntMap a -> Maybe (Key, a)
+lookupMax Nil = Nothing
+lookupMax (Tip k v) = Just (k,v)
+lookupMax (Bin _ m l r)
   | m < 0     = go l
   | otherwise = go r
-    where go (Tip k v)      = (k,v)
+    where go (Tip k v)      = Just (k,v)
           go (Bin _ _ _ r') = go r'
-          go Nil            = error "findMax Nil"
+          go Nil            = Nothing
+
+-- | /O(min(n,W))/. The maximal key of the map. Calls 'error' if the map is empty.
+findMax :: IntMap a -> (Key, a)
+findMax t
+  | Just r <- lookupMax t = r
+  | otherwise = error "findMax: empty map has no maximal element"          
 
 -- | /O(min(n,W))/. Delete the minimal key. Returns an empty map if the map is empty.
 --
index 949ca66..fe558d8 100644 (file)
@@ -187,6 +187,8 @@ module Data.IntMap.Lazy (
     , isProperSubmapOf, isProperSubmapOfBy
 
     -- * Min\/Max
+    , lookupMin
+    , lookupMax
     , findMin
     , findMax
     , deleteMin
index 6106cf9..af17784 100644 (file)
@@ -194,6 +194,8 @@ module Data.IntMap.Strict (
     , isProperSubmapOf, isProperSubmapOfBy
 
     -- * Min\/Max
+    , lookupMin
+    , lookupMax
     , findMin
     , findMax
     , deleteMin
@@ -271,6 +273,8 @@ import Data.IntMap.Internal
   , lookupGE
   , lookupLT
   , lookupGT
+  , lookupMin
+  , lookupMax
   , minView
   , maxView
   , minViewWithKey
index 1c37cc9..44464c5 100644 (file)
@@ -106,6 +106,8 @@ main = defaultMain
              , testCase "isSubmapOf" test_isSubmapOf
              , testCase "isProperSubmapOfBy" test_isProperSubmapOfBy
              , testCase "isProperSubmapOf" test_isProperSubmapOf
+             , testCase "lookupMin" test_lookupMin
+             , testCase "lookupMax" test_lookupMax
              , testCase "findMin" test_findMin
              , testCase "findMax" test_findMax
              , testCase "deleteMin" test_deleteMin
@@ -152,6 +154,8 @@ main = defaultMain
              , testProperty "lookupGT"             prop_lookupGT
              , testProperty "lookupLE"             prop_lookupLE
              , testProperty "lookupGE"             prop_lookupGE
+             , testProperty "lookupMin"            prop_lookupMin
+             , testProperty "lookupMax"            prop_lookupMax
              , testProperty "findMin"              prop_findMin
              , testProperty "findMax"              prop_findMax
              , testProperty "deleteMin"            prop_deleteMinModel
@@ -190,6 +194,11 @@ instance Arbitrary a => Arbitrary (IntMap a) where
                 ; return (fromList (zip xs ks))
                 }
 
+newtype NonEmptyIntMap a = NonEmptyIntMap {getNonEmptyIntMap :: IntMap a} deriving (Eq, Show)
+
+instance Arbitrary a => Arbitrary (NonEmptyIntMap a) where
+  arbitrary = fmap (NonEmptyIntMap . fromList . getNonEmpty) arbitrary
+
 
 ------------------------------------------------------------------------
 
@@ -682,6 +691,16 @@ test_isProperSubmapOf = do
 ----------------------------------------------------------------
 -- Min/Max
 
+test_lookupMin :: Assertion
+test_lookupMin = do
+  lookupMin (fromList [(5,"a"), (3,"b")]) @?= Just (3,"b")
+  lookupMin (empty :: SMap) @?= Nothing
+
+test_lookupMax :: Assertion
+test_lookupMax = do
+  lookupMax (fromList [(5,"a"), (3,"b")]) @?= Just (5,"a")
+  lookupMax (empty :: SMap) @?= Nothing
+
 test_findMin :: Assertion
 test_findMin = findMin (fromList [(5,"a"), (3,"b")]) @?= (3,"b")
 
@@ -966,17 +985,17 @@ prop_lookupLE = test_lookupSomething lookupLE (<=)
 prop_lookupGE :: [(Int, Int)] -> Bool
 prop_lookupGE = test_lookupSomething lookupGE (>=)
 
-prop_findMin :: [(Int, Int)] -> Property
-prop_findMin ys = length ys > 0 ==>
-  let xs = List.nubBy ((==) `on` fst) ys
-      m  = fromList xs
-  in  findMin m == List.minimumBy (comparing fst) xs
+prop_lookupMin :: IntMap Int -> Property
+prop_lookupMin im = lookupMin im === listToMaybe (toAscList im)
 
-prop_findMax :: [(Int, Int)] -> Property
-prop_findMax ys = length ys > 0 ==>
-  let xs = List.nubBy ((==) `on` fst) ys
-      m  = fromList xs
-  in  findMax m == List.maximumBy (comparing fst) xs
+prop_lookupMax :: IntMap Int -> Property
+prop_lookupMax im = lookupMax im === listToMaybe (toDescList im)
+
+prop_findMin :: NonEmptyIntMap Int -> Property
+prop_findMin (NonEmptyIntMap im) = findMin im === head (toAscList im)
+
+prop_findMax :: NonEmptyIntMap Int -> Property
+prop_findMax (NonEmptyIntMap im) = findMax im === head (toDescList im)
 
 prop_deleteMinModel :: [(Int, Int)] -> Property
 prop_deleteMinModel ys = length ys > 0 ==>