obt

Documentation

Overview

Package obt (Ordered Binary Tree) provides interfaces to implement by binary trees. It also provides convenience functions for many common operations.

Index

• func ContainsAll[V any](obt Keyless[V], value ...V) bool
• func ContainsAny[V any](obt Keyless[V], value ...V) bool
• func DeleteMany[V any](obt Keyless[V], value ...V)
• func PutMany[V any](obt Keyless[V], value ...V)
• type Keyless
• type Obt

Functions

func ContainsAll

func ContainsAll[V any](obt Keyless[V], value ...V) bool

ContainsAll is like ContainsAny, but checks if every value is contained in Keyless.

func ContainsAny

func ContainsAny[V any](obt Keyless[V], value ...V) bool

ContainsAny is a convenience function for checking if any of multiple values is contained in Keyless. The complexity is O(k log n) where k is the number of values to check, and n is the Keyless.Len of the tree. This could technically be achieved in O(n) time, however for a couple of values, O(k log n) would be much faster.

If you need to check every value iterate over the tree!

func DeleteMany

func DeleteMany[V any](obt Keyless[V], value ...V)

DeleteMany is like PutMany but for deletion.

func PutMany

func PutMany[V any](obt Keyless[V], value ...V)

PutMany is a convenience function for putting multiple values into a Keyless. Ignores any errors that occured. The complexity is O(k log n) where k is the number of values to put, and n is the Keyless.Len of the tree.

Types

type Keyless

type Keyless[V any] interface {
	// Put inserts a value (or a generated key-value pair) into the Keyless.
	// Put must return true if the value has been added.
	Put(V) (added bool)

	// Delete removes the value (or a generated key-value pair) from the Keyless.
	// Delete must return true if the value has been deleted.
	Delete(V) (removed bool)

	// Contains is like Obt.Contains but checks for values or generated keys.
	Contains(V) bool

	// Len returns the amount of elements in the Keyless.
	Len() int
}

Keyless is a no-key version of Obt. The name may be misleading, as most implementations may still need to allocate for keys. The name Keyless comes from generating key-value pairs based on values (usually). See bst.Keyless for the simplest implementation.

type Obt

type Obt[K cmp.Ordered, V any] interface {
	// Put inserts a key-value pair into the Obt.
	// Put must return true if the key-value pair has been added.
	Put(K, V) (put bool)

	// Delete removes a key-value pair from the Obt.
	// Delete must return true if the key-value pair has been deleted.
	Delete(K) (deleted bool)

	// Contains checks if the key exists in the Obt.
	Contains(K) bool

	// Len returns the amount of elements in the Obt.
	Len() int
}

Obt is short for Ordered Binary Tree. This essentially is an alias for Binary Search Tree, which is the simplest implementation of this interface and some self-balancing Obts. All Obts are functionally Set-like.

Obt and Keyless are designed to be mutually exclusive, you either implement one or the other.