X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FIntSet.hs;h=a3cb7666f7c26f43f1619c29ea1c94e9bf45bce2;hb=e9e2a5412bb7cda8d13a063ac403d9f18ac97380;hp=3e940f7c2f3792efb568320d250a0218fe0c2ba5;hpb=3b4368f9022e58ff7bdd16777df2b83f467326c1;p=ghc-base.git diff --git a/Data/IntSet.hs b/Data/IntSet.hs index 3e940f7..a3cb766 100644 --- a/Data/IntSet.hs +++ b/Data/IntSet.hs @@ -1,35 +1,40 @@ {-# OPTIONS -cpp -fglasgow-exts #-} --------------------------------------------------------------------------------- -{-| Module : Data.IntSet - Copyright : (c) Daan Leijen 2002 - License : BSD-style - Maintainer : libraries@haskell.org - Stability : provisional - Portability : portable - - An efficient implementation of integer sets. - - This module is intended to be imported @qualified@, to avoid name - clashes with Prelude functions. eg. - - > import Data.IntSet as Set - - The implementation is based on /big-endian patricia trees/. This data structure - performs especially well on binary operations like 'union' and 'intersection'. However, - my benchmarks show that it is also (much) faster on insertions and deletions when - compared to a generic size-balanced set implementation (see "Set"). - - * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\", - Workshop on ML, September 1998, pages 77--86, - - * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information - Coded In Alphanumeric/\", Journal of the ACM, 15(4), October 1968, pages 514--534. +----------------------------------------------------------------------------- +-- | +-- Module : Data.IntSet +-- Copyright : (c) Daan Leijen 2002 +-- License : BSD-style +-- Maintainer : libraries@haskell.org +-- Stability : provisional +-- Portability : portable +-- +-- An efficient implementation of integer sets. +-- +-- This module is intended to be imported @qualified@, to avoid name +-- clashes with "Prelude" functions. eg. +-- +-- > import Data.IntSet as Set +-- +-- The implementation is based on /big-endian patricia trees/. This data +-- structure performs especially well on binary operations like 'union' +-- and 'intersection'. However, my benchmarks show that it is also +-- (much) faster on insertions and deletions when compared to a generic +-- size-balanced set implementation (see "Data.Set"). +-- +-- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\", +-- Workshop on ML, September 1998, pages 77-86, +-- +-- +-- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve +-- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4), +-- October 1968, pages 514-534. +-- +-- Many operations have a worst-case complexity of /O(min(n,W))/. +-- This means that the operation can become linear in the number of +-- elements with a maximum of /W/ -- the number of bits in an 'Int' +-- (32 or 64). +----------------------------------------------------------------------------- - Many operations have a worst-case complexity of /O(min(n,W))/. This means that the - operation can become linear in the number of elements - with a maximum of /W/ -- the number of bits in an 'Int' (32 or 64). --} ----------------------------------------------------------------------------------} module Data.IntSet ( -- * Set type IntSet -- instance Eq,Show @@ -90,6 +95,7 @@ import Data.Int import qualified Data.List as List import Data.Monoid +import Data.Typeable {- -- just for testing @@ -98,21 +104,24 @@ import List (nub,sort) import qualified List -} +#if __GLASGOW_HASKELL__ +import Data.Generics.Basics +import Data.Generics.Instances +#endif -#ifdef __GLASGOW_HASKELL__ -{-------------------------------------------------------------------- - GHC: use unboxing to get @shiftRL@ inlined. ---------------------------------------------------------------------} #if __GLASGOW_HASKELL__ >= 503 import GHC.Word import GHC.Exts ( Word(..), Int(..), shiftRL# ) -#else +#elif __GLASGOW_HASKELL__ import Word import GlaExts ( Word(..), Int(..), shiftRL# ) +#else +import Data.Word #endif infixl 9 \\{-This comment teaches CPP correct behaviour -} +-- A "Nat" is a natural machine word (an unsigned Int) type Nat = Word natFromInt :: Int -> Nat @@ -122,50 +131,14 @@ intFromNat :: Nat -> Int intFromNat w = fromIntegral w shiftRL :: Nat -> Int -> Nat -shiftRL (W# x) (I# i) - = W# (shiftRL# x i) - -#elif __HUGS__ +#if __GLASGOW_HASKELL__ {-------------------------------------------------------------------- - Hugs: - * raises errors on boundary values when using 'fromIntegral' - but not with the deprecated 'fromInt/toInt'. - * Older Hugs doesn't define 'Word'. - * Newer Hugs defines 'Word' in the Prelude but no operations. + GHC: use unboxing to get @shiftRL@ inlined. --------------------------------------------------------------------} -import Data.Word -infixl 9 \\ -- comment to fool cpp - -type Nat = Word32 -- illegal on 64-bit platforms! - -natFromInt :: Int -> Nat -natFromInt i = fromInt i - -intFromNat :: Nat -> Int -intFromNat w = toInt w - -shiftRL :: Nat -> Int -> Nat -shiftRL x i = shiftR x i - +shiftRL (W# x) (I# i) + = W# (shiftRL# x i) #else -{-------------------------------------------------------------------- - 'Standard' Haskell - * A "Nat" is a natural machine word (an unsigned Int) ---------------------------------------------------------------------} -import Data.Word -infixl 9 \\ -- comment to fool cpp - -type Nat = Word - -natFromInt :: Int -> Nat -natFromInt i = fromIntegral i - -intFromNat :: Nat -> Int -intFromNat w = fromIntegral w - -shiftRL :: Nat -> Int -> Nat -shiftRL w i = shiftR w i - +shiftRL x i = shiftR x i #endif {-------------------------------------------------------------------- @@ -186,6 +159,23 @@ data IntSet = Nil type Prefix = Int type Mask = Int +#if __GLASGOW_HASKELL__ + +{-------------------------------------------------------------------- + A Data instance +--------------------------------------------------------------------} + +-- This instance preserves data abstraction at the cost of inefficiency. +-- We omit reflection services for the sake of data abstraction. + +instance Data IntSet where + gfoldl f z is = z fromList `f` (toList is) + toConstr _ = error "toConstr" + gunfold _ _ = error "gunfold" + dataTypeOf _ = mkNorepType "Data.IntSet.IntSet" + +#endif + {-------------------------------------------------------------------- Query --------------------------------------------------------------------} @@ -415,7 +405,7 @@ subsetCmp Nil Nil = EQ subsetCmp Nil t = LT -- | /O(n+m)/. Is this a subset? --- @(s1 `isSubsetOf` s2)@ tells whether s1 is a subset of s2. +-- @(s1 `isSubsetOf` s2)@ tells whether @s1@ is a subset of @s2@. isSubsetOf :: IntSet -> IntSet -> Bool isSubsetOf t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2) @@ -456,7 +446,7 @@ partition pred t Nil -> (Nil,Nil) --- | /O(log n)/. The expression (@split x set@) is a pair @(set1,set2)@ +-- | /O(log n)/. 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@. -- @@ -475,24 +465,24 @@ split x t -- | /O(log n)/. Performs a 'split' but also returns whether the pivot -- element was found in the original set. -splitMember :: Int -> IntSet -> (Bool,IntSet,IntSet) +splitMember :: Int -> IntSet -> (IntSet,Bool,IntSet) splitMember x t = case t of Bin p m l r - | zero x m -> let (found,lt,gt) = splitMember x l in (found,lt,union gt r) - | otherwise -> let (found,lt,gt) = splitMember x r in (found,union l lt,gt) + | zero x m -> let (lt,found,gt) = splitMember x l in (lt,found,union gt r) + | otherwise -> let (lt,found,gt) = splitMember x r in (union l lt,found,gt) Tip y - | x>y -> (False,t,Nil) - | x (False,Nil,t) - | otherwise -> (True,Nil,Nil) - Nil -> (False,Nil,Nil) + | x>y -> (t,False,Nil) + | x (Nil,False,t) + | otherwise -> (Nil,True,Nil) + Nil -> (Nil,False,Nil) {---------------------------------------------------------------------- Map ----------------------------------------------------------------------} -- | /O(n*min(n,W))/. --- @map f s@ is the set obtained by applying @f@ to each element of @s@. +-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@. -- -- It's worth noting that the size of the result may be smaller if, -- for some @(x,y)@, @x \/= y && f x == f y@ @@ -614,6 +604,13 @@ showSet (x:xs) showTail (x:xs) = showChar ',' . shows x . showTail xs {-------------------------------------------------------------------- + Typeable +--------------------------------------------------------------------} + +#include "Typeable.h" +INSTANCE_TYPEABLE0(IntSet,intSetTc,"IntSet") + +{-------------------------------------------------------------------- Debugging --------------------------------------------------------------------} -- | /O(n)/. Show the tree that implements the set. The tree is shown @@ -623,10 +620,10 @@ showTree s = showTreeWith True False s -{- | /O(n)/. The expression (@showTreeWith hang wide map@) shows +{- | /O(n)/. The expression (@'showTreeWith' hang wide map@) shows the tree that implements the set. If @hang@ is - @True@, a /hanging/ tree is shown otherwise a rotated tree is shown. If - @wide@ is true, an extra wide version is shown. + 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If + @wide@ is 'True', an extra wide version is shown. -} showTreeWith :: Bool -> Bool -> IntSet -> String showTreeWith hang wide t