dsa

package module
v0.8.2 Latest Latest
Warning

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

 Go to latest Published: May 29, 2025 License: MIT Imports: 8 Imported by: 0

README

dsa

A Go module with my common data structures and algorithms.

go get github.com/clickermonkey/dsa

Interfaces
  • dsa.Stack[T] a stack interface (FILO/LIFO)
  • dsa.Queue[T] a queue interface (FIFO/LILO)
Concrete
  • dsa.LinkedList[T] a doubly linked list of T values. non-sequential memory layout but O(1) insertion & removal. Implements stack & queue.
  • dsa.LinkedNode[T] a doubly linked list node.
  • dsa.Circle[T] a size bounded stack & queue.
  • dsa.PriorityQueue[T] a queue where highest priority value is in the front.
  • dsa.WaitQueue[T] a concurrent queue implementation where Dequeue() waits for a value.
  • dsa.ReadyQueue[T] a concurrent priority queue implementation where dequeue waits for a value which meets an expected priority (ready state).
  • dsa.SyncQueue[T] a conccurrent queue wrapper.
  • dsa.SliceStack[T] a slice stack implementation.
  • dsa.WaitStack[T] a concurrent stack implementation where Pop() waits for a value.
  • dsa.SyncStack[T] a concurrent stack wrapper.
Helpers
  • dsa.Stopper a wait/stop object to simplify gates across goroutines.
Functions
  • dsa.After(fn) converts a function call into a channel that resolves when the function returns.
  • dsa.ToChannel(fn) converts a function which returns a value into a channel which resolves that value when the function returns it.
  • dsa.WorkerPool(ctx,n,q,do) creates an async pool of workers which do work off of a queue which can be stopped at any time.
  • dsa.Executor(ctx,q,do) creates an async work processor from a queue of work that can be stopped at any time.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// EndOfTime is a constant representing the end of time.
	EndOfTime = time.Unix(1<<63-62135596801, 999999999)
	// BeginningOfTime is a constant representing the beginning of time.
	BeginningOfTime = time.Unix(-62135596801, 0)
)

Functions

func After 

func After(fn func()) <-chan struct{}

After executes the provided function in a separate goroutine and returns a channel that is closed when the function completes. This is useful for running a function asynchronously and waiting for its completion.

func DrainDone added in v0.6.0 

func DrainDone[T any](done <-chan struct{}, take func() T, len int) <-chan T

DrainDone drains a function into a channel until the done channel is closed. The channel is closed when the done channel is closed.

func DrainEmpty added in v0.6.0 

func DrainEmpty[T any](isEmpty func() bool, take func() T, len int) <-chan T

DrainEmpty drains a function into a channel until the isEmpty function returns true. The channel is closed when the isEmpty function returns true.

func Executor 

func Executor[W any](done <-chan struct{}, workQueue <-chan W, doWork func(W)) (stopper Stopper, waiter Stopper)

Execute processes tasks from a work queue as fast as work is available. A goroutines is started for each task, and the provided function is called with the task as an argument. The function returns two Stopper channels: one for stopping the execution and one for waiting for completion.

func HeapIterate added in v0.3.0 

func HeapIterate(h heap.Interface) iter.Seq[int]

Iterates a heap interface in order without copying. This is a modified breadth first search that looks at the children of the lowest value in the heap and yields them in order of their value. This will allocate an []int slice half the size of the heap. The underlying heap must not be modified during iteration.

func LessEqual added in v0.3.0 

func LessEqual[T any](a, b T, less Less[T]) bool

Returns whether a and b are equal given a less function.

func Log2 added in v0.3.0 

func Log2[I constraints.Integer](x I) int

Log2 calculates the base-2 logarithm of a given positive integer `x`. If x is not greater than 0, it returns 0.

func QueueDrainDone added in v0.6.0 

func QueueDrainDone[T any](done <-chan struct{}, q Queue[T], len int) <-chan T

QueueChannel creates a channel that will receive values from the queue. It's assumed the queue has a blocking Dequeue method. Only the given done channel is used to cancel the channel, otherwise the spawned goroutine will run forever waiting for values to be added to the queue.

func QueueDrainEmpty added in v0.6.0 

func QueueDrainEmpty[T any](q Queue[T], len int) <-chan T

QueueChannelDrain drains the queue into a channel. The channel is closed when the queue is empty.

func RacePair added in v0.6.2 

func RacePair[T any](a <-chan T, b <-chan T) <-chan T

RacePair returns a channel that sends values from either of the two input channels. It will close when it receives a value from either channel. If both channels close or are closed and return no values, the returned channel will also close without a value.

func StackDrainDone added in v0.6.0 

func StackDrainDone[T any](done <-chan struct{}, q Stack[T], len int) <-chan T

StackDrainDone creates a channel that will receive values from the queue. It's assumed the queue has a blocking Dequeue method. Only the given done channel is used to cancel the channel, otherwise the spawned goroutine will run forever waiting for values to be added to the queue.

func StackDrainEmpty added in v0.6.0 

func StackDrainEmpty[T any](s Stack[T], len int) <-chan T

StackDrainEmpty drains the stack into a channel. The channel is closed when the stack is empty.

func ToChannel 

func ToChannel[T any](fn func() T) <-chan T

ToChannel converts a function that returns a value of type T into a channel that sends that value. This is useful for running a function asynchronously and getting its result through a channel.

func WorkerPool 

func WorkerPool[W any](done <-chan struct{}, size int, workQueue <-chan W, doWork func(W)) (stopper Stopper, waiter Stopper)

WorkerPool creates a pool of workers that can process tasks concurrently. It takes a context, the size of the pool, a work queue, and a function to process the tasks. The function returns two Stopper channels: one for stopping the workers and one for waiting for their completion.

func Zero added in v0.3.0 

func Zero[T any]() T

Returns the zero value of T.

Types

type Circle added in v0.2.0 

type Circle[T any] struct {
	// contains filtered or unexported fields
}

A size bounded stack and queue implementation that uses a circular buffer.

func NewCircle added in v0.2.0 

func NewCircle[T any](max int) *Circle[T]

NewCircle creates a new Circle with the given size. The size is the maximum number of items that can be stored in the queue. If more items are added, the oldest items are removed.

func (*Circle[T]) Cap added in v0.2.0 

func (cq *Circle[T]) Cap() int

Cap returns the capacity of the circle. This is the maximum number of items that can be stored in the circle.

func (*Circle[T]) Dequeue added in v0.2.0 

func (cq *Circle[T]) Dequeue() T

Dequeue removes the item at the front of the circle. If the circle is empty, it returns the zero value of T.

func (*Circle[T]) Enqueue added in v0.2.0 

func (cq *Circle[T]) Enqueue(value T)

Enqueue adds an item to the circle. If the circle is full, the oldest item is removed.

func (*Circle[T]) IsEmpty added in v0.2.0 

func (cq *Circle[T]) IsEmpty() bool

IsEmpty returns true if the circle is empty.

func (*Circle[T]) Len added in v0.2.0 

func (cq *Circle[T]) Len() int

Len returns the number of items in the circle.

func (*Circle[T]) Peek added in v0.2.0 

func (cq *Circle[T]) Peek() T

Peek returns the item at the front of the circle without removing it. If the circle is empty, it returns the zero value of T.

func (*Circle[T]) Pop added in v0.2.0 

func (cq *Circle[T]) Pop() T

Pop removes the item at the end of the circle. If the circle is empty, it returns the zero value of T.

func (*Circle[T]) Push added in v0.2.0 

func (cq *Circle[T]) Push(value T)

Push adds an item to the circle.

func (*Circle[T]) SetOnOverwrite added in v0.5.0 

func (cq *Circle[T]) SetOnOverwrite(fn func(T))

SetOnOverwrite sets the function to be called when an item is overwritten.

func (*Circle[T]) Top added in v0.2.0 

func (cq *Circle[T]) Top() T

Top returns the item at the end of the circle without removing it. If the circle is empty, it returns the zero value of T.

func (*Circle[T]) Values added in v0.2.0 

func (cq *Circle[T]) Values() iter.Seq[T]

Values returns a sequence of the values in the circle. The order of the values is oldest to newest.

type FrequencyLoop added in v0.6.0 

type FrequencyLoop struct {
	// A maximum amount of time to allow the doWork function to run.
	// If the doWork function takes longer than this time, the context will be cancelled.
	Timeout time.Duration
	// The ideal interval at which to run the doWork function.
	// The doWork function will be called at this interval, but it may not be exact.
	// The actual interval may be longer if the doWork function takes longer to run.
	Interval time.Duration
	// The minimum interval between executions of the doWork function.
	// This is used to prevent the doWork function from being called too frequently.
	MinInterval time.Duration
	// A stopper that can be used to stop the loop.
	Stopper Stopper
}

FrequencyLoop is a structure that allows running a function at a specified interval. It can be used to create a loop that runs a task periodically, with a minimum interval between executions. A timeout can also be set for a child context passed to the doWork function to not allow the interval to exceed a certain duration. The loop will stop when the Stopper is stopped or when the context is done.

func (*FrequencyLoop) Sync added in v0.6.0 

func (fw *FrequencyLoop) Sync(ctx context.Context, doWork func(ctx context.Context))

Sync runs the doWork function at the specified interval. This is a blocking call and will not return until the Stopper is stopped or the context is done. The doWork function will be called with a context that is cancelled if the Timeout is exceeded.

type Less 

type Less[T any] func(a T, b T) bool

A comparison function that returns true if a is less than b.

func LessToEqual added in v0.3.0 

func LessToEqual[T any](less Less[T]) Less[T]

Converts a Less func to an Equal func

func LessToMore added in v0.3.0 

func LessToMore[T any](less Less[T]) Less[T]

Converts a Less func to an More func

type LinkedList added in v0.2.0 

type LinkedList[T any] struct {
	// contains filtered or unexported fields
}

A doubly linked list that can be used as a queue or stack. This is not a thread safe list, so it should only be used in a single goroutine.

func NewLinkedList added in v0.2.0 

func NewLinkedList[T any]() *LinkedList[T]

Creates a new linked list.

func (*LinkedList[T]) Add added in v0.2.0 

func (ll *LinkedList[T]) Add(value T) *LinkedNode[T]

Adds a new value to the list and returns the new node.

func (*LinkedList[T]) Clear added in v0.2.0 

func (ll *LinkedList[T]) Clear()

Clear removes all values from the list.

func (*LinkedList[T]) Dequeue added in v0.2.0 

func (ll *LinkedList[T]) Dequeue() T

Dequeue removes the value in the beginning of the list and returns it.

func (*LinkedList[T]) DequeueNode added in v0.2.0 

func (ll *LinkedList[T]) DequeueNode() *LinkedNode[T]

DequeueNode removes the node in the beginning of the list and returns it.

func (*LinkedList[T]) Enqueue added in v0.2.0 

func (ll *LinkedList[T]) Enqueue(value T)

Enqueue adds a new value to the end of the list.

func (*LinkedList[T]) EnqueueNode added in v0.2.0 

func (ll *LinkedList[T]) EnqueueNode(n *LinkedNode[T])

EnqueueNode adds a new node to the end of the list.

func (*LinkedList[T]) Head added in v0.6.4 

func (ll *LinkedList[T]) Head() *LinkedNode[T]

Head returns the head of the list. THe head is a dummy node that is not used in the list. The first node in the list is head.Next() if the list is not empty.

func (*LinkedList[T]) IsEmpty added in v0.2.0 

func (ll *LinkedList[T]) IsEmpty() bool

IsEmpty returns true if the list is empty.

func (*LinkedList[T]) Len added in v0.2.0 

func (ll *LinkedList[T]) Len() int

Len returns the number of values in the list. This is O(n) because it has to iterate the list.

func (*LinkedList[T]) Nodes added in v0.2.0 

func (ll *LinkedList[T]) Nodes() iter.Seq[*LinkedNode[T]]

Nodes returns an iterator of the nodes in the list.

func (*LinkedList[T]) Peek added in v0.2.0 

func (ll *LinkedList[T]) Peek() T

Peek returns the first value in the list, or the zero value if the list is empty.

func (*LinkedList[T]) Pop added in v0.2.0 

func (ll *LinkedList[T]) Pop() T

Pop removes the value from the end of the list and returns it.

func (*LinkedList[T]) PopNode added in v0.2.0 

func (ll *LinkedList[T]) PopNode() *LinkedNode[T]

PopNode removes the node from the end of the list and returns it.

func (*LinkedList[T]) Push added in v0.2.0 

func (ll *LinkedList[T]) Push(value T)

Push adds a new value to the end of the list.

func (*LinkedList[T]) PushNode added in v0.2.0 

func (ll *LinkedList[T]) PushNode(n *LinkedNode[T])

PushNode adds a new node to the end of the list.

func (*LinkedList[T]) ToBack added in v0.2.0 

func (ll *LinkedList[T]) ToBack(n *LinkedNode[T])

ToBack moves the node to the back of this list.

func (*LinkedList[T]) ToFront added in v0.2.0 

func (ll *LinkedList[T]) ToFront(n *LinkedNode[T])

ToFront moves the node to the front of this list.

func (*LinkedList[T]) Top added in v0.2.0 

func (ll *LinkedList[T]) Top() T

Top returns the last value in the list, or the zero value if the list is empty.

func (*LinkedList[T]) Values added in v0.2.0 

func (ll *LinkedList[T]) Values() iter.Seq[T]

Values returns an iterator of the values in the list.

type LinkedNode added in v0.2.0 

type LinkedNode[T any] struct {
	Value T
	// contains filtered or unexported fields
}

A linked list node that can be inserted and removed from anywhere in a list in O(1) time.

func NewLinkedNode added in v0.2.0 

func NewLinkedNode[T any](value T) *LinkedNode[T]

NewLinkedNode Creates a new linked node with the given value.

func (*LinkedNode[T]) Get added in v0.2.0 

func (ln *LinkedNode[T]) Get() T

Get returns the value of the linked node, or the zero value if the node is nil.

func (*LinkedNode[T]) InsertAfter added in v0.2.0 

func (ln *LinkedNode[T]) InsertAfter(after *LinkedNode[T])

InsertAfter inserts the node after the given node in the list.

func (*LinkedNode[T]) InsertBefore added in v0.2.0 

func (ln *LinkedNode[T]) InsertBefore(before *LinkedNode[T])

InsertBefore inserts the node before the given node in the list.

func (*LinkedNode[T]) IsRemoved added in v0.2.0 

func (ln *LinkedNode[T]) IsRemoved() bool

IsRemoved returns true if the node is removed from the list.

func (*LinkedNode[T]) Next added in v0.2.0 

func (ln *LinkedNode[T]) Next() *LinkedNode[T]

Next returns the next node in the list, or nil if the node is removed.

func (*LinkedNode[T]) Prev added in v0.2.0 

func (ln *LinkedNode[T]) Prev() *LinkedNode[T]

Prev returns the previous node in the list, or nil if the node is removed.

func (*LinkedNode[T]) Remove added in v0.2.0 

func (ln *LinkedNode[T]) Remove()

remove removes the node from the list by detaching it from its previous and next nodes.

type PriorityQueue 

type PriorityQueue[T any] struct {
	// contains filtered or unexported fields
}

A priority queue implementation that uses a heap to store the items. This is not a thread-safe queue.

func NewPriorityQueue 

func NewPriorityQueue[T any](less Less[T]) *PriorityQueue[T]

NewPriorityQueue creates a new priority queue with the given less function. The less function orders the items in the queue, the first item in the queue is the one that is less than all the others.

func (*PriorityQueue[T]) Clear added in v0.5.0 

func (pq *PriorityQueue[T]) Clear()

Clear clears the queue.

func (*PriorityQueue[T]) Dequeue 

func (pq *PriorityQueue[T]) Dequeue() T

Dequeue removes the item at the front of the queue. If the queue is empty, it returns the zero value of T.

func (*PriorityQueue[T]) Enqueue 

func (pq *PriorityQueue[T]) Enqueue(h T)

Enqueue adds an item to the queue.

func (*PriorityQueue[T]) GetLess added in v0.5.0 

func (pq *PriorityQueue[T]) GetLess() Less[T]

GetLess returns the less function that is used to order the items in the queue.

func (PriorityQueue[T]) IsEmpty added in v0.2.0 

func (pq PriorityQueue[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty.

func (PriorityQueue[T]) Len 

func (pq PriorityQueue[T]) Len() int

Len returns the number of items in the queue.

func (PriorityQueue[T]) Less 

func (pq PriorityQueue[T]) Less(i, j int) bool

Less returns true if the item at index i is less than the item at index j. This is used by the heap interface to order the items in the queue.

func (*PriorityQueue[T]) Peek 

func (pq *PriorityQueue[T]) Peek() T

Peek returns the item at the front of the queue without removing it. If the queue is empty, it returns the zero value of T.

func (*PriorityQueue[T]) Pop 

func (pq *PriorityQueue[T]) Pop() any

Pop removes the item at the end of the queue. This is used by the heap interface to remove items from the queue.

func (*PriorityQueue[T]) Push 

func (pq *PriorityQueue[T]) Push(x any)

Push adds an item to the queue. This is used by the heap interface to add items to the queue.

func (*PriorityQueue[T]) Refresh added in v0.3.0 

func (pq *PriorityQueue[T]) Refresh()

Refresh updates the order of the items in the priority queue if they've become out of order.

func (*PriorityQueue[T]) Remove added in v0.3.0 

func (pq *PriorityQueue[T]) Remove(i int) bool

Remove tries to remove the value at the index from the queue. True is returned if the value is removed.

func (*PriorityQueue[T]) SetIndex added in v0.5.0 

func (pq *PriorityQueue[T]) SetIndex(setIndex func(T, int))

SetIndex sets the function that will be used to set the index of the items in the queue.

func (*PriorityQueue[T]) SetLess added in v0.5.0 

func (pq *PriorityQueue[T]) SetLess(less Less[T])

SetLess sets the less function that will be used to order the items in the queue. This will cause the queue to be re-ordered.

func (PriorityQueue[T]) Swap 

func (pq PriorityQueue[T]) Swap(i, j int)

Swap swaps the items at index i and j. This is used by the heap interface to order the items in the queue.

func (*PriorityQueue[T]) Update added in v0.3.0 

func (pq *PriorityQueue[T]) Update(i int) bool

Update tells the queue that a value has been changed in a way that would affect its order in the queue. True is returned if the value was updated.

func (*PriorityQueue[T]) Values added in v0.2.0 

func (pq *PriorityQueue[T]) Values() iter.Seq[T]

Values returns a sequence of the values in the queue. The order of the values is guaranteed to be in the order of least to greatest according to the less function.

type Queue 

type Queue[T any] interface {
	// Enqueue adds a new element to the end of the queue.
	Enqueue(T)
	// Dequeue removes and returns the first element of the queue.
	// If the queue is empty, it returns the zero value of T.
	Dequeue() T
	// Peek returns the first element of the queue without removing it.
	// If the queue is empty, it returns the zero value of T.
	Peek() T
	// Len returns the number of elements in the queue.
	// This may be O(n) for some implementations.
	Len() int
	// IsEmpty returns true if the queue is empty.
	// This is expected to be O(1) for most implementations.
	IsEmpty() bool
	// Values returns an iterator of the values in the queue.
	// The order of the values is not guaranteed.
	Values() iter.Seq[T]
}

A queue interface that can be used to enqueue and dequeue values. It is a FIFO (First In First Out) data structure that allows adding and removing elements in a specific order.

type ReadyQueue 

type ReadyQueue[T any] struct {
	// contains filtered or unexported fields
}

A ready queue is a thread-safe queue where the Dequeue method blocks until an item is available and meets a ready state. The ready state is a function that returns a value that can be used to compare the item at the front of the queue to the ready state. As soon as the item at the front of the queue is less than the ready state, it is removed from the queue and returned. A ready queue can be dynamic or static. A dynamic ready queue expects that order may change over time so dequeue & ready checking logic needs to restructure the queue before returning the item to ensure the correct next item at dequeue time is returned.

func NewReadyQueue 

func NewReadyQueue[T any](less Less[T], readyState func() T, checkFrequency time.Duration) *ReadyQueue[T]

NewReadyQueue creates a new ReadyQueue with the given less function, ready state function, and check frequency.

func (*ReadyQueue[T]) Dequeue 

func (rq *ReadyQueue[T]) Dequeue() T

Dequeue removes an item from the queue and blocks until an item is available. If the queue is empty, it waits until an item is added to the queue. If the item at the front of the queue is not less than the ready state, it waits until it is checking at the given check frequency.

func (*ReadyQueue[T]) Enqueue 

func (rq *ReadyQueue[T]) Enqueue(item T)

Enqueue adds an item to the queue and signals any waiting goroutines that an item is available.

func (*ReadyQueue[T]) GetLess added in v0.5.0 

func (rq *ReadyQueue[T]) GetLess() Less[T]

GetLess returns the less function that is used to order the items in the queue.

func (*ReadyQueue[T]) Interrupt added in v0.8.1 

func (wq *ReadyQueue[T]) Interrupt()

Interrupt interrupts any waiting goroutines and signals them to wake up.

func (*ReadyQueue[T]) IsEmpty added in v0.2.0 

func (rq *ReadyQueue[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty.

func (*ReadyQueue[T]) Len 

func (rq *ReadyQueue[T]) Len() int

Len returns the number of items in the queue.

func (*ReadyQueue[T]) Peek 

func (rq *ReadyQueue[T]) Peek() T

Peek returns the item at the front of the queue without removing it. If the queue is empty, it returns the zero value of T.

func (*ReadyQueue[T]) Refresh added in v0.3.0 

func (rq *ReadyQueue[T]) Refresh()

Refreshes the order of the items in the priority queue if they've become out of order. This is a no-op if the queue is empty.

func (*ReadyQueue[T]) Remove added in v0.3.0 

func (rq *ReadyQueue[T]) Remove(i int) bool

Remove tries to remove the value at the index from the queue. True is returned if the value is removed.

func (*ReadyQueue[T]) SetDynamic added in v0.5.1 

func (rq *ReadyQueue[T]) SetDynamic(dynamic bool)

SetDynamic sets the dynamic flag for the queue. If true, the queue will be re-ordered before returning the item.

func (*ReadyQueue[T]) SetIndex added in v0.5.0 

func (rq *ReadyQueue[T]) SetIndex(setIndex func(T, int))

SetIndex sets the function that will be used to set the index of the items in the queue.

func (*ReadyQueue[T]) SetLess added in v0.5.0 

func (rq *ReadyQueue[T]) SetLess(less Less[T])

SetLess sets the less function that will be used to order the items in the queue. This will cause the queue to be re-ordered.

func (*ReadyQueue[T]) Update added in v0.3.0 

func (rq *ReadyQueue[T]) Update(i int) bool

Update tells the queue that a value has been changed in a way that would affect its order in the queue. True is returned if the value was updated.

func (*ReadyQueue[T]) Values added in v0.2.0 

func (rq *ReadyQueue[T]) Values() iter.Seq[T]

Values returns a sequence of the values in the queue. The order of the values matches the order of the internal queue.

type Schedule added in v0.7.0 

type Schedule[T any] struct {
	// contains filtered or unexported fields
}

A schedule is a collection of events occurring at specific times. You can Eval() to get events that are due, or you can call Run() to loop sending events to a callback function until a done channel is closed. The schedule is thread-safe and can be used from multiple goroutines.

func NewSchedule added in v0.7.0 

func NewSchedule[T any](getTime func(T) time.Time) *Schedule[T]

NewSchedule creates a new Schedule with the given function to get the time for each event. The getTime function should return the time at which the event is scheduled to occur. The schedule is initialized with the next time set to EndOfTime. If the event does not have a time (yet), it should return EndOfTime. If an event's scheduled time changes,

func (*Schedule[T]) Add added in v0.7.0 

func (s *Schedule[T]) Add(event T) (remove func())

Add adds an event to the schedule and returns a function to remove it. The remove function should be called when the event is no longer needed.

func (*Schedule[T]) CancelInterrupt added in v0.7.1 

func (s *Schedule[T]) CancelInterrupt()

CancelInterrupt cancels the interrupt signal if it has been sent. This is a non-blocking call and will not wait for the schedule to process the signal. It is used to prevent the schedule from being interrupted if it is not needed.

func (*Schedule[T]) Eval added in v0.7.0 

func (s *Schedule[T]) Eval() (ready []T, nextEarliest time.Time)

Eval evaluates the schedule and returns a list of events that are ready (i.e., their scheduled time has passed) and the next earliest time for any remaining events. This is a blocking call and iterates over all events.

func (*Schedule[T]) GetTime added in v0.7.0 

func (s *Schedule[T]) GetTime(event T) time.Time

GetTime returns the scheduled time for the given event based on the time function provided during the creation of the schedule.

func (*Schedule[T]) Interrupt added in v0.7.1 

func (s *Schedule[T]) Interrupt()

Interrupt sends an interrupt signal to the schedule. This is a non-blocking call and will not wait for the schedule to process the signal. It is used to wake up the schedule if it is waiting on a timer.

func (*Schedule[T]) IsEmpty added in v0.7.0 

func (s *Schedule[T]) IsEmpty() bool

IsEmpty checks if the schedule is empty. This is a blocking call.

func (*Schedule[T]) IsRunning added in v0.7.1 

func (s *Schedule[T]) IsRunning() bool

IsRunning checks if the schedule is currently running.

func (*Schedule[T]) LastTime added in v0.7.0 

func (s *Schedule[T]) LastTime() time.Time

LastTime returns the last scheduled time for the events in the schedule. It returns BeginningOfTime if there are no scheduled events. This is a blocking call and iterates over all events.

func (*Schedule[T]) Len added in v0.7.0 

func (s *Schedule[T]) Len() int

Len returns the number of events in the schedule. This is a blocking call. This is O(n) because it has to iterate the list.

func (*Schedule[T]) NextTime added in v0.7.0 

func (s *Schedule[T]) NextTime() time.Time

NextTime returns the next scheduled time for the events in the schedule. It returns EndOfTime if there are no scheduled events.

func (*Schedule[T]) Nodes added in v0.7.0 

func (s *Schedule[T]) Nodes() iter.Seq[*LinkedNode[T]]

Nodes returns a sequence of all nodes in the schedule. Iterating over the nodes allows you to remove any events from the schedule. This is a blocking call and should be used with caution in a multi-threaded environment.

func (*Schedule[T]) Run added in v0.7.0 

func (s *Schedule[T]) Run(done <-chan struct{}, onReady func([]T))

Run starts the schedule and continuously evaluates it until the done channel is closed. It calls the onReady function with the list of ready events whenever they are available. onReady is only called when events are ready and it blocks the schedule so it should return as quickly as possible. 

go s.Run(ctx.Done(), func(ready []T) {
    // Process ready events
})

func (*Schedule[T]) SetNextTime added in v0.7.0 

func (s *Schedule[T]) SetNextTime(nextTime time.Time)

SetNextTime sets the next scheduled time for the events in the schedule. It also resets the timer to trigger at the new time. If the given time is after the earlest event time, it will schedule the events late. If the given time is in the past, it will schedule an Eval() in the Run() loop immediately.

func (*Schedule[T]) Stop added in v0.7.0 

func (s *Schedule[T]) Stop(immediate bool)

Stop stops the schedule. If immediate is true, it stops immediately. If false, it will stop after all events are processed.

func (*Schedule[T]) Update added in v0.7.0 

func (s *Schedule[T]) Update(event T)

Update updates the schedule based on the new time for the event. If the time of the event is more recent than the next time the schedule is set to trigger, it will update the next time.

func (*Schedule[T]) Values added in v0.7.0 

func (s *Schedule[T]) Values() iter.Seq[T]

Values returns a sequence of all events in the schedule. This is a blocking call and should be used with caution in a multi-threaded environment.

type SliceStack added in v0.2.0 

type SliceStack[T any] []T

SliceStack is a stack implementation using a slice.

func (SliceStack[T]) IsEmpty added in v0.2.0 

func (s SliceStack[T]) IsEmpty() bool

IsEmpty returns true if the stack is empty.

func (SliceStack[T]) Len added in v0.2.0 

func (s SliceStack[T]) Len() int

Len returns the number of elements in the stack.

func (*SliceStack[T]) Pop added in v0.2.0 

func (s *SliceStack[T]) Pop() T

Pop removes and returns the top element of the stack. If the stack is empty, it returns the zero value of T.

func (*SliceStack[T]) Push added in v0.2.0 

func (s *SliceStack[T]) Push(value T)

Push adds a new element to the top of the stack.

func (SliceStack[T]) Top added in v0.2.0 

func (s SliceStack[T]) Top() T

Top returns the top element of the stack without removing it. If the stack is empty, it returns the zero value of T.

func (SliceStack[T]) Values added in v0.2.0 

func (s SliceStack[T]) Values() iter.Seq[T]

Values returns an iterator of the values in the stack.

type Stack added in v0.2.0 

type Stack[T any] interface {
	// Push adds a new element to the top of the stack.
	Push(T)
	// Pop removes and returns the top element of the stack.
	// If the stack is empty, it returns the zero value of T.
	Pop() T
	// Top returns the top element of the stack without removing it.
	// If the stack is empty, it returns the zero value of T.
	Top() T
	// Len returns the number of elements in the stack.
	// This may be O(n) for some implementations.
	Len() int
	// IsEmpty returns true if the stack is empty.
	// This is expected to be O(1) for most implementations.
	IsEmpty() bool
	// Values returns an iterator of the values in the stack.
	Values() iter.Seq[T]
}

Stack is a generic stack interface that defines the basic operations of a stack. It is a LIFO (Last In First Out) data structure that allows adding and removing elements in a specific order.

type Stopper 

type Stopper chan struct{}

Stopper is a channel that can be used to signal when a task should stop. It can be used to implement a simple stop mechanism for long-running tasks.

func GoWaiter added in v0.7.0 

func GoWaiter(fn func()) Stopper

GoWaiter runs a function in a separate goroutine and returns a Stopper that can be used to wait for its completion.

func NewStopper 

func NewStopper() Stopper

NewStopper creates a new Stopper channel.

func (Stopper) Stop 

func (s Stopper) Stop()

Stop sends a signal to the Stopper to indicate that it should stop. It closes the channel to prevent further sends.

func (Stopper) Stopped 

func (s Stopper) Stopped() bool

Stopped checks if the Stopper has been stopped.

func (Stopper) Wait 

func (s Stopper) Wait()

Waits for the Stopper to be closed

func (Stopper) WithCancel added in v0.6.0 

func (s Stopper) WithCancel(ctx context.Context) (context.Context, Stopper)

WithCancel creates a new context with a cancel function that is triggered when the Stopper is stopped. It returns the new context and the Stopper itself.

type SyncQueue added in v0.3.1 

type SyncQueue[T any] struct {
	// contains filtered or unexported fields
}

A thread-safe queue implementation.

func NewSyncQueue added in v0.3.1 

func NewSyncQueue[T any](queue Queue[T]) *SyncQueue[T]

NewSyncQueue creates a new SyncQueue with the given queue. The queue is wrapped in a mutex to ensure that all operations are thread-safe.

func (*SyncQueue[T]) Dequeue added in v0.3.1 

func (sq *SyncQueue[T]) Dequeue() T

Dequeue removes an item from the queue. If the queue is empty, a zero value of T is returned. It is safe to call this method concurrently.

func (*SyncQueue[T]) Enqueue added in v0.3.1 

func (sq *SyncQueue[T]) Enqueue(item T)

Enqueue adds an item to the queue. It is safe to call this method concurrently.

func (*SyncQueue[T]) IsEmpty added in v0.3.1 

func (sq *SyncQueue[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty. It is safe to call this method concurrently.

func (*SyncQueue[T]) Len added in v0.3.1 

func (sq *SyncQueue[T]) Len() int

Len returns the number of items in the queue. It is safe to call this method concurrently.

func (*SyncQueue[T]) Peek added in v0.3.1 

func (sq *SyncQueue[T]) Peek() T

Pop removes the item at the end of the queue. If the queue is empty, it returns the zero value of T. It is safe to call this method concurrently.

func (*SyncQueue[T]) Refresh added in v0.5.0 

func (sq *SyncQueue[T]) Refresh()

Refreshes the order of the items in the priority queue if they've become out of order. This is a no-op if the queue is empty. If the queue does not support refresh, it does nothing. It is safe to call this method concurrently.

func (*SyncQueue[T]) Remove added in v0.5.0 

func (sq *SyncQueue[T]) Remove(i int) bool

Remove calls remove on the underlying queue if it exists. If the queue does not support remove, it returns false. It is safe to call this method concurrently.

func (*SyncQueue[T]) Update added in v0.5.0 

func (sq *SyncQueue[T]) Update(i int) bool

Update tells the queue that a value has been changed in a way that would affect its order in the queue. True is returned if the value was updated. If the queue does not support update, it returns false. It is safe to call this method concurrently.

func (*SyncQueue[T]) Values added in v0.3.1 

func (sq *SyncQueue[T]) Values() iter.Seq[T]

Values returns a sequence of the values in the queue. The order of the values matches the order of the internal queue. It locks the queue while iterating over the values. It is not safe to modify the queue while iterating.

type SyncStack added in v0.3.1 

type SyncStack[T any] struct {
	// contains filtered or unexported fields
}

A thread-safe stack implementation.

func NewSyncStack added in v0.3.1 

func NewSyncStack[T any](stack Stack[T]) *SyncStack[T]

NewSyncStack creates a new SyncStack that wraps the given stack.

func (*SyncStack[T]) IsEmpty added in v0.3.1 

func (s *SyncStack[T]) IsEmpty() bool

IsEmpty returns true if the stack is empty. It is safe to call this method concurrently.

func (*SyncStack[T]) Len added in v0.3.1 

func (s *SyncStack[T]) Len() int

Len returns the number of items in the stack. It is safe to call this method concurrently.

func (*SyncStack[T]) Pop added in v0.3.1 

func (s *SyncStack[T]) Pop() T

Pop removes and returns the top item from the stack. If the stack is empty, a zero value of T is returned. It is safe to call this method concurrently.

func (*SyncStack[T]) Push added in v0.3.1 

func (s *SyncStack[T]) Push(item T)

Push adds a new item to the stack. It is safe to call this method concurrently.

func (*SyncStack[T]) Top added in v0.3.1 

func (s *SyncStack[T]) Top() T

Top returns the top item from the stack without removing it. If the stack is empty, a zero value of T is returned. It is safe to call this method concurrently.

func (*SyncStack[T]) Values added in v0.3.1 

func (s *SyncStack[T]) Values() iter.Seq[T]

Values returns an iterator of the values in the stack. The order of the values matches the order of the internal stack. It locks the stack while iterating, so it is not safe to modify the stack while iterating over it.

type WaitQueue 

type WaitQueue[T any] struct {
	// contains filtered or unexported fields
}

A queue implementation that uses an internal queue where the Dequeue method blocks until an item is available.

func NewWaitQueue 

func NewWaitQueue[T any](queue Queue[T]) *WaitQueue[T]

NewWaitQueue creates a new WaitQueue with the given queue.

func (*WaitQueue[T]) Dequeue 

func (wq *WaitQueue[T]) Dequeue() T

Dequeue removes an item from the queue and blocks until an item is available. If the queue is empty, it waits until an item is added to the queue.

func (*WaitQueue[T]) Enqueue 

func (wq *WaitQueue[T]) Enqueue(item T)

Enqueue adds an item to the queue and signals any waiting goroutines that an item is available.

func (*WaitQueue[T]) Interrupt added in v0.8.1 

func (wq *WaitQueue[T]) Interrupt()

Interrupt interrupts any waiting goroutines and signals them to wake up.

func (*WaitQueue[T]) IsEmpty added in v0.2.0 

func (wq *WaitQueue[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty.

func (*WaitQueue[T]) Len 

func (wq *WaitQueue[T]) Len() int

Len returns the number of items in the queue.

func (*WaitQueue[T]) Peek 

func (wq *WaitQueue[T]) Peek() T

Peek returns the item at the front of the queue without removing it. If the queue is empty, it returns the zero value of T.

func (*WaitQueue[T]) Refresh added in v0.5.0 

func (wq *WaitQueue[T]) Refresh()

Refreshes the order of the items in the priority queue if they've become out of order. This is a no-op if the queue is empty. If the queue does not support refresh, it does nothing. It is safe to call this method concurrently.

func (*WaitQueue[T]) Remove added in v0.5.0 

func (wq *WaitQueue[T]) Remove(i int) bool

Remove calls remove on the underlying queue if it exists. If the queue does not support remove, it returns false. It is safe to call this method concurrently.

func (*WaitQueue[T]) Update added in v0.5.0 

func (wq *WaitQueue[T]) Update(i int) bool

Update tells the queue that a value has been changed in a way that would affect its order in the queue. True is returned if the value was updated. If the queue does not support update, it returns false. It is safe to call this method concurrently.

func (*WaitQueue[T]) Values added in v0.2.0 

func (wq *WaitQueue[T]) Values() iter.Seq[T]

Values returns a sequence of the values in the queue. The order of the values matches the order of the internal queue.

type WaitStack added in v0.2.0 

type WaitStack[T any] struct {
	// contains filtered or unexported fields
}

WaitStack is a thread-safe stack implementation that wraps another stack. The Pop method blocks until an item is available to pop.

func NewWaitStack added in v0.2.0 

func NewWaitStack[T any](stack Stack[T]) *WaitStack[T]

NewWaitStack creates a new WaitStack that wraps the given stack.

func (*WaitStack[T]) IsEmpty added in v0.2.0 

func (ts *WaitStack[T]) IsEmpty() bool

IsEmpty returns true if the stack is empty.

func (*WaitStack[T]) Len added in v0.2.0 

func (ts *WaitStack[T]) Len() int

Len returns the number of items in the stack.

func (*WaitStack[T]) Pop added in v0.2.0 

func (wq *WaitStack[T]) Pop() T

Pop removes and returns the top item from the stack. If the stack is empty, it blocks until an item is available.

func (*WaitStack[T]) Push added in v0.2.0 

func (wq *WaitStack[T]) Push(item T)

Push adds a new item to the stack and signals any waiting

func (*WaitStack[T]) Top added in v0.2.0 

func (wq *WaitStack[T]) Top() T

Peek returns the top item from the stack without removing it. If the stack is empty, it returns the zero value of T.

func (*WaitStack[T]) Values added in v0.2.0 

func (ts *WaitStack[T]) Values() iter.Seq[T]

Values returns an iterator of the values in the stack. It locks the stack while iterating, so it is not safe to modify the stack while iterating over it.

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.