btree

README

btree

go 1.18 generics experiment in building generic augmented btree data structures.

Don't use this in production, go 1.18 isn't even out yet!

Read more about this in the introductory blog post.

Documentation

Index

• type Map
  • func MakeMap[K, V any](cmp func(K, K) int) Map[K, V]
  • func (m *Map[K, V]) Clone() Map[K, V]
• type Set
  • func MakeSet[T any](cmp func(T, T) int) Set[T]
  • func (t *Set[T]) Clone() Set[T]
  • func (t *Set[K]) Delete(item K) (removed bool)
  • func (t *Set[T]) Upsert(item T) (replaced T, overwrote bool)

Examples

• Map

Types

type Map

type Map[K, V any] struct {
	abstract.Map[K, V, struct{}]
}

Map is a ordered map from K to V.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/ajwerner/btree"
)

func main() {
	m := btree.MakeMap[string, int](strings.Compare)
	m.Upsert("foo", 1)
	m.Upsert("bar", 2)
	fmt.Println(m.Get("foo"))
	fmt.Println(m.Get("baz"))
	it := m.Iterator()
	for it.First(); it.Valid(); it.Next() {
		fmt.Println(it.Cur(), it.Value())
	}

}

Output:

1 true
0 false
bar 2
foo 1

func MakeMap

func MakeMap[K, V any](cmp func(K, K) int) Map[K, V]

MakeMap constructs a new Map with the provided comparison function.

func (*Map[K, V]) Clone

func (m *Map[K, V]) Clone() Map[K, V]

Clone clones the Map, lazily. It does so in constant time.

type Set

type Set[T any] Map[T, struct{}]

Set is an ordered set of items of type T.

func MakeSet

func MakeSet[T any](cmp func(T, T) int) Set[T]

MakeSet constructs a new Set with the provided comparison function.

func (*Set[T]) Clone

func (t *Set[T]) Clone() Set[T]

Clone clones the Set, lazily. It does so in constant time.

func (*Set[K]) Delete

func (t *Set[K]) Delete(item K) (removed bool)

Delete removes the value with the provided key. It returns true if the item existed in the set.

func (*Set[T]) Upsert

func (t *Set[T]) Upsert(item T) (replaced T, overwrote bool)

Upsert inserts or updates the provided item. It returns the overwritten item if a previous value existed for the key.