forked from ardanlabs/gotraining
-
Notifications
You must be signed in to change notification settings - Fork 0
/
example4.go
328 lines (263 loc) · 8.17 KB
/
example4.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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
// All material is licensed under the Apache License Version 2.0, January 2004
// http://www.apache.org/licenses/LICENSE-2.0
// Sample program that takes a stream of bytes and looks for the bytes
// “elvis” and when they are found, replace them with “Elvis”. The code
// cannot assume that there are any line feeds or other delimiters in the
// stream and the code must assume that the stream is of any arbitrary length.
// The solution cannot meaningfully buffer to the end of the stream and
// then process the replacement.
package main
import (
"bufio"
"bytes"
"fmt"
"io"
)
// data represents a table of input and expected output.
var data = []struct {
input []byte
output []byte
}{
{[]byte("abc"), []byte("abc")},
{[]byte("elvis"), []byte("Elvis")},
{[]byte("aElvis"), []byte("aElvis")},
{[]byte("abcelvis"), []byte("abcElvis")},
{[]byte("eelvis"), []byte("eElvis")},
{[]byte("aelvis"), []byte("aElvis")},
{[]byte("aabeeeelvis"), []byte("aabeeeElvis")},
{[]byte("e l v i s"), []byte("e l v i s")},
{[]byte("aa bb e l v i saa"), []byte("aa bb e l v i saa")},
{[]byte(" elvi s"), []byte(" elvi s")},
{[]byte("elvielvis"), []byte("elviElvis")},
{[]byte("elvielvielviselvi1"), []byte("elvielviElviselvi1")},
{[]byte("elvielviselvis"), []byte("elviElvisElvis")},
}
// Declare what needs to be found and its replacement.
var find = []byte("elvis")
var repl = []byte("Elvis")
// Calculate the number of bytes we need to locate.
var size = len(find)
func main() {
var output bytes.Buffer
fmt.Println("=======================================\nRunning Algorithm One")
for _, d := range data {
input := bytes.NewReader(d.input)
output.Reset()
algOne(input, &output)
matched := bytes.Compare(d.output, output.Bytes())
fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
}
fmt.Println("=======================================\nRunning Algorithm Two")
for _, d := range data {
input := bytes.NewReader(d.input)
output.Reset()
algTwo(input, &output)
matched := bytes.Compare(d.output, output.Bytes())
fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
}
fmt.Println("=======================================\nRunning Algorithm Three")
for _, d := range data {
input := bytes.NewReader(d.input)
output.Reset()
algThree(input, &output)
matched := bytes.Compare(d.output, output.Bytes())
fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
}
fmt.Println("=======================================\nRunning Algorithm Four")
for _, d := range data {
output.Reset()
output.ReadFrom(NewReplaceReader(bytes.NewReader(d.input), find, repl))
matched := bytes.Compare(d.output, output.Bytes())
fmt.Printf("Matched: %v Inp: [%s] Exp: [%s] Got: [%s]\n", matched == 0, d.input, d.output, output.Bytes())
}
}
// algOne is one way to solve the problem. This approach first
// reads a minimum number of bytes required and then starts processing
// new bytes as they are provided in the stream.
func algOne(r io.Reader, w *bytes.Buffer) {
// Declare the buffers we need to process the stream.
buf := make([]byte, size)
tmp := make([]byte, 1)
end := size - 1
// Read in an initial number of bytes we need to get started.
if n, err := io.ReadFull(r, buf[:end]); err != nil {
w.Write(buf[:n])
return
}
for {
// Read in one byte from the input stream.
n, err := io.ReadFull(r, tmp)
// If we have a byte then process it.
if n == 1 {
// Add this byte to the end of the buffer.
buf[end] = tmp[0]
// If we have a match, replace the bytes.
if bytes.Compare(buf, find) == 0 {
copy(buf, repl)
}
// Write the front byte since it has been compared.
w.WriteByte(buf[0])
// Slice that front byte out.
copy(buf, buf[1:])
}
// Did we hit the end of the stream, then we are done.
if err != nil {
// Flush the reset of the bytes we have.
w.Write(buf[:end])
break
}
}
}
// algTwo is a second way to solve the problem. This approach takes an
// io.Reader to represent an infinite stream. This allows for the algorithm to
// accept input from just about anywhere, thanks to the beauty of Go
// interfaces.
// Provided by Tyler Bunnell https://twitter.com/TylerJBunnell
func algTwo(r io.Reader, w *bytes.Buffer) {
// Create a byte slice of length 1 into which our byte will be read.
b := make([]byte, 1)
// Create an index variable to match bytes.
idx := 0
for {
// Are we re-using the byte from a previous call?
if b[0] == 0 {
// Read a single byte from our input.
n, err := r.Read(b)
if n == 0 || err != nil {
break
}
}
// Does this byte match the byte at this offset?
if b[0] == find[idx] {
// It matches so increment the index position.
idx++
// If every byte has been matched, write
// out the replacement.
if idx == size {
w.Write(repl)
idx = 0
}
// Reset the reader byte to 0 so another byte will be read.
b[0] = 0
continue
}
// Did we have any sort of match on any given byte?
if idx != 0 {
// Write what we've matched up to this point.
w.Write(find[:idx])
// NOTE: we are NOT resetting the reader byte to 0 here because we need
// to re-use it on the next call. This is equivalent to the UnreadByte()
// call in the other functions.
// Reset the offset to start matching from the beginning.
idx = 0
continue
}
// There was no previous match. Write byte and reset.
w.WriteByte(b[0])
// Reset the reader byte to 0 so another byte will be read.
b[0] = 0
}
}
// algThree is a third way to solve the problem.
// Provided by Bill Hathaway https://twitter.com/billhathaway
func algThree(r io.Reader, w *bytes.Buffer) {
// This identifies where we are in the match.
var idx int
var buf = make([]byte, 1)
for {
n, err := r.Read(buf)
if err != nil || n == 0 {
break
}
// Does newest byte match next byte of find pattern?
if buf[0] == find[idx] {
idx++
// If a full match, write out the replacement pattern.
if idx == len(find) {
w.Write(repl)
idx = 0
}
continue
}
// If we have matched anything earlier, write it.
if idx > 0 {
w.Write(find[:idx])
idx = 0
}
// Match start of pattern?
if buf[0] == find[0] {
idx = 1
continue
}
// Write out what we read since no match.
w.Write(buf)
}
// Write out any partial match before returning.
if idx > 0 {
w.Write(find[:idx])
}
}
// algFour is a forth way to solve the problem. This takes a Functional approach.
// Provided by Adam Williams https://twitter.com/acw5
func algFour(r io.Reader, w *bytes.Buffer) {
buf := bufio.NewReaderSize(r, len(find))
for {
peek, err := buf.Peek(len(find))
if err == nil && bytes.Equal(find, peek) {
// A match was found. Advance the bufio reader past the match.
if _, err := buf.Discard(len(find)); err != nil {
return
}
w.Write(repl)
continue
}
// Ignore any peek errors because we may not be able to peek
// but still be able to read a byte.
c, err := buf.ReadByte()
if err != nil {
return
}
w.WriteByte(c)
}
}
// NewReplaceReader returns an io.Reader that reads from r, replacing
// any occurrence of old with new. Used by algFour.
func NewReplaceReader(r io.Reader, old, new []byte) io.Reader {
return &replaceReader{
br: bufio.NewReaderSize(r, len(old)),
old: old,
new: new,
}
}
type replaceReader struct {
br *bufio.Reader
old, new []byte
}
// Read reads into p the translated bytes.
func (r *replaceReader) Read(p []byte) (int, error) {
var n int
for {
peek, err := r.br.Peek(len(r.old))
if err == nil && bytes.Equal(r.old, peek) {
// A match was found. Advance the bufio reader past the match.
if _, err := r.br.Discard(len(r.old)); err != nil {
return n, err
}
copy(p[n:], r.new)
n += len(r.new)
continue
}
// Ignore any peek errors because we may not be able to peek
// but still be able to read a byte.
p[n], err = r.br.ReadByte()
if err != nil {
return n, err
}
n++
// Read reads up to len(p) bytes into p. Since we could potentially add
// len(r.new) new bytes, we check here that p still has capacity.
if n+len(r.new) >= len(p) {
return n, nil
}
}
}