node.go

package abnf

import (
	"bytes"
	"sync"
)

// Node represents a single node in a tree generated by [Operator].
type Node struct {
	Key      string
	Value    []byte
	Children Nodes
}

// String returns the node's value as string.
func (n Node) String() string {
	return string(n.Value)
}

// Len returns length of the node's value.
func (n Node) Len() int {
	return len(n.Value)
}

// IsEmpty returns true if the node's value length = 0.
func (n Node) IsEmpty() bool {
	return len(n.Value) == 0
}

// Contains returns whether the subtree contains the given key.
func (n Node) Contains(key string) bool {
	_, ok := n.GetNode(key)
	return ok
}

// GetNode recursively searches a node with the given key starting from itself.
// Returns found node and true on success, empty node and false on failure.
func (n Node) GetNode(key string) (Node, bool) {
	if n.Key == key {
		return n, true
	}
	return n.Children.Get(key)
}

// GetNodes recursively searches all nodes with the given key starting from itself.
func (n Node) GetNodes(key string) Nodes {
	var ns Nodes
	if n.Key == key {
		ns = append(ns, n)
	}
	for _, n := range n.Children.GetAll(key) {
		ns = append(ns, n)
	}
	return ns
}

// Compare compares node values via [bytes.Compare].
// The result will be 0 if n.Value == other.Value, -1 if n.Value < other.Value, and +1 if n.Value > other.Value.
func (n Node) Compare(other Node) int {
	return bytes.Compare(n.Value, other.Value)
}

// Nodes represents a list of nodes.
type Nodes []Node

// Contains returns whether the subtree contains the given key.
func (ns Nodes) Contains(key string) bool {
	for _, n := range ns {
		if n.Key == key || n.Children.Contains(key) {
			return true
		}
	}
	return false
}

// Get recursively searches a node with the given key.
func (ns Nodes) Get(key string) (Node, bool) {
	for _, n := range ns {
		if n.Key == key {
			return n, true
		}
		if n, ok := n.Children.Get(key); ok {
			return n, true
		}
	}
	return Node{}, false
}

// GetAll recursively searches all nodes with the given key.
func (ns Nodes) GetAll(key string) Nodes {
	var nodes Nodes
	for _, n := range ns {
		if n.Key == key {
			nodes = append(nodes, n)
		}
		nodes = append(nodes, n.Children.GetAll(key)...)
	}
	return nodes
}

// Best returns a node with the longest value.
func (ns Nodes) Best() Node {
	if len(ns) == 0 {
		return Node{}
	}
	best := ns[0]
	for _, n := range ns[1:] {
		if n.Len() > best.Len() {
			best = n
		}
	}
	return best
}

// Compare compares two best nodes.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b where a - self best node, b - other best node.
func (ns Nodes) Compare(other Nodes) int {
	return ns.Best().Compare(other.Best())
}

var nodesPool = sync.Pool{
	New: func() any { return make(Nodes, 0, 1) },
}

func newNodes() Nodes {
	return nodesPool.Get().(Nodes)[:0]
}

func (ns Nodes) free() {
	nodesPool.Put(ns[:0])
}

func freeNodesChildren(ns Nodes) {
	for _, n := range ns {
		if n.Children != nil {
			n.Children.free()
		}
	}
}