avl

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:

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: