Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Another useful iterator is the Generator, which takes a closure and offers up the stuff it yields as an iterator, without having to keep all of the generated data around in memory. (It's based loosely on Ruby 1.9's Generator, which was also the challenge in Ruby Quiz #66)

Code Block
//JAVA CODE CODE
import java.util.concurrent.*;
import java.lang.ref.*;
import groovy.lang.Closure;
import java.util.*;

public class Generator<T> implements Iterator<T>, Iterable<T>{
   Semaphore availSemaphore=new Semaphore(0);
   Semaphore emptySemaphore=new Semaphore(1);

   //the thread can push one value at at time into pushedValue
   T pushedValue=null;

   //pull value moves it from pushedValue to pulledValue
   //until it is released by next()
   T pulledValue=null;
   boolean hasPulledValue=false;

   Generator(Closure closure){
      new GeneratorThread<T>(this,closure).start();
   }

   private void pullValue(){
      availSemaphore.acquireUninterruptibly();
      pulledValue=pushedValue;
      pushedValue=null;
      hasPulledValue=true;
      emptySemaphore.release();
   }

   public boolean hasNext(){
      if (!hasPulledValue)
	 pullValue();
      return emptySemaphore.availablePermits() != 2;
   }

   public T next(){
      if (!hasNext())
	 throw new NoSuchElementException("Closure has no more values");
      T retval=pulledValue;
      hasPulledValue=false;
      return retval;
   }

   public void remove(){
      throw new UnsupportedOperationException(
	 "Remove is not supported on generators");
   }

   public Iterator<T> iterator(){
      return this;
   }
}

class GeneratorThread<T> extends Thread{
   WeakReference<Generator<T>> generatorRef;
   Closure closure;
   public GeneratorThread(Generator<T> generator, Closure cl){
      generatorRef=new WeakReference<Generator<T>>(generator);
      closure=cl;
   }

   public void run(){
      closure.call(new SaveClosure<T>(this));
      Generator generator=generatorRef.get();

      //NOTE: when the closure completes, pullValue() will block forever
      //waiting for more available data. This release() allows it to
      //get in one last time, and read a variable indicating that the
      //thread has died and isn't producing any more data. one final
      //pullValue() run will have emptySemaphore==1 and
      //availSemaphore==1, and it will make emptySemaphore==2 thus
      //indicating that the thread has died
      if (generator!=null){
	 generator.availSemaphore.release();
      }
      //NOTE: if the generator has been garbage collected, we don't care
      //about letting the generator pull a termination condition.
   }
}

class SaveClosure<T> extends Closure{
   WeakReference<Generator<T>> generatorRef;
   public SaveClosure(GeneratorThread<T> gt){
      super(gt,null);
      generatorRef=gt.generatorRef;
   }

   public void doCall(T value){
      Generator<T> generator=generatorRef.get();
      if (generator!=null){
	 generator.emptySemaphore.acquireUninterruptibly();
	 generator.pushedValue=value;
	 generator.availSemaphore.release();
      }else{
	 throw new GeneratorDisposedException();
      }
   }
}

/**
 * A GeneratorDisposedException is used to terminate the thread
 * that was generating values, once the Generator has been garbage
 * collected.
 */
class GeneratorDisposedException extends RuntimeException{
}

...

Code Block
//generates an infinite sequence of Fibonacci numbers numbers
def fibonacci(Closure yield){
     def a=0
    def b=1
    def temp temp
    while(true){
         yield(b)
        temp=a
        a=b
        b=a+temp temp
    } 
}
 
//find the first Fibonacci number that's evenly divisible by 20 20
println(new Generator(this.&fibonacci).find{ it % 20 == 0})
 
//BROKEN: the groovy runtime wants to run fibonacci to termination loading values into an array.
//this generates an out of memory error.
 this.&fibonacci.find{it % 20 == 0}

As the Groovy runtime implements this now, you would exhaust all available ram when converting the MethodClosure to an iterator, before find() was ever called. With a Generator, values are only generated on demand.

...