collections

package
v1.3.0 Latest Latest
Warning

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

 Go to latest Published: Mar 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 int)

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 int)

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 int)

	// 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 int
}

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

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.