content: {-# LANGUAGE CPP #-}
  #if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
  {-# LANGUAGE Trustworthy #-}
  #endif
  -----------------------------------------------------------------------------
  -- |
  -- Module      :  Data.IntMap.Lazy
  -- Copyright   :  (c) Daan Leijen 2002
  --                (c) Andriy Palamarchuk 2008
  -- License     :  BSD-style
  -- Maintainer  :  libraries@haskell.org
  -- Stability   :  provisional
  -- Portability :  portable
  --
  -- An efficient implementation of maps from integer keys to values
  -- (dictionaries).
  --
  -- API of this module is strict in the keys, but lazy in the values.
  -- If you need value-strict maps, use 'Data.IntMap.Strict' instead.
  -- The 'IntMap' type itself is shared between the lazy and strict modules,
  -- meaning that the same 'IntMap' value can be passed to functions in
  -- both modules (although that is rarely needed).
  --
  -- These modules are intended to be imported qualified, to avoid name
  -- clashes with Prelude functions, e.g.
  --
  -- >  import Data.IntMap.Lazy (IntMap)
  -- >  import qualified Data.IntMap.Lazy as IntMap
  --
  -- The implementation is based on /big-endian patricia trees/.  This data
  -- structure performs especially well on binary operations like 'union'
  -- and 'intersection'.  However, my benchmarks show that it is also
  -- (much) faster on insertions and deletions when compared to a generic
  -- size-balanced map implementation (see "Data.Map").
  --
  --    * Chris Okasaki and Andy Gill,  \"/Fast Mergeable Integer Maps/\",
  --      Workshop on ML, September 1998, pages 77-86,
  --      <http://citeseer.ist.psu.edu/okasaki98fast.html>
  --
  --    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve
  --      Information Coded In Alphanumeric/\", Journal of the ACM, 15(4),
  --      October 1968, pages 514-534.
  --
  -- Operation comments contain the operation time complexity in
  -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
  -- Many operations have a worst-case complexity of /O(min(n,W))/.
  -- This means that the operation can become linear in the number of
  -- elements with a maximum of /W/ -- the number of bits in an 'Int'
  -- (32 or 64).
  -----------------------------------------------------------------------------
  
  module Data.IntMap.Lazy (
              -- * Strictness properties
              -- $strictness
  
              -- * Map type
  #if !defined(TESTING)
                IntMap, Key          -- instance Eq,Show
  #else
                IntMap(..), Key          -- instance Eq,Show
  #endif
  
              -- * Operators
              , (!), (\\)
  
              -- * Query
              , IM.null
              , size
              , member
              , notMember
              , IM.lookup
              , findWithDefault
              , lookupLT
              , lookupGT
              , lookupLE
              , lookupGE
  
              -- * Construction
              , empty
              , singleton
  
              -- ** Insertion
              , insert
              , insertWith
              , insertWithKey
              , insertLookupWithKey
  
              -- ** Delete\/Update
              , delete
              , adjust
              , adjustWithKey
              , update
              , updateWithKey
              , updateLookupWithKey
              , alter
  
              -- * Combine
  
              -- ** Union
              , union
              , unionWith
              , unionWithKey
              , unions
              , unionsWith
  
              -- ** Difference
              , difference
              , differenceWith
              , differenceWithKey
  
              -- ** Intersection
              , intersection
              , intersectionWith
              , intersectionWithKey
  
              -- ** Universal combining function
              , mergeWithKey
  
              -- * Traversal
              -- ** Map
              , IM.map
              , mapWithKey
              , traverseWithKey
              , mapAccum
              , mapAccumWithKey
              , mapAccumRWithKey
              , mapKeys
              , mapKeysWith
              , mapKeysMonotonic
  
              -- * Folds
              , IM.foldr
              , IM.foldl
              , foldrWithKey
              , foldlWithKey
              -- ** Strict folds
              , foldr'
              , foldl'
              , foldrWithKey'
              , foldlWithKey'
  
              -- * Conversion
              , elems
              , keys
              , assocs
              , keysSet
              , fromSet
  
              -- ** Lists
              , toList
              , fromList
              , fromListWith
              , fromListWithKey
  
              -- ** Ordered lists
              , toAscList
              , toDescList
              , fromAscList
              , fromAscListWith
              , fromAscListWithKey
              , fromDistinctAscList
  
              -- * Filter
              , IM.filter
              , filterWithKey
              , partition
              , partitionWithKey
  
              , mapMaybe
              , mapMaybeWithKey
              , mapEither
              , mapEitherWithKey
  
              , split
              , splitLookup
  
              -- * Submap
              , isSubmapOf, isSubmapOfBy
              , isProperSubmapOf, isProperSubmapOfBy
  
              -- * Min\/Max
              , findMin
              , findMax
              , deleteMin
              , deleteMax
              , deleteFindMin
              , deleteFindMax
              , updateMin
              , updateMax
              , updateMinWithKey
              , updateMaxWithKey
              , minView
              , maxView
              , minViewWithKey
              , maxViewWithKey
  
              -- * Debugging
              , showTree
              , showTreeWith
              ) where
  
  import Data.IntMap.Base as IM
  
  -- $strictness
  --
  -- This module satisfies the following strictness property:
  --
  -- * Key arguments are evaluated to WHNF
  --
  -- Here are some examples that illustrate the property:
  --
  -- > insertWith (\ new old -> old) undefined v m  ==  undefined
  -- > insertWith (\ new old -> old) k undefined m  ==  OK
  -- > delete undefined m  ==  undefined
  