diff options
author | ian <ian@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-10-26 23:57:58 +0000 |
---|---|---|
committer | ian <ian@138bc75d-0d04-0410-961f-82ee72b054a4> | 2011-10-26 23:57:58 +0000 |
commit | fa5d125b5cfa5c935e46d27a2cbcd71ae37687ac (patch) | |
tree | 19d182df05ead7ff8ba7ee00a7d57555e1383fdf /libgo/go/container | |
parent | e3d46e67996cf20ca3a75fccbb5a0007bfa3f992 (diff) | |
download | gcc-fa5d125b5cfa5c935e46d27a2cbcd71ae37687ac.tar.gz |
Update Go library to last weekly.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@180552 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libgo/go/container')
-rw-r--r-- | libgo/go/container/heap/heap_test.go | 32 | ||||
-rw-r--r-- | libgo/go/container/vector/defs.go | 43 | ||||
-rw-r--r-- | libgo/go/container/vector/intvector.go | 188 | ||||
-rw-r--r-- | libgo/go/container/vector/intvector_test.go | 331 | ||||
-rw-r--r-- | libgo/go/container/vector/nogen_test.go | 67 | ||||
-rw-r--r-- | libgo/go/container/vector/numbers_test.go | 123 | ||||
-rw-r--r-- | libgo/go/container/vector/stringvector.go | 188 | ||||
-rw-r--r-- | libgo/go/container/vector/stringvector_test.go | 331 | ||||
-rw-r--r-- | libgo/go/container/vector/vector.go | 188 | ||||
-rw-r--r-- | libgo/go/container/vector/vector_test.go | 331 |
10 files changed, 23 insertions, 1799 deletions
diff --git a/libgo/go/container/heap/heap_test.go b/libgo/go/container/heap/heap_test.go index c5c1f76e1e1..6625e3a2b0f 100644 --- a/libgo/go/container/heap/heap_test.go +++ b/libgo/go/container/heap/heap_test.go @@ -6,32 +6,46 @@ package heap_test import ( "testing" - "container/vector" . "container/heap" ) -type myHeap struct { - // A vector.Vector implements sort.Interface except for Less, - // and it implements Push and Pop as required for heap.Interface. - vector.Vector +type myHeap []int + +func (h *myHeap) Less(i, j int) bool { + return (*h)[i] < (*h)[j] +} + +func (h *myHeap) Swap(i, j int) { + (*h)[i], (*h)[j] = (*h)[j], (*h)[i] +} + +func (h *myHeap) Len() int { + return len(*h) +} + +func (h *myHeap) Pop() (v interface{}) { + *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1] + return } -func (h *myHeap) Less(i, j int) bool { return h.At(i).(int) < h.At(j).(int) } +func (h *myHeap) Push(v interface{}) { + *h = append(*h, v.(int)) +} -func (h *myHeap) verify(t *testing.T, i int) { +func (h myHeap) verify(t *testing.T, i int) { n := h.Len() j1 := 2*i + 1 j2 := 2*i + 2 if j1 < n { if h.Less(j1, i) { - t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1)) + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h[i], j1, h[j1]) return } h.verify(t, j1) } if j2 < n { if h.Less(j2, i) { - t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2)) + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h[i], j1, h[j2]) return } h.verify(t, j2) diff --git a/libgo/go/container/vector/defs.go b/libgo/go/container/vector/defs.go deleted file mode 100644 index 6d6b2ac81a3..00000000000 --- a/libgo/go/container/vector/defs.go +++ /dev/null @@ -1,43 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Package vector implements containers for managing sequences of elements. -// Vectors grow and shrink dynamically as necessary. -package vector - -// Vector is a container for numbered sequences of elements of type interface{}. -// A vector's length and capacity adjusts automatically as necessary. -// The zero value for Vector is an empty vector ready to use. -type Vector []interface{} - -// IntVector is a container for numbered sequences of elements of type int. -// A vector's length and capacity adjusts automatically as necessary. -// The zero value for IntVector is an empty vector ready to use. -type IntVector []int - -// StringVector is a container for numbered sequences of elements of type string. -// A vector's length and capacity adjusts automatically as necessary. -// The zero value for StringVector is an empty vector ready to use. -type StringVector []string - -// Initial underlying array size -const initialSize = 8 - -// Partial sort.Interface support - -// LessInterface provides partial support of the sort.Interface. -type LessInterface interface { - 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)[i].(LessInterface).Less((*p)[j]) } - -// 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)[i] < (*p)[j] } - -// 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)[i] < (*p)[j] } diff --git a/libgo/go/container/vector/intvector.go b/libgo/go/container/vector/intvector.go deleted file mode 100644 index aa88cfeb367..00000000000 --- a/libgo/go/container/vector/intvector.go +++ /dev/null @@ -1,188 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector.go, it was generated -// automatically from vector.go - DO NOT EDIT in that case! - -package vector - -func (p *IntVector) realloc(length, capacity int) (b []int) { - if capacity < initialSize { - capacity = initialSize - } - if capacity < length { - capacity = length - } - b = make(IntVector, length, capacity) - copy(b, *p) - *p = b - return -} - -// Insert n elements at position i. -func (p *IntVector) Expand(i, n int) { - a := *p - - // make sure we have enough space - 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 - if capb < len1 { - // still not enough - use required length - capb = len1 - } - // capb >= len1 - a = p.realloc(len1, capb) - } - - // make a hole - for j := len0 - 1; j >= i; j-- { - a[j+n] = a[j] - } - - *p = a -} - -// Insert n elements at the end of a vector. -func (p *IntVector) Extend(n int) { p.Expand(len(*p), n) } - -// Resize changes the length and capacity of a vector. -// If the new length is shorter than the current length, Resize discards -// trailing elements. If the new length is longer than the current length, -// Resize adds the respective zero values for the additional elements. The capacity -// parameter is ignored unless the new length or capacity is longer than the current -// capacity. The resized vector's capacity may be larger than the requested capacity. -func (p *IntVector) Resize(length, capacity int) *IntVector { - a := *p - - if length > cap(a) || capacity > cap(a) { - // not enough space or larger capacity requested explicitly - a = p.realloc(length, capacity) - } else if length < len(a) { - // clear trailing elements - for i := range a[length:] { - var zero int - a[length+i] = zero - } - } - - *p = a[0:length] - return p -} - -// Len returns the number of elements in the vector. -// Same as len(*p). -func (p *IntVector) Len() int { return len(*p) } - -// Cap returns the capacity of the vector; that is, the -// maximum length the vector can grow without resizing. -// Same as cap(*p). -func (p *IntVector) Cap() int { return cap(*p) } - -// At returns the i'th element of the vector. -func (p *IntVector) At(i int) int { return (*p)[i] } - -// Set sets the i'th element of the vector to value x. -func (p *IntVector) Set(i int, x int) { (*p)[i] = x } - -// Last returns the element in the vector of highest index. -func (p *IntVector) Last() int { return (*p)[len(*p)-1] } - -// Copy makes a copy of the vector and returns it. -func (p *IntVector) Copy() IntVector { - arr := make(IntVector, len(*p)) - copy(arr, *p) - 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.Expand(i, 1) - (*p)[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 *IntVector) Delete(i int) { - a := *p - n := len(a) - - copy(a[i:n-1], a[i+1:n]) - var zero int - a[n-1] = zero // support GC, zero out entry - *p = 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 *IntVector) InsertVector(i int, x *IntVector) { - b := *x - - p.Expand(i, len(b)) - copy((*p)[i:i+len(b)], b) -} - -// Cut deletes elements i through j-1, inclusive. -func (p *IntVector) Cut(i, j int) { - a := *p - n := len(a) - m := n - (j - i) - - copy(a[i:m], a[j:n]) - for k := m; k < n; k++ { //TODO(bflm) don't zero out the elements unless it's a Vector. - var zero int - a[k] = zero // support GC, zero out entries - } - - *p = a[0:m] -} - -// Slice returns a new sub-vector by slicing the old one to extract slice [i:j]. -// The elements are copied. The original vector is unchanged. -func (p *IntVector) Slice(i, j int) *IntVector { - var s IntVector - s.realloc(j-i, 0) // will fail in Init() if j < i - copy(s, (*p)[i:j]) - return &s -} - -// Convenience wrappers - -// Push appends x to the end of the vector. -func (p *IntVector) Push(x int) { p.Insert(len(*p), x) } - -// Pop deletes the last element of the vector. -func (p *IntVector) Pop() int { - a := *p - - i := len(a) - 1 - x := a[i] - var zero int - a[i] = zero // support GC, zero out entry - *p = a[0:i] - return x -} - -// AppendVector appends the entire vector x to the end of this vector. -func (p *IntVector) AppendVector(x *IntVector) { p.InsertVector(len(*p), x) } - -// Swap exchanges the elements at indexes i and j. -func (p *IntVector) Swap(i, j int) { - a := *p - a[i], a[j] = a[j], a[i] -} - -// Do calls function f for each element of the vector, in order. -// The behavior of Do is undefined if f changes *p. -func (p *IntVector) Do(f func(elem int)) { - for _, e := range *p { - f(e) - } -} diff --git a/libgo/go/container/vector/intvector_test.go b/libgo/go/container/vector/intvector_test.go deleted file mode 100644 index b825af91221..00000000000 --- a/libgo/go/container/vector/intvector_test.go +++ /dev/null @@ -1,331 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector_test.go, it was generated -// automatically from vector_test.go - DO NOT EDIT in that case! - -package vector - -import "testing" - -func TestIntZeroLen(t *testing.T) { - a := new(IntVector) - if a.Len() != 0 { - t.Errorf("%T: B1) expected 0, got %d", a, a.Len()) - } - if len(*a) != 0 { - t.Errorf("%T: B2) expected 0, got %d", a, len(*a)) - } - var b IntVector - if b.Len() != 0 { - t.Errorf("%T: B3) expected 0, got %d", b, b.Len()) - } - if len(b) != 0 { - t.Errorf("%T: B4) expected 0, got %d", b, len(b)) - } -} - -func TestIntResize(t *testing.T) { - var a IntVector - 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 TestIntResize2(t *testing.T) { - var a IntVector - checkSize(t, &a, 0, 0) - a.Push(int2IntValue(1)) - a.Push(int2IntValue(2)) - a.Push(int2IntValue(3)) - a.Push(int2IntValue(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) != intzero { - t.Errorf("%T: expected a.At(%d) == %v; found %v!", a, i, intzero, a.At(i)) - } - } - for i := 4; i < len(a); i++ { - if a[i] != intzero { - t.Errorf("%T: expected a[%d] == %v; found %v", a, i, intzero, a[i]) - } - } -} - -func checkIntZero(t *testing.T, a *IntVector, i int) { - for j := 0; j < i; j++ { - if a.At(j) == intzero { - t.Errorf("%T: 1 expected a.At(%d) == %d; found %v", a, j, j, a.At(j)) - } - if (*a)[j] == intzero { - t.Errorf("%T: 2 expected (*a)[%d] == %d; found %v", a, j, j, (*a)[j]) - } - } - for ; i < a.Len(); i++ { - if a.At(i) != intzero { - t.Errorf("%T: 3 expected a.At(%d) == %v; found %v", a, i, intzero, a.At(i)) - } - if (*a)[i] != intzero { - t.Errorf("%T: 4 expected (*a)[%d] == %v; found %v", a, i, intzero, (*a)[i]) - } - } -} - -func TestIntTrailingElements(t *testing.T) { - var a IntVector - for i := 0; i < 10; i++ { - a.Push(int2IntValue(i + 1)) - } - checkIntZero(t, &a, 10) - checkSize(t, &a, 10, 16) - checkSize(t, a.Resize(5, 0), 5, 16) - checkSize(t, a.Resize(10, 0), 10, 16) - checkIntZero(t, &a, 5) -} - -func TestIntAccess(t *testing.T) { - const n = 100 - var a IntVector - a.Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2IntValue(val(i))) - } - for i := 0; i < n; i++ { - if elem2IntValue(a.At(i)) != int2IntValue(val(i)) { - t.Error(i) - } - } - var b IntVector - b.Resize(n, 0) - for i := 0; i < n; i++ { - b[i] = int2IntValue(val(i)) - } - for i := 0; i < n; i++ { - if elem2IntValue(b[i]) != int2IntValue(val(i)) { - t.Error(i) - } - } -} - -func TestIntInsertDeleteClear(t *testing.T) { - const n = 100 - var a IntVector - - for i := 0; i < n; i++ { - if a.Len() != i { - t.Errorf("%T: A) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: A) wrong len() %d (expected %d)", a, len(a), i) - } - a.Insert(0, int2IntValue(val(i))) - if elem2IntValue(a.Last()) != int2IntValue(val(0)) { - t.Errorf("%T: B", a) - } - } - for i := n - 1; i >= 0; i-- { - if elem2IntValue(a.Last()) != int2IntValue(val(0)) { - t.Errorf("%T: C", a) - } - if elem2IntValue(a.At(0)) != int2IntValue(val(i)) { - t.Errorf("%T: D", a) - } - if elem2IntValue(a[0]) != int2IntValue(val(i)) { - t.Errorf("%T: D2", a) - } - a.Delete(0) - if a.Len() != i { - t.Errorf("%T: E) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: E) wrong len() %d (expected %d)", a, len(a), i) - } - } - - if a.Len() != 0 { - t.Errorf("%T: F) wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: F) wrong len() %d (expected 0)", a, len(a)) - } - for i := 0; i < n; i++ { - a.Push(int2IntValue(val(i))) - if a.Len() != i+1 { - t.Errorf("%T: G) wrong Len() %d (expected %d)", a, a.Len(), i+1) - } - if len(a) != i+1 { - t.Errorf("%T: G) wrong len() %d (expected %d)", a, len(a), i+1) - } - if elem2IntValue(a.Last()) != int2IntValue(val(i)) { - t.Errorf("%T: H", a) - } - } - a.Resize(0, 0) - if a.Len() != 0 { - t.Errorf("%T: I wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: I wrong len() %d (expected 0)", a, len(a)) - } - - const m = 5 - for j := 0; j < m; j++ { - a.Push(int2IntValue(j)) - for i := 0; i < n; i++ { - x := val(i) - a.Push(int2IntValue(x)) - if elem2IntValue(a.Pop()) != int2IntValue(x) { - t.Errorf("%T: J", a) - } - if a.Len() != j+1 { - t.Errorf("%T: K) wrong Len() %d (expected %d)", a, a.Len(), j+1) - } - if len(a) != j+1 { - t.Errorf("%T: K) wrong len() %d (expected %d)", a, len(a), j+1) - } - } - } - if a.Len() != m { - t.Errorf("%T: L) wrong Len() %d (expected %d)", a, a.Len(), m) - } - if len(a) != m { - t.Errorf("%T: L) wrong len() %d (expected %d)", a, len(a), m) - } -} - -func verify_sliceInt(t *testing.T, x *IntVector, elt, i, j int) { - for k := i; k < j; k++ { - if elem2IntValue(x.At(k)) != int2IntValue(elt) { - t.Errorf("%T: M) wrong [%d] element %v (expected %v)", x, k, elem2IntValue(x.At(k)), int2IntValue(elt)) - } - } - - s := x.Slice(i, j) - for k, n := 0, j-i; k < n; k++ { - if elem2IntValue(s.At(k)) != int2IntValue(elt) { - t.Errorf("%T: N) wrong [%d] element %v (expected %v)", x, k, elem2IntValue(x.At(k)), int2IntValue(elt)) - } - } -} - -func verify_patternInt(t *testing.T, x *IntVector, a, b, c int) { - n := a + b + c - if x.Len() != n { - t.Errorf("%T: O) wrong Len() %d (expected %d)", x, x.Len(), n) - } - if len(*x) != n { - t.Errorf("%T: O) wrong len() %d (expected %d)", x, len(*x), n) - } - verify_sliceInt(t, x, 0, 0, a) - verify_sliceInt(t, x, 1, a, a+b) - verify_sliceInt(t, x, 0, a+b, n) -} - -func make_vectorInt(elt, len int) *IntVector { - x := new(IntVector).Resize(len, 0) - for i := 0; i < len; i++ { - x.Set(i, int2IntValue(elt)) - } - return x -} - -func TestIntInsertVector(t *testing.T) { - // 1 - a := make_vectorInt(0, 0) - b := make_vectorInt(1, 10) - a.InsertVector(0, b) - verify_patternInt(t, a, 0, 10, 0) - // 2 - a = make_vectorInt(0, 10) - b = make_vectorInt(1, 0) - a.InsertVector(5, b) - verify_patternInt(t, a, 5, 0, 5) - // 3 - a = make_vectorInt(0, 10) - b = make_vectorInt(1, 3) - a.InsertVector(3, b) - verify_patternInt(t, a, 3, 3, 7) - // 4 - a = make_vectorInt(0, 10) - b = make_vectorInt(1, 1000) - a.InsertVector(8, b) - verify_patternInt(t, a, 8, 1000, 2) -} - -func TestIntDo(t *testing.T) { - const n = 25 - const salt = 17 - a := new(IntVector).Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2IntValue(salt*i)) - } - count := 0 - a.Do(func(e int) { - i := intf2IntValue(e) - if i != int2IntValue(count*salt) { - t.Error(tname(a), "value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(a), "should visit", n, "values; did visit", count) - } - - b := new(IntVector).Resize(n, 0) - for i := 0; i < n; i++ { - (*b)[i] = int2IntValue(salt * i) - } - count = 0 - b.Do(func(e int) { - i := intf2IntValue(e) - if i != int2IntValue(count*salt) { - t.Error(tname(b), "b) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(b), "b) should visit", n, "values; did visit", count) - } - - var c IntVector - c.Resize(n, 0) - for i := 0; i < n; i++ { - c[i] = int2IntValue(salt * i) - } - count = 0 - c.Do(func(e int) { - i := intf2IntValue(e) - if i != int2IntValue(count*salt) { - t.Error(tname(c), "c) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(c), "c) should visit", n, "values; did visit", count) - } - -} - -func TestIntVectorCopy(t *testing.T) { - // verify Copy() returns a copy, not simply a slice of the original vector - const Len = 10 - var src IntVector - for i := 0; i < Len; i++ { - src.Push(int2IntValue(i * i)) - } - dest := src.Copy() - for i := 0; i < Len; i++ { - src[i] = int2IntValue(-1) - v := elem2IntValue(dest[i]) - if v != int2IntValue(i*i) { - t.Error(tname(src), "expected", i*i, "got", v) - } - } -} diff --git a/libgo/go/container/vector/nogen_test.go b/libgo/go/container/vector/nogen_test.go deleted file mode 100644 index 7b6a25952b1..00000000000 --- a/libgo/go/container/vector/nogen_test.go +++ /dev/null @@ -1,67 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package vector - -import ( - "fmt" - "sort" - "testing" -) - -var ( - zero interface{} - intzero int - strzero string -) - -func int2Value(x int) int { return x } -func int2IntValue(x int) int { return x } -func int2StrValue(x int) string { return string(x) } - -func elem2Value(x interface{}) int { return x.(int) } -func elem2IntValue(x int) int { return x } -func elem2StrValue(x string) string { return x } - -func intf2Value(x interface{}) int { return x.(int) } -func intf2IntValue(x interface{}) int { return x.(int) } -func intf2StrValue(x interface{}) string { return x.(string) } - -type VectorInterface interface { - Len() int - Cap() int -} - -func checkSize(t *testing.T, v VectorInterface, len, cap int) { - if v.Len() != len { - t.Errorf("%T expected len = %d; found %d", v, len, v.Len()) - } - if v.Cap() < cap { - t.Errorf("%T expected cap >= %d; found %d", v, cap, v.Cap()) - } -} - -func val(i int) int { return i*991 - 1234 } - -func TestSorting(t *testing.T) { - const n = 100 - - a := new(IntVector).Resize(n, 0) - for i := n - 1; i >= 0; i-- { - a.Set(i, n-1-i) - } - if sort.IsSorted(a) { - t.Error("int vector not sorted") - } - - b := new(StringVector).Resize(n, 0) - for i := n - 1; i >= 0; i-- { - b.Set(i, fmt.Sprint(n-1-i)) - } - if sort.IsSorted(b) { - t.Error("string vector not sorted") - } -} - -func tname(x interface{}) string { return fmt.Sprintf("%T: ", x) } diff --git a/libgo/go/container/vector/numbers_test.go b/libgo/go/container/vector/numbers_test.go deleted file mode 100644 index abe01a8fb18..00000000000 --- a/libgo/go/container/vector/numbers_test.go +++ /dev/null @@ -1,123 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package vector - -import ( - "fmt" - "runtime" - "strings" - "testing" -) - -const memTestN = 1000000 - -func s(n uint64) string { - str := fmt.Sprintf("%d", n) - lens := len(str) - a := make([]string, (lens+2)/3) - start := lens - for i := range a { - start -= 3 - if start < 0 { - start = 0 - } - a[len(a)-i-1] = str[start:lens] - lens -= 3 - } - return strings.Join(a, " ") -} - -func TestVectorNums(t *testing.T) { - if testing.Short() { - return - } - var v Vector - c := int(0) - runtime.GC() - m0 := runtime.MemStats - v.Resize(memTestN, memTestN) - for i := 0; i < memTestN; i++ { - v.Set(i, c) - } - runtime.GC() - m := runtime.MemStats - v.Resize(0, 0) - runtime.GC() - n := m.Alloc - m0.Alloc - t.Logf("%T.Push(%#v), n = %s: Alloc/n = %.2f\n", v, c, s(memTestN), float64(n)/memTestN) -} - -func TestIntVectorNums(t *testing.T) { - if testing.Short() { - return - } - var v IntVector - c := int(0) - runtime.GC() - m0 := runtime.MemStats - v.Resize(memTestN, memTestN) - for i := 0; i < memTestN; i++ { - v.Set(i, c) - } - runtime.GC() - m := runtime.MemStats - v.Resize(0, 0) - runtime.GC() - n := m.Alloc - m0.Alloc - t.Logf("%T.Push(%#v), n = %s: Alloc/n = %.2f\n", v, c, s(memTestN), float64(n)/memTestN) -} - -func TestStringVectorNums(t *testing.T) { - if testing.Short() { - return - } - var v StringVector - c := "" - runtime.GC() - m0 := runtime.MemStats - v.Resize(memTestN, memTestN) - for i := 0; i < memTestN; i++ { - v.Set(i, c) - } - runtime.GC() - m := runtime.MemStats - v.Resize(0, 0) - runtime.GC() - n := m.Alloc - m0.Alloc - t.Logf("%T.Push(%#v), n = %s: Alloc/n = %.2f\n", v, c, s(memTestN), float64(n)/memTestN) -} - -func BenchmarkVectorNums(b *testing.B) { - c := int(0) - var v Vector - b.StopTimer() - runtime.GC() - b.StartTimer() - for i := 0; i < b.N; i++ { - v.Push(c) - } -} - -func BenchmarkIntVectorNums(b *testing.B) { - c := int(0) - var v IntVector - b.StopTimer() - runtime.GC() - b.StartTimer() - for i := 0; i < b.N; i++ { - v.Push(c) - } -} - -func BenchmarkStringVectorNums(b *testing.B) { - c := "" - var v StringVector - b.StopTimer() - runtime.GC() - b.StartTimer() - for i := 0; i < b.N; i++ { - v.Push(c) - } -} diff --git a/libgo/go/container/vector/stringvector.go b/libgo/go/container/vector/stringvector.go deleted file mode 100644 index dc81f06b74d..00000000000 --- a/libgo/go/container/vector/stringvector.go +++ /dev/null @@ -1,188 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector.go, it was generated -// automatically from vector.go - DO NOT EDIT in that case! - -package vector - -func (p *StringVector) realloc(length, capacity int) (b []string) { - if capacity < initialSize { - capacity = initialSize - } - if capacity < length { - capacity = length - } - b = make(StringVector, length, capacity) - copy(b, *p) - *p = b - return -} - -// Insert n elements at position i. -func (p *StringVector) Expand(i, n int) { - a := *p - - // make sure we have enough space - 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 - if capb < len1 { - // still not enough - use required length - capb = len1 - } - // capb >= len1 - a = p.realloc(len1, capb) - } - - // make a hole - for j := len0 - 1; j >= i; j-- { - a[j+n] = a[j] - } - - *p = a -} - -// Insert n elements at the end of a vector. -func (p *StringVector) Extend(n int) { p.Expand(len(*p), n) } - -// Resize changes the length and capacity of a vector. -// If the new length is shorter than the current length, Resize discards -// trailing elements. If the new length is longer than the current length, -// Resize adds the respective zero values for the additional elements. The capacity -// parameter is ignored unless the new length or capacity is longer than the current -// capacity. The resized vector's capacity may be larger than the requested capacity. -func (p *StringVector) Resize(length, capacity int) *StringVector { - a := *p - - if length > cap(a) || capacity > cap(a) { - // not enough space or larger capacity requested explicitly - a = p.realloc(length, capacity) - } else if length < len(a) { - // clear trailing elements - for i := range a[length:] { - var zero string - a[length+i] = zero - } - } - - *p = a[0:length] - return p -} - -// Len returns the number of elements in the vector. -// Same as len(*p). -func (p *StringVector) Len() int { return len(*p) } - -// Cap returns the capacity of the vector; that is, the -// maximum length the vector can grow without resizing. -// Same as cap(*p). -func (p *StringVector) Cap() int { return cap(*p) } - -// At returns the i'th element of the vector. -func (p *StringVector) At(i int) string { return (*p)[i] } - -// Set sets the i'th element of the vector to value x. -func (p *StringVector) Set(i int, x string) { (*p)[i] = x } - -// Last returns the element in the vector of highest index. -func (p *StringVector) Last() string { return (*p)[len(*p)-1] } - -// Copy makes a copy of the vector and returns it. -func (p *StringVector) Copy() StringVector { - arr := make(StringVector, len(*p)) - copy(arr, *p) - return arr -} - -// Insert inserts into the vector an element of value x before -// the current element at index i. -func (p *StringVector) Insert(i int, x string) { - p.Expand(i, 1) - (*p)[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 *StringVector) Delete(i int) { - a := *p - n := len(a) - - copy(a[i:n-1], a[i+1:n]) - var zero string - a[n-1] = zero // support GC, zero out entry - *p = 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 *StringVector) InsertVector(i int, x *StringVector) { - b := *x - - p.Expand(i, len(b)) - copy((*p)[i:i+len(b)], b) -} - -// Cut deletes elements i through j-1, inclusive. -func (p *StringVector) Cut(i, j int) { - a := *p - n := len(a) - m := n - (j - i) - - copy(a[i:m], a[j:n]) - for k := m; k < n; k++ { //TODO(bflm) don't zero out the elements unless it's a Vector. - var zero string - a[k] = zero // support GC, zero out entries - } - - *p = a[0:m] -} - -// Slice returns a new sub-vector by slicing the old one to extract slice [i:j]. -// The elements are copied. The original vector is unchanged. -func (p *StringVector) Slice(i, j int) *StringVector { - var s StringVector - s.realloc(j-i, 0) // will fail in Init() if j < i - copy(s, (*p)[i:j]) - return &s -} - -// Convenience wrappers - -// Push appends x to the end of the vector. -func (p *StringVector) Push(x string) { p.Insert(len(*p), x) } - -// Pop deletes the last element of the vector. -func (p *StringVector) Pop() string { - a := *p - - i := len(a) - 1 - x := a[i] - var zero string - a[i] = zero // support GC, zero out entry - *p = a[0:i] - return x -} - -// AppendVector appends the entire vector x to the end of this vector. -func (p *StringVector) AppendVector(x *StringVector) { p.InsertVector(len(*p), x) } - -// Swap exchanges the elements at indexes i and j. -func (p *StringVector) Swap(i, j int) { - a := *p - a[i], a[j] = a[j], a[i] -} - -// Do calls function f for each element of the vector, in order. -// The behavior of Do is undefined if f changes *p. -func (p *StringVector) Do(f func(elem string)) { - for _, e := range *p { - f(e) - } -} diff --git a/libgo/go/container/vector/stringvector_test.go b/libgo/go/container/vector/stringvector_test.go deleted file mode 100644 index c75676f786c..00000000000 --- a/libgo/go/container/vector/stringvector_test.go +++ /dev/null @@ -1,331 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector_test.go, it was generated -// automatically from vector_test.go - DO NOT EDIT in that case! - -package vector - -import "testing" - -func TestStrZeroLen(t *testing.T) { - a := new(StringVector) - if a.Len() != 0 { - t.Errorf("%T: B1) expected 0, got %d", a, a.Len()) - } - if len(*a) != 0 { - t.Errorf("%T: B2) expected 0, got %d", a, len(*a)) - } - var b StringVector - if b.Len() != 0 { - t.Errorf("%T: B3) expected 0, got %d", b, b.Len()) - } - if len(b) != 0 { - t.Errorf("%T: B4) expected 0, got %d", b, len(b)) - } -} - -func TestStrResize(t *testing.T) { - var a StringVector - 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 TestStrResize2(t *testing.T) { - var a StringVector - checkSize(t, &a, 0, 0) - a.Push(int2StrValue(1)) - a.Push(int2StrValue(2)) - a.Push(int2StrValue(3)) - a.Push(int2StrValue(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) != strzero { - t.Errorf("%T: expected a.At(%d) == %v; found %v!", a, i, strzero, a.At(i)) - } - } - for i := 4; i < len(a); i++ { - if a[i] != strzero { - t.Errorf("%T: expected a[%d] == %v; found %v", a, i, strzero, a[i]) - } - } -} - -func checkStrZero(t *testing.T, a *StringVector, i int) { - for j := 0; j < i; j++ { - if a.At(j) == strzero { - t.Errorf("%T: 1 expected a.At(%d) == %d; found %v", a, j, j, a.At(j)) - } - if (*a)[j] == strzero { - t.Errorf("%T: 2 expected (*a)[%d] == %d; found %v", a, j, j, (*a)[j]) - } - } - for ; i < a.Len(); i++ { - if a.At(i) != strzero { - t.Errorf("%T: 3 expected a.At(%d) == %v; found %v", a, i, strzero, a.At(i)) - } - if (*a)[i] != strzero { - t.Errorf("%T: 4 expected (*a)[%d] == %v; found %v", a, i, strzero, (*a)[i]) - } - } -} - -func TestStrTrailingElements(t *testing.T) { - var a StringVector - for i := 0; i < 10; i++ { - a.Push(int2StrValue(i + 1)) - } - checkStrZero(t, &a, 10) - checkSize(t, &a, 10, 16) - checkSize(t, a.Resize(5, 0), 5, 16) - checkSize(t, a.Resize(10, 0), 10, 16) - checkStrZero(t, &a, 5) -} - -func TestStrAccess(t *testing.T) { - const n = 100 - var a StringVector - a.Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2StrValue(val(i))) - } - for i := 0; i < n; i++ { - if elem2StrValue(a.At(i)) != int2StrValue(val(i)) { - t.Error(i) - } - } - var b StringVector - b.Resize(n, 0) - for i := 0; i < n; i++ { - b[i] = int2StrValue(val(i)) - } - for i := 0; i < n; i++ { - if elem2StrValue(b[i]) != int2StrValue(val(i)) { - t.Error(i) - } - } -} - -func TestStrInsertDeleteClear(t *testing.T) { - const n = 100 - var a StringVector - - for i := 0; i < n; i++ { - if a.Len() != i { - t.Errorf("%T: A) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: A) wrong len() %d (expected %d)", a, len(a), i) - } - a.Insert(0, int2StrValue(val(i))) - if elem2StrValue(a.Last()) != int2StrValue(val(0)) { - t.Errorf("%T: B", a) - } - } - for i := n - 1; i >= 0; i-- { - if elem2StrValue(a.Last()) != int2StrValue(val(0)) { - t.Errorf("%T: C", a) - } - if elem2StrValue(a.At(0)) != int2StrValue(val(i)) { - t.Errorf("%T: D", a) - } - if elem2StrValue(a[0]) != int2StrValue(val(i)) { - t.Errorf("%T: D2", a) - } - a.Delete(0) - if a.Len() != i { - t.Errorf("%T: E) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: E) wrong len() %d (expected %d)", a, len(a), i) - } - } - - if a.Len() != 0 { - t.Errorf("%T: F) wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: F) wrong len() %d (expected 0)", a, len(a)) - } - for i := 0; i < n; i++ { - a.Push(int2StrValue(val(i))) - if a.Len() != i+1 { - t.Errorf("%T: G) wrong Len() %d (expected %d)", a, a.Len(), i+1) - } - if len(a) != i+1 { - t.Errorf("%T: G) wrong len() %d (expected %d)", a, len(a), i+1) - } - if elem2StrValue(a.Last()) != int2StrValue(val(i)) { - t.Errorf("%T: H", a) - } - } - a.Resize(0, 0) - if a.Len() != 0 { - t.Errorf("%T: I wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: I wrong len() %d (expected 0)", a, len(a)) - } - - const m = 5 - for j := 0; j < m; j++ { - a.Push(int2StrValue(j)) - for i := 0; i < n; i++ { - x := val(i) - a.Push(int2StrValue(x)) - if elem2StrValue(a.Pop()) != int2StrValue(x) { - t.Errorf("%T: J", a) - } - if a.Len() != j+1 { - t.Errorf("%T: K) wrong Len() %d (expected %d)", a, a.Len(), j+1) - } - if len(a) != j+1 { - t.Errorf("%T: K) wrong len() %d (expected %d)", a, len(a), j+1) - } - } - } - if a.Len() != m { - t.Errorf("%T: L) wrong Len() %d (expected %d)", a, a.Len(), m) - } - if len(a) != m { - t.Errorf("%T: L) wrong len() %d (expected %d)", a, len(a), m) - } -} - -func verify_sliceStr(t *testing.T, x *StringVector, elt, i, j int) { - for k := i; k < j; k++ { - if elem2StrValue(x.At(k)) != int2StrValue(elt) { - t.Errorf("%T: M) wrong [%d] element %v (expected %v)", x, k, elem2StrValue(x.At(k)), int2StrValue(elt)) - } - } - - s := x.Slice(i, j) - for k, n := 0, j-i; k < n; k++ { - if elem2StrValue(s.At(k)) != int2StrValue(elt) { - t.Errorf("%T: N) wrong [%d] element %v (expected %v)", x, k, elem2StrValue(x.At(k)), int2StrValue(elt)) - } - } -} - -func verify_patternStr(t *testing.T, x *StringVector, a, b, c int) { - n := a + b + c - if x.Len() != n { - t.Errorf("%T: O) wrong Len() %d (expected %d)", x, x.Len(), n) - } - if len(*x) != n { - t.Errorf("%T: O) wrong len() %d (expected %d)", x, len(*x), n) - } - verify_sliceStr(t, x, 0, 0, a) - verify_sliceStr(t, x, 1, a, a+b) - verify_sliceStr(t, x, 0, a+b, n) -} - -func make_vectorStr(elt, len int) *StringVector { - x := new(StringVector).Resize(len, 0) - for i := 0; i < len; i++ { - x.Set(i, int2StrValue(elt)) - } - return x -} - -func TestStrInsertVector(t *testing.T) { - // 1 - a := make_vectorStr(0, 0) - b := make_vectorStr(1, 10) - a.InsertVector(0, b) - verify_patternStr(t, a, 0, 10, 0) - // 2 - a = make_vectorStr(0, 10) - b = make_vectorStr(1, 0) - a.InsertVector(5, b) - verify_patternStr(t, a, 5, 0, 5) - // 3 - a = make_vectorStr(0, 10) - b = make_vectorStr(1, 3) - a.InsertVector(3, b) - verify_patternStr(t, a, 3, 3, 7) - // 4 - a = make_vectorStr(0, 10) - b = make_vectorStr(1, 1000) - a.InsertVector(8, b) - verify_patternStr(t, a, 8, 1000, 2) -} - -func TestStrDo(t *testing.T) { - const n = 25 - const salt = 17 - a := new(StringVector).Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2StrValue(salt*i)) - } - count := 0 - a.Do(func(e string) { - i := intf2StrValue(e) - if i != int2StrValue(count*salt) { - t.Error(tname(a), "value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(a), "should visit", n, "values; did visit", count) - } - - b := new(StringVector).Resize(n, 0) - for i := 0; i < n; i++ { - (*b)[i] = int2StrValue(salt * i) - } - count = 0 - b.Do(func(e string) { - i := intf2StrValue(e) - if i != int2StrValue(count*salt) { - t.Error(tname(b), "b) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(b), "b) should visit", n, "values; did visit", count) - } - - var c StringVector - c.Resize(n, 0) - for i := 0; i < n; i++ { - c[i] = int2StrValue(salt * i) - } - count = 0 - c.Do(func(e string) { - i := intf2StrValue(e) - if i != int2StrValue(count*salt) { - t.Error(tname(c), "c) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(c), "c) should visit", n, "values; did visit", count) - } - -} - -func TestStrVectorCopy(t *testing.T) { - // verify Copy() returns a copy, not simply a slice of the original vector - const Len = 10 - var src StringVector - for i := 0; i < Len; i++ { - src.Push(int2StrValue(i * i)) - } - dest := src.Copy() - for i := 0; i < Len; i++ { - src[i] = int2StrValue(-1) - v := elem2StrValue(dest[i]) - if v != int2StrValue(i*i) { - t.Error(tname(src), "expected", i*i, "got", v) - } - } -} diff --git a/libgo/go/container/vector/vector.go b/libgo/go/container/vector/vector.go deleted file mode 100644 index 8470ec067ac..00000000000 --- a/libgo/go/container/vector/vector.go +++ /dev/null @@ -1,188 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector.go, it was generated -// automatically from vector.go - DO NOT EDIT in that case! - -package vector - -func (p *Vector) realloc(length, capacity int) (b []interface{}) { - if capacity < initialSize { - capacity = initialSize - } - if capacity < length { - capacity = length - } - b = make(Vector, length, capacity) - copy(b, *p) - *p = b - return -} - -// Insert n elements at position i. -func (p *Vector) Expand(i, n int) { - a := *p - - // make sure we have enough space - 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 - if capb < len1 { - // still not enough - use required length - capb = len1 - } - // capb >= len1 - a = p.realloc(len1, capb) - } - - // make a hole - for j := len0 - 1; j >= i; j-- { - a[j+n] = a[j] - } - - *p = a -} - -// Insert n elements at the end of a vector. -func (p *Vector) Extend(n int) { p.Expand(len(*p), n) } - -// Resize changes the length and capacity of a vector. -// If the new length is shorter than the current length, Resize discards -// trailing elements. If the new length is longer than the current length, -// Resize adds the respective zero values for the additional elements. The capacity -// parameter is ignored unless the new length or capacity is longer than 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 - - if length > cap(a) || capacity > cap(a) { - // not enough space or larger capacity requested explicitly - a = p.realloc(length, capacity) - } else if length < len(a) { - // clear trailing elements - for i := range a[length:] { - var zero interface{} - a[length+i] = zero - } - } - - *p = a[0:length] - return p -} - -// Len returns the number of elements in the vector. -// Same as len(*p). -func (p *Vector) Len() int { return len(*p) } - -// Cap returns the capacity of the vector; that is, the -// maximum length the vector can grow without resizing. -// Same as cap(*p). -func (p *Vector) Cap() int { return cap(*p) } - -// At returns the i'th element of the vector. -func (p *Vector) At(i int) interface{} { return (*p)[i] } - -// Set sets the i'th element of the vector to value x. -func (p *Vector) Set(i int, x interface{}) { (*p)[i] = x } - -// Last returns the element in the vector of highest index. -func (p *Vector) Last() interface{} { return (*p)[len(*p)-1] } - -// Copy makes a copy of the vector and returns it. -func (p *Vector) Copy() Vector { - arr := make(Vector, len(*p)) - copy(arr, *p) - 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)[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 - n := len(a) - - copy(a[i:n-1], a[i+1:n]) - var zero interface{} - a[n-1] = zero // support GC, zero out entry - *p = 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) { - b := *x - - p.Expand(i, len(b)) - copy((*p)[i:i+len(b)], b) -} - -// Cut deletes elements i through j-1, inclusive. -func (p *Vector) Cut(i, j int) { - a := *p - n := len(a) - m := n - (j - i) - - copy(a[i:m], a[j:n]) - for k := m; k < n; k++ { //TODO(bflm) don't zero out the elements unless it's a Vector. - var zero interface{} - a[k] = zero // support GC, zero out entries - } - - *p = a[0:m] -} - -// Slice returns a new sub-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 { - var s Vector - s.realloc(j-i, 0) // will fail in Init() if j < i - copy(s, (*p)[i:j]) - return &s -} - -// Convenience wrappers - -// Push appends x to the end of the vector. -func (p *Vector) Push(x interface{}) { p.Insert(len(*p), x) } - -// Pop deletes the last element of the vector. -func (p *Vector) Pop() interface{} { - a := *p - - i := len(a) - 1 - x := a[i] - var zero interface{} - a[i] = zero // support GC, zero out entry - *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), x) } - -// Swap exchanges the elements at indexes i and j. -func (p *Vector) Swap(i, j int) { - a := *p - a[i], a[j] = a[j], a[i] -} - -// Do calls function f for each element of the vector, in order. -// The behavior of Do is undefined if f changes *p. -func (p *Vector) Do(f func(elem interface{})) { - for _, e := range *p { - f(e) - } -} diff --git a/libgo/go/container/vector/vector_test.go b/libgo/go/container/vector/vector_test.go deleted file mode 100644 index a7f47b8c2a5..00000000000 --- a/libgo/go/container/vector/vector_test.go +++ /dev/null @@ -1,331 +0,0 @@ -// Copyright 2009 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// CAUTION: If this file is not vector_test.go, it was generated -// automatically from vector_test.go - DO NOT EDIT in that case! - -package vector - -import "testing" - -func TestZeroLen(t *testing.T) { - a := new(Vector) - if a.Len() != 0 { - t.Errorf("%T: B1) expected 0, got %d", a, a.Len()) - } - if len(*a) != 0 { - t.Errorf("%T: B2) expected 0, got %d", a, len(*a)) - } - var b Vector - if b.Len() != 0 { - t.Errorf("%T: B3) expected 0, got %d", b, b.Len()) - } - if len(b) != 0 { - t.Errorf("%T: B4) expected 0, got %d", b, len(b)) - } -} - -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) -} - -func TestResize2(t *testing.T) { - var a Vector - checkSize(t, &a, 0, 0) - a.Push(int2Value(1)) - a.Push(int2Value(2)) - a.Push(int2Value(3)) - a.Push(int2Value(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) != zero { - t.Errorf("%T: expected a.At(%d) == %v; found %v!", a, i, zero, a.At(i)) - } - } - for i := 4; i < len(a); i++ { - if a[i] != zero { - t.Errorf("%T: expected a[%d] == %v; found %v", a, i, zero, a[i]) - } - } -} - -func checkZero(t *testing.T, a *Vector, i int) { - for j := 0; j < i; j++ { - if a.At(j) == zero { - t.Errorf("%T: 1 expected a.At(%d) == %d; found %v", a, j, j, a.At(j)) - } - if (*a)[j] == zero { - t.Errorf("%T: 2 expected (*a)[%d] == %d; found %v", a, j, j, (*a)[j]) - } - } - for ; i < a.Len(); i++ { - if a.At(i) != zero { - t.Errorf("%T: 3 expected a.At(%d) == %v; found %v", a, i, zero, a.At(i)) - } - if (*a)[i] != zero { - t.Errorf("%T: 4 expected (*a)[%d] == %v; found %v", a, i, zero, (*a)[i]) - } - } -} - -func TestTrailingElements(t *testing.T) { - var a Vector - for i := 0; i < 10; i++ { - a.Push(int2Value(i + 1)) - } - checkZero(t, &a, 10) - checkSize(t, &a, 10, 16) - checkSize(t, a.Resize(5, 0), 5, 16) - checkSize(t, a.Resize(10, 0), 10, 16) - checkZero(t, &a, 5) -} - -func TestAccess(t *testing.T) { - const n = 100 - var a Vector - a.Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2Value(val(i))) - } - for i := 0; i < n; i++ { - if elem2Value(a.At(i)) != int2Value(val(i)) { - t.Error(i) - } - } - var b Vector - b.Resize(n, 0) - for i := 0; i < n; i++ { - b[i] = int2Value(val(i)) - } - for i := 0; i < n; i++ { - if elem2Value(b[i]) != int2Value(val(i)) { - t.Error(i) - } - } -} - -func TestInsertDeleteClear(t *testing.T) { - const n = 100 - var a Vector - - for i := 0; i < n; i++ { - if a.Len() != i { - t.Errorf("%T: A) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: A) wrong len() %d (expected %d)", a, len(a), i) - } - a.Insert(0, int2Value(val(i))) - if elem2Value(a.Last()) != int2Value(val(0)) { - t.Errorf("%T: B", a) - } - } - for i := n - 1; i >= 0; i-- { - if elem2Value(a.Last()) != int2Value(val(0)) { - t.Errorf("%T: C", a) - } - if elem2Value(a.At(0)) != int2Value(val(i)) { - t.Errorf("%T: D", a) - } - if elem2Value(a[0]) != int2Value(val(i)) { - t.Errorf("%T: D2", a) - } - a.Delete(0) - if a.Len() != i { - t.Errorf("%T: E) wrong Len() %d (expected %d)", a, a.Len(), i) - } - if len(a) != i { - t.Errorf("%T: E) wrong len() %d (expected %d)", a, len(a), i) - } - } - - if a.Len() != 0 { - t.Errorf("%T: F) wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: F) wrong len() %d (expected 0)", a, len(a)) - } - for i := 0; i < n; i++ { - a.Push(int2Value(val(i))) - if a.Len() != i+1 { - t.Errorf("%T: G) wrong Len() %d (expected %d)", a, a.Len(), i+1) - } - if len(a) != i+1 { - t.Errorf("%T: G) wrong len() %d (expected %d)", a, len(a), i+1) - } - if elem2Value(a.Last()) != int2Value(val(i)) { - t.Errorf("%T: H", a) - } - } - a.Resize(0, 0) - if a.Len() != 0 { - t.Errorf("%T: I wrong Len() %d (expected 0)", a, a.Len()) - } - if len(a) != 0 { - t.Errorf("%T: I wrong len() %d (expected 0)", a, len(a)) - } - - const m = 5 - for j := 0; j < m; j++ { - a.Push(int2Value(j)) - for i := 0; i < n; i++ { - x := val(i) - a.Push(int2Value(x)) - if elem2Value(a.Pop()) != int2Value(x) { - t.Errorf("%T: J", a) - } - if a.Len() != j+1 { - t.Errorf("%T: K) wrong Len() %d (expected %d)", a, a.Len(), j+1) - } - if len(a) != j+1 { - t.Errorf("%T: K) wrong len() %d (expected %d)", a, len(a), j+1) - } - } - } - if a.Len() != m { - t.Errorf("%T: L) wrong Len() %d (expected %d)", a, a.Len(), m) - } - if len(a) != m { - t.Errorf("%T: L) wrong len() %d (expected %d)", a, len(a), m) - } -} - -func verify_slice(t *testing.T, x *Vector, elt, i, j int) { - for k := i; k < j; k++ { - if elem2Value(x.At(k)) != int2Value(elt) { - t.Errorf("%T: M) wrong [%d] element %v (expected %v)", x, k, elem2Value(x.At(k)), int2Value(elt)) - } - } - - s := x.Slice(i, j) - for k, n := 0, j-i; k < n; k++ { - if elem2Value(s.At(k)) != int2Value(elt) { - t.Errorf("%T: N) wrong [%d] element %v (expected %v)", x, k, elem2Value(x.At(k)), int2Value(elt)) - } - } -} - -func verify_pattern(t *testing.T, x *Vector, a, b, c int) { - n := a + b + c - if x.Len() != n { - t.Errorf("%T: O) wrong Len() %d (expected %d)", x, x.Len(), n) - } - if len(*x) != n { - t.Errorf("%T: O) wrong len() %d (expected %d)", x, len(*x), 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) - for i := 0; i < len; i++ { - x.Set(i, int2Value(elt)) - } - 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) - // 2 - 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) - // 4 - a = make_vector(0, 10) - b = make_vector(1, 1000) - a.InsertVector(8, b) - verify_pattern(t, a, 8, 1000, 2) -} - -func TestDo(t *testing.T) { - const n = 25 - const salt = 17 - a := new(Vector).Resize(n, 0) - for i := 0; i < n; i++ { - a.Set(i, int2Value(salt*i)) - } - count := 0 - a.Do(func(e interface{}) { - i := intf2Value(e) - if i != int2Value(count*salt) { - t.Error(tname(a), "value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(a), "should visit", n, "values; did visit", count) - } - - b := new(Vector).Resize(n, 0) - for i := 0; i < n; i++ { - (*b)[i] = int2Value(salt * i) - } - count = 0 - b.Do(func(e interface{}) { - i := intf2Value(e) - if i != int2Value(count*salt) { - t.Error(tname(b), "b) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(b), "b) should visit", n, "values; did visit", count) - } - - var c Vector - c.Resize(n, 0) - for i := 0; i < n; i++ { - c[i] = int2Value(salt * i) - } - count = 0 - c.Do(func(e interface{}) { - i := intf2Value(e) - if i != int2Value(count*salt) { - t.Error(tname(c), "c) value at", count, "should be", count*salt, "not", i) - } - count++ - }) - if count != n { - t.Error(tname(c), "c) should visit", n, "values; did visit", count) - } - -} - -func TestVectorCopy(t *testing.T) { - // verify Copy() returns a copy, not simply a slice of the original vector - const Len = 10 - var src Vector - for i := 0; i < Len; i++ { - src.Push(int2Value(i * i)) - } - dest := src.Copy() - for i := 0; i < Len; i++ { - src[i] = int2Value(-1) - v := elem2Value(dest[i]) - if v != int2Value(i*i) { - t.Error(tname(src), "expected", i*i, "got", v) - } - } -} |