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