{-# LANGUAGE CPP #-}
#if defined(__GLASGOW_HASKELL__)
{-# LANGUAGE Safe #-}
#endif

#include "containers.h"
------------------------------------------------------------------------------- |-- Module : Data.Map.Strict-- Copyright : (c) Daan Leijen 2002-- (c) Andriy Palamarchuk 2008-- License : BSD-style-- Maintainer : libraries@haskell.org-- Portability : portable------ = Finite Maps (strict interface)---- The @'Map' k v@ type represents a finite map (sometimes called a dictionary)-- from keys of type @k@ to values of type @v@.---- Each function in this module is careful to force values before installing-- them in a 'Map'. This is usually more efficient when laziness is not-- necessary. When laziness /is/ required, use the functions in "Data.Map.Lazy".---- In particular, the functions in this module obey the following law:---- - If all values stored in all maps in the arguments are in WHNF, then all-- values stored in all maps in the results will be in WHNF once those maps-- are evaluated.---- When deciding if this is the correct data structure to use, consider:---- * If you are using 'Prelude.Int' keys, you will get much better performance for-- most operations using "Data.IntMap.Strict".---- * If you don't care about ordering, consider use @Data.HashMap.Strict@ from the-- <https://hackage.haskell.org/package/unordered-containers unordered-containers>-- package instead.---- For a walkthrough of the most commonly used functions see the-- <https://haskell-containers.readthedocs.io/en/latest/map.html maps introduction>.---- This module is intended to be imported qualified, to avoid name clashes with-- Prelude functions, e.g.---- > import Data.Map.Strict (Map)-- > import qualified Data.Map.Strict as Map---- Note that the implementation is generally /left-biased/. Functions that take-- two maps as arguments and combine them, such as `union` and `intersection`,-- prefer the values in the first argument to those in the second.------ == Warning---- The size of a 'Map' must not exceed @maxBound::Int@. Violation of this-- condition is not detected and if the size limit is exceeded, its behaviour is-- undefined.---- The 'Map' type is shared between the lazy and strict modules, meaning that-- the same 'Map' value can be passed to functions in both modules. This means-- that the 'Data.Functor.Functor', 'Data.Traversable.Traversable' and-- 'Data.Data.Data' instances are the same as for the "Data.Map.Lazy" module, so-- if they are used the resulting maps may contain suspended values (thunks).------ == Implementation---- The implementation of 'Map' is based on /size balanced/ binary trees (or-- trees of /bounded balance/) as described by:---- * Stephen Adams, \"/Efficient sets—a balancing act/\",-- Journal of Functional Programming 3(4):553-562, October 1993,-- <https://doi.org/10.1017/S0956796800000885>,-- <https://groups.csail.mit.edu/mac/users/adams/BB/index.html>.-- * J. Nievergelt and E.M. Reingold,-- \"/Binary search trees of bounded balance/\",-- SIAM journal of computing 2(1), March 1973.-- <https://doi.org/10.1137/0202005>.-- * Yoichi Hirai and Kazuhiko Yamamoto,-- \"/Balancing weight-balanced trees/\",-- Journal of Functional Programming 21(3):287-307, 2011,-- <https://doi.org/10.1017/S0956796811000104>---- Bounds for 'union', 'intersection', and 'difference' are as given-- by---- * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,-- \"/Parallel Ordered Sets Using Join/\",-- <https://arxiv.org/abs/1602.02120v4>.------ == Performance information---- The time complexity is given for each operation in-- [big-O notation](http://en.wikipedia.org/wiki/Big_O_notation), with \(n\)-- referring to the number of entries in the map.---- Operations like 'lookup', 'insert', and 'delete' take \(O(\log n)\) time.---- Binary set operations like 'union' and 'intersection' take-- \(O\bigl(m \log\bigl(\frac{n}{m}+1\bigr)\bigr)\) time, where \(m\) and \(n\)-- are the sizes of the smaller and larger input maps respectively.---- Benchmarks comparing "Data.Map.Strict" with other dictionary implementations-- can be found at https://github.com/haskell-perf/dictionaries.--------------------------------------------------------------------------------- See the notes at the beginning of Data.Map.Internal.moduleData.Map.Strict(-- * Map typeMap -- instance Eq,Show,Read-- * Construction,empty ,singleton ,fromSet ,fromArgSet -- ** From Unordered Lists,fromList ,fromListWith ,fromListWithKey -- ** From Ascending Lists,fromAscList ,fromAscListWith ,fromAscListWithKey ,fromDistinctAscList -- ** From Descending Lists,fromDescList ,fromDescListWith ,fromDescListWithKey ,fromDistinctDescList -- * Insertion,insert ,insertWith ,insertWithKey ,insertLookupWithKey -- * Deletion\/Update,delete ,adjust ,adjustWithKey ,update ,updateWithKey ,updateLookupWithKey ,alter ,alterF -- * Query-- ** Lookup,lookup ,(!?) ,(!) ,findWithDefault ,member ,notMember ,lookupLT ,lookupGT ,lookupLE ,lookupGE -- ** Size,null ,size -- * Combine-- ** Union,union ,unionWith ,unionWithKey ,unions ,unionsWith -- ** Difference,difference ,(\\) ,differenceWith ,differenceWithKey -- ** Intersection,intersection ,intersectionWith ,intersectionWithKey -- ** Symmetric difference,symmetricDifference -- ** Disjoint,disjoint -- ** Compose,compose -- ** General combining functions-- | See "Data.Map.Merge.Strict"-- ** Deprecated general combining function,mergeWithKey -- * Traversal-- ** Map,map ,mapWithKey ,traverseWithKey ,traverseMaybeWithKey ,mapAccum ,mapAccumWithKey ,mapAccumRWithKey ,mapKeys ,mapKeysWith ,mapKeysMonotonic -- * Folds,foldr ,foldl ,foldrWithKey ,foldlWithKey ,foldMapWithKey -- ** Strict folds,foldr' ,foldl' ,foldrWithKey' ,foldlWithKey' -- * Conversion,elems ,keys ,assocs ,keysSet ,argSet -- ** Lists,toList -- ** Ordered lists,toAscList ,toDescList -- * Filter,filter ,filterKeys ,filterWithKey ,restrictKeys ,withoutKeys ,partition ,partitionWithKey ,takeWhileAntitone ,dropWhileAntitone ,spanAntitone ,mapMaybe ,mapMaybeWithKey ,mapEither ,mapEitherWithKey ,split ,splitLookup ,splitRoot -- * Submap,isSubmapOf ,isSubmapOfBy ,isProperSubmapOf ,isProperSubmapOfBy -- * Indexed,lookupIndex ,findIndex ,elemAt ,updateAt ,deleteAt ,take ,drop ,splitAt -- * Min\/Max,lookupMin ,lookupMax ,findMin ,findMax ,deleteMin ,deleteMax ,deleteFindMin ,deleteFindMax ,updateMin ,updateMax ,updateMinWithKey ,updateMaxWithKey ,minView ,maxView ,minViewWithKey ,maxViewWithKey -- * Debugging,valid )whereimportData.Map.Strict.Internal importPrelude()