pq

README

Small library for personal projects that need to use some sort of priority queue. Includes an implementation of a priority channel.

Documentation

Index

• type ChannelMessage
• type Comparator
• type PriorityChannel
  • func NewPriorityChannel[T any]() *PriorityChannel[T]
  • func (pc *PriorityChannel[T]) Close() error
  • func (pc *PriorityChannel[T]) Len() int
  • func (pc *PriorityChannel[T]) Pop(ctx context.Context) (T, int, bool, error)
  • func (pc *PriorityChannel[T]) PopBlocking(ctx context.Context) (T, int, error)
  • func (pc *PriorityChannel[T]) Push(item T, priority int) error
  • func (pc *PriorityChannel[T]) TryImmediatePop() (T, int, bool)
• type PriorityQueue
  • func NewPriorityQueue[C Comparator[T], T any](cmp C) *PriorityQueue[C, T]
  • func (pq *PriorityQueue[C, T]) Len() int
  • func (pq *PriorityQueue[C, T]) Peek() (T, bool)
  • func (pq *PriorityQueue[C, T]) Pop() (T, bool)
  • func (pq *PriorityQueue[C, T]) Push(item T)

Types

type ChannelMessage

type ChannelMessage[T any] struct {
	Payload  T
	Priority int
}

ChannelMessage pairs a pushed payload with the priority it was pushed under.

type Comparator

type Comparator[T any] = func(a, b T) int

Comparator orders two values of type T. It returns a negative number if a sorts before b (a has higher priority), zero if they are equivalent, and a positive number if a sorts after b.

type PriorityChannel

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

PriorityChannel is a concurrency-safe, channel-like queue that always pops the pending item with the highest priority. Zero value is not usable; construct one with NewPriorityChannel.

func NewPriorityChannel

func NewPriorityChannel[T any]() *PriorityChannel[T]

NewPriorityChannel creates an empty, open PriorityChannel.

func (*PriorityChannel[T]) Close

func (pc *PriorityChannel[T]) Close() error

Close stops the channel from accepting further Pushes, blocks until every item already queued has been drained by consumers via Pop or PopBlocking, and then releases the underlying queue. Once Close returns, Push, Pop, and PopBlocking all report the channel as closed.

func (*PriorityChannel[T]) Len

func (pc *PriorityChannel[T]) Len() int

Len returns the number of items currently pending in the channel.

func (*PriorityChannel[T]) Pop

func (pc *PriorityChannel[T]) Pop(ctx context.Context) (T, int, bool, error)

Pop attempts to pop the highest-priority item without waiting for the queue to become non-empty; it only waits for the internal lock, racing that wait against ctx cancellation. If the queue is currently empty it returns ok=false with a nil error. It returns a non-nil error if ctx is canceled before the lock is acquired, or if the channel has been closed.

func (*PriorityChannel[T]) PopBlocking

func (pc *PriorityChannel[T]) PopBlocking(ctx context.Context) (T, int, error)

PopBlocking blocks until the highest-priority item is available to pop, ctx is canceled, or the channel is closed. It returns ctx.Err() on cancellation, or an error if the channel is closed before an item is available.

func (*PriorityChannel[T]) Push

func (pc *PriorityChannel[T]) Push(item T, priority int) error

Push adds item to the channel under the given priority, waking one blocked PopBlocking caller if any is waiting. It returns an error without enqueueing item if the channel has been closed.

func (*PriorityChannel[T]) TryImmediatePop

func (pc *PriorityChannel[T]) TryImmediatePop() (T, int, bool)

TryImmediatePop pops the highest-priority item without blocking at all. If the internal lock is currently held elsewhere it immediately returns ok=false rather than waiting for it.

type PriorityQueue

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

PriorityQueue is a binary-heap priority queue ordered by cmp. It is not safe for concurrent use; callers needing concurrency should use PriorityChannel instead.

func NewPriorityQueue

func NewPriorityQueue[C Comparator[T], T any](cmp C) *PriorityQueue[C, T]

NewPriorityQueue creates an empty PriorityQueue that orders items using cmp.

func (*PriorityQueue[C, T]) Len

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

Len returns the number of items currently in the queue.

func (*PriorityQueue[C, T]) Peek

func (pq *PriorityQueue[C, T]) Peek() (T, bool)

Peek returns the highest-priority item in the queue without removing it. The returned bool is false, with a zero value, if the queue is empty.

func (*PriorityQueue[C, T]) Pop

func (pq *PriorityQueue[C, T]) Pop() (T, bool)

Pop removes and returns the highest-priority item in the queue. The returned bool is false, with a zero value, if the queue is empty.

func (*PriorityQueue[C, T]) Push

func (pq *PriorityQueue[C, T]) Push(item T)

Push inserts item into the queue.