stupidb.associative.segmenttree

Functions

make_segment_tree(leaf_arguments, ...)

Make a segment tree from tuples leaves and class aggregate_type.

Classes

SegmentTree(leaves, aggregate_type, *, fanout)

A segment tree for window aggregation.

class stupidb.associative.segmenttree.SegmentTree(leaves, aggregate_type, *, fanout)

A segment tree for window aggregation.

nodes

The nodes of the segment tree

aggregate_type

The class of the aggregate to use

levels

A list of the nodes in each level of the tree

fanout

The number of leaves to aggregate into each interior node

static iterlevels(nodes, *, fanout)

Iterate over every level in the tree.

Parameters

• nodes (Sequence[~AssociativeAggregate]) – The nodes of the tree whose levels will be yielded.

• fanout (int) – The number child nodes per interior node

Return type

Iterator[Sequence[~AssociativeAggregate]]

query(begin, end)

Aggregate the values between begin and end using aggregate.

Parameters

• begin – The start of the range to aggregate

• end – The end of the range to aggregate

stupidb.associative.segmenttree.make_segment_tree(leaf_arguments, aggregate_type, *, fanout)

Make a segment tree from tuples leaves and class aggregate_type.

The algorithm used here traverses from the bottom of tree upward, updating the parent every time a new node is seen.

Parameters

• leaves – A sequence of tuples that make up the leaves of the segment tree

• aggregate_type – The aggregate class whose instances compose the tree.