Module t_tree

Implements T-trees extended with an notion of least upp and greatest lower bounds.

Copyright © (C) 2013-2020, Jan Henry Nystrom <JanHenryNystrom@gmail.com> -------------------------------------------------------------------

Authors: Jan Henry Nystrom (JanHenryNystrom@gmail.com).

Description

Implements T-trees extended with an notion of least upp and greatest lower bounds. For more information on T-Trees see: A Study of Index Structures for Main Memory Database Management Systems. by Tobin J. Lehman and Michael J. Carey, VLDB 1986.

Data Types

default()

default() = term()

flag()

flag() = check | nocheck

index()

index() = term()

opt()

opt() = {min, pos_integer()} | {max, pos_integer()}

t_tree()

abstract datatype: t_tree()

value()

value() = term()

Function Index

add/3 The Value is saved under the Index in the Tree, if that index is present the value associated with the index is replaced by Value.
add/4 The Value is saved under the Index in the Tree, the Flag determines what should happen if that index already has a value associated with in the Tree.
adds/2 For each {Index, Value} pair in Pairs the value is stored under the index in the Tree.
adds/3 For each {Index, Value} pair in Pairs the value is stored under the index in the Tree.
delete/2 If a value is associated the Index the Tree returned has that association removed.
delete/3 If a value is associated the Index the Tree returned has that association removed.
deletes/2 A tree that has all the associations for the indices removed.
deletes/3 A tree that has all the associations for the indices removed.
find/2 Returns the value associated with Index in the Tree or undefined if no such association exists.
find/3 Returns the value associated with Index in the Tree or Default if no such association exists.
first/1 Returns the value of the smallest index in the Tree or undefined if the tree is empty.
first/2 Returns the value of the smallest index in the Tree or Default if the tree is empty.
from_list/1 For each {Index, Value} pair in Pairs the value is stored under the index in the Tree.
greatest_lower_bound/2 Returns the value of the largest index that is less or equal to to Index that has a value associated with it, or undefined if no such index exists.
greatest_lower_bound/3 Returns the value of the largest index that is less or equal to to Index that has a value associated with it, or Default if no such index exists.
indices/1 Returns all the indices in ascending order.
is_empty/1 Returns true if the Tree is empty, false otherwise.
is_t_tree/1 Returns true if X is a t_tree, false otherwise.
last/1 Returns the value of the largest index in the Tree or undefined if the tree is empty.
last/2 Returns the value of the largest index in the Tree or Default if the tree is empty.
least_upper_bound/2 Returns the value of the smallest index that is greater or equal to to Index that has a value associated with it, or undefined if no such index exists.
least_upper_bound/3 Returns the value of the smallest index that is greater or equal to to Index that has a value associated with it, or Default if no such index exists.
member/2 Returns true if there is a value associated with Index in the tree, otherwise false.
new/0 Creates an empty T-tree.
new/1 Creates an empty T-tree with min and max internal size according to the options.
replace/3 Replaces any existing value associated with Index in the tree, otherwise adds a association for the value with the Index.
replace/4 Replaces any existing value associated with Index in the tree, otherwise the flag determines what happens.
to_list/1 From a T-tree a list of {Index, Value} pairs.
values/1 Returns all the values in ascending order of their indeces.

Function Details

add/3

add(Index::index(), Value::value(), Tree::t_tree()) -> t_tree()

The Value is saved under the Index in the Tree, if that index is present the value associated with the index is replaced by Value. add(Index, Value, Tree) is equivalent to add(Index, Value, Tree, nocheck).

add/4

add(Index::index(), Value::value(), Tree::t_tree(), Flag::flag()) -> t_tree()

The Value is saved under the Index in the Tree, the Flag determines what should happen if that index already has a value associated with in the Tree. If the flag is check an exception is generated and if nocheck the value is replaced.

adds/2

adds(Pairs::[{index(), value()}], Tree::t_tree()) -> t_tree()

For each {Index, Value} pair in Pairs the value is stored under the index in the Tree. The adds(Pairs, Tree) call is equivalent to adds(Pairs, Tree, nocheck).

adds/3

adds(Pairs::[{index(), value()}], Tree::t_tree(), X3::flag()) -> t_tree()

For each {Index, Value} pair in Pairs the value is stored under the index in the Tree. If an index already has a value associated with in the Tree the flag determines what happens. If the flag is check an exception is generated if a index has a value associated with it, if the flag is nocheck the values will be replaced.

delete/2

delete(Index::index(), Tree::t_tree()) -> t_tree()

If a value is associated the Index the Tree returned has that association removed. The call delete(Index, Tree) is equivalent to delete(Index, Tree, nocheck).

delete/3

delete(Index::index(), Tree::t_tree(), Flag::flag()) -> t_tree()

If a value is associated the Index the Tree returned has that association removed. If there is no value associated with the Index in the Tree the flag determines what happens. If the flag is check an exception is generated if no association exists, if the flag is nocheck the unchanged tree is returned.

deletes/2

deletes(Indices::[index()], Tree::t_tree()) -> t_tree()

A tree that has all the associations for the indices removed. The call deletes(Indces, Tree) is equivalent to deletes(Indces, Tree, nocheck).

deletes/3

deletes(Indices::[index()], Tree::t_tree(), X3::flag()) -> t_tree()

A tree that has all the associations for the indices removed. If there is no value associated with any of the Indices in the Tree, the flag determines what happens. If the flag is check an exception is generated if, if the flag is nocheck a tree is returned with the other associations removed.

find/2

find(Index::index(), Tree::t_tree()) -> value() | undefined

Returns the value associated with Index in the Tree or undefined if no such association exists. The call find(Index, Tree) is equivalent to find(Index, Tree, undefined).

find/3

find(Index::index(), T_tree::t_tree(), Default::default()) -> value() | default()

Returns the value associated with Index in the Tree or Default if no such association exists.

first/1

first(Tree::t_tree()) -> value() | undefined

Returns the value of the smallest index in the Tree or undefined if the tree is empty. The call first(Tree) if equivalent to first(Tree, undefined).

first/2

first(T_tree::t_tree(), Default::default()) -> value() | default()

Returns the value of the smallest index in the Tree or Default if the tree is empty.

from_list/1

from_list(Pairs::[{index(), value()}]) -> t_tree()

For each {Index, Value} pair in Pairs the value is stored under the index in the Tree. Equivalent to from_list(Pairs, []).

greatest_lower_bound/2

greatest_lower_bound(Index::index(), Tree::t_tree()) -> value() | undefined

Returns the value of the largest index that is less or equal to to Index that has a value associated with it, or undefined if no such index exists. The call greatest_lower_bound(Index, Tree) is equivalent to greatest_lower_bound(Index, Tree, undefined).

greatest_lower_bound/3

greatest_lower_bound(Index::index(), T_tree::t_tree(), Default::default()) -> value() | default()

Returns the value of the largest index that is less or equal to to Index that has a value associated with it, or Default if no such index exists.

indices/1

indices(T_tree::t_tree()) -> [index()]

Returns all the indices in ascending order.

is_empty/1

is_empty(T_tree::term()) -> boolean()

Returns true if the Tree is empty, false otherwise.

is_t_tree/1

is_t_tree(T_tree::term()) -> boolean()

Returns true if X is a t_tree, false otherwise.

last/1

last(Tree::t_tree()) -> value() | undefined

Returns the value of the largest index in the Tree or undefined if the tree is empty. The call last(Tree) if equivalent to last(Tree, undefined).

last/2

last(T_tree::t_tree(), Default::default()) -> value() | default()

Returns the value of the largest index in the Tree or Default if the tree is empty.

least_upper_bound/2

least_upper_bound(Index::index(), Tree::t_tree()) -> value() | undefined

Returns the value of the smallest index that is greater or equal to to Index that has a value associated with it, or undefined if no such index exists. The call least_upper_bound(Index, Tree) is equivalent to least_upper_bound(Index, Tree, undefined).

least_upper_bound/3

least_upper_bound(Index::index(), T_tree::t_tree(), Default::default()) -> value() | default()

Returns the value of the smallest index that is greater or equal to to Index that has a value associated with it, or Default if no such index exists.

member/2

member(Index::index(), T_tree::t_tree()) -> boolean()

Returns true if there is a value associated with Index in the tree, otherwise false.

new/0

new() -> t_tree()

Creates an empty T-tree. The call new() is equivalent to new([]).

new/1

new(Opts::[opt()]) -> t_tree()

Creates an empty T-tree with min and max internal size according to the options.

replace/3

replace(Index::index(), Value::value(), Tree::t_tree()) -> t_tree()

Replaces any existing value associated with Index in the tree, otherwise adds a association for the value with the Index. The call replace(Index, Value, Tree) is equivalent to replace(Index, Value, Tree, nocheck).

replace/4

replace(Index::index(), Value::value(), Tree::t_tree(), X4::flag()) -> t_tree()

Replaces any existing value associated with Index in the tree, otherwise the flag determines what happens. If the flag is check an exception is generated, otherwise the value is added.

to_list/1

to_list(T_tree::t_tree()) -> [{index(), value()}]

From a T-tree a list of {Index, Value} pairs.

values/1

values(T_tree::t_tree()) -> [index()]

Returns all the values in ascending order of their indeces.


Generated by EDoc