-
Notifications
You must be signed in to change notification settings - Fork 10
/
ring.go
113 lines (91 loc) · 1.71 KB
/
ring.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
104
105
106
107
108
109
110
111
112
113
package containerx
type Ring[T any] struct {
size int
elems []T
head, tail, count int
}
func NewRing[T any](size int) *Ring[T] {
if size <= 0 {
panic("invaild ring size")
}
return &Ring[T]{
elems: make([]T, size),
size: size,
}
}
func (r *Ring[T]) Len() int {
return r.count
}
func (r *Ring[T]) PushFront(elems ...T) {
for i := range elems {
if r.count == 0 {
r.elems[r.head] = elems[i]
r.head = r.prevHead()
} else {
r.head = r.prevHead()
r.elems[r.head] = elems[i]
}
if r.count == r.size {
r.tail = r.prevHead()
} else {
r.count++
}
}
}
func (r *Ring[T]) PushBack(elems ...T) {
for i := range elems {
r.elems[r.tail] = elems[i]
r.tail = r.nextTail()
if r.count == r.size {
r.head = r.nextHead()
} else {
r.count++
}
}
}
func (r *Ring[T]) Front() T {
return r.elems[r.head]
}
func (r *Ring[T]) Back() T {
return r.elems[r.prevTail()]
}
func (r *Ring[T]) PopFront() (T, bool) {
var t T
if r.count <= 0 {
return t, false
}
ret := r.elems[r.head]
r.elems[r.head] = t
r.head = r.nextHead()
r.count--
return ret, true
}
func (r *Ring[T]) PopBack() (T, bool) {
var t T
if r.count <= 0 {
return t, false
}
back := r.prevTail()
ret := r.elems[back]
r.elems[back] = t
r.tail = back
r.count--
return ret, true
}
func (r *Ring[T]) Range(f func(T)) {
for count := 0; count < r.count; count++ {
f(r.elems[(r.head+count)%(r.size-1)])
}
}
func (r *Ring[T]) nextTail() int {
return (r.tail + 1) % r.size
}
func (r *Ring[T]) prevTail() int {
return (r.tail - 1 + r.size) % r.size
}
func (r *Ring[T]) nextHead() int {
return (r.head + 1) % r.size
}
func (r *Ring[T]) prevHead() int {
return (r.head - 1 + r.size) % r.size
}