rbtree

package
v1.3.27 Latest Latest
Warning

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

 Go to latest Published: Aug 11, 2023 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	RED   = false
	BLACK = true
)

Define node 's colors

Variables

View Source 
var ErrorNotFound = errors.New("not found")

Functions

This section is empty.

Types

type Color 

type Color bool

Color defines node color type

type Node 

type Node[K, V any] struct {
	// contains filtered or unexported fields
}

Node is a tree node

func (*Node[K, V]) Key 

func (n *Node[K, V]) Key() K

Key returns node's key

func (*Node[K, V]) Next 

func (n *Node[K, V]) Next() *Node[K, V]

Next returns the Node's successor as an iterator.

func (*Node[K, V]) Prev 

func (n *Node[K, V]) Prev() *Node[K, V]

Prev returns the Node's predecessor as an iterator.

func (*Node[K, V]) SetValue 

func (n *Node[K, V]) SetValue(val V)

SetValue sets node's value

func (*Node[K, V]) Value 

func (n *Node[K, V]) Value() V

Value returns node's value

type Option added in v1.3.3 

type Option func(option *Options)

Option is a function type used to set Options

func WithGoroutineSafe added in v1.3.3 

func WithGoroutineSafe() Option

WithGoroutineSafe is used to set the set goroutine-safe Note that iterators are not goroutine safe, and it is useless to turn on the setting option here. so don't use iterators in multi goroutines

type Options added in v1.3.3 

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

Options holds the Set's options

type RbTree 

type RbTree[K, V any] struct {
	// contains filtered or unexported fields
}

RbTree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

func New 

func New[K, V any](cmp comparator.Comparator[K]) *RbTree[K, V]

New creates a new RbTree

func (*RbTree[K, V]) Begin 

func (t *RbTree[K, V]) Begin() *Node[K, V]

Begin returns the node with minimum key in the RbTree

func (*RbTree[K, V]) Clear 

func (t *RbTree[K, V]) Clear()

Clear clears the RbTree

func (*RbTree[K, V]) Contains added in v1.3.13 

func (t *RbTree[K, V]) Contains(key K) bool

func (*RbTree[K, V]) Delete 

func (t *RbTree[K, V]) Delete(node *Node[K, V])

Delete deletes node from the RbTree

func (*RbTree[K, V]) Empty 

func (t *RbTree[K, V]) Empty() bool

Empty returns true if Tree is empty,otherwise returns false.

func (*RbTree[K, V]) Find 

func (t *RbTree[K, V]) Find(key K) (V, error)

Find finds the first node that the key is equal to the passed key, and returns its value

func (*RbTree[K, V]) FindLowerBoundNode 

func (t *RbTree[K, V]) FindLowerBoundNode(key K) *Node[K, V]

FindLowerBoundNode finds the first node that its key is equal or greater than the passed key, and returns it 返回 >=key 的node

func (*RbTree[K, V]) FindNode 

func (t *RbTree[K, V]) FindNode(key K) *Node[K, V]

FindNode the first node that the key is equal to the passed key and return it

func (*RbTree[K, V]) FindUpperBoundNode 

func (t *RbTree[K, V]) FindUpperBoundNode(key K) *Node[K, V]

FindUpperBoundNode finds the first node that its key is greater than the passed key, and returns it 从key开始向上找 用正序查找 返回大于或者等于key的第一个值 ，从最小值开始查找. next

func (*RbTree[K, V]) First 

func (t *RbTree[K, V]) First() *Node[K, V]

First returns the node with minimum key in the RbTree

func (*RbTree[K, V]) Get added in v1.3.3 

func (t *RbTree[K, V]) Get(key K) (V, bool)

Find finds the first node that the key is equal to the passed key, and returns its value

func (*RbTree[K, V]) GetOrSet added in v1.3.9 

func (t *RbTree[K, V]) GetOrSet(key K, value V) (V, bool)

获取，如果没有则设置， 是否找到

func (*RbTree[K, V]) GetOrSetFunc added in v1.3.9 

func (t *RbTree[K, V]) GetOrSetFunc(key K, fn func() V) (V, bool)

func (*RbTree[K, V]) Insert 

func (t *RbTree[K, V]) Insert(key K, value V)

这个地方如果key，已经存在了，还是会添加，会出现多个相同的key Insert inserts a key-value pair into the RbTree.

func (*RbTree[K, V]) IsRbTree 

func (t *RbTree[K, V]) IsRbTree() (bool, error)

IsRbTree is a function use to test whether t is a RbTree or not

func (*RbTree[K, V]) IterFirst 

func (t *RbTree[K, V]) IterFirst() *RbTreeIterator[K, V]

IterFirst returns the iterator of first node

func (*RbTree[K, V]) IterLast 

func (t *RbTree[K, V]) IterLast() *RbTreeIterator[K, V]

IterLast returns the iterator of first node

func (*RbTree[K, V]) IteratorAsc added in v1.3.1 

func (t *RbTree[K, V]) IteratorAsc(visitor visitor.KvVisitor[K, V])

IteratorDesc traversals elements in the RbTree, it will not stop until to the end of RbTree or the visitor returns false

func (*RbTree[K, V]) IteratorDesc added in v1.3.1 

func (t *RbTree[K, V]) IteratorDesc(visitor visitor.KvVisitor[K, V])

IteratorDesc traversals elements in the RbTree, it will not stop until to the end of RbTree or the visitor returns false

func (*RbTree[K, V]) Keys added in v1.3.1 

func (t *RbTree[K, V]) Keys() []K

func (*RbTree[K, V]) Last 

func (t *RbTree[K, V]) Last() *Node[K, V]

Last returns the Node with maximum key in the RbTree

func (*RbTree[K, V]) RBegin 

func (t *RbTree[K, V]) RBegin() *Node[K, V]

RBegin returns the Node with maximum key in the RbTree

func (*RbTree[K, V]) Remove added in v1.3.15 

func (t *RbTree[K, V]) Remove(key K) (V, bool)

func (*RbTree[K, V]) Search added in v1.3.8 

func (t *RbTree[K, V]) Search(key K) (V, bool)

func (*RbTree[K, V]) Set added in v1.3.9 

func (t *RbTree[K, V]) Set(key K, value V) V

如果存在，则进行替换。返回旧值

func (*RbTree[K, V]) SetIfNotExist added in v1.3.14 

func (t *RbTree[K, V]) SetIfNotExist(key K, value V) bool

func (*RbTree[K, V]) Size 

func (t *RbTree[K, V]) Size() int

Size returns the size of the rbtree.

func (*RbTree[K, V]) String added in v1.3.17 

func (t *RbTree[K, V]) String() string

func (*RbTree[K, V]) Traversal 

func (t *RbTree[K, V]) Traversal(visitor visitor.KvVisitor[K, V])

Traversal traversals elements in the RbTree, it will not stop until to the end of RbTree or the visitor returns false

func (*RbTree[K, V]) Values added in v1.3.10 

func (t *RbTree[K, V]) Values() []V

type RbTreeIterator 

type RbTreeIterator[K, V any] struct {
	// contains filtered or unexported fields
}

RbTreeIterator is an iterator implementation of RbTree

func NewIterator 

func NewIterator[K, V any](node *Node[K, V]) *RbTreeIterator[K, V]

NewIterator creates a RbTreeIterator from the passed node

func (*RbTreeIterator[K, V]) Clone 

func (iter *RbTreeIterator[K, V]) Clone() iterator.ConstIterator[V]

Clone clones the iterator into a new RbTreeIterator

func (*RbTreeIterator[K, V]) Equal 

func (iter *RbTreeIterator[K, V]) Equal(other iterator.ConstIterator[V]) bool

Equal returns true if the iterator is equal to the passed iterator

func (*RbTreeIterator[K, V]) IsValid 

func (iter *RbTreeIterator[K, V]) IsValid() bool

IsValid returns true if the iterator is valid, otherwise returns false

func (*RbTreeIterator[K, V]) Key 

func (iter *RbTreeIterator[K, V]) Key() K

Key returns the node's key of the iterator point to

func (*RbTreeIterator[K, V]) Next 

func (iter *RbTreeIterator[K, V]) Next() iterator.ConstIterator[V]

Next moves the pointer of the iterator to the next node, and returns itself

func (*RbTreeIterator[K, V]) Prev 

func (iter *RbTreeIterator[K, V]) Prev() iterator.ConstBidIterator[V]

Prev moves the pointer of the iterator to the previous node, and returns itself

func (*RbTreeIterator[K, V]) SetValue 

func (iter *RbTreeIterator[K, V]) SetValue(val V) error

SetValue sets the node's value of the iterator point to

func (*RbTreeIterator[K, V]) Value 

func (iter *RbTreeIterator[K, V]) Value() V

Value returns the node's value of the iterator point to

type RbTreeSync added in v1.3.3 

type RbTreeSync[K, V any] struct {
	Tree *RbTree[K, V]
	Lock sync.Locker
	// contains filtered or unexported fields
}

func NewSync added in v1.3.3 

func NewSync[K, V any](cmp comparator.Comparator[K], opts ...Option) *RbTreeSync[K, V]

New creates a new NewSync

func (*RbTreeSync[K, V]) Contains added in v1.3.13 

func (t *RbTreeSync[K, V]) Contains(key K) bool

func (*RbTreeSync[K, V]) Diff added in v1.3.21 

func (t *RbTreeSync[K, V]) Diff(other *RbTreeSync[K, V]) *RbTreeSync[K, V]

Diff returns a new set with the elements in the set s but not in the passed set Please ensure s set and other set uses the same keyCmp 返回 other 中没有的部分

func (*RbTreeSync[K, V]) Empty added in v1.3.3 

func (t *RbTreeSync[K, V]) Empty() bool

Empty returns true if Tree is empty,otherwise returns false.

func (*RbTreeSync[K, V]) Get added in v1.3.3 

func (t *RbTreeSync[K, V]) Get(key K) (V, bool)

Find finds the first node that the key is equal to the passed key, and returns its value

func (*RbTreeSync[K, V]) GetOrSet added in v1.3.9 

func (t *RbTreeSync[K, V]) GetOrSet(key K, value V) (V, bool)

获取，如果没有则设置， 是否找到

func (*RbTreeSync[K, V]) GetOrSetFunc added in v1.3.9 

func (t *RbTreeSync[K, V]) GetOrSetFunc(key K, fn func() V) (V, bool)

func (*RbTreeSync[K, V]) Insert added in v1.3.3 

func (t *RbTreeSync[K, V]) Insert(key K, value V)

这个地方如果key，已经存在了，还是会添加，会出现多个相同的key

func (*RbTreeSync[K, V]) Intersect added in v1.3.21 

func (t *RbTreeSync[K, V]) Intersect(other *RbTreeSync[K, V]) *RbTreeSync[K, V]

Intersect returns a new set with the common elements in the set s and the passed set Please ensure s set and other set uses the same keyCmp

func (*RbTreeSync[K, V]) IsDiff added in v1.3.21 

func (t *RbTreeSync[K, V]) IsDiff(other *RbTreeSync[K, V]) bool

如果不同返回true，相同返回false

func (*RbTreeSync[K, V]) IsIntersect added in v1.3.23 

func (t *RbTreeSync[K, V]) IsIntersect(other *RbTreeSync[K, V]) bool

如果交叉返回true ，否则 false

func (*RbTreeSync[K, V]) IteratorAsc added in v1.3.3 

func (t *RbTreeSync[K, V]) IteratorAsc(visitor visitor.KvVisitor[K, V])

IteratorDesc traversals elements in the RbTree, it will not stop until to the end of RbTree or the visitor returns false

func (*RbTreeSync[K, V]) IteratorDesc added in v1.3.3 

func (t *RbTreeSync[K, V]) IteratorDesc(visitor visitor.KvVisitor[K, V])

IteratorDesc traversals elements in the RbTree, it will not stop until to the end of RbTree or the visitor returns false

func (*RbTreeSync[K, V]) Keys added in v1.3.3 

func (t *RbTreeSync[K, V]) Keys() []K

func (*RbTreeSync[K, V]) Remove added in v1.3.3 

func (t *RbTreeSync[K, V]) Remove(key K) (V, bool)

func (*RbTreeSync[K, V]) Search added in v1.3.9 

func (t *RbTreeSync[K, V]) Search(key K) (V, bool)

func (*RbTreeSync[K, V]) Set added in v1.3.9 

func (t *RbTreeSync[K, V]) Set(key K, value V) V

如果存在，则进行替换。返回旧值

func (*RbTreeSync[K, V]) SetIfNotExist added in v1.3.14 

func (t *RbTreeSync[K, V]) SetIfNotExist(key K, value V) bool

func (*RbTreeSync[K, V]) Size added in v1.3.3 

func (t *RbTreeSync[K, V]) Size() int

Size returns the size of the rbtree.

func (*RbTreeSync[K, V]) String added in v1.3.17 

func (t *RbTreeSync[K, V]) String() string

func (*RbTreeSync[K, V]) UnIntersect added in v1.3.21 

func (t *RbTreeSync[K, V]) UnIntersect(other *RbTreeSync[K, V]) *RbTreeSync[K, V]

Union returns a new set with the all elements in the set s and the passed set Please ensure s set and other set uses the same keyCmp 和 Intersect 相反 ，返回两个不同部分

func (*RbTreeSync[K, V]) Union added in v1.3.21 

func (t *RbTreeSync[K, V]) Union(other *RbTreeSync[K, V]) *RbTreeSync[K, V]

Union returns a new set with the all elements in the set s and the passed set Please ensure s set and other set uses the same keyCmp

func (*RbTreeSync[K, V]) Values added in v1.3.13 

func (t *RbTreeSync[K, V]) Values() []V

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.