queue package - github.com/adrianbrad/queue - Go Packages (original) (raw)

Package queue provides multiple thread-safe generic queue implementations. Currently, there are 2 available implementations:

A blocking queue, which provides methods that wait for the queue to have available elements when attempting to retrieve an element, and waits for a free slot when attempting to insert an element.

A priority queue based on a container.Heap. The elements in the queue must implement the Lesser interface, and are ordered based on the Less method. The head of the queue is always the highest priority element.

A circular queue, which is a queue that uses a fixed-size slice as if it were connected end-to-end. When the queue is full, adding a new element to the queue overwrites the oldest element.

A linked queue, implemented as a singly linked list, offering O(1) time complexity for enqueue and dequeue operations. The queue maintains pointers to both the head (front) and tail (end) of the list for efficient operations without the need for traversal.

This section is empty.

This section is empty.

Blocking is a Queue implementation that additionally supports operations that wait for the queue to have available items, and wait for a slot to become available in case the queue is full. ! The Blocking Queue shares most functionality with channels. If you do not make use of Peek, Reset and Contains methods you are safe to use channels instead.

It supports operations for retrieving and adding elements to a FIFO queue. If there are no elements available the retrieve operations wait until elements are added to the queue.

package main

import ( "fmt" "time"

"github.com/adrianbrad/queue"

)

func main() { elems := []int{1, 2, 3}

blockingQueue := queue.NewBlocking(elems, queue.WithCapacity(4))

containsThree := blockingQueue.Contains(3)
fmt.Println("Contains 3:", containsThree)

size := blockingQueue.Size()
fmt.Println("Size:", size)

empty := blockingQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)

clearElems := blockingQueue.Clear()
fmt.Println("Clear:", clearElems)

empty = blockingQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)

var (
    elem  int
    after time.Duration
)

done := make(chan struct{})

start := time.Now()

// this function waits for a new element to be available in the queue.
go func() {
    defer close(done)

    elem = blockingQueue.GetWait()
    after = time.Since(start)
}()

time.Sleep(time.Millisecond)

// insert a new element into the queue.
if err := blockingQueue.Offer(4); err != nil {
    fmt.Println("Offer err:", err)
    return
}

nextElem, err := blockingQueue.Peek()
if err != nil {
    fmt.Println("Peek err:", err)
    return
}

fmt.Println("Peeked elem:", nextElem)

<-done

fmt.Printf(
    "Elem %d received after %s",
    elem,
    after.Round(time.Millisecond),
)

}

Output:

Contains 3: true Size: 3 Empty before clear: false Clear: [1 2 3] Empty after clear: true Peeked elem: 4 Elem 4 received after 1ms

func NewBlocking[T comparable]( elems []T, opts ...Option, ) *Blocking[T]

NewBlocking returns a new Blocking Queue containing the given elements.

func (bq *Blocking[T]) Clear() []T

Clear removes and returns all elements from the queue.

func (bq *Blocking[T]) Contains(elem T) bool

Contains returns true if the queue contains the given element.

func (bq *Blocking[T]) Get() (v T, _ error)

Get removes and returns the head of the elements queue. If no element is available it returns an ErrNoElementsAvailable error.

func (bq *Blocking[T]) GetWait() (v T)

GetWait removes and returns the head of the elements queue. If no element is available it waits until the queue has an element available.

func (bq *Blocking[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty.

func (bq *Blocking[T]) Iterator() <-chan T

Iterator returns an iterator over the elements in this queue. It removes the elements from the queue.

MarshalJSON serializes the Blocking queue to JSON.

func (bq *Blocking[T]) Offer(elem T) error

Offer inserts the element to the tail the queue. If the queue is full it returns the ErrQueueIsFull error.

func (bq *Blocking[T]) OfferWait(elem T)

OfferWait inserts the element to the tail the queue. It waits for necessary space to become available.

func (bq *Blocking[T]) Peek() (v T, _ error)

Peek retrieves but does not return the head of the queue. If no element is available it returns an ErrNoElementsAvailable error.

func (bq *Blocking[T]) PeekWait() T

PeekWait retrieves but does not return the head of the queue. If no element is available it waits until the queue has an element available.

func (bq *Blocking[T]) Reset()

Reset sets the queue to its initial state with the original elements.

func (bq *Blocking[T]) Size() int

Size returns the number of elements in the queue.

Circular is a Queue implementation. A circular queue is a queue that uses a fixed-size slice as if it were connected end-to-end. When the queue is full, adding a new element to the queue overwrites the oldest element.

Example: We have the following queue with a capacity of 3 elements: [1, 2, 3]. If the tail of the queue is set to 0, as if we just added the element `3`, then the next element to be added to the queue will overwrite the element at index 0. So, if we add the element `4`, the queue will look like this: [4, 2, 3]. If the head of the queue is set to 0, as if we never removed an element yet, then the next element to be removed from the queue will be the element at index 0, which is `4`.

package main

import ( "fmt"

"github.com/adrianbrad/queue"

)

func main() { elems := []int{1, 2, 3}

const capacity = 4

priorityQueue := queue.NewCircular(
    elems,
    capacity,
)

containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)

size := priorityQueue.Size()
fmt.Println("Size:", size)

if err := priorityQueue.Offer(4); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

nextElem, err := priorityQueue.Peek()
if err != nil {
    fmt.Println("Peek err: ", err)
    return
}

fmt.Println("Peek:", nextElem)

if err := priorityQueue.Offer(5); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

fmt.Println("Offered 5")

if err := priorityQueue.Offer(6); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

fmt.Println("Offered 6")

clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)

fmt.Println("Offered 7")

if err := priorityQueue.Offer(7); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

elem, err := priorityQueue.Get()
if err != nil {
    fmt.Println("Get err: ", err)
    return
}

fmt.Println("Get:", elem)

}

Output:

Contains 2: true Size: 3 Peek: 1 Offered 5 Offered 6 Clear: [5 6 3 4] Offered 7 Get: 7

func NewCircular[T comparable]( givenElems []T, capacity int, opts ...Option, ) *Circular[T]

NewCircular creates a new Circular Queue containing the given elements.

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

Clear removes all elements from the queue.

func (q *Circular[T]) Contains(elem T) bool

Contains returns true if the queue contains the given element.

func (q *Circular[T]) Get() (v T, _ error)

Get returns the element at the head of the queue.

func (q *Circular[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty.

func (q *Circular[T]) Iterator() <-chan T

Iterator returns an iterator over the elements in the queue. It removes the elements from the queue.

MarshalJSON serializes the Circular queue to JSON.

func (q *Circular[T]) Offer(item T) error

Offer adds an element into the queue. If the queue is full then the oldest item is overwritten.

func (q *Circular[T]) Peek() (v T, _ error)

Peek returns the element at the head of the queue.

func (q *Circular[T]) Reset()

Reset resets the queue to its initial state.

func (q *Circular[T]) Size() int

Size returns the number of elements in the queue.

Linked represents a data structure representing a queue that uses a linked list for its internal storage.

package main

import ( "fmt"

"github.com/adrianbrad/queue"

)

func main() { elems := []int{2, 4, 1}

priorityQueue := queue.NewLinked(
    elems,
)

containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)

size := priorityQueue.Size()
fmt.Println("Size:", size)

if err := priorityQueue.Offer(3); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

empty := priorityQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)

clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)

empty = priorityQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)

if err := priorityQueue.Offer(5); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

elem, err := priorityQueue.Get()
if err != nil {
    fmt.Println("Get err: ", err)
    return
}

fmt.Println("Get:", elem)

}

Output:

Contains 2: true Size: 3 Empty before clear: false Clear: [2 4 1 3] Empty after clear: true Get: 5

NewLinked creates a new Linked containing the given elements.

func (lq *Linked[T]) Clear() []T

Clear removes and returns all elements from the queue.

func (lq *Linked[T]) Contains(value T) bool

Contains returns true if the queue contains the element.

func (lq *Linked[T]) Get() (elem T, _ error)

Get retrieves and removes the head of the queue.

func (lq *Linked[T]) IsEmpty() bool

IsEmpty returns true if the queue is empty, false otherwise.

func (lq *Linked[T]) Iterator() <-chan T

Iterator returns a channel that will be filled with the elements. It removes the elements from the queue.

MarshalJSON serializes the Linked queue to JSON.

func (lq *Linked[T]) Offer(value T) error

Offer inserts the element into the queue.

func (lq *Linked[T]) Peek() (elem T, _ error)

Peek retrieves but does not remove the head of the queue.

func (lq *Linked[T]) Reset()

Reset sets the queue to its initial state.

func (lq *Linked[T]) Size() int

Size returns the number of elements in the queue.

type Option interface {

}

An Option configures a Queue using the functional options paradigm.

func WithCapacity(capacity int) Option

WithCapacity specifies a fixed capacity for a queue.

Priority is a Queue implementation.

The ordering is given by the lessFunc. The head of the queue is always the highest priority element.

! If capacity is provided and is less than the number of elements provided, the elements slice is sorted and trimmed to fit the capacity.

For ordered types (types that support the operators < <= >= >), the order can be defined by using the following operators: > - for ascending order < - for descending order.

package main

import ( "fmt"

"github.com/adrianbrad/queue"

)

func main() { elems := []int{2, 4, 1}

priorityQueue := queue.NewPriority(
    elems,
    func(elem, otherElem int) bool {
        return elem < otherElem
    },
    queue.WithCapacity(4),
)

containsTwo := priorityQueue.Contains(2)
fmt.Println("Contains 2:", containsTwo)

size := priorityQueue.Size()
fmt.Println("Size:", size)

if err := priorityQueue.Offer(3); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

empty := priorityQueue.IsEmpty()
fmt.Println("Empty before clear:", empty)

clearElems := priorityQueue.Clear()
fmt.Println("Clear:", clearElems)

empty = priorityQueue.IsEmpty()
fmt.Println("Empty after clear:", empty)

if err := priorityQueue.Offer(5); err != nil {
    fmt.Println("Offer err: ", err)
    return
}

elem, err := priorityQueue.Get()
if err != nil {
    fmt.Println("Get err: ", err)
    return
}

fmt.Println("Get:", elem)

}

Output:

Contains 2: true Size: 3 Empty before clear: false Clear: [1 2 3 4] Empty after clear: true Get: 5

func NewPriority[T comparable]( elems []T, lessFunc func(elem, otherElem T) bool, opts ...Option, ) *Priority[T]

NewPriority creates a new Priority Queue containing the given elements. It panics if lessFunc is nil.

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

Clear removes all elements from the queue.

func (pq *Priority[T]) Contains(a T) bool

Contains returns true if the queue contains the element, false otherwise.

func (pq *Priority[T]) Get() (elem T, _ error)

Get removes and returns the head of the queue. If no element is available it returns an ErrNoElementsAvailable error.

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

IsEmpty returns true if the queue is empty, false otherwise.

func (pq *Priority[T]) Iterator() <-chan T

Iterator returns an iterator over the elements in the queue. It removes the elements from the queue.

MarshalJSON serializes the Priority queue to JSON.

func (pq *Priority[T]) Offer(elem T) error

Offer inserts the element into the queue. If the queue is full it returns the ErrQueueIsFull error.

func (pq *Priority[T]) Peek() (elem T, _ error)

Peek retrieves but does not return the head of the queue.

func (pq *Priority[T]) Reset()

Reset sets the queue to its initial stat, by replacing the current elements with the elements provided at creation.

func (pq *Priority[T]) Size() int

Size returns the number of elements in the queue.

type Queue[T comparable] interface {

Get() (T, [error](/builtin#error))


Offer(elem T) [error](/builtin#error)


Reset()


Contains(elem T) [bool](/builtin#bool)


Peek() (T, [error](/builtin#error))


Size() [int](/builtin#int)


IsEmpty() [bool](/builtin#bool)


Iterator() <-chan T


Clear() []T

}

A Queue is an ordered sequence of items, the order is usually first in first out. New items are added to the back of the queue and existing items are removed from the front of the queue.

This interface provides basic methods for adding and extracting elements from the queue. Items are extracted from the head of the queue and added to the tail of the queue.