containers/priorityqueue.go

package containers

import "sync"

type element[T any] struct {
	priority int
	value    T
}

type PriorityQueue[T any] struct {
	lock  sync.RWMutex
	items []*element[T]
}

func (q *PriorityQueue[T]) Add(priority int, value T) {
	q.lock.Lock()
	defer q.lock.Unlock()

	item := &element[T]{
		priority: priority,
		value:    value,
	}

	inserted := false
	for k, v := range q.items {
		if item.priority > v.priority {
			q.items = append(q.items[:k], append([]*element[T]{item}, q.items[k+1:]...)...)
			inserted = true
			break
		}
	}

	if !inserted {
		q.items = append(q.items, item)
	}

}

func (q *PriorityQueue[T]) Pop() (T, bool) {
	q.lock.Lock()
	defer q.lock.Unlock()

	if len(q.items) == 0 {
		var res T
		return res, false
	}

	item := q.items[0]
	q.items = q.items[1:]

	return item.value, true
}

func (q *PriorityQueue[T]) Len() int {
	q.lock.RLock()
	defer q.lock.RUnlock()

	return len(q.items)
}

// offset should be between 0 and Len() - 1
func (q *PriorityQueue[T]) Peek(offset int) (T, bool) {
	q.lock.RLock()
	defer q.lock.RUnlock()

	if offset < 0 || offset >= len(q.items) {
		var t T
		return t, false
	}

	return q.items[offset].value, true
}

func (q *PriorityQueue[T]) Clear() {
	q.lock.Lock()
	defer q.lock.Unlock()

	q.items = []*element[T]{}
}

func (q *PriorityQueue[T]) ForEach(fn func(*T)) {
	q.lock.RLock()
	defer q.lock.RUnlock()

	for _, v := range q.items {
		fn(&v.value)
	}
}