Documentation
¶
Overview ¶
Package priorityqueue implements a priority queue backed by binary queue.
An unbounded priority queue based on a priority queue. The elements of the priority queue are ordered by a comparator provided at queue construction time.
The heap of this queue is the least/smallest element with respect to the specified ordering. If multiple elements are tied for least value, the heap is one of those elements arbitrarily.
Structure is not thread safe.
References: https://en.wikipedia.org/wiki/Priority_queue
Index ¶
- type OrderedIterator
- type Queue
- func New[T any](comparator utils.Comparator[T], values ...T) *Queue[T]
- func NewFromIterator[T any](comparator utils.Comparator[T], begin ds.ReadCompForIterator[T]) *Queue[T]
- func NewFromIterators[T any](comparator utils.Comparator[T], begin ds.ReadCompForIterator[T], ...) *Queue[T]
- func NewFromSlice[T any](comparator utils.Comparator[T], slice []T) *Queue[T]
- func (stack *Queue[T]) Begin() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
- func (queue *Queue[T]) Clear()
- func (queue *Queue[T]) Dequeue() (value T, ok bool)
- func (stack *Queue[T]) End() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
- func (queue *Queue[T]) Enqueue(value T)
- func (stack *Queue[T]) First() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
- func (queue *Queue[T]) FromJSON(data []byte) error
- func (queue *Queue[T]) GetValues() []T
- func (queue *Queue[T]) IsEmpty() bool
- func (stack *Queue[T]) Last() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
- func (queue *Queue[T]) MarshalJSON() ([]byte, error)
- func (list *Queue[T]) NewOrderedIterator(q *Queue[T], index int) *OrderedIterator[T]
- func (queue *Queue[T]) Peek() (value T, ok bool)
- func (queue *Queue[T]) Size() int
- func (queue *Queue[T]) ToJSON() ([]byte, error)
- func (queue *Queue[T]) ToString() string
- func (queue *Queue[T]) UnmarshalJSON(bytes []byte) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type OrderedIterator ¶ added in v0.16.2
type OrderedIterator[T any] struct { *binaryheap.OrderedIterator[T] }
Iterator holding the iterator's state
func (*OrderedIterator[T]) DistanceTo ¶ added in v0.16.2
func (it *OrderedIterator[T]) DistanceTo(other ds.OrderedIterator) int
DistanceTo implements ds.ReadWriteOrdCompBidRandCollIterator If other is of type IndexedIterator, IndexedIterator.Index() will be used, possibly executing in O(1)
func (*OrderedIterator[T]) IsAfter ¶ added in v0.16.2
func (it *OrderedIterator[T]) IsAfter(other ds.OrderedIterator) bool
IsAfter implements ds.ReadWriteOrdCompBidRandCollIterator
func (*OrderedIterator[T]) IsBefore ¶ added in v0.16.2
func (it *OrderedIterator[T]) IsBefore(other ds.OrderedIterator) bool
IsBefore implements ds.ReadWriteOrdCompBidRandCollIterator
func (*OrderedIterator[T]) IsEqual ¶ added in v0.16.2
func (it *OrderedIterator[T]) IsEqual(other ds.ComparableIterator) bool
IsEqual implements ds.ReadWriteOrdCompBidRandCollIterator
type Queue ¶
type Queue[T any] struct { Comparator utils.Comparator[T] // contains filtered or unexported fields }
Queue holds elements in an array-queue
func New ¶ added in v0.16.2
func New[T any](comparator utils.Comparator[T], values ...T) *Queue[T]
New instantiates a new empty queue with the custom comparator.
func NewFromIterator ¶ added in v0.16.2
func NewFromIterator[T any](comparator utils.Comparator[T], begin ds.ReadCompForIterator[T]) *Queue[T]
NewFromIterator instantiates a new queue containing the elements provided by the passed iterator.
func NewFromIterators ¶ added in v0.16.2
func NewFromIterators[T any](comparator utils.Comparator[T], begin ds.ReadCompForIterator[T], end ds.ComparableIterator) *Queue[T]
NewFromIterators instantiates a new queue containing the elements provided by first, until it is equal to end. end is a sentinel and not included.
func NewFromSlice ¶ added in v0.16.2
func NewFromSlice[T any](comparator utils.Comparator[T], slice []T) *Queue[T]
NewFromSlice instantiates a new queue containing the provided slice.
func (*Queue[T]) Begin ¶ added in v0.16.1
func (stack *Queue[T]) Begin() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
Begin returns an initialized iterator, which points to one element before it's first. Unless Next() is called, the iterator is in an invalid state.
func (*Queue[T]) Dequeue ¶
Dequeue removes first element of the queue and returns it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to dequeue.
func (*Queue[T]) End ¶ added in v0.16.1
func (stack *Queue[T]) End() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
End returns an initialized iterator, which points to one element afrer it's last. Unless Previous() is called, the iterator is in an invalid state.
func (*Queue[T]) Enqueue ¶
func (queue *Queue[T]) Enqueue(value T)
Enqueue adds a value to the end of the queue
func (*Queue[T]) First ¶ added in v0.16.1
func (stack *Queue[T]) First() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
First returns an initialized iterator, which points to it's first element.
func (*Queue[T]) GetValues ¶ added in v0.3.0
func (queue *Queue[T]) GetValues() []T
Values returns all elements in the queue.
func (*Queue[T]) IsEmpty ¶ added in v0.3.0
Empty returns true if queue does not contain any elements.
func (*Queue[T]) Last ¶ added in v0.16.1
func (stack *Queue[T]) Last() ds.ReadWriteOrdCompBidRandCollIterator[int, T]
Last returns an initialized iterator, which points to it's last element.
func (*Queue[T]) MarshalJSON ¶
MarshalJSON @implements json.Marshaler
func (*Queue[T]) NewOrderedIterator ¶ added in v0.16.2
func (list *Queue[T]) NewOrderedIterator(q *Queue[T], index int) *OrderedIterator[T]
NewIterator returns a stateful iterator whose values can be fetched by an index.
func (*Queue[T]) Peek ¶
Peek returns top element on the queue without removing it, or nil if queue is empty. Second return parameter is true, unless the queue was empty and there was nothing to peek.
func (*Queue[T]) UnmarshalJSON ¶
UnmarshalJSON @implements json.Unmarshaler
Source Files