mv src/lib to src/pkg

tests: all.bash passes, gobuild still works, godoc still works.

R=rsc
OCL=30096
CL=30102

5 files changed, 758 insertions, 0 deletions

diff --git a/src/pkg/container/vector/Makefile b/src/pkg/container/vector/Makefile
new file mode 100644
index 0000000000..20490549d3
--- /dev/null
+++ b/src/pkg/container/vector/Makefile
@@ -0,0 +1,69 @@
+# 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.
+
+# DO NOT EDIT.  Automatically generated by gobuild.
+# gobuild -m >Makefile
+
+D=/container/
+
+include $(GOROOT)/src/Make.$(GOARCH)
+AR=gopack
+
+default: packages
+
+clean:
+	rm -rf *.[$(OS)] *.a [$(OS)].out _obj
+
+test: packages
+	gotest
+
+coverage: packages
+	gotest
+	6cov -g `pwd` | grep -v '_test\.go:'
+
+%.$O: %.go
+	$(GC) -I_obj $*.go
+
+%.$O: %.c
+	$(CC) $*.c
+
+%.$O: %.s
+	$(AS) $*.s
+
+O1=\
+	vector.$O\
+
+O2=\
+	intvector.$O\
+	stringvector.$O\
+
+
+phases: a1 a2
+_obj$D/vector.a: phases
+
+a1: $(O1)
+	$(AR) grc _obj$D/vector.a vector.$O
+	rm -f $(O1)
+
+a2: $(O2)
+	$(AR) grc _obj$D/vector.a intvector.$O stringvector.$O
+	rm -f $(O2)
+
+
+newpkg: clean
+	mkdir -p _obj$D
+	$(AR) grc _obj$D/vector.a
+
+$(O1): newpkg
+$(O2): a1
+$(O3): a2
+
+nuke: clean
+	rm -f $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/vector.a
+
+packages: _obj$D/vector.a
+
+install: packages
+	test -d $(GOROOT)/pkg && mkdir -p $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D
+	cp _obj$D/vector.a $(GOROOT)/pkg/$(GOOS)_$(GOARCH)$D/vector.a
diff --git a/src/pkg/container/vector/intvector.go b/src/pkg/container/vector/intvector.go
new file mode 100644
index 0000000000..c3b62f256a
--- /dev/null
+++ b/src/pkg/container/vector/intvector.go
@@ -0,0 +1,118 @@
+// 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 "container/vector"
+
+// IntVector is a specialization of Vector that hides the wrapping of Elements around ints.
+type IntVector struct {
+	vector.Vector;
+}
+
+
+// Init initializes a new or resized vector.  The initial length may be <= 0 to
+// request a default length.  If initial_len is shorter than the current
+// length of the IntVector, trailing elements of the IntVector will be cleared.
+func (p *IntVector) Init(len int) *IntVector {
+	p.Vector.Init(len);
+	return p;
+}
+
+
+// NewIntVector returns an initialized new IntVector with length at least len.
+func NewIntVector(len int) *IntVector {
+	return new(IntVector).Init(len)
+}
+
+
+// At returns the i'th element of the vector.
+func (p *IntVector) At(i int) int {
+	return p.Vector.At(i).(int)
+}
+
+
+// Set sets the i'th element of the vector to value x.
+func (p *IntVector) Set(i int, x int) {
+	p.a[i] = x
+}
+
+
+// Last returns the element in the vector of highest index.
+func (p *IntVector) Last() int {
+	return p.Vector.Last().(int)
+}
+
+
+// Data returns all the elements as a slice.
+func (p *IntVector) Data() []int {
+	arr := make([]int, p.Len());
+	for i, v := range p.a {
+		arr[i] = v.(int)
+	}
+	return arr
+}
+
+
+// Insert inserts into the vector an element of value x before
+// the current element at index i.
+func (p *IntVector) Insert(i int, x int) {
+	p.Vector.Insert(i, x)
+}
+
+
+// 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) {
+	p.Vector.InsertVector(i, &x.Vector)
+}
+
+
+// Slice returns a new IntVector 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 {
+	return &IntVector{ *p.Vector.Slice(i, j) };
+}
+
+
+// Push appends x to the end of the vector.
+func (p *IntVector) Push(x int) {
+	p.Vector.Push(x)
+}
+
+
+// Pop deletes and returns the last element of the vector.
+func (p *IntVector) Pop() int {
+	return p.Vector.Pop().(int)
+}
+
+
+// AppendVector appends the entire IntVector x to the end of this vector.
+func (p *IntVector) AppendVector(x *IntVector) {
+	p.Vector.InsertVector(len(p.a), &x.Vector);
+}
+
+
+// SortInterface support
+// Less returns a boolean denoting whether the i'th element is less than the j'th element.
+func (p *IntVector) Less(i, j int) bool {
+	return p.At(i) < p.At(j)
+}
+
+
+// Iterate over all elements; driver for range
+func (p *IntVector) iterate(c chan int) {
+	for i, v := range p.a {
+		c <- v.(int)
+	}
+	close(c);
+}
+
+
+// Channel iterator for range.
+func (p *IntVector) Iter() chan int {
+	c := make(chan int);
+	go p.iterate(c);
+	return c;
+}
diff --git a/src/pkg/container/vector/stringvector.go b/src/pkg/container/vector/stringvector.go
new file mode 100644
index 0000000000..18ca11a3f3
--- /dev/null
+++ b/src/pkg/container/vector/stringvector.go
@@ -0,0 +1,118 @@
+// 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 "container/vector"
+
+// StringVector is a specialization of Vector that hides the wrapping of Elements around strings.
+type StringVector struct {
+	vector.Vector;
+}
+
+
+// Init initializes a new or resized vector.  The initial length may be <= 0 to
+// request a default length.  If initial_len is shorter than the current
+// length of the StringVector, trailing elements of the StringVector will be cleared.
+func (p *StringVector) Init(len int) *StringVector {
+	p.Vector.Init(len);
+	return p;
+}
+
+
+// NewStringVector returns an initialized new StringVector with length at least len.
+func NewStringVector(len int) *StringVector {
+	return new(StringVector).Init(len)
+}
+
+
+// At returns the i'th element of the vector.
+func (p *StringVector) At(i int) string {
+	return p.Vector.At(i).(string)
+}
+
+
+// Set sets the i'th element of the vector to value x.
+func (p *StringVector) Set(i int, x string) {
+	p.a[i] = x
+}
+
+
+// Last returns the element in the vector of highest index.
+func (p *StringVector) Last() string {
+	return p.Vector.Last().(string)
+}
+
+
+// Data returns all the elements as a slice.
+func (p *StringVector) Data() []string {
+	arr := make([]string, p.Len());
+	for i, v := range p.a {
+		arr[i] = v.(string)
+	}
+	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.Vector.Insert(i, x)
+}
+
+
+// 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) {
+	p.Vector.InsertVector(i, &x.Vector)
+}
+
+
+// Slice returns a new StringVector 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 {
+	return &StringVector{ *p.Vector.Slice(i, j) };
+}
+
+
+// Push appends x to the end of the vector.
+func (p *StringVector) Push(x string) {
+	p.Vector.Push(x)
+}
+
+
+// Pop deletes and returns the last element of the vector.
+func (p *StringVector) Pop() string {
+	return p.Vector.Pop().(string)
+}
+
+
+// AppendVector appends the entire StringVector x to the end of this vector.
+func (p *StringVector) AppendVector(x *StringVector) {
+	p.Vector.InsertVector(len(p.a), &x.Vector);
+}
+
+
+// SortInterface support
+// Less returns a boolean denoting whether the i'th element is less than the j'th element.
+func (p *StringVector) Less(i, j int) bool {
+	return p.At(i) < p.At(j)
+}
+
+
+// Iterate over all elements; driver for range
+func (p *StringVector) iterate(c chan string) {
+	for i, v := range p.a {
+		c <- v.(string)
+	}
+	close(c);
+}
+
+
+// Channel iterator for range.
+func (p *StringVector) Iter() chan string {
+	c := make(chan string);
+	go p.iterate(c);
+	return c;
+}
diff --git a/src/pkg/container/vector/vector.go b/src/pkg/container/vector/vector.go
new file mode 100644
index 0000000000..5b5cad21cd
--- /dev/null
+++ b/src/pkg/container/vector/vector.go
@@ -0,0 +1,244 @@
+// 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 an efficient container for managing
+// linear arrays of elements.  Unlike arrays, vectors can change size dynamically.
+package vector
+
+// Element is an empty-interface object representing the contents of
+// a cell in the vector.
+type Element interface {}
+
+
+// Vector is the container itself.
+type Vector struct {
+	a []Element
+}
+
+
+func copy(dst, src []Element) {
+	for i := 0; i < len(src); i++ {
+		dst[i] = src[i]
+	}
+}
+
+
+// Insert n elements at position i.
+func expand(a []Element, i, n int) []Element {
+	// 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
+		b := make([]Element, len1, capb);
+		copy(b, a);
+		a = b
+	}
+
+	// make a hole
+	for j := len0-1; j >= i ; j-- {
+		a[j+n] = a[j]
+	}
+	return a
+}
+
+
+// Init initializes a new or resized vector.  The initial_len may be <= 0 to
+// request a default length.  If initial_len is shorter than the current
+// length of the Vector, trailing elements of the Vector will be cleared.
+func (p *Vector) Init(initial_len int) *Vector {
+	a := p.a;
+
+	if cap(a) == 0 || cap(a) < initial_len {
+		n := 8;  // initial capacity
+		if initial_len > n {
+			n = initial_len
+		}
+		a = make([]Element, n);
+	} else {
+		// nil out entries
+		for j := len(a) - 1; j >= 0; j-- {
+			a[j] = nil
+		}
+	}
+
+	p.a = a[0 : initial_len];
+	return p
+}
+
+
+// New returns an initialized new Vector with length at least len.
+func New(len int) *Vector {
+	return new(Vector).Init(len)
+}
+
+
+// Len returns the number of elements in the vector.
+// Len is 0 if p == nil.
+func (p *Vector) Len() int {
+	if p == nil {
+		return 0;
+	}
+	return len(p.a)
+}
+
+
+// At returns the i'th element of the vector.
+func (p *Vector) At(i int) Element {
+	return p.a[i]
+}
+
+
+// Set sets the i'th element of the vector to value x.
+func (p *Vector) Set(i int, x Element) {
+	p.a[i] = x
+}
+
+
+// Last returns the element in the vector of highest index.
+func (p *Vector) Last() Element {
+	return p.a[len(p.a) - 1]
+}
+
+
+// Data returns all the elements as a slice.
+func (p *Vector) Data() []Element {
+	arr := make([]Element, p.Len());
+	for i, v := range p.a {
+		arr[i] = v
+	}
+	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 Element) {
+	p.a = expand(p.a, i, 1);
+	p.a[i] = x;
+}
+
+
+// Delete deletes the i'th element of the vector.  The gap is closed so the old
+// element at index i+1 has index i afterwards.
+func (p *Vector) Delete(i int) {
+	a := p.a;
+	n := len(a);
+
+	copy(a[i : n-1], a[i+1 : n]);
+	a[n-1] = nil;  // support GC, nil out entry
+	p.a = a[0 : n-1];
+}
+
+
+// InsertVector inserts into the vector the contents of the Vector
+// x such that the 0th element of x appears at index i after insertion.
+func (p *Vector) InsertVector(i int, x *Vector) {
+	p.a = expand(p.a, i, len(x.a));
+	copy(p.a[i : i + len(x.a)], x.a);
+}
+
+
+// Cut deletes elements i through j-1, inclusive.
+func (p *Vector) Cut(i, j int) {
+	a := p.a;
+	n := len(a);
+	m := n - (j - i);
+
+	copy(a[i : m], a[j : n]);
+	for k := m; k < n; k++ {
+		a[k] = nil  // support GC, nil out entries
+	}
+
+	p.a = a[0 : m];
+}
+
+
+// Slice returns a new Vector by slicing the old one to extract slice [i:j].
+// The elements are copied. The original vector is unchanged.
+func (p *Vector) Slice(i, j int) *Vector {
+	s := New(j - i);  // will fail in Init() if j < j
+	copy(s.a, p.a[i : j]);
+	return s;
+}
+
+
+// Do calls function f for each element of the vector, in order.
+// The function should not change the indexing of the vector underfoot.
+func (p *Vector) Do(f func(elem Element)) {
+	for i := 0; i < len(p.a); i++ {
+		f(p.a[i])	// not too safe if f changes the Vector
+	}
+}
+
+
+// Convenience wrappers
+
+// Push appends x to the end of the vector.
+func (p *Vector) Push(x Element) {
+	p.Insert(len(p.a), x)
+}
+
+
+// Pop deletes the last element of the vector.
+func (p *Vector) Pop() Element {
+	i := len(p.a) - 1;
+	x := p.a[i];
+	p.a[i] = nil;  // support GC, nil out entry
+	p.a = p.a[0 : i];
+	return x;
+}
+
+
+// AppendVector appends the entire Vector x to the end of this vector.
+func (p *Vector) AppendVector(x *Vector) {
+	p.InsertVector(len(p.a), x);
+}
+
+
+// Partial SortInterface support
+
+// LessInterface provides partial support of the SortInterface.
+type LessInterface interface {
+	Less(y Element) bool
+}
+
+
+// Less returns a boolean denoting whether the i'th element is less than the j'th element.
+func (p *Vector) Less(i, j int) bool {
+	return p.a[i].(LessInterface).Less(p.a[j])
+}
+
+
+// Swap exchanges the elements at indexes i and j.
+func (p *Vector) Swap(i, j int) {
+	a := p.a;
+	a[i], a[j] = a[j], a[i]
+}
+
+
+// Iterate over all elements; driver for range
+func (p *Vector) iterate(c chan Element) {
+	for i, v := range p.a {
+		c <- v
+	}
+	close(c);
+}
+
+
+// Channel iterator for range.
+func (p *Vector) Iter() chan Element {
+	c := make(chan Element);
+	go p.iterate(c);
+	return c;
+}
diff --git a/src/pkg/container/vector/vector_test.go b/src/pkg/container/vector/vector_test.go
new file mode 100644
index 0000000000..2a9819394c
--- /dev/null
+++ b/src/pkg/container/vector/vector_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 vector
+
+import "container/vector"
+import "testing"
+import "sort"
+import "fmt"
+
+
+func TestZeroLen(t *testing.T) {
+	var a *vector.Vector;
+	if a.Len() != 0 { t.Errorf("A) expected 0, got %d", a.Len()); }
+	a = vector.New(0);
+	if a.Len() != 0 { t.Errorf("B) expected 0, got %d", a.Len()); }
+}
+
+
+func TestInit(t *testing.T) {
+	var a vector.Vector;
+	if a.Init(0).Len() != 0 { t.Error("A") }
+	if a.Init(1).Len() != 1 { t.Error("B") }
+	if a.Init(10).Len() != 10 { t.Error("C") }
+}
+
+
+func TestNew(t *testing.T) {
+	if vector.New(0).Len() != 0 { t.Error("A") }
+	if vector.New(1).Len() != 1 { t.Error("B") }
+	if vector.New(10).Len() != 10 { t.Error("C") }
+}
+
+
+func val(i int) int {
+	return i*991 - 1234
+}
+
+
+func TestAccess(t *testing.T) {
+	const n = 100;
+	var a vector.Vector;
+	a.Init(n);
+	for i := 0; i < n; i++ {
+		a.Set(i, val(i));
+	}
+	for i := 0; i < n; i++ {
+		if a.At(i).(int) != val(i) { t.Error(i) }
+	}
+}
+
+
+func TestInsertDeleteClear(t *testing.T) {
+	const n = 100;
+	a := vector.New(0);
+
+	for i := 0; i < n; i++ {
+		if a.Len() != i { t.Errorf("A) wrong len %d (expected %d)", a.Len(), i) }
+		a.Insert(0, val(i));
+		if a.Last().(int) != val(0) { t.Error("B") }
+	}
+	for i := n-1; i >= 0; i-- {
+		if a.Last().(int) != val(0) { t.Error("C") }
+		if a.At(0).(int) != val(i) { t.Error("D") }
+		a.Delete(0);
+		if a.Len() != i { t.Errorf("E) wrong len %d (expected %d)", a.Len(), i) }
+	}
+
+	if a.Len() != 0 { t.Errorf("F) wrong len %d (expected 0)", a.Len()) }
+	for i := 0; i < n; i++ {
+		a.Push(val(i));
+		if a.Len() != i+1 { t.Errorf("G) wrong len %d (expected %d)", a.Len(), i+1) }
+		if a.Last().(int) != val(i) { t.Error("H") }
+	}
+	a.Init(0);
+	if a.Len() != 0 { t.Errorf("I wrong len %d (expected 0)", a.Len()) }
+
+	const m = 5;
+	for j := 0; j < m; j++ {
+		a.Push(j);
+		for i := 0; i < n; i++ {
+			x := val(i);
+			a.Push(x);
+			if a.Pop().(int) != x { t.Error("J") }
+			if a.Len() != j+1 { t.Errorf("K) wrong len %d (expected %d)", a.Len(), j+1) }
+		}
+	}
+	if a.Len() != m { t.Errorf("L) wrong len %d (expected %d)", a.Len(), m) }
+}
+
+
+func verify_slice(t *testing.T, x *vector.Vector, elt, i, j int) {
+	for k := i; k < j; k++ {
+		if x.At(k).(int) != elt {
+			t.Errorf("M) wrong [%d] element %d (expected %d)", k, x.At(k).(int), elt)
+		}
+	}
+
+	s := x.Slice(i, j);
+	for k, n := 0, j-i; k < n; k++ {
+		if s.At(k).(int) != elt {
+			t.Errorf("N) wrong [%d] element %d (expected %d)", k, x.At(k).(int), elt)
+		}
+	}
+}
+
+
+func verify_pattern(t *testing.T, x *vector.Vector, a, b, c int) {
+	n := a + b + c;
+	if x.Len() != n {
+		t.Errorf("O) wrong len %d (expected %d)", x.Len(), n)
+	}
+	verify_slice(t, x, 0, 0, a);
+	verify_slice(t, x, 1, a, a + b);
+	verify_slice(t, x, 0, a + b, n);
+}
+
+
+func make_vector(elt, len int) *vector.Vector {
+	x := vector.New(len);
+	for i := 0; i < len; i++ {
+		x.Set(i, 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);
+}
+
+
+// This also tests IntVector and StringVector
+func TestSorting(t *testing.T) {
+	const n = 100;
+
+	a := vector.NewIntVector(n);
+	for i := n-1; i >= 0; i-- {
+		a.Set(i, n-1-i);
+	}
+	if sort.IsSorted(a) { t.Error("int vector not sorted") }
+
+	b := vector.NewStringVector(n);
+	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 TestDo(t *testing.T) {
+	const n = 25;
+	const salt = 17;
+	a := vector.NewIntVector(n);
+	for i := 0; i < n; i++ {
+		a.Set(i, salt * i);
+	}
+	count := 0;
+	a.Do(
+		func(e vector.Element) {
+			i := e.(int);
+			if i != count*salt {
+				t.Error("value at", count, "should be", count*salt, "not", i)
+			}
+			count++;
+		}
+	);
+	if count != n {
+		t.Error("should visit", n, "values; did visit", count)
+	}
+}
+
+func TestIter(t *testing.T) {
+	const Len = 100;
+	x := vector.New(Len);
+	for i := 0; i < Len; i++ {
+		x.Set(i, i*i);
+	}
+	i := 0;
+	for v := range x.Iter() {
+		if v.(int) != i*i {
+			t.Error("Iter expected", i*i, "got", v.(int))
+		}
+		i++;
+	}
+	if i != Len {
+		t.Error("Iter stopped at", i, "not", Len)
+	}
+}