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

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!

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

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

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

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

   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

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

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

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

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

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

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

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

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,
                     double gamma)
   {
      if (level < 1)
      {
         throw new IllegalArgumentException();
      }

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

   public static BufferedImage mipmapGammaCorrected(BufferedImage src, double gamma)
   {
      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, gamma);
            int r = gammaCorrectedAverage(p0, p1, p2, p3, 16, gamma);
            int g = gammaCorrectedAverage(p0, p1, p2, p3,  8, gamma);
            int b = gammaCorrectedAverage(p0, p1, p2, p3,  0, gamma);

            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, double gamma)
   {
      double x = Math.pow(((a >> shift) & 0xFF) / 255.0f, gamma);
      double y = Math.pow(((b >> shift) & 0xFF) / 255.0f, gamma);
      double z = Math.pow(((c >> shift) & 0xFF) / 255.0f, gamma);
      double w = Math.pow(((d >> shift) & 0xFF) / 255.0f, gamma);

      return (int) Math.round(Math.pow((x+y+z+w) * 0.25f, 1.0 / gamma) * 255.0);
   }
}

Verlet :: collision math / spring

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

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

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

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

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

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

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);
      }
   }