ordmap

README

go-ordmap

Persistent generic ordered maps for Go.

This is v2 which is based on 1.18 generics. If you can't (or don't want to) use generics there is still v1 which uses code generation. See v1 branch.

Rationale

Standard library does not provide a key-value store data structure that would also allow quick access to minimum/maximum and in-order iteration.

This package provides such data structure (called OrdMap for "ordered map") and implements it on top of AVL trees (self balancing binary trees). This allows us O(log n) read/write access to arbitrary key as well as to the min & max while still supporting O(n) iteration over elements - just that it's now in order.

One detail that may not be idiomatic for Go is that these OrdMaps are persistent data structures - meaning that each operation gives you back a new map while keeping the old intact. This is beneficial when you have many concurrent readers - your writer can advance while the readers still traverse the old versions (kind of similar to MVCC)

In order to facilitate safe API and efficient internalization the this module ueses type parameters and thus requires go 1.18+.

Usage

go get github.com/edofic/go-ordmap/v2@v2.0.0-beta2

You only need to remember to always assign the returned value of all operations; the original object is never updated in-place:

package main

import (
	"fmt"

	"github.com/edofic/go-ordmap/v2"
)

func main() {
	m1 := ordmap.NewBuiltin[int, string]()

	m1 = m1.Insert(1, "foo") // adding entries
	m1 = m1.Insert(2, "baz")
	m1 = m1.Insert(2, "bar") // will override
	fmt.Println(m1.Get(2))   // access by key
	m1 = m1.Insert(3, "baz")
	// this is how you can efficiently iterate in-order
	for i := m1.Iterate(); !i.Done(); i.Next() {
		fmt.Println(i.GetKey(), i.GetValue())
	}
	m1 = m1.Remove(1)         // can also remove entries
	fmt.Println(m1.Entries()) // or get a slice of all of them

	// can use another map of different type in the same package
	m2 := ordmap.NewBuiltin[int, int]()
	v, ok := m2.Get(0)
	fmt.Println("wat", v, ok)
	m2 = m2.Insert(1, 1) // this one has "raw" ints for keys
	m2 = m2.Insert(2, 3) // in order to support this you will also need to pass
	m2 = m2.Insert(2, 2) // `-less "<"` to the genreeator in order to use
	m2 = m2.Insert(3, 3) // native comparator
	// can iterate in reverse as well
	for i := m2.IterateReverse(); !i.Done(); i.Next() {
		fmt.Println(i.GetKey(), i.GetValue())
	}
	fmt.Println(m2.Min(), m2.Max()) // access the extremes
}

See examples for more.

You will need to provide the Less method on your - so the map knows how to order itself. Or if you want to use one of the builtin types (e.g. int) you can use NewBulitin which only takes supported types.`

func (k MyKey) Less(k2 MyKey) bool {
    ...
}

Development

Go 1.18+ required.

Testing

Standard testing

go test ./...

100% test coverage expected on the core implementation (avl.go)

Documentation

Index

• Variables
• type Builtin
  • func (b Builtin[A]) Less(b2 Builtin[A]) bool
• type BuiltinComparable
• type Comparable
• type Entry
• type Iterator
  • func (i *Iterator[K, V]) Done() bool
  • func (i *Iterator[K, V]) GetKey() K
  • func (i *Iterator[K, V]) GetValue() V
  • func (i *Iterator[K, V]) Next()
• type IteratorBuiltin
  • func (i *IteratorBuiltin[K, V]) Done() bool
  • func (i *IteratorBuiltin[K, V]) GetKey() K
  • func (i *IteratorBuiltin[K, V]) GetValue() V
  • func (i *IteratorBuiltin[K, V]) Next()
• type Node
  • func New[K Comparable[K], V any]() *Node[K, V]
  • func (node *Node[K, V]) Entries() []Entry[K, V]
  • func (node *Node[K, V]) Get(key K) (value V, ok bool)
  • func (node *Node[K, V]) Insert(key K, value V) *Node[K, V]
  • func (node *Node[K, V]) Iterate() Iterator[K, V]
  • func (node *Node[K, V]) IterateFrom(k K) Iterator[K, V]
  • func (node *Node[K, V]) IterateReverse() Iterator[K, V]
  • func (node *Node[K, V]) IterateReverseFrom(k K) Iterator[K, V]
  • func (node *Node[K, V]) Len() int
  • func (node *Node[K, V]) Max() *Entry[K, V]
  • func (node *Node[K, V]) Min() *Entry[K, V]
  • func (node *Node[K, V]) Remove(key K) *Node[K, V]
• type NodeBuiltin
  • func NewBuiltin[K BuiltinComparable, V any]() NodeBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) Entries() []Entry[K, V]
  • func (n NodeBuiltin[K, V]) Get(key K) (value V, ok bool)
  • func (n NodeBuiltin[K, V]) Insert(key K, value V) NodeBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) Iterate() IteratorBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) IterateFrom(k K) IteratorBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) IterateReverse() IteratorBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) IterateReverseFrom(k K) IteratorBuiltin[K, V]
  • func (n NodeBuiltin[K, V]) Len() int
  • func (n NodeBuiltin[K, V]) Max() *Entry[K, V]
  • func (n NodeBuiltin[K, V]) Min() *Entry[K, V]
  • func (n NodeBuiltin[K, V]) Remove(key K) NodeBuiltin[K, V]

Variables

var Template string

Types

type Builtin

type Builtin[A BuiltinComparable] struct {
	// contains filtered or unexported fields
}

func (Builtin[A]) Less

func (b Builtin[A]) Less(b2 Builtin[A]) bool

type BuiltinComparable

type BuiltinComparable interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 |
		~string
}

type Comparable

type Comparable[A any] interface {
	Less(A) bool
}

type Entry

type Entry[K, V any] struct {
	K K
	V V
}

type Iterator

type Iterator[K Comparable[K], V any] struct {
	// contains filtered or unexported fields
}

func (*Iterator[K, V]) Done

func (i *Iterator[K, V]) Done() bool

func (*Iterator[K, V]) GetKey

func (i *Iterator[K, V]) GetKey() K

func (*Iterator[K, V]) GetValue

func (i *Iterator[K, V]) GetValue() V

func (*Iterator[K, V]) Next

func (i *Iterator[K, V]) Next()

type IteratorBuiltin

type IteratorBuiltin[K BuiltinComparable, V any] struct {
	// contains filtered or unexported fields
}

func (*IteratorBuiltin[K, V]) Done

func (i *IteratorBuiltin[K, V]) Done() bool

func (*IteratorBuiltin[K, V]) GetKey

func (i *IteratorBuiltin[K, V]) GetKey() K

func (*IteratorBuiltin[K, V]) GetValue

func (i *IteratorBuiltin[K, V]) GetValue() V

func (*IteratorBuiltin[K, V]) Next

func (i *IteratorBuiltin[K, V]) Next()

type Node

type Node[K Comparable[K], V any] struct {
	// contains filtered or unexported fields
}

func New

func New[K Comparable[K], V any]() *Node[K, V]

func (*Node[K, V]) Entries

func (node *Node[K, V]) Entries() []Entry[K, V]

func (*Node[K, V]) Get

func (node *Node[K, V]) Get(key K) (value V, ok bool)

func (*Node[K, V]) Insert

func (node *Node[K, V]) Insert(key K, value V) *Node[K, V]

func (*Node[K, V]) Iterate

func (node *Node[K, V]) Iterate() Iterator[K, V]

func (*Node[K, V]) IterateFrom

func (node *Node[K, V]) IterateFrom(k K) Iterator[K, V]

func (*Node[K, V]) IterateReverse

func (node *Node[K, V]) IterateReverse() Iterator[K, V]

func (*Node[K, V]) IterateReverseFrom

func (node *Node[K, V]) IterateReverseFrom(k K) Iterator[K, V]

func (*Node[K, V]) Len

func (node *Node[K, V]) Len() int

func (*Node[K, V]) Max

func (node *Node[K, V]) Max() *Entry[K, V]

func (*Node[K, V]) Min

func (node *Node[K, V]) Min() *Entry[K, V]

func (*Node[K, V]) Remove

func (node *Node[K, V]) Remove(key K) *Node[K, V]

type NodeBuiltin

type NodeBuiltin[K BuiltinComparable, V any] struct {
	// contains filtered or unexported fields
}

func NewBuiltin

func NewBuiltin[K BuiltinComparable, V any]() NodeBuiltin[K, V]

func (NodeBuiltin[K, V]) Entries

func (n NodeBuiltin[K, V]) Entries() []Entry[K, V]

func (NodeBuiltin[K, V]) Get

func (n NodeBuiltin[K, V]) Get(key K) (value V, ok bool)

func (NodeBuiltin[K, V]) Insert

func (n NodeBuiltin[K, V]) Insert(key K, value V) NodeBuiltin[K, V]

func (NodeBuiltin[K, V]) Iterate

func (n NodeBuiltin[K, V]) Iterate() IteratorBuiltin[K, V]

func (NodeBuiltin[K, V]) IterateFrom

func (n NodeBuiltin[K, V]) IterateFrom(k K) IteratorBuiltin[K, V]

func (NodeBuiltin[K, V]) IterateReverse

func (n NodeBuiltin[K, V]) IterateReverse() IteratorBuiltin[K, V]

func (NodeBuiltin[K, V]) IterateReverseFrom

func (n NodeBuiltin[K, V]) IterateReverseFrom(k K) IteratorBuiltin[K, V]

func (NodeBuiltin[K, V]) Len

func (n NodeBuiltin[K, V]) Len() int

func (NodeBuiltin[K, V]) Max

func (n NodeBuiltin[K, V]) Max() *Entry[K, V]

func (NodeBuiltin[K, V]) Min

func (n NodeBuiltin[K, V]) Min() *Entry[K, V]

func (NodeBuiltin[K, V]) Remove

func (n NodeBuiltin[K, V]) Remove(key K) NodeBuiltin[K, V]