rbtree

README

rbtree - purely functional red-black trees for Go

rbtree provides a map-like data structure rbtree.Map[K, V] that can rollback to any points in time.

It allocates internal nodes with bump allocation, and they point each other with indices, which minimizes the impact on GC.

This implementation is roughly based on red-black tree from Purely Functional Data Structures by Chris Okasaki.

Installation

go get github.com/ichiban/rbtree

Basic Usage

package main

import (
	"fmt"

	"github.com/ichiban/rbtree"
)

func main() {
	var m rbtree.Map[string, int]
	m.Set("a", 1) // {a: 1}
	m.Set("b", 2) // {a: 1, b: 2}
	snapshot := m
	m.Set("c", 3) 
	m.Set("a", 4) // Overwrites "a".
	m.Delete("b") // Deletes "b".

	for k, v := range rbtree.All(m) {
		fmt.Printf("%s: %v\n", k, v)
	}

	fmt.Println("rollback to snapshot")
	m = snapshot

	for k, v := range rbtree.All(m) {
		fmt.Printf("%s: %v\n", k, v)
	}
}

a: 4
c: 3
rollback to snapshot
a: 1
b: 2

License

Distributed under the MIT license. See LICENSE for more information.

Contributing

1. Fork it (https://github.com/ichiban/rbtree/fork)
2. Create your feature branch (git checkout -b feature/fooBar)
3. Commit your changes (git commit -am 'Add some fooBar')
4. Push to the branch (git push origin feature/fooBar)
5. Create a new Pull Request

Documentation

Index

• func All[K cmp.Ordered, V any](m Map[K, V]) iter.Seq2[K, V]
• func Copy[K cmp.Ordered, V any](dst *Map[K, V], src Map[K, V])
• func DeleteFunc[K cmp.Ordered, V any](m *Map[K, V], del func(K, V) bool)
• func Equal[K cmp.Ordered, V comparable](m1, m2 Map[K, V]) bool
• func EqualFunc[K cmp.Ordered, V1, V2 any](m1 Map[K, V1], m2 Map[K, V2], eq func(V1, V2) bool) bool
• func Insert[K cmp.Ordered, V any](m *Map[K, V], seq iter.Seq2[K, V])
• func Keys[K cmp.Ordered, V any](m Map[K, V]) iter.Seq[K]
• func Values[K cmp.Ordered, V any](m Map[K, V]) iter.Seq[V]
• type Color
• type KeyValue
• type Map
  • func Clone[K cmp.Ordered, V any](m Map[K, V]) Map[K, V]
  • func Collect[K cmp.Ordered, V any](seq iter.Seq2[K, V]) Map[K, V]
  • func (m *Map[K, V]) Delete(key K)
  • func (m *Map[K, V]) Get(key K) (V, bool)
  • func (m *Map[K, V]) Set(key K, value V)
• type Node

Examples

• Map.Delete
• Map.Set

Functions

func All

func All[K cmp.Ordered, V any](m Map[K, V]) iter.Seq2[K, V]

All returns an iterator that iterates over all the key-value pairs in order.

func Copy

func Copy[K cmp.Ordered, V any](dst *Map[K, V], src Map[K, V])

Copy copies the key-value pairs from src to dst.

func DeleteFunc

func DeleteFunc[K cmp.Ordered, V any](m *Map[K, V], del func(K, V) bool)

DeleteFunc deletes the key-value pairs that satisfy del.

func Equal

func Equal[K cmp.Ordered, V comparable](m1, m2 Map[K, V]) bool

Equal returns if two maps contains the same key-value pairs.

func EqualFunc

func EqualFunc[K cmp.Ordered, V1, V2 any](m1 Map[K, V1], m2 Map[K, V2], eq func(V1, V2) bool) bool

EqualFunc returns if two maps contains the same keys and their associated values satisfy eq.

func Insert

func Insert[K cmp.Ordered, V any](m *Map[K, V], seq iter.Seq2[K, V])

Insert inserts the key-value pairs from the iterator to the map.

func Keys

func Keys[K cmp.Ordered, V any](m Map[K, V]) iter.Seq[K]

Keys returns an iterator over the keys in order.

func Values

func Values[K cmp.Ordered, V any](m Map[K, V]) iter.Seq[V]

Values returns an iterator over the values in keys' order.

Types

type Color

type Color int8

Color is a "color" of nodes.

const (
	Red Color = iota
	Black
)

type KeyValue

type KeyValue[K cmp.Ordered, V any] struct {
	Key   K
	Value V
}

KeyValue is a key-value pair.

type Map

type Map[K cmp.Ordered, V any] struct {
	Nodes *[]Node[K, V]
	Root  int
}

Map is a map backed by a binary search tree.

func Clone

func Clone[K cmp.Ordered, V any](m Map[K, V]) Map[K, V]

Clone returns a shallow copy of the map.

func Collect

func Collect[K cmp.Ordered, V any](seq iter.Seq2[K, V]) Map[K, V]

Collect creates a new map from the key-value pairs from the iterator.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K)

Delete removes the key-value pair from the map.

Example

var m Map[string, int]
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)
snapshot := m
m.Delete("b")

for k, v := range All(m) {
	fmt.Printf("%s: %v\n", k, v)
}

fmt.Println("rollback to snapshot")
m = snapshot

for k, v := range All(m) {
	fmt.Printf("%s: %v\n", k, v)
}

Output:

a: 1
c: 3
rollback to snapshot
a: 1
b: 2
c: 3

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (V, bool)

Get returns the associated value for a key.

func (*Map[K, V]) Set

func (m *Map[K, V]) Set(key K, value V)

Set stores a pair of key and value.

Example

var m Map[string, int]
m.Set("a", 1)
m.Set("b", 2)
snapshot := m
m.Set("c", 3)
m.Set("a", 4)

for k, v := range All(m) {
	fmt.Printf("%s: %v\n", k, v)
}

fmt.Println("rollback to snapshot")
m = snapshot

for k, v := range All(m) {
	fmt.Printf("%s: %v\n", k, v)
}

Output:

a: 4
b: 2
c: 3
rollback to snapshot
a: 1
b: 2

type Node

type Node[K cmp.Ordered, V any] struct {
	Color       Color
	Left, Right int
	KeyValue[K, V]
}

Node is a tree node. []Node works as a memory region for a tree. Instead of *Node, we point Left and Right branches with indexes.