001package squidpony.squidgrid.mapping; 002 003import squidpony.squidgrid.Direction; 004import squidpony.squidgrid.iterator.SquidIterators; 005import squidpony.squidgrid.zone.Zone; 006import squidpony.squidmath.Coord; 007 008import java.util.*; 009 010/** 011 * Rectangles in 2D grids. Checkout {@link Utils} for utility methods. 012 * 013 * @author smelC 014 * @see RectangleRoomFinder How to find rectangles in a dungeon 015 */ 016public interface Rectangle extends Zone { 017 018 /** 019 * @return The bottom left coordinate of the room. 020 */ 021 Coord getBottomLeft(); 022 /** 023 * @return The room's width (from {@link #getBottomLeft()}). It is greater or 024 * equal than 0. 025 */ 026 @Override 027 int getWidth(); 028 029 /** 030 * @return The room's height (from {@link #getBottomLeft()}). It is greater 031 * or equal than 0. 032 */ 033 @Override 034 int getHeight(); 035 036 /** 037 * Utilities pertaining to {@link Rectangle} 038 * 039 * @author smelC 040 */ 041 class Utils { 042 043 /** 044 * A comparator that uses {@link #size(Rectangle)} as the measure. 045 */ 046 public static final Comparator<Rectangle> SIZE_COMPARATOR = new Comparator<Rectangle>() { 047 @Override 048 public int compare(Rectangle o1, Rectangle o2) { 049 return Integer.compare(size(o1), size(o2)); 050 } 051 }; 052 053 /** 054 * @param r a Rectangle 055 * @param c a Coord to check against r for presence 056 * @return Whether {@code r} contains {@code c}. 057 */ 058 public static boolean contains(Rectangle r, Coord c) { 059 return c != null && contains(r, c.x, c.y); 060 } 061 062 /** 063 * @param r a Rectangle 064 * @param x x-coordinate of a point to check against r 065 * @param y y-coordinate of a point to check against r 066 * @return Whether {@code r} contains {@code c}. 067 */ 068 public static boolean contains(Rectangle r, int x, int y) { 069 if (r == null) 070 return false; 071 final Coord bottomLeft = r.getBottomLeft(); 072 final int width = r.getWidth(); 073 final int height = r.getHeight(); 074 return !(x < bottomLeft.x /* Too much to the left */ 075 || bottomLeft.x + width < x /* Too much to the right */ 076 || bottomLeft.y < y /* Too low */ 077 || y < bottomLeft.y - height); /* Too high */ 078 } 079 080 /** 081 * @param r a Rectangle 082 * @param cs a Collection of Coord to check against r; returns true if r contains any items in cs 083 * @return {@code true} if {@code r} contains a member of {@code cs}. 084 */ 085 public static boolean containsAny(Rectangle r, Collection<Coord> cs) { 086 for (Coord c : cs) { 087 if (contains(r, c)) 088 return true; 089 } 090 return false; 091 } 092 093 /** 094 * @param rs an Iterable of Rectangle items to check against c 095 * @param c a Coord to try to find in any of the Rectangles in rs 096 * @return {@code true} if a member of {@code rs} 097 * {@link #contains(Rectangle, Coord) contains} {@code c}. 098 */ 099 public static boolean contains(Iterable<? extends Rectangle> rs, Coord c) { 100 for (Rectangle r : rs) { 101 if (contains(r, c)) 102 return true; 103 } 104 return false; 105 } 106 107 /** 108 * @param r a Rectangle 109 * @return The number of cells that {@code r} covers. 110 */ 111 public static int size(Rectangle r) { 112 return r.getWidth() * r.getHeight(); 113 } 114 115 /** 116 * @param r a Rectangle 117 * @return The center of {@code r}. 118 */ 119 public static Coord center(Rectangle r) { 120 final Coord bl = r.getBottomLeft(); 121 /* 122 * bl.y - ... : because we're in SquidLib coordinates (0,0) is top 123 * left 124 */ 125 return Coord.get(bl.x + Math.round(r.getWidth() * 0.5f), bl.y - Math.round(r.getHeight() * 0.5f)); 126 } 127 128 /** 129 * Use {@link #cellsList(Rectangle)} if you want them all. 130 * 131 * @param r a Rectangle 132 * @return The cells that {@code r} contains, from bottom left to top 133 * right; lazily computed. 134 */ 135 public static Iterator<Coord> cells(Rectangle r) { 136 return new SquidIterators.RectangleFromBottomLeftToTopRight(r.getBottomLeft(), r.getWidth(), 137 r.getHeight()); 138 } 139 140 /** 141 * Use {@link #cells(Rectangle)} if you may stop before the end of the 142 * list, you'll save some memory. 143 * 144 * @param r 145 * @return The cells that {@code r} contains, from bottom left to top 146 * right. 147 */ 148 public static List<Coord> cellsList(Rectangle r) { 149 /* Allocate it with the right size, to avoid internal resizings */ 150 final List<Coord> result = new ArrayList<Coord>(size(r)); 151 final Iterator<Coord> it = cells(r); 152 while (it.hasNext()) 153 result.add(it.next()); 154 assert result.size() == size(r); 155 return result; 156 } 157 158 /** 159 * @param d A direction. 160 * @return {@code r} extended to {@code d} by one row and/or column. 161 */ 162 public static Rectangle extend(Rectangle r, Direction d) { 163 final Coord bl = r.getBottomLeft(); 164 final int width = r.getWidth(); 165 final int height = r.getHeight(); 166 167 switch (d) { 168 case DOWN_LEFT: 169 return new Rectangle.Impl(bl.translate(Direction.DOWN_LEFT), width + 1, height + 1); 170 case DOWN_RIGHT: 171 return new Rectangle.Impl(bl.translate(Direction.DOWN), width + 1, height + 1); 172 case NONE: 173 return r; 174 case UP_LEFT: 175 return new Rectangle.Impl(bl.translate(Direction.LEFT), width + 1, height + 1); 176 case UP_RIGHT: 177 return new Rectangle.Impl(bl, width + 1, height + 1); 178 case DOWN: 179 return new Rectangle.Impl(bl.translate(Direction.DOWN), width, height + 1); 180 case LEFT: 181 return new Rectangle.Impl(bl.translate(Direction.LEFT), width + 1, height); 182 case RIGHT: 183 return new Rectangle.Impl(bl, width + 1, height); 184 case UP: 185 return new Rectangle.Impl(bl, width, height + 1); 186 } 187 throw new IllegalStateException("Unmatched direction in Rectangle.Utils::extend: " + d); 188 } 189 190 /** 191 * @param r 192 * @param dir 193 * @return The coord at the corner identified by {@code dir} in 194 * {@code r}. 195 */ 196 public static Coord getCorner(Rectangle r, Direction dir) { 197 switch (dir) { 198 case DOWN_LEFT: 199 return r.getBottomLeft(); 200 case DOWN_RIGHT: 201 return r.getBottomLeft().translate(r.getWidth() - 1, 0); 202 case UP_LEFT: 203 /* -y because in SquidLib higher y is smaller */ 204 return r.getBottomLeft().translate(0, -(r.getHeight() - 1)); 205 case UP_RIGHT: 206 /* -y because in SquidLib higher y is smaller */ 207 return r.getBottomLeft().translate(r.getWidth() - 1, -(r.getHeight() - 1)); 208 case NONE: 209 return r.getCenter(); 210 case DOWN: 211 case LEFT: 212 case RIGHT: 213 case UP: 214 final Coord c1 = getCorner(r, dir.clockwise()); 215 final Coord c2 = getCorner(r, dir.counterClockwise()); 216 return Coord.get((c1.x + c2.x) / 2, (c1.y + c2.y) / 2); 217 } 218 throw new IllegalStateException("Unmatched direction in Rectangle.Utils::getCorner: " + dir); 219 } 220 221 /** 222 * @param r 223 * @param buf 224 * An array of (at least) size 4, to hold the 4 corners. It 225 * is returned, except if {@code null} or too small, in which 226 * case a fresh array is returned. 227 * @return {@code buf}, if it had length of at least 4, or a new 4-element array; it contains this Rectangle's 4 corners 228 */ 229 public static Coord[] getAll4Corners(Rectangle r, Coord[] buf) { 230 final Coord[] result = buf == null || buf.length < 4 ? new Coord[4] : buf; 231 result[0] = getCorner(r, Direction.DOWN_LEFT); 232 result[1] = getCorner(r, Direction.DOWN_RIGHT); 233 result[2] = getCorner(r, Direction.UP_RIGHT); 234 result[3] = getCorner(r, Direction.UP_LEFT); 235 return result; 236 } 237 238 /** 239 * Creates a new Rectangle that is smaller than r by 1 cell from each of r's edges, to a minimum of a 1x1 cell. 240 * @param r a Rectangle to shrink 241 * @return the shrunken Rectangle, newly-allocated 242 */ 243 public static Rectangle shrink(Rectangle r) 244 { 245 return new Rectangle.Impl(r.getBottomLeft().translate(1, 1), 246 Math.max(1, r.getWidth() - 2), Math.max(1, r.getHeight() - 2)); 247 } 248 249 /** 250 * @param r 251 * @param cardinal 252 * @param buf 253 * The buffer to fill or {@code null} to let this method 254 * allocate. 255 * @return The border of {@code r} at the position {@code cardinal}, 256 * i.e. the lowest line if {@code r} is {@link Direction#DOWN}, 257 * the highest line if {@code r} is {@link Direction#UP}, the 258 * leftest column if {@code r} is {@link Direction#LEFT}, and 259 * the rightest column if {@code r} is {@link Direction#RIGHT}. 260 */ 261 public static List<Coord> getBorder(Rectangle r, Direction cardinal, 262 /* @Nullable */ List<Coord> buf) { 263 Coord start = null; 264 Direction dir = null; 265 int len = -1; 266 switch (cardinal) { 267 case DOWN: 268 case UP: 269 len = r.getWidth(); 270 dir = Direction.RIGHT; 271 start = cardinal == Direction.DOWN ? r.getBottomLeft() : getCorner(r, Direction.UP_LEFT); 272 break; 273 case LEFT: 274 case RIGHT: 275 len = r.getHeight(); 276 dir = Direction.UP; 277 start = cardinal == Direction.LEFT ? r.getBottomLeft() : getCorner(r, Direction.DOWN_RIGHT); 278 break; 279 case DOWN_LEFT: 280 case DOWN_RIGHT: 281 case NONE: 282 case UP_LEFT: 283 case UP_RIGHT: 284 throw new IllegalStateException( 285 "Expected a cardinal direction in Rectangle.Utils::getBorder. Received: " + cardinal); 286 } 287 if (start == null) 288 throw new IllegalStateException( 289 "Unmatched direction in Rectangle.Utils::Border: " + cardinal); 290 291 final List<Coord> result = buf == null ? new ArrayList<Coord>(len) : buf; 292 Coord now = start; 293 for (int i = 0; i < len; i++) { 294 result.add(now); 295 now = now.translate(dir); 296 } 297 return result; 298 } 299 } 300 301 /** 302 * @author smelC 303 */ 304 class Impl extends Zone.Skeleton implements Rectangle { 305 306 protected final Coord bottomLeft; 307 protected final int width; 308 protected final int height; 309 310 private static final long serialVersionUID = -6197401003733967116L; 311 312 public Impl(Coord bottomLeft, int width, int height) { 313 this.bottomLeft = bottomLeft; 314 this.width = width; 315 this.height = height; 316 } 317 318 @Override 319 public Coord getBottomLeft() { 320 return bottomLeft; 321 } 322 323 @Override 324 public int getWidth() { 325 return width; 326 } 327 328 @Override 329 public int getHeight() { 330 return height; 331 } 332 333 @Override 334 public int hashCode() { 335 final int prime = 31; 336 int result = 1; 337 result = prime * result + ((bottomLeft == null) ? 0 : bottomLeft.hashCode()); 338 result = prime * result + height; 339 result = prime * result + width; 340 return result; 341 } 342 343 @Override 344 public boolean equals(Object obj) { 345 if (this == obj) 346 return true; 347 if (obj == null) 348 return false; 349 if (getClass() != obj.getClass()) 350 return false; 351 Impl other = (Impl) obj; 352 if (bottomLeft == null) { 353 if (other.bottomLeft != null) 354 return false; 355 } else if (!bottomLeft.equals(other.bottomLeft)) 356 return false; 357 if (height != other.height) 358 return false; 359 return width == other.width; 360 } 361 362 @Override 363 public String toString() { 364 return "Rectangle at " + bottomLeft + ", width:" + width + ", height:" + height; 365 } 366 367 // Implementation of Zone: 368 369 @Override 370 public boolean isEmpty() { 371 return width == 0 || height == 0; 372 } 373 374 @Override 375 public int size() { 376 return width * height; 377 } 378 379 @Override 380 public boolean contains(int x, int y) { 381 return x >= bottomLeft.x && x < bottomLeft.x + width && y <= bottomLeft.y 382 && bottomLeft.y - height < y; 383 } 384 385 @Override 386 public boolean contains(Coord c) { 387 return contains(c.x, c.y); 388 } 389 390 @Override 391 public int xBound(boolean smallestOrBiggest) { 392 return bottomLeft.x + (smallestOrBiggest ? 0 : getWidth() - 1); 393 } 394 395 @Override 396 public int yBound(boolean smallestOrBiggest) { 397 return bottomLeft.y - (smallestOrBiggest ? (getHeight() - 1) : 0); 398 } 399 400 @Override 401 public Coord getCenter() { 402 return Utils.center(this); 403 } 404 405 @Override 406 public List<Coord> getAll() { 407 final List<Coord> result = Utils.cellsList(this); 408 assert result.size() == size(); 409 return result; 410 } 411 412 @Override 413 public Zone translate(int x, int y) { 414 return new Impl(bottomLeft.translate(x, y), width, height); 415 } 416 417 @Override 418 public List<Coord> getInternalBorder() { 419 if (width <= 1 || height <= 1) 420 return getAll(); 421 final int expectedSize = width + (height - 1) + (width - 1) + (height - 2); 422 final List<Coord> result = new ArrayList<Coord>(expectedSize); 423 Coord current = Utils.getCorner(this, Direction.DOWN_LEFT); 424 for (int i = 0; i < width; i++) { 425 assert !result.contains(current); 426 result.add(current); 427 current = current.translate(Direction.RIGHT); 428 } 429 current = Utils.getCorner(this, Direction.UP_LEFT); 430 for (int i = 0; i < width; i++) { 431 assert !result.contains(current); 432 result.add(current); 433 current = current.translate(Direction.RIGHT); 434 } 435 current = Utils.getCorner(this, Direction.DOWN_LEFT); 436 /* Stopping at height - 1 to avoid doublons */ 437 for (int i = 0; i < height - 1; i++) { 438 if (0 < i) { 439 /* 440 * To avoid doublons (with the very first value of 'current' 441 * atop this method. 442 */ 443 assert !result.contains(current); 444 result.add(current); 445 } 446 current = current.translate(Direction.UP); 447 } 448 current = Utils.getCorner(this, Direction.DOWN_RIGHT); 449 /* Stopping at height - 1 to avoid doublons */ 450 for (int i = 0; i < height - 1; i++) { 451 if (0 < i) { 452 /* 453 * To avoid doublons (with the very first value of 'current' 454 * atop this method. 455 */ 456 assert !result.contains(current); 457 result.add(current); 458 } 459 current = current.translate(Direction.UP); 460 } 461 assert result.size() == expectedSize; 462 return result; 463 } 464 465 @Override 466 public Collection<Coord> getExternalBorder() { 467 final Rectangle extension = extend(); 468 final List<Coord> result = new ArrayList<Coord>( 469 (extension.getWidth() + extension.getHeight()) * 2); 470 for (Direction dir : Direction.CARDINALS) 471 Utils.getBorder(extension, dir, result); 472 return result; 473 } 474 475 @Override 476 public Rectangle extend() { 477 return new Rectangle.Impl(bottomLeft.translate(Direction.DOWN_LEFT), width + 2, height + 2); 478 } 479 480 @Override 481 public Iterator<Coord> iterator() { 482 /* Do not rely on getAll(), to avoid allocating the list */ 483 return Rectangle.Utils.cells(this); 484 } 485 } 486 487}