Add operator IntMap.!?. (#454)
[packages/containers.git] / Data / IntMap / Lazy.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.IntMap.Lazy
11 -- Copyright : (c) Daan Leijen 2002
12 -- (c) Andriy Palamarchuk 2008
13 -- License : BSD-style
14 -- Maintainer : libraries@haskell.org
15 -- Portability : portable
16 --
17 -- An efficient implementation of maps from integer keys to values
18 -- (dictionaries).
19 --
20 -- API of this module is strict in the keys, but lazy in the values.
21 -- If you need value-strict maps, use "Data.IntMap.Strict" instead.
22 -- The 'IntMap' type itself is shared between the lazy and strict modules,
23 -- meaning that the same 'IntMap' value can be passed to functions in
24 -- both modules (although that is rarely needed).
25 --
26 -- These modules are intended to be imported qualified, to avoid name
27 -- clashes with Prelude functions, e.g.
28 --
29 -- > import Data.IntMap.Lazy (IntMap)
30 -- > import qualified Data.IntMap.Lazy as IntMap
31 --
32 -- The implementation is based on /big-endian patricia trees/. This data
33 -- structure performs especially well on binary operations like 'union'
34 -- and 'intersection'. However, my benchmarks show that it is also
35 -- (much) faster on insertions and deletions when compared to a generic
36 -- size-balanced map implementation (see "Data.Map").
37 --
38 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
39 -- Workshop on ML, September 1998, pages 77-86,
40 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
41 --
42 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
43 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
44 -- October 1968, pages 514-534.
45 --
46 -- Operation comments contain the operation time complexity in
47 -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
48 -- Many operations have a worst-case complexity of /O(min(n,W))/.
49 -- This means that the operation can become linear in the number of
50 -- elements with a maximum of /W/ -- the number of bits in an 'Int'
51 -- (32 or 64).
52 -----------------------------------------------------------------------------
53
54 module Data.IntMap.Lazy (
55 -- * Strictness properties
56 -- $strictness
57
58 -- * Map type
59 #if !defined(TESTING)
60 IntMap, Key -- instance Eq,Show
61 #else
62 IntMap(..), Key -- instance Eq,Show
63 #endif
64
65 -- * Operators
66 , (!), (!?), (\\)
67
68 -- * Query
69 , IM.null
70 , size
71 , member
72 , notMember
73 , IM.lookup
74 , findWithDefault
75 , lookupLT
76 , lookupGT
77 , lookupLE
78 , lookupGE
79
80 -- * Construction
81 , empty
82 , singleton
83
84 -- ** Insertion
85 , insert
86 , insertWith
87 , insertWithKey
88 , insertLookupWithKey
89
90 -- ** Delete\/Update
91 , delete
92 , adjust
93 , adjustWithKey
94 , update
95 , updateWithKey
96 , updateLookupWithKey
97 , alter
98 , alterF
99
100 -- * Combine
101
102 -- ** Union
103 , union
104 , unionWith
105 , unionWithKey
106 , unions
107 , unionsWith
108
109 -- ** Difference
110 , difference
111 , differenceWith
112 , differenceWithKey
113
114 -- ** Intersection
115 , intersection
116 , intersectionWith
117 , intersectionWithKey
118
119 -- ** Universal combining function
120 , mergeWithKey
121
122 -- * Traversal
123 -- ** Map
124 , IM.map
125 , mapWithKey
126 , traverseWithKey
127 , mapAccum
128 , mapAccumWithKey
129 , mapAccumRWithKey
130 , mapKeys
131 , mapKeysWith
132 , mapKeysMonotonic
133
134 -- * Folds
135 , IM.foldr
136 , IM.foldl
137 , foldrWithKey
138 , foldlWithKey
139 , foldMapWithKey
140
141 -- ** Strict folds
142 , foldr'
143 , foldl'
144 , foldrWithKey'
145 , foldlWithKey'
146
147 -- * Conversion
148 , elems
149 , keys
150 , assocs
151 , keysSet
152 , fromSet
153
154 -- ** Lists
155 , toList
156 , fromList
157 , fromListWith
158 , fromListWithKey
159
160 -- ** Ordered lists
161 , toAscList
162 , toDescList
163 , fromAscList
164 , fromAscListWith
165 , fromAscListWithKey
166 , fromDistinctAscList
167
168 -- * Filter
169 , IM.filter
170 , filterWithKey
171 , restrictKeys
172 , withoutKeys
173 , partition
174 , partitionWithKey
175
176 , mapMaybe
177 , mapMaybeWithKey
178 , mapEither
179 , mapEitherWithKey
180
181 , split
182 , splitLookup
183 , splitRoot
184
185 -- * Submap
186 , isSubmapOf, isSubmapOfBy
187 , isProperSubmapOf, isProperSubmapOfBy
188
189 -- * Min\/Max
190 , lookupMin
191 , lookupMax
192 , findMin
193 , findMax
194 , deleteMin
195 , deleteMax
196 , deleteFindMin
197 , deleteFindMax
198 , updateMin
199 , updateMax
200 , updateMinWithKey
201 , updateMaxWithKey
202 , minView
203 , maxView
204 , minViewWithKey
205 , maxViewWithKey
206
207 -- * Debugging
208 , showTree
209 , showTreeWith
210 ) where
211
212 import Data.IntMap.Internal as IM hiding (showTree, showTreeWith)
213 import Data.IntMap.Internal.DeprecatedDebug
214
215 -- $strictness
216 --
217 -- This module satisfies the following strictness property:
218 --
219 -- * Key arguments are evaluated to WHNF
220 --
221 -- Here are some examples that illustrate the property:
222 --
223 -- > insertWith (\ new old -> old) undefined v m == undefined
224 -- > insertWith (\ new old -> old) k undefined m == OK
225 -- > delete undefined m == undefined