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