// 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
