From bbbada7b269987c36526d5d29d1182b4b7c0d1d3 Mon Sep 17 00:00:00 2001 From: David Symonds Date: Tue, 20 Oct 2009 14:10:22 -0700 Subject: Move usr/dsymonds/iterable to src/pkg/exp/iterable. Remove remainder of usr/dsymonds. R=rsc,r APPROVED=r DELTA=685 (275 added, 409 deleted, 1 changed) OCL=35810 CL=35933 --- src/clean.bash | 2 +- src/pkg/Make.deps | 1 + src/pkg/Makefile | 1 + src/pkg/exp/iterable/Makefile | 11 +++ src/pkg/exp/iterable/iterable.go | 134 +++++++++++++++++++++++++++++++++ src/pkg/exp/iterable/iterable_test.go | 128 +++++++++++++++++++++++++++++++ src/run.bash | 5 -- usr/dsymonds/iterable/Makefile | 11 --- usr/dsymonds/iterable/iterable.go | 134 --------------------------------- usr/dsymonds/iterable/iterable_test.go | 128 ------------------------------- 10 files changed, 276 insertions(+), 279 deletions(-) create mode 100644 src/pkg/exp/iterable/Makefile create mode 100644 src/pkg/exp/iterable/iterable.go create mode 100644 src/pkg/exp/iterable/iterable_test.go delete mode 100644 usr/dsymonds/iterable/Makefile delete mode 100644 usr/dsymonds/iterable/iterable.go delete mode 100644 usr/dsymonds/iterable/iterable_test.go diff --git a/src/clean.bash b/src/clean.bash index 2bfc88f22..31cbdab86 100755 --- a/src/clean.bash +++ b/src/clean.bash @@ -7,7 +7,7 @@ rm -rf $GOROOT/pkg/${GOOS}_$GOARCH rm -f $GOROOT/lib/*.a for i in lib9 libbio libcgo libmach libregexp cmd pkg \ ../misc/cgo/gmp ../misc/cgo/stdio \ - ../usr/r/rpc ../usr/dsymonds/iterable \ + ../usr/r/rpc \ ../test/bench do( cd $i || exit 1 diff --git a/src/pkg/Make.deps b/src/pkg/Make.deps index 49862d2dc..9cd6ff34b 100644 --- a/src/pkg/Make.deps +++ b/src/pkg/Make.deps @@ -30,6 +30,7 @@ encoding/git85.install: bytes.install io.install os.install strconv.install exec.install: os.install strings.install exp/datafmt.install: bytes.install container/vector.install fmt.install go/scanner.install go/token.install io.install os.install reflect.install runtime.install strconv.install strings.install exp/eval.install: bignum.install fmt.install go/ast.install go/parser.install go/scanner.install go/token.install log.install os.install reflect.install runtime.install strconv.install strings.install +exp/iterable.install: container/vector.install expvar.install: bytes.install fmt.install http.install log.install strconv.install sync.install flag.install: fmt.install os.install strconv.install fmt.install: io.install os.install reflect.install strconv.install utf8.install diff --git a/src/pkg/Makefile b/src/pkg/Makefile index cd50bb92f..9da15b83a 100644 --- a/src/pkg/Makefile +++ b/src/pkg/Makefile @@ -44,6 +44,7 @@ DIRS=\ exec\ exp/datafmt\ exp/eval\ + exp/iterable\ expvar\ flag\ fmt\ diff --git a/src/pkg/exp/iterable/Makefile b/src/pkg/exp/iterable/Makefile new file mode 100644 index 000000000..18e9e8170 --- /dev/null +++ b/src/pkg/exp/iterable/Makefile @@ -0,0 +1,11 @@ +# 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. + +include $(GOROOT)/src/Make.$(GOARCH) + +TARG=exp/iterable +GOFILES=\ + iterable.go\ + +include $(GOROOT)/src/Make.pkg diff --git a/src/pkg/exp/iterable/iterable.go b/src/pkg/exp/iterable/iterable.go new file mode 100644 index 000000000..bdcce11d0 --- /dev/null +++ b/src/pkg/exp/iterable/iterable.go @@ -0,0 +1,134 @@ +// 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 iterable package provides several traversal and searching methods. +// It can be used on anything that satisfies the Iterable interface, +// including vector, though certain functions, such as Map, can also be used on +// something that would produce an infinite amount of data. +package iterable + +import "container/vector" + +type Iterable interface { + // Iter should return a fresh channel each time it is called. + Iter() <-chan interface {} +} + +func not(f func(interface {}) bool) (func(interface {}) bool) { + return func(e interface {}) bool { return !f(e) } +} + +// All tests whether f is true for every element of iter. +func All(iter Iterable, f func(interface {}) bool) bool { + for e := range iter.Iter() { + if !f(e) { + return false + } + } + return true +} + +// Any tests whether f is true for at least one element of iter. +func Any(iter Iterable, f func(interface {}) bool) bool { + return !All(iter, not(f)) +} + +// Data returns a slice containing the elements of iter. +func Data(iter Iterable) []interface {} { + vec := vector.New(0); + for e := range iter.Iter() { + vec.Push(e) + } + return vec.Data() +} + +// filteredIterable is a struct that implements Iterable with each element +// passed through a filter. +type filteredIterable struct { + it Iterable; + f func(interface {}) bool; +} + +func (f *filteredIterable) iterate(out chan<- interface {}) { + for e := range f.it.Iter() { + if f.f(e) { + out <- e + } + } + close(out) +} + +func (f *filteredIterable) Iter() <-chan interface {} { + ch := make(chan interface {}); + go f.iterate(ch); + return ch; +} + +// Filter returns an Iterable that returns the elements of iter that satisfy f. +func Filter(iter Iterable, f func(interface {}) bool) Iterable { + return &filteredIterable{ iter, f } +} + +// Find returns the first element of iter that satisfies f. +// Returns nil if no such element is found. +func Find(iter Iterable, f func(interface {}) bool) interface {} { + for e := range Filter(iter, f).Iter() { + return e + } + return nil +} + +// Injector is a type representing a function that takes two arguments, +// an accumulated value and an element, and returns the next accumulated value. +// See the Inject function. +type Injector func(interface {}, interface {}) interface{}; + +// Inject combines the elements of iter by repeatedly calling f with an +// accumulated value and each element in order. The starting accumulated value +// is initial, and after each call the accumulated value is set to the return +// value of f. For instance, to compute a sum: +// var arr IntArray = []int{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; +// sum := iterable.Inject(arr, 0, +// func(ax interface {}, x interface {}) interface {} { +// return ax.(int) + x.(int) }).(int) +func Inject(iter Iterable, initial interface {}, f Injector) interface {} { + acc := initial; + for e := range iter.Iter() { + acc = f(acc, e) + } + return acc +} + +// mappedIterable is a helper struct that implements Iterable, returned by Map. +type mappedIterable struct { + it Iterable; + f func(interface {}) interface {}; +} + +func (m *mappedIterable) iterate(out chan<- interface {}) { + for e := range m.it.Iter() { + out <- m.f(e) + } + close(out) +} + +func (m *mappedIterable) Iter() <-chan interface {} { + ch := make(chan interface {}); + go m.iterate(ch); + return ch +} + +// Map returns an Iterable that returns the result of applying f to each +// element of iter. +func Map(iter Iterable, f func(interface {}) interface {}) Iterable { + return &mappedIterable{ iter, f } +} + +// Partition(iter, f) returns Filter(iter, f) and Filter(iter, !f). +func Partition(iter Iterable, f func(interface {}) bool) (Iterable, Iterable) { + return Filter(iter, f), Filter(iter, not(f)) +} + +// TODO: +// - Zip diff --git a/src/pkg/exp/iterable/iterable_test.go b/src/pkg/exp/iterable/iterable_test.go new file mode 100644 index 000000000..28bdfb66f --- /dev/null +++ b/src/pkg/exp/iterable/iterable_test.go @@ -0,0 +1,128 @@ +// 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 iterable + +import ( + "testing"; +) + +type IntArray []int; + +func (arr IntArray) Iter() <-chan interface {} { + ch := make(chan interface {}); + go func() { + for _, x := range arr { + ch <- x + } + close(ch) + }(); + return ch +} + +var oneToFive = IntArray{ 1, 2, 3, 4, 5 }; + +func isNegative(n interface {}) bool { + return n.(int) < 0 +} +func isPositive(n interface {}) bool { + return n.(int) > 0 +} +func isAbove3(n interface {}) bool { + return n.(int) > 3 +} +func isEven(n interface {}) bool { + return n.(int) % 2 == 0 +} +func doubler(n interface {}) interface {} { + return n.(int) * 2 +} +func addOne(n interface {}) interface {} { + return n.(int) + 1 +} +func adder(acc interface {}, n interface {}) interface {} { + return acc.(int) + n.(int) +} + +// A stream of the natural numbers: 0, 1, 2, 3, ... +type integerStream struct {} +func (i integerStream) Iter() <-chan interface {} { + ch := make(chan interface {}); + go func() { + for i := 0; ; i++ { + ch <- i + } + }(); + return ch +} + +func TestAll(t *testing.T) { + if !All(oneToFive, isPositive) { + t.Error("All(oneToFive, isPositive) == false") + } + if All(oneToFive, isAbove3) { + t.Error("All(oneToFive, isAbove3) == true") + } +} + +func TestAny(t *testing.T) { + if Any(oneToFive, isNegative) { + t.Error("Any(oneToFive, isNegative) == true") + } + if !Any(oneToFive, isEven) { + t.Error("Any(oneToFive, isEven) == false") + } +} + +func assertArraysAreEqual(t *testing.T, res []interface {}, expected []int) { + if len(res) != len(expected) { + t.Errorf("len(res) = %v, want %v", len(res), len(expected)); + goto missing + } + for i := range res { + if v := res[i].(int); v != expected[i] { + t.Errorf("res[%v] = %v, want %v", i, v, expected[i]); + goto missing + } + } + return; +missing: + t.Errorf("res = %v\nwant %v", res, expected); +} + +func TestFilter(t *testing.T) { + ints := integerStream{}; + moreInts := Filter(ints, isAbove3).Iter(); + res := make([]interface {}, 3); + for i := 0; i < 3; i++ { + res[i] = <-moreInts; + } + assertArraysAreEqual(t, res, []int{ 4, 5, 6 }) +} + +func TestFind(t *testing.T) { + ints := integerStream{}; + first := Find(ints, isAbove3); + if first.(int) != 4 { + t.Errorf("Find(ints, isAbove3) = %v, want 4", first) + } +} + +func TestInject(t *testing.T) { + res := Inject(oneToFive, 0, adder); + if res.(int) != 15 { + t.Errorf("Inject(oneToFive, 0, adder) = %v, want 15", res) + } +} + +func TestMap(t *testing.T) { + res := Data(Map(Map(oneToFive, doubler), addOne)); + assertArraysAreEqual(t, res, []int{ 3, 5, 7, 9, 11 }) +} + +func TestPartition(t *testing.T) { + ti, fi := Partition(oneToFive, isEven); + assertArraysAreEqual(t, Data(ti), []int{ 2, 4 }); + assertArraysAreEqual(t, Data(fi), []int{ 1, 3, 5 }) +} diff --git a/src/run.bash b/src/run.bash index 619ba9b7d..d88ea7852 100755 --- a/src/run.bash +++ b/src/run.bash @@ -59,11 +59,6 @@ time make ./chanrun ) || exit $? -(xcd ../usr/dsymonds/iterable -make clean -time make test -) || exit $? - (xcd pkg/exp/ogle make clean time make ogle diff --git a/usr/dsymonds/iterable/Makefile b/usr/dsymonds/iterable/Makefile deleted file mode 100644 index 3485d0ee4..000000000 --- a/usr/dsymonds/iterable/Makefile +++ /dev/null @@ -1,11 +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. - -include $(GOROOT)/src/Make.$(GOARCH) - -TARG=iterable -GOFILES=\ - iterable.go\ - -include $(GOROOT)/src/Make.pkg diff --git a/usr/dsymonds/iterable/iterable.go b/usr/dsymonds/iterable/iterable.go deleted file mode 100644 index bdcce11d0..000000000 --- a/usr/dsymonds/iterable/iterable.go +++ /dev/null @@ -1,134 +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. - -// The iterable package provides several traversal and searching methods. -// It can be used on anything that satisfies the Iterable interface, -// including vector, though certain functions, such as Map, can also be used on -// something that would produce an infinite amount of data. -package iterable - -import "container/vector" - -type Iterable interface { - // Iter should return a fresh channel each time it is called. - Iter() <-chan interface {} -} - -func not(f func(interface {}) bool) (func(interface {}) bool) { - return func(e interface {}) bool { return !f(e) } -} - -// All tests whether f is true for every element of iter. -func All(iter Iterable, f func(interface {}) bool) bool { - for e := range iter.Iter() { - if !f(e) { - return false - } - } - return true -} - -// Any tests whether f is true for at least one element of iter. -func Any(iter Iterable, f func(interface {}) bool) bool { - return !All(iter, not(f)) -} - -// Data returns a slice containing the elements of iter. -func Data(iter Iterable) []interface {} { - vec := vector.New(0); - for e := range iter.Iter() { - vec.Push(e) - } - return vec.Data() -} - -// filteredIterable is a struct that implements Iterable with each element -// passed through a filter. -type filteredIterable struct { - it Iterable; - f func(interface {}) bool; -} - -func (f *filteredIterable) iterate(out chan<- interface {}) { - for e := range f.it.Iter() { - if f.f(e) { - out <- e - } - } - close(out) -} - -func (f *filteredIterable) Iter() <-chan interface {} { - ch := make(chan interface {}); - go f.iterate(ch); - return ch; -} - -// Filter returns an Iterable that returns the elements of iter that satisfy f. -func Filter(iter Iterable, f func(interface {}) bool) Iterable { - return &filteredIterable{ iter, f } -} - -// Find returns the first element of iter that satisfies f. -// Returns nil if no such element is found. -func Find(iter Iterable, f func(interface {}) bool) interface {} { - for e := range Filter(iter, f).Iter() { - return e - } - return nil -} - -// Injector is a type representing a function that takes two arguments, -// an accumulated value and an element, and returns the next accumulated value. -// See the Inject function. -type Injector func(interface {}, interface {}) interface{}; - -// Inject combines the elements of iter by repeatedly calling f with an -// accumulated value and each element in order. The starting accumulated value -// is initial, and after each call the accumulated value is set to the return -// value of f. For instance, to compute a sum: -// var arr IntArray = []int{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; -// sum := iterable.Inject(arr, 0, -// func(ax interface {}, x interface {}) interface {} { -// return ax.(int) + x.(int) }).(int) -func Inject(iter Iterable, initial interface {}, f Injector) interface {} { - acc := initial; - for e := range iter.Iter() { - acc = f(acc, e) - } - return acc -} - -// mappedIterable is a helper struct that implements Iterable, returned by Map. -type mappedIterable struct { - it Iterable; - f func(interface {}) interface {}; -} - -func (m *mappedIterable) iterate(out chan<- interface {}) { - for e := range m.it.Iter() { - out <- m.f(e) - } - close(out) -} - -func (m *mappedIterable) Iter() <-chan interface {} { - ch := make(chan interface {}); - go m.iterate(ch); - return ch -} - -// Map returns an Iterable that returns the result of applying f to each -// element of iter. -func Map(iter Iterable, f func(interface {}) interface {}) Iterable { - return &mappedIterable{ iter, f } -} - -// Partition(iter, f) returns Filter(iter, f) and Filter(iter, !f). -func Partition(iter Iterable, f func(interface {}) bool) (Iterable, Iterable) { - return Filter(iter, f), Filter(iter, not(f)) -} - -// TODO: -// - Zip diff --git a/usr/dsymonds/iterable/iterable_test.go b/usr/dsymonds/iterable/iterable_test.go deleted file mode 100644 index 28bdfb66f..000000000 --- a/usr/dsymonds/iterable/iterable_test.go +++ /dev/null @@ -1,128 +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 iterable - -import ( - "testing"; -) - -type IntArray []int; - -func (arr IntArray) Iter() <-chan interface {} { - ch := make(chan interface {}); - go func() { - for _, x := range arr { - ch <- x - } - close(ch) - }(); - return ch -} - -var oneToFive = IntArray{ 1, 2, 3, 4, 5 }; - -func isNegative(n interface {}) bool { - return n.(int) < 0 -} -func isPositive(n interface {}) bool { - return n.(int) > 0 -} -func isAbove3(n interface {}) bool { - return n.(int) > 3 -} -func isEven(n interface {}) bool { - return n.(int) % 2 == 0 -} -func doubler(n interface {}) interface {} { - return n.(int) * 2 -} -func addOne(n interface {}) interface {} { - return n.(int) + 1 -} -func adder(acc interface {}, n interface {}) interface {} { - return acc.(int) + n.(int) -} - -// A stream of the natural numbers: 0, 1, 2, 3, ... -type integerStream struct {} -func (i integerStream) Iter() <-chan interface {} { - ch := make(chan interface {}); - go func() { - for i := 0; ; i++ { - ch <- i - } - }(); - return ch -} - -func TestAll(t *testing.T) { - if !All(oneToFive, isPositive) { - t.Error("All(oneToFive, isPositive) == false") - } - if All(oneToFive, isAbove3) { - t.Error("All(oneToFive, isAbove3) == true") - } -} - -func TestAny(t *testing.T) { - if Any(oneToFive, isNegative) { - t.Error("Any(oneToFive, isNegative) == true") - } - if !Any(oneToFive, isEven) { - t.Error("Any(oneToFive, isEven) == false") - } -} - -func assertArraysAreEqual(t *testing.T, res []interface {}, expected []int) { - if len(res) != len(expected) { - t.Errorf("len(res) = %v, want %v", len(res), len(expected)); - goto missing - } - for i := range res { - if v := res[i].(int); v != expected[i] { - t.Errorf("res[%v] = %v, want %v", i, v, expected[i]); - goto missing - } - } - return; -missing: - t.Errorf("res = %v\nwant %v", res, expected); -} - -func TestFilter(t *testing.T) { - ints := integerStream{}; - moreInts := Filter(ints, isAbove3).Iter(); - res := make([]interface {}, 3); - for i := 0; i < 3; i++ { - res[i] = <-moreInts; - } - assertArraysAreEqual(t, res, []int{ 4, 5, 6 }) -} - -func TestFind(t *testing.T) { - ints := integerStream{}; - first := Find(ints, isAbove3); - if first.(int) != 4 { - t.Errorf("Find(ints, isAbove3) = %v, want 4", first) - } -} - -func TestInject(t *testing.T) { - res := Inject(oneToFive, 0, adder); - if res.(int) != 15 { - t.Errorf("Inject(oneToFive, 0, adder) = %v, want 15", res) - } -} - -func TestMap(t *testing.T) { - res := Data(Map(Map(oneToFive, doubler), addOne)); - assertArraysAreEqual(t, res, []int{ 3, 5, 7, 9, 11 }) -} - -func TestPartition(t *testing.T) { - ti, fi := Partition(oneToFive, isEven); - assertArraysAreEqual(t, Data(ti), []int{ 2, 4 }); - assertArraysAreEqual(t, Data(fi), []int{ 1, 3, 5 }) -} -- cgit v1.2.3