/*
   Barrier.java
   
   Description:
     Barrier class. Stops threads that want to pass the
     barrier until a specific number of threads is at
     hold. Then the threads are released and can continue.
     Usable for syncronizing threads, build pipeline
     structures etc.

   Comments:
     Error checking can be greatly improved. Threads might
     have to wait forever if not enough threads want to pass
     the barrier. A robust system should have some kind of 
     timeout mechanism or other construct to deal with this.
     This is only a simple example.

   Author:     Moggen
   Homepage:   http://www.moggen.org/
   License:    Public Domain, use as you like

   Log:
      010926   First version
*/

import java.util.ArrayList;

public class Barrier {

   private static final int MODE_WAIT=1,MODE_RELEASE=2;
   private ArrayList barrierQueue;
   private ArrayList releaseQueue;
   private int mode;
   private int waitFor;

   // constructor: nthreads is the number of threads to wait for
   //  in this barrier instance
   public Barrier(int nthreads) {
      barrierQueue=new ArrayList();
      releaseQueue=new ArrayList();
      waitFor=nthreads;
      mode=MODE_WAIT;
   }
   
   // pass: Pass the barrier, wait if necessary
   public synchronized void pass() {
      Thread thread=Thread.currentThread();

      // If the barrier is releasing older threads, then we must wait for
      // that to complete before we can go on. Loop until mode is MODE_WAIT
      while(mode==MODE_RELEASE){
         // Wait until something happens. This will release the monitor on
         // the lock instance and let other threads call methods.
         try{
            this.wait();
         } catch(InterruptedException e) {} // Todo: better handling here
         // Thread woke up, the monitor is reclaimed and we are synchronized
         // again
      }

      // mode is always MODE_WAIT here

      // Is enough threads waiting in the queue (including this thread)?
      if(barrierQueue.size()==(waitFor-1)){
         // All right, enough threads in the trap
         // Swap places of the queues.
         ArrayList tmp;
         tmp=barrierQueue;
         barrierQueue=releaseQueue;
         releaseQueue=tmp;
         // barrierQueue is always empty here

         // Switch to MODE_RELEASE
         mode=MODE_RELEASE;

         // Signal all sleeping threads to wake up
         this.notifyAll();

         // No we must wait for the others to get out of
         // the barrier
         while(releaseQueue.size()>0){

            // Wait until something happens. This will release the monitor on
            // the lock instance and let other threads call methods.
            try{
               this.wait();
            } catch(InterruptedException e) {} // Todo: better handling here
            // Thread woke up, the monitor is reclaimed and we are synchronized
            // again
         }
         // All threads accounted for, releaseQueue is empty. Switch mode
         mode=MODE_WAIT;

         // Signal to any sleeping threads waiting for MODE_WAIT
         this.notifyAll();

         // We're done. waitFor-1 threads have passed, and now this will
         return;
      }

      // We must wait for more threads, add us to the queue
      barrierQueue.add(thread);

      // Sleep until mode changes    
      while(mode==MODE_WAIT){

         // Wait until something happens. This will release the monitor on
         // the lock instance and let other threads call methods.
         try{
            this.wait();
         } catch(InterruptedException e) {} // Todo: better handling here
         // Thread woke up, the monitor is reclaimed and we are synchronized
         // again
      }

      // mode is MODE_RELEASE, the last thread in into the barrier
      // has switched the queues, so remove us from releaseQueue
      // Note: lastIndexOf must be used, another thread might have
      //       removed itself and affected the index of our thread.
      releaseQueue.remove(releaseQueue.lastIndexOf(thread));

      // Are there any more threads still left to be released?
      if(releaseQueue.size()==0){
         // No.. all threads are released except for the last one in
         // That thread is waiting for the queue to empty so it can
         // change mode to MODE_WAIT and continue.

         this.notifyAll();	// Notify all including the last thread
      }

      // We're done!
   }
}