trie

Documentation

Index

• type Edge
• type Node
  • func NewNode() *Node
  • func (node *Node) BFS(callback WalkCallback)
  • func (node *Node) Children() []*Node
  • func (node *Node) Condense() error
  • func (node *Node) Count() int
  • func (node *Node) DFS(callback WalkCallback)
  • func (node *Node) GetEdge(item interface{}) *Edge
  • func (node *Node) GetEdges() []*Edge
  • func (node *Node) Insert(prefix interface{}) error
• type WalkCallback

Types

type Edge

type Edge struct {
	PrefixCount int
	Prefix      interface{}
}

Edge is the connection between two nodes

type Node

type Node struct {
	Edges     map[*Edge]*Node
	IsMutable bool
	DataCount int
}

Node implementing NodeInterface

func NewNode

func NewNode() *Node

NewNode creates new trie node

func (*Node) BFS

func (node *Node) BFS(callback WalkCallback)

BFS performs breadth first search on the trie and calls callback with each node element

func (*Node) Children

func (node *Node) Children() []*Node

Children returns all direct children for a trie node

func (*Node) Condense

func (node *Node) Condense() error

Condense marks the trie as un-mutable and in case parent has single child, it merges itself with parent node. Prefix interface must support Addition operation, otherwise it will cause panic.

func (*Node) Count

func (node *Node) Count() int

Count returns sum of items passing through this node i.e. prefix and data counts

func (*Node) DFS

func (node *Node) DFS(callback WalkCallback)

DFS performs breadth first search on the trie and calls callback with each node element and prefix till now

func (*Node) GetEdge

func (node *Node) GetEdge(item interface{}) *Edge

GetEdge returns edge if it exists from current node, otherwise returns nil

func (*Node) GetEdges

func (node *Node) GetEdges() []*Edge

GetEdges returns edges of the node in the sorted order of prefixes

func (*Node) Insert

func (node *Node) Insert(prefix interface{}) error

Insert adds new element into trie

type WalkCallback

type WalkCallback func(interface{}, int)

WalkCallback is a callback for the bfs/dfs functions