trie

README

Trie

Implementation of "Trie" data structure

See https://en.wikipedia.org/wiki/Trie. Why yet another "trie" implementation?

Some of them do not expose needed methods like traversing, some of them do not expose parents or children. And some of them just plain peculiar. At least I think so :)

Install

go get github.com/markelog/trie

Usage

Simple example here, see docs for more stuff and explanations

package main

import (
	"github.com/markelog/trie"
	"github.com/markelog/trie/node"
)

func main() {
	tree := trie.New()

	tree.Add("cool", "So cool")
	tree.Add("coolio", 54) // Age of his at the moment of writing

	println(tree.Size) // 2

	println(tree.Contains("cool")) // true

	println(len(tree.Root.Children))   // 1
	println(tree.Root.Children[0].Key) // "cool"

	results := tree.Search("cool") // []string{"cool", "coolio"}
	cool := results[0]

	println(cool.Value.(string))  // "So cool"
	println(cool.Children[0].Key) // "coolio"

	coolio := tree.Find("coolio")

	println(coolio.Value.(int)) // 54

	println(coolio.Key)        // "coolio"
	println(coolio.Parent.Key) // "cool"

	i := 0
	tree.Traverse(func(item *node.Node) bool {
		i++
		return true
	})

	println(i) // 2

	i = 0
	tree.Visit(cool, func(item *node.Node) bool {
		i++
		return true
	})

	println(i) // 1

	// Including branches
	i = 0
	tree.VisitAll(cool, func(item *node.Node) bool {
		i++
		return true
	})

	println(i) // 2
}

Documentation

Overview

Package trie implements the trie data structure See https://en.wikipedia.org/wiki/Trie

Index

• type Trie
  • func New() *Trie
  • func (trie *Trie) Add(key string, value interface{}) (result *node.Node)
  • func (trie Trie) Contains(key string) bool
  • func (trie Trie) Find(key string) *node.Node
  • func (trie *Trie) Remove(key string) bool
  • func (trie Trie) Search(prefix string) (result []*node.Node)
  • func (trie Trie) Traverse(fn Walker)
  • func (trie Trie) Visit(current *node.Node, fn Walker)
  • func (trie Trie) VisitAll(current *node.Node, fn Walker)
  • func (trie *Trie) Yank(key string) bool
• type Walker

Types

type Trie

type Trie struct {

	// Root node
	Root *node.Node

	// Size of the trie (counting only the leafs)
	Size int
}

Trie essential structure

func New

func New() *Trie

New returns new Trie

func (*Trie) Add

func (trie *Trie) Add(key string, value interface{}) (result *node.Node)

Add stuff to the trie

func (Trie) Contains

func (trie Trie) Contains(key string) bool

Contains check presence of the key in the trie

func (Trie) Find

func (trie Trie) Find(key string) *node.Node

Find specific one full matched key

func (*Trie) Remove

func (trie *Trie) Remove(key string) bool

Remove removes subtree of the exact key match

func (Trie) Search

func (trie Trie) Search(prefix string) (result []*node.Node)

Search returns every word with the given prefix

func (Trie) Traverse

func (trie Trie) Traverse(fn Walker)

Traverse the leaves (not the branches)

func (Trie) Visit

func (trie Trie) Visit(current *node.Node, fn Walker)

Visit specific part of the tree

func (Trie) VisitAll

func (trie Trie) VisitAll(current *node.Node, fn Walker)

VisitAll allows visit every node

func (*Trie) Yank

func (trie *Trie) Yank(key string) bool

Yank removes only one leaf not the subtree. Difference with Remove() is that Yank does not removes the leaf subtree, still removes the branches though

type Walker

type Walker func(item *node.Node) bool

Walker for the traverse function If such function returns false it will stop traverse