toposort

Documentation

Overview

Package toposort provides a topological sort for segments/flags based on their dependencies.

Index

• func Sort(allData []st.Collection) []st.Collection
• type AdjacencyList
• type Neighbors
  • func GetNeighbors(kind st.DataKind, fromItem st.ItemDescriptor) Neighbors
  • func (s Neighbors) Add(value Vertex)
  • func (s Neighbors) Contains(value Vertex) bool
• type Vertex
  • func NewVertex(kind st.DataKind, key string) Vertex
  • func (v Vertex) Key() string
  • func (v Vertex) Kind() st.DataKind

Functions

func Sort

func Sort(allData []st.Collection) []st.Collection

Sort performs a topological sort on the given data collections, so that the items can be inserted into a persistent store to minimize the risk of evaluating a flag before its prerequisites/segments have been stored.

Types

type AdjacencyList

type AdjacencyList map[Vertex]Neighbors

AdjacencyList is a map of vertices (kind/key) to neighbors (dependencies).

type Neighbors

type Neighbors map[Vertex]struct{}

Neighbors is a set of vertices. It is used instead of a list for efficient lookup.

func GetNeighbors

func GetNeighbors(kind st.DataKind, fromItem st.ItemDescriptor) Neighbors

GetNeighbors returns all direct neighbors of the given item.

func (Neighbors) Add

func (s Neighbors) Add(value Vertex)

Add adds a vertex to the set.

func (Neighbors) Contains

func (s Neighbors) Contains(value Vertex) bool

Contains returns true if the set contains the vertex.

type Vertex

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

Vertex represents a particular data item, identified by kind + key.

func NewVertex

func NewVertex(kind st.DataKind, key string) Vertex

NewVertex constructs a Vertex.

func (Vertex) Key

func (v Vertex) Key() string

Key returns the key of the vertex.

func (Vertex) Kind

func (v Vertex) Kind() st.DataKind

Kind returns the data kind of the vertex.