diff options
Diffstat (limited to 'src/pkg/container/vector')
| -rw-r--r-- | src/pkg/container/vector/intvector.go | 34 | ||||
| -rw-r--r-- | src/pkg/container/vector/stringvector.go | 32 | ||||
| -rw-r--r-- | src/pkg/container/vector/vector.go | 110 | ||||
| -rw-r--r-- | src/pkg/container/vector/vector_test.go | 170 |
4 files changed, 173 insertions, 173 deletions
diff --git a/src/pkg/container/vector/intvector.go b/src/pkg/container/vector/intvector.go index 43f8ff8081..1ec4b85a9b 100644 --- a/src/pkg/container/vector/intvector.go +++ b/src/pkg/container/vector/intvector.go @@ -7,7 +7,7 @@ package vector // IntVector is a specialization of Vector that hides the wrapping of Elements around ints. type IntVector struct { - Vector; + Vector } @@ -17,40 +17,40 @@ type IntVector struct { // Resize adds 0 elements. The capacity parameter is ignored unless the // new length or capacity is longer that the current capacity. func (p *IntVector) Resize(length, capacity int) *IntVector { - i := p.Len(); - p.Vector.Resize(length, capacity); + i := p.Len() + p.Vector.Resize(length, capacity) for a := p.a; i < len(a); i++ { a[i] = 0 } - return p; + return p } // At returns the i'th element of the vector. -func (p *IntVector) At(i int) int { return p.Vector.At(i).(int) } +func (p *IntVector) At(i int) int { return p.Vector.At(i).(int) } // Set sets the i'th element of the vector to value x. -func (p *IntVector) Set(i int, x int) { p.a[i] = x } +func (p *IntVector) Set(i int, x int) { p.a[i] = x } // Last returns the element in the vector of highest index. -func (p *IntVector) Last() int { return p.Vector.Last().(int) } +func (p *IntVector) Last() int { return p.Vector.Last().(int) } // Data returns all the elements as a slice. func (p *IntVector) Data() []int { - arr := make([]int, p.Len()); + arr := make([]int, p.Len()) for i, v := range p.a { arr[i] = v.(int) } - return arr; + return arr } // Insert inserts into the vector an element of value x before // the current element at index i. -func (p *IntVector) Insert(i int, x int) { p.Vector.Insert(i, x) } +func (p *IntVector) Insert(i int, x int) { p.Vector.Insert(i, x) } // InsertVector inserts into the vector the contents of the Vector @@ -68,11 +68,11 @@ func (p *IntVector) Slice(i, j int) *IntVector { // Push appends x to the end of the vector. -func (p *IntVector) Push(x int) { p.Vector.Push(x) } +func (p *IntVector) Push(x int) { p.Vector.Push(x) } // Pop deletes and returns the last element of the vector. -func (p *IntVector) Pop() int { return p.Vector.Pop().(int) } +func (p *IntVector) Pop() int { return p.Vector.Pop().(int) } // AppendVector appends the entire IntVector x to the end of this vector. @@ -83,7 +83,7 @@ func (p *IntVector) AppendVector(x *IntVector) { // sort.Interface support // Less returns a boolean denoting whether the i'th element is less than the j'th element. -func (p *IntVector) Less(i, j int) bool { return p.At(i) < p.At(j) } +func (p *IntVector) Less(i, j int) bool { return p.At(i) < p.At(j) } // Iterate over all elements; driver for range @@ -91,13 +91,13 @@ func (p *IntVector) iterate(c chan<- int) { for _, v := range p.a { c <- v.(int) } - close(c); + close(c) } // Channel iterator for range. func (p *IntVector) Iter() <-chan int { - c := make(chan int); - go p.iterate(c); - return c; + c := make(chan int) + go p.iterate(c) + return c } diff --git a/src/pkg/container/vector/stringvector.go b/src/pkg/container/vector/stringvector.go index 93a4197a58..821a7a101d 100644 --- a/src/pkg/container/vector/stringvector.go +++ b/src/pkg/container/vector/stringvector.go @@ -6,7 +6,7 @@ package vector // StringVector is a specialization of Vector that hides the wrapping of Elements around strings. type StringVector struct { - Vector; + Vector } @@ -16,34 +16,34 @@ type StringVector struct { // Resize adds "" elements. The capacity parameter is ignored unless the // new length or capacity is longer that the current capacity. func (p *StringVector) Resize(length, capacity int) *StringVector { - i := p.Len(); - p.Vector.Resize(length, capacity); + i := p.Len() + p.Vector.Resize(length, capacity) for a := p.a; i < len(a); i++ { a[i] = "" } - return p; + return p } // At returns the i'th element of the vector. -func (p *StringVector) At(i int) string { return p.Vector.At(i).(string) } +func (p *StringVector) At(i int) string { return p.Vector.At(i).(string) } // Set sets the i'th element of the vector to value x. -func (p *StringVector) Set(i int, x string) { p.a[i] = x } +func (p *StringVector) Set(i int, x string) { p.a[i] = x } // Last returns the element in the vector of highest index. -func (p *StringVector) Last() string { return p.Vector.Last().(string) } +func (p *StringVector) Last() string { return p.Vector.Last().(string) } // Data returns all the elements as a slice. func (p *StringVector) Data() []string { - arr := make([]string, p.Len()); + arr := make([]string, p.Len()) for i, v := range p.a { arr[i] = v.(string) } - return arr; + return arr } @@ -69,11 +69,11 @@ func (p *StringVector) Slice(i, j int) *StringVector { // Push appends x to the end of the vector. -func (p *StringVector) Push(x string) { p.Vector.Push(x) } +func (p *StringVector) Push(x string) { p.Vector.Push(x) } // Pop deletes and returns the last element of the vector. -func (p *StringVector) Pop() string { return p.Vector.Pop().(string) } +func (p *StringVector) Pop() string { return p.Vector.Pop().(string) } // AppendVector appends the entire StringVector x to the end of this vector. @@ -84,7 +84,7 @@ func (p *StringVector) AppendVector(x *StringVector) { // sort.Interface support // Less returns a boolean denoting whether the i'th element is less than the j'th element. -func (p *StringVector) Less(i, j int) bool { return p.At(i) < p.At(j) } +func (p *StringVector) Less(i, j int) bool { return p.At(i) < p.At(j) } // Iterate over all elements; driver for range @@ -92,13 +92,13 @@ func (p *StringVector) iterate(c chan<- string) { for _, v := range p.a { c <- v.(string) } - close(c); + close(c) } // Channel iterator for range. func (p *StringVector) Iter() <-chan string { - c := make(chan string); - go p.iterate(c); - return c; + c := make(chan string) + go p.iterate(c) + return c } diff --git a/src/pkg/container/vector/vector.go b/src/pkg/container/vector/vector.go index 0408490bea..ed1845b27c 100644 --- a/src/pkg/container/vector/vector.go +++ b/src/pkg/container/vector/vector.go @@ -9,8 +9,8 @@ package vector // Vector is the container itself. // The zero value for Vector is an empty vector ready to use. type Vector struct { - a []interface{}; - bootstrap [8]interface{}; + a []interface{} + bootstrap [8]interface{} } @@ -21,31 +21,31 @@ func (p *Vector) realloc(length, capacity int) (b []interface{}) { } else { b = make([]interface{}, length, capacity) } - copy(b, p.a); - p.a = b; - return; + copy(b, p.a) + p.a = b + return } // Insert n elements at position i. func (p *Vector) expand(i, n int) { - a := p.a; + a := p.a // make sure we have enough space - len0 := len(a); - len1 := len0 + n; + len0 := len(a) + len1 := len0 + n if len1 <= cap(a) { // enough space - just expand a = a[0:len1] } else { // not enough space - double capacity - capb := cap(a) * 2; + capb := cap(a) * 2 if capb < len1 { // still not enough - use required length capb = len1 } // capb >= len1 - a = p.realloc(len1, capb); + a = p.realloc(len1, capb) } // make a hole @@ -53,7 +53,7 @@ func (p *Vector) expand(i, n int) { a[j+n] = a[j] } - p.a = a; + p.a = a } @@ -64,7 +64,7 @@ func (p *Vector) expand(i, n int) { // new length or capacity is longer that the current capacity. The resized // vector's capacity may be larger than the requested capacity. func (p *Vector) Resize(length, capacity int) *Vector { - a := p.a; + a := p.a if length > cap(a) || capacity > cap(a) { // not enough space or larger capacity requested explicitly @@ -76,91 +76,91 @@ func (p *Vector) Resize(length, capacity int) *Vector { } } - p.a = a[0:length]; - return p; + p.a = a[0:length] + return p } // Len returns the number of elements in the vector. -func (p *Vector) Len() int { return len(p.a) } +func (p *Vector) Len() int { return len(p.a) } // Cap returns the capacity of the vector; that is, the // maximum length the vector can grow without resizing. -func (p *Vector) Cap() int { return cap(p.a) } +func (p *Vector) Cap() int { return cap(p.a) } // At returns the i'th element of the vector. -func (p *Vector) At(i int) interface{} { return p.a[i] } +func (p *Vector) At(i int) interface{} { return p.a[i] } // Set sets the i'th element of the vector to value x. -func (p *Vector) Set(i int, x interface{}) { p.a[i] = x } +func (p *Vector) Set(i int, x interface{}) { p.a[i] = x } // Last returns the element in the vector of highest index. -func (p *Vector) Last() interface{} { return p.a[len(p.a)-1] } +func (p *Vector) Last() interface{} { return p.a[len(p.a)-1] } // Data returns all the elements as a slice. func (p *Vector) Data() []interface{} { - arr := make([]interface{}, p.Len()); + arr := make([]interface{}, p.Len()) for i, v := range p.a { arr[i] = v } - return arr; + return arr } // Insert inserts into the vector an element of value x before // the current element at index i. func (p *Vector) Insert(i int, x interface{}) { - p.expand(i, 1); - p.a[i] = x; + p.expand(i, 1) + p.a[i] = x } // Delete deletes the i'th element of the vector. The gap is closed so the old // element at index i+1 has index i afterwards. func (p *Vector) Delete(i int) { - a := p.a; - n := len(a); + a := p.a + n := len(a) - copy(a[i:n-1], a[i+1:n]); - a[n-1] = nil; // support GC, nil out entry - p.a = a[0 : n-1]; + copy(a[i:n-1], a[i+1:n]) + a[n-1] = nil // support GC, nil out entry + p.a = a[0 : n-1] } // InsertVector inserts into the vector the contents of the Vector // x such that the 0th element of x appears at index i after insertion. func (p *Vector) InsertVector(i int, x *Vector) { - p.expand(i, len(x.a)); - copy(p.a[i:i+len(x.a)], x.a); + p.expand(i, len(x.a)) + copy(p.a[i:i+len(x.a)], x.a) } // Cut deletes elements i through j-1, inclusive. func (p *Vector) Cut(i, j int) { - a := p.a; - n := len(a); - m := n - (j - i); + a := p.a + n := len(a) + m := n - (j - i) - copy(a[i:m], a[j:n]); + copy(a[i:m], a[j:n]) for k := m; k < n; k++ { - a[k] = nil // support GC, nil out entries + a[k] = nil // support GC, nil out entries } - p.a = a[0:m]; + p.a = a[0:m] } // Slice returns a new Vector by slicing the old one to extract slice [i:j]. // The elements are copied. The original vector is unchanged. func (p *Vector) Slice(i, j int) *Vector { - s := new(Vector).Resize(j-i, 0); // will fail in Init() if j < i - copy(s.a, p.a[i:j]); - return s; + s := new(Vector).Resize(j-i, 0) // will fail in Init() if j < i + copy(s.a, p.a[i:j]) + return s } @@ -168,7 +168,7 @@ func (p *Vector) Slice(i, j int) *Vector { // The function should not change the indexing of the vector underfoot. func (p *Vector) Do(f func(elem interface{})) { for i := 0; i < len(p.a); i++ { - f(p.a[i]) // not too safe if f changes the Vector + f(p.a[i]) // not too safe if f changes the Vector } } @@ -176,39 +176,39 @@ func (p *Vector) Do(f func(elem interface{})) { // Convenience wrappers // Push appends x to the end of the vector. -func (p *Vector) Push(x interface{}) { p.Insert(len(p.a), x) } +func (p *Vector) Push(x interface{}) { p.Insert(len(p.a), x) } // Pop deletes the last element of the vector. func (p *Vector) Pop() interface{} { - i := len(p.a) - 1; - x := p.a[i]; - p.a[i] = nil; // support GC, nil out entry - p.a = p.a[0:i]; - return x; + i := len(p.a) - 1 + x := p.a[i] + p.a[i] = nil // support GC, nil out entry + p.a = p.a[0:i] + return x } // AppendVector appends the entire Vector x to the end of this vector. -func (p *Vector) AppendVector(x *Vector) { p.InsertVector(len(p.a), x) } +func (p *Vector) AppendVector(x *Vector) { p.InsertVector(len(p.a), x) } // Partial sort.Interface support // LessInterface provides partial support of the sort.Interface. type LessInterface interface { - Less(y interface{}) bool; + Less(y interface{}) bool } // Less returns a boolean denoting whether the i'th element is less than the j'th element. -func (p *Vector) Less(i, j int) bool { return p.a[i].(LessInterface).Less(p.a[j]) } +func (p *Vector) Less(i, j int) bool { return p.a[i].(LessInterface).Less(p.a[j]) } // Swap exchanges the elements at indexes i and j. func (p *Vector) Swap(i, j int) { - a := p.a; - a[i], a[j] = a[j], a[i]; + a := p.a + a[i], a[j] = a[j], a[i] } @@ -217,13 +217,13 @@ func (p *Vector) iterate(c chan<- interface{}) { for _, v := range p.a { c <- v } - close(c); + close(c) } // Channel iterator for range. func (p *Vector) Iter() <-chan interface{} { - c := make(chan interface{}); - go p.iterate(c); - return c; + c := make(chan interface{}) + go p.iterate(c) + return c } diff --git a/src/pkg/container/vector/vector_test.go b/src/pkg/container/vector/vector_test.go index f187f72188..755ba7cad0 100644 --- a/src/pkg/container/vector/vector_test.go +++ b/src/pkg/container/vector/vector_test.go @@ -10,7 +10,7 @@ import "fmt" func TestZeroLen(t *testing.T) { - a := new(Vector); + a := new(Vector) if a.Len() != 0 { t.Errorf("B) expected 0, got %d", a.Len()) } @@ -18,8 +18,8 @@ func TestZeroLen(t *testing.T) { type VectorInterface interface { - Len() int; - Cap() int; + Len() int + Cap() int } @@ -34,27 +34,27 @@ func checkSize(t *testing.T, v VectorInterface, len, cap int) { func TestResize(t *testing.T) { - var a Vector; - checkSize(t, &a, 0, 0); - checkSize(t, a.Resize(0, 5), 0, 5); - checkSize(t, a.Resize(1, 0), 1, 5); - checkSize(t, a.Resize(10, 0), 10, 10); - checkSize(t, a.Resize(5, 0), 5, 10); - checkSize(t, a.Resize(3, 8), 3, 10); - checkSize(t, a.Resize(0, 100), 0, 100); - checkSize(t, a.Resize(11, 100), 11, 100); + var a Vector + checkSize(t, &a, 0, 0) + checkSize(t, a.Resize(0, 5), 0, 5) + checkSize(t, a.Resize(1, 0), 1, 5) + checkSize(t, a.Resize(10, 0), 10, 10) + checkSize(t, a.Resize(5, 0), 5, 10) + checkSize(t, a.Resize(3, 8), 3, 10) + checkSize(t, a.Resize(0, 100), 0, 100) + checkSize(t, a.Resize(11, 100), 11, 100) } func TestIntResize(t *testing.T) { - var a IntVector; - checkSize(t, &a, 0, 0); - a.Push(1); - a.Push(2); - a.Push(3); - a.Push(4); - checkSize(t, &a, 4, 4); - checkSize(t, a.Resize(10, 0), 10, 10); + var a IntVector + checkSize(t, &a, 0, 0) + a.Push(1) + a.Push(2) + a.Push(3) + a.Push(4) + checkSize(t, &a, 4, 4) + checkSize(t, a.Resize(10, 0), 10, 10) for i := 4; i < a.Len(); i++ { if a.At(i) != 0 { t.Errorf("expected a.At(%d) == 0; found %d", i, a.At(i)) @@ -64,14 +64,14 @@ func TestIntResize(t *testing.T) { func TestStringResize(t *testing.T) { - var a StringVector; - checkSize(t, &a, 0, 0); - a.Push("1"); - a.Push("2"); - a.Push("3"); - a.Push("4"); - checkSize(t, &a, 4, 4); - checkSize(t, a.Resize(10, 0), 10, 10); + var a StringVector + checkSize(t, &a, 0, 0) + a.Push("1") + a.Push("2") + a.Push("3") + a.Push("4") + checkSize(t, &a, 4, 4) + checkSize(t, a.Resize(10, 0), 10, 10) for i := 4; i < a.Len(); i++ { if a.At(i) != "" { t.Errorf("expected a.At(%d) == "+"; found %s", i, a.At(i)) @@ -95,25 +95,25 @@ func checkNil(t *testing.T, a *Vector, i int) { func TestTrailingElements(t *testing.T) { - var a Vector; + var a Vector for i := 0; i < 10; i++ { a.Push(i) } - checkNil(t, &a, 10); - checkSize(t, &a, 10, 16); - checkSize(t, a.Resize(5, 0), 5, 16); - checkSize(t, a.Resize(10, 0), 10, 16); - checkNil(t, &a, 5); + checkNil(t, &a, 10) + checkSize(t, &a, 10, 16) + checkSize(t, a.Resize(5, 0), 5, 16) + checkSize(t, a.Resize(10, 0), 10, 16) + checkNil(t, &a, 5) } -func val(i int) int { return i*991 - 1234 } +func val(i int) int { return i*991 - 1234 } func TestAccess(t *testing.T) { - const n = 100; - var a Vector; - a.Resize(n, 0); + const n = 100 + var a Vector + a.Resize(n, 0) for i := 0; i < n; i++ { a.Set(i, val(i)) } @@ -126,14 +126,14 @@ func TestAccess(t *testing.T) { func TestInsertDeleteClear(t *testing.T) { - const n = 100; - var a Vector; + const n = 100 + var a Vector for i := 0; i < n; i++ { if a.Len() != i { t.Errorf("A) wrong len %d (expected %d)", a.Len(), i) } - a.Insert(0, val(i)); + a.Insert(0, val(i)) if a.Last().(int) != val(0) { t.Error("B") } @@ -145,7 +145,7 @@ func TestInsertDeleteClear(t *testing.T) { if a.At(0).(int) != val(i) { t.Error("D") } - a.Delete(0); + a.Delete(0) if a.Len() != i { t.Errorf("E) wrong len %d (expected %d)", a.Len(), i) } @@ -155,7 +155,7 @@ func TestInsertDeleteClear(t *testing.T) { t.Errorf("F) wrong len %d (expected 0)", a.Len()) } for i := 0; i < n; i++ { - a.Push(val(i)); + a.Push(val(i)) if a.Len() != i+1 { t.Errorf("G) wrong len %d (expected %d)", a.Len(), i+1) } @@ -163,17 +163,17 @@ func TestInsertDeleteClear(t *testing.T) { t.Error("H") } } - a.Resize(0, 0); + a.Resize(0, 0) if a.Len() != 0 { t.Errorf("I wrong len %d (expected 0)", a.Len()) } - const m = 5; + const m = 5 for j := 0; j < m; j++ { - a.Push(j); + a.Push(j) for i := 0; i < n; i++ { - x := val(i); - a.Push(x); + x := val(i) + a.Push(x) if a.Pop().(int) != x { t.Error("J") } @@ -195,7 +195,7 @@ func verify_slice(t *testing.T, x *Vector, elt, i, j int) { } } - s := x.Slice(i, j); + s := x.Slice(i, j) for k, n := 0, j-i; k < n; k++ { if s.At(k).(int) != elt { t.Errorf("N) wrong [%d] element %d (expected %d)", k, x.At(k).(int), elt) @@ -205,54 +205,54 @@ func verify_slice(t *testing.T, x *Vector, elt, i, j int) { func verify_pattern(t *testing.T, x *Vector, a, b, c int) { - n := a + b + c; + n := a + b + c if x.Len() != n { t.Errorf("O) wrong len %d (expected %d)", x.Len(), n) } - verify_slice(t, x, 0, 0, a); - verify_slice(t, x, 1, a, a+b); - verify_slice(t, x, 0, a+b, n); + verify_slice(t, x, 0, 0, a) + verify_slice(t, x, 1, a, a+b) + verify_slice(t, x, 0, a+b, n) } func make_vector(elt, len int) *Vector { - x := new(Vector).Resize(len, 0); + x := new(Vector).Resize(len, 0) for i := 0; i < len; i++ { x.Set(i, elt) } - return x; + return x } func TestInsertVector(t *testing.T) { // 1 - a := make_vector(0, 0); - b := make_vector(1, 10); - a.InsertVector(0, b); - verify_pattern(t, a, 0, 10, 0); + a := make_vector(0, 0) + b := make_vector(1, 10) + a.InsertVector(0, b) + verify_pattern(t, a, 0, 10, 0) // 2 - a = make_vector(0, 10); - b = make_vector(1, 0); - a.InsertVector(5, b); - verify_pattern(t, a, 5, 0, 5); + a = make_vector(0, 10) + b = make_vector(1, 0) + a.InsertVector(5, b) + verify_pattern(t, a, 5, 0, 5) // 3 - a = make_vector(0, 10); - b = make_vector(1, 3); - a.InsertVector(3, b); - verify_pattern(t, a, 3, 3, 7); + a = make_vector(0, 10) + b = make_vector(1, 3) + a.InsertVector(3, b) + verify_pattern(t, a, 3, 3, 7) // 4 - a = make_vector(0, 10); - b = make_vector(1, 1000); - a.InsertVector(8, b); - verify_pattern(t, a, 8, 1000, 2); + a = make_vector(0, 10) + b = make_vector(1, 1000) + a.InsertVector(8, b) + verify_pattern(t, a, 8, 1000, 2) } // This also tests IntVector and StringVector func TestSorting(t *testing.T) { - const n = 100; + const n = 100 - a := new(IntVector).Resize(n, 0); + a := new(IntVector).Resize(n, 0) for i := n - 1; i >= 0; i-- { a.Set(i, n-1-i) } @@ -260,7 +260,7 @@ func TestSorting(t *testing.T) { t.Error("int vector not sorted") } - b := new(StringVector).Resize(n, 0); + b := new(StringVector).Resize(n, 0) for i := n - 1; i >= 0; i-- { b.Set(i, fmt.Sprint(n-1-i)) } @@ -271,20 +271,20 @@ func TestSorting(t *testing.T) { func TestDo(t *testing.T) { - const n = 25; - const salt = 17; - a := new(IntVector).Resize(n, 0); + const n = 25 + const salt = 17 + a := new(IntVector).Resize(n, 0) for i := 0; i < n; i++ { a.Set(i, salt*i) } - count := 0; + count := 0 a.Do(func(e interface{}) { - i := e.(int); + i := e.(int) if i != count*salt { t.Error("value at", count, "should be", count*salt, "not", i) } - count++; - }); + count++ + }) if count != n { t.Error("should visit", n, "values; did visit", count) } @@ -292,17 +292,17 @@ func TestDo(t *testing.T) { func TestIter(t *testing.T) { - const Len = 100; - x := new(Vector).Resize(Len, 0); + const Len = 100 + x := new(Vector).Resize(Len, 0) for i := 0; i < Len; i++ { x.Set(i, i*i) } - i := 0; + i := 0 for v := range x.Iter() { if v.(int) != i*i { t.Error("Iter expected", i*i, "got", v.(int)) } - i++; + i++ } if i != Len { t.Error("Iter stopped at", i, "not", Len) |
