diff options
author | David Symonds <dsymonds@golang.org> | 2009-10-20 14:10:22 -0700 |
---|---|---|
committer | David Symonds <dsymonds@golang.org> | 2009-10-20 14:10:22 -0700 |
commit | bbbada7b269987c36526d5d29d1182b4b7c0d1d3 (patch) | |
tree | fdbfb5fe33fdc437fc9e930ac7202fff35760152 /src/pkg/exp | |
parent | 6d708b667f866254dfb27c85b009f0ff42b8b0cf (diff) | |
download | golang-bbbada7b269987c36526d5d29d1182b4b7c0d1d3.tar.gz |
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
Diffstat (limited to 'src/pkg/exp')
-rw-r--r-- | src/pkg/exp/iterable/Makefile | 11 | ||||
-rw-r--r-- | src/pkg/exp/iterable/iterable.go | 134 | ||||
-rw-r--r-- | src/pkg/exp/iterable/iterable_test.go | 128 |
3 files changed, 273 insertions, 0 deletions
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 }) +} |