gleamy/red_black_tree_map

This module provides an implementation of a red-black tree map, a self-balancing binary search tree data structure that maintains a balanced shape which ensures tree operations stay efficient. It associates keys with values, where each key is unique and ordered according to the comparison function.

Types

Map

opaque </>

pub opaque type Map(k, v)

Values

clear

</>

pub fn clear(tree: Map(k, v)) -> Map(k, v)

Removes all elements from the map, resulting in an empty map. Time complexity: O(1)

delete

</>

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

Removes a key-value pair from the map, if the key exists. Time complexity: O(log n)

find

</>

pub fn find(tree: Map(k, v), key: k) -> Result(v, Nil)

Searches for a key in the map and returns the associated value if found. Time complexity: O(log n)

fold

</>

pub fn fold(tree: Map(k, v), acc: b, fun: fn(b, k, v) -> b) -> b

Applies a function to every key-value pair in the map, accumulating the results with the provided initial accumulator value. Time complexity: O(n)

foldr

</>

pub fn foldr(tree: Map(k, v), acc: b, fun: fn(b, k, v) -> b) -> b

Applies a function to every key-value pair in the map, accumulating the results with the provided initial accumulator value, but in reverse order. Time complexity: O(n)

insert

</>

pub fn insert(tree: Map(k, v), key: k, value: v) -> Map(k, v)

Inserts a new key-value pair into the map. If the key already exists, its associated value is updated with the new value. Time complexity: O(log n)

larger

</>

pub fn larger(tree: Map(k, v), key: k) -> Result(#(k, v), Nil)

Find the smallest key that is larger than the given key. Time complexity: O(log n)

new

</>

pub fn new(compare: fn(k, k) -> order.Order) -> Map(k, v)

Creates a new empty map with the provided comparison function for keys.

smaller

</>

pub fn smaller(tree: Map(k, v), key: k) -> Result(#(k, v), Nil)

Find the largest key that is smaller than the given key. Time complexity: O(log n)