priorityqueue

package module
v0.1.0-alpha Latest Latest
Warning

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

 Go to latest Published: Sep 29, 2024 License: Apache-2.0 Imports: 7 Imported by: 1

README

xybor founder Go Reference GitHub Repo stars GitHub top language GitHub go.mod Go version GitHub release (release name instead of tag name) Codacy Badge Codacy Badge Go Report

Introduction

A fast, thread-safe implementation of Priority Queue in Golang

Get started

pqueue := priorityqueue.Default[int]()

// Setup priority level.
pqueue.SetPriority(Urgent, 0)
pqueue.SetPriority(Necessary, 5)
pqueue.SetPriority(Lazy, 10)
pqueue.SetPriority(Background, 100)

// Specially for the Necessary level, after 500 miliseconds since the element is
// enqueued into the queue, its priority level will be raised up.
pqueue.SetAgingTimeSlice(Necessary, 500*time.Millisecond)

// Enqueue three elements to Lazy level.
pqueue.Enqueue(Lazy, 4, 5, 6)

// Enqueue an element to Urgent level.
pqueue.Enqueue(Urgent, 1)

// Enqueue two elements to Necessary level.
pqueue.Enqueue(Necessary, 2, 3)

// Use Dequeue() to get the first highest priority element.
v, err := pqueue.Dequeue()
assert.NoError(t, err)
assert.Equal(t, 1, v.To())

// Or use JustDequeue(), a shortcut of Dequeue().
assert.Equal(t, 2, pqueue.JustDequeue().To())
assert.Equal(t, 3, pqueue.JustDequeue().To())
assert.Equal(t, 4, pqueue.JustDequeue().To())
assert.Equal(t, 5, pqueue.JustDequeue().To())
assert.Equal(t, 6, pqueue.JustDequeue().To())
assert.Nil(t, pqueue.JustDequeue())

Documentation

Index

Constants

View Source 
const NoAging = time.Duration(0)

Variables

View Source 
var ErrEmpty = errors.New("queue is empty")
View Source 
var ErrExistedLevel = errors.New("level has already existed")
View Source 
var ErrNotExistedLevel = errors.New("not found level")
View Source 
var ErrNotMeetCondition = errors.New("not meet condition")
View Source 
var ErrTimeout = errors.New("timeout")

Functions

This section is empty.

Types

type Element 

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

Element is a wrapper of an element in priority queue. It contains some metadata.

func (Element[T]) Level 

func (e Element[T]) Level() int

Level returns the current priority level value (after aging).

func (Element[T]) OriginalLevel 

func (e Element[T]) OriginalLevel() int

OriginalLevel returns the original priority level value.

func (Element[T]) OriginalPriority 

func (e Element[T]) OriginalPriority() any

OriginalPriority returns the original priority.

func (Element[T]) Priority 

func (e Element[T]) Priority() any

Priority returns the current priority (after aging).

func (Element[T]) To 

func (e Element[T]) To() T

To returns the inner value of the Element.

type MultiLevelQueue 

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

MultiLevelQueue is a queue supporting multiple inner queues.

func DefaultMultiLevelQueue 

func DefaultMultiLevelQueue[T any]() *MultiLevelQueue[T]

DefaultMultiLevelQueue returns an empty MultiLevelQueue with the default inner Queue.

func NewMultiLevelQueue 

func NewMultiLevelQueue[T any](queuer func() Queuer[T]) *MultiLevelQueue[T]

NewMultiLevelQueue returns an empty MultiLevelQueue with a customized Queuer.

func (*MultiLevelQueue[T]) AddLevel 

func (mq *MultiLevelQueue[T]) AddLevel(level any) error

AddLevel adds a new queue in MultiLevelQueue.

func (*MultiLevelQueue[T]) Dequeue 

func (mq *MultiLevelQueue[T]) Dequeue(level any) (T, error)

Dequeue returns the first element of a specific queue.

func (*MultiLevelQueue[T]) DequeueIf 

func (mq *MultiLevelQueue[T]) DequeueIf(level any, cond func(T) (bool, error)) (T, error)

DequeueIf returns the first element of a specific level queue if it sastifies the condition.

func (*MultiLevelQueue[T]) Enqueue 

func (mq *MultiLevelQueue[T]) Enqueue(level any, obj ...T) error

Enqueue pushes some values into queue with a given level.

func (*MultiLevelQueue[T]) HasLevel 

func (mq *MultiLevelQueue[T]) HasLevel(level any) bool

HasLevel returns true if the level has existed in MultiLevelQueue.

func (*MultiLevelQueue[T]) Length 

func (mq *MultiLevelQueue[T]) Length(level any) int

Length returns the number of elements with a given level.

func (*MultiLevelQueue[T]) TotalLength 

func (mq *MultiLevelQueue[T]) TotalLength() int

TotalLength returns the number of elements in MultiLevelQueue.

func (*MultiLevelQueue[T]) WaitDequeue 

func (mq *MultiLevelQueue[T]) WaitDequeue(ctx context.Context, level any) (T, error)

WaitDequeueIf returns the first element of a specific queue. It blocks the current process if the queue is empty.

func (*MultiLevelQueue[T]) WaitDequeueAll 

func (mq *MultiLevelQueue[T]) WaitDequeueAll(ctx context.Context) (T, error)

func (*MultiLevelQueue[T]) WaitDequeueIf 

func (mq *MultiLevelQueue[T]) WaitDequeueIf(
	ctx context.Context,
	level any,
	cond func(T) (bool, error),
	retrigger func(T) <-chan time.Time,
) (T, error)

WaitDequeueIf returns the first element of a specific queue if it sastifies the condition. It blocks the current process if the queue is empty.

type PriorityQueue 

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

PriorityQueue implements a fast, thread-safe priority queue.

func Default 

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

Default returns an empty PriorityQueue with the default MultiLevelQueue.

func New 

func New[T any](core *MultiLevelQueue[Element[T]]) *PriorityQueue[T]

New returns an empty PriorityQueue with the customized metadata.

func (*PriorityQueue[T]) Dequeue 

func (pq *PriorityQueue[T]) Dequeue() (Element[T], error)

Dequeue pops the first element which has the highest priority in PriorityQueue.

func (*PriorityQueue[T]) Enqueue 

func (pq *PriorityQueue[T]) Enqueue(priority any, values ...T) error

Enqueue pushes some values into PriorityQueue with a specific Priority.

func (*PriorityQueue[T]) ForceAging 

func (pq *PriorityQueue[T]) ForceAging() error

ForceAging do checking aging immediately no matter of the aging-interval.

func (*PriorityQueue[T]) HasLevel 

func (pq *PriorityQueue[T]) HasLevel(level int) bool

HasLevel returns true if the level value has existed in PriorityQueue.

func (*PriorityQueue[T]) HasPriority 

func (pq *PriorityQueue[T]) HasPriority(priority any) bool

HasPriority returns true if the Priority has existed in PriorityQueue.

func (*PriorityQueue[T]) JustDequeue 

func (pq *PriorityQueue[T]) JustDequeue() *Element[T]

JustDequeue is a wrapper method of Dequeue, it returns nil when the queue is empty, and panics if got other errors.

func (*PriorityQueue[T]) JustWaitDequeue 

func (pq *PriorityQueue[T]) JustWaitDequeue(ctx context.Context) *Element[T]

JustWaitDequeue is a wrapper function of WaitDequeue, it returns nil if the timeout is reached, and panic if got other errors.

func (*PriorityQueue[T]) Length 

func (pq *PriorityQueue[T]) Length(priority any) int

Length returns the number of elements with a given priority.

func (*PriorityQueue[T]) SetAgingInterval 

func (pq *PriorityQueue[T]) SetAgingInterval(interval time.Duration)

SetAgingInterval sets the interval. The PriorityQueue will check the aging every the interval passes. If the interval is unset, it will be chosen automatically (equal to the least aging timeslice of all levels)

func (*PriorityQueue[T]) SetAgingTimeSlice 

func (pq *PriorityQueue[T]) SetAgingTimeSlice(priority any, timeslice time.Duration) error

SetAgingTimeSlice sets the aging time slice for a specific level. If an element existed for more than this time slice, it will be moved to the next higher level.

func (*PriorityQueue[T]) SetDefaultAgingTimeSlice 

func (pq *PriorityQueue[T]) SetDefaultAgingTimeSlice(timeslice time.Duration) error

SetDefaultAgingTimeSlice sets the default aging time slice for Priority levels which have not set the aging yet. If an element existed for more than this time slice, it will be moved to the next higher level.

func (*PriorityQueue[T]) SetPriority 

func (pq *PriorityQueue[T]) SetPriority(priority any, level int) error

SetPriority assigns a new Priority with a level value.

func (*PriorityQueue[T]) TotalLength 

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

TotalLength returns the total number of elements in PriorityQueue.

func (*PriorityQueue[T]) WaitDequeue 

func (pq *PriorityQueue[T]) WaitDequeue(ctx context.Context) (Element[T], error)

WaitDequeue returns first element which has the highest priority. Differ from Dequeue, this method will blocks the current process if the queue is empty.

type Queue 

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

Queue is a default implementation of Queuer. It is a wrapper of slice. It uses mutex to keep the queue thread-safe.

func NewQueue 

func NewQueue[T any]() *Queue[T]

NewQueue returns an empty Queue.

func (*Queue[T]) Back 

func (q *Queue[T]) Back() (T, error)

Back returns the last element of queue without popping it out.

func (*Queue[T]) Clear 

func (q *Queue[T]) Clear()

Clear removes all elements in the queue.

func (*Queue[T]) Dequeue 

func (q *Queue[T]) Dequeue() (T, error)

Dequeue pops the first element of queue.

func (*Queue[T]) DequeueIf 

func (q *Queue[T]) DequeueIf(cond func(t T) (bool, error)) (T, error)

DequeueIf pops the first element in queue if it satifies the condition.

func (*Queue[T]) Enqueue 

func (q *Queue[T]) Enqueue(obj ...T) error

Enqueue pushes some elements into the end of queue.

func (*Queue[T]) Front 

func (q *Queue[T]) Front() (T, error)

Front returns the first element of queue without popping it out.

func (*Queue[T]) Length 

func (q *Queue[T]) Length() int

Length returns the number of elements in the queue.

func (*Queue[T]) WaitDequeue 

func (q *Queue[T]) WaitDequeue(ctx context.Context) (T, error)

WaitDequeue is the blocking-version of Dequeue.

func (*Queue[T]) WaitDequeueIf 

func (q *Queue[T]) WaitDequeueIf(
	ctx context.Context,
	cond func(t T) (bool, error),
	retrigger func(T) <-chan time.Time,
) (T, error)

WaitDequeueIf is the blocking version of DequeueIf.

type Queuer 

type Queuer[T any] interface {
	// Enqueue push an element into the queue.
	Enqueue(obj ...T) error

	// DequeueIf returns and removes the element at the begining of the queue if
	// the element meets the condition. This function is non-blocking.
	DequeueIf(func(t T) (bool, error)) (T, error)

	// Dequeue returns and removes the element at the begining of the queue.
	// This function is non-blocking.
	Dequeue() (T, error)

	// WaitDequeueIf is the same as DequeueIf, but this function is blocking.
	//
	// If the condition was not sastified, this function will check again when
	// the returned channel of retrigger function sends a signal.
	//
	// If you want returns immediately when the condition was not sastified,
	// pass a nil value to the retrigger parameter.
	//
	// For example:
	// 	// No retrigger.
	// 	queue.WaitDequeueIf(ctx, nil, nil)
	//
	//	// Retrigger after some time.
	// 	queue.WaitDequeueIf(
	//  	ctx,
	// 		func(t time.Time) (bool, error) {
	// 			return time.Now().After(t), nil
	// 		},
	//		func(t time.Time) <- chan time.Time {
	//			// Approach 1: Check after every 5 minutes.
	//			return time.After(5*time.Minutes)
	//
	//			// Approach 2: Re-check at t.
	//			return time.After(time.Since(t))
	// 		}
	// 	)
	WaitDequeueIf(
		ctx context.Context,
		cond func(t T) (bool, error),
		retrigger func(T) <-chan time.Time,
	) (T, error)

	// WaitDequeue is the same as Dequeue, but this function is blocking.
	WaitDequeue(ctx context.Context) (T, error)

	// Front returns the element at the begining of the queue.
	Front() (T, error)

	// Back returns the element at the end of the queue.
	Back() (T, error)

	// Clear removes all elements in the queue.
	Clear()

	// Length returns the number of elements in the queue.
	Length() int
}

Queuer represents for a thread-safe queue.

type WaitResult 

type WaitResult[T any] struct {
	Value T
	Err   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.