3409d5536f15615a346660aca76c9601c0134038
[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 -- * Operators
77 , (\\)
78
79 -- * Query
80 , IS.null
81 , size
82 , member
83 , notMember
84 , lookupLT
85 , lookupGT
86 , lookupLE
87 , lookupGE
88 , isSubsetOf
89 , isProperSubsetOf
90 , disjoint
91
92 -- * Construction
93 , empty
94 , singleton
95 , insert
96 , delete
97
98 -- * Combine
99 , union
100 , unions
101 , difference
102 , intersection
103
104 -- * Filter
105 , IS.filter
106 , partition
107 , split
108 , splitMember
109 , splitRoot
110
111 -- * Map
112 , IS.map
113
114 -- * Folds
115 , IS.foldr
116 , IS.foldl
117 -- ** Strict folds
118 , foldr'
119 , foldl'
120 -- ** Legacy folds
121 , fold
122
123 -- * Min\/Max
124 , findMin
125 , findMax
126 , deleteMin
127 , deleteMax
128 , deleteFindMin
129 , deleteFindMax
130 , maxView
131 , minView
132
133 -- * Conversion
134
135 -- ** List
136 , elems
137 , toList
138 , fromList
139
140 -- ** Ordered list
141 , toAscList
142 , toDescList
143 , fromAscList
144 , fromDistinctAscList
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