Bedrock.DataPlane.Resolver.Tree (bedrock v0.6.0)

View Source

Provides functionality for an interval tree, allowing for efficient insertion, querying, overlap detection, and filtering of intervals.

This module defines a self-balancing binary search tree (AVL tree) that stores intervals, making it possible to efficiently perform operations such as checking for overlaps with a given interval or point, inserting new intervals with associated values, and filtering the tree's intervals based on the values associated with them.

Intervals are represented as tuples of a start and end key paired with a value. Operations are provided for both inserting new intervals into the tree and querying for existing intervals that overlap a given range. The tree is kept balanced automatically to ensure operations perform optimally.

Various utility functions are also provided, including converting the tree into a list of its intervals and filtering by a predicate.

Types

  • t: The type representing an interval tree node.

Functions

  • new/3: Creates a new interval tree node.
  • overlap?/3: Checks if a given range or key overlaps with any interval in the tree.
  • insert/3: Inserts a new interval into the tree, balancing it if necessary, and returns the updated tree.
  • height/1: Gets the height of the tree.
  • filter_by_value/2: Filters the tree by evaluating a predicate on each node's value.
  • to_list/1: Converts the interval tree into a list of tuples.

Summary

Types

t()

Functions

filter_by_value(tree, predicate)

Filters the tree by evaluating a predicate on each node's value.

height(arg1)
insert(tree, range, value)

Inserts a new interval into the tree, balancing it if necessary, and returns the updated tree.

insert_bulk(tree, range_value_pairs)

Inserts multiple intervals into the tree efficiently with delayed rebalancing.

overlap?(tree, range)

Checks if a given range or key overlaps with any interval in the tree.

to_list(tree)

Converts the interval tree into a list of tuples, where each tuple represents an interval with its associated value. The list is ordered by the start of the range.

Types

t()

@type t() :: %Bedrock.DataPlane.Resolver.Tree{
  end: Bedrock.key(),
  height: non_neg_integer(),
  left: t() | nil,
  right: t() | nil,
  start: Bedrock.key(),
  value: Bedrock.version()
}

Functions

filter_by_value(tree, predicate)

@spec filter_by_value(t() | nil, (Bedrock.version() -> boolean())) :: t() | nil

Filters the tree by evaluating a predicate on each node's value.

Parameters

  • tree: The tree to filter, or nil if empty.
  • predicate: A function that returns true for nodes that should be kept in the tree.

Returns

  • A new tree containing only the nodes for which the predicate returned true.

height(arg1)

@spec height(t() | nil) :: non_neg_integer()

insert(tree, range, value)

@spec insert(nil | t(), Bedrock.key() | Bedrock.key_range(), Bedrock.version()) :: t()

Inserts a new interval into the tree, balancing it if necessary, and returns the updated tree.

Parameters

  • tree: The current interval tree or nil if empty.
  • range: A tuple representing the start and end of the interval to insert, or a single key to be inserted as an interval with its respective value.
  • value: The value associated with the interval.

Returns

  • The updated interval tree containing the new interval.

insert_bulk(tree, range_value_pairs)

@spec insert_bulk(nil | t(), [{Bedrock.key_range(), Bedrock.version()}]) :: t() | nil

Inserts multiple intervals into the tree efficiently with delayed rebalancing.

This is more efficient than calling insert/3 multiple times as it only rebalances once at the end instead of after each insertion.

Parameters

  • tree: The current interval tree or nil if empty.
  • ranges: A list of ranges to insert, each as {range, value} tuple.
  • version: The version to associate with all ranges.

Returns

  • The updated interval tree containing all new intervals, properly balanced.

overlap?(tree, range)

@spec overlap?(t(), Bedrock.key() | Bedrock.key_range()) :: boolean()

Checks if a given range or key overlaps with any interval in the tree.

Parameters

  • tree: The interval tree to check for overlaps, or nil if empty.
  • range: A tuple representing the start and end of the range or a single key to be checked for overlap with range in the tree.

Returns

  • true if there is an overlap with any range, otherwise false.

to_list(tree)

@spec to_list(t() | nil) :: [{Bedrock.key(), Bedrock.key(), Bedrock.version()}]

Converts the interval tree into a list of tuples, where each tuple represents an interval with its associated value. The list is ordered by the start of the range.

Parameters

  • tree: The interval tree to convert, or nil if empty.

Returns

  • A list of tuples in the form {start, end, value}, representing the range and their associated values in the tree.