89 lines
1.4 KiB
Go
89 lines
1.4 KiB
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)
|
|
}
|
|
}
|