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

7 files changed, 276 insertions, 6 deletions

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