splay

package
v0.4.30 Latest Latest
Warning

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

Go to latest
Published: Aug 9, 2024 License: Apache-2.0 Imports: 2 Imported by: 0

Documentation

Overview

Package splay provides splay tree implementation. It is used to implement List by using splay tree.

Index

Constants

This section is empty.

Variables

View Source
var ErrOutOfIndex = fmt.Errorf("out of index")

ErrOutOfIndex is returned when the given index is out of index.

Functions

This section is empty.

Types

type Node

type Node[V Value] struct {
	// contains filtered or unexported fields
}

Node is a node of Tree.

func NewNode

func NewNode[V Value](value V) *Node[V]

NewNode creates a new instance of Node.

func (*Node[V]) InitWeight added in v0.2.10

func (t *Node[V]) InitWeight()

InitWeight sets initial weight of this node.

func (*Node[V]) Value

func (t *Node[V]) Value() V

Value returns the value of this Node.

type Tree

type Tree[V Value] struct {
	// contains filtered or unexported fields
}

Tree is weighted binary search tree which is based on Splay tree. original paper on Splay Trees: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

func NewTree

func NewTree[V Value](root *Node[V]) *Tree[V]

NewTree creates a new instance of Tree.

func (*Tree[V]) CheckWeight added in v0.2.12

func (t *Tree[V]) CheckWeight() bool

CheckWeight returns false when there is an incorrect weight node. for debugging purpose.

func (*Tree[V]) Delete

func (t *Tree[V]) Delete(node *Node[V])

Delete deletes the given node from this Tree.

func (*Tree[V]) DeleteRange added in v0.2.10

func (t *Tree[V]) DeleteRange(leftBoundary, rightBoundary *Node[V])

DeleteRange separates the range between given 2 boundaries from this Tree. This function separates the range to delete as a subtree by splaying outer boundary nodes. leftBoundary must exist because of 0-indexed initial dummy node of tree, but rightBoundary can be nil means range to delete includes the end of tree. Refer to the design document: ./design/range-deletion-in-slay-tree.md

func (*Tree[V]) Find

func (t *Tree[V]) Find(index int) (*Node[V], int, error)

Find returns the Node and offset of the given index.

func (*Tree[V]) IndexOf

func (t *Tree[V]) IndexOf(node *Node[V]) int

IndexOf Find the index of the given node.

func (*Tree[V]) Insert

func (t *Tree[V]) Insert(node *Node[V]) *Node[V]

Insert inserts the node at the last.

func (*Tree[V]) InsertAfter

func (t *Tree[V]) InsertAfter(prev *Node[V], node *Node[V]) *Node[V]

InsertAfter inserts the node after the given previous node.

func (*Tree[V]) Len added in v0.2.19

func (t *Tree[V]) Len() int

Len returns the size of this Tree.

func (*Tree[V]) Splay

func (t *Tree[V]) Splay(node *Node[V])

Splay moves the given node to the root.

func (*Tree[V]) String

func (t *Tree[V]) String() string

String returns a string containing node values.

func (*Tree[V]) ToTestString added in v0.4.8

func (t *Tree[V]) ToTestString() string

ToTestString returns a string containing the metadata of the Node for debugging purpose.

func (*Tree[V]) UpdateWeight added in v0.2.8

func (t *Tree[V]) UpdateWeight(node *Node[V])

UpdateWeight recalculates the weight of this node with the value and children.

type Value

type Value interface {
	Len() int
	String() string
}

Value represents the data stored in the nodes of Tree.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL