[project @ 2003-10-20 20:00:25 by panne]

[ghc-base.git] / Data / FiniteMap.hs

diff --git a/Data/FiniteMap.hs b/Data/FiniteMap.hs
index 244b811..54ff2f6 100644 (file)
--- a/Data/FiniteMap.hs
+++ b/Data/FiniteMap.hs
@@ -74,13 +74,13 @@ module Data.FiniteMap (
        IF_NOT_GHC(intersectFM_C COMMA)
        IF_NOT_GHC(mapFM COMMA filterFM COMMA)
 
+       foldFM_GE, fmToList_GE, keysFM_GE, eltsFM_GE
+
 #ifdef COMPILING_GHC
        , bagToFM
 #endif
     ) where
 
-import Prelude
-
 import Data.Maybe ( isJust )
 #ifdef __GLASGOW_HASKELL__
 import GHC.Base
@@ -142,7 +142,8 @@ addListToFM :: (Ord key OUTPUTABLE_key) => FiniteMap key elt -> [(key,elt)] -> F
 
 -- | Adds an element to a 'FiniteMap'.  If there is already an element
 -- with the same key, then the specified combination function is used
--- to calculate the new value.
+-- to calculate the new value. The already present element is passed as
+-- the first argument and the new element to add as second.
 addToFM_C      :: (Ord key OUTPUTABLE_key) => (elt -> elt -> elt)
                           -> FiniteMap key elt -> key -> elt
                           -> FiniteMap key elt
@@ -160,12 +161,12 @@ delFromFM :: (Ord key OUTPUTABLE_key) => FiniteMap key elt -> key   -> FiniteMap
 -- | List version of 'delFromFM'.
 delListFromFM  :: (Ord key OUTPUTABLE_key) => FiniteMap key elt -> [key] -> FiniteMap key elt
 
--- | Combine two 'FiniteMaps'.  Mappings in the second argument shadow
+-- | Combine two 'FiniteMap's.  Mappings in the second argument shadow
 -- those in the first.
 plusFM         :: (Ord key OUTPUTABLE_key) => FiniteMap key elt -> FiniteMap key elt
                           -> FiniteMap key elt
 
--- | Combine two 'FiniteMaps'.  The specified combination function is
+-- | Combine two 'FiniteMap's.  The specified combination function is
 -- used to calculate the new value when there are two elements with
 -- the same key.
 plusFM_C       :: (Ord key OUTPUTABLE_key) => (elt -> elt -> elt)
@@ -210,8 +211,21 @@ lookupWithDefaultFM
                -- to return for an unmapped key
 
 --     LISTIFYING
+
+-- | Convert a 'FiniteMap' to a @[(key, elt)]@ sorted by 'Ord' key
+--
 fmToList       :: FiniteMap key elt -> [(key,elt)]
+
+-- | Extract the keys from a 'FiniteMap', in the order of the keys, so
+--
+-- > keysFM == map fst . fmToList
+--
 keysFM         :: FiniteMap key elt -> [key]
+
+-- | Extract the elements from a 'FiniteMap', in the order of the keys, so
+--
+-- > eltsFM == map snd . fmToList
+--
 eltsFM         :: FiniteMap key elt -> [elt]
 
 -- ---------------------------------------------------------------------------
@@ -418,6 +432,33 @@ eltsFM fm   = foldFM (\ key elt rest -> elt : rest)       [] fm
 
 
 -- ---------------------------------------------------------------------------
+-- Bulk operations on all keys >= a certain threshold
+
+-- | Fold through all elements greater than or equal to the supplied key,
+-- in increasing order.
+foldFM_GE       :: Ord key => (key -> elt -> a -> a) -> a -> key ->
+   FiniteMap key elt -> a
+
+foldFM_GE k z fr EmptyFM = z
+foldFM_GE k z fr (Branch key elt _ fm_l fm_r)
+  | key >= fr = foldFM_GE k (k key elt (foldFM_GE k z fr fm_r)) fr fm_l
+  | otherwise = foldFM_GE k z fr fm_r
+
+-- | List elements greater than or equal to the supplied key, in increasing
+-- order
+fmToList_GE      :: Ord key => FiniteMap key elt -> key ->  [(key,elt)]
+fmToList_GE fm fr = foldFM_GE (\ key elt rest -> (key,elt) : rest) [] fr fm
+
+-- | List keys greater than or equal to the supplied key, in increasing order
+keysFM_GE       :: Ord key => FiniteMap key elt -> key -> [key]
+keysFM_GE fm fr  = foldFM_GE (\ key elt rest -> key : rest)       [] fr fm
+
+-- | List elements corresponding to keys greater than or equal to the supplied
+-- key, in increasing order of key.
+eltsFM_GE       :: Ord key => FiniteMap key elt -> key -> [elt]
+eltsFM_GE fm fr  = foldFM_GE (\ key elt rest -> elt : rest)       [] fr fm
+
+-- ---------------------------------------------------------------------------
 -- The implementation of balancing
 
 -- Basic construction of a @FiniteMap@:
@@ -775,4 +816,4 @@ instance (Ord key, Ord elt) => Ord (FiniteMap key elt) where
     IF_NCG(COMMA   (elt -> elt -> elt) -> FiniteMap Reg elt -> FiniteMap Reg elt -> FiniteMap Reg elt)
     #-}
 
-#endif {- compiling for GHC -}
+#endif /* compiling for GHC */