X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FIntSet.hs;h=16226082b7f98e8f8475456341746321dc3fd8c5;hb=74bc2d04fdbae494bcf4839c4ec5e6ec1d0bf600;hp=b48a7c8f974fe268d790d750d06bf39ca9dfb3e6;hpb=b3211905110da0fca41fe9634bee0210c5325e9c;p=haskell-directory.git

diff --git a/Data/IntSet.hs b/Data/IntSet.hs
index b48a7c8..1622608 100644
--- a/Data/IntSet.hs
+++ b/Data/IntSet.hs
@@ -10,10 +10,11 @@
 --
 -- An efficient implementation of integer sets.
 --
--- This module is intended to be imported @qualified@, to avoid name
--- clashes with "Prelude" functions.  eg.
+-- Since many function names (but not the type name) clash with
+-- "Prelude" names, this module is usually imported @qualified@, e.g.
 --
--- >  import Data.IntSet as Set
+-- >  import Data.IntSet (IntSet)
+-- >  import qualified Data.IntSet as IntSet
 --
 -- The implementation is based on /big-endian patricia trees/.  This data
 -- structure performs especially well on binary operations like 'union'
@@ -67,6 +68,16 @@ module Data.IntSet  (
             , split
             , splitMember
 
+            -- * Min\/Max
+            , findMin   
+            , findMax
+            , deleteMin
+            , deleteMax
+            , deleteFindMin
+            , deleteFindMax
+            , maxView
+            , minView
+
             -- * Map
 	    , map
 
@@ -92,7 +103,6 @@ module Data.IntSet  (
 
 import Prelude hiding (lookup,filter,foldr,foldl,null,map)
 import Data.Bits 
-import Data.Int
 
 import qualified Data.List as List
 import Data.Monoid (Monoid(..))
@@ -107,12 +117,11 @@ import qualified List
 
 #if __GLASGOW_HASKELL__
 import Text.Read
-import Data.Generics.Basics
-import Data.Generics.Instances
+import Data.Generics.Basics (Data(..), mkNorepType)
+import Data.Generics.Instances ()
 #endif
 
 #if __GLASGOW_HASKELL__ >= 503
-import GHC.Word
 import GHC.Exts ( Word(..), Int(..), shiftRL# )
 #elif __GLASGOW_HASKELL__
 import Word
@@ -157,6 +166,8 @@ m1 \\ m2 = difference m1 m2
 data IntSet = Nil
             | Tip {-# UNPACK #-} !Int
             | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
+-- Invariant: Nil is never found as a child of Bin.
+
 
 type Prefix = Int
 type Mask   = Int
@@ -210,7 +221,7 @@ member x t
       Tip y -> (x==y)
       Nil   -> False
     
--- | /O(log n)/. Is the element not in the set?
+-- | /O(min(n,W))/. Is the element not in the set?
 notMember :: Int -> IntSet -> Bool
 notMember k = not . member k
 
@@ -457,7 +468,7 @@ partition pred t
       Nil -> (Nil,Nil)
 
 
--- | /O(log n)/. The expression (@'split' x set@) is a pair @(set1,set2)@
+-- | /O(min(n,W))/. The expression (@'split' x set@) is a pair @(set1,set2)@
 -- where all elements in @set1@ are lower than @x@ and all elements in
 -- @set2@ larger than @x@.
 --
@@ -490,7 +501,7 @@ split' x t
         | otherwise -> (Nil,Nil)
       Nil -> (Nil,Nil)
 
--- | /O(log n)/. Performs a 'split' but also returns whether the pivot
+-- | /O(min(n,W))/. Performs a 'split' but also returns whether the pivot
 -- element was found in the original set.
 splitMember :: Int -> IntSet -> (IntSet,Bool,IntSet)
 splitMember x t
@@ -521,6 +532,80 @@ splitMember' x t
       Nil -> (Nil,False,Nil)
 
 {----------------------------------------------------------------------
+  Min/Max
+----------------------------------------------------------------------}
+
+-- | /O(min(n,W))/. Retrieves the maximal key of the set, and the set stripped from that element
+-- @fail@s (in the monad) when passed an empty set.
+maxView :: (Monad m) => IntSet -> m (Int, IntSet)
+maxView t
+    = case t of
+        Bin p m l r | m < 0 -> let (result,t') = maxViewUnsigned l in return (result, bin p m t' r)
+        Bin p m l r         -> let (result,t') = maxViewUnsigned r in return (result, bin p m l t')            
+        Tip y -> return (y,Nil)
+        Nil -> fail "maxView: empty set has no maximal element"
+
+maxViewUnsigned :: IntSet -> (Int, IntSet)
+maxViewUnsigned t 
+    = case t of
+        Bin p m l r -> let (result,t') = maxViewUnsigned r in (result, bin p m l t')
+        Tip y -> (y, Nil)
+
+-- | /O(min(n,W))/. Retrieves the minimal key of the set, and the set stripped from that element
+-- @fail@s (in the monad) when passed an empty set.
+minView :: (Monad m) => IntSet -> m (Int, IntSet)
+minView t
+    = case t of
+        Bin p m l r | m < 0 -> let (result,t') = minViewUnsigned r in return (result, bin p m l t')            
+        Bin p m l r         -> let (result,t') = minViewUnsigned l in return (result, bin p m t' r)
+        Tip y -> return (y, Nil)
+        Nil -> fail "minView: empty set has no minimal element"
+
+minViewUnsigned :: IntSet -> (Int, IntSet)
+minViewUnsigned t 
+    = case t of
+        Bin p m l r -> let (result,t') = minViewUnsigned l in (result, bin p m t' r)
+        Tip y -> (y, Nil)
+
+
+-- Duplicate the Identity monad here because base < mtl.
+newtype Identity a = Identity { runIdentity :: a }
+instance Monad Identity where
+	return a = Identity a
+	m >>= k  = k (runIdentity m)
+
+
+-- | /O(min(n,W))/. Delete and find the minimal element.
+-- 
+-- > deleteFindMin set = (findMin set, deleteMin set)
+deleteFindMin :: IntSet -> (Int, IntSet)
+deleteFindMin = runIdentity . minView
+
+-- | /O(min(n,W))/. Delete and find the maximal element.
+-- 
+-- > deleteFindMax set = (findMax set, deleteMax set)
+deleteFindMax :: IntSet -> (Int, IntSet)
+deleteFindMax = runIdentity . maxView
+
+-- | /O(min(n,W))/. The minimal element of a set.
+findMin :: IntSet -> Int
+findMin = fst . runIdentity . minView
+
+-- | /O(min(n,W))/. The maximal element of a set.
+findMax :: IntSet -> Int
+findMax = fst . runIdentity . maxView
+
+-- | /O(min(n,W))/. Delete the minimal element.
+deleteMin :: IntSet -> IntSet
+deleteMin = snd . runIdentity . minView
+
+-- | /O(min(n,W))/. Delete the maximal element.
+deleteMax :: IntSet -> IntSet
+deleteMax = snd . runIdentity . maxView
+
+
+
+{----------------------------------------------------------------------
   Map
 ----------------------------------------------------------------------}