Documentation
¶
Index ¶
- func Apply[T any](queue *PriorityQueue[T], f func(item T))
- func Fold[T any, G any](queue *PriorityQueue[T], initialAccumulator G, f func(item T, accumulator G) G) G
- func Map[T any](queue *PriorityQueue[T], f func(item T) T)
- type PriorityQueue
- func (queue *PriorityQueue[T]) Add(item T)
- func (queue *PriorityQueue[T]) Find(predicate func(item T) bool) (T, error)
- func (queue *PriorityQueue[T]) FindAll(predicate func(item T) bool) []T
- func (queue *PriorityQueue[T]) Items() []T
- func (queue *PriorityQueue[T]) Iterator() iter.Seq[T]
- func (queue *PriorityQueue[T]) Peek() (T, error)
- func (queue *PriorityQueue[T]) Remove() (T, error)
- func (queue *PriorityQueue[T]) Size() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Apply ¶ added in v1.1.0
func Apply[T any](queue *PriorityQueue[T], f func(item T))
Iterate over the queue and apply a function to each item.
Idiomatic Go should likely use Iterator() rather than functional methods.
BEWARE: Iteration order is not the same as priority order! To iterate in priority order, use Items() and sort by priority.
Since Apply does not update the queue items, this method does *not* call heapify (reorganize the queue).
Internally this method calls minbinaryheap.Apply, as the backing data structure is a heap.
It is expected that Apply does *not* update the queue items. To modify the queue items, use Map. To accumulate values over the queue, use Fold.
func Fold ¶ added in v1.1.0
func Fold[T any, G any](queue *PriorityQueue[T], initialAccumulator G, f func(item T, accumulator G) G) G
Iterate over the queue and apply the function f to it. The function f also takes the current value of the accumulator. The results of f become the new value of the accumulator at each step.
Idiomatic Go should likely use Iterator() rather than functional methods.
BEWARE: Iteration order is not the same as priority order! To iterate in priority order, use Items() and sort by priority.
This function returns the final accumulator.
Internally this method calls minbinaryheap.Fold, as the backing data structure is a heap.
This function is not a method on PriorityQueue to allow for generic accumulators.
func Map ¶ added in v1.1.0
func Map[T any](queue *PriorityQueue[T], f func(item T) T)
Iterate over the queue apply a function to each item.
Idiomatic Go should likely use Iterator() rather than functional methods.
BEWARE: Iteration order is not the same as priority order! To iterate in priority order, use Items() and sort by priority.
BEWARE: Since this method updates the queue data, this method calls heapify to restore queue order. However, since this method may update *all* queue items, this method calls heapify on *all* items. That is potentially very expensive!
Internally this method calls minbinaryheap.Map, as the backing data structure is a heap.
Map can update the node items by returning the update value. If you do not need to modify the queue items, use Apply. To accumulate values over the queue, use Fold.
Types ¶
type PriorityQueue ¶
type PriorityQueue[T any] struct { // contains filtered or unexported fields }
Implement a priority queue.
A priority queue will accept items and ensure those items are retrievable in priority order.
This implementation uses a min-heap (github.com/hmcalister/Go-DSA/heap/MinBinaryHeap) and hence lower priority values are put at the front of the queue. If you require the opposite behavior, simply flip the logic in the comparator passed to the constructor.
func New ¶
func New[T any](comparatorFunction comparator.ComparatorFunction[T]) *PriorityQueue[T]
Create a new priority queue.
The comparatorFunction allows for items in the queue to be compared based on priority. Remember that lower priority values are pushed to the front of the queue.
func (*PriorityQueue[T]) Add ¶
func (queue *PriorityQueue[T]) Add(item T)
Enqueue an item, adding it to the end of the queue.
This method automatically updates the priority queue to ensure the head item has the lowest priority value.
func (*PriorityQueue[T]) Find ¶
func (queue *PriorityQueue[T]) Find(predicate func(item T) bool) (T, error)
Find the first item in a queue matching a predicate. The queue is traversed from front to back.
Returns (item, nil) if the item is present, or (*new(T), dsa_error.ErrorItemNotFound) if the item is not present.
func (*PriorityQueue[T]) FindAll ¶
func (queue *PriorityQueue[T]) FindAll(predicate func(item T) bool) []T
Find all items in a queue matching a predicate. The queue is traversed from front to back.
Returns all items from the queue that match the predicate.
func (*PriorityQueue[T]) Items ¶ added in v1.1.0
func (queue *PriorityQueue[T]) Items() []T
Get all items from the queue. This method allocates an array of length equal to the number of items.
func (*PriorityQueue[T]) Iterator ¶ added in v1.2.0
func (queue *PriorityQueue[T]) Iterator() iter.Seq[T]
Iterate over the items of the queue.
BEWARE: Iteration order is not the same as priority order! To iterate in priority order, use Items() and sort by priority.
If you are updating items in the queue, please note this method does *not* reheapify.
This method is not concurrency safe. For concurrent applications, consider using a mutex, or pull the data out using Items().
func (*PriorityQueue[T]) Peek ¶
func (queue *PriorityQueue[T]) Peek() (T, error)
Peek at the front item in the queue.
Returns a dsa_error.ErrorDataStructureEmpty error if the queue is empty.
func (*PriorityQueue[T]) Remove ¶
func (queue *PriorityQueue[T]) Remove() (T, error)
Dequeue an item, removing from the front of the queue.
Returns a dsa_error.ErrorDataStructureEmpty if the queue is empty.
func (*PriorityQueue[T]) Size ¶
func (queue *PriorityQueue[T]) Size() int
Get the size of the queue, the number of items in the queue.
Source Files