The Shed
Check-in [d5adabf68e]
Login
HomeTimelineFilesBranchesTagsTicketsWiki
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
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

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


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 backed with uints
// 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

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

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 New(size uint) Vector {
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)
}

func NewBool(size uint) Vector {
	var slice []bool = make([]bool, size)
	return boolvector(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

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

func TestSize(t *testing.T) {
	sizes := []uint{0, 31, 32, 33, 61, 63, 64, 127, 128, 129}
var sizes []uint = []uint{0, 31, 32, 33, 61, 63, 64, 127, 128, 129}

func TestBitSize(t *testing.T) {
	for _, size := range sizes {
		v := New(size)
		v := NewBit(size)
		if v.Len() < size || v.Len() > size+strconv.IntSize {
			t.Error("Invalid length", v.Len(), "expected", size)
		}
	}
}

func TestEmpty(t *testing.T) {
func TestBitEmpty(t *testing.T) {
	var size uint = 128
	v := New(size)
	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 TestBasic(t *testing.T) {
func TestBoolBasic(t *testing.T) {
	var size uint = 128
	v := New(size)
	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 TestFlip(t *testing.T) {
func TestBoolFlip(t *testing.T) {
	var size uint = 128
	v := New(size)
	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

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)
	//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
		var from []line = hd.line(!added)
		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)
		}
	}

}

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

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

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

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


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 (
	bits "0dev.org/bits"
	"fmt"
	_ "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 TestLCS(t *testing.T) {
func TestDiff(t *testing.T) {
	fmt.Println("")

	data := diffSlice{
		[]rune("abcdefgh"),
		[]rune("abbcedfh"),
	}

	fmt.Println(Diff(data))

	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)
	}
	// first, second, total := LCS(data)
	// fmt.Println(first, second, total)
}

func TestWTF(t *testing.T) {
	data := diffSlice{
		[]rune("abcdefgh"),
		[]rune("abbcedfh"),
	}
// 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}
// 	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))
// 	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)
}
// 	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(".")
// 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(" |")
	}
	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
}

Powered by Fossil · RSS