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