Data/IntMap/Lazy.hs

{-# 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