import "github.com/autom8ter/dagger/v3"
Package dagger is a collection of generic, concurrency safe datastructures including a Directed Acyclic Graph and others. Datastructures are implemented using generics in Go 1.18.
Supported Datastructures:
DAG: thread safe directed acyclic graph
Queue: unbounded thread safe fifo queue
Stack: unbounded thread safe lifo stack
BoundedQueue: bounded thread safe fifo queue with a fixed capacity
PriorityQueue: thread safe priority queue
HashMap: thread safe hashmap
Set: thread safe set
ChannelGroup: thread safe group of channels for broadcasting 1 value to N channels
MultiContext: thread safe context for coordinating the cancellation of multiple contexts
Borrower: thread safe object ownership manager
- func UniqueID(prefix string) string
- type BoundedQueue
- func NewBoundedQueue[T any](maxSize int) *BoundedQueue[T]
- func (q *BoundedQueue[T]) Close()
- func (q *BoundedQueue[T]) Len() int
- func (q *BoundedQueue[T]) Pop() (T, bool)
- func (q *BoundedQueue[T]) PopContext(ctx context.Context) (T, bool)
- func (q *BoundedQueue[T]) Push(val T) bool
- func (q *BoundedQueue[T]) PushContext(ctx context.Context, val T) bool
- func (q *BoundedQueue[T]) Range(fn func(element T) bool)
- func (q *BoundedQueue[T]) RangeContext(ctx context.Context, fn func(element T) bool)
- type DAG
- func NewDAG[T Node](opts ...DagOpt) (*DAG[T], error)
- func (g *DAG[T]) Acyclic() bool
- func (g *DAG[T]) BFS(ctx context.Context, reverse bool, start *GraphNode[T], search GraphSearchFunc[T]) error
- func (g *DAG[T]) DFS(ctx context.Context, reverse bool, start *GraphNode[T], fn GraphSearchFunc[T]) error
- func (g *DAG[T]) GetEdge(id string) (*GraphEdge[T], bool)
- func (g *DAG[T]) GetEdges() []*GraphEdge[T]
- func (g *DAG[T]) GetNode(id string) (*GraphNode[T], bool)
- func (g *DAG[T]) GetNodes() []*GraphNode[T]
- func (g *DAG[T]) GraphViz() (image.Image, error)
- func (g *DAG[T]) HasEdge(id string) bool
- func (g *DAG[T]) HasNode(id string) bool
- func (g *DAG[T]) RangeEdges(fn func(e *GraphEdge[T]) bool)
- func (g *DAG[T]) RangeNodes(fn func(n *GraphNode[T]) bool)
- func (g *DAG[T]) SetNode(node Node) *GraphNode[T]
- func (g *DAG[T]) Size() (int, int)
- func (g *DAG[T]) TopologicalSort(reverse bool) ([]*GraphNode[T], error)
- type DagOpt
- type GraphEdge
- type GraphNode
- func (n *GraphNode[T]) Ancestors(fn func(node *GraphNode[T]) bool)
- func (n *GraphNode[T]) BFS(ctx context.Context, reverse bool, fn GraphSearchFunc[T]) error
- func (n *GraphNode[T]) DFS(ctx context.Context, reverse bool, fn GraphSearchFunc[T]) error
- func (n *GraphNode[T]) Descendants(fn func(node *GraphNode[T]) bool)
- func (n *GraphNode[T]) EdgesFrom(relationship string, fn func(e *GraphEdge[T]) bool)
- func (n *GraphNode[T]) EdgesTo(relationship string, fn func(e *GraphEdge[T]) bool)
- func (n *GraphNode[T]) Graph() *DAG[T]
- func (n *GraphNode[T]) IsConnectedTo(node *GraphNode[T]) bool
- func (n *GraphNode[T]) Remove() error
- func (n *GraphNode[T]) RemoveEdge(edgeID string)
- func (n *GraphNode[T]) SetEdge(relationship string, toNode Node, metadata map[string]string) (*GraphEdge[T], error)
- type GraphSearchFunc
- type HashMap
- func NewHashMap[K comparable, V any]() *HashMap[K, V]
- func (n *HashMap[K, V]) Clear()
- func (n *HashMap[K, V]) Delete(key K)
- func (n *HashMap[K, V]) Exists(key K) bool
- func (n *HashMap[K, V]) Filter(f func(key K, value V) bool) *HashMap[K, V]
- func (n *HashMap[K, V]) Get(key K) (V, bool)
- func (n *HashMap[K, V]) Keys() []K
- func (n *HashMap[K, V]) Len() int
- func (n *HashMap[K, V]) Map() map[K]V
- func (n *HashMap[K, V]) Range(f func(key K, value V) bool)
- func (n *HashMap[K, V]) Set(key K, value V)
- func (n *HashMap[K, V]) Values() []V
- type Node
- type PriorityQueue
- type Queue
- type Set
- type Stack
- func NewStack[T any]() *Stack[T]
- func (s *Stack[T]) Clear()
- func (s *Stack[T]) Len() int
- func (s *Stack[T]) Peek() (T, bool)
- func (s *Stack[T]) Pop() (T, bool)
- func (s *Stack[T]) Push(f T)
- func (s *Stack[T]) Range(fn func(element T) bool)
- func (s *Stack[T]) RangeUntil(fn func(element T) bool, done chan struct{})
- func (s *Stack[T]) Sort(lessFunc func(i T, j T) bool) []T
- func (s *Stack[T]) Values() []T
func UniqueID
func UniqueID(prefix string) string
UniqueID returns a unique identifier with the given prefix
type BoundedQueue
BoundedQueue is a basic FIFO BoundedQueue based on a buffered channel
type BoundedQueue[T any] struct {
// contains filtered or unexported fields
}
func NewBoundedQueue
func NewBoundedQueue[T any](maxSize int) *BoundedQueue[T]
NewBoundedQueue returns a new BoundedQueue with the given max size. When the max size is reached, the queue will block until a value is removed. If maxSize is 0, the queue will always block until a value is removed. The BoundedQueue is concurrent-safe.
func (*BoundedQueue[T]) Close
func (q *BoundedQueue[T]) Close()
Close closes the BoundedQueue channel.
func (*BoundedQueue[T]) Len
func (q *BoundedQueue[T]) Len() int
Len returns the number of elements in the BoundedQueue.
func (*BoundedQueue[T]) Pop
func (q *BoundedQueue[T]) Pop() (T, bool)
Pop removes and returns an element from the beginning of the BoundedQueue.
func (*BoundedQueue[T]) PopContext
func (q *BoundedQueue[T]) PopContext(ctx context.Context) (T, bool)
PopContext removes and returns an element from the beginning of the BoundedQueue. If no element is available, it will block until an element is available or the context is cancelled.
func (*BoundedQueue[T]) Push
func (q *BoundedQueue[T]) Push(val T) bool
Push adds an element to the end of the BoundedQueue and returns a channel that will block until the element is added. If the queue is full, it will block until an element is removed.
func (*BoundedQueue[T]) PushContext
func (q *BoundedQueue[T]) PushContext(ctx context.Context, val T) bool
PushContext adds an element to the end of the BoundedQueue and returns a channel that will block until the element is added. If the queue is full, it will block until an element is removed or the context is cancelled.
func (*BoundedQueue[T]) Range
func (q *BoundedQueue[T]) Range(fn func(element T) bool)
Range executes a provided function once for each BoundedQueue element until it returns false.
func (*BoundedQueue[T]) RangeContext
func (q *BoundedQueue[T]) RangeContext(ctx context.Context, fn func(element T) bool)
RangeContext executes a provided function once for each BoundedQueue element until it returns false or a value is sent to the done channel. Use this function when you want to continuously process items from the queue until a done signal is received.
type DAG
DAG is a concurrency safe, mutable, in-memory directed graph
type DAG[T Node] struct {
// contains filtered or unexported fields
}
func NewDAG
func NewDAG[T Node](opts ...DagOpt) (*DAG[T], error)
NewDAG creates a new Directed Acyclic Graph instance
func (*DAG[T]) Acyclic
func (g *DAG[T]) Acyclic() bool
Acyclic returns true if the graph contains no cycles.
func (*DAG[T]) BFS
func (g *DAG[T]) BFS(ctx context.Context, reverse bool, start *GraphNode[T], search GraphSearchFunc[T]) error
BFS executes a depth first search on the graph starting from the current node. The reverse parameter determines whether the search is reversed or not. The fn parameter is a function that is called on each node in the graph. If the function returns false, the search is stopped.
func (*DAG[T]) DFS
func (g *DAG[T]) DFS(ctx context.Context, reverse bool, start *GraphNode[T], fn GraphSearchFunc[T]) error
DFS executes a depth first search on the graph starting from the current node. The reverse parameter determines whether the search is reversed or not. The fn parameter is a function that is called on each node in the graph. If the function returns false, the search is stopped.
func (*DAG[T]) GetEdge
func (g *DAG[T]) GetEdge(id string) (*GraphEdge[T], bool)
GetEdge returns the edge with the given id
func (*DAG[T]) GetEdges
func (g *DAG[T]) GetEdges() []*GraphEdge[T]
GetEdges returns all edges in the graph
func (*DAG[T]) GetNode
func (g *DAG[T]) GetNode(id string) (*GraphNode[T], bool)
GetNode returns the node with the given id
func (*DAG[T]) GetNodes
func (g *DAG[T]) GetNodes() []*GraphNode[T]
GetNodes returns all nodes in the graph
func (*DAG[T]) GraphViz
func (g *DAG[T]) GraphViz() (image.Image, error)
GraphViz returns a graphviz image
func (*DAG[T]) HasEdge
func (g *DAG[T]) HasEdge(id string) bool
HasEdge returns true if the edge with the given id exists in the graph
func (*DAG[T]) HasNode
func (g *DAG[T]) HasNode(id string) bool
HasNode returns true if the node with the given id exists in the graph
func (*DAG[T]) RangeEdges
func (g *DAG[T]) RangeEdges(fn func(e *GraphEdge[T]) bool)
RangeEdges iterates over all edges in the graph
func (*DAG[T]) RangeNodes
func (g *DAG[T]) RangeNodes(fn func(n *GraphNode[T]) bool)
RangeNodes iterates over all nodes in the graph
func (*DAG[T]) SetNode
func (g *DAG[T]) SetNode(node Node) *GraphNode[T]
SetNode sets a node in the graph - it will use the node's ID as the key and overwrite any existing node with the same ID
func (*DAG[T]) Size
func (g *DAG[T]) Size() (int, int)
Size returns the number of nodes and edges in the graph
func (*DAG[T]) TopologicalSort
func (g *DAG[T]) TopologicalSort(reverse bool) ([]*GraphNode[T], error)
type DagOpt
DagOpt is an option for configuring a DAG
type DagOpt func(*dagOpts)
func WithVizualization
func WithVizualization() DagOpt
WithVizualization enables graphviz visualization on the DAG
type GraphEdge
GraphEdge is a relationship between two nodes
type GraphEdge[T Node] struct {
// contains filtered or unexported fields
}
func (*GraphEdge[T]) From
func (n *GraphEdge[T]) From() *GraphNode[T]
From returns the from node of the edge
func (*GraphEdge[T]) ID
func (n *GraphEdge[T]) ID() string
ID returns the unique identifier of the node
func (*GraphEdge[T]) Metadata
func (n *GraphEdge[T]) Metadata() map[string]string
Metadata returns the metadata of the node
func (*GraphEdge[T]) Relationship
func (n *GraphEdge[T]) Relationship() string
Relationship returns the relationship between the two nodes
func (*GraphEdge[T]) SetMetadata
func (n *GraphEdge[T]) SetMetadata(metadata map[string]string)
SetMetadata sets the metadata of the node
func (*GraphEdge[T]) To
func (n *GraphEdge[T]) To() *GraphNode[T]
To returns the to node of the edge
type GraphNode
GraphNode is a node in the graph. It can be connected to other nodes via edges.
type GraphNode[T Node] struct {
Node
// contains filtered or unexported fields
}
func (*GraphNode[T]) Ancestors
func (n *GraphNode[T]) Ancestors(fn func(node *GraphNode[T]) bool)
Ancestors returns the ancestors of the current node
func (*GraphNode[T]) BFS
func (n *GraphNode[T]) BFS(ctx context.Context, reverse bool, fn GraphSearchFunc[T]) error
BFS performs a breadth-first search on the graph starting from the current node
func (*GraphNode[T]) DFS
func (n *GraphNode[T]) DFS(ctx context.Context, reverse bool, fn GraphSearchFunc[T]) error
DFS performs a depth-first search on the graph starting from the current node
func (*GraphNode[T]) Descendants
func (n *GraphNode[T]) Descendants(fn func(node *GraphNode[T]) bool)
Descendants returns the descendants of the current node
func (*GraphNode[T]) EdgesFrom
func (n *GraphNode[T]) EdgesFrom(relationship string, fn func(e *GraphEdge[T]) bool)
EdgesFrom iterates over the edges from the current node to other nodes with the given relationship. If the relationship is empty, all relationships will be iterated over.
func (*GraphNode[T]) EdgesTo
func (n *GraphNode[T]) EdgesTo(relationship string, fn func(e *GraphEdge[T]) bool)
EdgesTo iterates over the edges from other nodes to the current node with the given relationship. If the relationship is empty, all relationships will be iterated over.
func (*GraphNode[T]) Graph
func (n *GraphNode[T]) Graph() *DAG[T]
DirectedGraph returns the graph the node belongs to
func (*GraphNode[T]) IsConnectedTo
func (n *GraphNode[T]) IsConnectedTo(node *GraphNode[T]) bool
IsConnectedTo returns true if the current node is connected to the given node in any direction
func (*GraphNode[T]) Remove
func (n *GraphNode[T]) Remove() error
Remove removes the current node from the graph
func (*GraphNode[T]) RemoveEdge
func (n *GraphNode[T]) RemoveEdge(edgeID string)
RemoveEdge removes an edge from the current node by edgeID
func (*GraphNode[T]) SetEdge
func (n *GraphNode[T]) SetEdge(relationship string, toNode Node, metadata map[string]string) (*GraphEdge[T], error)
SetEdge sets an edge from the current node to the node with the given nodeID. If the nodeID does not exist, an error is returned. If the edgeID is empty, a unique id will be generated. If the metadata is nil, an empty map will be used.
type GraphSearchFunc
GraphSearchFunc is a function that is called on each node in the graph during a search
type GraphSearchFunc[T Node] func(ctx context.Context, relationship string, node *GraphNode[T]) bool
type HashMap
HashMap is a thread safe map
type HashMap[K comparable, V any] struct {
// contains filtered or unexported fields
}
func NewHashMap
func NewHashMap[K comparable, V any]() *HashMap[K, V]
NewHashMap creates a new generic hash map
func (*HashMap[K, V]) Clear
func (n *HashMap[K, V]) Clear()
Clear clears the map
func (*HashMap[K, V]) Delete
func (n *HashMap[K, V]) Delete(key K)
Delete deletes the key from the map
func (*HashMap[K, V]) Exists
func (n *HashMap[K, V]) Exists(key K) bool
Exists returns true if the key exists in the map
func (*HashMap[K, V]) Filter
func (n *HashMap[K, V]) Filter(f func(key K, value V) bool) *HashMap[K, V]
Filter returns a new hashmap with the values that return true from the function
func (*HashMap[K, V]) Get
func (n *HashMap[K, V]) Get(key K) (V, bool)
Get gets the value from the key
func (*HashMap[K, V]) Keys
func (n *HashMap[K, V]) Keys() []K
Keys returns a copy of the keys in the map as a slice
func (*HashMap[K, V]) Len
func (n *HashMap[K, V]) Len() int
Len returns the length of the map
func (*HashMap[K, V]) Map
func (n *HashMap[K, V]) Map() map[K]V
Map returns a copy of the hashmap as a map[string]T
func (*HashMap[K, V]) Range
func (n *HashMap[K, V]) Range(f func(key K, value V) bool)
Range ranges over the map with a function until false is returned
func (*HashMap[K, V]) Set
func (n *HashMap[K, V]) Set(key K, value V)
Set sets the key to the value
func (*HashMap[K, V]) Values
func (n *HashMap[K, V]) Values() []V
Values returns a copy of the values in the map as a slice
type Node
Node is a node in the graph. It can be connected to other nodes via edges.
type Node interface {
// ID returns the unique identifier of the node
ID() string
// Metadata returns the metadata of the node
Metadata() map[string]string
// SetMetadata sets the metadata of the node
SetMetadata(metadata map[string]string)
}
type PriorityQueue
PriorityQueue is a thread safe priority queue
type PriorityQueue[T any] struct {
// contains filtered or unexported fields
}
func NewPriorityQueue
func NewPriorityQueue[T any]() *PriorityQueue[T]
NewPriorityQueue creates a new priority queue
func (*PriorityQueue[T]) Len
func (q *PriorityQueue[T]) Len() int
Len returns the length of the queue
func (*PriorityQueue[T]) Peek
func (q *PriorityQueue[T]) Peek() (T, bool)
Peek returns the next item in the queue without removing it
func (*PriorityQueue[T]) Pop
func (q *PriorityQueue[T]) Pop() (T, bool)
Pop pops an item off the queue
func (*PriorityQueue[T]) Push
func (q *PriorityQueue[T]) Push(item T, weight float64)
Push pushes an item onto the queue
func (*PriorityQueue[T]) UpdatePriority
func (q *PriorityQueue[T]) UpdatePriority(value T, priority float64)
type Queue
Queue is a thread safe non-blocking queue
type Queue[T any] struct {
// contains filtered or unexported fields
}
func NewQueue
func NewQueue[T any]() *Queue[T]
NewQueue returns a new Queue
func (*Queue[T]) Len
func (s *Queue[T]) Len() int
Len returns the length of the queue
func (*Queue[T]) Peek
func (s *Queue[T]) Peek() (T, bool)
Peek returns the next item in the queue without removing it
func (*Queue[T]) Pop
func (s *Queue[T]) Pop() (T, bool)
Pop and return top element of Queue. Return false if Queue is empty.
func (*Queue[T]) Push
func (s *Queue[T]) Push(f T)
Push a new value onto the Queue
func (*Queue[T]) Range
func (q *Queue[T]) Range(fn func(element T) bool)
Range executes a provided function once for each Queue element until it returns false or the Queue is empty.
func (*Queue[T]) RangeUntil
func (q *Queue[T]) RangeUntil(fn func(element T) bool, done chan struct{})
RangeUntil executes a provided function once for each Queue element until it returns false or a value is sent on the done channel. Use this function when you want to continuously process items from the queue until a done signal is received.
type Set
Set is a basic thread-safe Set implementation.
type Set[T comparable] struct {
// contains filtered or unexported fields
}
func NewSet
func NewSet[T comparable]() *Set[T]
NewSet returns a new Set with the given initial size.
func (*Set[T]) Add
func (s *Set[T]) Add(val T)
Add adds an element to the Set.
func (*Set[T]) Contains
func (s *Set[T]) Contains(val T) bool
Contains returns true if the Set contains the element.
func (*Set[T]) Len
func (s *Set[T]) Len() int
Len returns the number of elements in the Set.
func (*Set[T]) Range
func (s *Set[T]) Range(fn func(element T) bool)
Range executes a provided function once for each Set element until it returns false.
func (*Set[T]) Remove
func (s *Set[T]) Remove(val T)
Remove removes an element from the Set.
func (*Set[T]) Sort
func (s *Set[T]) Sort(lessFunc func(i T, j T) bool) []T
Sort returns the values of the set as an array sorted by the provided less function
func (*Set[T]) Values
func (s *Set[T]) Values() []T
Values returns the values of the set as an array
type Stack
Stack is a basic LIFO Stack
type Stack[T any] struct {
// contains filtered or unexported fields
}
func NewStack
func NewStack[T any]() *Stack[T]
NewStack returns a new Stack instance
func (*Stack[T]) Clear
func (s *Stack[T]) Clear()
Clear removes all elements from the Stack
func (*Stack[T]) Len
func (s *Stack[T]) Len() int
Len returns the number of elements in the Stack.
func (*Stack[T]) Peek
func (s *Stack[T]) Peek() (T, bool)
Peek returns the top element of the Stack without removing it. Return false if Stack is empty.
func (*Stack[T]) Pop
func (s *Stack[T]) Pop() (T, bool)
Pop removes and return top element of Stack. Return false if Stack is empty.
func (*Stack[T]) Push
func (s *Stack[T]) Push(f T)
Push a new value onto the Stack (LIFO)
func (*Stack[T]) Range
func (s *Stack[T]) Range(fn func(element T) bool)
Range executes a provided function once for each Stack element until it returns false.
func (*Stack[T]) RangeUntil
func (s *Stack[T]) RangeUntil(fn func(element T) bool, done chan struct{})
RangeUntil executes a provided function once after calling Pop on the stack until the function returns false or a value is sent on the done channel. Use this function when you want to continuously process items from the stack until a done signal is received.
func (*Stack[T]) Sort
func (s *Stack[T]) Sort(lessFunc func(i T, j T) bool) []T
Sort returns the values of the stack as an array sorted by the provided less function
func (*Stack[T]) Values
func (s *Stack[T]) Values() []T
Values returns the values of the stack as an array
Generated by gomarkdoc