Check-in [d5adabf68e]
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: d5adabf68e98857170abaad175c3d960cc2e3123
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
9
10
11
12
13
14
15
16
17
18
19

20
21
22
23
24
25
26
// Package bits provides a bit vector backed with uints
package bits

import (
	"strconv"
)

// The Vector interface defines methods on the bit vector
type Vector interface {
	// Retrieves the bit at the designated position
	Peek(uint) bool
	// Sets the bit at the designated position
	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]
}

|


















>







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
// Package bits provides a bit vector interface and several implementations
package bits

import (
	"strconv"
)

// The Vector interface defines methods on the bit vector
type Vector interface {
	// Retrieves the bit at the designated position
	Peek(uint) bool
	// Sets the bit at the designated position
	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]
}

34
35
36
37
38
39
40





41
42
43
44
45
46
47
	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







>
>
>
>
>







35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
	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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
}

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)
}







|











<
<
<
<
<
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93





}

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
41
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
98
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
51
52
53
54
55
56
57
58


59
60
61
62
63
64
65

	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.Print(" < ")
			}
			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







<
<
<
<



|
<
<
<
<
<















>
>







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

	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.Print(" < ")
			}
			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
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

// 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 {







>

<







>




>
>
>
>
>
>
>
>
>







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

// 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
}
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<