st

Documentation

Overview

Package st provides symbol table data structures.

Deprecated: this package has been frozen and deprecated in favor of github.com/moorara/algo/ds/st

Index

• Constants
• type KeyValue
• type OrderedSymbolTable
  • func NewAVL(compareKey func(a, b interface{}) int) OrderedSymbolTable
  • func NewBST(compareKey func(a, b interface{}) int) OrderedSymbolTable
  • func NewRedBlack(compareKey func(a, b interface{}) int) OrderedSymbolTable
• type SymbolTable
• type VisitFunc

Constants

const (
	// TraversePreOrder represents pre-order traversal order
	TraversePreOrder = 0
	// TraverseInOrder represents in-order traversal order
	TraverseInOrder = 1
	// TraversePostOrder represents post-order traversal order
	TraversePostOrder = 2
)

Types

type KeyValue

type KeyValue struct {
	// contains filtered or unexported fields
}

KeyValue represents a key-value pair

type OrderedSymbolTable

type OrderedSymbolTable interface {
	SymbolTable
	Min() (interface{}, interface{})
	Max() (interface{}, interface{})
	Floor(interface{}) (interface{}, interface{})
	Ceiling(interface{}) (interface{}, interface{})
	Rank(interface{}) int
	Select(int) (interface{}, interface{})
	DeleteMin() (interface{}, interface{})
	DeleteMax() (interface{}, interface{})
	RangeSize(interface{}, interface{}) int
	Range(interface{}, interface{}) []KeyValue
	Traverse(int, VisitFunc)
	Graphviz() string
}

OrderedSymbolTable represents an ordered symbol table (key-value collection)

func NewAVL

func NewAVL(compareKey func(a, b interface{}) int) OrderedSymbolTable

NewAVL creates a new AVL Tree

func NewBST

func NewBST(compareKey func(a, b interface{}) int) OrderedSymbolTable

NewBST creates a new Binary Search Tree

func NewRedBlack

func NewRedBlack(compareKey func(a, b interface{}) int) OrderedSymbolTable

NewRedBlack creates a new Red-Black Tree

type SymbolTable

type SymbolTable interface {
	Size() int
	Height() int
	IsEmpty() bool
	Put(interface{}, interface{})
	Get(interface{}) (interface{}, bool)
	Delete(interface{}) (interface{}, bool)
	KeyValues() []KeyValue
	// contains filtered or unexported methods
}

SymbolTable represents an unordered symbol table (key-value collection)

type VisitFunc

type VisitFunc func(interface{}, interface{}) bool

VisitFunc represents the function for visting a key-value