Struct std::BST

#include <std/collections/bst.h> source

generic<K, V, C: Order> struct BST {
    ?&heap struct BSTNode<K, V> root;
    C ord;
    unsigned long len;
    struct NodePool<struct BSTNode<K, V>> pool;
}

Fields

§?&heap struct BSTNode<K, V> rootsource

§C ordsource

§unsigned long lensource

§struct NodePool<struct BSTNode<K, V>> poolsource

Methods

§static struct BST<K, V, C> new()source · definition

stateless C (Less, Greater): C from the target

§static struct BST<K, V, C> new_with(C ord)source · definition

ordering value (FnOrder, ...)

§int insert(K key, V val)source · definition

insert or overwrite; 0 on OOM

§?&V get(K key) constsource · definition

null if missing

§int contains(K key) constsource · definition

§?V remove(K key)source · definition

the removed value, or null

§unsigned long length() constsource · definition

§int is_empty() constsource · definition

§?&K min_key() constsource · definition

null if empty

§?&K max_key() constsource · definition

null if empty

§void foreach_inorder(fn void(const &K, &V) func)source · definition

Morris in-order traversal: O(n) time, O(1) extra space. Threads each predecessor's empty right link back to its successor while descending and removes the thread on the way back, so the tree is unchanged afterwards.

§void clear()source · definition

drop every entry

§void drop()source · definition

drops the entries, releases the nodes (Drop)

§void free() consumesource · definition

= drop()