README
¶
AVL
Library implementing AVL trees in Go.
Usage
Install the library with
go get -u github.com/nyttikord/avl@latest
You can create use simple AVL tree storing int with:
// create a new AVL storing int using the standard cmp.Compare.
tree := avl.NewSimple[int]()
// insert new nodes
tree.Insert(1, 2, 3, 8, 7, 5)
// delete nodes
tree.Delete(5, 2)
// get a node
var got *int
got = tree.Get(func (v int) { return 1 - v }) // returns the node containing 1
if got == nil {
println("not found!")
} else {
println("got", *got)
}
// get the maximum
got = tree.Max()
// get the minimum
got = tree.Min()
// get number of nodes
n := tree.Size()
// get sorted nodes
sorted := tree.Sort()
// clone the tree
cloned := tree.Clone()
Complex types
If you want to store more complex types, you can:
// `comp` is a function comparing two values.
// It must returns 0 if a == b, > 0 if a > b, and < 0 if a < b.
// The order must be linear (or total, or simple) on the set used.
//
// comp = func(a, b int) { return a - b } is a good function for ordering the set of integer.
tree := avl.New(comp)
// `find` is a function returning 0 for the requested value.
// It must returns < 0 if the value checked if before the requested value and > 0 if it is after.
// It is useful when you are sorting a set with a key.
//
// find = func(v int) { return v - 5 } is a good function for getting the 5.
got := avl.Get(find)
Immutable data
By default, the tree returned does not contain immutable data. It has side effects if it contains pointers (like an array). To avoid side effects, you can create an AVL storing immutable data.
// `clone` is a function cloning the given value.
// It must perform a deep copy to completely avoid side effects.
//
// clone = func(v []int) []int {
// dst := make([]int, len(v))
// copy(dst, v)
// return dst
// } is a good function for cloning []int.
tree := avl.NewImmutable(comp, clone)
If the type stored in the AVL implements avl.Clonable[T], avl.New automatically creates an immutable data using the
method defined by this implementation.
package main
type intArr []int
// Clone implements avl.Clonable[intArr] for intArr to creates immutable data.
func (i intArr) Clone() intArr {
dst := make(intArr, len(v))
copy(dst, v)
return dst
}
func main() {
// automatically creates an AVL storing immutable data, because intArr implements avl.Clonable[intArr]
tree := avl.New(func(a, b intArr) { return len(a) - len(b) }) // this is a bad comp function, because {0} == {1}!
}
If you want to store a type implementing avl.Clonable[T] in a mutable AVL, use avl.NewMutable.
// http.Header already implements avl.Clonable[http.Header]
var header http.Header
// creates an AVL storing mutable data, despite its implementation of avl.Clonable[http.Header]
tree := avl.NewMutable(header)
Helping functions
You can use helping functions to avoid writing common comparison function.
// create a new AVL using the standard cmp.Compare function.
tree := avl.NewSimple[int]()
// Create a new AVL storing strings using the standard strings.Compare function.
// This function is faster than avl.NewOrdered (because strings.Compare is faster than cmp.Compare).
tree = avl.NewString()
avl.NewSimpleImmutable and avl.NewSimpleMutable are available.
These functions return a *SimpleAVL[T] that has the method Has(T) bool checking if the value is present in the AVL.
tree := avl.NewSimple[int]()
tree.Insert(1, 2, 3)
if !tree.Has(1) {
panic("tree does not have 1")
}
Key-value storage
You can use AVL trees as maps easily with the type KeyAVL.
// Create a new key-value AVL.
// The compare function only targets keys.
tree := avl.NewKey[int, string](cmp.Compare)
// you can also write
tree = avl.NewKeySimple[int, string]()
// insert "hello" with the key 1
tree.Insert(1, "hello").
Insert(2, "world").
Insert(3, "world")
// print "hello world !"
st := tree.Sort()
println(strings.Join(st, " "))
// remove the value associated with the key 2
tree.Delete(2)
// print "hello !"
st = tree.Sort()
println(strings.Join(st, " "))
// check if a value is associated with key 2
if !tree.Has(2) {
println("no world :(")
tree.Insert(2, "new world")
}
// get the value associated with the key 2
got := tree.Get(2)
if got == nil {
println("value not found")
} else {
println(*got)
}
Functions NewKeyImmutable, NewKeyMutable, NewKeySimpleImmutable and NewKeySimpleMutable are available too.
Documentation
¶
Overview ¶
Package avl contains the definition of the AVL tree.
Use New to create a new AVL. The data is treated as immutable if the type implements Clonable. See NewImmutable, NewMutable and NewSimple family functions.
Use NewKey to create a new KeyAVL. You can use this struct as a custom map. The data is treated as immutable if the type implements Clonable. See NewKeyImmutable, NewKeyMutable and NewSimple family functions.
Index ¶
- type AVL
- func (a *AVL[T]) Clone() *AVL[T]
- func (a *AVL[T]) Delete(vals ...T) *AVL[T]
- func (a *AVL[T]) Get(cmp func(v T) int) *T
- func (a *AVL[T]) Insert(vals ...T) *AVL[T]
- func (a *AVL[T]) Max() *T
- func (a *AVL[T]) Min() *T
- func (a *AVL[T]) Size() uint
- func (a *AVL[T]) Sort() []T
- func (a *AVL[T]) String() string
- func (a *AVL[T]) ToImmutable(clone CloneFunc[T]) *AVL[T]
- type Clonable
- type CloneFunc
- type CompareFunc
- type KeyAVL
- func NewKey[K, V any](cmp CompareFunc[K]) *KeyAVL[K, V]
- func NewKeyImmutable[K, V any](cmp CompareFunc[K], clone CloneFunc[V]) *KeyAVL[K, V]
- func NewKeyMutable[K, V any](cmp CompareFunc[K]) *KeyAVL[K, V]
- func NewKeySimple[K cmp.Ordered, V any]() *KeyAVL[K, V]
- func NewKeySimpleImmutable[K cmp.Ordered, V any](clone CloneFunc[V]) *KeyAVL[K, V]
- func NewKeySimpleMutable[K cmp.Ordered, V any]() *KeyAVL[K, V]
- func NewKeyString[V any]() *KeyAVL[string, V]
- func (a *KeyAVL[K, V]) Clone() *KeyAVL[K, V]
- func (a *KeyAVL[K, V]) Delete(keys ...K) *KeyAVL[K, V]
- func (a *KeyAVL[K, V]) Get(k K) *V
- func (a *KeyAVL[K, V]) Has(k K) bool
- func (a *KeyAVL[K, V]) Insert(k K, v V) *KeyAVL[K, V]
- func (a *KeyAVL[K, V]) Max() *V
- func (a *KeyAVL[K, V]) Min() *V
- func (a *KeyAVL[K, V]) Size() uint
- func (a *KeyAVL[K, V]) Sort() []V
- func (a *KeyAVL[K, V]) String() string
- func (a *KeyAVL[K, V]) ToImmutable(clone CloneFunc[V]) *KeyAVL[K, V]
- type Node
- type SimpleAVL
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AVL ¶
type AVL[T any] struct { // contains filtered or unexported fields }
AVL is a standard AVL tree containing nodes.
func New ¶
func New[T any](cmp CompareFunc[T]) *AVL[T]
New creates a new AVL.
If T implements Clonable, the inserted data becomes immutable. See NewMutable to avoid this behavior. See NewImmutable to use immutable data for types that don't implements Clonable.
func NewImmutable ¶ added in v0.2.0
func NewImmutable[T any](cmp CompareFunc[T], clone CloneFunc[T]) *AVL[T]
NewImmutable creates a new AVL storing immutable data.
clone is the function used to clone data to avoid side effects.
func NewMutable ¶ added in v0.2.0
func NewMutable[T any](cmp CompareFunc[T]) *AVL[T]
NewMutable creates a new AVL storing mutable data.
func (*AVL[T]) Get ¶
Get returns the value associated with the key provided.
cmp takes the checked value and returns an integer representing the order. It returns 0 if it is the value, > 0 if the checked value is bigger than the expected one and < 0 else.
// returns value 5 if it is present
a.Get(func(v int) { return a - 5 })
If key is not found, it returns nil.
type Clonable ¶ added in v0.2.0
type Clonable[T any] interface { Clone() T }
Clonable represents a type that will be automatically cloned when used in an AVL.
type CloneFunc ¶ added in v0.2.0
type CloneFunc[T any] func(T) T
CloneFunc is a function that clone the value. It is used to avoid side effects.
type CompareFunc ¶ added in v0.2.0
CompareFunc is a function that compares two values. Returns 0 if a = b, > 0 if a > b and < 0 if a < b.
type KeyAVL ¶ added in v0.2.0
type KeyAVL[K, V any] struct { // contains filtered or unexported fields }
KeyAVL is an AVL where the comparison is made on keys (K).
func NewKey ¶ added in v0.2.0
func NewKey[K, V any](cmp CompareFunc[K]) *KeyAVL[K, V]
NewKey returns a new KeyAVL.
If V implements Clonable, the inserted data becomes immutable. See NewKeyMutable to avoid this behavior. See NewKeyImmutable to use immutable data for types that don't implements Clonable.
func NewKeyImmutable ¶ added in v0.2.0
func NewKeyImmutable[K, V any](cmp CompareFunc[K], clone CloneFunc[V]) *KeyAVL[K, V]
NewKeyImmutable creates a new AVL storing immutable data.
clone is the function used to clone data to avoid side effects.
func NewKeyMutable ¶ added in v0.2.0
func NewKeyMutable[K, V any](cmp CompareFunc[K]) *KeyAVL[K, V]
NewKeyMutable creates a new AVL storing mutable data.
func NewKeySimple ¶ added in v0.2.0
NewKeySimple returns a new KeyAVL ordered with the standard function cmp.Compare.
If V is string, use NewKeyString instead.
func NewKeySimpleImmutable ¶ added in v0.2.0
NewKeySimpleImmutable returns a new KeyAVL storing immutable data ordered with the standard function cmp.Compare.
func NewKeySimpleMutable ¶ added in v0.2.0
NewKeySimpleMutable returns a new KeyAVL storing mutable data ordered with the standard function cmp.Compare.
func NewKeyString ¶ added in v0.2.0
NewKeyString returns a new KeyAVL using strings as keys ordered with the standard function strings.Compare.
func (*KeyAVL[K, V]) Get ¶ added in v0.2.0
func (a *KeyAVL[K, V]) Get(k K) *V
Get returns the value associated with the key provided.
If key is not found, it returns nil.
func (*KeyAVL[K, V]) Max ¶ added in v0.2.0
func (a *KeyAVL[K, V]) Max() *V
Max returns the max contained in the KeyAVL.
func (*KeyAVL[K, V]) Min ¶ added in v0.2.0
func (a *KeyAVL[K, V]) Min() *V
Min returns the min contained in the KeyAVL.
type Node ¶
type Node[T any] struct { Value T // contains filtered or unexported fields }
Node is contained in an AVL.
T should be a pointer to return nil if the value is not found.
type SimpleAVL ¶ added in v0.2.0
SimpleAVL represents an AVL that stores simple values.
func NewSimple ¶ added in v0.2.0
NewSimple returns a new AVL ordered with the standard function cmp.Compare.
If T is string, use NewString instead.
func NewSimpleImmutable ¶ added in v0.2.0
NewSimpleImmutable returns a new AVL storing immutable data ordered with the standard function cmp.Compare.
func NewSimpleMutable ¶ added in v0.2.0
NewSimpleMutable returns a new AVL storing mutable data ordered with the standard function cmp.Compare.
func NewString ¶ added in v0.2.0
NewString returns a new AVL storing strings ordered with the standard function strings.Compare.
Source Files