001package squidpony.squidgrid.zone; 002 003import squidpony.squidgrid.Direction; 004import squidpony.squidmath.Coord; 005 006import java.io.Serializable; 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Iterator; 010import java.util.List; 011 012/** 013 * Abstraction over a list of {@link Coord}. This allows to use the short arrays 014 * coming from {@link squidpony.squidmath.CoordPacker}, which are compressed for 015 * better memory usage, regular {@link List lists of Coord}, which are often the 016 * simplest option, or {@link squidpony.squidmath.GreasedRegion GreasedRegions}, 017 * which are "greasy" in the fatty-food sense (they are heavier objects, and are 018 * uncompressed) but also "greased" like greased lightning (they are very fast at 019 * spatial transformations on their region). 020 * <p> 021 * Zones are {@link Serializable}, but serialization doesn't change the internal 022 * representation (some would want to pack {@link ListZone} into 023 * {@link CoordPackerZone}s when serializing). I find that overzealous for a 024 * simple interface. If you want your zones to be be packed when serialized, 025 * create {@link CoordPackerZone} yourself. In squidlib-extra, GreasedRegions are 026 * given slightly special treatment during that JSON-like serialization so they 027 * avoid repeating certain information, but they are still going to be larger than 028 * compressed short arrays from CoordPacker. 029 * </p> 030 * <p> 031 * While CoordPacker produces short arrays that can be wrapped in CoordPackerZone 032 * objects, and a List of Coord can be similarly wrapped in a ListZone object, 033 * GreasedRegion extends {@link Zone.Skeleton} and so implements Zone itself. 034 * Unlike CoordPackerZone, which is immutable in practice (changing the short 035 * array reference is impossible and changing the elements rarely works as 036 * planned), GreasedRegion is mutable for performance reasons, and may need copies 037 * to be created if you want to keep around older GreasedRegions. 038 * </p> 039 * 040 * <p> 041 * The correct method to implement a {@link Zone} efficiently is to first try 042 * implementing the interface directly, looking at each method and thinking 043 * whether you can do something smart for it. Once you've inspected all methods, 044 * then extend {@link Zone.Skeleton} (instead of Object in the first place) so 045 * that it'll fill for you the methods for which you cannot provide a smart 046 * implementation. 047 * </p> 048 * 049 * @author smelC 050 * @see squidpony.squidmath.CoordPacker 051 * @see squidpony.squidmath.GreasedRegion 052 */ 053public interface Zone extends Serializable, Iterable<Coord> { 054 055 /** 056 * @return Whether this zone is empty. 057 */ 058 boolean isEmpty(); 059 060 /** 061 * @return The number of cells that this zone contains (the size 062 * {@link #getAll()}). 063 */ 064 int size(); 065 066 /** 067 * @param x 068 * @param y 069 * @return Whether this zone contains the coordinate (x,y). 070 */ 071 boolean contains(int x, int y); 072 073 /** 074 * @param c 075 * @return Whether this zone contains {@code c}. 076 */ 077 boolean contains(Coord c); 078 079 /** 080 * @param other 081 * @return true if all cells of {@code other} are in {@code this}. 082 */ 083 boolean contains(Zone other); 084 085 /** 086 * @param other 087 * @return true if {@code this} and {@code other} have a common cell. 088 */ 089 boolean intersectsWith(Zone other); 090 091 /** 092 * @return The approximate center of this zone, or null if this zone 093 * is empty. 094 */ 095 /* @Nullable */ Coord getCenter(); 096 097 /** 098 * @return The distance between the leftmost cell and the rightmost cell, or 099 * anything negative if {@code this} zone is empty; may be 0 if all cells 100 * are in one vertical line. 101 */ 102 int getWidth(); 103 104 /** 105 * @return The distance between the topmost cell and the lowest cell, or 106 * anything negative if {@code this} zone is empty; may be 0 if all cells 107 * are in one horizontal line. 108 */ 109 int getHeight(); 110 111 /** 112 * @return The approximation of the zone's diagonal, using 113 * {@link #getWidth()} and {@link #getHeight()}. 114 */ 115 double getDiagonal(); 116 117 /** 118 * @param smallestOrBiggest if true, finds the smallest x-coordinate value; 119 * if false, finds the biggest. 120 * @return The x-coordinate of the Coord within {@code this} that has the 121 * smallest (or biggest) x-coordinate. Or -1 if the zone is empty. 122 */ 123 int xBound(boolean smallestOrBiggest); 124 125 /** 126 * @param smallestOrBiggest if true, finds the smallest y-coordinate value; 127 * if false, finds the biggest. 128 * @return The y-coordinate of the Coord within {@code this} that has the 129 * smallest (or biggest) y-coordinate. Or -1 if the zone is empty. 130 */ 131 int yBound(boolean smallestOrBiggest); 132 133 /** 134 * @return All cells in this zone. 135 */ 136 List<Coord> getAll(); 137 138 /** @return {@code this} shifted by {@code (c.x,c.y)} */ 139 Zone translate(Coord c); 140 141 /** @return {@code this} shifted by {@code (x,y)} */ 142 Zone translate(int x, int y); 143 144 /** 145 * @return Cells in {@code this} that are adjacent to a cell not in 146 * {@code this} 147 */ 148 Collection<Coord> getInternalBorder(); 149 150 /** 151 * Gets a Collection of Coord values that are not in this Zone, but are 152 * adjacent to it, either orthogonally or diagonally. Related to the fringe() 153 * methods in CoordPacker and GreasedRegion, but guaranteed to use 8-way 154 * adjacency and to return a new Collection of Coord. 155 * @return Cells adjacent to {@code this} (orthogonally or diagonally) that 156 * aren't in {@code this} 157 */ 158 Collection<Coord> getExternalBorder(); 159 160 /** 161 * Gets a new Zone that contains all the Coords in {@code this} plus all 162 * neighboring Coords, which can be orthogonally or diagonally adjacent 163 * to any Coord this has in it. Related to the expand() methods in 164 * CoordPacker and GreasedRegion, but guaranteed to use 8-way adjacency 165 * and to return a new Zone. 166 * @return A variant of {@code this} where cells adjacent to {@code this} 167 * (orthogonally or diagonally) have been added (i.e. it's {@code this} 168 * plus {@link #getExternalBorder()}). 169 */ 170 Zone extend(); 171 172 /** 173 * A convenience partial implementation. Please try for all new 174 * implementations of {@link Zone} to be subtypes of this class. It usually 175 * prove handy at some point to have a common superclass. 176 * 177 * @author smelC 178 */ 179 abstract class Skeleton implements Zone { 180 181 private transient Coord center; 182 protected transient int width = -2; 183 protected transient int height = -2; 184 185 private static final long serialVersionUID = 4436698111716212256L; 186 187 @Override 188 /* Convenience implementation, feel free to override */ 189 public int size() { 190 return getAll().size(); 191 } 192 193 @Override 194 /* Convenience implementation, feel free to override */ 195 public boolean contains(int x, int y) { 196 for (Coord in : this) { 197 if (in.x == x && in.y == y) 198 return true; 199 } 200 return false; 201 } 202 203 @Override 204 /* Convenience implementation, feel free to override */ 205 public boolean contains(Coord c) { 206 return contains(c.x, c.y); 207 } 208 209 @Override 210 /* Convenience implementation, feel free to override */ 211 public boolean contains(Zone other) { 212 for (Coord c : other) { 213 if (!contains(c)) 214 return false; 215 } 216 return true; 217 } 218 219 @Override 220 public boolean intersectsWith(Zone other) { 221 final int tsz = size(); 222 final int osz = other.size(); 223 final Iterable<Coord> iteratedOver = tsz < osz ? this : other; 224 final Zone other_ = tsz < osz ? other : this; 225 for (Coord c : iteratedOver) { 226 if (other_.contains(c)) 227 return true; 228 } 229 return false; 230 } 231 232 @Override 233 /* 234 * Convenience implementation, feel free to override, in particular if 235 * you can avoid allocating the list usually allocated by getAll(). 236 */ 237 public Iterator<Coord> iterator() { 238 return getAll().iterator(); 239 } 240 241 @Override 242 /* Convenience implementation, feel free to override. */ 243 public int getWidth() { 244 if (width == -2) 245 width = isEmpty() ? -1 : xBound(false) - xBound(true); 246 return width; 247 } 248 249 @Override 250 /* Convenience implementation, feel free to override. */ 251 public int getHeight() { 252 if (height == -2) 253 height = isEmpty() ? -1 : yBound(false) - yBound(true); 254 return height; 255 } 256 257 @Override 258 public double getDiagonal() { 259 final int w = getWidth(); 260 final int h = getHeight(); 261 return Math.sqrt((w * w) + (h * h)); 262 } 263 264 @Override 265 /* Convenience implementation, feel free to override. */ 266 public int xBound(boolean smallestOrBiggest) { 267 return smallestOrBiggest ? smallest(true) : biggest(true); 268 } 269 270 @Override 271 /* Convenience implementation, feel free to override. */ 272 public int yBound(boolean smallestOrBiggest) { 273 return smallestOrBiggest ? smallest(false) : biggest(false); 274 } 275 276 @Override 277 /* Convenience implementation, feel free to override. */ 278 /* 279 * A possible enhancement would be to check that the center is within 280 * the zone, and if not to return the coord closest to the center, that 281 * is in the zone . 282 */ 283 public /* @Nullable */ Coord getCenter() { 284 if (center == null) { 285 /* Need to compute it */ 286 if (isEmpty()) 287 return null; 288 int x = 0, y = 0; 289 float nb = 0; 290 for (Coord c : this) { 291 x += c.x; 292 y += c.y; 293 nb++; 294 } 295 /* Remember it */ 296 center = Coord.get(Math.round(x / nb), Math.round(y / nb)); 297 } 298 return center; 299 } 300 301 @Override 302 /* Convenience implementation, feel free to override. */ 303 public Zone translate(Coord c) { 304 return translate(c.x, c.y); 305 } 306 307 @Override 308 /* Convenience implementation, feel free to override. */ 309 public Zone translate(int x, int y) { 310 final List<Coord> initial = getAll(); 311 final int sz = initial.size(); 312 final List<Coord> shifted = new ArrayList<Coord>(sz); 313 for (int i = 0; i < sz; i++) { 314 final Coord c = initial.get(i); 315 shifted.add(Coord.get(c.x + x, c.y + y)); 316 } 317 assert shifted.size() == sz; 318 return new ListZone(shifted); 319 } 320 321 @Override 322 /* Convenience implementation, feel free to override. */ 323 public Collection<Coord> getInternalBorder() { 324 return size() <= 1 ? getAll() : Helper.border(getAll(), null); 325 } 326 327 @Override 328 /* Convenience implementation, feel free to override. */ 329 public Collection<Coord> getExternalBorder() { 330 final int sz = size(); 331 final List<Coord> result = new ArrayList<Coord>(sz); 332 final List<Coord> internalBorder = sz <= 1 ? getAll() : Helper.border(getAll(), null); 333 final int ibsz = internalBorder.size(); 334 for (int i = 0; i < ibsz; i++) { 335 final Coord b = internalBorder.get(i); 336 for (Direction dir : Direction.OUTWARDS) { 337 final Coord borderNeighbor = b.translate(dir); 338 if (!contains(borderNeighbor)) 339 result.add(borderNeighbor); 340 } 341 } 342 return result; 343 } 344 345 @Override 346 /* Convenience implementation, feel free to override. */ 347 public Zone extend() { 348 final List<Coord> list = new ArrayList<Coord>(getAll()); 349 list.addAll(getExternalBorder()); 350 return new ListZone(list); 351 } 352 353 private int smallest(boolean xOrY) { 354 if (isEmpty()) 355 return -1; 356 int min = Integer.MAX_VALUE; 357 for (Coord c : this) { 358 final int val = xOrY ? c.x : c.y; 359 if (val < min) 360 min = val; 361 } 362 return min; 363 } 364 365 private int biggest(boolean xOrY) { 366 int max = -1; 367 for (Coord c : this) { 368 final int val = xOrY ? c.x : c.y; 369 if (max < val) 370 max = val; 371 } 372 return max; 373 } 374 } 375 final class Helper 376 { 377 private static boolean hasANeighborNotIn(Coord c, Collection<Coord> others) { 378 for (Direction dir : Direction.OUTWARDS) { 379 if (!others.contains(c.translate(dir))) 380 return true; 381 } 382 return false; 383 } 384 385 /** 386 * An easy way to get the Coord items in a List of Coord that are at the edge of the region, using 8-way 387 * adjacency (a corner is adjacent to both orthogonal and diagonal neighbors). This is not the most 388 * efficient way to do this; If you find you need to do more complicated manipulations of regions or are 389 * calling this method often, consider using {@link squidpony.squidmath.GreasedRegion}, which should be 390 * significantly faster and has better support for more intricate alterations on an area of Coords. 391 * @param zone a List of Coord representing a region 392 * @param buffer The list to fill if non null (i.e. if non-null, it is 393 * returned). If null, a fresh list will be allocated and 394 * returned. 395 * @return Elements in {@code zone} that are neighbors to an element not in {@code zone}. 396 */ 397 public static List<Coord> border(final List<Coord> zone, /* @Nullable */ List<Coord> buffer) { 398 final int zsz = zone.size(); 399 final List<Coord> border = buffer == null ? new ArrayList<Coord>(zsz / 4) : buffer; 400 for (int i = 0; i < zsz; i++) { 401 final Coord c = zone.get(i); 402 if (hasANeighborNotIn(c, zone)) 403 border.add(c); 404 } 405 return border; 406 } 407 408 } 409}