3ec561090c1e6f9c2c8e829bc5543637fc3964ac
[packages/containers.git] / Data / IntMap / Strict.hs
1 {-# LANGUAGE CPP #-}
2 {-# LANGUAGE BangPatterns #-}
3 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
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 -- Stability : provisional
17 -- Portability : portable
18 --
19 -- An efficient implementation of maps from integer keys to values
20 -- (dictionaries).
21 --
22 -- API of this module is strict in both the keys and the values.
23 -- If you need value-lazy maps, use "Data.IntMap.Lazy" instead.
24 -- The 'IntMap' type itself is shared between the lazy and strict modules,
25 -- meaning that the same 'IntMap' value can be passed to functions in
26 -- both modules (although that is rarely needed).
27 --
28 -- These modules are intended to be imported qualified, to avoid name
29 -- clashes with Prelude functions, e.g.
30 --
31 -- > import Data.IntMap.Strict (IntMap)
32 -- > import qualified Data.IntMap.Strict as IntMap
33 --
34 -- The implementation is based on /big-endian patricia trees/. This data
35 -- structure performs especially well on binary operations like 'union'
36 -- and 'intersection'. However, my benchmarks show that it is also
37 -- (much) faster on insertions and deletions when compared to a generic
38 -- size-balanced map implementation (see "Data.Map").
39 --
40 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
41 -- Workshop on ML, September 1998, pages 77-86,
42 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
43 --
44 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
45 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
46 -- October 1968, pages 514-534.
47 --
48 -- Operation comments contain the operation time complexity in
49 -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
50 -- Many operations have a worst-case complexity of /O(min(n,W))/.
51 -- This means that the operation can become linear in the number of
52 -- elements with a maximum of /W/ -- the number of bits in an 'Int'
53 -- (32 or 64).
54 --
55 -- Be aware that the 'Functor', 'Traversable' and 'Data' instances
56 -- are the same as for the "Data.IntMap.Lazy" module, so if they are used
57 -- on strict maps, the resulting maps will be lazy.
58 -----------------------------------------------------------------------------
59
60 -- See the notes at the beginning of Data.IntMap.Base.
61
62 module Data.IntMap.Strict (
63 -- * Strictness properties
64 -- $strictness
65
66 -- * Map type
67 #if !defined(TESTING)
68 IntMap, Key -- instance Eq,Show
69 #else
70 IntMap(..), Key -- instance Eq,Show
71 #endif
72
73 -- * Operators
74 , (!), (\\)
75
76 -- * Query
77 , null
78 , size
79 , member
80 , notMember
81 , lookup
82 , findWithDefault
83 , lookupLT
84 , lookupGT
85 , lookupLE
86 , lookupGE
87
88 -- * Construction
89 , empty
90 , singleton
91
92 -- ** Insertion
93 , insert
94 , insertWith
95 , insertWithKey
96 , insertLookupWithKey
97
98 -- ** Delete\/Update
99 , delete
100 , adjust
101 , adjustWithKey
102 , update
103 , updateWithKey
104 , updateLookupWithKey
105 , alter
106 , alterF
107
108 -- * Combine
109
110 -- ** Union
111 , union
112 , unionWith
113 , unionWithKey
114 , unions
115 , unionsWith
116
117 -- ** Difference
118 , difference
119 , differenceWith
120 , differenceWithKey
121
122 -- ** Intersection
123 , intersection
124 , intersectionWith
125 , intersectionWithKey
126
127 -- ** Universal combining function
128 , mergeWithKey
129
130 -- * Traversal
131 -- ** Map
132 , map
133 , mapWithKey
134 , traverseWithKey
135 , mapAccum
136 , mapAccumWithKey
137 , mapAccumRWithKey
138 , mapKeys
139 , mapKeysWith
140 , mapKeysMonotonic
141
142 -- * Folds
143 , foldr
144 , foldl
145 , foldrWithKey
146 , foldlWithKey
147 , foldMapWithKey
148
149 -- ** Strict folds
150 , foldr'
151 , foldl'
152 , foldrWithKey'
153 , foldlWithKey'
154
155 -- * Conversion
156 , elems
157 , keys
158 , assocs
159 , keysSet
160 , fromSet
161
162 -- ** Lists
163 , toList
164 , fromList
165 , fromListWith
166 , fromListWithKey
167
168 -- ** Ordered lists
169 , toAscList
170 , toDescList
171 , fromAscList
172 , fromAscListWith
173 , fromAscListWithKey
174 , fromDistinctAscList
175
176 -- * Filter
177 , filter
178 , filterWithKey
179 , restrictKeys
180 , withoutKeys
181 , partition
182 , partitionWithKey
183
184 , mapMaybe
185 , mapMaybeWithKey
186 , mapEither
187 , mapEitherWithKey
188
189 , split
190 , splitLookup
191 , splitRoot
192
193 -- * Submap
194 , isSubmapOf, isSubmapOfBy
195 , isProperSubmapOf, isProperSubmapOfBy
196
197 -- * Min\/Max
198 , findMin
199 , findMax
200 , deleteMin
201 , deleteMax
202 , deleteFindMin
203 , deleteFindMax
204 , updateMin
205 , updateMax
206 , updateMinWithKey
207 , updateMaxWithKey
208 , minView
209 , maxView
210 , minViewWithKey
211 , maxViewWithKey
212
213 -- * Debugging
214 , showTree
215 , showTreeWith
216 ) where
217
218 import Prelude hiding (lookup,map,filter,foldr,foldl,null)
219
220 import Data.Bits
221 import Data.IntMap.Base hiding
222 ( findWithDefault
223 , singleton
224 , insert
225 , insertWith
226 , insertWithKey
227 , insertLookupWithKey
228 , adjust
229 , adjustWithKey
230 , update
231 , updateWithKey
232 , updateLookupWithKey
233 , alter
234 , alterF
235 , unionsWith
236 , unionWith
237 , unionWithKey
238 , differenceWith
239 , differenceWithKey
240 , intersectionWith
241 , intersectionWithKey
242 , mergeWithKey
243 , updateMinWithKey
244 , updateMaxWithKey
245 , updateMax
246 , updateMin
247 , map
248 , mapWithKey
249 , mapAccum
250 , mapAccumWithKey
251 , mapAccumRWithKey
252 , mapKeysWith
253 , mapMaybe
254 , mapMaybeWithKey
255 , mapEither
256 , mapEitherWithKey
257 , fromSet
258 , fromList
259 , fromListWith
260 , fromListWithKey
261 , fromAscList
262 , fromAscListWith
263 , fromAscListWithKey
264 , fromDistinctAscList
265 )
266
267 import qualified Data.IntSet.Base as IntSet
268 import Data.Utils.BitUtil
269 import Data.Utils.StrictFold
270 import Data.Utils.StrictPair
271 #if __GLASGOW_HASKELL__ >= 709
272 import Data.Coerce
273 #endif
274 #if !MIN_VERSION_base(4,8,0)
275 import Data.Functor((<$>))
276 #endif
277
278 -- $strictness
279 --
280 -- This module satisfies the following strictness properties:
281 --
282 -- 1. Key arguments are evaluated to WHNF;
283 --
284 -- 2. Keys and values are evaluated to WHNF before they are stored in
285 -- the map.
286 --
287 -- Here's an example illustrating the first property:
288 --
289 -- > delete undefined m == undefined
290 --
291 -- Here are some examples that illustrate the second property:
292 --
293 -- > map (\ v -> undefined) m == undefined -- m is not empty
294 -- > mapKeys (\ k -> undefined) m == undefined -- m is not empty
295
296 {--------------------------------------------------------------------
297 Query
298 --------------------------------------------------------------------}
299
300 -- | /O(min(n,W))/. The expression @('findWithDefault' def k map)@
301 -- returns the value at key @k@ or returns @def@ when the key is not an
302 -- element of the map.
303 --
304 -- > findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
305 -- > findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
306
307 -- See IntMap.Base.Note: Local 'go' functions and capturing]
308 findWithDefault :: a -> Key -> IntMap a -> a
309 findWithDefault def !k = go
310 where
311 go (Bin p m l r) | nomatch k p m = def
312 | zero k m = go l
313 | otherwise = go r
314 go (Tip kx x) | k == kx = x
315 | otherwise = def
316 go Nil = def
317
318 {--------------------------------------------------------------------
319 Construction
320 --------------------------------------------------------------------}
321 -- | /O(1)/. A map of one element.
322 --
323 -- > singleton 1 'a' == fromList [(1, 'a')]
324 -- > size (singleton 1 'a') == 1
325
326 singleton :: Key -> a -> IntMap a
327 singleton k !x
328 = Tip k x
329 {-# INLINE singleton #-}
330
331 {--------------------------------------------------------------------
332 Insert
333 --------------------------------------------------------------------}
334 -- | /O(min(n,W))/. Insert a new key\/value pair in the map.
335 -- If the key is already present in the map, the associated value is
336 -- replaced with the supplied value, i.e. 'insert' is equivalent to
337 -- @'insertWith' 'const'@.
338 --
339 -- > insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
340 -- > insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
341 -- > insert 5 'x' empty == singleton 5 'x'
342
343 insert :: Key -> a -> IntMap a -> IntMap a
344 insert !k !x t =
345 case t of
346 Bin p m l r
347 | nomatch k p m -> link k (Tip k x) p t
348 | zero k m -> Bin p m (insert k x l) r
349 | otherwise -> Bin p m l (insert k x r)
350 Tip ky _
351 | k==ky -> Tip k x
352 | otherwise -> link k (Tip k x) ky t
353 Nil -> Tip k x
354
355 -- right-biased insertion, used by 'union'
356 -- | /O(min(n,W))/. Insert with a combining function.
357 -- @'insertWith' f key value mp@
358 -- will insert the pair (key, value) into @mp@ if key does
359 -- not exist in the map. If the key does exist, the function will
360 -- insert @f new_value old_value@.
361 --
362 -- > insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
363 -- > insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
364 -- > insertWith (++) 5 "xxx" empty == singleton 5 "xxx"
365
366 insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
367 insertWith f k x t
368 = insertWithKey (\_ x' y' -> f x' y') k x t
369
370 -- | /O(min(n,W))/. Insert with a combining function.
371 -- @'insertWithKey' f key value mp@
372 -- will insert the pair (key, value) into @mp@ if key does
373 -- not exist in the map. If the key does exist, the function will
374 -- insert @f key new_value old_value@.
375 --
376 -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
377 -- > insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
378 -- > insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
379 -- > insertWithKey f 5 "xxx" empty == singleton 5 "xxx"
380 --
381 -- If the key exists in the map, this function is lazy in @x@ but strict
382 -- in the result of @f@.
383
384 insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
385 insertWithKey f !k x t =
386 case t of
387 Bin p m l r
388 | nomatch k p m -> link k (singleton k x) p t
389 | zero k m -> Bin p m (insertWithKey f k x l) r
390 | otherwise -> Bin p m l (insertWithKey f k x r)
391 Tip ky y
392 | k==ky -> Tip k $! f k x y
393 | otherwise -> link k (singleton k x) ky t
394 Nil -> singleton k x
395
396 -- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)
397 -- is a pair where the first element is equal to (@'lookup' k map@)
398 -- and the second element equal to (@'insertWithKey' f k x map@).
399 --
400 -- > let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
401 -- > insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
402 -- > insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")])
403 -- > insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")
404 --
405 -- This is how to define @insertLookup@ using @insertLookupWithKey@:
406 --
407 -- > let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
408 -- > insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
409 -- > insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "x")])
410
411 insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)
412 insertLookupWithKey f0 !k0 x0 t0 = toPair $ go f0 k0 x0 t0
413 where
414 go f k x t =
415 case t of
416 Bin p m l r
417 | nomatch k p m -> Nothing :*: link k (singleton k x) p t
418 | zero k m -> let (found :*: l') = go f k x l in (found :*: Bin p m l' r)
419 | otherwise -> let (found :*: r') = go f k x r in (found :*: Bin p m l r')
420 Tip ky y
421 | k==ky -> (Just y :*: (Tip k $! f k x y))
422 | otherwise -> (Nothing :*: link k (singleton k x) ky t)
423 Nil -> Nothing :*: (singleton k x)
424
425
426 {--------------------------------------------------------------------
427 Deletion
428 --------------------------------------------------------------------}
429 -- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not
430 -- a member of the map, the original map is returned.
431 --
432 -- > adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
433 -- > adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
434 -- > adjust ("new " ++) 7 empty == empty
435
436 adjust :: (a -> a) -> Key -> IntMap a -> IntMap a
437 adjust f k m
438 = adjustWithKey (\_ x -> f x) k m
439
440 -- | /O(min(n,W))/. Adjust a value at a specific key. When the key is not
441 -- a member of the map, the original map is returned.
442 --
443 -- > let f key x = (show key) ++ ":new " ++ x
444 -- > adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
445 -- > adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
446 -- > adjustWithKey f 7 empty == empty
447
448 adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap a
449 adjustWithKey f !k t =
450 case t of
451 Bin p m l r
452 | nomatch k p m -> t
453 | zero k m -> Bin p m (adjustWithKey f k l) r
454 | otherwise -> Bin p m l (adjustWithKey f k r)
455 Tip ky y
456 | k==ky -> Tip ky $! f k y
457 | otherwise -> t
458 Nil -> Nil
459
460 -- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@
461 -- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
462 -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
463 --
464 -- > let f x = if x == "a" then Just "new a" else Nothing
465 -- > update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
466 -- > update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
467 -- > update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
468
469 update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
470 update f
471 = updateWithKey (\_ x -> f x)
472
473 -- | /O(min(n,W))/. The expression (@'update' f k map@) updates the value @x@
474 -- at @k@ (if it is in the map). If (@f k x@) is 'Nothing', the element is
475 -- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
476 --
477 -- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
478 -- > updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
479 -- > updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
480 -- > updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
481
482 updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a
483 updateWithKey f !k t =
484 case t of
485 Bin p m l r
486 | nomatch k p m -> t
487 | zero k m -> binCheckLeft p m (updateWithKey f k l) r
488 | otherwise -> binCheckRight p m l (updateWithKey f k r)
489 Tip ky y
490 | k==ky -> case f k y of
491 Just !y' -> Tip ky y'
492 Nothing -> Nil
493 | otherwise -> t
494 Nil -> Nil
495
496 -- | /O(min(n,W))/. Lookup and update.
497 -- The function returns original value, if it is updated.
498 -- This is different behavior than 'Data.Map.updateLookupWithKey'.
499 -- Returns the original key value if the map entry is deleted.
500 --
501 -- > let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
502 -- > updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
503 -- > updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])
504 -- > updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
505
506 updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a,IntMap a)
507 updateLookupWithKey f0 !k0 t0 = toPair $ go f0 k0 t0
508 where
509 go f k t =
510 case t of
511 Bin p m l r
512 | nomatch k p m -> (Nothing :*: t)
513 | zero k m -> let (found :*: l') = go f k l in (found :*: binCheckLeft p m l' r)
514 | otherwise -> let (found :*: r') = go f k r in (found :*: binCheckRight p m l r')
515 Tip ky y
516 | k==ky -> case f k y of
517 Just !y' -> (Just y :*: Tip ky y')
518 Nothing -> (Just y :*: Nil)
519 | otherwise -> (Nothing :*: t)
520 Nil -> (Nothing :*: Nil)
521
522
523
524 -- | /O(min(n,W))/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.
525 -- 'alter' can be used to insert, delete, or update a value in an 'IntMap'.
526 -- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
527 alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
528 alter f !k t =
529 case t of
530 Bin p m l r
531 | nomatch k p m -> case f Nothing of
532 Nothing -> t
533 Just !x -> link k (Tip k x) p t
534 | zero k m -> binCheckLeft p m (alter f k l) r
535 | otherwise -> binCheckRight p m l (alter f k r)
536 Tip ky y
537 | k==ky -> case f (Just y) of
538 Just !x -> Tip ky x
539 Nothing -> Nil
540 | otherwise -> case f Nothing of
541 Just !x -> link k (Tip k x) ky t
542 Nothing -> t
543 Nil -> case f Nothing of
544 Just !x -> Tip k x
545 Nothing -> Nil
546
547 -- | /O(log n)/. The expression (@'alterF' f k map@) alters the value @x@ at
548 -- @k@, or absence thereof. 'alterF' can be used to inspect, insert, delete,
549 -- or update a value in an 'IntMap'. In short : @'lookup' k <$> 'alterF' f k m = f
550 -- ('lookup' k m)@.
551 --
552 -- Example:
553 --
554 -- @
555 -- interactiveAlter :: Int -> IntMap String -> IO (IntMap String)
556 -- interactiveAlter k m = alterF f k m where
557 -- f Nothing -> do
558 -- putStrLn $ show k ++
559 -- " was not found in the map. Would you like to add it?"
560 -- getUserResponse1 :: IO (Maybe String)
561 -- f (Just old) -> do
562 -- putStrLn "The key is currently bound to " ++ show old ++
563 -- ". Would you like to change or delete it?"
564 -- getUserresponse2 :: IO (Maybe String)
565 -- @
566 --
567 -- 'alterF' is the most general operation for working with an individual
568 -- key that may or may not be in a given map.
569
570 -- Note: 'alterF' is a flipped version of the 'at' combinator from
571 -- 'Control.Lens.At'.
572 --
573 -- @since 0.5.8
574
575 alterF :: Functor f
576 => (Maybe a -> f (Maybe a)) -> Key -> IntMap a -> f (IntMap a)
577 -- This implementation was modified from 'Control.Lens.At'.
578 alterF f k m = (<$> f mv) $ \fres ->
579 case fres of
580 Nothing -> maybe m (const (delete k m)) mv
581 Just !v' -> insert k v' m
582 where mv = lookup k m
583
584
585 {--------------------------------------------------------------------
586 Union
587 --------------------------------------------------------------------}
588 -- | The union of a list of maps, with a combining operation.
589 --
590 -- > unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
591 -- > == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
592
593 unionsWith :: (a->a->a) -> [IntMap a] -> IntMap a
594 unionsWith f ts
595 = foldlStrict (unionWith f) empty ts
596
597 -- | /O(n+m)/. The union with a combining function.
598 --
599 -- > unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
600
601 unionWith :: (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
602 unionWith f m1 m2
603 = unionWithKey (\_ x y -> f x y) m1 m2
604
605 -- | /O(n+m)/. The union with a combining function.
606 --
607 -- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
608 -- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
609
610 unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
611 unionWithKey f m1 m2
612 = mergeWithKey' Bin (\(Tip k1 x1) (Tip _k2 x2) -> Tip k1 $! f k1 x1 x2) id id m1 m2
613
614 {--------------------------------------------------------------------
615 Difference
616 --------------------------------------------------------------------}
617
618 -- | /O(n+m)/. Difference with a combining function.
619 --
620 -- > let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
621 -- > differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
622 -- > == singleton 3 "b:B"
623
624 differenceWith :: (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
625 differenceWith f m1 m2
626 = differenceWithKey (\_ x y -> f x y) m1 m2
627
628 -- | /O(n+m)/. Difference with a combining function. When two equal keys are
629 -- encountered, the combining function is applied to the key and both values.
630 -- If it returns 'Nothing', the element is discarded (proper set difference).
631 -- If it returns (@'Just' y@), the element is updated with a new value @y@.
632 --
633 -- > let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
634 -- > differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
635 -- > == singleton 3 "3:b|B"
636
637 differenceWithKey :: (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
638 differenceWithKey f m1 m2
639 = mergeWithKey f id (const Nil) m1 m2
640
641 {--------------------------------------------------------------------
642 Intersection
643 --------------------------------------------------------------------}
644
645 -- | /O(n+m)/. The intersection with a combining function.
646 --
647 -- > intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
648
649 intersectionWith :: (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
650 intersectionWith f m1 m2
651 = intersectionWithKey (\_ x y -> f x y) m1 m2
652
653 -- | /O(n+m)/. The intersection with a combining function.
654 --
655 -- > let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
656 -- > intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
657
658 intersectionWithKey :: (Key -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
659 intersectionWithKey f m1 m2
660 = mergeWithKey' bin (\(Tip k1 x1) (Tip _k2 x2) -> Tip k1 $! f k1 x1 x2) (const Nil) (const Nil) m1 m2
661
662 {--------------------------------------------------------------------
663 MergeWithKey
664 --------------------------------------------------------------------}
665
666 -- | /O(n+m)/. A high-performance universal combining function. Using
667 -- 'mergeWithKey', all combining functions can be defined without any loss of
668 -- efficiency (with exception of 'union', 'difference' and 'intersection',
669 -- where sharing of some nodes is lost with 'mergeWithKey').
670 --
671 -- Please make sure you know what is going on when using 'mergeWithKey',
672 -- otherwise you can be surprised by unexpected code growth or even
673 -- corruption of the data structure.
674 --
675 -- When 'mergeWithKey' is given three arguments, it is inlined to the call
676 -- site. You should therefore use 'mergeWithKey' only to define your custom
677 -- combining functions. For example, you could define 'unionWithKey',
678 -- 'differenceWithKey' and 'intersectionWithKey' as
679 --
680 -- > myUnionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) id id m1 m2
681 -- > myDifferenceWithKey f m1 m2 = mergeWithKey f id (const empty) m1 m2
682 -- > myIntersectionWithKey f m1 m2 = mergeWithKey (\k x1 x2 -> Just (f k x1 x2)) (const empty) (const empty) m1 m2
683 --
684 -- When calling @'mergeWithKey' combine only1 only2@, a function combining two
685 -- 'IntMap's is created, such that
686 --
687 -- * if a key is present in both maps, it is passed with both corresponding
688 -- values to the @combine@ function. Depending on the result, the key is either
689 -- present in the result with specified value, or is left out;
690 --
691 -- * a nonempty subtree present only in the first map is passed to @only1@ and
692 -- the output is added to the result;
693 --
694 -- * a nonempty subtree present only in the second map is passed to @only2@ and
695 -- the output is added to the result.
696 --
697 -- The @only1@ and @only2@ methods /must return a map with a subset (possibly empty) of the keys of the given map/.
698 -- The values can be modified arbitrarily. Most common variants of @only1@ and
699 -- @only2@ are 'id' and @'const' 'empty'@, but for example @'map' f@ or
700 -- @'filterWithKey' f@ could be used for any @f@.
701
702 mergeWithKey :: (Key -> a -> b -> Maybe c) -> (IntMap a -> IntMap c) -> (IntMap b -> IntMap c)
703 -> IntMap a -> IntMap b -> IntMap c
704 mergeWithKey f g1 g2 = mergeWithKey' bin combine g1 g2
705 where -- We use the lambda form to avoid non-exhaustive pattern matches warning.
706 combine = \(Tip k1 x1) (Tip _k2 x2) -> case f k1 x1 x2 of Nothing -> Nil
707 Just !x -> Tip k1 x
708 {-# INLINE combine #-}
709 {-# INLINE mergeWithKey #-}
710
711 {--------------------------------------------------------------------
712 Min\/Max
713 --------------------------------------------------------------------}
714
715 -- | /O(log n)/. Update the value at the minimal key.
716 --
717 -- > updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
718 -- > updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
719
720 updateMinWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
721 updateMinWithKey f t =
722 case t of Bin p m l r | m < 0 -> binCheckRight p m l (go f r)
723 _ -> go f t
724 where
725 go f' (Bin p m l r) = binCheckLeft p m (go f' l) r
726 go f' (Tip k y) = case f' k y of
727 Just !y' -> Tip k y'
728 Nothing -> Nil
729 go _ Nil = error "updateMinWithKey Nil"
730
731 -- | /O(log n)/. Update the value at the maximal key.
732 --
733 -- > updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
734 -- > updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
735
736 updateMaxWithKey :: (Key -> a -> Maybe a) -> IntMap a -> IntMap a
737 updateMaxWithKey f t =
738 case t of Bin p m l r | m < 0 -> binCheckLeft p m (go f l) r
739 _ -> go f t
740 where
741 go f' (Bin p m l r) = binCheckRight p m l (go f' r)
742 go f' (Tip k y) = case f' k y of
743 Just !y' -> Tip k y'
744 Nothing -> Nil
745 go _ Nil = error "updateMaxWithKey Nil"
746
747 -- | /O(log n)/. Update the value at the maximal key.
748 --
749 -- > updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
750 -- > updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
751
752 updateMax :: (a -> Maybe a) -> IntMap a -> IntMap a
753 updateMax f = updateMaxWithKey (const f)
754
755 -- | /O(log n)/. Update the value at the minimal key.
756 --
757 -- > updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
758 -- > updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
759
760 updateMin :: (a -> Maybe a) -> IntMap a -> IntMap a
761 updateMin f = updateMinWithKey (const f)
762
763
764 {--------------------------------------------------------------------
765 Mapping
766 --------------------------------------------------------------------}
767 -- | /O(n)/. Map a function over all values in the map.
768 --
769 -- > map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
770
771 map :: (a -> b) -> IntMap a -> IntMap b
772 map f = go
773 where
774 go (Bin p m l r) = Bin p m (go l) (go r)
775 go (Tip k x) = Tip k $! f x
776 go Nil = Nil
777
778 #ifdef __GLASGOW_HASKELL__
779 {-# NOINLINE [1] map #-}
780 {-# RULES
781 "map/map" forall f g xs . map f (map g xs) = map (f . g) xs
782 #-}
783 #endif
784 #if __GLASGOW_HASKELL__ >= 709
785 {-# RULES
786 "map/coerce" map coerce = coerce
787 #-}
788 #endif
789
790 -- | /O(n)/. Map a function over all values in the map.
791 --
792 -- > let f key x = (show key) ++ ":" ++ x
793 -- > mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
794
795 mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap b
796 mapWithKey f t
797 = case t of
798 Bin p m l r -> Bin p m (mapWithKey f l) (mapWithKey f r)
799 Tip k x -> Tip k $! f k x
800 Nil -> Nil
801
802 #ifdef __GLASGOW_HASKELL__
803 {-# NOINLINE [1] mapWithKey #-}
804 {-# RULES
805 "mapWithKey/mapWithKey" forall f g xs . mapWithKey f (mapWithKey g xs) =
806 mapWithKey (\k a -> f k (g k a)) xs
807 "mapWithKey/map" forall f g xs . mapWithKey f (map g xs) =
808 mapWithKey (\k a -> f k (g a)) xs
809 "map/mapWithKey" forall f g xs . map f (mapWithKey g xs) =
810 mapWithKey (\k a -> f (g k a)) xs
811 #-}
812 #endif
813
814 -- | /O(n)/. The function @'mapAccum'@ threads an accumulating
815 -- argument through the map in ascending order of keys.
816 --
817 -- > let f a b = (a ++ b, b ++ "X")
818 -- > mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
819
820 mapAccum :: (a -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c)
821 mapAccum f = mapAccumWithKey (\a' _ x -> f a' x)
822
823 -- | /O(n)/. The function @'mapAccumWithKey'@ threads an accumulating
824 -- argument through the map in ascending order of keys.
825 --
826 -- > let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
827 -- > mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
828
829 mapAccumWithKey :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c)
830 mapAccumWithKey f a t
831 = mapAccumL f a t
832
833 -- | /O(n)/. The function @'mapAccumL'@ threads an accumulating
834 -- argument through the map in ascending order of keys. Strict in
835 -- the accumulating argument and the both elements of the
836 -- result of the function.
837 mapAccumL :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c)
838 mapAccumL f0 a0 t0 = toPair $ go f0 a0 t0
839 where
840 go f a t
841 = case t of
842 Bin p m l r -> let (a1 :*: l') = go f a l
843 (a2 :*: r') = go f a1 r
844 in (a2 :*: Bin p m l' r')
845 Tip k x -> let !(a',!x') = f a k x in (a' :*: Tip k x')
846 Nil -> (a :*: Nil)
847
848 -- | /O(n)/. The function @'mapAccumR'@ threads an accumulating
849 -- argument through the map in descending order of keys.
850 mapAccumRWithKey :: (a -> Key -> b -> (a,c)) -> a -> IntMap b -> (a,IntMap c)
851 mapAccumRWithKey f0 a0 t0 = toPair $ go f0 a0 t0
852 where
853 go f a t
854 = case t of
855 Bin p m l r -> let (a1 :*: r') = go f a r
856 (a2 :*: l') = go f a1 l
857 in (a2 :*: Bin p m l' r')
858 Tip k x -> let !(a',!x') = f a k x in (a' :*: Tip k x')
859 Nil -> (a :*: Nil)
860
861 -- | /O(n*log n)/.
862 -- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
863 --
864 -- The size of the result may be smaller if @f@ maps two or more distinct
865 -- keys to the same new key. In this case the associated values will be
866 -- combined using @c@.
867 --
868 -- > mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
869 -- > mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
870
871 mapKeysWith :: (a -> a -> a) -> (Key->Key) -> IntMap a -> IntMap a
872 mapKeysWith c f = fromListWith c . foldrWithKey (\k x xs -> (f k, x) : xs) []
873
874 {--------------------------------------------------------------------
875 Filter
876 --------------------------------------------------------------------}
877 -- | /O(n)/. Map values and collect the 'Just' results.
878 --
879 -- > let f x = if x == "a" then Just "new a" else Nothing
880 -- > mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
881
882 mapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap b
883 mapMaybe f = mapMaybeWithKey (\_ x -> f x)
884
885 -- | /O(n)/. Map keys\/values and collect the 'Just' results.
886 --
887 -- > let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
888 -- > mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
889
890 mapMaybeWithKey :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b
891 mapMaybeWithKey f (Bin p m l r)
892 = bin p m (mapMaybeWithKey f l) (mapMaybeWithKey f r)
893 mapMaybeWithKey f (Tip k x) = case f k x of
894 Just !y -> Tip k y
895 Nothing -> Nil
896 mapMaybeWithKey _ Nil = Nil
897
898 -- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
899 --
900 -- > let f a = if a < "c" then Left a else Right a
901 -- > mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
902 -- > == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
903 -- >
904 -- > mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
905 -- > == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
906
907 mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
908 mapEither f m
909 = mapEitherWithKey (\_ x -> f x) m
910
911 -- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
912 --
913 -- > let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
914 -- > mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
915 -- > == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
916 -- >
917 -- > mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
918 -- > == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
919
920 mapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)
921 mapEitherWithKey f0 t0 = toPair $ go f0 t0
922 where
923 go f (Bin p m l r)
924 = bin p m l1 r1 :*: bin p m l2 r2
925 where
926 (l1 :*: l2) = go f l
927 (r1 :*: r2) = go f r
928 go f (Tip k x) = case f k x of
929 Left !y -> (Tip k y :*: Nil)
930 Right !z -> (Nil :*: Tip k z)
931 go _ Nil = (Nil :*: Nil)
932
933 {--------------------------------------------------------------------
934 Conversions
935 --------------------------------------------------------------------}
936
937 -- | /O(n)/. Build a map from a set of keys and a function which for each key
938 -- computes its value.
939 --
940 -- > fromSet (\k -> replicate k 'a') (Data.IntSet.fromList [3, 5]) == fromList [(5,"aaaaa"), (3,"aaa")]
941 -- > fromSet undefined Data.IntSet.empty == empty
942
943 fromSet :: (Key -> a) -> IntSet.IntSet -> IntMap a
944 fromSet _ IntSet.Nil = Nil
945 fromSet f (IntSet.Bin p m l r) = Bin p m (fromSet f l) (fromSet f r)
946 fromSet f (IntSet.Tip kx bm) = buildTree f kx bm (IntSet.suffixBitMask + 1)
947 where -- This is slightly complicated, as we to convert the dense
948 -- representation of IntSet into tree representation of IntMap.
949 --
950 -- We are given a nonzero bit mask 'bmask' of 'bits' bits with prefix 'prefix'.
951 -- We split bmask into halves corresponding to left and right subtree.
952 -- If they are both nonempty, we create a Bin node, otherwise exactly
953 -- one of them is nonempty and we construct the IntMap from that half.
954 buildTree g !prefix !bmask bits = case bits of
955 0 -> Tip prefix $! g prefix
956 _ -> case intFromNat ((natFromInt bits) `shiftRL` 1) of
957 bits2 | bmask .&. ((1 `shiftLL` bits2) - 1) == 0 ->
958 buildTree g (prefix + bits2) (bmask `shiftRL` bits2) bits2
959 | (bmask `shiftRL` bits2) .&. ((1 `shiftLL` bits2) - 1) == 0 ->
960 buildTree g prefix bmask bits2
961 | otherwise ->
962 Bin prefix bits2 (buildTree g prefix bmask bits2) (buildTree g (prefix + bits2) (bmask `shiftRL` bits2) bits2)
963
964 {--------------------------------------------------------------------
965 Lists
966 --------------------------------------------------------------------}
967 -- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs.
968 --
969 -- > fromList [] == empty
970 -- > fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
971 -- > fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
972
973 fromList :: [(Key,a)] -> IntMap a
974 fromList xs
975 = foldlStrict ins empty xs
976 where
977 ins t (k,x) = insert k x t
978
979 -- | /O(n*min(n,W))/. Create a map from a list of key\/value pairs with a combining function. See also 'fromAscListWith'.
980 --
981 -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
982 -- > fromListWith (++) [] == empty
983
984 fromListWith :: (a -> a -> a) -> [(Key,a)] -> IntMap a
985 fromListWith f xs
986 = fromListWithKey (\_ x y -> f x y) xs
987
988 -- | /O(n*min(n,W))/. Build a map from a list of key\/value pairs with a combining function. See also fromAscListWithKey'.
989 --
990 -- > fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
991 -- > fromListWith (++) [] == empty
992
993 fromListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
994 fromListWithKey f xs
995 = foldlStrict ins empty xs
996 where
997 ins t (k,x) = insertWithKey f k x t
998
999 -- | /O(n)/. Build a map from a list of key\/value pairs where
1000 -- the keys are in ascending order.
1001 --
1002 -- > fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
1003 -- > fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
1004
1005 fromAscList :: [(Key,a)] -> IntMap a
1006 fromAscList xs
1007 = fromAscListWithKey (\_ x _ -> x) xs
1008
1009 -- | /O(n)/. Build a map from a list of key\/value pairs where
1010 -- the keys are in ascending order, with a combining function on equal keys.
1011 -- /The precondition (input list is ascending) is not checked./
1012 --
1013 -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
1014
1015 fromAscListWith :: (a -> a -> a) -> [(Key,a)] -> IntMap a
1016 fromAscListWith f xs
1017 = fromAscListWithKey (\_ x y -> f x y) xs
1018
1019 -- | /O(n)/. Build a map from a list of key\/value pairs where
1020 -- the keys are in ascending order, with a combining function on equal keys.
1021 -- /The precondition (input list is ascending) is not checked./
1022 --
1023 -- > fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
1024
1025 fromAscListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
1026 fromAscListWithKey _ [] = Nil
1027 fromAscListWithKey f (x0 : xs0) = fromDistinctAscList (combineEq x0 xs0)
1028 where
1029 -- [combineEq f xs] combines equal elements with function [f] in an ordered list [xs]
1030 combineEq z [] = [z]
1031 combineEq z@(kz,zz) (x@(kx,xx):xs)
1032 | kx==kz = let !yy = f kx xx zz in combineEq (kx,yy) xs
1033 | otherwise = z:combineEq x xs
1034
1035 -- | /O(n)/. Build a map from a list of key\/value pairs where
1036 -- the keys are in ascending order and all distinct.
1037 -- /The precondition (input list is strictly ascending) is not checked./
1038 --
1039 -- > fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
1040
1041 fromDistinctAscList :: [(Key,a)] -> IntMap a
1042 fromDistinctAscList [] = Nil
1043 fromDistinctAscList (z0 : zs0) = work z0 zs0 Nada
1044 where
1045 work (kx,!vx) [] stk = finish kx (Tip kx vx) stk
1046 work (kx,!vx) (z@(kz,_):zs) stk = reduce z zs (branchMask kx kz) kx (Tip kx vx) stk
1047
1048 reduce :: (Key,a) -> [(Key,a)] -> Mask -> Prefix -> IntMap a -> Stack a -> IntMap a
1049 reduce z zs _ px tx Nada = work z zs (Push px tx Nada)
1050 reduce z zs m px tx stk@(Push py ty stk') =
1051 let mxy = branchMask px py
1052 pxy = mask px mxy
1053 in if shorter m mxy
1054 then reduce z zs m pxy (Bin pxy mxy ty tx) stk'
1055 else work z zs (Push px tx stk)
1056
1057 finish _ t Nada = t
1058 finish px tx (Push py ty stk) = finish p (link py ty px tx) stk
1059 where m = branchMask px py
1060 p = mask px m
1061
1062 data Stack a = Push {-# UNPACK #-} !Prefix !(IntMap a) !(Stack a) | Nada