757abaad8fb8fc680ce343899fd32df37c1364a1
[packages/containers.git] / Data / IntSet.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
3 {-# LANGUAGE Safe #-}
4 #endif
5
6 #include "containers.h"
7
8 -----------------------------------------------------------------------------
9 -- |
10 -- Module : Data.IntSet
11 -- Copyright : (c) Daan Leijen 2002
12 -- (c) Joachim Breitner 2011
13 -- License : BSD-style
14 -- Maintainer : libraries@haskell.org
15 -- Stability : provisional
16 -- Portability : portable
17 --
18 -- An efficient implementation of integer sets.
19 --
20 -- These modules are intended to be imported qualified, to avoid name
21 -- clashes with Prelude functions, e.g.
22 --
23 -- > import Data.IntSet (IntSet)
24 -- > import qualified Data.IntSet as IntSet
25 --
26 -- The implementation is based on /big-endian patricia trees/. This data
27 -- structure performs especially well on binary operations like 'union'
28 -- and 'intersection'. However, my benchmarks show that it is also
29 -- (much) faster on insertions and deletions when compared to a generic
30 -- size-balanced set implementation (see "Data.Set").
31 --
32 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
33 -- Workshop on ML, September 1998, pages 77-86,
34 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
35 --
36 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
37 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
38 -- October 1968, pages 514-534.
39 --
40 -- Additionally, this implementation places bitmaps in the leaves of the tree.
41 -- Their size is the natural size of a machine word (32 or 64 bits) and greatly
42 -- reduce memory footprint and execution times for dense sets, e.g. sets where
43 -- it is likely that many values lie close to each other. The asymptotics are
44 -- not affected by this optimization.
45 --
46 -- Many operations have a worst-case complexity of /O(min(n,W))/.
47 -- This means that the operation can become linear in the number of
48 -- elements with a maximum of /W/ -- the number of bits in an 'Int'
49 -- (32 or 64).
50 -----------------------------------------------------------------------------
51
52 module Data.IntSet (
53 -- * Strictness properties
54 -- $strictness
55
56 -- * Set type
57 #if !defined(TESTING)
58 IntSet -- instance Eq,Show
59 #else
60 IntSet(..) -- instance Eq,Show
61 #endif
62 , Key
63
64 -- * Operators
65 , (\\)
66
67 -- * Query
68 , IS.null
69 , size
70 , member
71 , notMember
72 , lookupLT
73 , lookupGT
74 , lookupLE
75 , lookupGE
76 , isSubsetOf
77 , isProperSubsetOf
78
79 -- * Construction
80 , empty
81 , singleton
82 , insert
83 , delete
84
85 -- * Combine
86 , union
87 , unions
88 , difference
89 , intersection
90
91 -- * Filter
92 , IS.filter
93 , partition
94 , split
95 , splitMember
96 , splitRoot
97
98 -- * Map
99 , IS.map
100
101 -- * Folds
102 , IS.foldr
103 , IS.foldl
104 -- ** Strict folds
105 , foldr'
106 , foldl'
107 -- ** Legacy folds
108 , fold
109
110 -- * Min\/Max
111 , findMin
112 , findMax
113 , deleteMin
114 , deleteMax
115 , deleteFindMin
116 , deleteFindMax
117 , maxView
118 , minView
119
120 -- * Conversion
121
122 -- ** List
123 , elems
124 , toList
125 , fromList
126
127 -- ** Ordered list
128 , toAscList
129 , toDescList
130 , fromAscList
131 , fromDistinctAscList
132
133 -- * Debugging
134 , showTree
135 , showTreeWith
136
137 #if defined(TESTING)
138 -- * Internals
139 , match
140 #endif
141 ) where
142
143 import Data.IntSet.Base as IS
144
145 -- $strictness
146 --
147 -- This module satisfies the following strictness property:
148 --
149 -- * Key arguments are evaluated to WHNF
150 --
151 -- Here are some examples that illustrate the property:
152 --
153 -- > delete undefined s == undefined