splay

Documentation

Overview

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

Index

• Variables
• type Node
  • func NewNode[V Value](value V) *Node[V]
  • func (t *Node[V]) InitWeight()
  • func (t *Node[V]) Value() V
• type Tree
  • func NewTree[V Value](root *Node[V]) *Tree[V]
  • func (t *Tree[V]) CheckWeight() bool
  • func (t *Tree[V]) Delete(node *Node[V])
  • func (t *Tree[V]) DeleteRange(leftBoundary, rightBoundary *Node[V])
  • func (t *Tree[V]) Find(index int) (*Node[V], int, error)
  • func (t *Tree[V]) IndexOf(node *Node[V]) int
  • func (t *Tree[V]) Insert(node *Node[V]) *Node[V]
  • func (t *Tree[V]) InsertAfter(prev *Node[V], node *Node[V]) *Node[V]
  • func (t *Tree[V]) Len() int
  • func (t *Tree[V]) Splay(node *Node[V])
  • func (t *Tree[V]) String() string
  • func (t *Tree[V]) ToTestString() string
  • func (t *Tree[V]) UpdateWeight(node *Node[V])
• type Value

Variables

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

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

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

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

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

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

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

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

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

func (*Tree[V]) UpdateWeight

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.