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