In this post I'm going to show a little experiment for combining iterators in Java.
A couple of week a ago I read an excellent blog entry by
Debasish Ghosh called
Infinite Streams using Java Closures. In it an implementation of the Infinite Stream concept is presented with the help of Java closures.
For this post I wanted to show something related to this but using the
Iterable/
Iterator interfaces instead of a custom stream object. What interest me the most is the operations applied to stream objects such as map or filter but on iterators. These and other operations are defined for the
IEnumerable/
IEnumerator interfaces in C# with the extension methods defined in
System.Linq.Enumerable.
Also, given the amount of discussion lately around Java closures I wanted to create this code using the Java closures prototype of the
BGGA closures proposal to learn about it.
What I want to have is the following operations on iterators:
import java.util.*;
public class IteratorUtils {
public static <X,V> Iterable<V> map({X=>V} f,Iterable<X> i) {
return new EachElementIterable<X,V>(i,f);
}
public static <X> Iterable<X> take(int count,Iterable<X> i) {
return new TakeIterable<X>(i,count);
}
public static <X> Iterable<X> filter({X=>boolean} pred,Iterable<X> i) {
return new FilterIterable<X>(i,pred);
}
public static <X> Iterable<X> flatten(Iterable<Iterable<X>> multiIterator) {
return new FlattenIterable<X>(multiIterator);
}
}
The
map operation takes a function and a iterator and generate another iterator with the function applied to each element. The
take operation generates an iterator for a number of elements on another iterator. The
filter operation takes a predicate and a iterator and returns another iterator with only the elements that applied to the predicate. The
flatten operation takes an iterator of iterators and returns a flattened sequence of values.
Heres the iterator for the
map operation:
import java.util.*;
public class EachElementIterable<T,J> implements Iterable<J>{
private Iterable<T> iterable;
private {T=>J} function;
public EachElementIterable(Iterable<T> iterable,{T=>J} function) {
this.iterable = iterable;
this.function = function;
}
public Iterator<J> iterator() {
return new EachElementIterator<T,J>(iterable.iterator(),function);
}
static class EachElementIterator<T,J> implements Iterator<J>{
private Iterator<T> iterator;
private {T=>J} function;
public EachElementIterator(Iterator<T> iterator,{T=>J} function) {
this.function = function;
this.iterator = iterator;
}
public J next() {
return function.invoke(iterator.next());
}
public boolean hasNext() {
return iterator.hasNext();
}
public void remove() {
}
}
}
The implementation is not as elegant as the one presented in the Infinite Stream
entry, but it can be used with anything implementing Iterable.
Heres the iterator for the take operation:
import java.util.*;
public class TakeIterable<T> implements Iterable<T> {
private int count;
private Iterable<T> iterable;
public TakeIterable(Iterable<T> iterable,int count) {
this.count = count;
this.iterable = iterable;
}
public Iterator<T> iterator() {
return new TakeIterator<T>(iterable.iterator(),count);
}
static class TakeIterator<T> implements Iterator<T> {
private Iterator<T> iterator;
private int count;
private int current;
public TakeIterator(Iterator<T> iterator,int count) {
this.count = count;
this.iterator = iterator;
this.current = 0;
}
public T next() {
if (current++ < count) {
return iterator.next();
} else{
return null;
}
}
public boolean hasNext() {
return iterator.hasNext() && current < count;
}
public void remove() {
}
}
}
Here's the implementation of the
filter iterator:
import java.util.*;
public class FilterIterable<T> implements Iterable<T> {
private Iterable<T> iterable;
private {T=>boolean} predicate;
public FilterIterable(Iterable<T> iterable,{T=>boolean} predicate) {
this.iterable = iterable;
this.predicate = predicate;
}
public Iterator<T> iterator() {
return new FilterIterator<T>(iterable.iterator(),predicate);
}
static class FilterIterator<T> implements Iterator<T> {
private Iterator<T> iterator;
private {T=>boolean} predicate;
private T currentValue;
boolean finished = false;
boolean nextConsumed = true;
public FilterIterator(Iterator<T> iterator,{T=>boolean} predicate) {
this.predicate = predicate;
this.iterator = iterator;
}
public boolean moveToNextValid() {
boolean found = false;
while(!found && iterator.hasNext()) {
T currentValue = iterator.next();
if(predicate.invoke(currentValue)) {
found = true;
this.currentValue = currentValue;
nextConsumed = false;
}
}
if(!found) {
finished = true;
}
return found;
}
public T next() {
if (!nextConsumed) {
nextConsumed = true;
return currentValue;
} else {
if (!finished) {
if(moveToNextValid()) {
nextConsumed = true;
return currentValue;
}
}
}
return null;
}
public boolean hasNext() {
return !finished &&
(!nextConsumed || moveToNextValid());
}
public void remove() {
}
}
}
And finally, here's the
flatten iterator:
public class FlattenIterable<T> implements Iterable<T> {
private Iterable<Iterable<T>> iterable;
public FlattenIterable(Iterable<Iterable<T>> iterable) {
this.iterable = iterable;
}
public Iterator<T> iterator() {
return new FlattenIterator<T>(iterable.iterator());
}
static class FlattenIterator<T> implements Iterator<T> {
private Iterator<Iterable<T>> iterator;
private Iterator<T> currentIterator;
public FlattenIterator(Iterator<Iterable<T>> iterator) {
this.iterator = iterator;
currentIterator = null;
}
public boolean hasNext() {
boolean hasNext = true;
if (currentIterator == null) {
if (iterator.hasNext()) {
currentIterator = iterator.next().iterator();
} else {
return false;
}
}
while(!currentIterator.hasNext() &&
iterator.hasNext()) {
currentIterator = iterator.next().iterator();
}
return currentIterator.hasNext();
}
public T next() {
return currentIterator.next();
}
public void remove() {
}
}
}
We can combine these wrapper iterators to create operators on iterators of any kind for example:
ArrayList<String> anArray = new ArrayList<String>();
anArray.add("foo");
anArray.add("goo");
anArray.add("zoo");
...
for(String s : map({String s => "<li>"+s+"</li>"},
filter({String s => !s.startsWith("g")},
anArray))) {
System.out.println(s);
}
This example prints the "foo" and "zoo" between <li> and </li> tags. Also here I'm using
Java static import to avoid writing
IteratorUtils in every operation call.
Returning to the infinite stream operations, for me the most interesting thing about these wrapper iterators is that an iterator with a large amout of elements could be manipulated without consuming all of its elements in each step. For example take the following iterator:
public class NumericSequence implements Iterable<Integer>,Iterator<Integer>{
private int value = 0;
public NumericSequence() {
}
public NumericSequence(int start) {
value = start;
}
public Iterator<Integer> iterator() {
return this;
}
public Integer next() {
return value++;
}
public boolean hasNext() {
return true;
}
public void remove() {
}
}
We can manipulate this iterator using the operations and wrappers defined above:
for(int i : take(5,
filter(
{Integer x => x % 2 != 0 },
map( {Integer x=>x*x},
new NumericSequence())))) {
System.out.println(i);
}
This program prints only 1,9,25,49 and 81.
For the final example I wanted to create a little snippet that prints a list of friendly pairs of numbers. A
Friendly Pair is a pair of numbers that share the common characteristic of having the same value as a result of the sum of all of its divisors divided by itself. Another nice definition of a Friendly number is presented
here.
First we define some utilities:
public class IntegerIteratorUtils {
public static int sum(Iterable<Integer> integerIterable) {
int result = 0;
for(Integer i : integerIterable) {
result += i.intValue();
}
return result;
}
public static Iterable<Integer> divisors(int number) {
return
IteratorUtils.filter(
{Integer x => x != 0 && number % x == 0 },
IteratorUtils.take(number+1,new NumericSequence()));
}
public static int divisorFunction(int number) {
return sum(divisors(number));
}
}
Having these functions we can now calculate the pairs:
int max = 1000;
for(Pair<Integer,Integer> p :
filter( {Pair<Integer,Integer> p =>
divisorFunction(p.first)/(double)p.first ==
divisorFunction(p.second)/(double)p.second },
flatten(
map(
{Integer x =>
map({Integer ix => new Pair<Integer,Integer>(x,ix)},
take(max,new NumericSequence(x+1)))},
take(max,
new NumericSequence(1)))))) {
System.out.println("("+p.first.toString()+", "+p.second.toString()+")");
}
This program prints:
(6, 28)
(6, 496)
(12, 234)
(28, 496)
(30, 140)
(40, 224)
(66, 308)
(78, 364)
(80, 200)
(84, 270)
....
Code for this example was created with the
closures prototype from 2007-11-30. Source can be found
here.
