--
-- 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'
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(..))
#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
-- | /O(log n)/. Is the element not in the set?
notMember :: Int -> IntSet -> Bool
-notMember k = not $ member k
+notMember k = not . member k
-- 'lookup' is used by 'intersection' for left-biasing
lookup :: Int -> IntSet -> Maybe Int