collections

package
v1.5.0-alpha5 Latest Latest
Warning

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

Go to latest
Published: Sep 24, 2024 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Index

Constants

View Source
const (
	InitialQueueCapacity = 64
)

Variables

View Source
var (
	ErrEmptyQueue error = errors.New("queue is empty")
	ErrNoMatch    error = errors.New("no items matched")
)

Functions

This section is empty.

Types

type HashedPriorityQueue

type HashedPriorityQueue[K comparable, T any] struct {
	// contains filtered or unexported fields
}

func NewHashedPriorityQueue

func NewHashedPriorityQueue[K comparable, T any](indexer IndexerFunc[K, T]) *HashedPriorityQueue[K, T]

NewHashedPriorityQueue creates a new PriorityQueue that allows us to check if specific items (indexed by a key field) are present in the queue. The provided IndexerFunc will be used on Enqueue/Dequeue to keep the index up to date.

func (*HashedPriorityQueue[K, T]) Contains

func (q *HashedPriorityQueue[K, T]) Contains(id K) bool

Contains will return true if the provided identifier (of type K) will be found in this queue, false if it is not present.

func (*HashedPriorityQueue[K, T]) Dequeue

func (q *HashedPriorityQueue[K, T]) Dequeue() *QueueItem[T]

Dequeue returns the next highest priority item, returning both the data Enqueued previously, and the priority with which it was enqueued. An err (ErrEmptyQueue) may be returned if the queue is currently empty.

func (*HashedPriorityQueue[K, T]) DequeueWhere

func (q *HashedPriorityQueue[K, T]) DequeueWhere(matcher MatchingFunction[T]) *QueueItem[T]

DequeueWhere allows the caller to iterate through the queue, in priority order, and attempt to match an item using the provided `MatchingFunction`. This method has a high time cost as dequeued but non-matching items must be held and requeued once the process is complete. Luckily, we use the same amount of space (bar a few bytes for the extra PriorityQueue) for the dequeued items.

func (*HashedPriorityQueue[K, T]) Enqueue

func (q *HashedPriorityQueue[K, T]) Enqueue(data T, priority int64)

Enqueue will add the item specified by `data` to the queue with the the priority given by `priority`.

func (*HashedPriorityQueue[K, T]) IsEmpty

func (q *HashedPriorityQueue[K, T]) IsEmpty() bool

IsEmpty returns a boolean denoting whether the queue is currently empty or not.

func (*HashedPriorityQueue[K, T]) Len

func (q *HashedPriorityQueue[K, T]) Len() int

Len returns the number of items currently in the queue

type IndexerFunc

type IndexerFunc[K comparable, T any] func(item T) K

IndexerFunc is used to find the key (of type K) from the provided item (T). This will be used for the item lookup in `Contains`

type MatchingFunction

type MatchingFunction[T any] func(possibleMatch T) bool

MatchingFunction can be used when 'iterating' the priority queue to find items with specific properties.

type Pair added in v1.2.2

type Pair[L any, R any] struct {
	Left  L
	Right R
}

Pair is a generic structure that holds two values of any type.

func NewPair added in v1.2.2

func NewPair[L any, R any](left L, right R) Pair[L, R]

NewPair creates a new Pair with the given values.

func (Pair[L, R]) String added in v1.2.2

func (p Pair[L, R]) String() string

String returns a string representation of the Pair.

type PriorityQueue

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

PriorityQueue contains items of type T, and allows you to enqueue and dequeue items with a specific priority. Items are dequeued in highest priority first order.

func NewPriorityQueue

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

NewPriorityQueue creates a new ptr to a priority queue for type T.

func (*PriorityQueue[T]) Dequeue

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

Dequeue returns the next highest priority item, returning both the data Enqueued previously, and the priority with which it was enqueued. An err (ErrEmptyQueue) may be returned if the queue is currently empty.

func (*PriorityQueue[T]) DequeueWhere

func (pq *PriorityQueue[T]) DequeueWhere(matcher MatchingFunction[T]) *QueueItem[T]

DequeueWhere allows the caller to iterate through the queue, in priority order, and attempt to match an item using the provided `MatchingFunction`. This method has a high time cost as dequeued but non-matching items must be held and requeued once the process is complete. Luckily, we use the same amount of space (bar a few bytes for the extra PriorityQueue) for the dequeued items.

func (*PriorityQueue[T]) Enqueue

func (pq *PriorityQueue[T]) Enqueue(data T, priority int64)

Enqueue will add the item specified by `data` to the queue with the the priority given by `priority`.

func (*PriorityQueue[T]) IsEmpty

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

IsEmpty returns a boolean denoting whether the queue is currently empty or not.

func (*PriorityQueue[T]) Len

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

Len returns the number of items currently in the queue

type PriorityQueueInterface

type PriorityQueueInterface[T any] interface {
	// Enqueue will add the item specified by `data` to the queue with the
	// the priority given by `priority`.
	Enqueue(data T, priority int64)

	// Dequeue returns the next highest priority item, returning both
	// the data Enqueued previously, and the priority with which it was
	// enqueued. An err (ErrEmptyQueue) may be returned if the queue is
	// currently empty.
	Dequeue() *QueueItem[T]

	// DequeueWhere allows the caller to iterate through the queue, in priority order, and
	// attempt to match an item using the provided `MatchingFunction`.  This method has a high
	// time cost as dequeued but non-matching items must be held and requeued once the process
	// is complete.  Luckily, we use the same amount of space (bar a few bytes for the
	// extra PriorityQueue) for the dequeued items.
	DequeueWhere(matcher MatchingFunction[T]) *QueueItem[T]

	// Len returns the number of items currently in the queue
	Len() int

	// IsEmpty returns a boolean denoting whether the queue is
	// currently empty or not.
	IsEmpty() bool
}

type QueueItem

type QueueItem[T any] struct {
	Value    T
	Priority int64
}

QueueItem encapsulates an item in the queue when we return it from the various dequeue methods

type ScheduledTask

type ScheduledTask[T any] interface {
	Data() T              // The data object
	ID() string           // ID of the object
	WaitUntil() time.Time // Time to wait until
}

ScheduledTask is an interface type implemented by objects stored in the ScheduledTaskHeap

type ScheduledTaskHeap

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

ScheduledTaskHeap wraps a heap and provides deduplication and operations other than Push/Pop. The heap elements are sorted by the time in the WaitUntil field of scheduledHeapNode

func NewScheduledTaskHeap

func NewScheduledTaskHeap[T any]() *ScheduledTaskHeap[T]

func (*ScheduledTaskHeap[T]) Contains

func (h *ScheduledTaskHeap[T]) Contains(task ScheduledTask[T]) bool

func (*ScheduledTaskHeap[T]) Length

func (h *ScheduledTaskHeap[T]) Length() int

func (*ScheduledTaskHeap[T]) Peek

func (h *ScheduledTaskHeap[T]) Peek() ScheduledTask[T]

func (*ScheduledTaskHeap[T]) Pop

func (h *ScheduledTaskHeap[T]) Pop() ScheduledTask[T]

func (*ScheduledTaskHeap[T]) Push

func (h *ScheduledTaskHeap[T]) Push(task ScheduledTask[T]) error

func (*ScheduledTaskHeap[T]) Remove

func (h *ScheduledTaskHeap[T]) Remove(task ScheduledTask[T])

func (*ScheduledTaskHeap[T]) Update

func (h *ScheduledTaskHeap[T]) Update(task ScheduledTask[T]) error

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL