--
-- 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'
, null
, size
, member
+ , notMember
, isSubsetOf
, isProperSubsetOf
Tip y -> (x==y)
Nil -> False
+-- | /O(log n)/. Is the element not in the set?
+notMember :: Int -> IntSet -> Bool
+notMember k = not . member k
+
-- 'lookup' is used by 'intersection' for left-biasing
lookup :: Int -> IntSet -> Maybe Int
lookup k t