/
ints.go
79 lines (66 loc) · 1.68 KB
/
ints.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
package heap
import (
"sort"
)
// A heap for ints. The pointer to the zero value of Ints is a heap with default less
// func which compares int values on the natual order.
// Use NewInts to customize less func and initial capacity.
type Ints struct {
// Less func given indexes of i, j in the list slice.
less func(i, j int) bool
list sort.IntSlice
}
// Len returns the number of elements in the current heap.
func (h *Ints) Len() int {
return len(h.list)
}
// Push inserts an element to the heap.
func (h *Ints) Push(x int) {
h.list = append(h.list, x)
if h.less == nil {
PushLastF(len(h.list), h.list.Less, h.list.Swap)
} else {
PushLastF(len(h.list), h.less, h.list.Swap)
}
}
// Peek returns the top most element. It panics if the heap is empty.
func (h *Ints) Peek() int {
return h.list[0]
}
// Pop removes the top element from the heap and returns it.
func (h *Ints) Pop() int {
if h.less == nil {
PopToLastF(len(h.list), h.list.Less, h.list.Swap)
} else {
PopToLastF(len(h.list), h.less, h.list.Swap)
}
res := h.list[len(h.list)-1]
h.list = h.list[:len(h.list)-1]
return res
}
// PopAll pops and returns all elements of the heap in reverse order.
func (h *Ints) PopAll() []int {
for n := h.Len(); n > 1; n-- {
if h.less == nil {
PopToLastF(n, h.list.Less, h.list.Swap)
} else {
PopToLastF(n, h.less, h.list.Swap)
}
}
res := h.list
h.list = nil
return res
}
// NewInts returns a *Ints with customized less func and initial capacity.
func NewInts(less func(x, y int) bool, cap int) *Ints {
h := &Ints{}
if less != nil {
h.less = func(i, j int) bool {
return less(h.list[i], h.list[j])
}
}
if cap > 0 {
h.list = make(sort.IntSlice, 0, cap)
}
return h
}