KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > batik > ext > awt > image > rendered > TileBlock


1 /*
2
3    Copyright 2001,2003 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.ext.awt.image.rendered;
19
20 import java.util.Iterator JavaDoc;
21 import java.util.Vector JavaDoc;
22
23 /**
24  * This class is responsible for breaking up a block of tiles into
25  * a set of smaller requests that are a large as possible without
26  * rerequesting significant numbers of tiles that are already
27  * available
28  */
29 public class TileBlock {
30     int occX, occY, occW, occH;
31     int xOff, yOff, w, h, benefit;
32     boolean [] occupied;
33
34     /**
35      * Construct a tile block this represents a block of contigous
36      * tiles.
37      * @param xloc The x index of left edge of the tile block.
38      * @param yloc The y index of top edge of the tile block.
39      * @param w The number of tiles across in the block
40      * @param h The number of tiles down the block
41      * @param occupied Which entries in the block are already
42      * computed.
43      */
44     TileBlock(int occX, int occY, int occW, int occH, boolean [] occupied,
45               int xOff, int yOff, int w, int h) {
46         this.occX = occX;
47         this.occY = occY;
48         this.occW = occW;
49         this.occH = occH;
50         this.xOff = xOff;
51         this.yOff = yOff;
52         this.w = w ;
53         this.h = h ;
54         this.occupied = occupied;
55
56
57
58         // System.out.println("Block: [" +
59 // xloc + "," + yloc + "," +
60 // w + "," + h + "]");
61 for (int y=0; y<h; y++)
62             for (int x=0; x<w; x++)
63                 if (!occupied[x+xOff+occW*(y+yOff)])
64                     benefit++;
65     }
66
67     /**
68      * Really nice to string that outlines what tiles are filled
69      * and what region this block covers. Really useful for
70      * debugging the TileBlock stuff.
71      */
72     public String JavaDoc toString() {
73         String JavaDoc ret = "";
74         for (int y=0; y<occH; y++) {
75             for (int x=0; x<occW+1; x++) {
76                 if ((x==xOff) || (x==xOff+w)) {
77                     if ((y==yOff) || (y==yOff+h-1))
78                         ret += "+";
79                     else if ((y>yOff) && (y<yOff+h-1))
80                         ret += "|";
81                     else
82                         ret += " ";
83                 }
84                 else if ((y==yOff) && (x> xOff) && (x < xOff+w))
85                     ret += "-";
86                 else if ((y==yOff+h-1) && (x> xOff) && (x < xOff+w))
87                     ret += "_";
88                 else
89                     ret += " ";
90
91                 if (x== occW)
92                     continue;
93
94                 if (occupied[x+y*occW])
95                     ret += "*";
96                 else
97                     ret += ".";
98             }
99             ret += "\n";
100         }
101         return ret;
102     }
103
104     /**
105      * Return the x location of this block of tiles
106      */
107     int getXLoc() { return occX+xOff; }
108     /**
109      * Return the y location of this block of tiles
110      */
111     int getYLoc() { return occY+yOff; }
112     /**
113      * Return the width of this block of tiles
114      */
115     int getWidth() { return w; }
116     /**
117      * Return the height of this block of tiles
118      */
119     int getHeight() { return h; }
120
121     /**
122      * Return the number of new tiles computed.
123      */
124     int getBenefit() { return benefit; }
125         
126     /**
127      * Return the approximate amount of work required to compute
128      * those tiles.
129      */
130     int getWork() { return w*h+1; }
131
132     /**
133      * Returns the total amount of work for the array of tile blocks
134      */
135     static int getWork(TileBlock [] blocks) {
136         int ret=0;
137         for (int i=0; i<blocks.length; i++)
138             ret += blocks[i].getWork();
139         return ret;
140     }
141
142     /**
143      * Returnes an optimized list of TileBlocks to generate that
144      * tries to minimize the work to benefit ratio, for the set of
145      * blocks defined by this block.
146      */
147     TileBlock [] getBestSplit() {
148         if (simplify())
149             return null;
150             
151         // Optimal split already...
152 if (benefit == w*h)
153             return new TileBlock [] { this };
154
155         return splitOneGo();
156     }
157
158     public TileBlock [] splitOneGo() {
159         boolean [] filled = (boolean [])occupied.clone();
160         Vector JavaDoc items = new Vector JavaDoc();
161         for (int y=yOff; y<yOff+h; y++)
162             for (int x=xOff; x<xOff+w; x++) {
163                 if (!filled[x+y*occW]) {
164                     // We have an unfilled tile slot, so first we
165 // figure out how long the slot is in this row.
166 int cw = xOff+w-x;
167                     for (int cx=x; cx<x+cw; cx++)
168                         if (filled[cx+y*occW])
169                             cw = cx-x;
170                         else
171                             filled[cx+y*occW] = true; // fill as we go..
172
173                     // Then we check the next rows until we hit
174 // a row that doesn't have this slot all free.
175 // at which point we stop...
176 int ch=1;
177                     for (int cy=y+1; cy<yOff+h; cy++) {
178                         int cx=x;
179                         for (; cx<x+cw; cx++)
180                             if (filled[cx+cy*occW])
181                                 break;
182
183                         // Partial row so bail (we'll get it later..)
184 if (cx != x+cw)
185                             break;
186
187                         // Fill in the slot since we will use it...
188 for (cx=x; cx<x+cw; cx++)
189                             filled[cx+cy*occW] = true;
190                         ch++;
191                     }
192                     items.add(new TileBlock(occX, occY, occW, occH,
193                                             occupied, x, y, cw, ch));
194                     x+=(cw-1);
195                 }
196             }
197
198         TileBlock [] ret = new TileBlock[items.size()];
199         Iterator JavaDoc iter = items.iterator();
200         int i=0;
201         while (iter.hasNext())
202             ret[i++] = (TileBlock)iter.next();
203         return ret;
204     }
205
206     public boolean simplify() {
207         for (int y=0; y<h; y++) {
208             int x;
209             for (x=0; x<w; x++)
210                 if (!occupied[x+xOff+occW*(y+yOff)])
211                     break;
212             if (x!=w) break;
213
214             // Fully occupied row so remove it.
215 yOff++;
216             y--;
217             h--;
218         }
219
220         // return true if we were simplified out of existance.
221 if (h==0) return true;
222
223         // If we make it past here we must have at least one good block.
224
225         for (int y=h-1; y>=0; y--) {
226             int x;
227             for (x=0; x<w; x++)
228                 if (!occupied[x+xOff+occW*(y+yOff)])
229                     break;
230             if (x!=w) break;
231
232             // Fully occupied row so remove it.
233 h--;
234         }
235
236         for (int x=0; x<w; x++) {
237             int y;
238             for (y=0; y<h; y++)
239                 if (!occupied[x+xOff+occW*(y+yOff)])
240                     break;
241             if (y!=h) break;
242
243             // Fully occupied Col so remove it.
244 xOff++;
245             x--;
246             w--;
247         }
248
249         for (int x=w-1; x>=0; x--) {
250             int y;
251             for (y=0; y<h; y++)
252                 if (!occupied[x+xOff+occW*(y+yOff)])
253                     break;
254             if (y!=h) break;
255
256             // Fully occupied Col so remove it.
257 w--;
258         }
259
260         return false;
261     }
262 }
263
264
265
Popular Tags