Minilib.Collection.Internal.PatTree
Defined in minilib-collection@0.7.0-beta2
Simple map using Patricia Tree.
The type of key is U64, and the type of value is any type.
Reference
This module was inspired by Haskell's Data.IntMap package.
In particular, I used the following papers mentioned in the Data.IntMap package's documentation:
Values
namespace Minilib.Collection.Internal.PatTree::Combine
append
Type: [a : Std::Add] Minilib.Collection.Internal.PatTree::Combine a
A combining function that appends the new value after the old value.
overwrite
Type: Minilib.Collection.Internal.PatTree::Combine a
A combining function that replaces the old value into the new value.
namespace Minilib.Collection.Internal.PatTree::PNodeIndex
empty
Type: Minilib.Collection.Internal.PatTree::PNodeIndex
A special index which represents an empty node.
namespace Minilib.Collection.Internal.PatTree::PTree
empty
Type: Minilib.Collection.Internal.PatTree::PTree a
An empty Patricia Tree.
Types and aliases
namespace Minilib.Collection.Internal.PatTree
Combine
Defined as: type Combine a = a -> a -> a
The type of combining functions that resolve collisions.
combine(old_value, new_value) should return a value combined from old_value and new_value.
PKey
Defined as: type PKey = Std::U64
The key type of Patricia Trees.
PMask
Defined as: type PMask = Std::U64
The mask type. (used internally)
PNode
Defined as: type PNode a = unbox union { ...variants... }
The type of tree nodes.
variant empty
Type: ()
An empty node.
variant leaf
Type: (Minilib.Collection.Internal.PatTree::PKey, a)
A leaf node. (key, data)
variant branch
Type: (Minilib.Collection.Internal.PatTree::Prefix, Minilib.Collection.Internal.PatTree::PMask, Minilib.Collection.Internal.PatTree::PNodeIndex, Minilib.Collection.Internal.PatTree::PNodeIndex)
A branch node. (prefix, mask of the branching bit, left, right)
PNodeIndex
Defined as: type PNodeIndex = Std::I64
The type of index of the node array.
PTree
Defined as: type PTree a = unbox struct { ...fields... }
The type of Patricia Trees.
Prefix
Defined as: type Prefix = Std::U64
The prefix type. (used internally)
namespace Minilib.Collection.Internal.PatTree::PTree
PTreeIterator
Defined as: type PTreeIterator a = unbox struct { ...fields... }
field tree
Type: Minilib.Collection.Internal.PatTree::PTree a
field lower_bound
Type: Minilib.Collection.Trait::Bound Minilib.Collection.Internal.PatTree::PKey
field upper_bound
Type: Minilib.Collection.Trait::Bound Minilib.Collection.Internal.PatTree::PKey
field ascending
Type: Std::Bool
field stack
Type: Std::Array Minilib.Collection.Internal.PatTree::PNodeIndex