Lazy.hs

{-|
    @'LazyPatricia' a@ is a spine-lazy big-endian PATRICIA tree, a compressed
    trie with a radix of 2, using 'Word's as keys.

    == Laziness

    Evaluating any particular entry in the tree to WHNF forces the evaluation
    of the part of the spine leading up to that entry to normal form.

    == Performance

    Each function's time complexity is provided in the documentation.

    Laziness-amortized functions specify two time complexities:
    time to construct the return value (denoted with a \(\texttt{+}\)) and time to
    fully apply the function to the tree.

    \(n\) refers to the number of evaluated entries in the resulting tree.
    Parts of the tree are denoted using subscripts: \(n_L\) refers to the left side,
    \(n_R\) to the right side, \(n_I\) to a range (interval), and
    \(n_M\) to entries collected with the use of a 'Monoid'.

    \(W\) is the size of 'Word' in bits, i.e. @'Data.Bits.finiteBitSize' (0 :: 'Word')@.

    == Implementation

    See the implementation section in "Data.Patricia.Word.Strict".
 -}

module Data.Patricia.Word.Lazy
  ( LazyPatricia
  , Patricia

    -- * Construct
  , empty
  , singleton

    -- ** Convert
  , toStrict

    -- * Single-key
    -- ** Lookup
  , Data.Patricia.Word.Lazy.Internal.lookup
  , Data.Patricia.Word.Lazy.Internal.find
  , member

    -- ** Insert
  , insert
  , insertWith

    -- ** Map
  , adjust

    -- ** Delete
  , delete

    -- ** Update
  , update

  , alter

    -- ** Take
  , splitLookup

    -- * Directional
    -- ** Lookup
  , Lookup (..)
  , lookupL
  , lookupR

    -- ** Map
    -- | === Left
  , adjustL
  , adjustLWithKey

    -- | === Right
  , adjustR
  , adjustRWithKey

    -- ** Delete
  , deleteL
  , deleteR

    -- ** Update
    -- | === Left
  , updateL
  , updateLWithKey

    -- | === Right
  , updateR
  , updateRWithKey

    -- ** Take
    -- | === Left
  , takeL
  , splitL

    -- | === Right
  , takeR
  , splitR

    -- * Range
  , Range (Range)

    -- ** Map
  , adjustRange
  , adjustRangeWithKey

    -- ** Delete
  , deleteRange

    -- ** Update
  , updateRange
  , updateRangeWithKey

    -- ** Take
  , takeRange

    -- * Edges

    -- ** Lookup
    -- | === Min
  , lookupMin
  , lookupMinWithKey

    -- | === Max
  , lookupMax
  , lookupMaxWithKey

    -- ** Map
    -- | === Min
  , adjustMin
  , adjustMinWithKey

    -- | === Max
  , adjustMax
  , adjustMaxWithKey

    -- ** Delete
  , deleteMin
  , deleteMax

    -- ** Update
    -- | === Min
  , updateMin
  , updateMinWithKey

    -- | === Max
  , updateMax
  , updateMaxWithKey

    -- ** View
    -- | === Min
  , ViewL (..)
  , minView

    -- | === Max
  , ViewR (..)
  , maxView

    -- * Full tree
    -- ** Size
  , Data.Patricia.Word.Lazy.Internal.null
  , size

    -- ** Map
  , Data.Patricia.Word.Lazy.Internal.map
  , mapWithKey

    -- ** Fold
    -- | === Left-to-right
  , Data.Patricia.Word.Lazy.Internal.foldl
  , Data.Patricia.Word.Lazy.Internal.foldl'
  , foldlWithKey
  , foldlWithKey'

    -- | === Right-to-left
  , Data.Patricia.Word.Lazy.Internal.foldr
  , Data.Patricia.Word.Lazy.Internal.foldr'
  , foldrWithKey
  , foldrWithKey'

    -- | === Monoid
  , Data.Patricia.Word.Lazy.Internal.foldMap
  , foldMapWithKey

    -- ** Traverse
  , Data.Patricia.Word.Lazy.Internal.traverse
  , traverseWithKey

    -- ** Filter
    -- | === One side
  , Data.Patricia.Word.Lazy.Internal.filter
  , filterWithKey

  , mapMaybe
  , mapMaybeWithKey

    -- | === Both sides
  , partition
  , partitionWithKey

  , mapEither
  , mapEitherWithKey

    -- ** Comparison
  , PartialOrdering (..)
  , Data.Patricia.Word.Lazy.Internal.compare

    -- ** Union
  , union
  , unionL
  , unionWith
  , unionWithKey

    -- ** Difference
  , difference
  , differenceWith
  , differenceWithKey

    -- ** Intersection
  , disjoint
  , intersection
  , intersectionL
  , intersectionWith
  , intersectionWithKey

    -- ** Merge
    -- | See 'Data.Patricia.Word.Lazy.Unsafe.merge'.
  ) where

import           Data.Patricia.Word.Common
import           Data.Patricia.Word.Conversion
import           Data.Patricia.Word.Lazy.Internal
import           Radix.Common
import           Radix.Word.Common



-- | \(\mathcal{O}(1)\). Empty tree.
empty :: Patricia a
empty = Nil

-- | \(\mathcal{O}(1)\). Tree with a single entry.
singleton :: Word -> a -> Patricia a
singleton = Tip