3330153163fc4365481aae443b1e13968beca389
[packages/containers.git] / Data / Map.hs
1 {-# LANGUAGE CPP #-}
2 #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
3 {-# LANGUAGE Safe #-}
4 #endif
5
6 #ifdef __GLASGOW_HASKELL__
7 {-# LANGUAGE DataKinds, FlexibleContexts #-}
8 #endif
9 #if __GLASGOW_HASKELL__ >= 800
10 {-# LANGUAGE MonoLocalBinds #-}
11 #endif
12
13 #include "containers.h"
14
15 -----------------------------------------------------------------------------
16 -- |
17 -- Module : Data.Map
18 -- Copyright : (c) Daan Leijen 2002
19 -- (c) Andriy Palamarchuk 2008
20 -- License : BSD-style
21 -- Maintainer : libraries@haskell.org
22 -- Portability : portable
23 --
24 -- /Note:/ You should use "Data.Map.Strict" instead of this module if:
25 --
26 -- * You will eventually need all the values stored.
27 --
28 -- * The stored values don't represent large virtual data structures
29 -- to be lazily computed.
30 --
31 -- An efficient implementation of ordered maps from keys to values
32 -- (dictionaries).
33 --
34 -- These modules are intended to be imported qualified, to avoid name
35 -- clashes with Prelude functions, e.g.
36 --
37 -- > import qualified Data.Map as Map
38 --
39 -- The implementation of 'Map' is based on /size balanced/ binary trees (or
40 -- trees of /bounded balance/) as described by:
41 --
42 -- * Stephen Adams, \"/Efficient sets: a balancing act/\",
43 -- Journal of Functional Programming 3(4):553-562, October 1993,
44 -- <http://www.swiss.ai.mit.edu/~adams/BB/>.
45 -- * J. Nievergelt and E.M. Reingold,
46 -- \"/Binary search trees of bounded balance/\",
47 -- SIAM journal of computing 2(1), March 1973.
48 --
49 -- Bounds for 'union', 'intersection', and 'difference' are as given
50 -- by
51 --
52 -- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
53 -- \"/Just Join for Parallel Ordered Sets/\",
54 -- <https://arxiv.org/abs/1602.02120v3>.
55 --
56 -- Note that the implementation is /left-biased/ -- the elements of a
57 -- first argument are always preferred to the second, for example in
58 -- 'union' or 'insert'.
59 --
60 -- /Warning/: The size of the map must not exceed @maxBound::Int@. Violation of
61 -- this condition is not detected and if the size limit is exceeded, its
62 -- behaviour is undefined.
63 --
64 -- Operation comments contain the operation time complexity in
65 -- the Big-O notation (<http://en.wikipedia.org/wiki/Big_O_notation>).
66 -----------------------------------------------------------------------------
67
68 module Data.Map
69 ( module Data.Map.Lazy
70 #ifdef __GLASGOW_HASKELL__
71 , insertWith'
72 , insertWithKey'
73 , insertLookupWithKey'
74 , fold
75 , foldWithKey
76 #endif
77 ) where
78
79 import Data.Map.Lazy
80
81 #ifdef __GLASGOW_HASKELL__
82 import Utils.Containers.Internal.TypeError
83
84 -- | This function is being removed and is no longer usable.
85 -- Use 'Data.Map.Strict.insertWith'.
86 insertWith' :: Whoops "Data.Map.insertWith' is gone. Use Data.Map.Strict.insertWith."
87 => (a -> a -> a) -> k -> a -> Map k a -> Map k a
88 insertWith' _ _ _ _ = undefined
89
90 -- | This function is being removed and is no longer usable.
91 -- Use 'Data.Map.Strict.insertWithKey'.
92 insertWithKey' :: Whoops "Data.Map.insertWithKey' is gone. Use Data.Map.Strict.insertWithKey."
93 => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
94 insertWithKey' _ _ _ _ = undefined
95
96 -- | This function is being removed and is no longer usable.
97 -- Use 'Data.Map.Strict.insertLookupWithKey'.
98 insertLookupWithKey' :: Whoops "Data.Map.insertLookupWithKey' is gone. Use Data.Map.Strict.insertLookupWithKey."
99 => (k -> a -> a -> a) -> k -> a -> Map k a
100 -> (Maybe a, Map k a)
101 insertLookupWithKey' _ _ _ _ = undefined
102
103 -- | This function is being removed and is no longer usable.
104 -- Use 'Data.Map.Strict.foldr'.
105 fold :: Whoops "Data.Map.fold is gone. Use foldr."
106 => (a -> b -> b) -> b -> Map k a -> b
107 fold _ _ _ = undefined
108
109 -- | This function is being removed and is no longer usable.
110 -- Use 'foldrWithKey'.
111 foldWithKey :: Whoops "Data.Map.foldWithKey is gone. Use foldrWithKey."
112 => (k -> a -> b -> b) -> b -> Map k a -> b
113 foldWithKey _ _ _ = undefined
114 #endif