Make strict IntMap merges strict
[packages/containers.git] / Data / IntMap / Strict.hs
1 {-# LANGUAGE CPP #-}
2 {-# LANGUAGE BangPatterns #-}
3 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
4 {-# LANGUAGE Trustworthy #-}
5 #endif
6
7 #include "containers.h"
8
9 -----------------------------------------------------------------------------
10 -- |
11 -- Module : Data.IntMap.Strict
12 -- Copyright : (c) Daan Leijen 2002
13 -- (c) Andriy Palamarchuk 2008
14 -- License : BSD-style
15 -- Maintainer : libraries@haskell.org
16 -- Portability : portable
17 --
18 --
19 -- = Finite Int Maps (strict interface)
20 --
21 -- The @'IntMap' v@ type represents a finite map (sometimes called a dictionary)
22 -- from key of type @Int@ to values of type @v@.
23 --
24 -- Each function in this module is careful to force values before installing
25 -- them in an 'IntMap'. This is usually more efficient when laziness is not
26 -- necessary. When laziness /is/ required, use the functions in
27 -- "Data.IntMap.Lazy".
28 --
29 -- In particular, the functions in this module obey the following law:
30 --
31 -- - If all values stored in all maps in the arguments are in WHNF, then all
32 -- values stored in all maps in the results will be in WHNF once those maps
33 -- are evaluated.
34 --
35 -- For a walkthrough of the most commonly used functions see the
36 -- <https://haskell-containers.readthedocs.io/en/latest/map.html maps introduction>.
37 --
38 -- This module is intended to be imported qualified, to avoid name clashes with
39 -- Prelude functions:
40 --
41 -- > import Data.IntMap.Strict (IntMap)
42 -- > import qualified Data.IntMap.Strict as IntMap
43 --
44 -- Note that the implementation is generally /left-biased/. Functions that take
45 -- two maps as arguments and combine them, such as `union` and `intersection`,
46 -- prefer the values in the first argument to those in the second.
47 --
48 --
49 -- == Detailed performance information
50 --
51 -- The amortized running time is given for each operation, with /n/ referring to
52 -- the number of entries in the map and /W/ referring to the number of bits in
53 -- an 'Int' (32 or 64).
54 --
55 -- Benchmarks comparing "Data.IntMap.Strict" with other dictionary
56 -- implementations can be found at https://github.com/haskell-perf/dictionaries.
57 --
58 --
59 -- == Warning
60 --
61 -- The 'IntMap' type is shared between the lazy and strict modules, meaning that
62 -- the same 'IntMap' value can be passed to functions in both modules. This
63 -- means that the 'Functor', 'Traversable' and 'Data.Data.Data' instances are
64 -- the same as for the "Data.IntMap.Lazy" module, so if they are used the
65 -- resulting map may contain suspended values (thunks).
66 --
67 --
68 -- == Implementation
69 --
70 -- The implementation is based on /big-endian patricia trees/. This data
71 -- structure performs especially well on binary operations like 'union' and
72 -- 'intersection'. Additionally, benchmarks show that it is also (much) faster
73 -- on insertions and deletions when compared to a generic size-balanced map
74 -- implementation (see "Data.Map").
75 --
76 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
77 -- Workshop on ML, September 1998, pages 77-86,
78 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
79 --
80 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
81 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
82 -- October 1968, pages 514-534.
83 --
84 -----------------------------------------------------------------------------
85
86 -- See the notes at the beginning of Data.IntMap.Internal.
87
88 module Data.IntMap.Strict (
89 -- * Map type
90 #if !defined(TESTING)
91 IntMap, Key -- instance Eq,Show
92 #else
93 IntMap(..), Key -- instance Eq,Show
94 #endif
95
96 -- * Construction
97 , empty
98 , singleton
99 , fromSet
100
101 -- ** From Unordered Lists
102 , fromList
103 , fromListWith
104 , fromListWithKey
105
106 -- ** From Ascending Lists
107 , fromAscList
108 , fromAscListWith
109 , fromAscListWithKey
110 , fromDistinctAscList
111
112 -- * Insertion
113 , insert
114 , insertWith
115 , insertWithKey
116 , insertLookupWithKey
117
118 -- * Deletion\/Update
119 , delete
120 , adjust
121 , adjustWithKey
122 , update
123 , updateWithKey
124 , updateLookupWithKey
125 , alter
126 , alterF
127
128 -- * Query
129 -- ** Lookup
130 , lookup
131 , (!?)
132 , (!)
133 , findWithDefault
134 , member
135 , notMember
136 , lookupLT
137 , lookupGT
138 , lookupLE
139 , lookupGE
140
141 -- ** Size
142 , null
143 , size
144
145 -- * Combine
146
147 -- ** Union
148 , union
149 , unionWith
150 , unionWithKey
151 , unions
152 , unionsWith
153
154 -- ** Difference
155 , difference
156 , (\\)
157 , differenceWith
158 , differenceWithKey
159
160 -- ** Intersection
161 , intersection
162 , intersectionWith
163 , intersectionWithKey
164
165 -- ** Universal combining function
166 , mergeWithKey
167
168 -- * Traversal
169 -- ** Map
170 , map
171 , mapWithKey
172 , traverseWithKey
173 , mapAccum
174 , mapAccumWithKey
175 , mapAccumRWithKey
176 , mapKeys
177 , mapKeysWith
178 , mapKeysMonotonic
179
180 -- * Folds
181 , foldr
182 , foldl
183 , foldrWithKey
184 , foldlWithKey
185 , foldMapWithKey
186
187 -- ** Strict folds
188 , foldr'
189 , foldl'
190 , foldrWithKey'
191 , foldlWithKey'
192
193 -- * Conversion
194 , elems
195 , keys
196 , assocs
197 , keysSet
198
199 -- ** Lists
200 , toList
201
202 -- ** Ordered lists
203 , toAscList
204 , toDescList
205
206 -- * Filter
207 , filter
208 , filterWithKey
209 , restrictKeys
210 , withoutKeys
211 , partition
212 , partitionWithKey
213
214 , mapMaybe
215 , mapMaybeWithKey
216 , mapEither
217 , mapEitherWithKey
218
219 , split
220 , splitLookup
221 , splitRoot
222
223 -- * Submap
224 , isSubmapOf, isSubmapOfBy
225 , isProperSubmapOf, isProperSubmapOfBy
226
227 -- * Min\/Max
228 , lookupMin
229 , lookupMax
230 , findMin
231 , findMax
232 , deleteMin
233 , deleteMax
234 , deleteFindMin
235 , deleteFindMax
236 , updateMin
237 , updateMax
238 , updateMinWithKey
239 , updateMaxWithKey
240 , minView
241 , maxView
242 , minViewWithKey
243 , maxViewWithKey
244
245 #ifdef __GLASGOW_HASKELL__
246 -- * Debugging
247 , showTree
248 , showTreeWith
249 #endif
250 ) where
251
252 import Data.IntMap.Strict.Internal
253 import Prelude ()