async/priorityqueue.go at main · b97tsk/async · GitHub

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
package async

import "sort"

type lesser[E any] interface {
	less(v E) bool
}

type priorityqueue[E lesser[E]] struct {
	head, tail []E
}

func (q *priorityqueue[E]) Empty() bool {
	return len(q.head) == 0
}

func (q *priorityqueue[E]) Push(v E) {
	headsize, tailsize := len(q.head), len(q.tail)

	n := headsize + tailsize

	i := sort.Search(n, func(i int) bool {
		if i < headsize {
			return v.less(q.head[i])
		}

		i -= headsize

		return v.less(q.tail[i])
	})

	if n == cap(q.tail) {
		var zero E

		s := append(q.tail[:n], zero)[:0]

		if i < headsize {
			s = append(s, q.head[:i]...)
			s = append(s, v)
			s = append(s, q.head[i:]...)
			s = append(s, q.tail...)
		} else {
			i -= headsize
			s = append(s, q.head...)
			s = append(s, q.tail[:i]...)
			s = append(s, v)
			s = append(s, q.tail[i:]...)
		}

		q.head, q.tail = s, s[:0]

		return
	}

	if headsize < cap(q.head) {
		s := q.head
		s = s[:headsize+1]
		copy(s[i+1:], s[i:])
		s[i] = v
		q.head = s
		return
	}

	if i < headsize {
		s := q.head
		u := s[headsize-1]
		copy(s[i+1:], s[i:])
		s[i] = v
		v = u
		i = headsize
	}

	i -= headsize

	s := q.tail
	s = s[:tailsize+1]
	copy(s[i+1:], s[i:])
	s[i] = v
	q.tail = s
}

func (q *priorityqueue[E]) Pop() (v E) {
	q.head[0], v = v, q.head[0]

	if len(q.head) > 1 {
		q.head = q.head[1:]
	} else {
		q.head, q.tail = q.tail, q.tail[:0]
	}

	return v
}