avl

Documentation

Overview

Package avl provides a barebones key-value pair accepting Avl implementation and a Keyless variant for user-defined key generation based on provided values.

Index

• type Avl
  • func New[K cmp.Ordered, V any]() *Avl[K, V]
  • func (avl *Avl[K, V]) Contains(key K) bool
  • func (avl *Avl[K, V]) Delete(key K) (deleted bool)
  • func (avl *Avl[K, V]) Len() int
  • func (avl *Avl[K, V]) Put(key K, value V) (put bool)
  • func (avl *Avl[K, V]) String() string
• type KeyFunc
• type Keyless
  • func NewKeyless[K cmp.Ordered, V any](generateKey KeyFunc[K, V]) *Keyless[K, V]
  • func (k *Keyless[K, V]) Contains(value V) bool
  • func (k *Keyless[K, V]) Delete(value V) (removed bool)
  • func (k *Keyless[K, V]) Len() int
  • func (k *Keyless[K, V]) Put(value V) (added bool)
  • func (k *Keyless[K, V]) String() string

Types

type Avl

type Avl[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Avl is a rigidly self-balancing bst.Bst. Every single operation in worst case is O(log n). Avl has fast lookups and generally more efficient operations thanks to the balanced nature of the tree. Unless inserting highly randomized data, this variant is recommended over regular bst.Bst. Implements obt.Obt, refer to Keyless for obt.Keyless variant.

func New

func New[K cmp.Ordered, V any]() *Avl[K, V]

New creates a new *Avl[K, V] with nil root and length equal to 0.

func (*Avl[K, V]) Contains

func (avl *Avl[K, V]) Contains(key K) bool

Contains implements obt.Obt.Contains.

func (*Avl[K, V]) Delete

func (avl *Avl[K, V]) Delete(key K) (deleted bool)

Delete implements obt.Obt.Delete.

func (*Avl[K, V]) Len

func (avl *Avl[K, V]) Len() int

Len implements obt.Obt.Len.

func (*Avl[K, V]) Put

func (avl *Avl[K, V]) Put(key K, value V) (put bool)

Put implements obt.Obt.Put.

func (*Avl[K, V]) String

func (avl *Avl[K, V]) String() string

String implements fmt.Stringer by showing the tree in a slice format, ignoring keys.

type KeyFunc

type KeyFunc[K cmp.Ordered, V any] func(V) K

KeyFunc is a key generating function signature for Avl variants with no explicit keys.

type Keyless

type Keyless[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Keyless is essentially a wrapper over a normal Avl with user-provided key generation out of inserted values. The overhead is miniscule (~15-20 nanoseconds more per op in comparison to the ordinary variant).

func NewKeyless

func NewKeyless[K cmp.Ordered, V any](generateKey KeyFunc[K, V]) *Keyless[K, V]

NewKeyless constructs a *Keyless[Key, Value] with a key generating function for ordering.

func (*Keyless[K, V]) Contains

func (k *Keyless[K, V]) Contains(value V) bool

Contains implements obt.KeylessObt.Contains

func (*Keyless[K, V]) Delete

func (k *Keyless[K, V]) Delete(value V) (removed bool)

Delete implements obt.KeylessObt.Delete

func (*Keyless[K, V]) Len

func (k *Keyless[K, V]) Len() int

Len implements obt.KeylessObt.Len

func (*Keyless[K, V]) Put

func (k *Keyless[K, V]) Put(value V) (added bool)

Put implements obt.KeylessObt.Put

func (*Keyless[K, V]) String

func (k *Keyless[K, V]) String() string

String implements fmt.Stringer by showing the tree in a slice format, ignoring keys.