trie

Documentation

Overview

Package trie implements a general purpose Path-*Node.

Index

• func SplitPath(path string) []string
• type Node
  • func NewNode() *Node
  • func NewNodeWithData(data interface{}) *Node
  • func (n *Node) Insert(path string) *Node
  • func (n *Node) InsertWithData(path string, data interface{}) *Node
  • func (n *Node) Len() int64
  • func (n *Node) Lookup(path string) *Node
  • func (n *Node) Path() string
  • func (n *Node) Print()
  • func (n *Node) Remove() *Node
  • func (n *Node) Root() *Node
  • func (n *Node) String() string
  • func (n *Node) Up(visit func(*Node))
  • func (n *Node) Walk(dfs bool, visit func(*Node) bool)

Functions

func SplitPath

func SplitPath(path string) []string

SplitPath splits the path according to os.PathSeparator, but omits a leading empty name on /unix/paths

Types

type Node

type Node struct {
	// Pointer to parent node or nil
	Parent *Node

	// Basename to child-nodes
	Children map[string]*Node

	// Basename of the node's Path
	Name string

	// Number of explicitly added children of this node.
	// (1 for leaf nodes)
	Length int64

	// Depth of the node. The root is at depth 0.
	Depth uint16

	// Arbitrary data pointer
	Data interface{}
}

Node represents a single node in a *Node, but it can be used as a whole (sub-)*Node through the *Node interface. A node value of `nil` is a perfectly valid trie. Node is suitable for embedding it into other structs.

func NewNode

func NewNode() *Node

NewNode returns a trie with the root element pre-inserted. Note that `nil` is a perfectly valid, but empty trie.

func NewNodeWithData

func NewNodeWithData(data interface{}) *Node

NewNodeWithData works like NewNode but populates the .Data field.

func (*Node) Insert

func (n *Node) Insert(path string) *Node

Insert adds a node into the trie at `path`

func (*Node) InsertWithData

func (n *Node) InsertWithData(path string, data interface{}) *Node

InsertWithData adds a node into the trie at `path`, storing `data` in the Node.Data field. If the node already exists, data will be set anyways.

func (*Node) Len

func (n *Node) Len() int64

Len returns the number of explicitly inserted elements in the trie.

func (*Node) Lookup

func (n *Node) Lookup(path string) *Node

Lookup searches a Node by it's absolute path. Returns nil if Node does not exist.

func (*Node) Path

func (n *Node) Path() string

Path returns a full absolute path from the receiver to the root node of the trie.

func (*Node) Print

func (n *Node) Print()

Print dumps a debugging representation of the trie on stdout.

func (*Node) Remove

func (n *Node) Remove() *Node

Remove removes the receiver and all of it's children. The removed node's parent is returned.

func (*Node) Root

func (n *Node) Root() *Node

Root returns the root node of the trie.

func (*Node) String

func (n *Node) String() string

String returns the absolute path of the node.

func (*Node) Up

func (n *Node) Up(visit func(*Node))

Up walks from the receiving node to the root node, calling `visit` on each node on it's way.

func (*Node) Walk

func (n *Node) Walk(dfs bool, visit func(*Node) bool)

Walk iterates over all (including intermediate )nodes in the trie. Depending on dfs the nodes are visited in depth-first or breadth-first. The supplied callback is called once for each visited node.