exometer_shallowtree.md

Module exometer_shallowtree

• Description
• Data Types
• Function Index
• Function Details

Size-constrained leftist tree Inspired by Leftist Trees by Sartaj Sahni.

Description

The purpose of this module is to efficiently store a limited number of values in e.g. a lossy histogram (ex. exometer_slot_slide). The complexity of insert operations is log(N), but once the tree is full, only values higher than the minimum value already in the tree will be inserted, and the old minimum is deleted - i.e. two O(log N) operations. For other values, the cost will be only two comparisons, since the top node in the tree always contains the minimum.

Data Types

tree()

tree() = #t{}

Function Index

fill/1
fill1/2
filter/2
insert/3	Insert value V into tree T.
limit/1	Returns the maximum number of values for the given tree.
new/1	Create an empty tree limited to Size.
size/1	Returns the number of values stored in the given tree.
take_min/1	Extract the smallest value from the tree T.
to_list/1	Converts a tree to a list.

Function Details

fill/1

fill(Size) -> any()

fill1/2

fill1(T, Tree) -> any()

filter/2

filter(F, T) -> any()

insert/3

insert(K::number(), V::any(), T::tree()) -> tree()

Insert value V into tree T.

If the tree is full and V is smaller than the minimum, this function will return immediately, leaving the tree unchanged.

limit/1

limit(T::tree()) -> non_neg_integer()

Returns the maximum number of values for the given tree.

new/1

new(Size::pos_integer()) -> tree()

Create an empty tree limited to Size.

size/1

size(T::tree()) -> non_neg_integer()

Returns the number of values stored in the given tree.

take_min/1

take_min(T::tree()) -> {number(), any(), tree()} | error

Extract the smallest value from the tree T.

If the tree is empty, error is returned, otherwise {Minimum, NewTree}.

to_list/1

to_list(T::tree()) -> [{number(), any()}]

Converts a tree to a list.

The list will not be ordered, since the aim is to produce the list as quickly as possible. Also, lists:sort(to_list(Tree)), if to_list/1 uses brute force, seems faster than most approaches for extracting values in order.