obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

15 files changed, 2986 insertions, 0 deletions

diff --git a/libgo/go/container/heap/heap.go b/libgo/go/container/heap/heap.go
new file mode 100644
index 000000000..4435a57c4
--- /dev/null
+++ b/libgo/go/container/heap/heap.go
@@ -0,0 +1,102 @@
+// 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.
+
+// This package provides heap operations for any type that implements
+// heap.Interface.
+//
+package heap
+
+import "sort"
+
+// Any type that implements heap.Interface may be used as a
+// min-heap with the following invariants (established after
+// Init has been called):
+//
+//	!h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()
+//
+type Interface interface {
+	sort.Interface
+	Push(x interface{})
+	Pop() interface{}
+}
+
+
+// A heaper must be initialized before any of the heap operations
+// can be used. Init is idempotent with respect to the heap invariants
+// and may be called whenever the heap invariants may have been invalidated.
+// Its complexity is O(n) where n = h.Len().
+//
+func Init(h Interface) {
+	// heapify
+	n := h.Len()
+	for i := n/2 - 1; i >= 0; i-- {
+		down(h, i, n)
+	}
+}
+
+
+// Push pushes the element x onto the heap. The complexity is
+// O(log(n)) where n = h.Len().
+//
+func Push(h Interface, x interface{}) {
+	h.Push(x)
+	up(h, h.Len()-1)
+}
+
+
+// Pop removes the minimum element (according to Less) from the heap
+// and returns it. The complexity is O(log(n)) where n = h.Len().
+// Same as Remove(h, 0).
+//
+func Pop(h Interface) interface{} {
+	n := h.Len() - 1
+	h.Swap(0, n)
+	down(h, 0, n)
+	return h.Pop()
+}
+
+
+// Remove removes the element at index i from the heap.
+// The complexity is O(log(n)) where n = h.Len().
+//
+func Remove(h Interface, i int) interface{} {
+	n := h.Len() - 1
+	if n != i {
+		h.Swap(i, n)
+		down(h, i, n)
+		up(h, i)
+	}
+	return h.Pop()
+}
+
+
+func up(h Interface, j int) {
+	for {
+		i := (j - 1) / 2 // parent
+		if i == j || h.Less(i, j) {
+			break
+		}
+		h.Swap(i, j)
+		j = i
+	}
+}
+
+
+func down(h Interface, i, n int) {
+	for {
+		j1 := 2*i + 1
+		if j1 >= n {
+			break
+		}
+		j := j1 // left child
+		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
+			j = j2 // = 2*i + 2  // right child
+		}
+		if h.Less(i, j) {
+			break
+		}
+		h.Swap(i, j)
+		i = j
+	}
+}
diff --git a/libgo/go/container/heap/heap_test.go b/libgo/go/container/heap/heap_test.go
new file mode 100644
index 000000000..89d444dd5
--- /dev/null
+++ b/libgo/go/container/heap/heap_test.go
@@ -0,0 +1,166 @@
+// 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 heap
+
+import (
+	"testing"
+	"container/vector"
+)
+
+
+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
+}
+
+
+func (h *myHeap) Less(i, j int) bool { return h.At(i).(int) < h.At(j).(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))
+			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))
+			return
+		}
+		h.verify(t, j2)
+	}
+}
+
+
+func TestInit0(t *testing.T) {
+	h := new(myHeap)
+	for i := 20; i > 0; i-- {
+		h.Push(0) // all elements are the same
+	}
+	Init(h)
+	h.verify(t, 0)
+
+	for i := 1; h.Len() > 0; i++ {
+		x := Pop(h).(int)
+		h.verify(t, 0)
+		if x != 0 {
+			t.Errorf("%d.th pop got %d; want %d", i, x, 0)
+		}
+	}
+}
+
+
+func TestInit1(t *testing.T) {
+	h := new(myHeap)
+	for i := 20; i > 0; i-- {
+		h.Push(i) // all elements are different
+	}
+	Init(h)
+	h.verify(t, 0)
+
+	for i := 1; h.Len() > 0; i++ {
+		x := Pop(h).(int)
+		h.verify(t, 0)
+		if x != i {
+			t.Errorf("%d.th pop got %d; want %d", i, x, i)
+		}
+	}
+}
+
+
+func Test(t *testing.T) {
+	h := new(myHeap)
+	h.verify(t, 0)
+
+	for i := 20; i > 10; i-- {
+		h.Push(i)
+	}
+	Init(h)
+	h.verify(t, 0)
+
+	for i := 10; i > 0; i-- {
+		Push(h, i)
+		h.verify(t, 0)
+	}
+
+	for i := 1; h.Len() > 0; i++ {
+		x := Pop(h).(int)
+		if i < 20 {
+			Push(h, 20+i)
+		}
+		h.verify(t, 0)
+		if x != i {
+			t.Errorf("%d.th pop got %d; want %d", i, x, i)
+		}
+	}
+}
+
+
+func TestRemove0(t *testing.T) {
+	h := new(myHeap)
+	for i := 0; i < 10; i++ {
+		h.Push(i)
+	}
+	h.verify(t, 0)
+
+	for h.Len() > 0 {
+		i := h.Len() - 1
+		x := Remove(h, i).(int)
+		if x != i {
+			t.Errorf("Remove(%d) got %d; want %d", i, x, i)
+		}
+		h.verify(t, 0)
+	}
+}
+
+
+func TestRemove1(t *testing.T) {
+	h := new(myHeap)
+	for i := 0; i < 10; i++ {
+		h.Push(i)
+	}
+	h.verify(t, 0)
+
+	for i := 0; h.Len() > 0; i++ {
+		x := Remove(h, 0).(int)
+		if x != i {
+			t.Errorf("Remove(0) got %d; want %d", x, i)
+		}
+		h.verify(t, 0)
+	}
+}
+
+
+func TestRemove2(t *testing.T) {
+	N := 10
+
+	h := new(myHeap)
+	for i := 0; i < N; i++ {
+		h.Push(i)
+	}
+	h.verify(t, 0)
+
+	m := make(map[int]bool)
+	for h.Len() > 0 {
+		m[Remove(h, (h.Len()-1)/2).(int)] = true
+		h.verify(t, 0)
+	}
+
+	if len(m) != N {
+		t.Errorf("len(m) = %d; want %d", len(m), N)
+	}
+	for i := 0; i < len(m); i++ {
+		if !m[i] {
+			t.Errorf("m[%d] doesn't exist", i)
+		}
+	}
+}
diff --git a/libgo/go/container/list/list.go b/libgo/go/container/list/list.go
new file mode 100755
index 000000000..c1ebcddaa
--- /dev/null
+++ b/libgo/go/container/list/list.go
@@ -0,0 +1,211 @@
+// 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.
+
+// The list package implements a doubly linked list.
+//
+// To iterate over a list (where l is a *List):
+//	for e := l.Front(); e != nil; e = e.Next() {
+//		// do something with e.Value
+//	}
+//
+package list
+
+// Element is an element in the linked list.
+type Element struct {
+	// Next and previous pointers in the doubly-linked list of elements.
+	// The front of the list has prev = nil, and the back has next = nil.
+	next, prev *Element
+
+	// The list to which this element belongs.
+	list *List
+
+	// The contents of this list element.
+	Value interface{}
+}
+
+// Next returns the next list element or nil.
+func (e *Element) Next() *Element { return e.next }
+
+// Prev returns the previous list element or nil.
+func (e *Element) Prev() *Element { return e.prev }
+
+// List represents a doubly linked list.
+// The zero value for List is an empty list ready to use.
+type List struct {
+	front, back *Element
+	len         int
+}
+
+// Init initializes or clears a List.
+func (l *List) Init() *List {
+	l.front = nil
+	l.back = nil
+	l.len = 0
+	return l
+}
+
+// New returns an initialized list.
+func New() *List { return new(List) }
+
+// Front returns the first element in the list.
+func (l *List) Front() *Element { return l.front }
+
+// Back returns the last element in the list.
+func (l *List) Back() *Element { return l.back }
+
+// Remove removes the element from the list
+// and returns its Value.
+func (l *List) Remove(e *Element) interface{} {
+	l.remove(e)
+	e.list = nil // do what remove does not
+	return e.Value
+}
+
+// remove the element from the list, but do not clear the Element's list field.
+// This is so that other List methods may use remove when relocating Elements
+// without needing to restore the list field.
+func (l *List) remove(e *Element) {
+	if e.list != l {
+		return
+	}
+	if e.prev == nil {
+		l.front = e.next
+	} else {
+		e.prev.next = e.next
+	}
+	if e.next == nil {
+		l.back = e.prev
+	} else {
+		e.next.prev = e.prev
+	}
+
+	e.prev = nil
+	e.next = nil
+	l.len--
+}
+
+func (l *List) insertBefore(e *Element, mark *Element) {
+	if mark.prev == nil {
+		// new front of the list
+		l.front = e
+	} else {
+		mark.prev.next = e
+	}
+	e.prev = mark.prev
+	mark.prev = e
+	e.next = mark
+	l.len++
+}
+
+func (l *List) insertAfter(e *Element, mark *Element) {
+	if mark.next == nil {
+		// new back of the list
+		l.back = e
+	} else {
+		mark.next.prev = e
+	}
+	e.next = mark.next
+	mark.next = e
+	e.prev = mark
+	l.len++
+}
+
+func (l *List) insertFront(e *Element) {
+	if l.front == nil {
+		// empty list
+		l.front, l.back = e, e
+		e.prev, e.next = nil, nil
+		l.len = 1
+		return
+	}
+	l.insertBefore(e, l.front)
+}
+
+func (l *List) insertBack(e *Element) {
+	if l.back == nil {
+		// empty list
+		l.front, l.back = e, e
+		e.prev, e.next = nil, nil
+		l.len = 1
+		return
+	}
+	l.insertAfter(e, l.back)
+}
+
+// PushFront inserts the value at the front of the list and returns a new Element containing the value.
+func (l *List) PushFront(value interface{}) *Element {
+	e := &Element{nil, nil, l, value}
+	l.insertFront(e)
+	return e
+}
+
+// PushBack inserts the value at the back of the list and returns a new Element containing the value.
+func (l *List) PushBack(value interface{}) *Element {
+	e := &Element{nil, nil, l, value}
+	l.insertBack(e)
+	return e
+}
+
+// InsertBefore inserts the value immediately before mark and returns a new Element containing the value.
+func (l *List) InsertBefore(value interface{}, mark *Element) *Element {
+	if mark.list != l {
+		return nil
+	}
+	e := &Element{nil, nil, l, value}
+	l.insertBefore(e, mark)
+	return e
+}
+
+// InsertAfter inserts the value immediately after mark and returns a new Element containing the value.
+func (l *List) InsertAfter(value interface{}, mark *Element) *Element {
+	if mark.list != l {
+		return nil
+	}
+	e := &Element{nil, nil, l, value}
+	l.insertAfter(e, mark)
+	return e
+}
+
+// MoveToFront moves the element to the front of the list.
+func (l *List) MoveToFront(e *Element) {
+	if e.list != l || l.front == e {
+		return
+	}
+	l.remove(e)
+	l.insertFront(e)
+}
+
+// MoveToBack moves the element to the back of the list.
+func (l *List) MoveToBack(e *Element) {
+	if e.list != l || l.back == e {
+		return
+	}
+	l.remove(e)
+	l.insertBack(e)
+}
+
+// Len returns the number of elements in the list.
+func (l *List) Len() int { return l.len }
+
+// PushBackList inserts each element of ol at the back of the list.
+func (l *List) PushBackList(ol *List) {
+	last := ol.Back()
+	for e := ol.Front(); e != nil; e = e.Next() {
+		l.PushBack(e.Value)
+		if e == last {
+			break
+		}
+	}
+}
+
+// PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved.
+func (l *List) PushFrontList(ol *List) {
+	first := ol.Front()
+	for e := ol.Back(); e != nil; e = e.Prev() {
+		l.PushFront(e.Value)
+		if e == first {
+			break
+		}
+	}
+}
diff --git a/libgo/go/container/list/list_test.go b/libgo/go/container/list/list_test.go
new file mode 100755
index 000000000..1d44ff84e
--- /dev/null
+++ b/libgo/go/container/list/list_test.go
@@ -0,0 +1,209 @@
+// 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 list
+
+import (
+	"testing"
+)
+
+func checkListPointers(t *testing.T, l *List, es []*Element) {
+	if len(es) == 0 {
+		if l.front != nil || l.back != nil {
+			t.Errorf("l.front/l.back = %v/%v should be nil/nil", l.front, l.back)
+		}
+		return
+	}
+
+	if l.front != es[0] {
+		t.Errorf("l.front = %v, want %v", l.front, es[0])
+	}
+	if last := es[len(es)-1]; l.back != last {
+		t.Errorf("l.back = %v, want %v", l.back, last)
+	}
+
+	for i, e := range es {
+		var e_prev, e_next *Element = nil, nil
+		if i > 0 {
+			e_prev = es[i-1]
+		}
+		if i < len(es)-1 {
+			e_next = es[i+1]
+		}
+		if e.prev != e_prev {
+			t.Errorf("elt #%d (%v) has prev=%v, want %v", i, e, e.prev, e_prev)
+		}
+		if e.next != e_next {
+			t.Errorf("elt #%d (%v) has next=%v, want %v", i, e, e.next, e_next)
+		}
+	}
+}
+
+func checkListLen(t *testing.T, l *List, n int) {
+	if an := l.Len(); an != n {
+		t.Errorf("l.Len() = %d, want %d", an, n)
+	}
+}
+
+func TestList(t *testing.T) {
+	l := New()
+	checkListPointers(t, l, []*Element{})
+	checkListLen(t, l, 0)
+
+	// Single element list
+	e := l.PushFront("a")
+	checkListLen(t, l, 1)
+	checkListPointers(t, l, []*Element{e})
+	l.MoveToFront(e)
+	checkListPointers(t, l, []*Element{e})
+	l.MoveToBack(e)
+	checkListPointers(t, l, []*Element{e})
+	checkListLen(t, l, 1)
+	l.Remove(e)
+	checkListPointers(t, l, []*Element{})
+	checkListLen(t, l, 0)
+
+	// Bigger list
+	e2 := l.PushFront(2)
+	e1 := l.PushFront(1)
+	e3 := l.PushBack(3)
+	e4 := l.PushBack("banana")
+	checkListPointers(t, l, []*Element{e1, e2, e3, e4})
+	checkListLen(t, l, 4)
+
+	l.Remove(e2)
+	checkListPointers(t, l, []*Element{e1, e3, e4})
+	checkListLen(t, l, 3)
+
+	l.MoveToFront(e3) // move from middle
+	checkListPointers(t, l, []*Element{e3, e1, e4})
+
+	l.MoveToFront(e1)
+	l.MoveToBack(e3) // move from middle
+	checkListPointers(t, l, []*Element{e1, e4, e3})
+
+	l.MoveToFront(e3) // move from back
+	checkListPointers(t, l, []*Element{e3, e1, e4})
+	l.MoveToFront(e3) // should be no-op
+	checkListPointers(t, l, []*Element{e3, e1, e4})
+
+	l.MoveToBack(e3) // move from front
+	checkListPointers(t, l, []*Element{e1, e4, e3})
+	l.MoveToBack(e3) // should be no-op
+	checkListPointers(t, l, []*Element{e1, e4, e3})
+
+	e2 = l.InsertBefore(2, e1) // insert before front
+	checkListPointers(t, l, []*Element{e2, e1, e4, e3})
+	l.Remove(e2)
+	e2 = l.InsertBefore(2, e4) // insert before middle
+	checkListPointers(t, l, []*Element{e1, e2, e4, e3})
+	l.Remove(e2)
+	e2 = l.InsertBefore(2, e3) // insert before back
+	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
+	l.Remove(e2)
+
+	e2 = l.InsertAfter(2, e1) // insert after front
+	checkListPointers(t, l, []*Element{e1, e2, e4, e3})
+	l.Remove(e2)
+	e2 = l.InsertAfter(2, e4) // insert after middle
+	checkListPointers(t, l, []*Element{e1, e4, e2, e3})
+	l.Remove(e2)
+	e2 = l.InsertAfter(2, e3) // insert after back
+	checkListPointers(t, l, []*Element{e1, e4, e3, e2})
+	l.Remove(e2)
+
+	// Check standard iteration.
+	sum := 0
+	for e := l.Front(); e != nil; e = e.Next() {
+		if i, ok := e.Value.(int); ok {
+			sum += i
+		}
+	}
+	if sum != 4 {
+		t.Errorf("sum over l.Iter() = %d, want 4", sum)
+	}
+
+	// Clear all elements by iterating
+	var next *Element
+	for e := l.Front(); e != nil; e = next {
+		next = e.Next()
+		l.Remove(e)
+	}
+	checkListPointers(t, l, []*Element{})
+	checkListLen(t, l, 0)
+}
+
+func checkList(t *testing.T, l *List, es []interface{}) {
+	if l.Len() != len(es) {
+		t.Errorf("list has len=%v, want %v", l.Len(), len(es))
+		return
+	}
+	i := 0
+	for e := l.Front(); e != nil; e = e.Next() {
+		le := e.Value.(int)
+		if le != es[i] {
+			t.Errorf("elt #%d has value=%v, want %v", i, le, es[i])
+		}
+		i++
+	}
+}
+
+func TestExtending(t *testing.T) {
+	l1 := New()
+	l2 := New()
+
+	l1.PushBack(1)
+	l1.PushBack(2)
+	l1.PushBack(3)
+
+	l2.PushBack(4)
+	l2.PushBack(5)
+
+	l3 := New()
+	l3.PushBackList(l1)
+	checkList(t, l3, []interface{}{1, 2, 3})
+	l3.PushBackList(l2)
+	checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
+
+	l3 = New()
+	l3.PushFrontList(l2)
+	checkList(t, l3, []interface{}{4, 5})
+	l3.PushFrontList(l1)
+	checkList(t, l3, []interface{}{1, 2, 3, 4, 5})
+
+	checkList(t, l1, []interface{}{1, 2, 3})
+	checkList(t, l2, []interface{}{4, 5})
+
+	l3 = New()
+	l3.PushBackList(l1)
+	checkList(t, l3, []interface{}{1, 2, 3})
+	l3.PushBackList(l3)
+	checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
+
+	l3 = New()
+	l3.PushFrontList(l1)
+	checkList(t, l3, []interface{}{1, 2, 3})
+	l3.PushFrontList(l3)
+	checkList(t, l3, []interface{}{1, 2, 3, 1, 2, 3})
+
+	l3 = New()
+	l1.PushBackList(l3)
+	checkList(t, l1, []interface{}{1, 2, 3})
+	l1.PushFrontList(l3)
+	checkList(t, l1, []interface{}{1, 2, 3})
+}
+
+func TestRemove(t *testing.T) {
+	l := New()
+	e1 := l.PushBack(1)
+	e2 := l.PushBack(2)
+	checkListPointers(t, l, []*Element{e1, e2})
+	e := l.Front()
+	l.Remove(e)
+	checkListPointers(t, l, []*Element{e2})
+	checkListLen(t, l, 1)
+	l.Remove(e)
+	checkListPointers(t, l, []*Element{e2})
+	checkListLen(t, l, 1)
+}
diff --git a/libgo/go/container/ring/ring.go b/libgo/go/container/ring/ring.go
new file mode 100644
index 000000000..335afbc3c
--- /dev/null
+++ b/libgo/go/container/ring/ring.go
@@ -0,0 +1,153 @@
+// 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.
+
+// The ring package implements operations on circular lists.
+package ring
+
+// A Ring is an element of a circular list, or ring.
+// Rings do not have a beginning or end; a pointer to any ring element
+// serves as reference to the entire ring. Empty rings are represented
+// as nil Ring pointers. The zero value for a Ring is a one-element
+// ring with a nil Value.
+//
+type Ring struct {
+	next, prev *Ring
+	Value      interface{} // for use by client; untouched by this library
+}
+
+
+func (r *Ring) init() *Ring {
+	r.next = r
+	r.prev = r
+	return r
+}
+
+
+// Next returns the next ring element. r must not be empty.
+func (r *Ring) Next() *Ring {
+	if r.next == nil {
+		return r.init()
+	}
+	return r.next
+}
+
+
+// Prev returns the previous ring element. r must not be empty.
+func (r *Ring) Prev() *Ring {
+	if r.next == nil {
+		return r.init()
+	}
+	return r.prev
+}
+
+
+// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
+// in the ring and returns that ring element. r must not be empty.
+//
+func (r *Ring) Move(n int) *Ring {
+	if r.next == nil {
+		return r.init()
+	}
+	switch {
+	case n < 0:
+		for ; n < 0; n++ {
+			r = r.prev
+		}
+	case n > 0:
+		for ; n > 0; n-- {
+			r = r.next
+		}
+	}
+	return r
+}
+
+
+// New creates a ring of n elements.
+func New(n int) *Ring {
+	if n <= 0 {
+		return nil
+	}
+	r := new(Ring)
+	p := r
+	for i := 1; i < n; i++ {
+		p.next = &Ring{prev: p}
+		p = p.next
+	}
+	p.next = r
+	r.prev = p
+	return r
+}
+
+
+// Link connects ring r with with ring s such that r.Next()
+// becomes s and returns the original value for r.Next().
+// r must not be empty.
+//
+// If r and s point to the same ring, linking
+// them removes the elements between r and s from the ring.
+// The removed elements form a subring and the result is a
+// reference to that subring (if no elements were removed,
+// the result is still the original value for r.Next(),
+// and not nil).
+//
+// If r and s point to different rings, linking
+// them creates a single ring with the elements of s inserted
+// after r. The result points to the element following the
+// last element of s after insertion.
+//
+func (r *Ring) Link(s *Ring) *Ring {
+	n := r.Next()
+	if s != nil {
+		p := s.Prev()
+		// Note: Cannot use multiple assignment because
+		// evaluation order of LHS is not specified.
+		r.next = s
+		s.prev = r
+		n.prev = p
+		p.next = n
+	}
+	return n
+}
+
+
+// Unlink removes n % r.Len() elements from the ring r, starting
+// at r.Next(). If n % r.Len() == 0, r remains unchanged.
+// The result is the removed subring. r must not be empty.
+//
+func (r *Ring) Unlink(n int) *Ring {
+	if n <= 0 {
+		return nil
+	}
+	return r.Link(r.Move(n + 1))
+}
+
+
+// Len computes the number of elements in ring r.
+// It executes in time proportional to the number of elements.
+//
+func (r *Ring) Len() int {
+	n := 0
+	if r != nil {
+		n = 1
+		for p := r.Next(); p != r; p = p.next {
+			n++
+		}
+	}
+	return n
+}
+
+
+func (r *Ring) Iter() <-chan interface{} {
+	c := make(chan interface{})
+	go func() {
+		if r != nil {
+			c <- r.Value
+			for p := r.Next(); p != r; p = p.next {
+				c <- p.Value
+			}
+		}
+		close(c)
+	}()
+	return c
+}
diff --git a/libgo/go/container/ring/ring_test.go b/libgo/go/container/ring/ring_test.go
new file mode 100644
index 000000000..ee3c41128
--- /dev/null
+++ b/libgo/go/container/ring/ring_test.go
@@ -0,0 +1,240 @@
+// 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 ring
+
+import (
+	"fmt"
+	"testing"
+)
+
+
+// For debugging - keep around.
+func dump(r *Ring) {
+	if r == nil {
+		fmt.Println("empty")
+		return
+	}
+	i, n := 0, r.Len()
+	for p := r; i < n; p = p.next {
+		fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next)
+		i++
+	}
+	fmt.Println()
+}
+
+
+func verify(t *testing.T, r *Ring, N int, sum int) {
+	// Len
+	n := r.Len()
+	if n != N {
+		t.Errorf("r.Len() == %d; expected %d", n, N)
+	}
+
+	// iteration
+	n = 0
+	s := 0
+	for p := range r.Iter() {
+		n++
+		if p != nil {
+			s += p.(int)
+		}
+	}
+	if n != N {
+		t.Errorf("number of forward iterations == %d; expected %d", n, N)
+	}
+	if sum >= 0 && s != sum {
+		t.Errorf("forward ring sum = %d; expected %d", s, sum)
+	}
+
+	if r == nil {
+		return
+	}
+
+	// connections
+	if r.next != nil {
+		var p *Ring // previous element
+		for q := r; p == nil || q != r; q = q.next {
+			if p != nil && p != q.prev {
+				t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev)
+			}
+			p = q
+		}
+		if p != r.prev {
+			t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev)
+		}
+	}
+
+	// Next, Prev
+	if r.Next() != r.next {
+		t.Errorf("r.Next() != r.next")
+	}
+	if r.Prev() != r.prev {
+		t.Errorf("r.Prev() != r.prev")
+	}
+
+	// Move
+	if r.Move(0) != r {
+		t.Errorf("r.Move(0) != r")
+	}
+	if r.Move(N) != r {
+		t.Errorf("r.Move(%d) != r", N)
+	}
+	if r.Move(-N) != r {
+		t.Errorf("r.Move(%d) != r", -N)
+	}
+	for i := 0; i < 10; i++ {
+		ni := N + i
+		mi := ni % N
+		if r.Move(ni) != r.Move(mi) {
+			t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi)
+		}
+		if r.Move(-ni) != r.Move(-mi) {
+			t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi)
+		}
+	}
+}
+
+
+func TestCornerCases(t *testing.T) {
+	var (
+		r0 *Ring
+		r1 Ring
+	)
+	// Basics
+	verify(t, r0, 0, 0)
+	verify(t, &r1, 1, 0)
+	// Insert
+	r1.Link(r0)
+	verify(t, r0, 0, 0)
+	verify(t, &r1, 1, 0)
+	// Insert
+	r1.Link(r0)
+	verify(t, r0, 0, 0)
+	verify(t, &r1, 1, 0)
+	// Unlink
+	r1.Unlink(0)
+	verify(t, &r1, 1, 0)
+}
+
+
+func makeN(n int) *Ring {
+	r := New(n)
+	for i := 1; i <= n; i++ {
+		r.Value = i
+		r = r.Next()
+	}
+	return r
+}
+
+
+func sum(r *Ring) int {
+	s := 0
+	for p := range r.Iter() {
+		s += p.(int)
+	}
+	return s
+}
+
+
+func sumN(n int) int { return (n*n + n) / 2 }
+
+
+func TestNew(t *testing.T) {
+	for i := 0; i < 10; i++ {
+		r := New(i)
+		verify(t, r, i, -1)
+	}
+	for i := 0; i < 10; i++ {
+		r := makeN(i)
+		verify(t, r, i, sumN(i))
+	}
+}
+
+
+func TestLink1(t *testing.T) {
+	r1a := makeN(1)
+	var r1b Ring
+	r2a := r1a.Link(&r1b)
+	verify(t, r2a, 2, 1)
+	if r2a != r1a {
+		t.Errorf("a) 2-element link failed")
+	}
+
+	r2b := r2a.Link(r2a.Next())
+	verify(t, r2b, 2, 1)
+	if r2b != r2a.Next() {
+		t.Errorf("b) 2-element link failed")
+	}
+
+	r1c := r2b.Link(r2b)
+	verify(t, r1c, 1, 1)
+	verify(t, r2b, 1, 0)
+}
+
+
+func TestLink2(t *testing.T) {
+	var r0 *Ring
+	r1a := &Ring{Value: 42}
+	r1b := &Ring{Value: 77}
+	r10 := makeN(10)
+
+	r1a.Link(r0)
+	verify(t, r1a, 1, 42)
+
+	r1a.Link(r1b)
+	verify(t, r1a, 2, 42+77)
+
+	r10.Link(r0)
+	verify(t, r10, 10, sumN(10))
+
+	r10.Link(r1a)
+	verify(t, r10, 12, sumN(10)+42+77)
+}
+
+
+func TestLink3(t *testing.T) {
+	var r Ring
+	n := 1
+	for i := 1; i < 100; i++ {
+		n += i
+		verify(t, r.Link(New(i)), n, -1)
+	}
+}
+
+
+func TestUnlink(t *testing.T) {
+	r10 := makeN(10)
+	s10 := r10.Move(6)
+
+	sum10 := sumN(10)
+
+	verify(t, r10, 10, sum10)
+	verify(t, s10, 10, sum10)
+
+	r0 := r10.Unlink(0)
+	verify(t, r0, 0, 0)
+
+	r1 := r10.Unlink(1)
+	verify(t, r1, 1, 2)
+	verify(t, r10, 9, sum10-2)
+
+	r9 := r10.Unlink(9)
+	verify(t, r9, 9, sum10-2)
+	verify(t, r10, 9, sum10-2)
+}
+
+
+func TestLinkUnlink(t *testing.T) {
+	for i := 1; i < 4; i++ {
+		ri := New(i)
+		for j := 0; j < i; j++ {
+			rj := ri.Unlink(j)
+			verify(t, rj, j, -1)
+			verify(t, ri, i-j, -1)
+			ri.Link(rj)
+			verify(t, ri, i, -1)
+		}
+	}
+}
diff --git a/libgo/go/container/vector/defs.go b/libgo/go/container/vector/defs.go
new file mode 100644
index 000000000..a2febb6de
--- /dev/null
+++ b/libgo/go/container/vector/defs.go
@@ -0,0 +1,51 @@
+// 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.
+
+// The vector package 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
new file mode 100644
index 000000000..5ad9e294b
--- /dev/null
+++ b/libgo/go/container/vector/intvector.go
@@ -0,0 +1,208 @@
+// 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
new file mode 100644
index 000000000..1e38a1982
--- /dev/null
+++ b/libgo/go/container/vector/intvector_test.go
@@ -0,0 +1,344 @@
+// 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
new file mode 100644
index 000000000..790d3749f
--- /dev/null
+++ b/libgo/go/container/vector/nogen_test.go
@@ -0,0 +1,76 @@
+// 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
new file mode 100644
index 000000000..d540ace05
--- /dev/null
+++ b/libgo/go/container/vector/numbers_test.go
@@ -0,0 +1,122 @@
+// 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) {
+	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) {
+	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) {
+	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
new file mode 100644
index 000000000..852685f5a
--- /dev/null
+++ b/libgo/go/container/vector/stringvector.go
@@ -0,0 +1,208 @@
+// 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
new file mode 100644
index 000000000..776ae26de
--- /dev/null
+++ b/libgo/go/container/vector/stringvector_test.go
@@ -0,0 +1,344 @@
+// 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
new file mode 100644
index 000000000..f43e4d23c
--- /dev/null
+++ b/libgo/go/container/vector/vector.go
@@ -0,0 +1,208 @@
+// 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
new file mode 100644
index 000000000..a9c4ceb55
--- /dev/null
+++ b/libgo/go/container/vector/vector_test.go
@@ -0,0 +1,344 @@
+// 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)
+		}
+	}
+}