index

Documentation

Overview

Package index provides an index tree structure to represent a document of text-base editor.

Index

• Constants
• Variables
• func ToXML[V Value](node *Node[V]) string
• func Traverse[V Value](tree *Tree[V], callback func(node *Node[V], depth int))
• func TraverseNode[V Value](node *Node[V], callback func(node *Node[V], depth int))
• type Node
  • func NewNode[V Value](nodeType string, value V, children ...*Node[V]) *Node[V]
  • func (n *Node[V]) Append(newNodes ...*Node[V]) error
  • func (n *Node[V]) Child(index int) (*Node[V], error)
  • func (n *Node[V]) Children(includeRemovedNode ...bool) []*Node[V]
  • func (n *Node[V]) FindBranchOffset(node *Node[V]) (int, error)
  • func (n *Node[V]) FindOffset(node *Node[V]) (int, error)
  • func (n *Node[V]) HasTextChild() bool
  • func (n *Node[V]) InsertAfter(newNode, referenceNode *Node[V]) error
  • func (n *Node[V]) InsertAfterInternal(newNode, prevNode *Node[V]) error
  • func (n *Node[V]) InsertAt(newNode *Node[V], offset int) error
  • func (n *Node[V]) InsertBefore(newNode, referenceNode *Node[V]) error
  • func (n *Node[V]) IsAncestorOf(node *Node[V]) bool
  • func (n *Node[V]) IsText() bool
  • func (n *Node[V]) Len() int
  • func (n *Node[V]) OffsetOfChild(node *Node[V]) int
  • func (n *Node[V]) PaddedLength() int
  • func (n *Node[V]) Prepend(children ...*Node[V]) error
  • func (n *Node[V]) RemoveChild(child *Node[V]) error
  • func (n *Node[V]) SetChildren(children []*Node[V]) error
  • func (n *Node[V]) UpdateAncestorsSize()
  • func (n *Node[V]) UpdateDescendantsSize() int
• type TokenType
  • func (c TokenType) ToString() string
• type Tree
  • func NewTree[V Value](root *Node[V]) *Tree[V]
  • func (t *Tree[V]) FindCommonAncestor(nodeA, nodeB *Node[V]) V
  • func (t *Tree[V]) FindLeftmost(node *Node[V]) V
  • func (t *Tree[V]) FindPostorderRight(pos *TreePos[V]) (V, error)
  • func (t *Tree[V]) FindTreePos(index int, preferTexts ...bool) (*TreePos[V], error)
  • func (t *Tree[V]) GetAncestors(node *Node[V]) []*Node[V]
  • func (t *Tree[V]) IndexOf(pos *TreePos[V]) (int, error)
  • func (t *Tree[V]) LeftSiblingsSize(parent *Node[V], offset int) (int, error)
  • func (t *Tree[V]) PathToIndex(path []int) (int, error)
  • func (t *Tree[V]) PathToTreePos(path []int) (*TreePos[V], error)
  • func (t *Tree[V]) Root() *Node[V]
  • func (t *Tree[V]) TokensBetween(from int, to int, callback func(token TreeToken[V], ended bool)) error
  • func (t *Tree[V]) TreePosToPath(treePos *TreePos[V]) ([]int, error)
• type TreePos
• type TreeToken
• type Value

Constants

const (
	// DefaultTextType is the type of default text node.
	// TODO(hackerwins): Allow users to define the type of text node.
	DefaultTextType = "text"
)

Variables

var (
	// ErrInvalidMethodCallForTextNode is returned when a invalid method is called for text node.
	ErrInvalidMethodCallForTextNode = errors.New("text node cannot have children")

	// ErrChildNotFound is returned when a child is not found.
	ErrChildNotFound = errors.New("child not found")

	// ErrUnreachablePath is returned when a path is unreachable.
	ErrUnreachablePath = errors.New("unreachable path")

	// ErrInvalidTreePos is returned when a TreePos is invalid.
	ErrInvalidTreePos = errors.New("invalid tree pos")
)

Functions

func ToXML

func ToXML[V Value](node *Node[V]) string

ToXML returns the XML representation of this tree.

func Traverse

func Traverse[V Value](tree *Tree[V], callback func(node *Node[V], depth int))

Traverse traverses the tree with postorder traversal.

func TraverseNode

func TraverseNode[V Value](node *Node[V], callback func(node *Node[V], depth int))

TraverseNode traverses the tree with the given callback.

Types

type Node

type Node[V Value] struct {
	Type string

	Parent *Node[V]

	Value  V
	Length int
	// contains filtered or unexported fields
}

Node is a node of Tree.

func NewNode

func NewNode[V Value](nodeType string, value V, children ...*Node[V]) *Node[V]

NewNode creates a new instance of Node.

func (*Node[V]) Append

func (n *Node[V]) Append(newNodes ...*Node[V]) error

Append appends the given node to the end of the children.

func (*Node[V]) Child

func (n *Node[V]) Child(index int) (*Node[V], error)

Child returns the child of the given index.

func (*Node[V]) Children

func (n *Node[V]) Children(includeRemovedNode ...bool) []*Node[V]

Children returns the children of the given node.

func (*Node[V]) FindBranchOffset

func (n *Node[V]) FindBranchOffset(node *Node[V]) (int, error)

FindBranchOffset returns offset of the given descendant node in this node. If the given node is not a descendant of this node, it returns -1.

func (*Node[V]) FindOffset

func (n *Node[V]) FindOffset(node *Node[V]) (int, error)

FindOffset returns the offset of the given node in the children.

func (*Node[V]) HasTextChild

func (n *Node[V]) HasTextChild() bool

HasTextChild returns true if the node's children consist of only text children.

func (*Node[V]) InsertAfter

func (n *Node[V]) InsertAfter(newNode, referenceNode *Node[V]) error

InsertAfter inserts the given node after the given child.

func (*Node[V]) InsertAfterInternal

func (n *Node[V]) InsertAfterInternal(newNode, prevNode *Node[V]) error

InsertAfterInternal inserts the given node after the given child. This method does not update the size of the ancestors.

func (*Node[V]) InsertAt

func (n *Node[V]) InsertAt(newNode *Node[V], offset int) error

InsertAt inserts the given node at the given offset.

func (*Node[V]) InsertBefore

func (n *Node[V]) InsertBefore(newNode, referenceNode *Node[V]) error

InsertBefore inserts the given node before the given child.

func (*Node[V]) IsAncestorOf

func (n *Node[V]) IsAncestorOf(node *Node[V]) bool

IsAncestorOf returns true if the node is an ancestor of the given node.

func (*Node[V]) IsText

func (n *Node[V]) IsText() bool

IsText returns whether the Node is text or not.

func (*Node[V]) Len

func (n *Node[V]) Len() int

Len returns the length of the Node.

func (*Node[V]) OffsetOfChild

func (n *Node[V]) OffsetOfChild(node *Node[V]) int

OffsetOfChild returns offset of children of the given node.

func (*Node[V]) PaddedLength

func (n *Node[V]) PaddedLength() int

PaddedLength returns the length of the node with padding.

func (*Node[V]) Prepend

func (n *Node[V]) Prepend(children ...*Node[V]) error

Prepend prepends the given nodes to the children. It is only used for creating a new node from shapshot.

func (*Node[V]) RemoveChild

func (n *Node[V]) RemoveChild(child *Node[V]) error

RemoveChild removes the given child.

func (*Node[V]) SetChildren

func (n *Node[V]) SetChildren(children []*Node[V]) error

SetChildren sets the children of the given node. This method does not update the size of the ancestors.

func (*Node[V]) UpdateAncestorsSize

func (n *Node[V]) UpdateAncestorsSize()

UpdateAncestorsSize updates the size of ancestors. It is used when the size of the node is changed.

func (*Node[V]) UpdateDescendantsSize

func (n *Node[V]) UpdateDescendantsSize() int

UpdateDescendantsSize updates the size of descendants. It is used when the tree is newly created and the size of the descendants is not calculated.

type TokenType

type TokenType int

TokenType represents the type of the selected token.

const (
	// Start represents that the start token type.
	Start TokenType = 1 + iota
	// End represents that the end token type.
	End
	// Text represents that the text token type.
	Text
)

func (TokenType) ToString

func (c TokenType) ToString() string

ToString returns the string of TokenType.

type Tree

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

Tree is a tree implementation to represent a document of text-based editors.

func NewTree

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

NewTree creates a new instance of Tree.

func (*Tree[V]) FindCommonAncestor

func (t *Tree[V]) FindCommonAncestor(nodeA, nodeB *Node[V]) V

FindCommonAncestor finds the lowest common ancestor of the given nodes.

func (*Tree[V]) FindLeftmost

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

FindLeftmost finds the leftmost node of the given tree.

func (*Tree[V]) FindPostorderRight

func (t *Tree[V]) FindPostorderRight(pos *TreePos[V]) (V, error)

FindPostorderRight finds right node of the given tree position with postorder traversal.

func (*Tree[V]) FindTreePos

func (t *Tree[V]) FindTreePos(index int, preferTexts ...bool) (*TreePos[V], error)

FindTreePos finds the position of the given index in the tree.

func (*Tree[V]) GetAncestors

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

GetAncestors returns the ancestors of the given node.

func (*Tree[V]) IndexOf

func (t *Tree[V]) IndexOf(pos *TreePos[V]) (int, error)

IndexOf returns the index of the given tree position.

func (*Tree[V]) LeftSiblingsSize

func (t *Tree[V]) LeftSiblingsSize(parent *Node[V], offset int) (int, error)

LeftSiblingsSize returns the size of left siblings of the given node

func (*Tree[V]) PathToIndex

func (t *Tree[V]) PathToIndex(path []int) (int, error)

PathToIndex converts the given path to index.

func (*Tree[V]) PathToTreePos

func (t *Tree[V]) PathToTreePos(path []int) (*TreePos[V], error)

PathToTreePos returns treePos from given path

func (*Tree[V]) Root

func (t *Tree[V]) Root() *Node[V]

Root returns the root node of the tree.

func (*Tree[V]) TokensBetween

func (t *Tree[V]) TokensBetween(from int, to int, callback func(token TreeToken[V], ended bool)) error

TokensBetween returns the tokens between the given range.

func (*Tree[V]) TreePosToPath

func (t *Tree[V]) TreePosToPath(treePos *TreePos[V]) ([]int, error)

TreePosToPath returns path from given treePos

type TreePos

type TreePos[V Value] struct {
	Node   *Node[V]
	Offset int
}

TreePos is the position of a node in the tree.

type TreeToken

type TreeToken[V Value] struct {
	Node      V
	TokenType TokenType
}

TreeToken represents a token in XML-like string.

type Value

type Value interface {
	IsRemoved() bool
	Length() int
	String() string
	Attributes() string
}

Value represents the data stored in the nodes of Tree.