Data.Zebra.Word.Unsafe

Data structure internals, helper operations and unsafe functions.

Implementation

The tree is structurally identical to the Patricia tree, holding Colors as values.

A key \(k\) in the tree denotes a right-open interval \([k, k_R)\) within which every key has the same color as \(k\). \(k_R\) is the key immediately to the right of \(k\), or, if \(k\) is the rightmost key, \(+\infty\).

Two adjacent intervals must not have the same color. This both removes redundancies and allows to make assumptions about the color of the key immediately to the left.

The following is a visual example of a possible 4-bit tree under these rules:

Documentation

data Zebra

Fully-strict one-dimensional space partitioning tree.

Constructors

Bin

Fields

• !Prefix
• !Zebra

  Masked bit is 0.

• !Zebra

  Masked bit is not 0.

Bla

Fields

• !Key

  Invariant: can only be 0 as the root of the tree.

Whi

Fields

• !Key

  Invariant: can only be 0 as the root of the tree.

Nil !Color

Invariant: unreachable state.

Bundled Patterns

pattern Mono :: Color -> Zebra

\(\mathcal{O}(1)\). All keys are the same color.

Instances

Show Zebra

Tree is represented as a list of closed intervals of all White keys.

Defined in Data.Zebra.Word.Internal

Methods

showsPrec :: Int -> Zebra -> ShowS

show :: Zebra -> String

showList :: [Zebra] -> ShowS

Eq Zebra

Defined in Data.Zebra.Word.Internal

Methods

(==) :: Zebra -> Zebra -> Bool

(/=) :: Zebra -> Zebra -> Bool

data Color

Space partition colors.

Constructors

Black

White

Instances

Show Color

Defined in Data.Zebra.Word.Internal

Methods

showsPrec :: Int -> Color -> ShowS

show :: Color -> String

showList :: [Color] -> ShowS

Eq Color

Defined in Data.Zebra.Word.Internal

Methods

(==) :: Color -> Color -> Bool

(/=) :: Color -> Color -> 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.

Directional

Size

unsafeSizeL :: Color -> Word -> Zebra -> Word

\(\mathcal{O}(\min(n,W) + n_L)\). Calculate the number of keys of the given color that are smaller than the given key.

The given key must not be equal to maxBound.

unsafeSizeR :: Color -> Word -> Zebra -> Word

\(\mathcal{O}(\min(n,W) + n_R)\). Calculate the number of keys of the given color that are greater than or equal to the given key.

The given key must not be 0.

Insert

unsafeFillL :: Word -> Color -> Zebra -> Zebra

\(\mathcal{O}(\min(n,W))\). Set every key smaller than the given one to the given color.

The given key must not be 0.

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

Size

unsafeMonoRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> Zebra

-> Maybe Color

\(\mathcal{O}(\min(n,W))\). Check whether all keys in the range are of the same color.

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

unsafeSizeRange

Arguments

:: Color

-> Word

\(k_L\)

-> Word

\(k_R\)

-> Zebra

-> Word

\(\mathcal{O}(\min(n,W) + n_I)\). Calculate the number of keys of the given color in the \([k_L, k_R)\) interval.

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

Insert

unsafeFillRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> Color

-> Zebra

-> Zebra

\(\mathcal{O}(\min(n,W) + n_L)\). Set every key in the \([k_L, k_R)\) interval to the given color.

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

Fold

Left-to-right

unsafeFoldlRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> (a -> Range -> Color -> a)

-> a

-> Zebra

-> a

\(\mathcal{O}(n)\). Fold left-to-right over the ranges of all the keys in the \([k_L, k_R)\) interval.

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

unsafeFoldlRange'

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> (a -> Range -> Color -> a)

-> a

-> Zebra

-> a

\(\mathcal{O}(n)\). Fold left-to-right over the ranges of all the keys in the \([k_L, k_R)\) interval.

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

Right-to-left

unsafeFoldrRange

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> (Range -> Color -> a -> a)

-> a

-> Zebra

-> a

\(\mathcal{O}(\min(n,W) + n_{I_L})\). Fold right-to-left over the ranges of all the keys in the \([k_L, k_R)\) interval.

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

unsafeFoldrRange'

Arguments

:: Word

\(k_L\)

-> Word

\(k_R\)

-> (Range -> Color -> a -> a)

-> a

-> Zebra

-> a

\(\mathcal{O}(\min(n,W) + n_I)\). Fold right-to-left with a strict accumulator over the ranges of all the keys in the \([k_L, k_R)\) interval.

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

Full tree

Size

unsafeSize :: Color -> Zebra -> Word

\(\mathcal{O}(n)\). Calculate the number of keys of the given color.

The tree must not be Mono.