/dagger

dagger is a fast, concurrency safe, mutable, in-memory directed graph library. Also includes a number of generic, concurrency safe data-structures

Primary LanguageGoApache License 2.0Apache-2.0

dagger

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

Index

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