avl

package module
v0.0.0-...-87d874c Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 18, 2019 License: GPL-3.0 Imports: 7 Imported by: 0

README

avl

CircleCI GoDoc FOSSA Status Go Report Card

avl is simple AVL Tree from scratch.

UnitTest

$ go clean -testcache; go test -race -v ./ -run ..

You can set the environment variable, AVL_DEBUG=1 for enabling debug mode.

avl2dot

avl2dot is simple utility to generate dot graph from TreeGenerator. You can install avl2dot.

$ go get github.com/spikeekips/avl/cmd/avl2dot

You can pass the nodes keys to avl2dot, it will print dot graph.

$ avl2dot my name is spike ekips i am developer

avl2dot-example-08bb.png

The nodes key can be passed by standard input.

Performance

Elapsed Time By Number Of Nodes

TreeGenerator-elapsedtime Plot

Estimated by avl2dot at 08bbcafe2359356bf0da02a1177635855f66de8d .

golang Benchmark
$ go clean -testcache; go test -race -v -run _ -bench BenchmarkTreeGenerator ./
goos: darwin
goarch: amd64
pkg: github.com/spikeekips/avl
BenchmarkTree10-8      	   14068	     83553 ns/op
BenchmarkTree100-8     	     919	   1284131 ns/op
BenchmarkTree200-8     	     423	   2768402 ns/op
BenchmarkTree300-8     	     271	   4393870 ns/op
BenchmarkTree400-8     	     195	   6032931 ns/op
BenchmarkTree500-8     	     152	   7734220 ns/op
BenchmarkTree600-8     	     126	   9456218 ns/op
BenchmarkTree700-8     	     105	  11239279 ns/op
BenchmarkTree800-8     	      80	  13124616 ns/op
BenchmarkTree900-8     	      72	  15055493 ns/op
BenchmarkTree1000-8    	      61	  16941144 ns/op
BenchmarkTree1100-8    	      56	  19040152 ns/op
BenchmarkTree1200-8    	      51	  20899512 ns/op
BenchmarkTree1300-8    	      45	  22839384 ns/op
BenchmarkTree1400-8    	      43	  24848736 ns/op
BenchmarkTree1500-8    	      40	  26989702 ns/op
BenchmarkTree1600-8    	      37	  28986443 ns/op
BenchmarkTree1700-8    	      34	  31502533 ns/op
BenchmarkTree1800-8    	      32	  33902428 ns/op
BenchmarkTree1900-8    	      30	  36840383 ns/op
BenchmarkTree10000-8   	       5	 235527047 ns/op

Documentation

Overview

Package avl is the implementation of AVL Tree(https://en.wikipedia.org/wiki/AVL_tree).

avl also supports the hashable node, which can generate it's own hash and leaves hash. With the hashable node, avl can generate node's proof. Please check the examples below.

NOTE

- Unlike other avl implementation, avl only provides insertion or updating of node, not deletion.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var (
	FailedToAddNodeInTreeError = NewWrapError("failed to add node to TreeGenerator")
)
View Source 
var (
	InvalidNodeError = NewWrapError("invalid node")
)
View Source 
var (
	InvalidTreeError = NewWrapError("invalid tree")
)
View Source 
var (
	NodeNotFoundInPoolError = NewWrapError("node not found in pool")
)

Functions

func CompareKey 

func CompareKey(a, b []byte) int

CompareKey compares node keys. it acts like bytes.Compare()

func EqualKey 

func EqualKey(a, b []byte) bool

EqualKey checks node keys are same. it acts like bytes.Equal()

func IsValidNode 

func IsValidNode(node, left, right Node) error

IsValidNode checks node is valid and well defined.

func PrintDotGraph 

func PrintDotGraph(tr *Tree, w io.Writer)

PrintDotGraph will print dot graph source of Tree. With the printed output, the dot graph image can be easily made: 

$ cat <dot graph source> | dot -Tpng -o/tmp/d.png

`dot` is the utility of graphviz.

Example

ExamplePrintDotGraph print a dot graph from the generated Tree. 

package main

import (
	"fmt"
	"os"

	"github.com/spikeekips/avl"
)

var numberOfNodesForDot = 10

// ExamplePrintDotGraph print a dot graph from the generated Tree.
func main() {
	// create new TreeGenerator
	tg := avl.NewTreeGenerator()

	// generate 10 new MutableNodes and add to TreeGenerator.
	for i := 0; i < numberOfNodesForDot; i++ {
		node := &ExampleMutableNode{
			key: []byte(fmt.Sprintf("%03d", i)),
		}
		if _, err := tg.Add(node); err != nil {
			return
		}
	}

	// Get Tree from TreeGenerator.
	tree, err := tg.Tree()
	if err != nil {
		return
	}

	avl.PrintDotGraph(tree, os.Stdout)
}

Output:

graph graphname {
  "003" [label="003 (3)"];
  "003" -- "001";
  "001" [label="001 (1)"];
  "001" -- "000";
  "000" [label="000 (0)"];
  "0000" [label=" " style="filled" color="white" bgcolor="white"];
  "000" -- "0000" [style="solid" color="white" bgcolor="white"];
  "0001" [label=" " style="filled" color="white" bgcolor="white"];
  "000" -- "0001" [style="solid" color="white" bgcolor="white"];
  "001" -- "002";
  "002" [label="002 (0)"];
  "0020" [label=" " style="filled" color="white" bgcolor="white"];
  "002" -- "0020" [style="solid" color="white" bgcolor="white"];
  "0021" [label=" " style="filled" color="white" bgcolor="white"];
  "002" -- "0021" [style="solid" color="white" bgcolor="white"];
  "003" -- "007";
  "007" [label="007 (2)"];
  "007" -- "005";
  "005" [label="005 (1)"];
  "005" -- "004";
  "004" [label="004 (0)"];
  "0040" [label=" " style="filled" color="white" bgcolor="white"];
  "004" -- "0040" [style="solid" color="white" bgcolor="white"];
  "0041" [label=" " style="filled" color="white" bgcolor="white"];
  "004" -- "0041" [style="solid" color="white" bgcolor="white"];
  "005" -- "006";
  "006" [label="006 (0)"];
  "0060" [label=" " style="filled" color="white" bgcolor="white"];
  "006" -- "0060" [style="solid" color="white" bgcolor="white"];
  "0061" [label=" " style="filled" color="white" bgcolor="white"];
  "006" -- "0061" [style="solid" color="white" bgcolor="white"];
  "007" -- "008";
  "008" [label="008 (1)"];
  "0081" [label=" " style="filled" color="white" bgcolor="white"];
  "008" -- "0081" [style="solid" color="white" bgcolor="white"];
  "008" -- "009";
  "009" [label="009 (0)"];
  "0090" [label=" " style="filled" color="white" bgcolor="white"];
  "009" -- "0090" [style="solid" color="white" bgcolor="white"];
  "0091" [label=" " style="filled" color="white" bgcolor="white"];
  "009" -- "0091" [style="solid" color="white" bgcolor="white"];
}

func SetDefaultLog 

func SetDefaultLog() zerolog.Logger

SetDefaultLog returns the predefined(default) zerolog.Logger.

Types

type Logger 

type Logger struct {
	// contains filtered or unexported fields
}

Logger is basic log for this package.

func NewLogger 

func NewLogger(cf func(zerolog.Context) zerolog.Context) *Logger

NewLogger returns new Logger. With argument function you can pass the context to Logger. For example, 

logger := NewLogger(func(c zerolog.Context) zerolog.Context {
	return c.Str("module", "avl_tree_validator")
})

func (*Logger) Log 

func (zl *Logger) Log() *zerolog.Logger

func (*Logger) SetLogger 

func (zl *Logger) SetLogger(l zerolog.Logger) *Logger

SetLogger set the new zerolog.Logger.

type MapMutableNodePool 

type MapMutableNodePool struct {
	// contains filtered or unexported fields
}

func NewMapMutableNodePool 

func NewMapMutableNodePool(m map[string]MutableNode) *MapMutableNodePool

func (*MapMutableNodePool) Get 

func (mn *MapMutableNodePool) Get(key []byte) (Node, error)

func (*MapMutableNodePool) Set 

func (mn *MapMutableNodePool) Set(node Node) error

func (*MapMutableNodePool) Traverse 

func (mn *MapMutableNodePool) Traverse(f NodeTraverseFunc) error

type MapNodePool 

type MapNodePool struct {
	// contains filtered or unexported fields
}

MapNodePool uses builtin map.

func NewMapNodePool 

func NewMapNodePool(m map[string]Node) *MapNodePool

func (*MapNodePool) Get 

func (mn *MapNodePool) Get(key []byte) (Node, error)

func (*MapNodePool) Set 

func (mn *MapNodePool) Set(node Node) error

func (*MapNodePool) Traverse 

func (mn *MapNodePool) Traverse(f NodeTraverseFunc) error

type MutableNode 

type MutableNode interface {
	Node
	// SetHeight set height.
	SetHeight(int16) error
	// Left() returns the MutableNode of left leaf.
	Left() MutableNode
	// Right() returns the MutableNode of right leaf.
	Right() MutableNode
	// SetLeft() replaces left leaf.
	SetLeft(MutableNode) error
	// SetRight() replaces right leaf.
	SetRight(MutableNode) error
	// Merge() merges source node. The basic properties(key, height, left right
	// key) will not be merged.
	Merge(source MutableNode) error
}

MutableNode is, the name said, is mutable node.Mainly it is used for TreeGenerator.

type Node 

type Node interface {
	Key() []byte
	Height() int16
	LeftKey() []byte
	RightKey() []byte
}

Node defines the basic node. By comparing with MutableNode, Node stands for immutable node.

type NodePool 

type NodePool interface {
	// Get returns node by key. The returned error is for the external storage
	// error. When node is not found, Get() will return (nil, nil).
	Get(key []byte) (Node, error)

	// Set inserts node. Like Get, the returned error is for the external
	// storage error.
	Set(Node) error

	// Traverse traverses all the nodes in NodePool. NodeTraverseFunc returns 2
	// result, If keep is false or error occurred, traversing will be stopped.
	Traverse(NodeTraverseFunc) error
}

NodePool is the container of node in Tree.

type NodeTraverseFunc 

type NodeTraverseFunc func(Node) (keep bool, err error)

NodeTraverseFunc is used for Tree.Traverse(). If keep is false, traversing will be stopped and error also stops traversing.

type SyncMapNodePool 

type SyncMapNodePool struct {
	// contains filtered or unexported fields
}

SyncMapNodePool uses sync.Map.

func NewSyncMapNodePool 

func NewSyncMapNodePool(m *sync.Map) *SyncMapNodePool

func (*SyncMapNodePool) Get 

func (mn *SyncMapNodePool) Get(key []byte) (Node, error)

func (*SyncMapNodePool) Set 

func (mn *SyncMapNodePool) Set(node Node) error

func (*SyncMapNodePool) Traverse 

func (mn *SyncMapNodePool) Traverse(f NodeTraverseFunc) error

type Tree 

type Tree struct {
	*Logger
	// contains filtered or unexported fields
}

Tree is AVL tree. Mainly Tree is used for loading the existing nodes.

Example (WithNode)

ExampleTree shows to load the existing nodes to Tree. 

package main

import (
	"fmt"

	"github.com/spikeekips/avl"
)

// ExampleNode implements Node.
type ExampleNode struct {
	key    []byte
	height int16
	left   []byte
	right  []byte
}

func (em *ExampleNode) Key() []byte {
	return em.key
}

func (em *ExampleNode) Height() int16 {
	return em.height
}

func (em *ExampleNode) LeftKey() []byte {
	if em.left == nil || len(em.left) < 1 {
		return nil
	}

	return em.left
}

func (em *ExampleNode) RightKey() []byte {
	if em.right == nil || len(em.right) < 1 {
		return nil
	}

	return em.right
}

// ExampleTree shows to load the existing nodes to Tree.
func main() {
	shape := map[int]struct {
		height int16
		left   int
		right  int
	}{
		100: {height: 3, left: 50, right: 150},
		50:  {height: 1, left: 30, right: 70},
		150: {height: 2, left: 130, right: 180},
		30:  {height: 0},
		70:  {height: 0},
		130: {height: 0},
		170: {height: 0},
		180: {height: 1, left: 170, right: 200},
		200: {height: 0},
	}

	i2k := func(i int) []byte {
		return []byte(fmt.Sprintf("%03d", i))
	}

	// NodePool will contain all the nodes.
	nodePool := avl.NewMapNodePool(nil)
	for key, properties := range shape {
		node := &ExampleNode{
			key: i2k(key),
		}
		node.height = properties.height

		if properties.left > 0 {
			node.left = i2k(properties.left)
		}
		if properties.right > 0 {
			node.right = i2k(properties.right)
		}

		_ = nodePool.Set(node)
	}

	// Trying to load nodes from NodePool
	tree, err := avl.NewTree(i2k(100), nodePool)
	if err != nil {
		fmt.Printf("error: failed to load nodes; %v", err)
		return
	}
	fmt.Println("< tree is loaded")

	fmt.Printf("tree root is %s\n", string(tree.Root().Key()))

	// Check all the nodes is added in Tree.
	var i int
	_ = tree.Traverse(func(node avl.Node) (bool, error) {
		fmt.Printf(
			"%d: node loaded: key=%s height=%d left=%s right=%s\n",
			i,
			string(node.Key()),
			node.Height(),
			string(node.LeftKey()),
			string(node.RightKey()),
		)
		i++
		return true, nil
	})

	// Check Tree is valid or not
	if err := tree.IsValid(); err != nil {
		fmt.Printf("error: failed to validate; %v", err)
		return
	}
	fmt.Println("< tree is valid")
}

Output:

func NewTree 

func NewTree(rootKey []byte, nodePool NodePool) (*Tree, error)

NewTree loads tree from NodePool.

func (*Tree) Get 

func (tr *Tree) Get(key []byte) (Node, error)

Get finds and returns node by key. It traverse the entire tree. Unlike NodePool.Get() the only organized(not orphan) node will be returned. For performance, NodePool.Get() will be better.

func (*Tree) GetWithParents 

func (tr *Tree) GetWithParents(key []byte) (Node, []Node, error)

GetWithParents returns node with it's parents node.

func (*Tree) IsValid 

func (tr *Tree) IsValid() error

IsValid checks whether Tree is valid or not.

func (*Tree) NodePool 

func (tr *Tree) NodePool() NodePool

NodePool returns NodePool of this tree.

func (*Tree) Root 

func (tr *Tree) Root() Node

Root returns root node.

func (*Tree) Traverse 

func (tr *Tree) Traverse(f NodeTraverseFunc) error

Traverse traverses the entire tree. The error of NodeTraverseFunc mainly error is from the external storage or other system.

type TreeGenerator 

type TreeGenerator struct {
	*Logger
	// contains filtered or unexported fields
}

TreeGenerator will generate new AVL Tree.

Example 
package main

import (
	"fmt"

	"github.com/spikeekips/avl"
	"golang.org/x/xerrors"
)

// ExampleMutableNode implements MutableNode. ExampleMutableNode has value field
// to store custom value.
type ExampleMutableNode struct {
	key    []byte
	height int16
	left   avl.MutableNode
	right  avl.MutableNode
	value  int
}

func (em *ExampleMutableNode) Key() []byte {
	return em.key
}

func (em *ExampleMutableNode) Height() int16 {
	return em.height
}

func (em *ExampleMutableNode) SetHeight(height int16) error {
	if height < 0 {
		return xerrors.Errorf("height must be greater than zero; height=%d", height)
	}

	em.height = height

	return nil
}

func (em *ExampleMutableNode) Left() avl.MutableNode {
	return em.left
}

func (em *ExampleMutableNode) LeftKey() []byte {
	if em.left == nil {
		return nil
	}

	return em.left.Key()
}

func (em *ExampleMutableNode) SetLeft(node avl.MutableNode) error {
	if node == nil {
		em.left = nil
		return nil
	}

	if avl.EqualKey(em.key, node.Key()) {
		return xerrors.Errorf("left is same node; key=%v", em.key)
	}

	em.left = node

	return nil
}

func (em *ExampleMutableNode) Right() avl.MutableNode {
	return em.right
}

func (em *ExampleMutableNode) RightKey() []byte {
	if em.right == nil {
		return nil
	}

	return em.right.Key()
}

func (em *ExampleMutableNode) SetRight(node avl.MutableNode) error {
	if node == nil {
		em.right = nil
		return nil
	}

	if avl.EqualKey(em.key, node.Key()) {
		return xerrors.Errorf("right is same node; key=%v", em.key)
	}

	em.right = node

	return nil
}

func (em *ExampleMutableNode) Merge(node avl.MutableNode) error {
	e, ok := node.(*ExampleMutableNode)
	if !ok {
		return xerrors.Errorf("merge node is not *ExampleMutableNode; node=%T", node)
	}

	em.value = e.value

	return nil
}

func main() {
	// create new TreeGenerator
	tg := avl.NewTreeGenerator()

	fmt.Println("> trying to generate new tree")

	// Generate 10 new MutableNodes and add to TreeGenerator.
	for i := 0; i < 10; i++ {
		node := &ExampleMutableNode{
			key: []byte(fmt.Sprintf("%03d", i)),
		}
		if _, err := tg.Add(node); err != nil {
			fmt.Printf("error: failed to add node: %v\n", err)
			return
		}
		fmt.Printf("> node added: key=%s\n", string(node.Key()))
	}

	// Get Tree from TreeGenerator.
	tree, err := tg.Tree()
	if err != nil {
		fmt.Printf("error: failed to get Tree from generator: %v\n", err)
		return
	}

	// Check all the nodes is added in Tree.
	var i int
	_ = tree.Traverse(func(node avl.Node) (bool, error) {
		fmt.Printf(
			"%d: node loaded: key=%s height=%d left=%s right=%s\n",
			i,
			string(node.Key()),
			node.Height(),
			string(node.LeftKey()),
			string(node.RightKey()),
		)
		i++
		return true, nil
	})

	// check Tree is valid or not
	if err := tree.IsValid(); err != nil {
		fmt.Printf("tree is invalid: %v\n", err)
		return
	}
	fmt.Println("< tree is valid")
}

Output:

func NewTreeGenerator 

func NewTreeGenerator() *TreeGenerator

NewTreeGenerator returns new TreeGenerator.

func (*TreeGenerator) Add 

func (tg *TreeGenerator) Add(node MutableNode) ([]MutableNode, error)

Add tries to add MutableNode into Tree.

func (*TreeGenerator) Nodes 

func (tg *TreeGenerator) Nodes() map[string]MutableNode

Nodes returns the map of added nodes.

func (*TreeGenerator) Root 

func (tg *TreeGenerator) Root() MutableNode

Root returns root node of tree.

func (*TreeGenerator) Tree 

func (tg *TreeGenerator) Tree() (*Tree, error)

Tree returns new Tree with added ndoes.

type TreeValidator 

type TreeValidator struct {
	*Logger
	// contains filtered or unexported fields
}

TreeValidator will validate Tree is formed properly.

func NewTreeValidator 

func NewTreeValidator(tr *Tree) TreeValidator

NewTreeValidator returns new TreeValidator.

func (TreeValidator) IsValid 

func (tv TreeValidator) IsValid() error

IsValid checks whether tree is valid or not.

type WrapError 

type WrapError struct {
	S     string
	Err   error
	Frame xerrors.Frame
}

WrapError is simple wrapper for xerror.Is and xerror.As.

func NewWrapError 

func NewWrapError(s string, a ...interface{}) WrapError

func (WrapError) Error 

func (we WrapError) Error() string

func (WrapError) FormatError 

func (we WrapError) FormatError(p xerrors.Printer) error

func (WrapError) Is 

func (we WrapError) Is(err error) bool

Is is for `xerrors.Is()`.

func (WrapError) Unwrap 

func (we WrapError) Unwrap() error

func (WrapError) Wrap 

func (we WrapError) Wrap(err error) error

Wrap put error inside WrapError.

func (WrapError) Wrapf 

func (we WrapError) Wrapf(s string, a ...interface{}) error

Wrapf acts like `fmt.Errorf()`.

Source Files

View all Source files

Directories

Path Synopsis
cmd
avl2dot

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.