Riven :: code brain :: dump

Java Continuations and Green Threads at native speeds

2010-11-30T23:29:00.014+01:00

Continuations, or green threads, are a concept mostly seen in scripting languages. Green threads are just like native threads, but you can run multiple of them on a single native thread. Java has no native support for continuations, so we have to transform (instrument) java bytecode with a library that saves localvars and the instruction pointer upon a GreenThread.yield(). Once the green thread is resumed, this information is used to rebuild the stacktrace, with all localvars intact.

The library used is: http://l33tlabs.org/Continuations/ written by Matthias Mann
His library depends on ASM3 to parse and construct the bytecode: http://asm.ow2.org/

Through the Java Instrumentation Agent that I wrote for the previously mentioned library, there is no need to transform your byteclass ahead of time. The java agent will take care of this at runtime.

java -javaagent:conti4.jar -cp ./your.jars your.MainClass

I wrote a wrapper around the continuation library, to lower the bar a bit. I hope the code pretty much speaks for itself, and if not, feel free to ask questions. For additional convenience, I added some demo code and its fascinating output at the bottom.

Enjoy!

import de.matthiasmann.continuations.Coroutine;
import de.matthiasmann.continuations.CoroutineProto;
import de.matthiasmann.continuations.SuspendExecution;
import de.matthiasmann.continuations.Coroutine.State;

/*
 * Created on Nov 30, 2010
 * 
 * @author Riven
 */

public abstract class GreenThread implements CoroutineProto
{
   public static final long EOF = -1L;

   private final Coroutine  coroutine;

   public GreenThread()
   {
      this.coroutine = new Coroutine(this);
   }

   private long doSleep;

   @Override
   // this is where you put your code
   public abstract void coExecute() throws SuspendExecution;

   long step()
   {
      coroutine.run();
      if (coroutine.getState() == State.FINISHED)
         return EOF;
      return this.doSleep;
   }

   public static void yield() throws SuspendExecution
   {
      GreenThread.sleep(0L);
   }

   public static void sleep(long ms) throws SuspendExecution
   {
      GreenThread thread = (GreenThread) Coroutine.getActiveCoroutine().getProto();

      thread.doSleep = Math.max(ms, 0L);

      Coroutine.yield();
   }
}



---------------------------------------------------------------------

import java.util.Comparator;
import java.util.PriorityQueue;

/*
 * Created on Nov 30, 2010
 * 
 * @author Riven
 */

public class GreenThreadQueue
{
   private final PriorityQueue queue;
   private final List          reschedule;

   public GreenThreadQueue()
   {
      this.queue = new PriorityQueue(16, new GreenThreadWakeupComparator());
      this.reschedule = new ArrayList();
   }

   public void start(GreenThread thread)
   {
      this.queue.add(new GreenThreadWakeup(thread, 0L));
   }

   public boolean tick(long now)
   {
      try
      {
         while (true)
         {
            GreenThreadWakeup wakeup = this.queue.peek();
            if (wakeup == null)
               return !this.reschedule.isEmpty(); // signal nothing more to do

            if (wakeup.timestamp > now)
               break;

            if (this.queue.poll() != wakeup)
               throw new IllegalStateException();

            long sleep = wakeup.thread.step();
            if (sleep == GreenThread.EOF)
               continue;

            wakeup.timestamp = now + sleep;
            this.reschedule.add(wakeup);
         }

         return true;
      }
      finally
      {
         for (GreenThreadWakeup wakeup : this.reschedule)
         {
            this.queue.add(wakeup);
         }
         this.reschedule.clear();
      }
   }

   static private class GreenThreadWakeup
   {
      public final GreenThread thread;
      public long              timestamp;

      public GreenThreadWakeup(GreenThread thread, long timestamp)
      {
         this.thread = thread;
         this.timestamp = timestamp;
      }
   }

   static class GreenThreadWakeupComparator implements Comparator
   {
      @Override
      public int compare(GreenThreadWakeup o1, GreenThreadWakeup o2)
      {
         int val = Long.signum(o1.timestamp - o2.timestamp);
         return (val == 0) ? 1 : val;
      }
   }
}

Demo code

GreenThreadQueue queue = new GreenThreadQueue();

      GreenThread thread1 = new GreenThread()
      {
         @Override
         public void coExecute() throws SuspendExecution
         {
            for (int i = 0; i < 3; i++)
            {
               System.out.println("a" + i);
               GreenThread.sleep(1500);
            }
         }
      };

      GreenThread thread2 = new GreenThread()
      {
         @Override
         public void coExecute() throws SuspendExecution
         {
            for (int i = 0; i < 4; i++)
            {
               System.out.println("b" + i);
               GreenThread.sleep(1300);
            }
         }
      };

      queue.start(thread1);
      queue.start(thread2);

      do
      {
         try { Thread.sleep(100); } catch(InterruptedException exc) { /* ignore */ }
      }
      while (queue.tick(System.currentTimeMillis()));
   }

Fancy output (from 1 thread)

a0
b0
b1
a1
b2
a2
b3

Lost four words... (pro nouns)

2010-11-24T23:42:00.092+01:00

It got cold while she called for juice from , not awaiting the tide and tied a tight knot. A scene never seen again, maybe missed due to the dew or mist on site by a dude with poor sight on one side. A phase etched on the edge of his face. Whether her patients had patience depended on the weather. So take a look at the sea and see: sow and pour it in a poor pore, with any luck, lock it. I'll weigh the way the rained isle was reigned. A pane hid me, then a pain hit me. During the war the witch wore a hat which was won by one bright bride. During the juring descent, she thought and fought the scent. Worn by the sun, I warn my son, as his eye tans tense, 'caus where regular wear hides hides, I knew a new gnu (its dead dad had that dept) that played ball, sipping a bowl for four hours, assuming it was ours, while the cued cheap cute sheep queued. Silence. Deaf by impending death. 'Hear here', she heard hurt. She waited, weighted by lead, led down the stairs by the wrath filled failed ref. Bye Susan, by all means, awe at the whirled world... Eight dodo's ate dough though.


cold/called
juice/
not/knot
tide/tight/tied
scene/seen
missed/mist
due/dew
site/side/sight
phase/face
etch/edge


whether/weather
patience/patients
suck it/socket
rained/reighed
thought/fought
eight/ate
dodo/though/dough
so/sow
luck/lock
sea/see
pour/pore/poor


war/wore
won/one
witch/which
bright/bride
worn/warn
sun/son
tans/tense
where/wear
knew/new/gnu
dead/dad/that/dept
descent/the scent


ball/bowl
for/four
hours/ours
cued/cute/queued
cheap/sheep
plug/plaque
deaf/death
hear/here
heard/hurt
waited/weighted


lead/led
wrath/ref
filled/failed
bye/by
all/awe
whirled/world
i'll/isle
way/weigh
pain/pane
hit/hid

Disclaimer: English is not my native language, so certain words might sound the same for me, while they are clearly distinct for you gays.

Calculate PerlinNoise faster with an optimization to grad()

2010-08-19T19:15:00.008+02:00

A simple optimization to the gradient function makes the noise function twice as fast.

PerlinNoise.grad()

inline float grad(int hash, float x, float y, float z)
   {  
 //float u = (h < 8) ? x : y;
 //float v = (h < 4) ? y : ((h == 12 || h == 14) ? x : z);
 //return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);

 switch(hash & 0xF)
 {
  case 0x0: return  x + y;
  case 0x1: return -x + y;
  case 0x2: return  x - y;
  case 0x3: return -x - y;
  case 0x4: return  x + z;
  case 0x5: return -x + z;
  case 0x6: return  x - z;
  case 0x7: return -x - z;
  case 0x8: return  y + z;
  case 0x9: return -y + z;
  case 0xA: return  y - z;
  case 0xB: return -y - z;
  case 0xC: return  y + x;
  case 0xD: return -y + z;
  case 0xE: return  y - x;
  case 0xF: return -y - z;
  default: return 0; // never happens
 }
   }

PerlinNoise.noise() (click code to expand)

int   perm[512];

   void initPerlinNoise()
   {
      int i, permutation[] = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145, 235, 249,
         14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180 };

      for (i = 0; i < 256; i++)
         perm[256 + i] = perm[i] = permutation[i];
   }


   inline float fade(float t)
   {
      return t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f);
   }

   inline float lerp(float t, float a, float b)
   {
      return a + t * (b - a);
   }

   inline float grad(int hash, float x, float y, float z)
   {  
 //float u = (h < 8) ? x : y;
 //float v = (h < 4) ? y : ((h == 12 || h == 14) ? x : z);
 //return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);

 switch(hash & 0xF)
 {
  case 0x0: return  x + y;
  case 0x1: return -x + y;
  case 0x2: return  x - y;
  case 0x3: return -x - y;
  case 0x4: return  x + x;
  case 0x5: return -x + x;
  case 0x6: return  x - x;
  case 0x7: return -x - x;
  case 0x8: return  y + x;
  case 0x9: return -y + x;
  case 0xA: return  y - x;
  case 0xB: return -y - x;
  case 0xC: return  y + z;
  case 0xD: return -y + x;
  case 0xE: return  y - x;
  case 0xF: return -y - z;
  default: return 0; // never happens
 }
   }

   static inline float __fastcall noise(float x, float y, float z)
   {
      jint ix,iy,iz,gx,gy,gz;
      jint a0,b0,aa,ab,ba,bb;

      float aa0,ab0,ba0,bb0;
      float aa1,ab1,ba1,bb1;
      float a1,a2,a3,a4,a5,a6,a7,a8;
      float u,v,w,a8_5,a4_1;

      ix = (jint)x; x-=ix;
      iy = (jint)y; y-=iy;
      iz = (jint)z; z-=iz;

      gx = ix & 0xFF;
      gy = iy & 0xFF;
      gz = iz & 0xFF;
      
      a0 = gy+perm[gx];
      b0 = gy+perm[gx + 1];
      aa = gz+perm[a0];
      ab = gz+perm[a0 + 1];
      ba = gz+perm[b0];
      bb = gz+perm[b0 + 1];

      aa0 = perm[aa]; aa1 = perm[aa + 1];
      ab0 = perm[ab]; ab1 = perm[ab + 1];
      ba0 = perm[ba]; ba1 = perm[ba + 1];
      bb0 = perm[bb]; bb1 = perm[bb + 1];

      a1 = grad(bb1, x-1, y-1, z-1);
      a2 = grad(ab1, x  , y-1, z-1);
      a3 = grad(ba1, x-1, y  , z-1);
      a4 = grad(aa1, x  , y  , z-1);
      a5 = grad(bb0, x-1, y-1, z  );
      a6 = grad(ab0, x  , y-1, z  );
      a7 = grad(ba0, x-1, y  , z  );
      a8 = grad(aa0, x  , y  , z  );

      u = fade(x);
      v = fade(y);
      w = fade(z);

      a8_5 = lerp(v, lerp(u, a8, a7), lerp(u, a6, a5));
      a4_1 = lerp(v, lerp(u, a4, a3), lerp(u, a2, a1));
      return lerp(w, a8_5, a4_1);
   }

Rhino ClassShutter replacement: SandboxShutter

2010-07-23T19:28:00.021+02:00

Because the ClassShutter in Rhino doesn't usually provide enough information to make decisions on whether or not certain Java objects, fields or methods should be accessible, I wrote the SandboxShutter which will enable you to control accessibility for each field and each method of each Java object. The performance impact is negligible, because JavaScript itself is an order of magnitude slower than the injected checks.

The SandboxShutter interface:

public interface SandboxShutter
{
   public boolean allowClassAccess(Class<?> type);

   public boolean allowFieldAccess(Class<?> type, Object instance, String fieldName);

   public boolean allowMethodAccess(Class<?> type, Object instance, String methodName);

   public boolean allowStaticFieldAccess(Class<?> type, String fieldName);

   public boolean allowStaticMethodAccess(Class<?> type, String methodName);
}

When the following javascript code is executed:

importPackage(Packages.my.game); // assuming the Java class my.game.Player exists

var player = new Player("Jake");
player.gender = "female"; // this is a Java method!
player.setGender("male"); // this the same Java method.
player.age = 18; // this is a Java field
player.age += 3;

var player = new Player("Jane");
player.gender = "male";
player.gender = "female";
player.age = 19;
player.age += 2;

var count = Player.PLAYER_COUNT;
Player.PLAYER_COUNT += 2;

The following SandboxShutter calls will be made:

allowClassAccess:       my.game.Player

allowMethodAccess:      my.game.Player.setGender() instance=Player@2346
allowFieldAccess:       my.game.Player.age         instance=Player@2346

allowMethodAccess:      my.game.Player.setGender() instance=Player@54326
allowFieldAccess:       my.game.Player.age         instance=Player@54326

allowStaticFieldAccess: my.game.Player.PLAYER_COUNT

As shown, there will be at most one call for each field/method in each object, and one call per class. This allows you to control accessibility per Java object.

Create the SandboxContextFactory:

   public static class SandboxContextFactory extends ContextFactory
   {
      final SandboxShutter shutter;

      public SandboxContextFactory(SandboxShutter shutter)
      {
         this.shutter = shutter;
      }

      @Override
      protected Context makeContext()
      {
         Context cx = super.makeContext();
         cx.setWrapFactory(new SandboxWrapFactory());
         cx.setClassShutter(new ClassShutter()
         {
            private final Map<String, Boolean> nameToAccepted = new HashMap<String, Boolean>();

            @Override
            public boolean visibleToScripts(String name)
            {
               Boolean granted = this.nameToAccepted.get(name);

               if (granted != null)
               {
                  return granted.booleanValue();
               }

               Class< ? > staticType;
               try
               {
                  staticType = Class.forName(name);
               }
               catch (Exception exc)
               {
                  this.nameToAccepted.put(name, Boolean.FALSE);
                  return false;
               }

               boolean grant = shutter.allowClassAccess(staticType);
               this.nameToAccepted.put(name, Boolean.valueOf(grant));
               return grant;
            }
         });
         return cx;
      }

      class SandboxWrapFactory extends WrapFactory
      {
         @Override
         public Scriptable wrapNewObject(Context cx, Scriptable scope, Object obj)
         {
            this.ensureReplacedClass(scope, obj, null);

            return super.wrapNewObject(cx, scope, obj);
         }

         @Override
         public Object wrap(Context cx, Scriptable scope, Object obj, Class< ? > staticType)
         {
            this.ensureReplacedClass(scope, obj, staticType);

            return super.wrap(cx, scope, obj, staticType);
         }

         @Override
         public Scriptable wrapAsJavaObject(Context cx, Scriptable scope, Object javaObject, Class< ? > staticType)
         {
            final Class< ? > type = this.ensureReplacedClass(scope, javaObject, staticType);

            return new NativeJavaObject(scope, javaObject, staticType)
            {
               private final Map<String, Boolean> instanceMethodToAllowed = new HashMap<String, Boolean>();

               @Override
               public Object get(String name, Scriptable scope)
               {
                  Object wrapped = super.get(name, scope);

                  if (wrapped instanceof BaseFunction)
                  {
                     String id = type.getName() + "." + name;
                     Boolean allowed = this.instanceMethodToAllowed.get(id);

                     if (allowed == null)
                     {
                        boolean allow = shutter.allowMethodAccess(type, javaObject, name);
                        this.instanceMethodToAllowed.put(id, allowed = Boolean.valueOf(allow));
                     }

                     if (!allowed.booleanValue())
                     {
                        return NOT_FOUND;
                     }
                  }
                  else
                  {
                     // NativeJavaObject + only boxed primitive types?
                     if (!shutter.allowFieldAccess(type, javaObject, name))
                     {
                        return NOT_FOUND;
                     }
                  }

                  return wrapped;
               }
            };
         }

         //

         private final Set<Class< ? >> replacedClasses = new HashSet<Class< ? >>();

         private Class< ? > ensureReplacedClass(Scriptable scope, Object obj, Class< ? > staticType)
         {
            final Class< ? > type = (staticType == null && obj != null) ? obj.getClass() : staticType;

            if (!type.isPrimitive() && !type.getName().startsWith("java.") && this.replacedClasses.add(type))
            {
               this.replaceJavaNativeClass(type, scope);
            }

            return type;
         }

         private void replaceJavaNativeClass(final Class< ? > type, Scriptable scope)
         {
            Object clazz = Context.jsToJava(ScriptableObject.getProperty(scope, "Packages"), Object.class);
            Object holder = null;
            for (String part : Text.split(type.getName(), '.'))
            {
               holder = clazz;
               clazz = ScriptableObject.getProperty((Scriptable) clazz, part);
            }
            NativeJavaClass nativeClass = (NativeJavaClass) clazz;

            nativeClass = new NativeJavaClass(scope, type)
            {
               @Override
               public Object get(String name, Scriptable start)
               {
                  Object wrapped = super.get(name, start);

                  if (wrapped instanceof BaseFunction)
                  {
                     if (!shutter.allowStaticMethodAccess(type, name))
                     {
                        return NOT_FOUND;
                     }
                  }
                  else
                  {
                     // NativeJavaObject + only boxed primitive types?
                     if (!shutter.allowStaticFieldAccess(type, name))
                     {
                        return NOT_FOUND;
                     }
                  }

                  return wrapped;
               }
            };

            ScriptableObject.putProperty((Scriptable) holder, type.getSimpleName(), nativeClass);
            ScriptableObject.putProperty(scope, type.getSimpleName(), nativeClass);
         }
      }
   }

Install the (global) SandboxContextFactory:

      ContextFactory.initGlobal(new SandboxContextFactory(new SandboxShutter()
      {
         ...
      }));

      // create and initialize Rhino Context
      Context cx = Context.enter();
      Scriptable prototype = cx.initStandardObjects();
      Scriptable topLevel = new ImporterTopLevel(cx);
      prototype.setParentScope(topLevel);
      Scriptable scope = cx.newObject(prototype);
      scope.setPrototype(prototype);

      // your scripts

Functions on Iterables :: Consume

2010-07-20T19:58:00.004+02:00

public class Functional
{
   /**
    * Consumes (removes) all items while iterating
    */

   public static <T> Iterable<T> consume(final Iterable<T> iterable)
   {
      if (iterable == null)
         throw new NullPointerException();

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public T next()
               {
                  T result = iterator.next();
                  iterator.remove();
                  return result;
               }

               @Override
               public void remove()
               {
                  throw new NoSuchElementException("already removed");
               }
            };
         }
      };
   }

To remove all short texts in a list:

List<String> data = ...;

Filter<String> shortText = new Filter<String>()
{
   public boolean accept(String item) { return item == null || item.length() <= 3; }
}

for(String item: consume(filter(data, shortText)))
{
   System.out.println("By the time you see this, '"+item+"' has been removed.");
}

Functions on Iterables :: Event Hooks

2010-07-20T19:35:00.008+02:00

public interface Operator
{
   public void operate(T item);
}

public class Functional
{
   /**
    * Performs a callback on each element-visit, and each element removal
    */

    public static <T> Iterable<T> eventHook(final Iterable<T> iterable,
                                            final Operator<T> onVisit,
                                            final Operator<T> onRemove)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (onVisit == null && onRemove == null)
         throw new NullPointerException("must specify either onVisit, onRemove or both");

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public T next()
               {
                  this.current = iterator.next();
                  if (onVisit != null)
                     onVisit.operate(this.current);
                  return this.current;
               }

               @Override
               public void remove()
               {
                  iterator.remove();
                  if (onRemove != null)
                     onRemove.operate(this.current);
               }

               //

               private T current;
            };
         }
      };
   }
}

Example:

Operator<String> onVisit= new Operator<String>()
{
   public void operate(String text)
   {
      System.out.println("visited: "+text);
   }
};

Operator<String> onRemove= new Operator<String>()
{
   public void operate(String text)
   {
      System.out.println("removed: "+text);
   }
};

Iterable<String> data = ...;

for(String item: eventHook(data, onVisit, onRemove))
{
   if(item.length() > String.valueOf(Math.PI))
      System.out.println("this text is longer than PI!");
}

Once you created an Iterable (say, a filtered view on a List) you can iterate over it as often as you want. No need to create a new Iterable.

With the support for closures in Java 7 a lot of the boilerplate code will disappear.

Functions on Iterables :: Transformer

2010-07-20T19:31:00.007+02:00

public interface Transformer<I, O>
{
   public O transform(I item);
}

public class Functional
{
   /**
    * Transforms Iterable<I> into Iterable<O> using a Transformer<I, O>
    */

   public static <I, O> Iterable<O> transform(final Iterable<I> iterable,
                                              final Transformer<I, O> transformer)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (transformer == null)
         throw new NullPointerException();

      return new Iterable<O>()
      {
         @Override
         public Iterator<O> iterator()
         {
            final Iterator<I> iterator = iterable.iterator();

            return new Iterator<O>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public O next()
               {
                  return transformer.transform(iterator.next());
               }

               @Override
               public void remove()
               {
                  iterator.remove();
               }
            };
         }
      };
   }
}

Example:

Transformer<String, Integer> textToNumber = new Transformer<String, Integer>()
{
   public Integer transform(String text)
   {
      return Integer.valueOf(text);
   }
};

Iterable<String> data = ...;

for(Integer number: transform(data, textToNumber))
{
   System.out.println("number: "+number.intValue());
}

Functions on Iterables :: Filter

2010-07-20T19:24:00.002+02:00

Functional programming has its strengths when iterating over data. If you want a view on a subset data, you can make a filter, and iterate over your data only seeing the elements that the filter accepted:

public interface Filter<T>
{
   public boolean accept(T value);
}

public class Functional
{
   /**
    * Filter items from the view of the returned Iterable<T>
    */

   public static <T> Iterable<T> filter(final Iterable<T> iterable, final Filter<T> filter)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (filter == null)
         throw new NullPointerException();

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  this.ensureReady();
                  return this.ready;
               }

               @Override
               public T next()
               {
                  this.ensureReady();
                  if (!this.ready)
                     throw new NoSuchElementException();

                  T result = this.current;
                  this.ready = false;
                  this.current = null;
                  return result;
               }

               @Override
               public void remove()
               {
                  iterator.remove();
               }

               //

               private boolean ready = false;
               private T       current;

               private void ensureReady()
               {
                  while (!this.ready && iterator.hasNext())
                  {
                     T item = iterator.next();
                     if (!filter.accept(item))
                        continue;

                     this.ready = true;
                     this.current = item;
                  }
               }
            };
         }
      };
   }
}

Example:

Filter<String> nonNull = new Filter<String>()
{
   public boolean accept(String value)
   {
      return value != null;
   }
};

Iterable<String> data = ...;

for(String item: filter(data, nonNull))
{
   System.out.println("item: "+item); // guaranteed not to be null
}

Histogram :: array based

2010-04-29T11:10:00.006+02:00

For any reasonably sized Histogram, you probably want to look at this Histogram class based on a HashMap. However, if your histograms are tiny, say, less than 8 elements occur frequently, this array based histogram is an order of magnitude faster.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

public class TinyHistogram<T>
{
   private T[]   items;
   private int[] usage;
   private int   size;

   public TinyHistogram()
   {
      this.items = (T[]) new Object[4];
      this.usage = new int[4];
      this.size = 0;
   }

   public int put(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);

      if (io != -1)
      {
         int result = ++this.usage[io];
         this.swapIncreasedValue(io);
         return result;
      }

      // add item to the end
      if (this.size == this.items.length)
         this.grow();
      this.items[this.size] = item;
      this.usage[this.size] = 1;
      this.size += 1;
      return 1;
   }

   public int get(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);
      if (io == -1)
         return 0; // not -1, as the object occurred zero times
      return this.usage[io];
   }

   public List<T> topKeys()
   {
      return this.topKeys(Integer.MAX_VALUE);
   }

   public List<T> topKeys(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<T> tops = new ArrayList<T>();
      for (int i = 0; i < end; i++)
         tops.add(this.items[i]);
      return tops;
   }

   public List<Pair<T, Integer>> topEntries()
   {
      return this.topEntries(Integer.MAX_VALUE);
   }

   public List<Pair<T, Integer>> topEntries(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<Pair<T, Integer>> tops = new ArrayList<Pair<T, Integer>>();
      for (int i = 0; i < end; i++)
         tops.add(new Pair<T, Integer>(this.items[i], Integer.valueOf(this.usage[i])));
      return tops;
   }

   public int remove(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));

      int result = --this.usage[io];
      if (result == 0)
         return this.removeIndex(io);

      this.swapDecreasedValue(io);
      return result;
   }

   public int reset(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));
      return this.removeIndex(io);
   }

   //

   private final void swapDecreasedValue(int index)
   {
      while ((index + 1) < size && usage[index + 0] < usage[index + 1])
      {
         int a = index + 0;
         int b = index + 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index++;
      }
   }

   private final void swapIncreasedValue(int index)
   {
      while (index > 0 && usage[index + 0] > usage[index - 1])
      {
         int a = index - 0;
         int b = index - 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index--;
      }
   }

   private static final void swapInt(int[] array, int a, int b)
   {
      int temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private static final void swapObj(Object[] array, int a, int b)
   {
      Object temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private void grow()
   {
      this.items = Arrays.copyOf(this.items, this.items.length * 2);
      this.usage = Arrays.copyOf(this.usage, this.usage.length * 2);
   }

   private int removeIndex(int index)
   {
      int count = this.usage[index];
      int shift = --this.size - index;
      System.arraycopy(this.items, index + 1, this.items, index, shift);
      System.arraycopy(this.usage, index + 1, this.usage, index, shift);
      return count;
   }

   private int indexOfItem(T item)
   {
      for (int i = 0; i < this.size; i++)
         if (this.items[i] == item || this.items[i].equals(item))
            return i;
      return -1;
   }
}

Slicing direct buffers to workaround 4K overhead

2010-04-29T10:58:00.001+02:00

Direct ByteBuffers can have an unexpected massive overhead. For every allocation, a number of bytes equal to the system pagesize (typically 4K) is added. The reason for this is that MappedByteBuffers must be page-aligned. The code used behind the scenes in ByteBuffer.allocateDirect(int size) looks a little something like this:

private static ByteBuffer malloc(int size)
{
   int pageSize = unsafe.getPageSize(); // typically 4096
   long pointer = sun.misc.Unsafe.malloc(size + pageSize);
   long base = (pointer + (pageSize-1)) / pageSize * pageSize;
   ByteBuffer buffer = unsafe.createBufferAt(base);
   return buffer;
}

Code like this will have a massive overhead:

for(int i=0; i<count; i++)
   buffers[i] = ByteBuffer.allocateDirect(64);

Instead use an approach like below:

public class DirectBufferProvider
{
   private static final int ALLOCATION_SIZE = 1024*1024;

   private ByteBuffer currentBuffer = null;

   public ByteBuffer allocate(int size)
   {
      if(size >= ALLOCATION_SIZE)
         return ByteBuffer.allocateDirect(size);

      if(currentBuffer == null || size > currentBuffer.remaining())
         currentBuffer = ByteBuffer.allocateDirect(ALLOCATION_SIZE);

      currentBuffer.limit(currentBuffer.position() + size);
      ByteBuffer result = currentBuffer.slice();
      currentBuffer.position(currentBuffer.limit());
      currentBuffer.limit(currentBuffer.capacity());
      return result;
   }



   private static DirectBufferProvider global_synced = new DirectBufferProvider();

   public static ByteBuffer allocateDirect(int size)
   {
      synchronized(global_synced)
      {
         return global_synced.allocate(size);
      }
   }
}

Note that unlike ByteBuffer.allocateDirect(), the code in DirectBufferProvider.allocate() is not threadsafe. The static (convenience) method is synchronized and should thus not be used in heavily multithreaded code. Using ThreadLocals is even worse, performance wise, so just make new DirectBufferProvider instances when you need them.

Delaying security dialogs in Java until you need them

2010-02-23T16:56:00.037+01:00

Delaying security dialogs in Java until you need them, is a bit harder than it should be. By default, the dialog appears before the first line of code is executed, scaring off your casual visitor.

If you only occasionally need to perform actions that require elevated privileges, you can delay the security dialog to the absolute last moment (for example: right before reading/writing a file). The trick is to keep most of your code in an unsigned JAR, and the code that requires elevated privileges into a signed JAR. Use Class.forName(String) to load the signed class, which will prompt the security dialog.

Using an interface in the unsigned code, and the implementation in the signed code, you can keep your code tidy.

Note:

The browser will remember the choice of the user, until a *restart* of the browser. To workaround this (when people declined), create a dozen tiny signed JARs (with a dozen different certificates, mind you) and use a roundrobin algorithm, using serverside code or javascript that generates the applet-archive attribute. After a dozen hits and rejections, you can be sure your visitor will never grant access to his system anyway.

Update:

To make it work in MSIE, both classes MUST be in separate packages.

IMPORTANT: Since 6u19 this doesn't work anymore. You not only get a rather confusing security dialog (clicking [YES] means deny access, clicking [NO] means allow access), the two classes end up in different classloaders that cannot access eachother, resulting in ClassNotFoundException / NoClassDefFoundException. Thanks Oracle, for making Java's user experience even more secure and crap at the same time.
http://java.sun.com/javase/6/docs/technotes/guides/jweb/mixed_code.html

On to the code, which is reasonably simple.

Unsigned JAR:

package some.unsigned.stuff;

public interface SecureAccess
{
   public byte[] loadFile(File file);
   public void storeFile(File file, byte[] data);
}

     // Usage:

     File file = new File("/home/silly/image.jpg");
     Class< ? > clazz = Class.forName("some.signed.stuff.LocalSecureAccess");
     SecureAccess access = (SecureAccess) clazz.newInstance();
     byte[] data = access.loadFile(file);

Signed JAR:

package some.signed.stuff;

public class LocalSecureAccess implements SecureAccess
{
   public byte[] loadFile(final File file)
   {
      return AccessController.doPrivileged(new PrivilegedAction<byte[]>()
      {
         @Override
         public byte[] run()
         {
            return loadFileImpl(file);
         }
      });
   }

   @Override
   public void storeFile(final File file, final byte[] data)
   {
      AccessController.doPrivileged(new PrivilegedAction<Object>()
      {
         @Override
         public Object run()
         {
            storeFileImpl(file, data);

            return null;
         }
      });
   }

   // implementation

   static final int MAX_FILE_SIZE = 8 * 1024 * 1024; // prevent applet running out of memory

   byte[] loadFileImpl(File file)
   {
      DataInputStream input = null;

      try
      {
         long len = file.length();
         if (len > MAX_FILE_SIZE)
            throw new IllegalStateException("file too big: " + file);

         byte[] data = new byte[(int) len];
         input = new DataInputStream(new FileInputStream(file));
         input.readFully(data);
         input.close();
         return data;
      }
      catch (IOException exc)
      {
         throw new IllegalStateException(exc);
      }
      finally
      {
         try { if(input!=null) input.close(); } catch(IOException exc) {}
      }
   }

   void storeFileImpl(File file, byte[] data)
   {
      OutputStream output = null;

      try
      {
         output = new FileOutputStream(file);
         output.write(data);
         output.flush();
      }
      catch (IOException exc)
      {
         throw new IllegalStateException(exc);
      }
      finally
      {
         try { if(output!=null) output.close(); } catch(IOException exc) {}
      }
   }
}

Jar signing 101: (using DSA keys instead of RSA for Java 1.4 compatibility)

PATH=%PATH%;path\to\JDK\bin
SET ALIAS=MY_ALIAS
SET PASS=MY_PASSWORD
SET JAR=my.jar

keytool -delete -storepass %PASS% -alias %ALIAS%
keytool -genkey -storepass %PASS% -keypass %PASS% -keyalg DSA -alias %ALIAS%
   -dname "CN=full.domainname.com, OU=Your unit, O=Your Company,
           L=Your city, ST=Your state, C=CA,
           EMAILADDRESS=your@server.com DC=server, DC=com"
   -validity 999 (put all of this on one line)
keytool -selfcert -storepass %PASS% -alias %ALIAS% -validity 999
keytool -exportcert -storepass %PASS% -alias %ALIAS% -rfc -file %ALIAS%.cer
jarsigner -storepass %PASS% -keypass %PASS% %JAR% %ALIAS%
pause

Applet code: (nothing special)

    <applet
      code="package/of/YourApplet.class"
      archive="unsigned.jar,signed.jar"
      width="640"
      height="480">
      no applet?
    </applet>

Image :: Java Animated GIFs (with transparant pixel disposal modes)

2010-02-04T19:23:00.007+01:00

It's a nightmare to find the code to create animated GIFs in Java. Once you found it, you notice you can't set the frame disposal, and transparent pixels will show pixels in the previous frames. The following code snippet solves this.

public class GifFrame
{
   public static final String NONE                = "none";
   public static final String DO_NOT_DISPOSE      = "doNotDispose";
   public static final String RESTORE_TO_BGCOLOR  = "restoreToBackgroundColor";
   public static final String RESTORE_TO_PREVIOUS = "restoreToPrevious";

   public final BufferedImage img;
   public final long          delay; // in millis
   public final String        disposalMethod;

   public GifFrame(BufferedImage img, long delay)
   {
      this(img, delay, NONE);
   }

   public GifFrame(BufferedImage img, long delay, String disposalMethod)
   {
      this.img = img;
      this.delay = delay;
      this.disposalMethod = disposalMethod;
   }
}

public class ImageUtil
{
   public static BufferedImage convertRGBAToGIF(BufferedImage src, int transColor)
   {
      BufferedImage dst = new BufferedImage(src.getWidth(), src.getHeight(), BufferedImage.TYPE_BYTE_INDEXED);
      Graphics g = dst.getGraphics();
      g.setColor(new Color(transColor));
      g.fillRect(0, 0, dst.getWidth(), dst.getHeight());
      {
         IndexColorModel indexedModel = (IndexColorModel) dst.getColorModel();
         WritableRaster raster = dst.getRaster();
         int sample = raster.getSample(0, 0, 0);
         int size = indexedModel.getMapSize();
         byte[] rr = new byte[size];
         byte[] gg = new byte[size];
         byte[] bb = new byte[size];
         indexedModel.getReds(rr);
         indexedModel.getGreens(gg);
         indexedModel.getBlues(bb);
         IndexColorModel newModel = new IndexColorModel(8, size, rr, gg, bb, sample);
         dst = new BufferedImage(newModel, raster, dst.isAlphaPremultiplied(), null);
      }
      dst.createGraphics().drawImage(src, 0, 0, null);
      return dst;
   }

   public static void saveAnimatedGIF(OutputStream out, List<GifFrame> frames, int loopCount) throws Exception
   {
      ImageWriter iw = ImageIO.getImageWritersByFormatName("gif").next();

      ImageOutputStream ios = ImageIO.createImageOutputStream(out);
      iw.setOutput(ios);
      iw.prepareWriteSequence(null);

      int p = 0;
      for (GifFrame frame : frames)
      {
         ImageWriteParam iwp = iw.getDefaultWriteParam();
         IIOMetadata metadata = iw.getDefaultImageMetadata(new ImageTypeSpecifier(frame.img), iwp);
         ImageUtil.configureGIFFrame(metadata, String.valueOf(frame.delay / 10L), p++, frame.disposalMethod, loopCount);
         IIOImage ii = new IIOImage(frame.img, null, metadata);
         iw.writeToSequence(ii, null);
      }

      iw.endWriteSequence();
      ios.close();
   }

   private static void configureGIFFrame(IIOMetadata meta, String delayTime, int imageIndex, String disposalMethod, int loopCount)
   {
      String metaFormat = meta.getNativeMetadataFormatName();

      if (!"javax_imageio_gif_image_1.0".equals(metaFormat))
      {
         throw new IllegalArgumentException("Unfamiliar gif metadata format: " + metaFormat);
      }

      Node root = meta.getAsTree(metaFormat);

      Node child = root.getFirstChild();
      while (child != null)
      {
         if ("GraphicControlExtension".equals(child.getNodeName()))
            break;
         child = child.getNextSibling();
      }

      IIOMetadataNode gce = (IIOMetadataNode) child;
      gce.setAttribute("userDelay", "FALSE");
      gce.setAttribute("delayTime", delayTime);
      gce.setAttribute("disposalMethod", disposalMethod);

      if (imageIndex == 0)
      {
         IIOMetadataNode aes = new IIOMetadataNode("ApplicationExtensions");
         IIOMetadataNode ae = new IIOMetadataNode("ApplicationExtension");
         ae.setAttribute("applicationID", "NETSCAPE");
         ae.setAttribute("authenticationCode", "2.0");
         byte[] uo = new byte[] { 0x1, (byte) (loopCount & 0xFF), (byte) ((loopCount >> 8) & 0xFF) };
         ae.setUserObject(uo);
         aes.appendChild(ae);
         root.appendChild(aes);
      }

      try
      {
         meta.setFromTree(metaFormat, root);
      }
      catch (IIOInvalidTreeException e)
      {
         throw new Error(e);
      }
   }
}

Usage:

List<GifFrame> gifFrames = new ArrayList<GifFrame>();

   for(BufferedImage image: images)
   {
      int transparantColor = 0xFF00FF; // purple
      BufferedImage gif = convertRGBAToGIF(image, transparantColor);
      long delay = 100; // every frame takes 100ms
      String disposal = GifFrame.RESTORE_TO_BGCOLOR; // make transparent pixels not 'shine through'
      gifFrames.add(new GifFrame(gif, delay, disposal));
   }

   int loopCount = 0; // loop indefinitely
   saveAnimatedGIF(outputStream, gifFrames, loopCount);

Image :: read/write TGA

2010-02-04T19:14:00.008+01:00

public static BufferedImage readTGA(File file) throws IOException
   {
      if (!file.exists())
         throw new FileNotFoundException(file.getAbsolutePath());

      byte[] header = new byte[18];
      int len = (int) file.length() - header.length;
      if (len < 0)
         throw new IllegalStateException("file not big enough to contain header: " + file.getAbsolutePath());
      byte[] data = new byte[len];

      RandomAccessFile raf = new RandomAccessFile(file, "r");
      raf.read(header);
      raf.read(data);
      raf.close();

      if ((header[0] | header[1]) != 0)
         throw new IllegalStateException(file.getAbsolutePath());
      if (header[2] != 2)
         throw new IllegalStateException(file.getAbsolutePath());
      int w = 0, h = 0;
      w |= (header[12] & 0xFF) << 0;
      w |= (header[13] & 0xFF) << 8;
      h |= (header[14] & 0xFF) << 0;
      h |= (header[15] & 0xFF) << 8;

      boolean alpha;
      if ((w * h) * 3 == data.length)
         alpha = false;
      else if ((w * h) * 4 == data.length)
         alpha = true;
      else
         throw new IllegalStateException(file.getAbsolutePath());
      if (!alpha && (header[16] != 24))
         throw new IllegalStateException(file.getAbsolutePath());
      if (alpha && (header[16] != 32))
         throw new IllegalStateException(file.getAbsolutePath());
      if ((header[17] & 15) != (alpha ? 8 : 0))
         throw new IllegalStateException(file.getAbsolutePath());

      BufferedImage dst = new BufferedImage(w, h, alpha ? BufferedImage.TYPE_INT_ARGB : BufferedImage.TYPE_INT_RGB);
      int[] pixels = ((DataBufferInt) dst.getRaster().getDataBuffer()).getData();
      if (pixels.length != w * h)
         throw new IllegalStateException(file.getAbsolutePath());
      if (data.length != pixels.length * (alpha ? 4 : 3))
         throw new IllegalStateException(file.getAbsolutePath());

      if (alpha)
      {
         for (int i = 0, p = (pixels.length - 1) * 4; i < pixels.length; i++, p -= 4)
         {
            pixels[i] |= ((data[p + 0]) & 0xFF) << 0;
            pixels[i] |= ((data[p + 1]) & 0xFF) << 8;
            pixels[i] |= ((data[p + 2]) & 0xFF) << 16;
            pixels[i] |= ((data[p + 3]) & 0xFF) << 24;
         }
      }
      else
      {
         for (int i = 0, p = (pixels.length - 1) * 3; i < pixels.length; i++, p -= 3)
         {
            pixels[i] |= ((data[p + 0]) & 0xFF) << 0;
            pixels[i] |= ((data[p + 1]) & 0xFF) << 8;
            pixels[i] |= ((data[p + 2]) & 0xFF) << 16;
         }
      }

      if ((header[17] >> 4) == 1)
      {
         // ok
      }
      else if ((header[17] >> 4) == 0)
      {
         // flip horizontally

         for (int y = 0; y < h; y++)
         {
            int w2 = w / 2;
            for (int x = 0; x < w2; x++)
            {
               int a = (y * w) + x;
               int b = (y * w) + (w - 1 - x);
               int t = pixels[a];
               pixels[a] = pixels[b];
               pixels[b] = t;
            }
         }
      }
      else
      {
         throw new UnsupportedOperationException(file.getAbsolutePath());
      }

      return dst;
   }

   public static void writeTGA(BufferedImage src, File file) throws IOException
   {
      DataBuffer buffer = src.getRaster().getDataBuffer();
      boolean alpha = src.getColorModel().hasAlpha();
      byte[] data;

      if (buffer instanceof DataBufferByte)
      {
         byte[] pixels = ((DataBufferByte) src.getRaster().getDataBuffer()).getData();
         if (pixels.length != src.getWidth() * src.getHeight() * (alpha ? 4 : 3))
            throw new IllegalStateException();

         data = new byte[pixels.length];

         for (int i = 0, p = pixels.length - 1; i < data.length; i++, p--)
         {
            data[i] = pixels[p];
         }
      }
      else if (buffer instanceof DataBufferInt)
      {
         int[] pixels = ((DataBufferInt) src.getRaster().getDataBuffer()).getData();
         if (pixels.length != src.getWidth() * src.getHeight())
            throw new IllegalStateException();

         data = new byte[pixels.length * (alpha ? 4 : 3)];

         if (alpha)
         {
            for (int i = 0, p = pixels.length - 1; i < data.length; i += 4, p--)
            {
               data[i + 0] = (byte) ((pixels[p] >> 0) & 0xFF);
               data[i + 1] = (byte) ((pixels[p] >> 8) & 0xFF);
               data[i + 2] = (byte) ((pixels[p] >> 16) & 0xFF);
               data[i + 3] = (byte) ((pixels[p] >> 24) & 0xFF);
            }
         }
         else
         {
            for (int i = 0, p = pixels.length - 1; i < data.length; i += 3, p--)
            {
               data[i + 0] = (byte) ((pixels[p] >> 0) & 0xFF);
               data[i + 1] = (byte) ((pixels[p] >> 8) & 0xFF);
               data[i + 2] = (byte) ((pixels[p] >> 16) & 0xFF);
            }
         }
      }
      else
      {
         throw new UnsupportedOperationException();
      }

      byte[] header = new byte[18];
      header[2] = 2; // uncompressed, true-color image
      header[12] = (byte) ((src.getWidth() >> 0) & 0xFF);
      header[13] = (byte) ((src.getWidth() >> 8) & 0xFF);
      header[14] = (byte) ((src.getHeight() >> 0) & 0xFF);
      header[15] = (byte) ((src.getHeight() >> 8) & 0xFF);
      header[16] = (byte) (alpha ? 32 : 24); // bits per pixel
      header[17] = (byte) ((alpha ? 8 : 0) | (1 << 4));

      RandomAccessFile raf = new RandomAccessFile(file, "rw");
      raf.write(header);
      raf.write(data);
      raf.setLength(raf.getFilePointer()); // trim
      raf.close();
   }

FastMath :: fast floor + ceil

2010-02-04T18:56:00.025+01:00

Calling Math.floor() simply takes too long. The problem with optimizing is that you can't simply cast the floatingpoint number to an integer, because that will result in invalid results for negative numbers. If we know our input values are in a specific range, we can safely add a certain (big) constant to the input, cast the guaranteed positive value to an integer and subtract the constant again.

The code is ~9x faster than Math.floor(). Replacing the doubles with floats makes it faster, but the results are rather... random, so don't.

public class FastMath
{
   private static final int    BIG_ENOUGH_INT   = 16 * 1024;
   private static final double BIG_ENOUGH_FLOOR = BIG_ENOUGH_INT + 0.0000;
   private static final double BIG_ENOUGH_ROUND = BIG_ENOUGH_INT + 0.5000;
   private static final double BIG_ENOUGH_CEIL  = BIG_ENOUGH_INT + 0.9999;

   public static int fastFloor(float x) {
      return (int) (x + BIG_ENOUGH_FLOOR) - BIG_ENOUGH_INT;
   }

   public static int fastRound(float x) {
      return (int) (x + BIG_ENOUGH_ROUND) - BIG_ENOUGH_INT;
   }

   public static int fastCeil(float x) {
      return (int) (x + BIG_ENOUGH_CEIL) - BIG_ENOUGH_INT;
   }
}

Image :: read size of JPG/PNG/BMP/GIF

2009-10-26T15:55:00.007+01:00

If you would believe Google, everybody is searching for code that reads the dimensions of an image,without loading all those colorful pixels. Oh well, without further ado....

public class ImageUtil
{
   public static Dimension getImageDimension(File file) throws IOException
   {
      return ImageUtil.getImageDimension(new FileInputStream(file));
   }

   public static Dimension getImageDimension(InputStream in) throws IOException
   {
      DataInputStream dis = new DataInputStream(in);

      try
      {
         int header = dis.readUnsignedShort();

         if (header == 0x8950)
         {
            // PNG
            dis.readFully(new byte[(8 - 2) + 4 + 4]); // thanks Abuse

            return new Dimension(dis.readInt(), dis.readInt());
         }

         if (header == 0xffd8)
         {
            // JPG (see below)
         }
         else if (header == 0x424D)
         {
            // BMP
            dis.readFully(new byte[16]);

            int w = dis.read() | (dis.read() << 8) | (dis.read() << 16) | (dis.read() << 24);
            int h = dis.read() | (dis.read() << 8) | (dis.read() << 16) | (dis.read() << 24);
            return new Dimension(w, h);
         }
         else if (header == (('G' << 8) | ('I' << 0))) // GIF
         {
            // GIF
            dis.readFully(new byte[4]);
            int w = dis.read() | (dis.read() << 8);
            int h = dis.read() | (dis.read() << 8);
            return new Dimension(w, h);
         }
         else
         {
            throw new IllegalStateException("unexpected header: " + Integer.toHexString(header));
         }

         while (true) // JPG is not so straight forward
         {
            int marker = dis.readUnsignedShort();

            switch (marker)
            {
               case 0xffd8: // SOI
               case 0xffd0: // RST0
               case 0xffd1: // RST1
               case 0xffd2: // RST2
               case 0xffd3: // RST3
               case 0xffd4: // RST4
               case 0xffd5: // RST5
               case 0xffd6: // RST6
               case 0xffd7: // RST7
               case 0xffd9: // EOI
                  break;

               case 0xffdd: // DRI
                  dis.readUnsignedShort();
                  break;

               case 0xffe0: // APP0
               case 0xffe1: // APP1
               case 0xffe2: // APP2
               case 0xffe3: // APP3
               case 0xffe4: // APP4
               case 0xffe5: // APP5
               case 0xffe6: // APP6
               case 0xffe7: // APP7
               case 0xffe8: // APP8
               case 0xffe9: // APP9
               case 0xffea: // APPa
               case 0xffeb: // APPb
               case 0xffec: // APPc
               case 0xffed: // APPd
               case 0xffee: // APPe
               case 0xffef: // APPf
               case 0xfffe: // COM
               case 0xffdb: // DQT
               case 0xffc4: // DHT
               case 0xffda: // SOS
                  dis.readFully(new byte[dis.readUnsignedShort() - 2]);
                  break;

               case 0xffc0: // SOF0
               case 0xffc2: // SOF2
                  dis.readUnsignedShort();
                  dis.readByte();
                  int height = dis.readUnsignedShort();
                  int width = dis.readUnsignedShort();
                  return new Dimension(width, height);

               default:
                  throw new IllegalStateException("invalid jpg marker: " + Integer.toHexString(marker));
            }
         }
      }
      finally
      {
         dis.close();
      }
   }
}

Graycode :: for analog stuff!

2009-08-30T02:18:00.005+02:00

THIS WAS FUN.

Proved the math teacher wrong.

public class Graycode
{
   public static int normalToGray(int orig)
   {
      int gray = 0;
      for (int n = 0; n < 31; n++)
         gray |= (((orig + (1 << n)) >> (n + 1)) & 1) << n;
      return gray;
   }

   public static int grayToNormal(int gray)
   {
      int parity = 0;
      int norm = 0;
      for (int pos = 31; pos >= 0; pos--)
         norm = (norm << 1) | (parity ^= ((gray >> pos) & 1));
      return norm;
   }

   public static int changedBitInNextGrayCode(int gray)
   {
      for (int i = 0; i < 31; i++)
         if (parity(gray >> i) == 0)
            return i + 1;
      return -1;
   }

   private static int parity(int v)
   {
      int c = 0;
      for (int i = 0; i < 31; i++)
         c ^= (v & (1 << i)) >> i;
      return c;
   }
}

Set :: binary operations

2009-08-30T02:02:00.003+02:00

Everybody should have these. It's just a drag to rewrite it time and time again.

public class SetUtil
{
   public static <T> Set<T> and(Set<T> a, Set<T> b)
   {
      Set<T> c = new HashSet<T>();
      // c.addAll(SetUtil.or(a, b));
      // c.removeAll(SetUtil.xor(a, b));
      c.addAll(a);
      c.retainAll(b);
      return c;
   }

   public static <T> Set<T> or(Set<T> a, Set<T> b)
   {
      Set<T> c = new HashSet<T>();
      c.addAll(a);
      c.addAll(b);
      return c;
   }

   public static <T> Set<T> xor(Set<T> a, Set<T> b)
   {
      Set<T> a_minus_b = new HashSet<T>();
      a_minus_b.addAll(a);
      a_minus_b.removeAll(b);

      Set<T> b_minus_a = new HashSet<T>();
      b_minus_a.addAll(b);
      b_minus_a.removeAll(a);

      Set<T> c = new HashSet<T>();
      c.addAll(a_minus_b);
      c.addAll(b_minus_a);
      return c;
   }
}

ArraySorter :: in-place, pre-calc

2009-08-30T01:50:00.003+02:00

The point of this class is to pre-calculate the sort-order in advance, so that we're not comparing objects all the time, and then do a proper/fast sort. In-place, meaning not creating an auxillary array, like Arrays.sort() does. This class is thread safe, as in... synchronized.

The 'chunked' version uses 'bucket sort' and then does a regular sort on the buckets, and merges the result back in the original array.

The Sortable interface is expected to calculate the sort-index in calcSortIndex() and return that value each and every time in getSortIndex()

public interface Sortable
{
   public void calcSortIndex();

   public int getSortIndex();
}

public class ArraySorter
{
   public static final synchronized void fineSort(Sortable[] p, int off, int len)
   {
      for (int i = 0; i < len; i++)
         p[off + i].calcSortIndex();

      ArraySorter.doFineSortImpl(p, off, len);
   }

   public static final synchronized void chunkedSort(Sortable[] p, int off, int len, int min, int max, int chunks)
   {
      for (int i = 0; i < len; i++)
         p[off + i].calcSortIndex();

      ArraySorter.doChunkedSortImpl(p, off, len, min, max, chunks);
   }

   /**
    * FINE
    */

   private static final void doFineSortImpl(Sortable[] p, int off, int len)
   {
      if (len < 7)
      {
         for (int i = off; i < len + off; i++)
            for (int j = i; j > off && p[j - 1].getSortIndex() > p[j].getSortIndex(); j--)
               swap(p, j, j - 1);

         return;
      }

      int m = off + (len >> 1);

      if (len > 7)
      {
         int l = off;
         int n = off + len - 1;

         if (len > 40)
         {
            int s = len >>> 3;
            l = med3(p, l, l + s, l + 2 * s);
            m = med3(p, m - s, m, m + s);
            n = med3(p, n - 2 * s, n - s, n);
         }

         m = med3(p, l, m, n);
      }

      int v = p[m].getSortIndex();

      int a = off;
      int b = a;
      int c = off + len - 1;
      int d = c;

      while (true)
      {
         while (b <= c && p[b].getSortIndex() <= v)
         {
            if (p[b].getSortIndex() == v)
               swap(p, a++, b);
            b++;
         }

         while (c >= b && p[c].getSortIndex() >= v)
         {
            if (p[c].getSortIndex() == v)
               swap(p, c, d--);
            c--;
         }

         if (b > c)
            break;

         swap(p, b++, c--);
      }

      int s, n = off + len;
      s = Math.min(a - off, b - a);
      swapRange(p, off, b - s, s);
      s = Math.min(d - c, n - d - 1);
      swapRange(p, b, n - s, s);

      if ((s = b - a) > 1)
         doFineSortImpl(p, off, s);

      if ((s = d - c) > 1)
         doFineSortImpl(p, n - s, s);
   }

   private static final void swap(Sortable[] p, int a, int b)
   {
      Sortable q = p[a];
      p[a] = p[b];
      p[b] = q;
   }

   private static final void swapRange(Sortable[] p, int a, int b, int n)
   {
      Sortable q;

      for (int i = 0; i < n; i++, a++, b++)
      {
         q = p[a];
         p[a] = p[b];
         p[b] = q;
      }
   }

   private static final int med3(Sortable[] p, int a, int b, int c)
   {
      int a0 = p[a].getSortIndex();
      int b0 = p[b].getSortIndex();
      int c0 = p[c].getSortIndex();
      return (a0 < b0 ? (b0 < c0 ? b : (a0 < c0 ? c : a)) : (b0 > c0 ? b : (a0 > c0 ? c : a)));
   }

   /**
    * CHUNKED
    */

   private static List<Sortable>   less  = new ArrayList<Sortable>();
   private static List<Sortable>[] parts = new List[0];
   private static List<Sortable>   more  = new ArrayList<Sortable>();
   private static Sortable[]       tmp   = new Sortable[64];

   private static final void doChunkedSortImpl(Sortable[] p, int off, int len, int min, int max, int chunks)
   {
      if (parts.length < chunks)
      {
         parts = new List[chunks];

         for (int i = 0; i < parts.length; i++)
            parts[i] = new ArrayList<Sortable>();
      }

      // sort-index is already calculated here

      // distribute sortables over lists
      for (int i = 0; i < len; i++)
      {
         Sortable s = p[off + i];
         int index = s.getSortIndex();

         if (index < min)
            less.add(s);
         else if (index >= max)
            more.add(s);
         else
         {
            float percent = (float) (s.getSortIndex() - min) / (max - min);
            int arrayIndex = (int) (percent * chunks);
            parts[arrayIndex].add(s);
         }
      }

      // sort lists, overwrite P
      tmp = less.toArray(tmp);
      ArraySorter.doFineSortImpl(tmp, 0, less.size());
      System.arraycopy(tmp, 0, p, off, less.size());
      off += less.size();

      for (int i = 0; i < chunks; i++)
      {
         if (parts[i].isEmpty())
            continue;

         tmp = parts[i].toArray(tmp);
         ArraySorter.doFineSortImpl(tmp, 0, parts[i].size());
         System.arraycopy(tmp, 0, p, off, parts[i].size());
         off += parts[i].size();
      }

      tmp = more.toArray(tmp);
      ArraySorter.doFineSortImpl(tmp, 0, more.size());
      System.arraycopy(tmp, 0, p, off, more.size());
      off += more.size();

      // clear up all references
      less.clear();
      for (int i = 0; i < chunks; i++)
         parts[i].clear();
      more.clear();
   }
}

Histogram :: map-based

2009-08-30T01:27:00.002+02:00

public class Histogram<T>
{
   private final Map<T, Integer> map;

   public Histogram()
   {
      this.map = new HashMap<T, Integer>();
   }

   public int put(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         count = Integer.valueOf(0);
      count = Integer.valueOf(count.intValue() + 1);
      this.map.put(t, count);
      return count.intValue();
   }

   public int get(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public List<T> topKeys(int amount)
   {
      //int threshold = Integer.MIN_VALUE;

      List<T> kList = new ArrayList<T>();
      List vList = new ArrayList();

      for (Entry e : this.map.entrySet())
      {
         //int val = e.getValue().intValue();
         //if (val <= threshold)
         {
            //continue;
         }

         // when full, remove lowest
         if (vList.size() == amount)
         {
            int index = indexOfMin(vList);
            kList.remove(index);
            vList.remove(index);
         }

         kList.add(e.getKey());
         vList.add(e.getValue());
      }

      // bubble sort
      for (int i = 0; i < vList.size(); i++)
      {
         for (int k = i + 1; k < vList.size(); k++)
         {
            if (vList.get(i).intValue() >= vList.get(k).intValue())
            {
               continue;
            }

            Integer a = vList.get(i);
            Integer b = vList.get(k);
            vList.set(k, a);
            vList.set(i, b);

            T x = kList.get(i);
            T y = kList.get(k);
            kList.set(k, x);
            kList.set(i, y);
         }
      }

      return kList;
   }

   public int remove(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         throw new NoSuchElementException(String.valueOf(t));
      if (count.intValue() == 0)
         throw new IllegalStateException("cannot remove");

      count = Integer.valueOf(count.intValue() - 1);
      if (count.intValue() == 0)
         this.map.remove(t);
      else
         this.map.put(t, count);

      return count.intValue();
   }

   public int reset(T t)
   {
      Integer count = this.map.remove(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public int set(T t, int val)
   {
      if (val < 0)
         throw new IllegalArgumentException();
      Integer count = this.map.get(t);

      if (count == null)
      {
         if (val != 0)
            this.map.put(t, Integer.valueOf(val));
         return 0;
      }

      if (val == 0)
         return this.map.remove(t).intValue();
      return this.map.put(t, Integer.valueOf(val)).intValue();
   }

   public Set<T> keys()
   {
      return this.map.keySet();
   }

   private static int indexOfMin(List<Integer> ids)
   {
      int minAt = 0;
      for (int i = 1; i < ids.size(); i++)
         if (ids.get(i).intValue() < ids.get(minAt).intValue())
            minAt = i;
      return minAt;
   }
}

Unsafe :: Pointers

2009-08-30T01:09:00.005+02:00

   private final static Unsafe   unsafe;
   private static long           addressOffset;
   private static long           positionOffset;
   private static long           limitOffset;
   private static long           capacityOffset;

   public static final long      WORD_SIZE_BITS, HEADER_SIZE;
   public static final long      BYTE_ARRAY_BASE_OFFSET;
   public static final long      SHORT_ARRAY_BASE_OFFSET;
   public static final long      INT_ARRAY_BASE_OFFSET;
   public static final long      LONG_ARRAY_BASE_OFFSET;
   public static final long      FLOAT_ARRAY_BASE_OFFSET;
   public static final long      DOUBLE_ARRAY_BASE_OFFSET;
   public static final long      OBJECT_ARRAY_BASE_OFFSET;
   private static final Object[] holder = new Object[1];

   static
   {
      try
      {
         ByteBuffer buffer = ByteBuffer.allocateDirect(1);
         Field unsafeField = buffer.getClass().getDeclaredField("unsafe");
         unsafeField.setAccessible(true);
         unsafe = (Unsafe) unsafeField.get(buffer);
         unsafeField.setAccessible(false);

         addressOffset = getObjectFieldOffset(buffer, "address");
         positionOffset = getObjectFieldOffset(buffer, "position");
         limitOffset = getObjectFieldOffset(buffer, "limit");
         capacityOffset = getObjectFieldOffset(buffer, "capacity");

         buffer.flip();
         buffer = null;
      }
      catch (Exception exc)
      {
         exc.printStackTrace();
         throw new InternalError();
      }

      WORD_SIZE_BITS = unsafe.addressSize() * 8;
      if (WORD_SIZE_BITS != 32 && WORD_SIZE_BITS != 64)
         throw new IllegalStateException("WORD_SIZE: " + WORD_SIZE_BITS);
      HEADER_SIZE = WORD_SIZE_BITS / 8 * 2;

      BYTE_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new byte[4].getClass());
      SHORT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new short[4].getClass());
      INT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new int[4].getClass());
      LONG_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new long[4].getClass());
      FLOAT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new float[4].getClass());
      DOUBLE_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new double[4].getClass());
      OBJECT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new Object[4].getClass());
   }

   public static final long getObjectAddress(Object obj)
   {
      holder[0] = obj;

      if (WORD_SIZE_BITS == 32)
         return unsafe.getInt(holder, OBJECT_ARRAY_BASE_OFFSET);
      if (WORD_SIZE_BITS == 64)
         return unsafe.getLong(holder, OBJECT_ARRAY_BASE_OFFSET);

      throw new IllegalStateException();
   }

   public static final Object getObjectAtAddress(long addr)
   {
      if (WORD_SIZE_BITS == 32)
         unsafe.putInt(holder, OBJECT_ARRAY_BASE_OFFSET, (int) (addr & 0xFFFFFFFF));
      if (WORD_SIZE_BITS == 64)
         unsafe.putLong(holder, OBJECT_ARRAY_BASE_OFFSET, addr);

      return holder[0];
   }

   public static final FloatBuffer createFloatBufferAt(long pntr, int len)
   {
      Native.zeroOut(pntr, len << 2);

      FloatBuffer buf = ByteBuffer.allocateDirect(4).order(ByteOrder.nativeOrder()).asFloatBuffer();
      NativeHacks.setBufferProperties(buf, pntr, 0, len, len);
      buf.clear();

      return buf;
   }

   public static final float[] createFloatArrayAt(long pntr, int len)
   {
      NativeHacks.copyObjectHeaderTo(new float[0], pntr);

      // write length
      unsafe.putInt(pntr + HEADER_SIZE, len);

      return (float[]) NativeHacks.fakePointerAsObject(pntr);
   }

   public static final void copyObjectHeaderTo(Object obj, long pntr)
   {
      for (int i = 0; i < HEADER_SIZE; i++)
         unsafe.putByte(pntr + i, unsafe.getByte(obj, (long) i));
   }

   public static final Object fakePointerAsObject(long addr)
   {
      if (WORD_SIZE_BITS == 32)
         unsafe.putInt(holder, OBJECT_ARRAY_BASE_OFFSET, (int) (addr & 0xFFFFFFFF));
      else if (WORD_SIZE_BITS == 64)
         unsafe.putLong(holder, OBJECT_ARRAY_BASE_OFFSET, addr);
      else
         throw new IllegalStateException();

      return holder[0];
   }

Thread :: monitor CPU usage

2009-08-25T03:48:00.006+02:00

If you want to monitor CPU usage, per thread, things couldn't get easier!

ThreadGroupMonitor gmonitor = new ThreadGroupMonitor();

while(true)
{
   gmonitor.poll();

   for(ThreadMonitor tmon: gmonitor.getAliveThreadMonitors())
   {
      double avg = tmon.getCpuTimeStats().avg();  // avg of last polls
      double avg = tmon.getCpuTimeStats().avg(3); // avg of last 3 polls
      double avg = tmon.getCpuTimeStats().avg(5); // avg of last 5 polls
   }

   for(ThreadMonitor tmon: gmonitor.getDeadThreadMonitors())
   {
      double total = tmon.getTotalCpuTime();
   }

   // sleep for a bit
}

Even dead threads...

public class ThreadMonitor
{
   private static ThreadMXBean tmxb;

   static
   {
      tmxb = ManagementFactory.getThreadMXBean();
      tmxb.setThreadCpuTimeEnabled(true);
   }

   //

   private long                tid;
   private CyclicUsageHistory  cpuTimeHistory;
   private CyclicUsageHistory  userTimeHistory;
   private CyclicUsageHistory  cpuUsageHistory;
   private CyclicUsageHistory  userUsageHistory;

   public ThreadMonitor(long tid, int slots)
   {
      this.tid = tid;
      this.cpuTimeHistory = new CyclicUsageHistory(slots);
      this.userTimeHistory = new CyclicUsageHistory(slots);
      this.cpuUsageHistory = new CyclicUsageHistory(slots);
      this.userUsageHistory = new CyclicUsageHistory(slots);
   }

   public long getId()
   {
      return tid;
   }

   private double totalCpuTime;
   private double totalUserTime;
   
   public double getTotalCpuTime()
   {
      return this.totalCpuTime;
   }
   
   public double getTotalUserTime()
   {
      return this.totalUserTime;
   }

   public void poll()
   {
      // a time of -1 means not alive

      double cpuTime = tmxb.getThreadCpuTime(this.tid) / 1000000000.0;
      this.totalCpuTime += cpuTime < 0 ? 0 : cpuTime;
      cpuTimeHistory.log(cpuTime < 0 ? 0 : cpuTime);
      cpuUsageHistory.log(cpuTimeHistory.previous(0) - cpuTimeHistory.previous(1));

      double userTime = tmxb.getThreadUserTime(this.tid) / 1000000000.0;
      this.totalUserTime += userTime < 0 ? 0 : userTime;
      userTimeHistory.log(userTime < 0 ? 0 : userTime);
      userUsageHistory.log(userTimeHistory.previous(0) - userTimeHistory.previous(1));
   }

   public CyclicUsageHistory getCpuTimeStats()
   {
      return this.cpuUsageHistory;
   }

   public CyclicUsageHistory getUserTimeStats()
   {
      return this.userUsageHistory;
   }
}

public class ThreadGroupMonitor
{
   public ThreadGroupMonitor()
   {
      this(Thread.currentThread().getThreadGroup());
   }

   public ThreadGroupMonitor(ThreadGroup group)
   {
      this.group = group;
      this.lastThreadIds = new long[0];
      this.aliveId2mon = new HashMap();
      this.deadId2mon = new HashMap();
   }

   //

   private final ThreadGroup group;

   public ThreadGroup getThreadGroup()
   {
      return group;
   }

   //

   private int totalDeadThreadCount = 0;

   public synchronized int getTotalDeadThreadCount()
   {
      return this.totalDeadThreadCount;
   }

   //

   private int regularThreadCount = 0;

   public synchronized int getRegularThreadCount()
   {
      return this.regularThreadCount;
   }

   //

   private int deamonThreadCount = 0;

   public synchronized int getDeamonThreadCount()
   {
      return this.deamonThreadCount;
   }

   //

   private static final int         default_slots = 3600;

   private long[]                   lastThreadIds;
   private Map aliveId2mon;
   private Map deadId2mon;

   public synchronized void poll()
   {
      Thread[] threads = this.findAllThreads();

      long[] currThreadIds = this.findAllThreadIds(threads);
      long[] newIds = this.findNewThreadIds(this.lastThreadIds, currThreadIds);
      long[] deadIds = this.findDeadThreadIds(this.lastThreadIds, currThreadIds);

      this.totalDeadThreadCount += deadIds.length;

      for (long newId : newIds)
         aliveId2mon.put(Long.valueOf(newId), new ThreadMonitor(newId, default_slots));
      for (long deadId : deadIds)
         deadId2mon.put(Long.valueOf(deadId), aliveId2mon.remove(Long.valueOf(deadId)));

      for (ThreadMonitor mon : aliveId2mon.values())
         mon.poll();
      for (ThreadMonitor mon : deadId2mon.values())
         mon.poll();

      this.analyzeThreads(threads);

      this.lastThreadIds = currThreadIds;
   }

   public synchronized double getAvgCpuTimeStats(int pollCount)
   {
      double sum = 0.0;
      for (ThreadMonitor mon : aliveId2mon.values())
         sum += mon.getCpuTimeStats().avg(pollCount);
      return sum;
   }

   public synchronized double getAvgUserTimeStats(int pollCount)
   {
      double sum = 0.0;
      for (ThreadMonitor mon : aliveId2mon.values())
         sum += mon.getUserTimeStats().avg(pollCount);
      return sum;
   }

   public Collection getAliveThreadMonitors()
   {
      return Collections.unmodifiableCollection(this.aliveId2mon.values());
   }

   public Collection getDeadThreadMonitors()
   {
      return Collections.unmodifiableCollection(this.deadId2mon.values());
   }

   private void analyzeThreads(Thread[] threads)
   {
      int deamonThreadCount = 0;
      int regularThreadCount = 0;

      for (Thread thread : threads)
      {
         if (!thread.isAlive())
            continue;
         if (thread.isDaemon())
            deamonThreadCount++;
         else
            regularThreadCount++;
      }

      this.deamonThreadCount = deamonThreadCount;
      this.regularThreadCount = regularThreadCount;
   }

   public Thread[] findAllThreads()
   {
      int threadCount;

      Thread[] tempThreadArray = new Thread[8];
      while ((threadCount = this.group.enumerate(tempThreadArray)) == tempThreadArray.length)
         tempThreadArray = ArrayUtil.growTo(tempThreadArray, tempThreadArray.length * 2);

      Thread[] threadArray = new Thread[threadCount];
      System.arraycopy(tempThreadArray, 0, threadArray, 0, threadCount);
      return threadArray;
   }

   private long[] findAllThreadIds(Thread[] threads)
   {
      long[] allThreadIds = new long[threads.length];
      for (int i = 0; i < allThreadIds.length; i++)
         allThreadIds[i] = threads[i].getId();
      return allThreadIds;
   }

   private long[] findNewThreadIds(long[] lastThreads, long[] currThreads)
   {
      long[] newThreadIds = new long[currThreads.length];
      int newThreadIndex = 0;

      outer: for (int i = 0; i < currThreads.length; i++)
      {
         for (int k = 0; k < lastThreads.length; k++)
            if (currThreads[i] == lastThreads[k])
               continue outer;
         newThreadIds[newThreadIndex++] = currThreads[i];
      }

      long[] ids = new long[newThreadIndex];
      System.arraycopy(newThreadIds, 0, ids, 0, newThreadIndex);
      return ids;
   }

   private long[] findDeadThreadIds(long[] lastThreads, long[] currThreads)
   {
      long[] deadThreadIds = new long[lastThreads.length];
      int deadThreadIndex = 0;

      outer: for (int i = 0; i < lastThreads.length; i++)
      {
         for (int k = 0; k < currThreads.length; k++)
            if (lastThreads[i] == currThreads[k])
               continue outer;
         deadThreadIds[deadThreadIndex++] = lastThreads[i];
      }

      long[] ids = new long[deadThreadIndex];
      System.arraycopy(deadThreadIds, 0, ids, 0, deadThreadIndex);
      return ids;
   }
}

public class CyclicUsageHistory
{
   private final double[] values;

   public CyclicUsageHistory(int slots)
   {
      this.values = new double[slots];
   }

   private int addIndex;

   public void log(double value)
   {
      this.values[this.addIndex++ % this.values.length] = value;
   }
   
   //

   public double previous()
   {
      return this.previous(0);
   }

   public double previous(int age)
   {
      int len = this.values.length;
      return this.values[(((this.addIndex - 1 - age) % len) + len) % len];
   }

   //

   public double max()
   {
      return this.max(this.values.length);
   }

   public double max(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      double max = 0.0;
      for (int i = 0; i < count; i++)
         if (this.previous(i) > max)
            max = this.previous(i);
      return max;
   }

   //

   public double sum()
   {
      return this.sum(this.values.length);
   }

   public double sum(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      double sum = 0.0;
      for (int i = 0; i < count; i++)
         sum += this.previous(i);
      return sum;
   }

   //

   public double avg()
   {
      return this.avg(this.values.length);
   }

   public double avg(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      return this.sum(slots) / count;
   }

   //

   public double nom()
   {
      return this.nom(this.values.length);
   }

   public double nom(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));
      if (count == 0)
         return 0.0;

      double[] arr = new double[count];
      for (int i = 0; i < count; i++)
         arr[i] = this.previous(i);
      Arrays.sort(arr);
      return arr[arr.length / 2];
   }
}

Swappable Jar ClassLoader

2009-08-25T02:00:00.026+02:00

So you have this pluggable stuff, and you want to support realtime loading of new classes. That's not so hard, but what if old classes try to load old classes, and the JAR has been replaced? Right! Native crash. Blehh.

With DynamicJarClassLoader you can do this:

ClassLoader loader = new DynamicJarClassLoader(parent, file);
Class clzz1 = loader.loadClass("my.package.MyClass");
// ...
// JAR is replaced
// ...
Class clzz2 = loader.loadClass("my.package.MyClass");
// ...
clzz1.newInstance(); // loads old "other.package.OtherClass"
clzz2.newInstance(); // loads new "other.package.OtherClass"

Let's say MyClass will also load "other.package.OtherClass" sooner or later. The classloader will keep that data loaded, so that clzz1 and clzz2 have access to their own version of OtherClass.

Fancy stuff!

public class DynamicJarClassLoader extends DynamicClassLoader
{
   private final File        jar;
   private long              prevLastModified;
   private final Set resourceNames;

   public DynamicJarClassLoader(ClassLoader parent, File jar)
   {
      super(parent);

      this.jar = jar;
      this.prevLastModified = -1L;
      this.resourceNames = new HashSet();

      this.ensureLatestClassLoader();
   }

   public File getJar()
   {
      return this.jar;
   }

   public Set getResourceNames()
   {
      return Collections.unmodifiableSet(this.resourceNames);
   }

   private static final long file_idle_timeout = 3 * 1000;

   @Override
   public boolean isUpdated()
   {
      long jarLastModified = this.jar.lastModified();

      boolean willBeUpdated = jarLastModified != this.prevLastModified;

      if (willBeUpdated && this.prevLastModified != -1L)
      {
         if (this.jar.lastModified() > System.currentTimeMillis() - file_idle_timeout)
         {
            Logger.notification("Pending new JAR file: %s", this.jar.getAbsolutePath());
            willBeUpdated = false;
         }
      }

      if (willBeUpdated)
      {
         Logger.notification("Loading new JAR file: %s", this.jar.getAbsolutePath());
         this.prevLastModified = jarLastModified;
      }

      return willBeUpdated;
   }

   @Override
   public ClassLoader createClassLoader()
   {
      final Map resources;

      this.resourceNames.clear();

      try
      {
         resources = this.loadCompleteJarFile();
      }
      catch (IOException exc)
      {
         throw new IllegalStateException("Failed to load JAR file: " + this.jar.getAbsolutePath(), exc);
      }

      this.resourceNames.addAll(resources.keySet());

      ClassLoader loader = new BytesClassLoader(this.getParent())
      {
         @Override
         public byte[] readBytes(String name)
         {
            return resources.get(name);
         }
      };

      return loader;
   }

   private final Map loadCompleteJarFile() throws IOException
   {
      Map map = new HashMap();

      JarFile jf = new JarFile(this.jar);
      Enumeration entries = jf.entries();
      while (entries.hasMoreElements())
      {
         byte[] buf = null;

         JarEntry entry = entries.nextElement();

         if (!entry.isDirectory())
         {
            buf = new byte[(int) entry.getSize()];
            InputStream in = jf.getInputStream(entry);
            int off = 0;
            while (off != buf.length)
            {
               int justRead = in.read(buf, off, buf.length - off);
               if (justRead == -1)
                  throw new EOFException("Could not fully read JAR file entry: " + entry.getName());
               off += justRead;
            }
            in.close();
         }

         map.put(entry.getName(), buf);
      }

      jf.close();

      return map;
   }
}

public abstract class DynamicClassLoader extends ClassLoader
{
   private ClassLoader currentLoader;

   public DynamicClassLoader(ClassLoader parent)
   {
      super(parent);
      this.currentLoader = null;
   }

   //

   public abstract boolean isUpdated();

   public abstract ClassLoader createClassLoader();

   //

   @Override
   public URL getResource(String name)
   {
      this.ensureLatestClassLoader();

      URL url = this.getParent().getResource(name);
      if (url != null)
         return url;

      return this.currentLoader.getResource(name);
   }

   @Override
   public Enumeration getResources(String name) throws IOException
   {
      this.ensureLatestClassLoader();

      Enumeration urls = this.getParent().getResources(name);
      if (urls != null)
         return urls;

      return this.currentLoader.getResources(name);
   }

   @Override
   public InputStream getResourceAsStream(String name)
   {
      this.ensureLatestClassLoader();

      InputStream in = this.getParent().getResourceAsStream(name);
      if (in != null)
         return in;

      return this.currentLoader.getResourceAsStream(name);
   }

   public synchronized Class< ? > loadClass(String name) throws ClassNotFoundException
   {
      this.ensureLatestClassLoader();

      return this.currentLoader.loadClass(name);
   }

   //

   private long lastChecked;
   private long minCheckInterval = 0;

   public void setMinCheckInterval(long minCheckInterval)
   {
      this.minCheckInterval = minCheckInterval;
   }

   public final boolean checkForUpdate()
   {
      long now = System.currentTimeMillis();
      long elapsed = now - this.lastChecked;

      if (elapsed < this.minCheckInterval)
      {
         // if we checked less than N ms ago,
         // just assume the loader is not updated.
         // otherwise we put a major strain on
         // the file system (?) for no real gain
         return false;
      }

      this.lastChecked = now;

      return this.isUpdated();
   }

   //

   public void ensureLatestClassLoader()
   {
      if (this.checkForUpdate())
      {
         this.replaceClassLoader();
      }
   }

   protected void replaceClassLoader()
   {
      this.currentLoader = this.createClassLoader();

      // protected, so do stuff, if you wish
   }
}

public abstract class BytesClassLoader extends ClassLoader
{
   public BytesClassLoader(ClassLoader parent)
   {
      super(parent);
   }
   
   protected abstract byte[] readBytes(String path);

   public synchronized Class< ? > loadClass(String name) throws ClassNotFoundException
   {
      Class< ? > found = this.findLoadedClass(name);
      if (found != null)
      {
         return found;
      }

      String path = name.replace('.', '/').concat(".class");

      byte[] raw = this.readBytes(path);

      if (raw == null)
      {
         return this.getParent().loadClass(name);
      }

      return super.defineClass(name, raw, 0, raw.length);
   }

   @Override
   public InputStream getResourceAsStream(String path)
   {
      byte[] raw = this.readBytes(path);
      if (raw == null)
         return null;
      return new ByteArrayInputStream(raw);
   }

   @Override
   public URL getResource(String name)
   {
      // who uses this anyway?
      throw new UnsupportedOperationException();
   }

   @Override
   public Enumeration getResources(String name) throws IOException
   {
      // who uses this anyway?
      throw new UnsupportedOperationException();
   }
}

Basic HTML to BufferedImage

2009-08-25T01:48:00.007+02:00

This is truely a poor man's HTML renderer. It basically uses JLabel under the hood, and even has rather limited CSS support. It's all rather crude, but it might do the job for you.

public class BasicHTMLRenderer
{
   public static synchronized void render(
                      final BufferedImage img,
                      final String html,
                      final boolean makeTransparant)
   {
      if (!inited)
         init();

      Runnable task = new Runnable()
      {
         @Override
         public void run()
         {
            htmlRender.setText("<html>" + html);
            Dimension dim = new Dimension(img.getWidth(), img.getHeight());
            htmlRender.setPreferredSize(dim);
            htmlHolder.pack();

            if (makeTransparant)
            {
               Graphics2D g2d = img.createGraphics();
               g2d.setComposite(AlphaComposite.getInstance(AlphaComposite.CLEAR, 0.0f));
               g2d.fillRect(0, 0, img.getWidth(), img.getHeight());
               g2d.dispose();
            }

            Graphics g = img.getGraphics();
            htmlRender.paint(g);
            g.dispose();
         }
      };

      try
      {
         SwingUtilities.invokeAndWait(task);
      }
      catch (InterruptedException exc)
      {
         throw new IllegalStateException(exc);
      }
      catch (InvocationTargetException exc)
      {
         throw new IllegalStateException(exc);
      }
   }

   static boolean inited;
   static JFrame  htmlHolder;
   static JLabel  htmlRender;

   private static synchronized void init()
   {
      Runnable task = new Runnable()
      {
         @Override
         public void run()
         {
            htmlRender = new JLabel("<html>");
            htmlRender.setVerticalAlignment(SwingConstants.TOP);

            htmlHolder = new JFrame();
            htmlHolder.getContentPane().setLayout(new BorderLayout());
            htmlHolder.getContentPane().add(htmlRender);

            synchronized (BasicHTMLRenderer.class)
            {
               inited = true;
            }
         }
      };
      SwingUtilities.invokeLater(task);
   }

   public static synchronized void dispose()
   {
      if (!inited)
         return;

      Runnable task = new Runnable()
      {
         @Override
         public void run()
         {
            htmlRender = null;

            htmlHolder.dispose();
            htmlHolder = null;

            synchronized (BasicHTMLRenderer.class)
            {
               inited = false;
            }
         }
      };
      SwingUtilities.invokeLater(task);
   }
}

Spline :: 2D

2009-08-25T01:35:00.007+02:00

public class Spline2D
{
   public Spline2D(float[][] points)
   {
      this.count = points.length;

      float[] x = new float[count];
      float[] y = new float[count];

      for (int i = 0; i < count; i++)
      {
         x[i] = points[i][0];
         y[i] = points[i][1];
      }

      this.x = Curve.calcCurve(count - 1, x);
      this.y = Curve.calcCurve(count - 1, y);
   }

   //

   final int count;
   private final Cubic[] x, y;

   /**
    * POINT COUNT
    */

   public final int pointCount()
   {
      return count;
   }

   /**
    * POSITION
    */

   public final float[] getPositionAt(float param)
   {
      float[] v = new float[2];
      this.getPositionAt(param, v);
      return v;
   }

   public final void getPositionAt(float param, float[] result)
   {
      // clamp
      if (param < 0.0f)
         param = 0.0f;
      if (param >= count - 1)
         param = (count - 1) - Math.ulp(count - 1);

      // split
      int ti = (int) param;
      float tf = param - ti;

      // eval
      result[0] = x[ti].eval(tf);
      result[1] = y[ti].eval(tf);
   }

   private List travelCache;
   private float           maxTravelStep;
   private float           posStep;

   public void enabledTripCaching(float maxTravelStep, float posStep)
   {
      this.maxTravelStep = maxTravelStep;
      this.posStep = posStep;

      float x = this.x[0].eval(0.0f);
      float y = this.y[0].eval(0.0f);

      this.travelCache = new ArrayList();
      this.travelCache.add(new CacheItem(x, y, 0.0f));
   }

   public boolean getTripPosition(float totalTrip, float[] coords)
   {
      boolean isValid = true;

      CacheItem last = this.travelCache.get(this.travelCache.size() - 1);

      // build cache
      while (last.travelled < totalTrip)
      {
         if (totalTrip == 0.0f)
         {
            // don't even bother
            break;
         }

         float travel = Math.min(totalTrip - last.travelled, maxTravelStep);

         CacheItem curr = this.getSteppingPosition(last.position, travel, posStep);

         if (curr.position >= this.count)
         {
            // reached end of spline
            isValid = false;
            break;
         }

         // only cache if we travelled far enough
         if (curr.travelled > this.maxTravelStep * 0.95f)
         {
            this.travelCache.add(curr);
         }

         curr.travelled += last.travelled;

         last = curr;
      }

      // figure out position

      int lo = 0;
      int hi = this.travelCache.size() - 1;

      while (true)
      {
         int mid = (lo + hi) / 2;

         last = this.travelCache.get(mid);

         if (last.travelled < totalTrip)
         {
            if (lo == mid)
               break;
            lo = mid;
         }
         else
         {
            if (hi == mid)
               break;
            hi = mid;
         }
      }

      for (int i = lo; i <= hi; i++)
      {
         CacheItem item = this.travelCache.get(i);

         if (item.travelled <= totalTrip)
         {
            last = item;
         }
         else
         {
            break;
         }
      }

      float travel = totalTrip - last.travelled;
      last = this.getSteppingPosition(last.position, travel, posStep);
      coords[0] = last.xpos;
      coords[1] = last.ypos;

      return isValid;
   }

   private CacheItem getSteppingPosition(float posOffset, float travel, float segmentStep)
   {
      float pos = posOffset;
      float[] last = this.getPositionAt(pos);

      float travelled = 0.0f;

      while (travelled < travel && pos < this.count)
      {
         float[] curr = this.getPositionAt(pos += segmentStep);
         travelled += Spline2D.dist(last, curr);
         last = curr;
      }

      CacheItem item = new CacheItem(last[0], last[1], 0.0f);
      item.position = pos;
      item.travelled = travelled;
      return item;
   }

   private static float dist(float[] a, float[] b)
   {
      float dx = b[0] - a[0];
      float dy = b[1] - a[1];

      return (float) Math.sqrt(dx * dx + dy * dy);
   }

   /**
    * CURVE CLASS
    */

   private static class Curve
   {
      static final Cubic[] calcCurve(int n, float[] axis)
      {
         float[] gamma = new float[n + 1];
         float[] delta = new float[n + 1];
         float[] d = new float[n + 1];
         Cubic[] c = new Cubic[n + 0];

         // gamma
         gamma[0] = 0.5f;
         for (int i = 1; i < n; i++)
            gamma[i] = 1.0f / (4.0f - gamma[i - 1]);
         gamma[n] = 1.0f / (2.0f - gamma[n - 1]);

         // delta
         delta[0] = 3.0f * (axis[1] - axis[0]) * gamma[0];
         for (int i = 1; i < n; i++)
            delta[i] = (3.0f * (axis[i + 1] - axis[i - 1]) - delta[i - 1]) * gamma[i];
         delta[n] = (3.0f * (axis[n] - axis[n - 1]) - delta[n - 1]) * gamma[n];

         // d
         d[n] = delta[n];
         for (int i = n - 1; i >= 0; i--)
            d[i] = delta[i] - gamma[i] * d[i + 1];

         // c
         for (int i = 0; i < n; i++)
         {
            float x0 = axis[i + 0];
            float x1 = axis[i + 1];
            float d0 = d[i + 0];
            float d1 = d[i + 1];
            c[i] = new Cubic(x0, d0, 3.0f * (x1 - x0) - 2.0f * d0 - d1, 2.0f * (x0 - x1) + d0 + d1);
         }
         return c;
      }
   }

   /**
    * CUBIC CLASS
    */

   static class Cubic
   {
      private final float a, b, c, d;

      Cubic(float a, float b, float c, float d)
      {
         this.a = a;
         this.b = b;
         this.c = c;
         this.d = d;
      }

      final float eval(float u)
      {
         return (((d * u) + c) * u + b) * u + a;
      }
   }
}

Spline :: 3D

2009-08-25T01:32:00.002+02:00

public class Spline3D
{
   public Spline3D(float[][] points)
   {
      count = points.length;

      float[] x = new float[count];
      float[] y = new float[count];
      float[] z = new float[count];

      for (int i = 0; i < count; i++)
      {
         x[i] = points[i][0];
         y[i] = points[i][1];
         z[i] = points[i][2];
      }

      this.x = Curve.calcCurve(count - 1, x);
      this.y = Curve.calcCurve(count - 1, y);
      this.z = Curve.calcCurve(count - 1, z);
   }

   final int count;
   private final Cubic[] x, y, z;

   /**
    * POINT COUNT
    */

   public final int pointCount()
   {
      return count;
   }

   /**
    * POSITION
    */

   public final float[] getPositionAt(float param)
   {
      float[] v = new float[3];
      this.getPositionAt(param, v);
      return v;
   }

   public final void getPositionAt(float param, float[] result)
   {
      // clamp
      if (param < 0.0f)
         param = 0.0f;
      if (param >= count - 1)
         param = (count - 1) - Math.ulp(count - 1);

      // split
      int ti = (int) param;
      float tf = param - ti;

      // eval
      result[0] = x[ti].eval(tf);
      result[1] = y[ti].eval(tf);
      result[2] = z[ti].eval(tf);
   }

   private List travelCache;
   private float           maxTravelStep;
   private float           posStep;

   public void enabledTripCaching(float maxTravelStep, float posStep)
   {
      this.maxTravelStep = maxTravelStep;
      this.posStep = posStep;

      float x = this.x[0].eval(0.0f);
      float y = this.y[0].eval(0.0f);
      float z = this.z[0].eval(0.0f);

      this.travelCache = new ArrayList();
      this.travelCache.add(new CacheItem(x, y, z));
   }

   public float[] getTripPosition(float totalTrip)
   {
      CacheItem last = this.travelCache.get(this.travelCache.size() - 1);

      // build cache
      while (last.travelled < totalTrip)
      {
         if (totalTrip == 0.0f)
         {
            // don't even bother
            break;
         }

         float travel = Math.min(totalTrip - last.travelled, maxTravelStep);

         CacheItem curr = this.getSteppingPosition(last.position, travel, posStep);

         if (curr.position >= this.count)
         {
            // reached end of spline
            break;
         }

         // only cache if we travelled far enough
         if (curr.travelled > this.maxTravelStep * 0.95f)
         {
            this.travelCache.add(curr);
         }

         curr.travelled += last.travelled;

         last = curr;
      }

      // figure out position

      int lo = 0;
      int hi = this.travelCache.size() - 1;

      while (true)
      {
         int mid = (lo + hi) / 2;

         last = this.travelCache.get(mid);

         if (last.travelled < totalTrip)
         {
            if (lo == mid)
               break;
            lo = mid;
         }
         else
         {
            if (hi == mid)
               break;
            hi = mid;
         }
      }

      for (int i = lo; i <= hi; i++)
      {
         CacheItem item = this.travelCache.get(i);

         if (item.travelled <= totalTrip)
         {
            last = item;
         }
         else
         {
            break;
         }
      }

      float travel = totalTrip - last.travelled;
      last = this.getSteppingPosition(last.position, travel, posStep);
      return new float[] { last.xpos, last.ypos };
   }

   private CacheItem getSteppingPosition(float posOffset, float travel, float segmentStep)
   {
      float pos = posOffset;
      float[] last = this.getPositionAt(pos);

      float travelled = 0.0f;

      while (travelled < travel && pos < this.count)
      {
         float[] curr = this.getPositionAt(pos += segmentStep);
         travelled += Spline3D.dist(last, curr);
         last = curr;
      }

      CacheItem item = new CacheItem(last[0], last[1], last[2]);
      item.position = pos;
      item.travelled = travelled;
      return item;
   }

   private static float dist(float[] a, float[] b)
   {
      float dx = b[0] - a[0];
      float dy = b[1] - a[1];
      float dz = b[2] - a[2];

      return (float) Math.sqrt(dx * dx + dy * dy + dz * dz);
   }

   /**
    * CURVE CLASS
    */

   private static class Curve
   {
      static final Cubic[] calcCurve(int n, float[] axis)
      {
         float[] gamma = new float[n + 1];
         float[] delta = new float[n + 1];
         float[] d = new float[n + 1];
         Cubic[] c = new Cubic[n];

         // gamma
         gamma[0] = 0.5F;
         for (int i = 1; i < n; i++)
            gamma[i] = 1.0F / (4.0F - gamma[i - 1]);
         gamma[n] = 1.0F / (2.0F - gamma[n - 1]);

         // delta
         delta[0] = 3.0F * (axis[1] - axis[0]) * gamma[0];
         for (int i = 1; i < n; i++)
            delta[i] = (3.0F * (axis[i + 1] - axis[i - 1]) - delta[i - 1]) * gamma[i];
         delta[n] = (3.0F * (axis[n] - axis[n - 1]) - delta[n - 1]) * gamma[n];

         // d
         d[n] = delta[n];
         for (int i = n - 1; i >= 0; i--)
            d[i] = delta[i] - gamma[i] * d[i + 1];

         // c
         for (int i = 0; i < n; i++)
         {
            float x0 = axis[i];
            float x1 = axis[i + 1];
            float d0 = d[i];
            float d1 = d[i + 1];
            c[i] = new Cubic(x0, d0, 3.0F * (x1 - x0) - 2.0F * d0 - d1, 2.0F * (x0 - x1) + d0 + d1);
         }
         return c;
      }
   }

   /**
    * CUBIC CLASS
    */

   static class Cubic
   {
      private final float a, b, c, d;

      Cubic(float a, float b, float c, float d)
      {
         this.a = a;
         this.b = b;
         this.c = c;
         this.d = d;
      }

      final float eval(float u)
      {
         return (((d * u) + c) * u + b) * u + a;
      }
   }
}

BezierCurve :: 2D

2009-08-25T01:28:00.003+02:00

public class BezierCurve
{
   public static Vec2 interpolate4(float t, Vec2 p1, Vec2 p2, Vec2 p3, Vec2 p4)
   {
      float invT = 1.0f - t;

      float m1 = pow3(invT) * 1.0f * pow0(t);
      float m2 = pow2(invT) * 3.0f * pow1(t);
      float m3 = pow1(invT) * 3.0f * pow2(t);
      float m4 = pow0(invT) * 1.0f * pow3(t);

      float x = 0.0f;
      float y = 0.0f;

      x += p1.x * m1;
      y += p1.y * m1;

      x += p2.x * m2;
      y += p2.y * m2;

      x += p3.x * m3;
      y += p3.y * m3;

      x += p4.x * m4;
      y += p4.y * m4;

      return new Vec2(x, y);
   }

   public static Vec2 interpolate(float t, Vec2... ps)
   {
      float x = 0.0f;
      float y = 0.0f;

      final int n = ps.length - 1;

      for (int k = 0; k <= n; k++)
      {
         float m = pow(1.0f - t, n - k) * coeff(n, k) * pow(t, k);

         x += ps[k].x * m;
         y += ps[k].y * m;
      }

      return new Vec2(x, y);
   }

  @SuppressWarnings("unused")
   private static float pow0(float t)
   {
      return 1.0f;
   }

   private static float pow1(float t)
   {
      return t;
   }

   private static float pow2(float t)
   {
      return t * t;
   }

   private static float pow3(float t)
   {
      return t * t * t;
   }

   private static float pow(float t, int times)
   {
      float tt = 1.0f;
      for (int i = 0; i < times; i++)
         tt *= t;
      return tt;
   }

   private static float coeff(int n, int k)
   {
      return (float) (fact(n) / (fact(k) * fact(n - k)));
   }

   private static double fact(int n)
   {
      double val = 1.0;
      for (int i = 2; i <= n; i++)
         val *= i;
      return val;
   }
}

Image :: alpha / write jpg

2009-08-25T01:22:00.006+02:00

public class ImageUtil
{
   public static void makeTransparant(BufferedImage img)
   {
      Graphics2D g = img.createGraphics();
      g.setComposite(AlphaComposite.getInstance(AlphaComposite.CLEAR, 0.0f));
      g.fillRect(0, 0, img.getWidth(), img.getHeight());
      g.dispose();
   }

   public static void writeJPG(BufferedImage img, File file, float quality) throws IOException
   {
      Iterator iter = ImageIO.getImageWritersByFormatName("jpeg");
      ImageWriter writer = iter.next();
      ImageWriteParam iwp = writer.getDefaultWriteParam();
      iwp.setCompressionMode(ImageWriteParam.MODE_EXPLICIT);
      iwp.setCompressionQuality(quality);

      FileImageOutputStream output = new FileImageOutputStream(file);
      writer.setOutput(output);
      IIOImage image = new IIOImage(img, null, null);
      writer.write(null, image, iwp);
      writer.dispose();
      output.close();
   }
}

Image :: mipmap with gamma

2009-08-25T01:18:00.009+02:00

Most people don't realize that when you scale down an image, the gamma changes. For those who care, here is the code to fixy fixy:

public class ImageUtil
{
   public static BufferedImage mipmapGammaCorrected(
                     BufferedImage src,
                     int level)
   {
      if (level < 1)
      {
         throw new IllegalArgumentException();
      }

      for (int i = 0; i < level; i++)
      {
         BufferedImage tmp = mipmapGammaCorrected(src);
         if (i != 0)
            src.flush(); // do not flush argument
         src = tmp;
      }
      return src;
   }

   public static BufferedImage mipmapGammaCorrected(BufferedImage src)
   {
      int wSrc = src.getWidth();
      int hSrc = src.getHeight();

      if (wSrc % 2 != 0 || hSrc % 2 != 0)
      {
         throw new IllegalStateException("dimensions must be multiple of 2");
      }

      int wDst = wSrc / 2;
      int hDst = hSrc / 2;

      int[] argbFull = src.getRGB(0, 0, wSrc, hSrc, null, 0, wSrc);

      int type = BufferedImage.TYPE_INT_RGB;
      if (src.getAlphaRaster() != null)
      {
         type = BufferedImage.TYPE_INT_ARGB;

         // merge alpha into RGB values
         int[] alphaFull = src.getAlphaRaster().getPixels(0, 0, wSrc, hSrc, (int[]) null);
         for (int i = 0; i < alphaFull.length; i++)
         {
            argbFull[i] = (alphaFull[i] << 24) | (argbFull[i] & 0x00FFFFFF);
         }
      }

      BufferedImage half = new BufferedImage(wDst, hDst, type);

      int[] argbHalf = new int[argbFull.length >>> 2];

      for (int y = 0; y < hDst; y++)
      {
         for (int x = 0; x < wDst; x++)
         {
            int p0 = argbFull[((y << 1) | 0) * wSrc + ((x << 1) | 0)];
            int p1 = argbFull[((y << 1) | 1) * wSrc + ((x << 1) | 0)];
            int p2 = argbFull[((y << 1) | 1) * wSrc + ((x << 1) | 1)];
            int p3 = argbFull[((y << 1) | 0) * wSrc + ((x << 1) | 1)];

            int a = gammaCorrectedAverage(p0, p1, p2, p3, 24);
            int r = gammaCorrectedAverage(p0, p1, p2, p3, 16);
            int g = gammaCorrectedAverage(p0, p1, p2, p3, 8);
            int b = gammaCorrectedAverage(p0, p1, p2, p3, 0);

            argbHalf[y * wDst + x] = (a << 24) | (r << 16) | (g << 8) | (b << 0);
         }
      }

      half.setRGB(0, 0, wDst, hDst, argbHalf, 0, wDst);
      if (type == BufferedImage.TYPE_INT_ARGB)
      {
         // extract alpha from ARGB values
         int[] alpha = new int[argbHalf.length];
         for (int i = 0; i < alpha.length; i++)
            alpha[i] = (argbHalf[i] >> 24) & 0xFF;
         half.getAlphaRaster().setPixels(0, 0, wDst, hDst, alpha);
      }

      return half;
   }

   static int gammaCorrectedAverage(int a, int b, int c, int d, int shift)
   {
      float x = ((a >> shift) & 0xFF) / 255.0f;
      float y = ((b >> shift) & 0xFF) / 255.0f;
      float z = ((c >> shift) & 0xFF) / 255.0f;
      float w = ((d >> shift) & 0xFF) / 255.0f;

      float e = x * x + y * y + z * z + w * w;
      e = (float) Math.sqrt(e * 0.25f);
      return (int) (e * 255.0f);
   }
}

Verlet :: collision math / spring

2009-08-25T00:46:00.006+02:00

Below is the code to do the actual collisions, verlet style. You might scratch your head and wonder how such basic math will handle all your physics. In reality it simply won't: it will only get more or less realistic when you start connecting lots of particles with lots of springs to create a representation of physical bodies.

With physics, it's all about how you structure your data. You don't want to collide everything against everything. How to design and optimize a spatial datastructure is left as an exercise to the reader. Such code is too big to post.

public class VerletMath
{
   // plane <--> sphere

   public static final boolean collides(VerletPlane a, VerletSphere b)
   {
      float dx = b.particle.now.x - a.nx * a.d;
      float dy = b.particle.now.y - a.ny * a.d;
      float dz = b.particle.now.z - a.nz * a.d;

      return ((a.nx * dx) + (a.ny * dy) + (a.nz * dz) - b.radius) < 0.0f;
   }

   public static final float collide(VerletPlane a, VerletSphere b)
   {
      float bx = b.particle.now.x;
      float by = b.particle.now.y;
      float bz = b.particle.now.z;
      float bd = b.radius;

      float dx = bx - a.nx * a.d;
      float dy = by - a.ny * a.d;
      float dz = bz - a.nz * a.d;

      float dst = (a.nx * dx) + (a.ny * dy) + (a.nz * dz) - bd;
      if (dst >= 0.0f)
         return 0.0f;

      // impl true bounce, using speed
      // push out along normal of plane

      b.particle.now.x = bx - dst * a.nx;
      b.particle.now.y = by - dst * a.ny;
      b.particle.now.z = bz - dst * a.nz;

      return -dst;
   }

   // sphere <--> sphere

   public static final void collide(VerletSphere target, Bag<VerletSphere> all)
   {
      int size = all.size();

      for (int i = 0; i < size; i++)
      {
         VerletSphere sphere = all.get(i);

         if (VerletMath.collides(sphere, target))
         {
            VerletMath.collide(sphere, target);
         }
      }
   }

   public static final boolean collides(VerletSphere a, VerletSphere b)
   {
      Vec3 va = a.particle.now;
      Vec3 vb = b.particle.now;
      float d = a.radius + b.radius;

      float x = va.x - vb.x;
      float y = va.y - vb.y;
      float z = va.z - vb.z;

      return (x * x + y * y + z * z) < (d * d);
   }

   public static final float collide(VerletSphere a, VerletSphere b)
   {
      Vec3 anow = a.particle.now;
      Vec3 bnow = b.particle.now;

      float ax = anow.x;
      float ay = anow.y;
      float az = anow.z;
      float aiw = a.particle.invWeight;

      float bx = bnow.x;
      float by = bnow.y;
      float bz = bnow.z;
      float biw = b.particle.invWeight;

      float dx = bx - ax;
      float dy = by - ay;
      float dz = bz - az;
      float d2 = dx * dx + dy * dy + dz * dz;

      if (d2 <= ulp_zero)
      {
         // sharing position, oh oh!
         // big problem! if we collide
         // it, it will explode 
         return 0.0f;
      }

      float dMin = a.radius + b.radius;
      if (d2 > (dMin * dMin))
         return 0.0f;

      // apply spring -> push out of eachother

      //final float tension = 1.0f;
      float d = (float) Math.sqrt(d2);
      float f = (d - dMin) / dMin * 0.5f;//* tension;

      float f1 = f * aiw / (aiw + biw);
      anow.x = ax + dx * f1;
      anow.y = ay + dy * f1;
      anow.z = az + dz * f1;

      float f2 = f * biw / (aiw + biw);
      bnow.x = bx - dx * f2;
      bnow.y = by - dy * f2;
      bnow.z = bz - dz * f2;

      return (dMin - d);
   }

   private static final float ulp_zero = Math.ulp(0.0f);
}

public class VerletSpring
{
   public static final int FIXED_LENGTH = 0;
   public static final int MIN_LENGTH   = 1;
   public static final int MAX_LENGTH   = 2;

   //

   public final VerletParticle a, b;

   public float                len, stf;
   public int                  how;

   public VerletSpring(VerletParticle a, VerletParticle b)
   {
      this.a = a;
      this.b = b;
   }

   //

   public final float setCurrentDistanceAsLength()
   {
      float dx = b.now.x - a.now.x;
      float dy = b.now.y - a.now.y;
      float dz = b.now.z - a.now.z;
      float d = (float) Math.sqrt(dx * dx + dy * dy + dz * dz);

      this.len = d;

      return d;
   }

   public final float tick()
   {
      float ax = a.now.x;
      float ay = a.now.y;
      float az = a.now.z;

      float bx = b.now.x;
      float by = b.now.y;
      float bz = b.now.z;

      float dx = ax - bx;
      float dy = ay - by;
      float dz = az - bz;
      float dist = (float) Math.sqrt(dx * dx + dy * dy + dz * dz);

      if (how == MIN_LENGTH)
      {
         if (dist > len)
            return 0.0f;
      }
      else if (how == MAX_LENGTH)
      {
         if (dist < len)
            return 0.0f;
      }

      float tension = (len - dist) / dist;
      float force = tension * this.stf;

      float aw = a.invWeight;
      float bw = b.invWeight;

      float f1 = force * aw / (aw + bw);
      float f2 = force * bw / (aw + bw);

      a.now.x = ax + dx * f1;
      a.now.y = ay + dy * f1;
      a.now.z = az + dz * f1;

      b.now.x = bx - dx * f2;
      b.now.y = by - dy * f2;
      b.now.z = bz - dz * f2;

      return tension;
   }
}

Verlet :: particle/sphere/plane

2009-08-25T00:39:00.002+02:00

public class VerletParticle
{
   public final Vec3 now, old;
   public float      invWeight;

   public VerletParticle()
   {
      this.old = new Vec3();
      this.now = new Vec3();
      this.invWeight = 1.0f;
   }
   
   public void setInfiniteWeight()
   {
      this.invWeight = 0.0f;
   }

   public void setWeight(float weight)
   {
      this.invWeight = 1.0f / weight;
   }

   //

   public final void setPosition(Vec3 vec)
   {
      this.setPosition(vec.x, vec.y, vec.z);
   }

   public final void setPosition(float x, float y, float z)
   {
      float xVel = now.x - old.x;
      float yVel = now.y - old.y;
      float zVel = now.z - old.z;

      now.x = x;
      now.y = y;
      now.z = z;

      old.x = x - xVel;
      old.y = y - yVel;
      old.z = z - zVel;
   }

   public final void getPosition(Vec3 vec)
   {
      vec.x = now.x;
      vec.y = now.y;
      vec.z = now.z;
   }

   //

   public void translate(Vec3 vec)
   {
      this.translate(vec.x, vec.y, vec.z);
   }

   public void translate(float x, float y, float z)
   {
      this.setPosition(now.x + x, now.y + y, now.z + z);
   }

   //

   public final void addForce(Vec3 vec)
   {
      this.addForce(vec.x, vec.y, vec.z);
   }

   public final void addForce(float x, float y, float z)
   {
      this.addVelocity(x * invWeight, y * invWeight, z * invWeight);
   }

   //

   public final void setVelocity(Vec3 vec)
   {
      this.setVelocity(vec.x, vec.y, vec.z);
   }

   public final void setVelocity(float x, float y, float z)
   {
      old.x = now.x - x;
      old.y = now.y - y;
      old.z = now.z - z;
   }

   public final void addVelocity(float x, float y, float z)
   {
      old.x = old.x - x;
      old.y = old.y - y;
      old.z = old.z - z;
   }

   public final void getVelocity(Vec3 vec)
   {
      vec.x = now.x - old.x;
      vec.y = now.y - old.y;
      vec.z = now.z - old.z;
   }

   public final void mulVelocity(float factor)
   {
      float xNow = now.x;
      float yNow = now.y;
      float zNow = now.z;

      old.x = xNow - (xNow - old.x) * factor;
      old.y = yNow - (yNow - old.y) * factor;
      old.z = zNow - (zNow - old.z) * factor;
   }

   //

   public final void tick()
   {
      float xOld = old.x;
      float yOld = old.y;
      float zOld = old.z;

      old.x = now.x;
      old.y = now.y;
      old.z = now.z;

      now.x += now.x - xOld;
      now.y += now.y - yOld;
      now.z += now.z - zOld;
   }
}

public class VerletPlane
{
   public float nx, ny, nz, d;

   public final void inferValues(Vec3 src, Vec3 dst)
   {
      float nx = dst.x - src.x;
      float ny = dst.y - src.y;
      float nz = dst.z - src.z;

      float d = (float) Math.sqrt(nx * nx + ny * ny + nz * nz);
      nx /= d;
      ny /= d;
      nz /= d;

      float d2 = VecMath.dot(src, src);
      d2 = (d2 == 0.0f) ? 1.0f : (float) Math.sqrt(d2);
      float nx2 = src.x / d2;
      float ny2 = src.y / d2;
      float nz2 = src.z / d2;

      d2 *= nx * nx2 + ny * ny2 + nz * nz2;

      this.nx = nx;
      this.ny = ny;
      this.nz = nz;
      this.d = d2;
   }

   public final static VerletPlane infer(Vec3 src, Vec3 dst)
   {
      VerletPlane plane = new VerletPlane();
      plane.inferValues(src, dst);
      return plane;
   }
}

public class VerletSphere
{
   public final VerletParticle particle;
   public float                radius;
   public float                invFriction = 0.1f;
   public float                drag        = 0.0f;

   public VerletSphere(float rad)
   {
      this(new VerletParticle(), rad);
   }

   public VerletSphere(VerletParticle p, float rad)
   {
      this.particle = p;
      this.radius = rad;
   }

   public void setFriction(float friction)
   {
      this.invFriction = 1.0f - friction;
   }

   public VerletParticle getParticle()
   {
      return particle;
   }
}

Color :: HSL <> RGB

2009-08-25T00:23:00.005+02:00

Hue Saturation Lightness (not to be confused with Hue Saturation Brightness) should be imagined as a double cone. The top of the upper-cone will be white. The bottom of the lower-cone will be black. The circle (where the cones touch) has the full range of colors in the rainbow, the center is gray.

Vertical axis: Lightness [0.0 .. 1.0]
Polar angle: Hue [0.0 .. 1.0] (wraps: 1.2 becomes 0.2)
Polar distance: Saturation [0.0 .. 1.0]

You can grab a RGB pixel, convert to HSL, modify it, and convert it back to RGB. Results are nice. When applied to a specific region of a photo, you can make a single object radically change color. Have fun.

public class ColorHSL
{
   public static final void rgb2hsl(int[] rgb, float[] hsl)
   {
      float R = rgb[0] / 255.0f;
      float G = rgb[1] / 255.0f;
      float B = rgb[2] / 255.0f;

      float MAX = max(R, max(G, B));
      float MIN = min(R, min(G, B));
      float H, L, S;

      if (MIN == MAX)
         H = 0.0f;
      else if (R == MAX)
         H = 0.16666666f * ((G - B) / (MAX - MIN)) + 0.00000000f;
      else if (G == MAX)
         H = 0.16666666f * ((B - R) / (MAX - MIN)) + 0.33333333f;
      else
         H = 0.16666666f * ((R - G) / (MAX - MIN)) + 0.66666666f;

      L = 0.5f * (MIN + MAX);
      if (L == 0.0f || (MIN == MAX))
         S = 0.0f;
      else if (L <= 0.5f)
         S = (MAX - MIN) / (2 * L);
      else
         S = (MAX - MIN) / (2 - 2 * L);

      hsl[0] = absMod(H, 1.0f);
      hsl[1] = S;
      hsl[2] = L;
   }

   public static final int[] hsl2rgb(float[] hsl, int[] rgb)
   {
      float H = hsl[0];
      float S = hsl[1];
      float L = hsl[2];

      float R, G, B;

      if (S == 0.0f)
      {
         R = G = B = L;
      }
      else
      {
         float Q = (L < 0.5f) ? (L * (1.0f + S)) : ((L + S) - (L * S));
         float P = 2.0f * L - Q;
         float Hk = absMod(H, 1.0f);

         R = convert(Q, P, Hk + 0.33333333333f);
         G = convert(Q, P, Hk + 0.00000000000f);
         B = convert(Q, P, Hk - 0.33333333333f);
      }

      rgb[0] = (int) (clamp(R, 0.0f, 1.0f) * 255.0f);
      rgb[1] = (int) (clamp(G, 0.0f, 1.0f) * 255.0f);
      rgb[2] = (int) (clamp(B, 0.0f, 1.0f) * 255.0f);

      return rgb;
   }

   private static final float convert(float Q, float P, float Tx)
   {
      Tx = absMod(Tx, 1.0f);
      if (Tx < 1.0f / 6.0f)
         return P + ((Q - P) * 6.0f * Tx);
      if (Tx < 3.0f / 6.0f)
         return Q;
      if (Tx < 4.0f / 6.0f)
         return P + ((Q - P) * 6.0f * (4.0f / 6.0f - Tx));
      return P;
   }

   public static final float absMod(float val, float max)
   {
      return ((val % max) + max) % max;
   }

   public static final float clamp(float cur, float min, float max)
   {
      return (cur < min ? min : (cur > max ? max : cur));
   }
}

PerlinNoise :: smooth/turbulent

2009-08-25T00:03:00.002+02:00

Nothing too fancy. Copy and paste if you need it.

public class PerlinNoise
{
   private float xo, yo, zo;

   public final void offset(float x, float y, float z)
   {
      this.xo = x;
      this.yo = y;
      this.zo = z;
   }

   public final float smoothNoise(float x, float y, float z, int octaves)
   {
      float height = 0.0f;
      for (int octave = 1; octave <= octaves; octave++)
         height += noise(x, y, z, octave);
      return height;
   }

   public final float turbulentNoise(float x, float y, float z, int octaves)
   {
      float height = 0.0f;
      for (int octave = 1; octave <= octaves; octave++)
      {
         float h = noise(x0, y0, z0, octave);
         if (h < 0.0f) h *= -1.0f;
         height += h;
      }
      return height;
   }

   public final float noise(float x, float y, float z)
   {
      float fx = floor(x);
      float fy = floor(y);
      float fz = floor(z);

      int gx = (int) fx & 0xFF;
      int gy = (int) fy & 0xFF;
      int gz = (int) fz & 0xFF;

      float u = fade(x -= fx);
      float v = fade(y -= fy);
      float w = fade(z -= fz);

      int a0 = perm[gx + 0] + gy;
      int b0 = perm[gx + 1] + gy;
      int aa = perm[a0 + 0] + gz;
      int ab = perm[a0 + 1] + gz;
      int ba = perm[b0 + 0] + gz;
      int bb = perm[b0 + 1] + gz;

      float a1 = grad(perm[bb + 1], x - 1, y - 1, z - 1);
      float a2 = grad(perm[ab + 1], x - 0, y - 1, z - 1);
      float a3 = grad(perm[ba + 1], x - 1, y - 0, z - 1);
      float a4 = grad(perm[aa + 1], x - 0, y - 0, z - 1);
      float a5 = grad(perm[bb + 0], x - 1, y - 1, z - 0);
      float a6 = grad(perm[ab + 0], x - 0, y - 1, z - 0);
      float a7 = grad(perm[ba + 0], x - 1, y - 0, z - 0);
      float a8 = grad(perm[aa + 0], x - 0, y - 0, z - 0);

      float a2_1 = lerp(u, a2, a1);
      float a4_3 = lerp(u, a4, a3);
      float a6_5 = lerp(u, a6, a5);
      float a8_7 = lerp(u, a8, a7);
      float a8_5 = lerp(v, a8_7, a6_5);
      float a4_1 = lerp(v, a4_3, a2_1);
      float a8_1 = lerp(w, a8_5, a4_1);

      return a8_1;
   }

   //

   private final float noise(float x, float y, float z, int octave)
   {
      float p = pow[octave];
      return this.noise(x * p + this.xo, y * p + this.yo, z * p + this.zo) / p;
   }

   private static final float floor(float v)
   {
      return (int) v;
   }

   private static final float fade(float t)
   {
      return t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f);
   }

   private static final float lerp(float t, float a, float b)
   {
      return a + t * (b - a);
   }

   private static final float grad(int hash, float x, float y, float z)
   {
      int h = hash & 15;
      float u = (h < 8) ? x : y;
      float v = (h < 4) ? y : ((h == 12 || h == 14) ? x : z);
      return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
   }

   private static final float[] pow  = new float[32];

   private static final int[]   perm = new int[512];

   static
   {
      for (int i = 0; i < pow.length; i++)
      {
         pow[i] = (float) Math.pow(2, i);
      }

      int[] permutation = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145, 235, 249,
         14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180 };

      if (permutation.length != 256)
         throw new IllegalStateException();

      for (int i = 0; i < 256; i++)
         perm[256 + i] = perm[i] = permutation[i];
   }
}

Bag :: fast insert, fast remove

2009-08-24T23:24:00.004+02:00

This Bag is an unordered list. Putting an element will append it to the backing array. Taking an element will move the last element in the array to the index of the element to be taken, nulling the last index. You get the elements by their index. There's not much too it.

The primary focus is on performance of inserting and removing from small collections.

import java.util.Arrays;
import java.util.NoSuchElementException;

public class Bag
{
   private T[] data;
   private int size;

   public Bag()
   {
      this(4);
   }

   public Bag(int space)
   {
      this.data = (T[]) new Object[space];
   }

   public void put(T t)
   {
      if (this.size == this.data.length)
      {
         this.data = Arrays.copyOf(this.data, Math.max((int) (this.size * 1.75f), 8));
      }

      this.data[size++] = t;
   }

   public void putAll(Bag bag)
   {
      if (bag.size == 0)
         return;

      int reqSize = this.size + bag.size;
      if (this.data.length < reqSize)
      {
         // calculate new length
         int makeSize = this.data.length;
         while (makeSize < reqSize)
            makeSize = Math.max((int) (makeSize * 1.75f), 8);

         // create array, copy elements
         this.data = Arrays.copyOf(this.data, makeSize);
      }

      // copy 'remote' elements to own array
      System.arraycopy(bag.data, 0, this.data, this.size, bag.size);
      this.size += bag.size;
   }

   public T get(int i)
   {
      if (i >= size)
         throw new ArrayIndexOutOfBoundsException();
      return data[i];
   }

   public T take(int i)
   {
      if (i >= size)
         throw new ArrayIndexOutOfBoundsException();

      T took = data[i];
      data[i] = data[--size];
      data[size] = null;
      return took;
   }

   public T take(T t)
   {
      int i = this.indexOf(t);
      if (i == -1)
         throw new NoSuchElementException();
      return this.take(i);
   }

   public void fillArray(T[] holder)
   {
      if (holder == null || holder.length < this.size)
         throw new IllegalStateException();
      System.arraycopy(this.data, 0, holder, 0, size);
   }

   public boolean contains(T t)
   {
      return this.indexOf(t) != -1;
   }

   public int indexOf(T t)
   {
      for (int i = 0; i < size; i++)
         if (data[i] == t)
            return i;
      return -1;
   }

   public void shrink()
   {
      if (this.data.length > 8)
      {
         int factor = 4;

         if (this.size < this.data.length / factor)
         {
            int newSize = Math.max(4, this.size);
            T[] newData = (T[]) new Object[newSize];
            System.arraycopy(this.data, 0, newData, 0, this.size);
            this.data = newData;
         }
      }
   }

   public void clear()
   {
      for (int i = 0; i < size; i++)
         data[i] = null;
      this.size = 0;
   }

   public int capacity()
   {
      return this.data.length;
   }

   public int size()
   {
      return size;
   }
}

FastMath :: atan2 lookup

2009-08-24T23:09:00.006+02:00

Math.atan2() is very convenient, yet very slow. A lookup table will be roughly 8x faster. You lose accuracy, but heck, that's obvious.


   public static final float atan2Deg(float y, float x)
   {
      return FastMath.atan2(y, x) * DEG;
   }

   public static final float atan2DegStrict(float y, float x)
   {
      return (float) Math.atan2(y, x) * DEG;
   }

   public static final float atan2(float y, float x)
   {
      float add, mul;

      if (x < 0.0f)
      {
         if (y < 0.0f)
         {
            x = -x;
            y = -y;

            mul = 1.0f;
         }
         else
         {
            x = -x;
            mul = -1.0f;
         }

         add = -3.141592653f;
      }
      else
      {
         if (y < 0.0f)
         {
            y = -y;
            mul = -1.0f;
         }
         else
         {
            mul = 1.0f;
         }

         add = 0.0f;
      }

      float invDiv = ATAN2_DIM_MINUS_1 / ((x < y) ? y : x);

      int xi = (int) (x * invDiv);
      int yi = (int) (y * invDiv);

      return (atan2[yi * ATAN2_DIM + xi] + add) * mul;
   }


private static final int     ATAN2_BITS        = 7;

   private static final int     ATAN2_BITS2       = ATAN2_BITS << 1;
   private static final int     ATAN2_MASK        = ~(-1 << ATAN2_BITS2);
   private static final int     ATAN2_COUNT       = ATAN2_MASK + 1;
   private static final int     ATAN2_DIM         = (int) Math.sqrt(ATAN2_COUNT);

   private static final float   ATAN2_DIM_MINUS_1 = (ATAN2_DIM - 1);

   private static final float[] atan2             = new float[ATAN2_COUNT];

   static
   {
      for (int i = 0; i < ATAN2_DIM; i++)
      {
         for (int j = 0; j < ATAN2_DIM; j++)
         {
            float x0 = (float) i / ATAN2_DIM;
            float y0 = (float) j / ATAN2_DIM;

            atan2[j * ATAN2_DIM + i] = (float) Math.atan2(y0, x0);
         }
      }
   }

And some test code:

int dim = 633 * 2; // random number times 2

      float maxDiff = 0.0f;
      float sumDiff = 0.0f;

      for (int i = 0; i < dim * dim; i++)
      {
         float x = (float) ((i % dim) - (dim / 2)) / (dim / 2);
         float y = (float) ((i / dim) - (dim / 2)) / (dim / 2);
         float slow = (float) Math.atan2(y, x);
         float fast = FastMath.atan2(y, x);
         float diff = Math.abs(slow - fast);
         if (diff > maxDiff)
            maxDiff = diff;
         sumDiff += diff;
      }

      float avgDiff = sumDiff / (dim * dim);

      System.out.println("maxDiff=" + maxDiff); // 0.007858515
      System.out.println("avgDiff=" + avgDiff); // 0.002910751

FastMath :: sin/cos lookup

2009-08-24T23:06:00.003+02:00

Math.sin() is slow. Using a lookup table for sin/cos is roughly 50x faster. The loss of accuracy is minimal, maximum error is roughly 0,001. You can probably get away with it.

   public static final float sin(float rad)
   {
      return sin[(int) (rad * radToIndex) & SIN_MASK];
   }

   public static final float cos(float rad)
   {
      return cos[(int) (rad * radToIndex) & SIN_MASK];
   }

   public static final float sinDeg(float deg)
   {
      return sin[(int) (deg * degToIndex) & SIN_MASK];
   }

   public static final float cosDeg(float deg)
   {
      return cos[(int) (deg * degToIndex) & SIN_MASK];
   }

   private static final float   RAD,DEG;
   private static final int     SIN_BITS,SIN_MASK,SIN_COUNT;
   private static final float   radFull,radToIndex;
   private static final float   degFull,degToIndex;
   private static final float[] sin, cos;

   static
   {
      RAD = (float) Math.PI / 180.0f;
      DEG = 180.0f / (float) Math.PI;

      SIN_BITS  = 12;
      SIN_MASK  = ~(-1 << SIN_BITS);
      SIN_COUNT = SIN_MASK + 1;

      radFull    = (float) (Math.PI * 2.0);
      degFull    = (float) (360.0);
      radToIndex = SIN_COUNT / radFull;
      degToIndex = SIN_COUNT / degFull;

      sin = new float[SIN_COUNT];
      cos = new float[SIN_COUNT];

      for (int i = 0; i < SIN_COUNT; i++)
      {
         sin[i] = (float) Math.sin((i + 0.5f) / SIN_COUNT * radFull);
         cos[i] = (float) Math.cos((i + 0.5f) / SIN_COUNT * radFull);
      }
   }