JOGL v2.6.0-rc-20250706
JOGL, High-Performance Graphics Binding for Java™ (public API).
Level.java
Go to the documentation of this file.
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
40package com.jogamp.opengl.util.packrect;
41
42import java.util.*;
43
44public class Level {
45 private final int width;
46 private int height;
47 private final int yPos;
48 private final LevelSet holder;
49
50 private final List<Rect> rects = new ArrayList<Rect>();
51 private List<Rect> freeList;
52 private int nextAddX;
53
54 static class RectXComparator implements Comparator<Rect> {
55 @Override
56 public int compare(final Rect r1, final Rect r2) {
57 return r1.x() - r2.x();
58 }
59
60 @Override
61 public boolean equals(final Object obj) {
62 return this == obj;
63 }
64 }
65 private static final Comparator<Rect> rectXComparator = new RectXComparator();
66
67 public Level(final int width, final int height, final int yPos, final LevelSet holder) {
68 this.width = width;
69 this.height = height;
70 this.yPos = yPos;
71 this.holder = holder;
72 }
73
74 public int w() { return width; }
75 public int h() { return height; }
76 public int yPos() { return yPos; }
77
78 /** Tries to add the given rectangle to this level only allowing
79 non-disruptive changes like trivial expansion of the last level
80 in the RectanglePacker and allocation from the free list. More
81 disruptive changes like compaction of the level must be
82 requested explicitly. */
83 public boolean add(final Rect rect) {
84 if (rect.h() > height) {
85 // See whether it's worth trying to expand vertically
86 if (nextAddX + rect.w() > width) {
87 return false;
88 }
89
90 // See whether we're the last level and can expand
91 if (!holder.canExpand(this, rect.h())) {
92 return false;
93 }
94
95 // Trivially expand and try the allocation
96 holder.expand(this, height, rect.h());
97 height = rect.h();
98 }
99
100 // See whether we can add at the end
101 if (nextAddX + rect.w() <= width) {
102 rect.setPosition(nextAddX, yPos);
103 rects.add(rect);
104 nextAddX += rect.w();
105 return true;
106 }
107
108 // See whether we can add from the free list
109 if (freeList != null) {
110 Rect candidate = null;
111 for (final Iterator<Rect> iter = freeList.iterator(); iter.hasNext(); ) {
112 final Rect cur = iter.next();
113 if (cur.canContain(rect)) {
114 candidate = cur;
115 break;
116 }
117 }
118
119 if (candidate != null) {
120 // Remove the candidate from the free list
121 freeList.remove(candidate);
122 // Set up and add the real rect
123 rect.setPosition(candidate.x(), candidate.y());
124 rects.add(rect);
125 // Re-add any remaining free space
126 if (candidate.w() > rect.w()) {
127 candidate.setPosition(candidate.x() + rect.w(), candidate.y());
128 candidate.setSize(candidate.w() - rect.w(), height);
129 freeList.add(candidate);
130 }
131
132 coalesceFreeList();
133
134 return true;
135 }
136 }
137
138 return false;
139 }
140
141 /** Removes the given Rect from this Level. */
142 public boolean remove(final Rect rect) {
143 if (!rects.remove(rect))
144 return false;
145
146 // If this is the rightmost rectangle, instead of adding its space
147 // to the free list, we can just decrease the nextAddX
148 if (rect.maxX() + 1 == nextAddX) {
149 nextAddX -= rect.w();
150 } else {
151 if (freeList == null) {
152 freeList = new ArrayList<Rect>();
153 }
154 freeList.add(new Rect(rect.x(), rect.y(), rect.w(), height, null));
155 coalesceFreeList();
156 }
157
158 return true;
159 }
160
161 /** Indicates whether this Level contains no rectangles. */
162 public boolean isEmpty() {
163 return rects.isEmpty();
164 }
165
166 /** Indicates whether this Level could satisfy an allocation request
167 if it were compacted. */
168 public boolean couldAllocateIfCompacted(final Rect rect) {
169 if (rect.h() > height)
170 return false;
171 if (freeList == null)
172 return false;
173 int freeListWidth = 0;
174 for (final Iterator<Rect> iter = freeList.iterator(); iter.hasNext(); ) {
175 final Rect cur = iter.next();
176 freeListWidth += cur.w();
177 }
178 // Add on the remaining space at the end
179 freeListWidth += (width - nextAddX);
180 return (freeListWidth >= rect.w());
181 }
182
183 public void compact(final Object backingStore, final BackingStoreManager manager) {
184 Collections.sort(rects, rectXComparator);
185 int nextCompactionDest = 0;
186 manager.beginMovement(backingStore, backingStore);
187 for (final Iterator<Rect> iter = rects.iterator(); iter.hasNext(); ) {
188 final Rect cur = iter.next();
189 if (cur.x() != nextCompactionDest) {
190 manager.move(backingStore, cur,
191 backingStore, new Rect(nextCompactionDest, cur.y(), cur.w(), cur.h(), null));
192 cur.setPosition(nextCompactionDest, cur.y());
193 }
194 nextCompactionDest += cur.w();
195 }
196 nextAddX = nextCompactionDest;
197 freeList.clear();
198 manager.endMovement(backingStore, backingStore);
199 }
200
201 public Iterator<Rect> iterator() {
202 return rects.iterator();
203 }
204
205 /** Visits all Rects contained in this Level. */
206 public void visit(final RectVisitor visitor) {
207 for (final Iterator<Rect> iter = rects.iterator(); iter.hasNext(); ) {
208 final Rect rect = iter.next();
209 visitor.visit(rect);
210 }
211 }
212
213 /** Updates the references to the Rect objects in this Level with
214 the "next locations" of those Rects. This is actually used to
215 update the new Rects in a newly laid-out LevelSet with the
216 original Rects. */
218 for (int i = 0; i < rects.size(); i++) {
219 final Rect cur = rects.get(i);
220 final Rect next = cur.getNextLocation();
221 next.setPosition(cur.x(), cur.y());
222 if (cur.w() != next.w() || cur.h() != next.h())
223 throw new RuntimeException("Unexpected disparity in rectangle sizes during updateRectangleReferences");
224 rects.set(i, next);
225 }
226 }
227
228 private void coalesceFreeList() {
229 if (freeList == null)
230 return;
231 if (freeList.isEmpty())
232 return;
233
234 // Try to coalesce adjacent free blocks in the free list
235 Collections.sort(freeList, rectXComparator);
236 int i = 0;
237 while (i < freeList.size() - 1) {
238 final Rect r1 = freeList.get(i);
239 final Rect r2 = freeList.get(i+1);
240 if (r1.maxX() + 1 == r2.x()) {
241 // Coalesce r1 and r2 into one block
242 freeList.remove(i+1);
243 r1.setSize(r1.w() + r2.w(), r1.h());
244 } else {
245 ++i;
246 }
247 }
248 // See whether the last block bumps up against the addition point
249 final Rect last = freeList.get(freeList.size() - 1);
250 if (last.maxX() + 1 == nextAddX) {
251 nextAddX -= last.w();
252 freeList.remove(freeList.size() - 1);
253 }
254 if (freeList.isEmpty()) {
255 freeList = null;
256 }
257 }
258
259 //----------------------------------------------------------------------
260 // Debugging functionality
261 //
262
263 public void dumpFreeSpace() {
264 int freeListWidth = 0;
265 for (final Iterator<Rect> iter = freeList.iterator(); iter.hasNext(); ) {
266 final Rect cur = iter.next();
267 System.err.println(" Free rectangle at " + cur);
268 freeListWidth += cur.w();
269 }
270 // Add on the remaining space at the end
271 System.err.println(" Remaining free space " + (width - nextAddX));
272 freeListWidth += (width - nextAddX);
273 System.err.println(" Total free space " + freeListWidth);
274 }
275}
Manages a list of Levels; this is the core data structure contained within the RectanglePacker and en...
Definition: LevelSet.java:48
void expand(final Level level, final int oldHeight, final int newHeight)
Definition: LevelSet.java:148
boolean canExpand(final Level level, final int height)
Indicates whether it's legal to trivially increase the height of the given Level.
Definition: LevelSet.java:139
void updateRectangleReferences()
Updates the references to the Rect objects in this Level with the "next locations" of those Rects.
Definition: Level.java:217
void visit(final RectVisitor visitor)
Visits all Rects contained in this Level.
Definition: Level.java:206
void compact(final Object backingStore, final BackingStoreManager manager)
Definition: Level.java:183
boolean couldAllocateIfCompacted(final Rect rect)
Indicates whether this Level could satisfy an allocation request if it were compacted.
Definition: Level.java:168
boolean isEmpty()
Indicates whether this Level contains no rectangles.
Definition: Level.java:162
boolean add(final Rect rect)
Tries to add the given rectangle to this level only allowing non-disruptive changes like trivial expa...
Definition: Level.java:83
Level(final int width, final int height, final int yPos, final LevelSet holder)
Definition: Level.java:67
Represents a rectangular region on the backing store.
Definition: Rect.java:58
void setPosition(final int x, final int y)
Definition: Rect.java:97
boolean canContain(final Rect other)
Definition: Rect.java:142
int maxX()
Returns the maximum x-coordinate contained within this rectangle.
Definition: Rect.java:125
void setSize(final int w, final int h)
Definition: Rect.java:106
This interface must be implemented by the end user and is called in response to events like addition ...
void beginMovement(Object oldBackingStore, Object newBackingStore)
Notification that movement is starting.
void endMovement(Object oldBackingStore, Object newBackingStore)
Notification that movement is ending.
void move(Object oldBackingStore, Rect oldLocation, Object newBackingStore, Rect newLocation)
Tells the manager to move the contents of the given rect from the old location on the old backing sto...
Iteration construct without exposing the internals of the RectanglePacker and without implementing a ...