/
xheap.go
68 lines (55 loc) · 1.12 KB
/
xheap.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
package xheap
import (
"container/heap"
"sort"
)
type pushPopper interface {
Push(interface{})
Pop() interface{}
}
func Flipped(h heap.Interface) heap.Interface {
return struct {
sort.Interface
pushPopper
}{
sort.Reverse(h),
h,
}
}
// type top struct {
// k int
// heap.Interface
// }
// func (me top) Push(x interface{}) {
// heap.Push(me.Interface, x)
// if me.Len() > me.k {
// heap.Pop(me)
// }
// }
// func Bounded(k int, h heap.Interface) heap.Interface {
// return top{k, Flipped(h)}
// }
type slice struct {
Slice *[]interface{}
Lesser func(l, r interface{}) bool
}
func (me slice) Len() int { return len(*me.Slice) }
func (me slice) Less(i, j int) bool {
return me.Lesser((*me.Slice)[i], (*me.Slice)[j])
}
func (me slice) Pop() (ret interface{}) {
i := me.Len() - 1
ret = (*me.Slice)[i]
*me.Slice = (*me.Slice)[:i]
return
}
func (me slice) Push(x interface{}) {
*me.Slice = append(*me.Slice, x)
}
func (me slice) Swap(i, j int) {
sl := *me.Slice
sl[i], sl[j] = sl[j], sl[i]
}
func Slice(sl *[]interface{}, lesser func(l, r interface{}) bool) heap.Interface {
return slice{sl, lesser}
}