forked from ardanlabs/gotraining
-
Notifications
You must be signed in to change notification settings - Fork 1
/
example4.go
161 lines (127 loc) · 4.13 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
// 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 (
"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 {
output.Reset()
algorithmOne(d.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 {
output.Reset()
algorithmTwo(d.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())
}
}
// algorithmOne is one way to solve the problem.
func algorithmOne(data []byte, output *bytes.Buffer) {
// Use a bytes Reader to provide a stream to process.
input := bytes.NewReader(data)
// Declare the buffer we need to process the stream.
buf := make([]byte, size)
end := size - 1
// Read in an initial number of bytes we need to get started.
if n, err := io.ReadFull(input, buf[:end]); err != nil {
output.Write(buf[:n])
return
}
for {
// Read in one byte from the input stream.
b, err := input.ReadByte()
if err != nil {
// Flush the reset of the bytes we have.
output.Write(buf[:end])
break
}
// Add this byte to the end of the buffer.
buf[end] = b
// 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.
output.WriteByte(buf[0])
// Slice that front byte out.
copy(buf, buf[1:])
}
}
// algorithmTwo is a second way to solve the problem.
// Provided by Tyler Bunnell https://twitter.com/TylerJBunnell
func algorithmTwo(data []byte, output *bytes.Buffer) {
// Use the bytes Reader to provide a stream to process.
input := bytes.NewReader(data)
// Create an index variable to match bytes.
idx := 0
for {
// Read a single byte from our input.
b, err := input.ReadByte()
if err != nil {
break
}
// Does this byte match the byte at this offset?
if b == find[idx] {
// It matches so increment the index position.
idx++
// If every byte has been matched, write
// out the replacement.
if idx == size {
output.Write(repl)
idx = 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.
output.Write(find[:idx])
// Unread the unmatched byte so it can be processed again.
input.UnreadByte()
// Reset the offset to start matching from the beginning.
idx = 0
continue
}
// There was no previous match. Write byte and reset.
output.WriteByte(b)
idx = 0
}
}