sorts

Documentation

Index

• Variables
• func Topological[Index comparable, V any](slice []V, queryIndexHandler func(item V) Index, ...) ([]V, error)

Examples

• Topological

Variables

var (
	ErrCircularDependencyDetected = errors.New("circular dependency detected")
)

Functions

func Topological

func Topological[Index comparable, V any](slice []V, queryIndexHandler func(item V) Index, queryDependsHandler func(item V) []Index) ([]V, error)

Topological 拓扑排序是一种对有向图进行排序的算法，它可以用来解决一些依赖关系的问题，比如计算字段的依赖关系。拓扑排序会将存在依赖关系的元素进行排序，使得依赖关系的元素总是排在被依赖的元素之前。

• slice: 需要排序的切片
• queryIndexHandler: 用于查询切片中每个元素的索引
• queryDependsHandler: 用于查询切片中每个元素的依赖关系，返回的是一个索引切片，如果没有依赖关系，那么返回空切片

该函数在存在循环依赖的情况下将会返回 ErrCircularDependencyDetected 错误

Example

package main

import (
	"fmt"
	"github.com/kercylan98/minotaur/utils/sorts"
)

func main() {
	type Item struct {
		ID      int
		Depends []int
	}

	var items = []Item{
		{ID: 2, Depends: []int{4}},
		{ID: 1, Depends: []int{2, 3}},
		{ID: 3, Depends: []int{4}},
		{ID: 4, Depends: []int{5}},
		{ID: 5, Depends: []int{}},
	}

	var sorted, err = sorts.Topological(items, func(item Item) int {
		return item.ID
	}, func(item Item) []int {
		return item.Depends
	})

	if err != nil {
		return
	}

	for _, item := range sorted {
		fmt.Println(item.ID, "|", item.Depends)
	}
}

Output:

1 | [2 3]
2 | [4]
3 | [4]
4 | [5]
5 | []