{-# LANGUAGE CPP #-}
#ifdef __GLASGOW_HASKELL__
{-# LANGUAGE Safe #-}
#endif

#include "containers.h"
------------------------------------------------------------------------------- |-- Module : Data.IntSet-- Copyright : (c) Daan Leijen 2002-- (c) Joachim Breitner 2011-- License : BSD-style-- Maintainer : libraries@haskell.org-- Portability : portable------ = Finite Int Sets---- The @'IntSet'@ type represents a set of elements of type @Int@. An @IntSet@-- is strict in its elements.---- For a walkthrough of the most commonly used functions see their-- <https://haskell-containers.readthedocs.io/en/latest/set.html sets introduction>.---- 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------ == Implementation---- The implementation is based on /big-endian patricia trees/. This data-- structure performs especially well on binary operations like 'union'-- and 'intersection'. Additionally, 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,-- <https://web.archive.org/web/20150417234429/https://ittc.ku.edu/~andygill/papers/IntMap98.pdf>.---- * D.R. Morrison,-- \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",-- Journal of the ACM, 15(4), October 1968, pages 514-534,-- <https://doi.org/10.1145/321479.321481>.---- 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-- reduces the 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.------ == Performance information---- The time complexity is given for each operation in-- [big-O notation](http://en.wikipedia.org/wiki/Big_O_notation), with \(n\)-- referring to the number of entries in the map and \(W\) referring to the-- number of bits in an 'Int' (32 or 64).---- Operations like 'member', 'insert', and 'delete' 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). These peculiar asymptotics are determined by the-- depth of the Patricia trees:---- * even for an extremely unbalanced tree, the depth cannot be larger than-- the number of elements \(n\),-- * each level of a Patricia tree determines at least one more bit-- shared by all subelements, so there could not be more-- than \(W\) levels.---- If all \(n\) elements in the tree are between 0 and \(N\) (or, say, between-- \(-N\) and \(N\)), the estimate can be refined to \(O(\min(n, \log N))\). If-- the set is sufficiently "dense", this becomes \(O(\min(n, \log n))\) or-- simply the familiar \(O(\log n)\), matching balanced binary trees.---- The most performant scenario for 'IntSet' are elements from a contiguous-- subset, in which case the complexity is proportional to \(\log n\), capped-- by \(W\). The worst scenario are exponentially growing elements \(1,2,4,-- \ldots,2^n\), for which complexity grows as fast as \(n\) but again is capped-- by \(W\).---- Binary set operations like 'union' and 'intersection' take-- \(O(\min(n, m \log \frac{2^W}{m}))\) time, where \(m\) and \(n\)-- are the sizes of the smaller and larger input sets respectively.-------------------------------------------------------------------------------moduleData.IntSet(-- * Set typeIntSet -- instance Eq,Show,Key -- * Construction,empty ,singleton ,fromList ,fromRange ,fromAscList ,fromDistinctAscList -- * Insertion,insert -- * Deletion,delete -- * Generalized insertion/deletion,alterF -- * Query,member ,notMember ,lookupLT ,lookupGT ,lookupLE ,lookupGE ,IS.null ,size ,isSubsetOf ,isProperSubsetOf ,disjoint -- * Combine,union ,unions ,difference ,(\\) ,intersection ,intersections ,symmetricDifference ,Intersection (..)-- * Filter,IS.filter ,partition ,takeWhileAntitone ,dropWhileAntitone ,spanAntitone ,split ,splitMember ,splitRoot -- * Map,IS.map ,mapMonotonic -- * Folds,IS.foldr ,IS.foldl ,IS.foldMap -- ** Strict folds,IS.foldr' ,IS.foldl' -- ** Legacy folds,fold -- * Min\/Max,lookupMin ,lookupMax ,findMin ,findMax ,deleteMin ,deleteMax ,deleteFindMin ,deleteFindMax ,maxView ,minView -- * Conversion-- ** List,elems ,toList ,toAscList ,toDescList -- * Debugging,showTree ,showTreeWith )whereimportData.IntSet.Internal asIS