splay

Documentation

Index

• type Node
  • func NewNode(value Value) *Node
  • func (n *Node) Value() Value
• type Tree
  • func NewTree(root *Node) *Tree
  • func (t *Tree) AnnotatedString() string
  • func (t *Tree) CutOffRange(fromOuter, fromInner, toInner, toOuter *Node)
  • func (t *Tree) Delete(node *Node)
  • func (t *Tree) Find(index int) (*Node, int)
  • func (t *Tree) IndexOf(node *Node) int
  • func (t *Tree) Insert(node *Node) *Node
  • func (t *Tree) InsertAfter(prev *Node, node *Node) *Node
  • func (t *Tree) Splay(node *Node)
  • func (t *Tree) String() string
  • func (t *Tree) UpdateWeight(node *Node)
• type Value

Types

type Node

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

Node is a node of Tree.

func NewNode

func NewNode(value Value) *Node

NewNode creates a new instance of Node.

func (*Node) Value

func (n *Node) Value() Value

Value returns the value of this Node.

type Tree

type Tree 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(root *Node) *Tree

NewTree creates a new instance of Tree.

func (*Tree) AnnotatedString

func (t *Tree) AnnotatedString() string

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

func (*Tree) CutOffRange

func (t *Tree) CutOffRange(fromOuter, fromInner, toInner, toOuter *Node)

CutOffRange cuts the given range from this Tree. This function separates the range from `fromInner` to `toInner` as a subtree by splaying outer nodes then cuts the subtree. 'xxxOuter' could be nil and means to delete the entire subtree in that direction.

CAUTION: This function does not filter out invalid argument inputs, such as non-consecutive indices in fromOuter and fromInner.

func (*Tree) Delete

func (t *Tree) Delete(node *Node)

Delete deletes the given node from this Tree.

func (*Tree) Find

func (t *Tree) Find(index int) (*Node, int)

Find returns the Node and offset of the given index.

func (*Tree) IndexOf

func (t *Tree) IndexOf(node *Node) int

IndexOf Find the index of the given node.

func (*Tree) Insert

func (t *Tree) Insert(node *Node) *Node

Insert inserts the node at the last.

func (*Tree) InsertAfter

func (t *Tree) InsertAfter(prev *Node, node *Node) *Node

InsertAfter inserts the node after the given previous node.

func (*Tree) Splay

func (t *Tree) Splay(node *Node)

Splay moves the given node to the root.

func (*Tree) String

func (t *Tree) String() string

String returns a string containing node values.

func (*Tree) UpdateWeight

func (t *Tree) UpdateWeight(node *Node)

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.