container

package
v1.0.9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 27, 2022 License: Apache-2.0 Imports: 9 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	LH = 1
	EH = 0
	RH = -1
)
View Source 
const (
	RED nodeColor = iota
	BLACK
)

Variables

This section is empty.

Functions

This section is empty.

Types

type AvlTraverseFunc added in v1.0.5 

type AvlTraverseFunc func(node *avlTreeNode) bool

type BalancedBinarySearchTree 

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

BalancedBinarySearchTree implements balanced binary search tree (AVL tree).

func NewBinarySearchTree 

func NewBinarySearchTree(values []NodeValue) (*BalancedBinarySearchTree, error)

NewBinarySearchTree creates AVL tree from slice.

func (*BalancedBinarySearchTree) Delete 

func (t *BalancedBinarySearchTree) Delete(value NodeValue) bool

Delete deletes specified node and keeps the tree an AVL tree. It should take O(logN) time.

func (*BalancedBinarySearchTree) Exist 

func (t *BalancedBinarySearchTree) Exist(value NodeValue) bool

Exist returns whether the value exists.

func (*BalancedBinarySearchTree) Height 

func (t *BalancedBinarySearchTree) Height() int

Height returns height of tree.

func (*BalancedBinarySearchTree) Insert 

func (t *BalancedBinarySearchTree) Insert(value NodeValue)

Insert inserts a new node and keeps the tree an AVL tree. It should take O(logN) time.

func (*BalancedBinarySearchTree) PrettyPrint 

func (t *BalancedBinarySearchTree) PrettyPrint() string

PrettyPrint returns the formatted string of the tree.

func (*BalancedBinarySearchTree) Size 

func (t *BalancedBinarySearchTree) Size() int

Size returns size of tree.

func (*BalancedBinarySearchTree) String 

func (t *BalancedBinarySearchTree) String() string

String returns the inorder sequence and preorder sequence.

func (*BalancedBinarySearchTree) Traverse 

func (t *BalancedBinarySearchTree) Traverse(f func(value NodeValue) bool, order TraverseOrder)

Traverse traverse tree with specified order and call the function for each non-nil node.

func (*BalancedBinarySearchTree) Validate 

func (t *BalancedBinarySearchTree) Validate() bool

Validate returns whether the tree is AVL tree which can be asserted true.

type BinarySearchTree added in v1.0.6 

type BinarySearchTree interface {
	// Height returns height of tree.
	Height() int
	// Size returns size of tree.
	Size() int
	Insert(value NodeValue)
	Delete(value NodeValue) bool
	Validate() bool
	Traverse(f func(value NodeValue) bool, order TraverseOrder)
	String() string
	PrettyPrint() string
	Exist(value NodeValue) bool
}

type ExpiringSet 

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

func NewExpiringSet 

func NewExpiringSet(expirationTime time.Duration) *ExpiringSet

func (*ExpiringSet) Add 

func (s *ExpiringSet) Add(value interface{})

func (*ExpiringSet) Exists 

func (s *ExpiringSet) Exists(value interface{}) bool

type Item 

type Item []ItemValue

func (Item) Len 

func (item Item) Len() int

func (Item) Less 

func (item Item) Less(i, j int) bool

func (Item) Peek 

func (item Item) Peek() *ItemValue

func (*Item) Pop 

func (item *Item) Pop() interface{}

func (*Item) Push 

func (item *Item) Push(x interface{})

func (Item) Swap 

func (item Item) Swap(i, j int)

type ItemValue 

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

type LimitedBinarySearchQueue added in v1.0.6 

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

LimitedBinarySearchQueue is a queue that supports binary search, or an Binary-Search tree that supports FIFO operations.

func NewLimitedQueueBinarySearch added in v1.0.6 

func NewLimitedQueueBinarySearch(values []NodeValue, capacity int) *LimitedBinarySearchQueue

NewLimitedQueueBinarySearch creates red-black tree from slice.

func (*LimitedBinarySearchQueue) Delete added in v1.0.6 

func (t *LimitedBinarySearchQueue) Delete(value NodeValue) bool

func (*LimitedBinarySearchQueue) Exist added in v1.0.6 

func (t *LimitedBinarySearchQueue) Exist(value NodeValue) bool

func (*LimitedBinarySearchQueue) Height added in v1.0.6 

func (t *LimitedBinarySearchQueue) Height() int

func (*LimitedBinarySearchQueue) Insert added in v1.0.6 

func (t *LimitedBinarySearchQueue) Insert(value NodeValue)

func (*LimitedBinarySearchQueue) PrettyPrint added in v1.0.6 

func (t *LimitedBinarySearchQueue) PrettyPrint() string

func (*LimitedBinarySearchQueue) Size added in v1.0.6 

func (t *LimitedBinarySearchQueue) Size() int

func (*LimitedBinarySearchQueue) String added in v1.0.6 

func (t *LimitedBinarySearchQueue) String() string

func (*LimitedBinarySearchQueue) Traverse added in v1.0.6 

func (t *LimitedBinarySearchQueue) Traverse(f func(value NodeValue) bool, order TraverseOrder)

func (*LimitedBinarySearchQueue) Validate added in v1.0.6 

func (t *LimitedBinarySearchQueue) Validate() bool

type NodeValue 

type NodeValue interface {
	// Compare method compares with another NodeValue and return 1 if greater, 0 if equal, -1 if less.
	Compare(value NodeValue) int

	// Stringer whose String() method would return formatted string.
	fmt.Stringer
}

NodeValue represents the element type storing in tree.

type RbTraverseFunc added in v1.0.5 

type RbTraverseFunc func(node *rbTreeNode) bool

traverse function that iterates over the tree. Traverse would stop if RbTraverseFunc returns false

type RedBlackTree 

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

RedBlackTree implements red-black tree. Refers to https://mp.weixin.qq.com/s/4sCnvWmW7-fOIlpNeIIjIw

func NewRedBlackTree 

func NewRedBlackTree(values []NodeValue) *RedBlackTree

NewRedBlackTree creates red-black tree from slice.

func (*RedBlackTree) Delete 

func (t *RedBlackTree) Delete(value NodeValue) bool

Delete deletes specified node and keeps the tree an red-black tree. It should take O(logN) time.

func (*RedBlackTree) Exist 

func (t *RedBlackTree) Exist(value NodeValue) bool

Exist returns whether the value exists.

func (*RedBlackTree) Height 

func (t *RedBlackTree) Height() int

func (*RedBlackTree) Insert 

func (t *RedBlackTree) Insert(value NodeValue)

Insert inserts a new node and keeps the tree an red-black tree. It should take O(logN) time.

func (*RedBlackTree) PopMax added in v1.0.5 

func (t *RedBlackTree) PopMax(atMost NodeValue, delete bool) NodeValue

PopMax pops the maximum value. If delete flag is set, delete the node. If atMost is not nil, pops the maximum value which is less than that.

func (*RedBlackTree) PopMin added in v1.0.5 

func (t *RedBlackTree) PopMin(atLeast NodeValue, delete bool) NodeValue

PopMin pops the minimum value. If delete flag is set, delete the node. If atLeast is not nil, pops the minimum value which is larger than that.

func (*RedBlackTree) PrettyPrint 

func (t *RedBlackTree) PrettyPrint() string

PrettyPrint returns the formatted string of the tree.

func (*RedBlackTree) Size 

func (t *RedBlackTree) Size() int

func (*RedBlackTree) String 

func (t *RedBlackTree) String() string

String returns the inorder sequence and preorder sequence.

func (*RedBlackTree) Traverse 

func (t *RedBlackTree) Traverse(f func(value NodeValue) bool, order TraverseOrder)

Traverse traverse tree with specified order and call the function for each non-nil node.

func (*RedBlackTree) Validate 

func (t *RedBlackTree) Validate() bool

Validate returns whether the tree is a red-black tree which should be asserted true.

type Slice 

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

func Of 

func Of(slice interface{}) *Slice

Of constructs a Slice object from a go slice, if argument is not a valid slice, a specific Slice Object would be returned which any operations on it would failed.

func (*Slice) Element 

func (s *Slice) Element() (interface{}, error)

Element gets the underlying slice.

func (*Slice) Error 

func (s *Slice) Error() error

func (*Slice) ListExist 

func (s *Slice) ListExist(element interface{}) bool

ListExist returns whether element exists in list. Note it returns false if any type errors happens.

func (*Slice) Remove 

func (s *Slice) Remove(element interface{}) *Slice

Remove removes element from list and return the result list with original list not modified. Note it removes only the first element found.

type TraverseOrder 

type TraverseOrder int
const (
	// PreOrder parent-left-right
	PreOrder TraverseOrder = iota
	// InOrder left-parent-right
	InOrder
	// PostOrder left-right-parent
	PostOrder
	// ReversedOrder right-parent-left
	ReversedOrder
)

type TreeIterator added in v1.0.5 

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

func CreateTreeIterator added in v1.0.7 

func CreateTreeIterator(tree BinarySearchTree, from NodeValue, to NodeValue, order TraverseOrder) (*TreeIterator, error)

func (TreeIterator) Close added in v1.0.5 

func (iter TreeIterator) Close()

func (TreeIterator) HasNext added in v1.0.5 

func (iter TreeIterator) HasNext() bool

func (TreeIterator) Next added in v1.0.5 

func (iter TreeIterator) Next() NodeValue

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.