Data/IntSet.hs

{-# LANGUAGE CPP #-}
#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
{-# LANGUAGE Safe #-}
#endif
-----------------------------------------------------------------------------
-- |
-- Module : Data.IntSet
-- Copyright : (c) Daan Leijen 2002
-- (c) Joachim Breitner 2011
-- License : BSD-style
-- Maintainer : libraries@haskell.org
-- Stability : provisional
-- Portability : portable
--
-- An efficient implementation of integer sets.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
-- > 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'
-- 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,
-- <http://citeseer.ist.psu.edu/okasaki98fast.html>
--
-- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
-- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
-- October 1968, pages 514-534.
--
-- Additionally, this implementation places bitmaps in the leaves of the tree.
-- Their size is the natural size of a machine word (32 or 64 bits) and greatly
-- reduce memory footprint and execution times for dense sets, e.g. sets where
-- it is likely that many values lie close to each other. The asymptotics are
-- not affected by this optimization.
--
-- 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 (
 -- * Strictness properties
 -- $strictness

 -- * Set type
#if !defined(TESTING)
 IntSet -- instance Eq,Show
#else
 IntSet(..) -- instance Eq,Show
#endif

 -- * Operators
 , (\\)

 -- * Query
 , IS.null
 , size
 , member
 , notMember
 , lookupLT
 , lookupGT
 , lookupLE
 , lookupGE
 , isSubsetOf
 , isProperSubsetOf

 -- * Construction
 , empty
 , singleton
 , insert
 , delete

 -- * Combine
 , union
 , unions
 , difference
 , intersection

 -- * Filter
 , IS.filter
 , partition
 , split
 , splitMember

 -- * Map
 , IS.map

 -- * Folds
 , IS.foldr
 , IS.foldl
 -- ** Strict folds
 , foldr'
 , foldl'
 -- ** Legacy folds
 , fold

 -- * Min\/Max
 , findMin
 , findMax
 , deleteMin
 , deleteMax
 , deleteFindMin
 , deleteFindMax
 , maxView
 , minView

 -- * Conversion

 -- ** List
 , elems
 , toList
 , fromList

 -- ** Ordered list
 , toAscList
 , toDescList
 , fromAscList
 , fromDistinctAscList

 -- * Debugging
 , showTree
 , showTreeWith

#if defined(TESTING)
 -- * Internals
 , match
#endif
 ) where

import Data.IntSet.Base as IS

-- $strictness
--
-- This module satisfies the following strictness property:
--
-- * Key arguments are evaluated to WHNF
--
-- Here are some examples that illustrate the property:
--
-- > delete undefined s == undefined