forked from timtadh/data-structures
/
unique.go
54 lines (46 loc) · 1.34 KB
/
unique.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
package heap
import (
"github.com/timtadh/data-structures/hashtable"
"github.com/timtadh/data-structures/set"
"github.com/timtadh/data-structures/types"
)
// This priority queue only allows unique entries. Internally this is
// implemented using a Hash set. All items added must be types.Hashable
type UniquePQ struct {
pq PriorityQueue
set *set.SetMap
}
// Construct a new unique priority queue using the provided priority queue.
func NewUnique(pq PriorityQueue) *UniquePQ {
return &UniquePQ{
pq: pq,
set: set.NewSetMap(hashtable.NewLinearHash()),
}
}
// How many items in the queue?
func (u *UniquePQ) Size() int {
return u.pq.Size()
}
// Add an item to the priority queue. It must be hashable.
func (u *UniquePQ) Add(priority int, item types.Hashable) {
if !u.set.Has(item) {
u.set.Add(item)
u.pq.Push(priority, item)
}
}
// This method is provided so it implements the PriorityQueue interface. In
// reality item must be types.Hashable. The implementation simply does a type
// assertion on item and calls Add.
func (u *UniquePQ) Push(priority int, item interface{}) {
u.Add(priority, item.(types.Hashable))
}
// Get the top element
func (u *UniquePQ) Peek() interface{} {
return u.pq.Peek()
}
// Get and remove the top element
func (u *UniquePQ) Pop() interface{} {
item := u.pq.Pop().(types.Hashable)
u.set.Delete(item)
return item
}