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