1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
/*
* 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.*;
/** 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/*<Level>*/ levels = new ArrayList/*<Level>*/();
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;
}
}
|
