-
Notifications
You must be signed in to change notification settings - Fork 1
/
priority-queue.go
103 lines (89 loc) · 3.42 KB
/
priority-queue.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*
© 2022–present Harald Rudell <harald.rudell@gmail.com> (https://haraldrudell.github.io/haraldrudell/)
ISC License
*/
// Ranking is a pointer-identity-to-value map of updatable values traversable by rank.
// Ranking implements [parl.Ranking][V comparable, R constraints.Ordered].
package pqs
import (
"github.com/haraldrudell/parl"
"github.com/haraldrudell/parl/parli"
"github.com/haraldrudell/parl/perrors"
"github.com/haraldrudell/parl/pslices"
"golang.org/x/exp/constraints"
)
// PriorityQueue is a pointer-identity-to-value map of updatable values traversable by rank.
// PriorityQueue implements [parl.PriorityQueue][V comparable, R constraints.Ordered].
// - V is a value reference composite type that is comparable, ie. not slice map function.
// Preferrably, V is interface or pointer to struct type.
// - R is an ordered type such as int floating-point string, used to rank the V values
// - values are added or updated using AddOrUpdate method distinguished by
// (computer science) identity
// - if the same comparable value V is added again, that value is re-ranked
// - rank R is computed from a value V using the ranker function.
// The ranker function may be examining field values of a struct
// - values can have the same rank. If they do, equal rank is provided in insertion order
type PriorityQueue[V any, P constraints.Ordered] struct {
// priorityFunc is the function computing priority for a value-pointer
priorityFunc func(value *V) (priority P)
// queue is a list of queue nodes ordered by descending priority
queue parli.Ordered[*AssignedPriority[V, P]]
// m is a map providing O(1) access to ranking nodes by value-pointer
m map[*V]*AssignedPriority[V, P]
}
// NewPriorityQueue returns a map of updatable values traversable by rank
func NewPriorityQueue[V any, P constraints.Ordered](
priorityFunc func(value *V) (priority P),
) (priorityQueue parl.PriorityQueue[V, P]) {
if priorityFunc == nil {
perrors.NewPF("ranker cannot be nil")
}
r := PriorityQueue[V, P]{
priorityFunc: priorityFunc,
m: map[*V]*AssignedPriority[V, P]{},
}
r.queue = pslices.NewOrderedAny(r.comparatorFunc)
return &r
}
// AddOrUpdate adds a new value to the ranking or updates the ranking of a value
// that has changed.
func (pq *PriorityQueue[V, P]) AddOrUpdate(valuep *V) {
// obtain updated priority
priority := pq.priorityFunc(valuep)
var assignedPriority *AssignedPriority[V, P]
var ok bool
if assignedPriority, ok = pq.m[valuep]; !ok {
// new value case
assignedPriority = NewAssignedPriority(priority, pq.queue.Length(), valuep)
pq.m[valuep] = assignedPriority
} else {
// node update case
pq.queue.Delete(assignedPriority)
assignedPriority.SetPriority(priority)
}
// update order: that’s what we do here. We keep order
pq.queue.Insert(assignedPriority)
}
// List returns the first n or default all values by rank
func (pq *PriorityQueue[V, P]) List(n ...int) (valueQueue []*V) {
// get number of items n0
var n0 int
length := pq.queue.Length()
if len(n) > 0 {
n0 = n[0]
}
if n0 < 1 || n0 > length {
n0 = length
}
// build list
valueQueue = make([]*V, n0)
assignedPriorityQueue := pq.queue.List()
for i := 0; i < n0; i++ {
valueQueue[i] = assignedPriorityQueue[i].Value
}
return
}
// comparatorFunc is provided to pslices.NewOrderedAny based on AssignedPriority.Cmp
func (pq *PriorityQueue[V, P]) comparatorFunc(a, b *AssignedPriority[V, P]) (result int) {
return a.Cmp(b)
}