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 {
	if n == nil {
		return ""
	}
	return string(n.Value)
}

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

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

// Contains returns whether the subtree contains the given key.
func (n *Node) Contains(key string) bool {
	if n == nil {
		return false
	}
	return n.GetNode(key) != nil
}

// 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 {
	if n.Key == key {
		return n
	}
	return n.Children.Get(key)
}

// GetNodes recursively searches all nodes with the given key starting from itself.
func (n *Node) GetNodes(key string) Nodes {
	if n == nil {
		return nil
	}

	var ns Nodes
	if n.Key == key {
		ns = append(ns, n)
	}
	ns = append(ns, n.Children.GetAll(key)...)
	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 {
	if n == other {
		return 0
	} else if n == nil {
		return -1
	} else if other == nil {
		return 1
	}
	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 {
	for _, n := range ns {
		if n.Key == key {
			return n
		}
		if n := n.Children.Get(key); n != nil {
			return n
		}
	}
	return nil
}

// 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 nil
	}
	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 {
		ns := make(Nodes, 0, 10)
		return &ns
	},
}

func newNodes() Nodes {
	ns := nodesPool.Get().(*Nodes)
	ns.clear()
	return *ns
}

func (ns *Nodes) clear() {
	clear(*ns)
	*ns = (*ns)[:0]
}

func (ns *Nodes) free() {
	ns.clear()
	if cap(*ns) > 1000 {
		return
	}
	nodesPool.Put(ns)
}