mbtree

package
v0.0.1-202203021618 Latest Latest
Warning

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

 Go to latest Published: Mar 2, 2022 License: MPL-2.0 Imports: 4 Imported by: 0

Documentation

Overview

Package mbtree 树结构相关方法

Index

Constants

View Source 
const DEFAULT_ROOT_ID = 0
View Source 
const DEFAULT_TREE_LEVEL = 100

DEFAULT_TREE_LEVEL the maximum tree level RSearch() will traverse back

Variables

View Source 
var (
	ErrNodeNotFound        = errors.New("node not found")
	ErrInvalidNode         = errors.New("invalid node")
	ErrInvalidNodeId       = errors.New("invalid node id")
	ErrNodeAlreadyExist    = errors.New("node already exist")
	ErrInvalidSourceDest   = errors.New("source node cannot be ancestor of destination parent node")
	ErrDeleteRootForbidden = errors.New("root node cannot be deleted")
)

Functions

This section is empty.

Types

type Action 

type Action int
const (
	ADD Action = iota
	DELETE
)

type FilterFunc 

type FilterFunc func(*Node) bool

FilterFunc filter function to traverse and filter nodes pass a node as an argument, if function returns true then the node is matched and will be kept

type Node 

type Node struct {
	// node id
	Id int64
	// node tag
	Tag string
	// parent id of the node
	Pid int64
	// child id list
	ChildIds []int64
	// node data
	Data interface{}
}

func NewNode 

func NewNode(id int64, data interface{}) *Node

NewNode new node

func NewRootNode 

func NewRootNode(data interface{}) *Node

NewRootNode new root node

func (*Node) HasChildren 

func (n *Node) HasChildren() bool

HasChildren return true if current node has children

func (*Node) IsLeaf 

func (n *Node) IsLeaf() bool

IsLeaf return true if current node has no children

type SafeMultiBranchTree 

type SafeMultiBranchTree struct {
	sync.Mutex
	// 根节点ID
	RootId int64
	// 并发安全的map
	Nodes sync.Map
	// the maximum tree level
	// RSearch() use this value to traverse back how many levels
	MaxTreeLevel int
}

SafeMultiBranchTree 并发安全的多叉树

func NewTree 

func NewTree(rootNode *Node, args ...int) *SafeMultiBranchTree

func (*SafeMultiBranchTree) AllPaths 

func (t *SafeMultiBranchTree) AllPaths() [][]int64

AllPaths use this function to get the identifiers allowing to go from the root nodes to each leaf. @return: a list of list of identifiers, root being not omitted. For example: 

Harry
|___ Bill
|___ Jane
|    |___ Diane
|         |___ George
|              |___ Jill
|         |___ Mary
|    |___ Mark

Expected result: 

 [['harry', 'jane', 'diane', 'mary'],
	['harry', 'jane', 'mark'],
	['harry', 'jane', 'diane', 'george', 'jill'],
	['harry', 'bill']]

func (*SafeMultiBranchTree) Contains 

func (t *SafeMultiBranchTree) Contains(id int64) bool

Contains check if nid in tree or not

func (*SafeMultiBranchTree) CreateNode 

func (t *SafeMultiBranchTree) CreateNode(id int64, pid int64, data interface{}) (*Node, error)

CreateNode create a child node for given @pid node.

func (*SafeMultiBranchTree) DeleteNode 

func (t *SafeMultiBranchTree) DeleteNode(id int64) error

DeleteNode delete a node by linking past it. For example, if we have `a -> b -> ccc` and delete node b, we are left with `a -> ccc`.

func (*SafeMultiBranchTree) Depth 

func (t *SafeMultiBranchTree) Depth(args ...int64) int

Depth get the maximum level of the tree or the level of the given node if specified the node id, then it get the depth of that given node if not specified the node id, it get the maximum level of the tree @param: args it could be @nodeId @return: the depth of the tree or the depth of the @nodeId

func (*SafeMultiBranchTree) DepthFirstTraversal 

func (t *SafeMultiBranchTree) DepthFirstTraversal(nid int64, args ...FilterFunc) chan int64

DepthFirstTraversal 深度优先遍历

func (*SafeMultiBranchTree) FilterNodes 

func (t *SafeMultiBranchTree) FilterNodes(f FilterFunc) []*Node

FilterNodes traverse all nodes in the tree by using filter function @param f: is passed one node as an argument and that node is included if function returns true, @return []*Node

func (*SafeMultiBranchTree) FilterNodesWithin 

func (t *SafeMultiBranchTree) FilterNodesWithin(ids []int64, f FilterFunc) []*Node

FilterNodesWithin filter nodes in specified id slice

func (*SafeMultiBranchTree) GetAllNodes 

func (t *SafeMultiBranchTree) GetAllNodes() []*Node

GetAllNodes 获取所有树节点slice

func (*SafeMultiBranchTree) GetAncestorNode 

func (t *SafeMultiBranchTree) GetAncestorNode(id int64, distance int) *Node

GetAncestorNode for a given id, get ancestor node object has distance to @nodeId @param: specified node id @param: distance value must > 1 and <= current level, the parent distance is 1 the grandparent distance is 2 the great-grandfather distance is 3

func (*SafeMultiBranchTree) GetChildIds 

func (t *SafeMultiBranchTree) GetChildIds(id int64) []int64

GetChildIds return the children nid list of specified id. empty slice is returned if nid does not exist

func (*SafeMultiBranchTree) GetChildNodes 

func (t *SafeMultiBranchTree) GetChildNodes(id int64) []*Node

GetChildNodes return the children node slice of specified node id empty slice is returned if no corresponding node exist for specified node id

func (*SafeMultiBranchTree) GetDescendantIds 

func (t *SafeMultiBranchTree) GetDescendantIds(id int64, args ...FilterFunc) []int64

GetDescendantIds get all descendant node ids, including myself

func (*SafeMultiBranchTree) GetDescendantNodes 

func (t *SafeMultiBranchTree) GetDescendantNodes(id int64, args ...FilterFunc) []*Node

GetDescendantNodes get all descendant nodes, including myself

func (*SafeMultiBranchTree) GetLeafNodes 

func (t *SafeMultiBranchTree) GetLeafNodes(args ...int64) []*Node

GetLeafNodes get leaf nodes of the tree, if specified node id, then get leaf node for that node

func (*SafeMultiBranchTree) GetNode 

func (t *SafeMultiBranchTree) GetNode(id int64) *Node

GetNode obtain node from the tree

func (*SafeMultiBranchTree) GetParentId 

func (t *SafeMultiBranchTree) GetParentId(id int64) int64

GetParentId 获取父节点的ID, 如果没找到，返回-1

func (*SafeMultiBranchTree) GetParentNode 

func (t *SafeMultiBranchTree) GetParentNode(id int64) *Node

GetParentNode 获取父节点, 如果没找到，返回nil

func (*SafeMultiBranchTree) GetPaths 

func (t *SafeMultiBranchTree) GetPaths(id int64) [][]int64

GetPaths 获取某个指定Node的路径，从根到叶节点

func (*SafeMultiBranchTree) GetRootNode 

func (t *SafeMultiBranchTree) GetRootNode() *Node

GetRootNode 获取根节点

func (*SafeMultiBranchTree) GetSiblingNodes 

func (t *SafeMultiBranchTree) GetSiblingNodes(id int64) []*Node

GetSiblingNodes return the siblings of given @id. If @nid is root or there are no siblings, nil is returned.

func (*SafeMultiBranchTree) IsAncestor 

func (t *SafeMultiBranchTree) IsAncestor(ancestorId int64, grandchildId int64) bool

IsAncestor check if the @ancestor is the preceding nodes of @grandchild @param: ancestorId, the ancestor node id @param: grandchild, the grandchild node id @return: true or false

func (*SafeMultiBranchTree) Level 

func (t *SafeMultiBranchTree) Level(id int64, args ...FilterFunc) int

Level get specified node's level The level is an integer starting with 0 at the root. In other words, the root lives at level 0 @id: node id @args: it can pass filter function to calculate level passing exclusive nodes.

func (*SafeMultiBranchTree) MoveNode 

func (t *SafeMultiBranchTree) MoveNode(id int64, destPid int64) error

MoveNode move node @id to be a child of parent @destPid

func (*SafeMultiBranchTree) RSearch 

func (t *SafeMultiBranchTree) RSearch(id int64, args ...FilterFunc) chan int64

RSearch traverse back from the nid node to its ancestors (until root) @param: it supports pass one filter func to check the node

func (*SafeMultiBranchTree) Size 

func (t *SafeMultiBranchTree) Size() int

Size get how many nodes in the tree

func (*SafeMultiBranchTree) SubTree 

func (t *SafeMultiBranchTree) SubTree(id int64) *SafeMultiBranchTree

SubTree return a shallow COPY of subtree with nid being the new root.

func (*SafeMultiBranchTree) WidthFirstTraversal 

func (t *SafeMultiBranchTree) WidthFirstTraversal(nid int64, args ...FilterFunc) chan int64

WidthFirstTraversal 广度优先遍历

type TraversalMode 

type TraversalMode int
const (
	// DEPTH 深度优先遍历算法
	DEPTH TraversalMode = iota
	// WIDTH 广度优先遍历算法
	WIDTH
)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.