diff options
Diffstat (limited to 'src/lib/container/array')
| -rw-r--r-- | src/lib/container/array/Makefile | 63 | ||||
| -rw-r--r-- | src/lib/container/array/array.go | 186 | ||||
| -rw-r--r-- | src/lib/container/array/array_test.go | 172 | ||||
| -rw-r--r-- | src/lib/container/array/intarray.go | 68 |
4 files changed, 0 insertions, 489 deletions
diff --git a/src/lib/container/array/Makefile b/src/lib/container/array/Makefile deleted file mode 100644 index bf76c44eb..000000000 --- a/src/lib/container/array/Makefile +++ /dev/null @@ -1,63 +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. - -# DO NOT EDIT. Automatically generated by gobuild. -# gobuild -m >Makefile -O=6 -GC=$(O)g -CC=$(O)c -w -AS=$(O)a -AR=$(O)ar - -default: packages - -clean: - rm -f *.$O *.a $O.out - -test: packages - gotest - -coverage: packages - gotest - 6cov -g `pwd` | grep -v '_test\.go:' - -%.$O: %.go - $(GC) $*.go - -%.$O: %.c - $(CC) $*.c - -%.$O: %.s - $(AS) $*.s - -O1=\ - array.$O\ - -O2=\ - intarray.$O\ - -array.a: a1 a2 - -a1: $(O1) - $(AR) grc array.a array.$O - rm -f $(O1) - -a2: $(O2) - $(AR) grc array.a intarray.$O - rm -f $(O2) - -newpkg: clean - $(AR) grc array.a - -$(O1): newpkg -$(O2): a1 - -nuke: clean - rm -f $(GOROOT)/pkg/array.a - -packages: array.a - -install: packages - cp array.a $(GOROOT)/pkg/array.a - diff --git a/src/lib/container/array/array.go b/src/lib/container/array/array.go deleted file mode 100644 index 4b8f686cc..000000000 --- a/src/lib/container/array/array.go +++ /dev/null @@ -1,186 +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. - -// -// *** DEPRECATED PACKAGE - USE package vector INSTEAD *** -// - -package array - -type ( - Element interface {}; - Array 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 -} - - -func (p *Array) Init(initial_len int) *Array { - 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 -} - - -func New(len int) *Array { - return new(Array).Init(len) -} - - -func (p *Array) Len() int { - return len(p.a) -} - - -func (p *Array) At(i int) Element { - return p.a[i] -} - - -func (p *Array) Set(i int, x Element) { - p.a[i] = x -} - - -func (p *Array) Last() Element { - return p.a[len(p.a) - 1] -} - - -func (p *Array) Insert(i int, x Element) { - p.a = expand(p.a, i, 1); - p.a[i] = x; -} - - -func (p *Array) Delete(i int) Element { - a := p.a; - n := len(a); - - x := a[i]; - copy(a[i : n-1], a[i+1 : n]); - a[n-1] = nil; // support GC, nil out entry - p.a = a[0 : n-1]; - - return x -} - - -func (p *Array) InsertArray(i int, x *Array) { - p.a = expand(p.a, i, len(x.a)); - copy(p.a[i : i + len(x.a)], x.a); -} - - -func (p *Array) 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]; -} - - -func (p *Array) Slice(i, j int) *Array { - s := New(j - i); // will fail in Init() if j < j - copy(s.a, p.a[i : j]); - return s; -} - - -func (p *Array) Do(f func(elem Element)) { - for i := 0; i < len(p.a); i++ { - f(p.a[i]) // not too safe if f changes the Array - } -} - - -// Convenience wrappers - -func (p *Array) Push(x Element) { - p.Insert(len(p.a), x) -} - - -func (p *Array) Pop() Element { - return p.Delete(len(p.a) - 1) -} - - -func (p *Array) AppendArray(x *Array) { - p.InsertArray(len(p.a), x); -} - - -// Partial SortInterface support - -type LessInterface interface { - Less(y Element) bool -} - - -func (p *Array) Less(i, j int) bool { - return p.a[i].(LessInterface).Less(p.a[j]) -} - - -func (p *Array) Swap(i, j int) { - a := p.a; - a[i], a[j] = a[j], a[i] -} diff --git a/src/lib/container/array/array_test.go b/src/lib/container/array/array_test.go deleted file mode 100644 index 43ac702ab..000000000 --- a/src/lib/container/array/array_test.go +++ /dev/null @@ -1,172 +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 array - -import "array" -import "testing" -import "sort" - - -func TestInit(t *testing.T) { - var a array.Array; - 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 array.New(0).Len() != 0 { t.Error("A") } - if array.New(1).Len() != 1 { t.Error("B") } - if array.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 array.Array; - 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 := array.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.Delete(0).(int) != val(i) { t.Error("D") } - 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 *array.Array, 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 *array.Array, 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_array(elt, len int) *array.Array { - x := array.New(len); - for i := 0; i < len; i++ { - x.Set(i, elt); - } - return x; -} - - -func TestInsertArray(t *testing.T) { - // 1 - a := make_array(0, 0); - b := make_array(1, 10); - a.InsertArray(0, b); - verify_pattern(t, a, 0, 10, 0); - // 2 - a = make_array(0, 10); - b = make_array(1, 0); - a.InsertArray(5, b); - verify_pattern(t, a, 5, 0, 5); - // 3 - a = make_array(0, 10); - b = make_array(1, 3); - a.InsertArray(3, b); - verify_pattern(t, a, 3, 3, 7); - // 4 - a = make_array(0, 10); - b = make_array(1, 1000); - a.InsertArray(8, b); - verify_pattern(t, a, 8, 1000, 2); -} - -func TestSorting(t *testing.T) { - const n = 100; - a := array.NewIntArray(n); - for i := n-1; i >= 0; i-- { - a.Set(i, n-1-i); - } - if sort.IsSorted(a) { t.Error("not sorted") } -} - - -func TestDo(t *testing.T) { - const n = 25; - const salt = 17; - a := array.NewIntArray(n); - for i := 0; i < n; i++ { - a.Set(i, salt * i); - } - count := 0; - a.Do( - func(e array.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) - } -} diff --git a/src/lib/container/array/intarray.go b/src/lib/container/array/intarray.go deleted file mode 100644 index 5f9549cfe..000000000 --- a/src/lib/container/array/intarray.go +++ /dev/null @@ -1,68 +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. - -// -// *** DEPRECATED PACKAGE - USE package vector INSTEAD *** -// - -package array - -import "array" - -type IntArray struct { - // TODO do not export field - array.Array; -} - - -func (p *IntArray) Init(len int) *IntArray { - p.Array.Init(len); - return p; -} - - -func NewIntArray(len int) *IntArray { - return new(IntArray).Init(len) -} - - -func (p *IntArray) At(i int) int { - return p.Array.At(i).(int) -} - - -func (p *IntArray) Set(i int, x int) { - p.Array.Set(i, x) -} - - -func (p *IntArray) Last() int { - return p.Array.Last().(int) -} - - -func (p *IntArray) Insert(i int, x int) { - p.Array.Insert(i, x) -} - - -func (p *IntArray) Delete(i int) int { - return p.Array.Delete(i).(int) -} - - -func (p *IntArray) Push(x int) { - p.Array.Push(x) -} - - -func (p *IntArray) Pop() int { - return p.Array.Pop().(int) -} - - -// SortInterface support -func (p *IntArray) Less(i, j int) bool { - return p.At(i) < p.At(j) -} |