From 2bb74885eaef215590bcd830368602e7aa5d7d8d Mon Sep 17 00:00:00 2001 From: Sven Gothel Date: Thu, 26 Jun 2008 01:14:29 +0000 Subject: removing relocated files git-svn-id: file:///usr/local/projects/SUN/JOGL/git-svn/svn-server-sync/jogl/branches/JOGL_2_SANDBOX@1690 232f8b59-042b-4e1e-8c03-345bb8c30851 --- .../opengl/impl/packrect/BackingStoreManager.java | 85 ------ .../com/sun/opengl/impl/packrect/Level.java | 275 ------------------- .../com/sun/opengl/impl/packrect/LevelSet.java | 213 --------------- src/classes/com/sun/opengl/impl/packrect/Rect.java | 170 ------------ .../com/sun/opengl/impl/packrect/RectVisitor.java | 47 ---- .../sun/opengl/impl/packrect/RectanglePacker.java | 295 --------------------- .../com/sun/opengl/impl/packrect/package.html | 7 - 7 files changed, 1092 deletions(-) delete mode 100755 src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/Level.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/LevelSet.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/Rect.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/RectVisitor.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java delete mode 100755 src/classes/com/sun/opengl/impl/packrect/package.html (limited to 'src/classes/com/sun/opengl/impl/packrect') diff --git a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java b/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java deleted file mode 100755 index acff0aa79..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/BackingStoreManager.java +++ /dev/null @@ -1,85 +0,0 @@ -/* - * 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 deleted file mode 100755 index 2ef6cb989..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/Level.java +++ /dev/null @@ -1,275 +0,0 @@ -/* - * 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/**/ rects = new ArrayList/**/(); - private List/**/ 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/**/(); - } - 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 deleted file mode 100755 index 724af27e0..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/LevelSet.java +++ /dev/null @@ -1,213 +0,0 @@ -/* - * 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/**/ levels = new ArrayList/**/(); - 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 deleted file mode 100755 index c3b6be6da..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/Rect.java +++ /dev/null @@ -1,170 +0,0 @@ -/* - * 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).

- - 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.

- - 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 deleted file mode 100755 index 9fd253d43..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/RectVisitor.java +++ /dev/null @@ -1,47 +0,0 @@ -/* - * 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 deleted file mode 100755 index f795fe00a..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/RectanglePacker.java +++ /dev/null @@ -1,295 +0,0 @@ -/* - * 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/**/ newRects = new ArrayList/**/(); - 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 deleted file mode 100755 index 7f2522244..000000000 --- a/src/classes/com/sun/opengl/impl/packrect/package.html +++ /dev/null @@ -1,7 +0,0 @@ -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.

-- cgit v1.2.3