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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
// Tideland Go Library - Collections - Ring Buffer
//
// Copyright (C) 2015 Frank Mueller / Tideland / Oldenburg / Germany
//
// All rights reserved. Use of this source code is governed
// by the new BSD license.
package collections
//--------------------
// IMPORTS
//--------------------
import (
"fmt"
"strings"
)
//--------------------
// RING BUFFER
//--------------------
// valueLink is one ring buffer element containing one
// value and linking to the next element.
type valueLink struct {
used bool
value interface{}
next *valueLink
}
// ringBuffer implements the RingBuffer interface.
type ringBuffer struct {
start *valueLink
end *valueLink
current *valueLink
}
// NewRingBuffer creates a new ring buffer.
func NewRingBuffer(size int) RingBuffer {
rb := &ringBuffer{}
rb.start = &valueLink{}
rb.end = rb.start
if size < 2 {
size = 2
}
for i := 0; i < size-1; i++ {
link := &valueLink{}
rb.end.next = link
rb.end = link
}
rb.end.next = rb.start
return rb
}
// Push implements the RingBuffer interface.
func (rb *ringBuffer) Push(values ...interface{}) {
for _, value := range values {
if rb.end.next.used == false {
rb.end.next.used = true
rb.end.next.value = value
rb.end = rb.end.next
continue
}
link := &valueLink{
used: true,
value: value,
next: rb.start,
}
rb.end.next = link
rb.end = rb.end.next
}
}
// Peek implements the RingBuffer interface.
func (rb *ringBuffer) Peek() (interface{}, bool) {
if rb.start.used == false {
return nil, false
}
return rb.start.value, true
}
// Pop implements the RingBuffer interface.
func (rb *ringBuffer) Pop() (interface{}, bool) {
if rb.start.used == false {
return nil, false
}
value := rb.start.value
rb.start.used = false
rb.start.value = nil
rb.start = rb.start.next
return value, true
}
// Len implements the RingBuffer interface.
func (rb *ringBuffer) Len() int {
l := 0
current := rb.start
for current.used {
l++
current = current.next
if current == rb.start {
break
}
}
return l
}
// Cap implements the RingBuffer interface.
func (rb *ringBuffer) Cap() int {
c := 1
current := rb.start
for current.next != rb.start {
c++
current = current.next
}
return c
}
// String implements the Stringer interface.
func (rb *ringBuffer) String() string {
vs := []string{}
current := rb.start
for current.used {
vs = append(vs, fmt.Sprintf("[%v]", current.value))
current = current.next
if current == rb.start {
break
}
}
return strings.Join(vs, "->")
}
// EOF
|
