Robustness improvements to TextRenderer and underlying RectanglePacker.

Added ability to specify a maximum size to which the RectanglePacker
can expand. Added preExpand method to BackingStoreManager to support
early eviction of unused entries instead of always expanding the
backing store, and additionFailed method used when the backing store
can not expand further. Added more robust free list coalescing to
Level. Added support for shrinking of backing store and for eager
compaction when there is a lot of vertical dead space. Added TextFlow
demo which shows how to do dynamic layout of text and which acts as a
stress test for the TextRenderer.


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

4 files changed, 256 insertions, 58 deletions

diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java
index ba4b0cf30..0c4636063 100755
--- a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java
+++ b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java
@@ -49,16 +49,37 @@ public interface BackingStoreManager {
   public Object allocateBackingStore(int w, int h);
   public void   deleteBackingStore(Object backingStore);
 
-  // Notification that movement is starting
+  /** 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);
 
-  // Can the backing stores be identical? I think so, in the case of
-  // compacting the existing backing store as opposed to reallocating it...
+  /** 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
+  /** 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
index e7eab9ca7..12a09cd9a 100755
--- a/src/classes/com/sun/opengl/impl/packrect/Level.java
+++ b/src/classes/com/sun/opengl/impl/packrect/Level.java
@@ -129,8 +129,7 @@ public class Level {
           freeList.add(candidate);
         }
         
-        if (freeList.isEmpty())
-          freeList = null;
+        coalesceFreeList();
 
         return true;
       }
@@ -148,38 +147,22 @@ public class Level {
     // to the free list, we can just decrease the nextAddX
     if (rect.maxX() + 1 == nextAddX) {
       nextAddX -= rect.w();
-
-      // Now try to coalesce additional free space at the end of the
-      // free list
-      if (freeList != null) {
-        boolean found = true;
-        while (found) {
-          found = false;
-          for (Iterator iter = freeList.iterator(); iter.hasNext(); ) {
-            Rect cur = (Rect) iter.next();
-            if (cur.maxX() + 1 == nextAddX) {
-              nextAddX -= cur.w();
-              found = true;
-              freeList.remove(cur);
-              break;
-            }
-          }
-        }
-        if (freeList.isEmpty())
-          freeList = null;
+    } else {
+      if (freeList == null) {
+        freeList = new ArrayList/*<Rect>*/();
       }
-
-      return true;
+      freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null));
+      coalesceFreeList();
     }
 
-    // Else, add the space consumed by this rectangle to the free list
-    if (freeList == null) {
-      freeList = new ArrayList/*<Rect>*/();
-    }
-    freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null));
     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) {
@@ -211,6 +194,7 @@ public class Level {
       nextCompactionDest += cur.w();
     }
     nextAddX = nextCompactionDest;
+    freeList.clear();
     manager.endMovement(backingStore, backingStore);
   }
 
@@ -240,4 +224,52 @@ public class Level {
       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
index 561a3fe14..97a1f2e74 100755
--- a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java
+++ b/src/classes/com/sun/opengl/impl/packrect/LevelSet.java
@@ -149,6 +149,39 @@ public class LevelSet {
     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();
   }
@@ -171,4 +204,10 @@ public class LevelSet {
       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/RectanglePacker.java b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java
index 453f5e1e2..6057f7bb9 100755
--- a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java
+++ b/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java
@@ -52,6 +52,13 @@ public class RectanglePacker {
   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) {
@@ -71,6 +78,8 @@ public class RectanglePacker {
                          int initialHeight) {
     this.manager = manager;
     levels = new LevelSet(initialWidth, initialHeight);
+    this.initialWidth = initialWidth;
+    this.initialHeight = initialHeight;
   }
 
   public Object getBackingStore() {
@@ -81,6 +90,16 @@ public class RectanglePacker {
     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. */
@@ -89,29 +108,89 @@ public class RectanglePacker {
     if (backingStore == null)
       backingStore = manager.allocateBackingStore(levels.w(), levels.h());
 
-    // Try to allocate
-    if (levels.add(rect))
-      return;
+    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);
+  }
 
-    // Try to allocate with compaction
-    if (levels.compactAndAdd(rect, backingStore, manager))
-      return;
+  /** 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();
+  }
 
-    // Have to expand. 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.
+  /** 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 (rect.w() > newWidth) {
-        newWidth = rect.w();
-      } else {
-        newHeight = (int) (newHeight * (1.0f + EXPANSION_FACTOR));
+      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
@@ -138,7 +217,42 @@ public class RectanglePacker {
           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
@@ -162,19 +276,11 @@ public class RectanglePacker {
     // Update to new versions of backing store and LevelSet
     backingStore = newBackingStore;
     levels = nextLevelSet;
-    // 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);
+  /** Clears all Rects contained in this RectanglePacker. */
+  public void clear() {
+    levels.clear();
   }
 
   /** Disposes the backing store allocated by the