Data.Patricia.Word.Lazy.Unsafe

Data structure internals, helper operations and unsafe functions.

Documentation

data Patricia a

Spine-lazy PATRICIA tree.

Constructors

Bin

Fields

• !Prefix
• (Patricia a)

  Masked bit is 0.

• (Patricia a)

  Masked bit is 1.

Tip !Key a

Nil

Invariant: only allowed as the root of the tree.

Instances

Foldable Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

fold :: Monoid m => Patricia m -> m

foldMap :: Monoid m => (a -> m) -> Patricia a -> m

foldMap' :: Monoid m => (a -> m) -> Patricia a -> m

foldr :: (a -> b -> b) -> b -> Patricia a -> b

foldr' :: (a -> b -> b) -> b -> Patricia a -> b

foldl :: (b -> a -> b) -> b -> Patricia a -> b

foldl' :: (b -> a -> b) -> b -> Patricia a -> b

foldr1 :: (a -> a -> a) -> Patricia a -> a

foldl1 :: (a -> a -> a) -> Patricia a -> a

toList :: Patricia a -> [a]

null :: Patricia a -> Bool

length :: Patricia a -> Int

elem :: Eq a => a -> Patricia a -> Bool

maximum :: Ord a => Patricia a -> a

minimum :: Ord a => Patricia a -> a

sum :: Num a => Patricia a -> a

product :: Num a => Patricia a -> a

Eq1 Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

liftEq :: (a -> b -> Bool) -> Patricia a -> Patricia b -> Bool

Read1 Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Patricia a)

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Patricia a]

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Patricia a)

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Patricia a]

Show1 Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Patricia a -> ShowS

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Patricia a] -> ShowS

Traversable Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

traverse :: Applicative f => (a -> f b) -> Patricia a -> f (Patricia b)

sequenceA :: Applicative f => Patricia (f a) -> f (Patricia a)

mapM :: Monad m => (a -> m b) -> Patricia a -> m (Patricia b)

sequence :: Monad m => Patricia (m a) -> m (Patricia a)

Functor Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

fmap :: (a -> b) -> Patricia a -> Patricia b

(<$) :: a -> Patricia b -> Patricia a

NFData1 Patricia

Defined in Data.Patricia.Word.Lazy.Internal

Methods

liftRnf :: (a -> ()) -> Patricia a -> ()

Lift a => Lift (Patricia a :: Type)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

lift :: Quote m => Patricia a -> m Exp

liftTyped :: forall (m :: Type -> Type). Quote m => Patricia a -> Code m (Patricia a)

Read a => Read (Patricia a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

readsPrec :: Int -> ReadS (Patricia a)

readList :: ReadS [Patricia a]

readPrec :: ReadPrec (Patricia a)

readListPrec :: ReadPrec [Patricia a]

Show a => Show (Patricia a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

showsPrec :: Int -> Patricia a -> ShowS

show :: Patricia a -> String

showList :: [Patricia a] -> ShowS

NFData a => NFData (Patricia a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

rnf :: Patricia a -> ()

Eq a => Eq (Patricia a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

(==) :: Patricia a -> Patricia a -> Bool

(/=) :: Patricia a -> Patricia a -> Bool

Bit operations

type Prefix = Word

Part of the Key from the largest bit to the Mask bit, plus the Mask bit.

type Key = Word

Key as stored in the data structure.

Compare

beyond :: Prefix -> Key -> Bool

\(\mathcal{O}(1)\). Whether the key does not match the prefix.

upper :: Prefix -> Key

\(\mathcal{O}(1)\). Largest key that can reside under this prefix.

lower :: Prefix -> Key

\(\mathcal{O}(1)\). Smallest key that can reside under this prefix.

Create

type Mask = Word

Masking bit.

zeroBit :: Key -> Mask -> Bool

\(\mathcal{O}(1)\). Get the state of the masked bit from the Key.

mask :: Key -> Mask -> Word

\(\mathcal{O}(1)\). Trim the Key down to the masking bit.

branchingBit :: Prefix -> Prefix -> Mask

\(\mathcal{O}(1)\). Find the bit two Prefixes disagree on.

Note that using this function on two equal integers yields 1 << (-1), which results in undefined behavior.

Exceptions

data MalformedTree

Exception thrown by functions that need to return a value, but instead find an invariant-breaking empty node.

Constructors

MalformedTree

Fields

• String

  Module name

• String

  Function name

Instances

Exception MalformedTree

Defined in Radix.Exception

Methods

toException :: MalformedTree -> SomeException

fromException :: SomeException -> Maybe MalformedTree

displayException :: MalformedTree -> String

Show MalformedTree

Defined in Radix.Exception

Methods

showsPrec :: Int -> MalformedTree -> ShowS

show :: MalformedTree -> String

showList :: [MalformedTree] -> ShowS

Range

data Range

A closed interval between two keys.

Constructors

UnsafeRange

Invariant: \(k_L \le k_R\).

Fields

• !Key

  \(k_L\)

• !Key

  \(k_R\)

Bundled Patterns

pattern Range

Reorders endpoints to fit mathematical notation: \([12, 3]\) will be converted to \([3, 12]\).

Pattern matching guarantees \(k_1 \le k_2\).

Fields

• :: Word

  \(k_1\)

• -> Word

  \(k_2\)

• -> Range

Instances

Show Range

Defined in Radix.Word.Common

Methods

showsPrec :: Int -> Range -> ShowS

show :: Range -> String

showList :: [Range] -> ShowS

Map

unsafeAdjustRange

Arguments

:: (a -> a)

-> Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W) + n_I)\). Apply a function to every value for which the key is in the given range.

\(k_R\) must be greater than \(k_L\).

unsafeAdjustRangeWithKey

Arguments

:: (Word -> a -> a)

-> Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W) + n_I)\). Apply a function to every value for which the key is in the given range.

\(k_R\) must be greater than \(k_L\).

Delete

unsafeDeleteRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W))\). Delete values for which keys are in the given range.

\(k_R\) must be greater than \(k_L\).

Update

unsafeUpdateRange

Arguments

:: (a -> Maybe a)

-> Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W) + n_I)\). Update every value for which the key is in the given range.

\(k_R\) must be greater than \(k_L\).

unsafeUpdateRangeWithKey

Arguments

:: (Word -> a -> Maybe a)

-> Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W) + n_I)\). Update every value for which the key is in the given range.

\(k_R\) must be greater than \(k_L\).

Take

unsafeTakeRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> Patricia a

-> Patricia a

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(\min(n,W))\). Take values for which keys are in the given range.

\(k_R\) must be greater than \(k_L\).

Edges

Lookup

data Lookup a

Key together with the value.

Constructors

Lookup !Word a

Instances

Show a => Show (Lookup a)

Defined in Data.Patricia.Word.Common

Methods

showsPrec :: Int -> Lookup a -> ShowS

show :: Lookup a -> String

showList :: [Lookup a] -> ShowS

Min

unsafeLookupMin :: Patricia a -> (# a #)

\(\mathcal{O}(\min(n,W))\). Look up a value at the leftmost key in the tree.

Throws MalformedTree if the tree is empty.

unsafeLookupMinWithKey :: Patricia a -> Lookup a

\(\mathcal{O}(\min(n,W))\). Look up a value at the leftmost key in the tree.

Throws MalformedTree if the tree is empty.

Max

unsafeLookupMax :: Patricia a -> (# a #)

\(\mathcal{O}(\min(n,W))\). Look up a value at the rightmost key in the tree.

Throws MalformedTree if the tree is empty.

unsafeLookupMaxWithKey :: Patricia a -> Lookup a

\(\mathcal{O}(\min(n,W))\). Look up a value at the rightmost key in the tree.

Throws MalformedTree if the tree is empty.

View

Min

data ViewL a

The leftmost value with its key and the rest of the tree.

Constructors

ViewL !(Lookup a) !(Patricia a)

Instances

Show a => Show (ViewL a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

showsPrec :: Int -> ViewL a -> ShowS

show :: ViewL a -> String

showList :: [ViewL a] -> ShowS

unsafeMinView :: Patricia a -> ViewL a

\(\mathcal{O}(\min(n,W))\). Look up the leftmost value and return it alongside the tree without it.

Throws MalformedTree if the tree is empty.

Max

data ViewR a

The rightmost value with its key and the rest of the tree.

Constructors

ViewR !(Patricia a) !(Lookup a)

Instances

Show a => Show (ViewR a)

Defined in Data.Patricia.Word.Lazy.Internal

Methods

showsPrec :: Int -> ViewR a -> ShowS

show :: ViewR a -> String

showList :: [ViewR a] -> ShowS

unsafeMaxView :: Patricia a -> ViewR a

\(\mathcal{O}(\min(n,W))\). Look up the rightmost value and return it alongside the tree without it.

Throws MalformedTree if the tree is empty.

Full-tree

Merge

merge

Arguments

:: (Key -> a -> b -> Patricia c)

Collision

-> (Key -> a -> Patricia c)

Single left value

-> (Prefix -> Patricia a -> Patricia a -> Patricia c)

Left subtree

-> (Key -> b -> Patricia c)

Single right value

-> (Prefix -> Patricia b -> Patricia b -> Patricia c)

Right subtree

-> Patricia a

-> Patricia b

-> Patricia c

\(\mathcal{O}(1)\texttt{+}, \mathcal{O}(n_A + n_B)\). General merge of two trees.

Collision and single value functions must return either Tip with the respective key, or Nil.

Subtree argument functions may return any tree, however the shape of said tree must be compatible with the prefix passed to the function.

This functions inlines when all argument functions are provided.