1 /* 2 * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * - Redistribution of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * - Redistribution in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * Neither the name of Sun Microsystems, Inc. or the names of 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * This software is provided "AS IS," without a warranty of any kind. ALL 20 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, 21 * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A 22 * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN 23 * MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR 24 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR 25 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR 26 * ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR 27 * DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE 28 * DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, 29 * ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF 30 * SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. 31 * 32 * You acknowledge that this software is not designed or intended for use 33 * in the design, construction, operation or maintenance of any nuclear 34 * facility. 35 * 36 * Sun gratefully acknowledges that this software was originally authored 37 * and developed by Kenneth Bradley Russell and Christopher John Kline. 38 */ 39 40 package com.sun.opengl.impl.packrect; 41 42 import java.util.*; 43 44 /** Manages a list of Levels; this is the core data structure 45 contained within the RectanglePacker and encompasses the storage 46 algorithm for the contained Rects. */ 47 48 public class LevelSet { 49 // Maintained in sorted order by increasing Y coordinate 50 private List/*<Level>*/ levels = new ArrayList/*<Level>*/(); 51 private int nextAddY; 52 private int w; 53 private int h; 54 55 /** A LevelSet manages all of the backing store for a region of a 56 specified width and height. */ LevelSet(int w, int h)57 public LevelSet(int w, int h) { 58 this.w = w; 59 this.h = h; 60 } 61 w()62 public int w() { return w; } h()63 public int h() { return h; } 64 65 /** Returns true if the given rectangle was successfully added to 66 the LevelSet given its current dimensions, false if not. Caller 67 is responsible for performing compaction, expansion, etc. as a 68 consequence. */ add(Rect rect)69 public boolean add(Rect rect) { 70 if (rect.w() > w) 71 return false; 72 73 // Go in reverse order through the levels seeing whether we can 74 // trivially satisfy the allocation request 75 for (int i = levels.size() - 1; i >= 0; --i) { 76 Level level = (Level) levels.get(i); 77 if (level.add(rect)) 78 return true; 79 } 80 81 // See whether compaction could satisfy this allocation. This 82 // increases the computational complexity of the addition process, 83 // but prevents us from expanding unnecessarily. 84 for (int i = levels.size() - 1; i >= 0; --i) { 85 Level level = (Level) levels.get(i); 86 if (level.couldAllocateIfCompacted(rect)) 87 return false; 88 } 89 90 // OK, we need to either add a new Level or expand the backing 91 // store. Try to add a new Level. 92 if (nextAddY + rect.h() > h) 93 return false; 94 95 Level newLevel = new Level(w, rect.h(), nextAddY, this); 96 levels.add(newLevel); 97 nextAddY += rect.h(); 98 boolean res = newLevel.add(rect); 99 if (!res) 100 throw new RuntimeException("Unexpected failure in addition to new Level"); 101 return true; 102 } 103 104 /** Removes the given Rect from this LevelSet. */ remove(Rect rect)105 public boolean remove(Rect rect) { 106 for (int i = levels.size() - 1; i >= 0; --i) { 107 Level level = (Level) levels.get(i); 108 if (level.remove(rect)) 109 return true; 110 } 111 112 return false; 113 } 114 115 /** Allocates the given Rectangle, performing compaction of a Level 116 if necessary. This is the correct fallback path to {@link 117 #add(Rect)} above. Returns true if allocated successfully, false 118 otherwise (indicating the need to expand the backing store). */ compactAndAdd(Rect rect, Object backingStore, BackingStoreManager manager)119 public boolean compactAndAdd(Rect rect, 120 Object backingStore, 121 BackingStoreManager manager) { 122 for (int i = levels.size() - 1; i >= 0; --i) { 123 Level level = (Level) levels.get(i); 124 if (level.couldAllocateIfCompacted(rect)) { 125 level.compact(backingStore, manager); 126 boolean res = level.add(rect); 127 if (!res) 128 throw new RuntimeException("Unexpected failure to add after compaction"); 129 return true; 130 } 131 } 132 133 return false; 134 } 135 136 /** Indicates whether it's legal to trivially increase the height of 137 the given Level. This is only possible if it's the last Level 138 added and there's enough room in the backing store. */ canExpand(Level level, int height)139 public boolean canExpand(Level level, int height) { 140 if (levels.isEmpty()) 141 return false; // Should not happen 142 if (levels.get(levels.size() - 1) == level && 143 (h - nextAddY >= height - level.h())) 144 return true; 145 return false; 146 } 147 expand(Level level, int oldHeight, int newHeight)148 public void expand(Level level, int oldHeight, int newHeight) { 149 nextAddY += (newHeight - oldHeight); 150 } 151 152 /** Gets the used height of the levels in this LevelSet. */ getUsedHeight()153 public int getUsedHeight() { 154 return nextAddY; 155 } 156 157 /** Sets the height of this LevelSet. It is only legal to reduce the 158 height to greater than or equal to the currently used height. */ setHeight(int height)159 public void setHeight(int height) throws IllegalArgumentException { 160 if (height < getUsedHeight()) { 161 throw new IllegalArgumentException("May not reduce height below currently used height"); 162 } 163 h = height; 164 } 165 166 /** Returns the vertical fragmentation ratio of this LevelSet. This 167 is defined as the ratio of the sum of the heights of all 168 completely empty Levels divided by the overall used height of 169 the LevelSet. A high vertical fragmentation ratio indicates that 170 it may be profitable to perform a compaction. */ verticalFragmentationRatio()171 public float verticalFragmentationRatio() { 172 int freeHeight = 0; 173 int usedHeight = getUsedHeight(); 174 if (usedHeight == 0) 175 return 0.0f; 176 for (Iterator iter = iterator(); iter.hasNext(); ) { 177 Level level = (Level) iter.next(); 178 if (level.isEmpty()) { 179 freeHeight += level.h(); 180 } 181 } 182 return (float) freeHeight / (float) usedHeight; 183 } 184 iterator()185 public Iterator iterator() { 186 return levels.iterator(); 187 } 188 189 /** Visits all Rects contained in this LevelSet. */ visit(RectVisitor visitor)190 public void visit(RectVisitor visitor) { 191 for (Iterator iter = levels.iterator(); iter.hasNext(); ) { 192 Level level = (Level) iter.next(); 193 level.visit(visitor); 194 } 195 } 196 197 /** Updates the references to the Rect objects in this LevelSet with 198 the "next locations" of those Rects. This is actually used to 199 update the new Rects in a newly laid-out LevelSet with the 200 original Rects. */ updateRectangleReferences()201 public void updateRectangleReferences() { 202 for (Iterator iter = levels.iterator(); iter.hasNext(); ) { 203 Level level = (Level) iter.next(); 204 level.updateRectangleReferences(); 205 } 206 } 207 208 /** Clears out all Levels stored in this LevelSet. */ clear()209 public void clear() { 210 levels.clear(); 211 nextAddY = 0; 212 } 213 } 214