balanced_tree

BalancedTree is a Gleam friendly wrapper around erlang’s gb_trees module It implements the same functions as gleam/dict, a few from gleam/list, and some additional that are unique to gb_trees

Build Target is Erlang-only. I may consider writing a javascript implementation in the future

Types

BalancedTree

</>

A Balanced Tree of keys and values.

Any type can be used for the keys and values of a tree, but all the keys must be of the same type and all the values must be of the same type.

Each key can only be present in a tree once.

BalancedTrees are ordered, unlike gleam/dict, and are a good solution for when your code relies on the ordering of of the entries, such as a Heap or PriorityQueue.

pub type BalancedTree(k, v)

Values

balance

</>

pub fn balance(tree: BalancedTree(k, v)) -> BalancedTree(k, v)

Notice that this is rarely necessary, but can be motivated when many nodes have been deleted from the tree without further insertions. Rebalancing can then be forced to minimize lookup times, as deletion does not rebalance the tree.

combine

</>

pub fn combine(
  tree: BalancedTree(k, v),
  other: BalancedTree(k, v),
  with fun: fn(v, v) -> v,
) -> BalancedTree(k, v)

Creates a new tree from a pair of given frees by combining their entries.

If there are entries with the same keys in both trees the given function is used to determine the new value to use in the resulting dict.

delete

</>

pub fn delete(
  from tree: BalancedTree(k, v),
  delete key: k,
) -> BalancedTree(k, v)

Creates a new tree from a given tree with all the same entries except for the one with a given key, if it exists.

drop

</>

pub fn drop(
  from tree: BalancedTree(k, v),
  drop disallowed_keys: List(k),
) -> BalancedTree(k, v)

each

</>

pub fn each(tree: BalancedTree(k, v), fun: fn(k, v) -> a) -> Nil

Calls a function for each key and value in a tree, discarding the return value.

Useful for producing a side effect for every item of a tree.

filter

</>

pub fn filter(
  in tree: BalancedTree(k, v),
  keeping predicate: fn(k, v) -> Bool,
) -> BalancedTree(k, v)

fold

</>

pub fn fold(
  over tree: BalancedTree(k, v),
  from initial: acc,
  with fun: fn(acc, k, v) -> acc,
) -> acc

Reduces a list of elements into a single value by calling a given function on each element, in order from min-key to max-key

This function runs in linear time.

fold_right

</>

pub fn fold_right(
  over tree: BalancedTree(k, v),
  from initial: acc,
  with fun: fn(acc, k, v) -> acc,
) -> acc

Reduces a list of elements into a single value by calling a given function on each element, in order from max-key to min-key

This function runs in linear time.

from_dict

</>

pub fn from_dict(dict: dict.Dict(k, v)) -> BalancedTree(k, v)

Converts a Dict(k, v) into a BalancedTree(k, v)

from_list

</>

pub fn from_list(list: List(#(k, v))) -> BalancedTree(k, v)

Converts a list of 2-element tuples #(key, value) to a tree.

If two tuples have the same key the last one in the list will be the one that is present in the tree.

get

</>

pub fn get(
  from gb_tree: BalancedTree(k, v),
  get key: k,
) -> Result(v, Nil)

Fetches a value from a tree for a given key.

The tree may not have a value for the key, so the value is wrapped in a Result.

get_larger

</>

pub fn get_larger(
  tree: BalancedTree(k, v),
  key: k,
) -> Result(#(k, v), Nil)

Gets the 2-element tuple #(key, value) of the next larger key in the Tree.

The tree may not have a larger key, so the tuple is wrapped in a Result.

get_max

</>

pub fn get_max(
  from tree: BalancedTree(k, v),
) -> Result(#(k, v), Nil)

Fetches the key-value pair for the largest key in the tree.

Returns Error(Nil) when the tree is empty, otherwise Ok(#(k, v))

get_min

</>

pub fn get_min(
  from tree: BalancedTree(k, v),
) -> Result(#(k, v), Nil)

Fetches the key-value pair for the smallest key in the tree.

Returns Error(Nil) when the tree is empty, otherwise Ok(#(k, v))

get_smaller

</>

pub fn get_smaller(
  tree: BalancedTree(k, v),
  key: k,
) -> Result(#(k, v), Nil)

Gets the 2-element tuple #(key, value) of the next smaller key in the Tree.

The tree may not have a smaller key, so the tuple is wrapped in a Result.

has_key

</>

pub fn has_key(tree: BalancedTree(k, v), key: k) -> Bool

Determines whether or not a value is present in the tree for a given key.

insert

</>

pub fn insert(
  into tree: BalancedTree(k, v),
  for key: k,
  insert value: v,
) -> BalancedTree(k, v)

is_empty

</>

pub fn is_empty(tree: BalancedTree(k, v)) -> Bool

Determines whether or not the tree is empty.

iterate

</>

pub fn iterate(
  tree: BalancedTree(k, v),
) -> yielder.Yielder(#(k, v))

Generate a Yielder that traverses in the tree in min-to-max order

iterate_right

</>

pub fn iterate_right(
  tree: BalancedTree(k, v),
) -> yielder.Yielder(#(k, v))

Generate a Yielder that traverses in the tree in max-to-min order

keys

</>

pub fn keys(tree: BalancedTree(k, v)) -> List(k)

Gets a list of all keys in a given dict.

BalancedTrees are ordered. Keys are returned ordered min-to-max.

map_values

</>

pub fn map_values(
  in tree: BalancedTree(k, v),
  with fun: fn(k, v) -> a,
) -> BalancedTree(k, a)

Updates all values in a given tree by calling a given function on each key and value.

merge

</>

pub fn merge(
  into tree: BalancedTree(k, v),
  from new_entries: BalancedTree(k, v),
) -> BalancedTree(k, v)

Creates a new tree from a pair of given trees by combining their entries.

If there are entries with the same keys in both trees the entry from the second tree takes precedence.

new

</>

pub fn new() -> BalancedTree(k, v)

Creates a fresh tree that contains no values.

pop_max

</>

pub fn pop_max(
  from tree: BalancedTree(k, v),
) -> Result(#(#(k, v), BalancedTree(k, v)), Nil)

Gets the max key-value pair in the tree, returning the pair and a new tree without that pair.

pop_min

</>

pub fn pop_min(
  from tree: BalancedTree(k, v),
) -> Result(#(#(k, v), BalancedTree(k, v)), Nil)

Gets the min key-value pair in the tree, returning the pair and a new tree without that pair.

size

</>

pub fn size(tree: BalancedTree(k, v)) -> Int

Determines the number of key-value pairs in the dict.

Unlike gleam/dict, this function must iterate over the tree and runs in linear time time

to_dict

</>

pub fn to_dict(tree: BalancedTree(k, v)) -> dict.Dict(k, v)

to_list

</>

pub fn to_list(tree: BalancedTree(k, v)) -> List(#(k, v))

Converts the dict to a list of 2-element tuples #(key, value), one for each key-value pair in the dict.

The tuples in the list are ordered by Key

upsert

</>

pub fn upsert(
  in tree: BalancedTree(k, v),
  update key: k,
  with fun: fn(option.Option(v)) -> v,
) -> BalancedTree(k, v)

Creates a new tree with one entry inserted or updated using a given function.

If there was not an entry in the tree for the given key then the function gets None as its argument, otherwise it gets Some(value).

values

</>

pub fn values(tree: BalancedTree(k, v)) -> List(v)

Gets a list of all values in a given tree.

BalancedTrees are ordered. Values are guaranteed to be in min-to-max order based on their associated Keys.