re-add

git-svn-id: file:///usr/local/projects/SUN/JOGL/git-svn/svn-server-sync/jogl/branches/JOGL_2_SANDBOX@1676 232f8b59-042b-4e1e-8c03-345bb8c30851

7 files changed, 1092 insertions, 0 deletions

diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java
new file mode 100755
index 000000000..acff0aa79
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+/** This interface must be implemented by the end user and is called
+    in response to events like addition of rectangles into the
+    RectanglePacker. It is used both when a full re-layout must be
+    done as well as when the data in the backing store must be copied
+    to a new one. */
+
+public interface BackingStoreManager {
+  public Object allocateBackingStore(int w, int h);
+  public void   deleteBackingStore(Object backingStore);
+
+  /** Notification that expansion of the backing store is about to be
+      done due to addition of the given rectangle. Gives the manager a
+      chance to do some compaction and potentially remove old entries
+      from the backing store, if it acts like a least-recently-used
+      cache. This method receives as argument the number of attempts
+      so far to add the given rectangle. Manager should return true if
+      the RectanglePacker should retry the addition (which may result
+      in this method being called again, with an increased attempt
+      number) or false if the RectanglePacker should just expand the
+      backing store. The caller should not call RectanglePacker.add()
+      in its preExpand() method. */
+  public boolean preExpand(Rect cause, int attemptNumber);
+
+  /** Notification that addition of the given Rect failed because a
+      maximum size was set in the RectanglePacker and the backing
+      store could not be expanded. */
+  public void additionFailed(Rect cause, int attemptNumber);
+
+  /** Notification that movement is starting. */
+  public void beginMovement(Object oldBackingStore, Object newBackingStore);
+
+  /** Tells the manager to move the contents of the given rect from
+      the old location on the old backing store to the new location on
+      the new backing store. The backing stores can be identical in
+      the case of compacting the existing backing store instead of
+      reallocating it. */
+  public void move(Object oldBackingStore,
+                   Rect   oldLocation,
+                   Object newBackingStore,
+                   Rect   newLocation);
+
+  /** Notification that movement is ending. */
+  public void endMovement(Object oldBackingStore, Object newBackingStore);
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/Level.java b/src/classes/com/sun/opengl/impl/packrect/Level.java
new file mode 100755
index 000000000..2ef6cb989
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/Level.java
@@ -0,0 +1,275 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+import java.util.*;
+
+public class Level {
+  private int width;
+  private int height;
+  private int yPos;
+  private LevelSet holder;
+
+  private List/*<Rect>*/ rects = new ArrayList/*<Rect>*/();
+  private List/*<Rect>*/ freeList;
+  private int nextAddX;
+
+  static class RectXComparator implements Comparator {
+    public int compare(Object o1, Object o2) {
+      Rect r1 = (Rect) o1;
+      Rect r2 = (Rect) o2;
+      return r1.x() - r2.x();
+    }
+
+    public boolean equals(Object obj) {
+      return this == obj;
+    }
+  }
+  private static final Comparator rectXComparator = new RectXComparator();
+
+  public Level(int width, int height, int yPos, LevelSet holder) {
+    this.width = width;
+    this.height = height;
+    this.yPos = yPos;
+    this.holder = holder;
+  }
+
+  public int w()    { return width;  }
+  public int h()    { return height; }
+  public int yPos() { return yPos;   }
+
+  /** Tries to add the given rectangle to this level only allowing
+      non-disruptive changes like trivial expansion of the last level
+      in the RectanglePacker and allocation from the free list. More
+      disruptive changes like compaction of the level must be
+      requested explicitly. */
+  public boolean add(Rect rect) {
+    if (rect.h() > height) {
+      // See whether it's worth trying to expand vertically
+      if (nextAddX + rect.w() > width) {
+        return false;
+      }
+
+      // See whether we're the last level and can expand
+      if (!holder.canExpand(this, rect.h())) {
+        return false;
+      }
+
+      // Trivially expand and try the allocation
+      holder.expand(this, height, rect.h());
+      height = rect.h();
+    }
+
+    // See whether we can add at the end
+    if (nextAddX + rect.w() <= width) {
+      rect.setPosition(nextAddX, yPos);
+      rects.add(rect);
+      nextAddX += rect.w();
+      return true;
+    }
+
+    // See whether we can add from the free list
+    if (freeList != null) {
+      Rect candidate = null;
+      for (Iterator iter = freeList.iterator(); iter.hasNext(); ) {
+        Rect cur = (Rect) iter.next();
+        if (cur.canContain(rect)) {
+          candidate = cur;
+          break;
+        }
+      }
+
+      if (candidate != null) {
+        // Remove the candidate from the free list
+        freeList.remove(candidate);
+        // Set up and add the real rect
+        rect.setPosition(candidate.x(), candidate.y());
+        rects.add(rect);
+        // Re-add any remaining free space
+        if (candidate.w() > rect.w()) {
+          candidate.setPosition(candidate.x() + rect.w(), candidate.y());
+          candidate.setSize(candidate.w() - rect.w(), height);
+          freeList.add(candidate);
+        }
+        
+        coalesceFreeList();
+
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+  /** Removes the given Rect from this Level. */
+  public boolean remove(Rect rect) {
+    if (!rects.remove(rect))
+      return false;
+
+    // If this is the rightmost rectangle, instead of adding its space
+    // to the free list, we can just decrease the nextAddX
+    if (rect.maxX() + 1 == nextAddX) {
+      nextAddX -= rect.w();
+    } else {
+      if (freeList == null) {
+        freeList = new ArrayList/*<Rect>*/();
+      }
+      freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null));
+      coalesceFreeList();
+    }
+
+    return true;
+  }
+
+  /** Indicates whether this Level contains no rectangles. */
+  public boolean isEmpty() {
+    return rects.isEmpty();
+  }
+
+  /** Indicates whether this Level could satisfy an allocation request
+      if it were compacted. */
+  public boolean couldAllocateIfCompacted(Rect rect) {
+    if (rect.h() > height)
+      return false;
+    if (freeList == null)
+      return false;
+    int freeListWidth = 0;
+    for (Iterator iter = freeList.iterator(); iter.hasNext(); ) {
+      Rect cur = (Rect) iter.next();
+      freeListWidth += cur.w();
+    }
+    // Add on the remaining space at the end
+    freeListWidth += (width - nextAddX);
+    return (freeListWidth >= rect.w());
+  }
+
+  public void compact(Object backingStore, BackingStoreManager manager) {
+    Collections.sort(rects, rectXComparator);
+    int nextCompactionDest = 0;
+    manager.beginMovement(backingStore, backingStore);
+    for (Iterator iter = rects.iterator(); iter.hasNext(); ) {
+      Rect cur = (Rect) iter.next();
+      if (cur.x() != nextCompactionDest) {
+        manager.move(backingStore, cur,
+                     backingStore, new Rect(nextCompactionDest, cur.y(), cur.w(), cur.h(), null));
+        cur.setPosition(nextCompactionDest, cur.y());
+      }
+      nextCompactionDest += cur.w();
+    }
+    nextAddX = nextCompactionDest;
+    freeList.clear();
+    manager.endMovement(backingStore, backingStore);
+  }
+
+  public Iterator iterator() {
+    return rects.iterator();
+  }
+
+  /** Visits all Rects contained in this Level. */
+  public void visit(RectVisitor visitor) {
+    for (Iterator iter = rects.iterator(); iter.hasNext(); ) {
+      Rect rect = (Rect) iter.next();
+      visitor.visit(rect);
+    }
+  }
+
+  /** Updates the references to the Rect objects in this Level with
+      the "next locations" of those Rects. This is actually used to
+      update the new Rects in a newly laid-out LevelSet with the
+      original Rects. */
+  public void updateRectangleReferences() {
+    for (int i = 0; i < rects.size(); i++) {
+      Rect cur = (Rect) rects.get(i);
+      Rect next = cur.getNextLocation();
+      next.setPosition(cur.x(), cur.y());
+      if (cur.w() != next.w() || cur.h() != next.h())
+        throw new RuntimeException("Unexpected disparity in rectangle sizes during updateRectangleReferences");
+      rects.set(i, next);
+    }
+  }
+
+  private void coalesceFreeList() {
+    if (freeList == null)
+      return;
+    if (freeList.isEmpty())
+      return;
+
+    // Try to coalesce adjacent free blocks in the free list
+    Collections.sort(freeList, rectXComparator);
+    int i = 0;
+    while (i < freeList.size() - 1) {
+      Rect r1 = (Rect) freeList.get(i);
+      Rect r2 = (Rect) freeList.get(i+1);
+      if (r1.maxX() + 1 == r2.x()) {
+        // Coalesce r1 and r2 into one block
+        freeList.remove(i+1);
+        r1.setSize(r1.w() + r2.w(), r1.h());
+      } else {
+        ++i;
+      }
+    }
+    // See whether the last block bumps up against the addition point
+    Rect last = (Rect) freeList.get(freeList.size() - 1);
+    if (last.maxX() + 1 == nextAddX) {
+      nextAddX -= last.w();
+      freeList.remove(freeList.size() - 1);
+    }
+    if (freeList.isEmpty()) {
+      freeList = null;
+    }
+  }
+
+  //----------------------------------------------------------------------
+  // Debugging functionality
+  //
+
+  public void dumpFreeSpace() {
+    int freeListWidth = 0;
+    for (Iterator iter = freeList.iterator(); iter.hasNext(); ) {
+      Rect cur = (Rect) iter.next();
+      System.err.println(" Free rectangle at " + cur);
+      freeListWidth += cur.w();
+    }
+    // Add on the remaining space at the end
+    System.err.println(" Remaining free space " + (width - nextAddX));
+    freeListWidth += (width - nextAddX);
+    System.err.println(" Total free space " + freeListWidth);
+  }
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java
new file mode 100755
index 000000000..724af27e0
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java
@@ -0,0 +1,213 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+import java.util.*;
+
+/** Manages a list of Levels; this is the core data structure
+    contained within the RectanglePacker and encompasses the storage
+    algorithm for the contained Rects. */
+
+public class LevelSet {
+  // Maintained in sorted order by increasing Y coordinate
+  private List/*<Level>*/ levels = new ArrayList/*<Level>*/();
+  private int nextAddY;
+  private int w;
+  private int h;
+
+  /** A LevelSet manages all of the backing store for a region of a
+      specified width and height. */
+  public LevelSet(int w, int h) {
+    this.w = w;
+    this.h = h;
+  }
+
+  public int w() { return w; }
+  public int h() { return h; }
+
+  /** Returns true if the given rectangle was successfully added to
+      the LevelSet given its current dimensions, false if not. Caller
+      is responsible for performing compaction, expansion, etc. as a
+      consequence. */
+  public boolean add(Rect rect) {
+    if (rect.w() > w)
+      return false;
+
+    // Go in reverse order through the levels seeing whether we can
+    // trivially satisfy the allocation request
+    for (int i = levels.size() - 1; i >= 0; --i) {
+      Level level = (Level) levels.get(i);
+      if (level.add(rect))
+        return true;
+    }
+
+    // See whether compaction could satisfy this allocation. This
+    // increases the computational complexity of the addition process,
+    // but prevents us from expanding unnecessarily.
+    for (int i = levels.size() - 1; i >= 0; --i) {
+      Level level = (Level) levels.get(i);
+      if (level.couldAllocateIfCompacted(rect))
+        return false;
+    }
+
+    // OK, we need to either add a new Level or expand the backing
+    // store. Try to add a new Level.
+    if (nextAddY + rect.h() > h)
+      return false;
+
+    Level newLevel = new Level(w, rect.h(), nextAddY, this);
+    levels.add(newLevel);
+    nextAddY += rect.h();
+    boolean res = newLevel.add(rect);
+    if (!res)
+      throw new RuntimeException("Unexpected failure in addition to new Level");
+    return true;
+  }
+
+  /** Removes the given Rect from this LevelSet. */
+  public boolean remove(Rect rect) {
+    for (int i = levels.size() - 1; i >= 0; --i) {
+      Level level = (Level) levels.get(i);
+      if (level.remove(rect))
+        return true;
+    }
+    
+    return false;
+  }
+
+  /** Allocates the given Rectangle, performing compaction of a Level
+      if necessary. This is the correct fallback path to {@link
+      #add(Rect)} above. Returns true if allocated successfully, false
+      otherwise (indicating the need to expand the backing store). */
+  public boolean compactAndAdd(Rect rect,
+                               Object backingStore,
+                               BackingStoreManager manager) {
+    for (int i = levels.size() - 1; i >= 0; --i) {
+      Level level = (Level) levels.get(i);
+      if (level.couldAllocateIfCompacted(rect)) {
+        level.compact(backingStore, manager);
+        boolean res = level.add(rect);
+        if (!res)
+          throw new RuntimeException("Unexpected failure to add after compaction");
+        return true;
+      }
+    }
+
+    return false;
+  }
+
+  /** Indicates whether it's legal to trivially increase the height of
+      the given Level. This is only possible if it's the last Level
+      added and there's enough room in the backing store. */
+  public boolean canExpand(Level level, int height) {
+    if (levels.isEmpty())
+      return false; // Should not happen
+    if (levels.get(levels.size() - 1) == level &&
+        (h - nextAddY >= height - level.h()))
+      return true;
+    return false;
+  }
+
+  public void expand(Level level, int oldHeight, int newHeight) {
+    nextAddY += (newHeight - oldHeight);
+  }
+
+  /** Gets the used height of the levels in this LevelSet. */
+  public int getUsedHeight() {
+    return nextAddY;
+  }
+
+  /** Sets the height of this LevelSet. It is only legal to reduce the
+      height to greater than or equal to the currently used height. */
+  public void setHeight(int height) throws IllegalArgumentException {
+    if (height < getUsedHeight()) {
+      throw new IllegalArgumentException("May not reduce height below currently used height");
+    }
+    h = height;
+  }
+
+  /** Returns the vertical fragmentation ratio of this LevelSet. This
+      is defined as the ratio of the sum of the heights of all
+      completely empty Levels divided by the overall used height of
+      the LevelSet. A high vertical fragmentation ratio indicates that
+      it may be profitable to perform a compaction. */
+  public float verticalFragmentationRatio() {
+    int freeHeight = 0;
+    int usedHeight = getUsedHeight();
+    if (usedHeight == 0)
+      return 0.0f;
+    for (Iterator iter = iterator(); iter.hasNext(); ) {
+      Level level = (Level) iter.next();
+      if (level.isEmpty()) {
+        freeHeight += level.h();
+      }
+    }
+    return (float) freeHeight / (float) usedHeight;
+  }
+
+  public Iterator iterator() {
+    return levels.iterator();
+  }
+
+  /** Visits all Rects contained in this LevelSet. */
+  public void visit(RectVisitor visitor) {
+    for (Iterator iter = levels.iterator(); iter.hasNext(); ) {
+      Level level = (Level) iter.next();
+      level.visit(visitor);
+    }
+  }
+
+  /** Updates the references to the Rect objects in this LevelSet with
+      the "next locations" of those Rects. This is actually used to
+      update the new Rects in a newly laid-out LevelSet with the
+      original Rects. */
+  public void updateRectangleReferences() {
+    for (Iterator iter = levels.iterator(); iter.hasNext(); ) {
+      Level level = (Level) iter.next();
+      level.updateRectangleReferences();
+    }
+  }
+
+  /** Clears out all Levels stored in this LevelSet. */
+  public void clear() {
+    levels.clear();
+    nextAddY = 0;
+  }
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/Rect.java b/src/classes/com/sun/opengl/impl/packrect/Rect.java
new file mode 100755
index 000000000..c3b6be6da
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/Rect.java
@@ -0,0 +1,170 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+/** Represents a rectangular region on the backing store. The edges of
+    the rectangle are the infinitely thin region between adjacent
+    pixels on the screen. The origin of the rectangle is its
+    upper-left corner. It is inclusive of the pixels on the top and
+    left edges and exclusive of the pixels on the bottom and right
+    edges. For example, a rect at position (0, 0) and of size (1, 1)
+    would include only the pixel at (0, 0). <P>
+
+    Negative coordinates and sizes are not supported, since they make
+    no sense in the context of the packer, which deals only with
+    positively sized regions. <P>
+
+    This class contains a user data field for efficient hookup to
+    external data structures as well as enough other hooks to
+    efficiently plug into the rectangle packer. */
+
+public class Rect {
+  private int x;
+  private int y;
+  private int w;
+  private int h;
+
+  // The level we're currently installed in in the parent
+  // RectanglePacker, or null if not hooked in to the table yet
+  private Level level;
+
+  // The user's object this rectangle represents.
+  private Object userData;
+
+  // Used transiently during re-layout of the backing store (when
+  // there is no room left due either to fragmentation or just being
+  // out of space)
+  private Rect nextLocation;
+  
+  public Rect() {
+    this(null);
+  }
+
+  public Rect(Object userData) {
+    this(0, 0, 0, 0, userData);
+  }
+
+  public Rect(int x, int y, int w, int h, Object userData) {
+    setPosition(x, y);
+    setSize(w, h);
+    setUserData(userData);
+  }
+
+  public int x() { return x; }
+  public int y() { return y; }
+  public int w() { return w; }
+  public int h() { return h; }
+  public Object getUserData() { return userData; }
+  public Rect getNextLocation() { return nextLocation; }
+
+  public void setPosition(int x, int y) {
+    if (x < 0)
+      throw new IllegalArgumentException("Negative x");
+    if (y < 0)
+      throw new IllegalArgumentException("Negative y");
+    this.x = x;
+    this.y = y;
+  }
+
+  public void setSize(int w, int h) throws IllegalArgumentException {
+    if (w < 0)
+      throw new IllegalArgumentException("Negative width");
+    if (h < 0)
+      throw new IllegalArgumentException("Negative height");
+    this.w = w;
+    this.h = h;
+  }
+
+  public void setUserData(Object obj) { userData = obj; }
+  public void setNextLocation(Rect nextLocation) { this.nextLocation = nextLocation; }
+
+  // Helpers for computations.
+
+  /** Returns the maximum x-coordinate contained within this
+      rectangle. Note that this returns a different result than Java
+      2D's rectangles; for a rectangle of position (0, 0) and size (1,
+      1) this will return 0, not 1. Returns -1 if the width of this
+      rectangle is 0. */
+  public int maxX() {
+    if (w() < 1)
+      return -1;
+    return x() + w() - 1;
+  }
+
+  /** Returns the maximum y-coordinate contained within this
+      rectangle. Note that this returns a different result than Java
+      2D's rectangles; for a rectangle of position (0, 0) and size (1,
+      1) this will return 0, not 1. Returns -1 if the height of this
+      rectangle is 0. */
+  public int maxY() {
+    if (h() < 1)
+      return -1;
+    return y() + h() - 1;
+  }
+
+  public boolean canContain(Rect other) {
+    return (w() >= other.w() &&
+            h() >= other.h());
+  }
+
+  public String toString() {
+    return "[Rect x: " + x() + " y: " + y() + " w: " + w() + " h: " + h() + "]";
+  }
+
+  // Unclear whether it's a good idea to override hashCode and equals
+  // for these objects
+  /*
+  public boolean equals(Object other) {
+    if (other == null || (!(other instanceof Rect))) {
+      return false;
+    }
+
+    Rect r = (Rect) other;
+    return (this.x() == r.x() &&
+            this.y() == r.y() &&
+            this.w() == r.w() &&
+            this.h() == r.h());
+  }
+
+  public int hashCode() {
+    return (x + y * 13 + w * 17 + h * 23);
+  }
+  */
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/RectVisitor.java b/src/classes/com/sun/opengl/impl/packrect/RectVisitor.java
new file mode 100755
index 000000000..9fd253d43
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/RectVisitor.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+/** Iteration construct without exposing the internals of the
+    RectanglePacker and without implementing a complex Iterator. */
+
+public interface RectVisitor {
+  public void visit(Rect rect);
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java
new file mode 100755
index 000000000..f795fe00a
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java
@@ -0,0 +1,295 @@
+/*
+ * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ * 
+ * - Redistribution of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ * - Redistribution in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * 
+ * Neither the name of Sun Microsystems, Inc. or the names of
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ * 
+ * This software is provided "AS IS," without a warranty of any kind. ALL
+ * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
+ * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
+ * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
+ * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR
+ * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR
+ * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
+ * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
+ * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
+ * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ * 
+ * You acknowledge that this software is not designed or intended for use
+ * in the design, construction, operation or maintenance of any nuclear
+ * facility.
+ * 
+ * Sun gratefully acknowledges that this software was originally authored
+ * and developed by Kenneth Bradley Russell and Christopher John Kline.
+ */
+
+package com.sun.opengl.impl.awt.packrect;
+
+import java.util.*;
+
+/** Packs rectangles supplied by the user (typically representing
+    image regions) into a larger backing store rectangle (typically
+    representing a large texture). Supports automatic compaction of
+    the space on the backing store, and automatic expansion of the
+    backing store, when necessary. */
+
+public class RectanglePacker {
+  private BackingStoreManager manager;
+  private Object backingStore;
+  private LevelSet levels;
+  private float EXPANSION_FACTOR = 0.5f;
+  private float SHRINK_FACTOR = 0.3f;
+
+  private int initialWidth;
+  private int initialHeight;
+
+  private int maxWidth  = -1;
+  private int maxHeight = -1;
+
+  static class RectHComparator implements Comparator {
+    public int compare(Object o1, Object o2) {
+      Rect r1 = (Rect) o1;
+      Rect r2 = (Rect) o2;
+      return r2.h() - r1.h();
+    }
+
+    public boolean equals(Object obj) {
+      return this == obj;
+    }
+  }
+  private static final Comparator rectHComparator = new RectHComparator();
+
+  public RectanglePacker(BackingStoreManager manager,
+                         int initialWidth,
+                         int initialHeight) {
+    this.manager = manager;
+    levels = new LevelSet(initialWidth, initialHeight);
+    this.initialWidth = initialWidth;
+    this.initialHeight = initialHeight;
+  }
+
+  public Object getBackingStore() {
+    if (backingStore == null) {
+      backingStore = manager.allocateBackingStore(levels.w(), levels.h());
+    }
+
+    return backingStore;
+  }
+
+  /** Sets up a maximum width and height for the backing store. These
+      are optional and if not specified the backing store will grow as
+      necessary. Setting up a maximum width and height introduces the
+      possibility that additions will fail; these are handled with the
+      BackingStoreManager's allocationFailed notification. */
+  public void setMaxSize(int maxWidth, int maxHeight) {
+    this.maxWidth  = maxWidth;
+    this.maxHeight = maxHeight;
+  }
+
+  /** Decides upon an (x, y) position for the given rectangle (leaving
+      its width and height unchanged) and places it on the backing
+      store. May provoke re-layout of other Rects already added. */
+  public void add(Rect rect) {
+    // Allocate backing store if we don't have any yet
+    if (backingStore == null)
+      backingStore = manager.allocateBackingStore(levels.w(), levels.h());
+
+    int attemptNumber = 0;
+    boolean tryAgain = false;
+
+    do {
+      // Try to allocate
+      if (levels.add(rect))
+        return;
+
+      // Try to allocate with horizontal compaction
+      if (levels.compactAndAdd(rect, backingStore, manager))
+        return;
+
+      // Let the manager have a chance at potentially evicting some entries
+      tryAgain = manager.preExpand(rect, attemptNumber++);
+    } while (tryAgain);
+
+    compactImpl(rect);
+
+    // Retry the addition of the incoming rectangle
+    add(rect);
+    // Done
+  }
+
+  /** Removes the given rectangle from this RectanglePacker. */
+  public void remove(Rect rect) {
+    levels.remove(rect);
+  }
+
+  /** Visits all Rects contained in this RectanglePacker. */
+  public void visit(RectVisitor visitor) {
+    levels.visit(visitor);
+  }
+
+  /** Returns the vertical fragmentation ratio of this
+      RectanglePacker. This is defined as the ratio of the sum of the
+      heights of all completely empty Levels divided by the overall
+      used height of the LevelSet. A high vertical fragmentation ratio
+      indicates that it may be profitable to perform a compaction. */
+  public float verticalFragmentationRatio() {
+    return levels.verticalFragmentationRatio();
+  }
+
+  /** Forces a compaction cycle, which typically results in allocating
+      a new backing store and copying all entries to it. */
+  public void compact() {
+    compactImpl(null);
+  }
+
+  // The "cause" rect may be null
+  private void compactImpl(Rect cause) {
+    // Have to either expand, compact or both. Need to figure out what
+    // direction to go. Prefer to expand vertically. Expand
+    // horizontally only if rectangle being added is too wide. FIXME:
+    // may want to consider rebalancing the width and height to be
+    // more equal if it turns out we keep expanding in the vertical
+    // direction.
+    boolean done = false;
+    int newWidth = levels.w();
+    int newHeight = levels.h();
+    LevelSet nextLevelSet = null;
+    int attemptNumber = 0;
+    boolean needAdditionFailureNotification = false;
+
+    while (!done) {
+      if (cause != null) {
+        if (cause.w() > newWidth) {
+          newWidth = cause.w();
+        } else {
+          newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR));
+        }
+      }
+
+      // Clamp to maximum values
+      needAdditionFailureNotification = false;
+      if (maxWidth > 0 && newWidth > maxWidth) {
+        newWidth = maxWidth;
+        needAdditionFailureNotification = true;
+      }
+      if (maxHeight > 0 && newHeight > maxHeight) {
+        newHeight = maxHeight;
+        needAdditionFailureNotification = true;
+      }
+
+      nextLevelSet = new LevelSet(newWidth, newHeight);
+      
+      // Make copies of all existing rectangles
+      List/*<Rect>*/ newRects = new ArrayList/*<Rect>*/();
+      for (Iterator i1 = levels.iterator(); i1.hasNext(); ) {
+        Level level = (Level) i1.next();
+        for (Iterator i2 = level.iterator(); i2.hasNext(); ) {
+          Rect cur = (Rect) i2.next();
+          Rect newRect = new Rect(0, 0, cur.w(), cur.h(), null);
+          cur.setNextLocation(newRect);
+          // Hook up the reverse mapping too for easier replacement
+          newRect.setNextLocation(cur);
+          newRects.add(newRect);
+        }
+      }
+      // Sort them by decreasing height (note: this isn't really
+      // guaranteed to improve the chances of a successful layout)
+      Collections.sort(newRects, rectHComparator);
+      // Try putting all of these rectangles into the new level set
+      done = true;
+      for (Iterator iter = newRects.iterator(); iter.hasNext(); ) {
+        if (!nextLevelSet.add((Rect) iter.next())) {
+          done = false;
+          break;
+        }
+      }
+
+      if (done && cause != null) {
+        // Try to add the new rectangle as well
+        if (nextLevelSet.add(cause)) {
+          // We're OK
+        } else {
+          done = false;
+        }
+      }
+
+      // Don't send addition failure notifications if we're only doing
+      // a compaction
+      if (!done && needAdditionFailureNotification && cause != null) {
+        manager.additionFailed(cause, attemptNumber);
+      }
+      ++attemptNumber;
+    }
+
+    // See whether the implicit compaction that just occurred has
+    // yielded excess empty space.
+    if (nextLevelSet.getUsedHeight() > 0 &&
+        nextLevelSet.getUsedHeight() < nextLevelSet.h() * SHRINK_FACTOR) {
+      int shrunkHeight = Math.max(initialHeight,
+                                  (int) (nextLevelSet.getUsedHeight() * (1.0f + EXPANSION_FACTOR)));
+      if (maxHeight > 0 && shrunkHeight > maxHeight) {
+        shrunkHeight = maxHeight;
+      }
+      nextLevelSet.setHeight(shrunkHeight);
+    }
+
+    // If we temporarily added the new rectangle to the new LevelSet,
+    // take it out since we don't "really" add it here but in add(), above
+    if (cause != null) {
+      nextLevelSet.remove(cause);
+    }
+
+    // OK, now we have a new layout and a mapping from the old to the
+    // new locations of rectangles on the backing store. Allocate a
+    // new backing store, move the contents over and deallocate the
+    // old one.
+    Object newBackingStore = manager.allocateBackingStore(nextLevelSet.w(),
+                                                          nextLevelSet.h());
+    manager.beginMovement(backingStore, newBackingStore);
+    for (Iterator i1 = levels.iterator(); i1.hasNext(); ) {
+      Level level = (Level) i1.next();
+      for (Iterator i2 = level.iterator(); i2.hasNext(); ) {
+        Rect cur = (Rect) i2.next();
+        manager.move(backingStore, cur,
+                     newBackingStore, cur.getNextLocation());
+      }
+    }
+    // Replace references to temporary rectangles with original ones
+    nextLevelSet.updateRectangleReferences();
+    manager.endMovement(backingStore, newBackingStore);
+    // Now delete the old backing store
+    manager.deleteBackingStore(backingStore);
+    // Update to new versions of backing store and LevelSet
+    backingStore = newBackingStore;
+    levels = nextLevelSet;
+  }
+
+  /** Clears all Rects contained in this RectanglePacker. */
+  public void clear() {
+    levels.clear();
+  }
+
+  /** Disposes the backing store allocated by the
+      BackingStoreManager. This RectanglePacker may no longer be used
+      after calling this method. */
+  public void dispose() {
+    if (backingStore != null)
+      manager.deleteBackingStore(backingStore);
+    backingStore = null;
+    levels = null;
+  }
+}
diff --git a/src/classes/com/sun/opengl/impl/packrect/package.html b/src/classes/com/sun/opengl/impl/packrect/package.html
new file mode 100755
index 000000000..7f2522244
--- /dev/null
+++ b/src/classes/com/sun/opengl/impl/packrect/package.html
@@ -0,0 +1,7 @@
+This package implements a rectangle packing algorithm suitable for
+tracking the placement of multiple rectangles inside a larger one. It
+is useful for cases such as placing the contents of multiple windows
+on a larger backing store texture for a compositing window manager;
+placing multiple rasterized strings in a texture map for quick
+rendering to the screen; and many other situations where it is useful
+to carve up a larger texture into smaller pieces dynamically. <P>