    {-# LANGUAGE CPP #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Data.Word64Map.Lazy
    -- Copyright   :  (c) Daan Leijen 2002
    --                (c) Andriy Palamarchuk 2008
    -- License     :  BSD-style
    -- Maintainer  :  libraries@haskell.org
    -- Portability :  portable
    --
    --
    -- = Finite Word64 Maps (lazy interface)
    --
    -- The @'Word64Map' v@ type represents a finite map (sometimes called a dictionary)
    -- from keys of type @Word64@ to values of type @v@.
    --
    -- The functions in "Data.Word64Map.Strict" are careful to force values before
    -- installing them in an 'Word64Map'. This is usually more efficient in cases where
    -- laziness is not essential. The functions in this module do not do so.
    --
    -- 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:
    --
    -- > import Data.Word64Map.Lazy (Word64Map)
    -- > import qualified Data.Word64Map.Lazy as Word64Map
    --
    -- 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.
    --
    --
    -- == Detailed performance information
    --
    -- The amortized running time is given for each operation, with \(n\) referring to
    -- the number of entries in the map and \(W\) referring to the number of bits in
    -- an 'Word64' (64).
    --
    -- Benchmarks comparing "Data.Word64Map.Lazy" with other dictionary
    -- implementations can be found at https://github.com/haskell-perf/dictionaries.
    --
    --
    -- == Implementation
    --
    -- The implementation is based on /big-endian patricia trees/.  This data
    -- structure performs especially well on binary operations like 'union' and
    -- 'intersection'. Additionally, 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://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452>
    --
    --    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",
    --      Journal of the ACM, 15(4), October 1968, pages 514-534.
    --
    -----------------------------------------------------------------------------

    module GHC.Data.Word64Map.Lazy (
        -- * Map type
    #if !defined(TESTING)
        Word64Map, Key          -- instance Eq,Show
    #else
        Word64Map(..), Key          -- instance Eq,Show
    #endif

        -- * Construction
        , empty
        , singleton
        , fromSet

        -- ** From Unordered Lists
        , fromList
        , fromListWith
        , fromListWithKey

        -- ** From Ascending Lists
        , fromAscList
        , fromAscListWith
        , fromAscListWithKey
        , fromDistinctAscList

        -- * Insertion
        , insert
        , insertWith
        , insertWithKey
        , insertLookupWithKey

        -- * Deletion\/Update
        , delete
        , adjust
        , adjustWithKey
        , update
        , updateWithKey
        , updateLookupWithKey
        , alter
        , alterF

        -- * Query
        -- ** Lookup
        , WM.lookup
        , (!?)
        , (!)
        , findWithDefault
        , member
        , notMember
        , lookupLT
        , lookupGT
        , lookupLE
        , lookupGE

        -- ** Size
        , WM.null
        , size

        -- * Combine

        -- ** Union
        , union
        , unionWith
        , unionWithKey
        , unions
        , unionsWith

        -- ** Difference
        , difference
        , (\\)
        , differenceWith
        , differenceWithKey

        -- ** Intersection
        , intersection
        , intersectionWith
        , intersectionWithKey

        -- ** Disjoint
        , disjoint

        -- ** Compose
        , compose

        -- ** Universal combining function
        , mergeWithKey

        -- * Traversal
        -- ** Map
        , WM.map
        , mapWithKey
        , traverseWithKey
        , traverseMaybeWithKey
        , mapAccum
        , mapAccumWithKey
        , mapAccumRWithKey
        , mapKeys
        , mapKeysWith
        , mapKeysMonotonic

        -- * Folds
        , WM.foldr
        , WM.foldl
        , foldrWithKey
        , foldlWithKey
        , foldMapWithKey

        -- ** Strict folds
        , foldr'
        , foldl'
        , foldrWithKey'
        , foldlWithKey'

        -- * Conversion
        , elems
        , keys
        , assocs
        , keysSet

        -- ** Lists
        , toList

        -- ** Ordered lists
        , toAscList
        , toDescList

        -- * Filter
        , WM.filter
        , filterWithKey
        , restrictKeys
        , withoutKeys
        , partition
        , partitionWithKey

        , takeWhileAntitone
        , dropWhileAntitone
        , spanAntitone

        , mapMaybe
        , mapMaybeWithKey
        , mapEither
        , mapEitherWithKey

        , split
        , splitLookup
        , splitRoot

        -- * Submap
        , isSubmapOf, isSubmapOfBy
        , isProperSubmapOf, isProperSubmapOfBy

        -- * Min\/Max
        , lookupMin
        , lookupMax
        , findMin
        , findMax
        , deleteMin
        , deleteMax
        , deleteFindMin
        , deleteFindMax
        , updateMin
        , updateMax
        , updateMinWithKey
        , updateMaxWithKey
        , minView
        , maxView
        , minViewWithKey
        , maxViewWithKey
        ) where

    import GHC.Data.Word64Map.Internal as WM