splay

Documentation

Index

• type Comparable
• type ConditionRangeFunc
• type MaintainInfo
• type RangeFunc
• type Splay
  • func NewSplay() Splay
• type StoredObj
  • func NewStoredObjForLookup(key string) StoredObj

Types

type Comparable

type Comparable interface {
	// Compare defines a comparison function in splay that returns `true` if and only if the
	// current element is strictly greater than the incoming element.
	Compare(Comparable) bool
}

type ConditionRangeFunc

type ConditionRangeFunc func(StoredObj) bool

ConditionRangeFunc visit objects by inorder traversal.

type MaintainInfo

type MaintainInfo interface {
	// Maintain defines the maintenance operation in the splay, which contains the properties
	// of the subtree rooted at the current node. We will update the properties of the current
	// node based on its left and right children.
	Maintain(MaintainInfo, MaintainInfo) MaintainInfo
}

type RangeFunc

type RangeFunc func(StoredObj)

RangeFunc visit objects by inorder traversal.

type Splay

type Splay interface {
	// Insert a StoredObj into the splay. Returns true if successful.
	Insert(StoredObj) bool
	// Delete a StoredObj from the splay. Returns true if successful.
	Delete(StoredObj) bool
	// Get a StoredObj from the splay.
	Get(StoredObj) StoredObj
	// Partition will bring together all objects strictly smaller than the current object
	// in a subtree and return the root's MaintainInfo of the subtree.
	Partition(Comparable) MaintainInfo
	// Range traverses the entire splay in mid-order.
	Range(RangeFunc)
	// ConditionRange traverses the entire splay in mid-order and ends the access immediately
	// if ConditionRangeFunc returns false.
	ConditionRange(ConditionRangeFunc)
	// Len returns the number of all objects in the splay.
	Len() int
	// String implements the String interface.
	String() string
	// Clone return a clone of the Splay.
	Clone() Splay
	// PrintTree outputs splay in the form of a tree diagram.
	PrintTree() string
}

Splay defines all methods of the splay-tree.

func NewSplay

func NewSplay() Splay

type StoredObj

type StoredObj interface {
	// Key returns the unique key used by the object in the splay.
	Key() string
	// String implements the String interface.
	String() string

	// MakeMaintainInfo return a MaintainInfo used by the StoredObj.
	MakeMaintainInfo() MaintainInfo

	Comparable
}

StoredObj defines all the methods that need to be implemented by the element being stored.

func NewStoredObjForLookup

func NewStoredObjForLookup(key string) StoredObj