Overview
Comment: | [bits] fixed package documentation [bits] added tests for the bool-backed vector [diff] added a real test, commented out the visual debug aids [plaindiff] added comments, removed commented code, added a helper []line getter [math] removed math package as it is currently unused |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
d5adabf68e98857170abaad175c3d960 |
User & Date: | spaskalev on 2014-12-14 01:03:44 |
Other Links: | manifest | tags |
Context
2014-12-14
| ||
12:11 | Skip diagonals shorter than the current match check-in: e01b36769d user: spaskalev tags: trunk | |
01:03 | [bits] fixed package documentation [bits] added tests for the bool-backed vector [diff] added a real test, commented out the visual debug aids [plaindiff] added comments, removed commented code, added a helper []line getter [math] removed math package as it is currently unused check-in: d5adabf68e user: spaskalev tags: trunk | |
00:16 | Initial implementation of a diff program and required libraries check-in: be5950faa4 user: spaskalev tags: trunk | |
Changes
Modified src/0dev.org/bits/bits.go from [6b768844ff] to [415ad79153].
1 2 3 4 5 6 7 8 .. 13 14 15 16 17 18 19 20 21 22 23 24 25 26 .. 34 35 36 37 38 39 40 41 42 43 44 45 46 47 .. 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 bits provides a bit vector backed with uints package bits import ( "strconv" ) // The Vector interface defines methods on the bit vector ................................................................................ Poke(uint, bool) // Flips the bit at the designated position Flip(uint) // Returns the total number of elements supported by the vector Len() uint } type boolvector []bool // Retrieves the bit at the designated position func (v boolvector) Peek(pos uint) bool { return v[pos] } ................................................................................ v[pos] = !v[pos] } // Returns the total number of elements supported by the vector func (v boolvector) Len() uint { return uint(len(v)) } type vector []uint // Retrieves the bit at the designated position func (v vector) Peek(pos uint) bool { var slot, offset uint = at(pos) return (v[slot] & (1 << offset)) > 0 ................................................................................ } func at(pos uint) (uint, uint) { return pos / strconv.IntSize, pos % strconv.IntSize } // Create a new bit vector sized up to the desired number of elements func New(size uint) Vector { var length uint = size / strconv.IntSize if size%strconv.IntSize > 0 { // Allocate one additional slot if the desired // size is does not divide by 32/64 length++ } var slice []uint = make([]uint, length) return vector(slice) } func NewBool(size uint) Vector { var slice []bool = make([]bool, size) return boolvector(slice) } |
| > > > > > > | < < < < < |
1 2 3 4 5 6 7 8 .. 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 .. 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 .. 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
// Package bits provides a bit vector interface and several implementations package bits import ( "strconv" ) // The Vector interface defines methods on the bit vector ................................................................................ Poke(uint, bool) // Flips the bit at the designated position Flip(uint) // Returns the total number of elements supported by the vector Len() uint } // A Vector type that simply stores booleans in a slice type boolvector []bool // Retrieves the bit at the designated position func (v boolvector) Peek(pos uint) bool { return v[pos] } ................................................................................ v[pos] = !v[pos] } // Returns the total number of elements supported by the vector func (v boolvector) Len() uint { return uint(len(v)) } func NewBool(size uint) Vector { var slice []bool = make([]bool, size) return boolvector(slice) } type vector []uint // Retrieves the bit at the designated position func (v vector) Peek(pos uint) bool { var slot, offset uint = at(pos) return (v[slot] & (1 << offset)) > 0 ................................................................................ } func at(pos uint) (uint, uint) { return pos / strconv.IntSize, pos % strconv.IntSize } // Create a new bit vector sized up to the desired number of elements func NewBit(size uint) Vector { var length uint = size / strconv.IntSize if size%strconv.IntSize > 0 { // Allocate one additional slot if the desired // size is does not divide by 32/64 length++ } var slice []uint = make([]uint, length) return vector(slice) } |
Modified src/0dev.org/bits/bits_test.go from [c68b8d450a] to [3c67937d6c].
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
..
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
package bits import ( "strconv" "testing" ) func TestSize(t *testing.T) { sizes := []uint{0, 31, 32, 33, 61, 63, 64, 127, 128, 129} for _, size := range sizes { v := New(size) if v.Len() < size || v.Len() > size+strconv.IntSize { t.Error("Invalid length", v.Len(), "expected", size) } } } func TestEmpty(t *testing.T) { var size uint = 128 v := New(size) // Check if it is empty by default for i := uint(0); i < size; i++ { if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBasic(t *testing.T) { var size uint = 128 v := New(size) // Raise and lower each position explicitly for i := uint(0); i < size; i++ { v.Poke(i, true) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } ................................................................................ v.Poke(i, false) if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestFlip(t *testing.T) { var size uint = 128 v := New(size) // Raise and lower each position by flipping for i := uint(0); i < size; i++ { v.Flip(i) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } |
<
|
>
|
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
|
|
|
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
..
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
package bits import ( "strconv" "testing" ) var sizes []uint = []uint{0, 31, 32, 33, 61, 63, 64, 127, 128, 129} func TestBitSize(t *testing.T) { for _, size := range sizes { v := NewBit(size) if v.Len() < size || v.Len() > size+strconv.IntSize { t.Error("Invalid length", v.Len(), "expected", size) } } } func TestBitEmpty(t *testing.T) { var size uint = 128 v := NewBit(size) // Check if it is empty by default for i := uint(0); i < size; i++ { if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBitBasic(t *testing.T) { var size uint = 128 v := NewBit(size) // Raise and lower each position explicitly for i := uint(0); i < size; i++ { v.Poke(i, true) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } v.Poke(i, false) if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBitFlip(t *testing.T) { var size uint = 128 v := NewBit(size) // Raise and lower each position by flipping for i := uint(0); i < size; i++ { v.Flip(i) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } v.Flip(i) if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBoolSize(t *testing.T) { for _, size := range sizes { v := NewBool(size) if v.Len() != size { t.Error("Invalid length", v.Len(), "expected", size) } } } func TestBoolEmpty(t *testing.T) { var size uint = 128 v := NewBool(size) // Check if it is empty by default for i := uint(0); i < size; i++ { if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBoolBasic(t *testing.T) { var size uint = 128 v := NewBool(size) // Raise and lower each position explicitly for i := uint(0); i < size; i++ { v.Poke(i, true) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } ................................................................................ v.Poke(i, false) if v.Peek(i) { t.Error("Invalid raised bit at", i) } } } func TestBoolFlip(t *testing.T) { var size uint = 128 v := NewBool(size) // Raise and lower each position by flipping for i := uint(0); i < size; i++ { v.Flip(i) if !v.Peek(i) { t.Error("Invalid lowered bit at", i) } |
Modified src/0dev.org/commands/plaindiff/main.go from [d48eb80ca4] to [f32b00c34a].
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 .. 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ... 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 |
var hd hashDiff hd.hash = fnv.New64a() hd.first = read(args[0], hd.hash) hd.second = read(args[1], hd.hash) var result diff.Delta = diff.Diff(&hd) //var marks []diff.Mark = make([]diff.Mark, len(result.Added)+len(result.Removed)) //var added, removed []diff.Mark = result.Added, result.Removed fmt.Println(result) gen := source(result) for have, added, mark := gen(); have; have, added, mark = gen() { var from []line if added { from = hd.second } else { from = hd.first } fmt.Println() for i := mark.From; i < mark.Length; i++ { fmt.Print(i) if added { fmt.Print(" > ") } else { ................................................................................ } fmt.Println(from[i].text) } } } func source(d diff.Delta) func() (bool, bool, diff.Mark) { var addedAt, removedAt int = 0, 0 return func() (bool, bool, diff.Mark) { var addsOver bool = addedAt == len(d.Added) var removesOver bool = removedAt == len(d.Removed) var add, remove diff.Mark ................................................................................ // A line-based diff.Interface implementation type hashDiff struct { first, second []line hash hash.Hash64 } func (h *hashDiff) Equal(i, j int) bool { // return h.first[i].text == h.second[j].text if h.first[i].hash != h.second[j].hash { return false } else { return h.first[i].text == h.second[j].text } } func (h *hashDiff) Len() (int, int) { return len(h.first), len(h.second) } type line struct { hash uint64 text string } // Reads all lines in a file and returns a line entry for each func read(name string, h hash.Hash64) []line { |
< < < < | < < < < < > > > < > > > > > > > > > > |
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 .. 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 .. 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 |
var hd hashDiff hd.hash = fnv.New64a() hd.first = read(args[0], hd.hash) hd.second = read(args[1], hd.hash) var result diff.Delta = diff.Diff(&hd) gen := source(result) for have, added, mark := gen(); have; have, added, mark = gen() { var from []line = hd.line(!added) fmt.Println() for i := mark.From; i < mark.Length; i++ { fmt.Print(i) if added { fmt.Print(" > ") } else { ................................................................................ } fmt.Println(from[i].text) } } } // Returns a closure over the provided diff.Delta // that returns diff.Mark entries while prioritizing removals when possible func source(d diff.Delta) func() (bool, bool, diff.Mark) { var addedAt, removedAt int = 0, 0 return func() (bool, bool, diff.Mark) { var addsOver bool = addedAt == len(d.Added) var removesOver bool = removedAt == len(d.Removed) var add, remove diff.Mark ................................................................................ // A line-based diff.Interface implementation type hashDiff struct { first, second []line hash hash.Hash64 } // Required per diff.Interface func (h *hashDiff) Equal(i, j int) bool { if h.first[i].hash != h.second[j].hash { return false } else { return h.first[i].text == h.second[j].text } } // Required per diff.Interface func (h *hashDiff) Len() (int, int) { return len(h.first), len(h.second) } // A helper method for getting a line slice func (h *hashDiff) line(first bool) []line { if first { return h.first } return h.second } // Holds a text line and its hash type line struct { hash uint64 text string } // Reads all lines in a file and returns a line entry for each func read(name string, h hash.Hash64) []line { |
Modified src/0dev.org/diff/diff.go from [f9b64d21c6] to [bb37f97581].
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
Removed []Mark } // Diffs the provided data and returns e Delta struct // with added entries' indices in the second sequence and removed from the first func Diff(data Interface) Delta { var len1, len2 = data.Len() var mat matrix = matrix{v: bits.New(uint(len1 * len2)), lenX: len1, lenY: len2} for i := 0; i < len1; i++ { for j := 0; j < len2; j++ { mat.v.Poke(mat.at(i, j), data.Equal(i, j)) } } |
| |
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
Removed []Mark
}
// Diffs the provided data and returns e Delta struct
// with added entries' indices in the second sequence and removed from the first
func Diff(data Interface) Delta {
var len1, len2 = data.Len()
var mat matrix = matrix{v: bits.NewBit(uint(len1 * len2)), lenX: len1, lenY: len2}
for i := 0; i < len1; i++ {
for j := 0; j < len2; j++ {
mat.v.Poke(mat.at(i, j), data.Equal(i, j))
}
}
|
Modified src/0dev.org/diff/diff_test.go from [6f1c8e9901] to [210041c492].
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 |
package diff import ( bits "0dev.org/bits" "fmt" "testing" ) type diffSlice struct { first []rune second []rune } func (d diffSlice) Len() (int, int) { return len(d.first), len(d.second) } func (d diffSlice) Equal(i, j int) bool { return d.first[i] == d.second[j] } func TestLCS(t *testing.T) { fmt.Println("") data := diffSlice{ []rune("abcdefgh"), []rune("abbcedfh"), } fmt.Println(Diff(data)) // first, second, total := LCS(data) // fmt.Println(first, second, total) } func TestWTF(t *testing.T) { data := diffSlice{ []rune("abcdefgh"), []rune("abbcedfh"), } var len1, len2 int = data.Len() var mat matrix = matrix{v: bits.NewBool(uint(len1 * len2)), lenX: len1, lenY: len2} for i := 0; i < len1; i++ { for j := 0; j < len2; j++ { mat.v.Poke(mat.at(i, j), data.Equal(i, j)) } } debugPrint(box{5, 5, 6, 6}, mat) debugPrint(box{5, 5, 7, 7}, mat) debugPrint(box{5, 5, 8, 8}, mat) } func debugPrint(bounds box, mat matrix) { // Debug print fmt.Printf("-%d-%d--%d-%d--\n", bounds.x, bounds.y, bounds.lenX, bounds.lenY) for i := bounds.x; i < bounds.lenX; i++ { fmt.Print("| ") for j := bounds.y; j < bounds.lenY; j++ { //if vector.Peek(uint(j + (i * bounds.lenY))) { if mat.v.Peek(mat.at(i, j)) { fmt.Print("\\") } else { fmt.Print(".") } } fmt.Println(" |") } fmt.Println("------------") } |
| | > > > | < < | > > > > > > | < < | | | | > | < | | | | | > > | < < | | | > | < | | | | | | | | | | | < < > > | < > | < > |
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 |
package diff import ( _ "0dev.org/bits" _ "fmt" "testing" ) // A diff.Interface implementation for testing purposes type diffSlice struct { first []rune second []rune } // Required per diff.Interface func (d diffSlice) Len() (int, int) { return len(d.first), len(d.second) } // Required per diff.Interface func (d diffSlice) Equal(i, j int) bool { return d.first[i] == d.second[j] } func TestDiff(t *testing.T) { data := diffSlice{ []rune("abcdefgh"), []rune("abbcedfh"), } result := Diff(data) if len(result.Added) != 2 || result.Added[0].From != 2 || result.Added[0].Length != 3 || result.Added[1].From != 5 || result.Added[1].Length != 6 || result.Removed[0].From != 3 || result.Removed[0].Length != 4 || result.Removed[1].From != 6 || result.Removed[1].Length != 7 { t.Error("Unexpected diff results", result) } } // func TestWTF(t *testing.T) { // data := diffSlice{ // []rune("abcdefgh"), // []rune("abbcedfh"), // } // var len1, len2 int = data.Len() // var mat matrix = matrix{v: bits.NewBool(uint(len1 * len2)), lenX: len1, lenY: len2} // for i := 0; i < len1; i++ { // for j := 0; j < len2; j++ { // mat.v.Poke(mat.at(i, j), data.Equal(i, j)) // } // } // debugPrint(box{5, 5, 6, 6}, mat) // visual debugging as its finest // debugPrint(box{5, 5, 7, 7}, mat) // debugPrint(box{5, 5, 8, 8}, mat) // ZO RELAXEN UND WATSCHEN DER BLINKENLICHTEN. // } // func debugPrint(bounds box, mat matrix) { // // Debug print // fmt.Printf("-%d-%d--%d-%d--\n", bounds.x, bounds.y, bounds.lenX, bounds.lenY) // for i := bounds.x; i < bounds.lenX; i++ { // fmt.Print("| ") // for j := bounds.y; j < bounds.lenY; j++ { // //if vector.Peek(uint(j + (i * bounds.lenY))) { // if mat.v.Peek(mat.at(i, j)) { // fmt.Print("\\") // } else { // fmt.Print(".") // } // } // fmt.Println(" |") // } // fmt.Println("------------") // } |
Deleted src/0dev.org/math/math.go version [1a240e5264].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Helper functions that really belong in the SDK or in a generic library... package math func MinInt(i1, i2 int) int { if i1 <= i2 { return i1 } return i2 } func MaxInt(i1, i2 int) int { if i1 >= i2 { return i1 } return i2 } |
< < < < < < < < < < < < < < < < |