Documentation
¶
Index ¶
- type Node
- type Option
- type Tree
- func New[K comparable, V any](cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromMap[K comparable, V any](m map[K]V, cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromOrderedMap[K cmp.Ordered, V any](m map[K]V, ops ...Option[K, V]) (*Tree[K, V], error)
- func NewFromSlice[V any](slice []V, ops ...Option[int, V]) (*Tree[int, V], error)
- func NewOrderedKeys[K cmp.Ordered, V any](ops ...Option[K, V]) (*Tree[K, V], error)
- func (t *Tree[K, V]) Ceiling(key K) (K, V, bool)
- func (t *Tree[K, V]) Clear()
- func (t *Tree[K, V]) Delete(key K) (V, bool)
- func (t *Tree[K, V]) Floor(key K) (K, V, bool)
- func (t *Tree[K, V]) Get(key K) (V, bool)
- func (t *Tree[K, V]) InOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) IsEmpty() bool
- func (t *Tree[K, V]) Keys() []K
- func (t *Tree[K, V]) LevelOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) MarshalJSON() ([]byte, error)
- func (t *Tree[K, V]) Max() (K, V, bool)
- func (t *Tree[K, V]) Min() (K, V, bool)
- func (t *Tree[K, V]) PostOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) PreOrder(fn func(key K, value V) bool)
- func (t *Tree[K, V]) Put(key K, val V)
- func (t *Tree[K, V]) Size() int
- func (t *Tree[K, V]) String() string
- func (t *Tree[K, V]) UnmarshalJSON(data []byte) error
- func (t *Tree[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[K comparable, V any] struct { Key K Value V Parent *Node[K, V] Children [2]*Node[K, V] }
type Option ¶
type Option[K comparable, V any] func(*Tree[K, V]) error
Option is a functional option type for configuring a splay tree.
func WithNodeFormat ¶
func WithNodeFormat[K comparable, V any](format string) Option[K, V]
WithNodeFormat creates a option that sets the node format when call tree.String(). Default node format is fmt.Sprintf("%v", n.Key). The format must contains two placeholders, the first is the key and the second is the value. For example: "%d:%s"
func WithSafe ¶
func WithSafe[K comparable, V any]() Option[K, V]
WithSafe creates a option that make the splay tree safe for concurrent use.
type Tree ¶
type Tree[K comparable, V any] struct { // contains filtered or unexported fields }
Tree represents a generic splay tree. It support keys of any comparable type and value of any type. The tree use a custom comparison function to matain order.
func New ¶
New creates and returns a splay tree. The provided function "cmp" is determines the order of the keys.
func NewFromMap ¶
func NewFromMap[K comparable, V any](m map[K]V, cmp func(K, K) int, ops ...Option[K, V]) (*Tree[K, V], error)
NewFromMap creates and returns a splay tree from a given map. The provided function "cmp" is determines the order of the keys.
func NewFromOrderedMap ¶
NewFromOrderedMap creates and returns a splay tree from a given map. It uses cmp.Compare[K] as the default comparison function, which is suitable for types that implement the cmp.Ordered interface, such as int, float64, and string.
func NewFromSlice ¶
NewFromSlice creates and returns a splay tree from a given slice. It use the cmp.Compare[K] as the default comparsion function.
func NewOrderedKeys ¶
NewOrderedKeys creates and returns a splay tree. It use the cmp.Compare[K] as the default comparsion function. This is suitable for types that implement the cmp.Ordered interface, such as int, float64 and string
func (*Tree[K, V]) Ceiling ¶
Ceiling returns the smallest key in the tree that is greater than or equal to the given key. If no such key exists, returns zero values and false. If the exact key exists, returns that key-value pair and true.
This operation modifies the tree structure due to splaying if found.
func (*Tree[K, V]) Delete ¶
Delete removes the node with the given key from the tree. It returns the value associated with the key and true if found, otherwise returns the zero value and false. The operation maintains the BST property by promoting the maximum node of the left subtree when deleting a node with two children.
func (*Tree[K, V]) Floor ¶
Floor returns the largest key in the tree that is less than or equal to the given key. If no such key exists, returns zero values and false. If the exact key exists, returns that key-value pair and true.
This operation modifies the tree structure due to splaying if found.
func (*Tree[K, V]) Get ¶
Get retrieves the value associated with the given key. It returns the value and true if the key exists, otherwise returns the zero value and false. The accessed node will be splayed to the root if found.
func (*Tree[K, V]) InOrder ¶
InOrder traverses the tree in-order (left-root-right) fashion, calling the provided function for each node. If the function returns false, the traversal is stopped. The traversal visits nodes in ascending order of keys.
Unlike Get/Put operations, InOrder does not perform any splay operations.
func (*Tree[K, V]) IsEmpty ¶
IsEmpty returns true if the tree contains no elements, false otherwise.
func (*Tree[K, V]) Keys ¶
func (t *Tree[K, V]) Keys() []K
Keys returns a sorted slice of all keys in the tree.
Unlink Get/Put operations, this operation does not perform any splay operations.
func (*Tree[K, V]) LevelOrder ¶
LevelOrder traverses the tree in level-order (breadth-first) fashion, calling the provided function for each node. If the function returns false, the traversal is stopped.
Unlike Get/Put operations, LevelOrder does not perform any splay operations.
func (*Tree[K, V]) MarshalJSON ¶
MarshalJSON implements the json.Marshaler interface.
func (*Tree[K, V]) Max ¶
Max returns the maximum key in the tree and its associated value. If the tree is empty, it returns the zero values for K and V, and false. Otherwise returns the key-value pair and true.
This operation modifies the tree structure due to splaying if found.
func (*Tree[K, V]) Min ¶
Min returns the minimum key in the tree and its associated value. If the tree is empty, it returns the zero values for K and V, and false. Otherwise returns the key-value pair and true.
This operation modifies the tree structure due to splaying if found.
func (*Tree[K, V]) PostOrder ¶
PostOrder traverses the tree in post-order (left-right-root) fashion, calling the provided function for each node. If the function returns false, the traversal is stopped.
Unlike Get/Put operations, PostOrder does not perform any splay operations.
func (*Tree[K, V]) PreOrder ¶
PreOrder traverses the tree in pre-order (root-left-right) fashion, calling the provided function for each node. If the function returns false, the traversal is stopped.
Unlike Get/Put operations, PreOrder does not perform any splay operations.
func (*Tree[K, V]) Put ¶
func (t *Tree[K, V]) Put(key K, val V)
Put inserts or updates a key-value pair in the splay tree
func (*Tree[K, V]) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface.
Source Files