1 files changed, 295 insertions, 0 deletions
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..3a77b3bd1
--- /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.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;
+  }
+}