Fix module references in the documentation.
[packages/containers.git] / Data / IntMap.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
3 {-# LANGUAGE Trustworthy #-}
4 #endif
5 -----------------------------------------------------------------------------
6 -- |
7 -- Module : Data.IntMap
8 -- Copyright : (c) Daan Leijen 2002
9 -- (c) Andriy Palamarchuk 2008
10 -- License : BSD-style
11 -- Maintainer : libraries@haskell.org
12 -- Stability : provisional
13 -- Portability : portable
14 --
15 -- An efficient implementation of maps from integer keys to values
16 -- (dictionaries).
17 --
18 -- This module re-exports the value lazy "Data.IntMap.Lazy" API, plus
19 -- several obsolete value strict functions. Please note that these functions
20 -- have different strictness properties than those in "Data.IntMap.Strict":
21 -- they only evaluate the result of the combining function. For example, the
22 -- default value to 'insertWith'' is only evaluated if the combining function
23 -- is called and uses it.
24 --
25 -- These modules are intended to be imported qualified, to avoid name
26 -- clashes with Prelude functions, e.g.
27 --
28 -- > import Data.IntMap (IntMap)
29 -- > import qualified Data.IntMap as IntMap
30 --
31 -- The implementation is based on /big-endian patricia trees/. This data
32 -- structure performs especially well on binary operations like 'union'
33 -- and 'intersection'. However, my benchmarks show that it is also
34 -- (much) faster on insertions and deletions when compared to a generic
35 -- size-balanced map implementation (see "Data.Map").
36 --
37 -- * Chris Okasaki and Andy Gill, \"/Fast Mergeable Integer Maps/\",
38 -- Workshop on ML, September 1998, pages 77-86,
39 -- <http://citeseer.ist.psu.edu/okasaki98fast.html>
40 --
41 -- * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
42 -- Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
43 -- October 1968, pages 514-534.
44 --
45 -- Operation comments contain the operation time complexity in
46 -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
47 -- Many operations have a worst-case complexity of /O(min(n,W))/.
48 -- This means that the operation can become linear in the number of
49 -- elements with a maximum of /W/ -- the number of bits in an 'Int'
50 -- (32 or 64).
51 -----------------------------------------------------------------------------
52
53 module Data.IntMap
54 ( module Data.IntMap.Lazy
55 , insertWith'
56 , insertWithKey'
57 , fold
58 , foldWithKey
59 ) where
60
61 import Prelude hiding (lookup,map,filter,foldr,foldl,null)
62 import Data.IntMap.Base (IntMap(..), join, nomatch, zero)
63 import Data.IntMap.Lazy
64
65 -- | /Deprecated./ As of version 0.5, replaced by
66 -- 'Data.IntMap.Strict.insertWith'.
67 --
68 -- /O(log n)/. Same as 'insertWith', but the result of the combining function
69 -- is evaluated to WHNF before inserted to the map. In contrast to
70 -- 'Data.IntMap.Strict.insertWith', the value argument is not evaluted when not
71 -- needed by the combining function.
72
73 insertWith' :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
74 -- We do not reuse Data.IntMap.Strict.insertWith, because it is stricter -- it
75 -- forces evaluation of the given value.
76 insertWith' f k x t
77 = insertWithKey' (\_ x' y' -> f x' y') k x t
78
79 -- | /Deprecated./ As of version 0.5, replaced by
80 -- 'Data.IntMap.Strict.insertWithKey'.
81 --
82 -- /O(log n)/. Same as 'insertWithKey', but the result of the combining
83 -- function is evaluated to WHNF before inserted to the map. In contrast to
84 -- 'Data.IntMap.Strict.insertWithKey', the value argument is not evaluted when
85 -- not needed by the combining function.
86
87 insertWithKey' :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
88 -- We do not reuse Data.IntMap.Strict.insertWithKey, because it is stricter -- it
89 -- forces evaluation of the given value.
90 insertWithKey' f k x t = k `seq`
91 case t of
92 Bin p m l r
93 | nomatch k p m -> join k (Tip k x) p t
94 | zero k m -> Bin p m (insertWithKey' f k x l) r
95 | otherwise -> Bin p m l (insertWithKey' f k x r)
96 Tip ky y
97 | k==ky -> Tip k $! f k x y
98 | otherwise -> join k (Tip k x) ky t
99 Nil -> Tip k x
100
101 -- | /Deprecated./ As of version 0.5, replaced by 'foldr'.
102 --
103 -- /O(n)/. Fold the values in the map using the given
104 -- right-associative binary operator. This function is an equivalent
105 -- of 'foldr' and is present for compatibility only.
106 fold :: (a -> b -> b) -> b -> IntMap a -> b
107 fold = foldr
108 {-# INLINE fold #-}
109
110 -- | /Deprecated./ As of version 0.5, replaced by 'foldrWithKey'.
111 --
112 -- /O(n)/. Fold the keys and values in the map using the given
113 -- right-associative binary operator. This function is an equivalent
114 -- of 'foldrWithKey' and is present for compatibility only.
115 foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b
116 foldWithKey = foldrWithKey
117 {-# INLINE foldWithKey #-}