Index: src/0dev.org/bits/bits.go ================================================================== --- src/0dev.org/bits/bits.go +++ src/0dev.org/bits/bits.go @@ -1,6 +1,6 @@ -// Package bits provides a bit vector backed with uints +// Package bits provides a bit vector interface and several implementations package bits import ( "strconv" ) @@ -15,10 +15,11 @@ 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] @@ -36,10 +37,15 @@ // 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 { @@ -71,11 +77,11 @@ 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 @@ -83,10 +89,5 @@ } var slice []uint = make([]uint, length) return vector(slice) } - -func NewBool(size uint) Vector { - var slice []bool = make([]bool, size) - return boolvector(slice) -} Index: src/0dev.org/bits/bits_test.go ================================================================== --- src/0dev.org/bits/bits_test.go +++ src/0dev.org/bits/bits_test.go @@ -3,36 +3,93 @@ 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 := 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 := New(size) + 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) { @@ -44,13 +101,13 @@ 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) { Index: src/0dev.org/commands/plaindiff/main.go ================================================================== --- src/0dev.org/commands/plaindiff/main.go +++ src/0dev.org/commands/plaindiff/main.go @@ -26,23 +26,14 @@ 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 - } + var from []line = hd.line(!added) fmt.Println() for i := mark.From; i < mark.Length; i++ { fmt.Print(i) if added { @@ -54,10 +45,12 @@ } } } +// 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) @@ -103,23 +96,33 @@ 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 } Index: src/0dev.org/diff/diff.go ================================================================== --- src/0dev.org/diff/diff.go +++ src/0dev.org/diff/diff.go @@ -29,11 +29,11 @@ // 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)) } Index: src/0dev.org/diff/diff_test.go ================================================================== --- src/0dev.org/diff/diff_test.go +++ src/0dev.org/diff/diff_test.go @@ -1,72 +1,77 @@ 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("------------") -} + _ "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 Index: src/0dev.org/math/math.go ================================================================== --- src/0dev.org/math/math.go +++ /dev/null @@ -1,16 +0,0 @@ -// 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 -}