{-| @'StrictPatricia' a@ is a spine-strict big-endian PATRICIA tree, a compressed binary trie, using 'Word's as keys. == Laziness Evaluating the root of the tree (i.e. @(_ :: 'StrictPatricia' a)@) to weak head normal form evaluates the entire spine of the tree to normal form. Functions do not perform any additional evaluations unless their documentation directly specifies so. == Performance Each function's time complexity is provided in the documentation. \(n\) refers to the total number of entries in the 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 Description of the PATRICIA tree and some of the algorithms implemented can be found within the following paper: * Chris Okasaki and Andy Gill, "/Fast Mergeable Integer Maps/", Workshop on ML, September 1998, pages 77-86, -} module Data.Patricia.Word.Strict ( StrictPatricia , Patricia -- * Construct , empty , singleton -- ** Convert , toLazy -- * Single-key -- ** Lookup , Data.Patricia.Word.Strict.Internal.lookup , Data.Patricia.Word.Strict.Internal.find , member -- *** Dirty -- -- | Dirty lookups omit intermediate checks and are thus faster for keys -- that are in the tree, at the cost of being slower for keys not in the tree. , dirtyLookup , dirtyFind , dirtyMember -- ** Insert , insert , insertWith , insertWith' -- ** Map , adjust , adjust' -- ** Delete , delete -- ** Update , update , alter -- ** Take , SplitLookup (..) , splitLookup -- * Directional -- ** Lookup , Lookup (..) , lookupL , lookupR -- ** Map -- | === Left , adjustL , adjustL' , adjustLWithKey , adjustLWithKey' -- | === Right , adjustR , adjustR' , adjustRWithKey , adjustRWithKey' -- ** Delete , deleteL , deleteR -- ** Update -- | === Left , updateL , updateLWithKey -- | === Right , updateR , updateRWithKey -- ** Take , Split (..) -- | === Left , takeL , splitL -- | === Right , takeR , splitR -- * Range , Range (Range) -- ** Map , adjustRange , adjustRange' , adjustRangeWithKey , adjustRangeWithKey' -- ** Delete , deleteRange -- ** Update , updateRange , updateRangeWithKey -- ** Take , takeRange -- * Edges -- ** Lookup -- | === Min , lookupMin , lookupMinWithKey -- | === Max , lookupMax , lookupMaxWithKey -- ** Map -- | === Min , adjustMin , adjustMin' , adjustMinWithKey , adjustMinWithKey' -- | === Max , adjustMax , adjustMax' , adjustMaxWithKey , adjustMaxWithKey' -- ** Delete , deleteMin , deleteMax -- ** Update -- | === Min , updateMin , updateMinWithKey -- | === Max , updateMax , updateMaxWithKey -- ** View -- | === Min , ViewL (..) , minView -- | === Max , ViewR (..) , maxView -- * Full tree -- ** Size , Data.Patricia.Word.Strict.Internal.null , size -- ** Map , Data.Patricia.Word.Strict.Internal.map , map' , mapWithKey , mapWithKey' -- ** Fold -- | === Left-to-right , Data.Patricia.Word.Strict.Internal.foldl , Data.Patricia.Word.Strict.Internal.foldl' , foldlWithKey , foldlWithKey' -- | === Right-to-left , Data.Patricia.Word.Strict.Internal.foldr , Data.Patricia.Word.Strict.Internal.foldr' , foldrWithKey , foldrWithKey' -- | === Monoid , Data.Patricia.Word.Strict.Internal.foldMap , foldMapWithKey -- ** Traverse , Data.Patricia.Word.Strict.Internal.traverse , traverseWithKey -- ** Filter -- | === One side , Data.Patricia.Word.Strict.Internal.filter , filterWithKey , mapMaybe , mapMaybeWithKey -- | === Both sides , partition , partitionWithKey , mapEither , mapEitherWithKey -- ** Comparison , PartialOrdering (..) , Data.Patricia.Word.Strict.Internal.compare -- ** Union , union , unionL , unionWith' , unionWithKey' -- ** Difference , difference , differenceWith , differenceWithKey -- ** Intersection , disjoint , intersection , intersectionL , intersectionWith' , intersectionWithKey' -- ** Merge -- | See 'Data.Patricia.Word.Strict.Unsafe.merge'. ) where import Data.Patricia.Word.Common import Data.Patricia.Word.Conversion import Data.Patricia.Word.Strict.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