001package squidpony.squidgrid.iterator; 002 003import squidpony.squidgrid.Direction; 004import squidpony.squidmath.Coord; 005 006import java.util.NoSuchElementException; 007 008/** 009 * Instances of {@link SquidIterator}. 010 * 011 * @author smelC 012 */ 013public class SquidIterators { 014 015 /** 016 * Iterator that starts from the bottom left element of the grid, to the top 017 * right. 018 * 019 * @author smelC 020 */ 021 public static class BottomLeftToTopRight implements SquidIterator { 022 023 protected final int width; 024 protected final int height; 025 026 /** 027 * The point whose character was returned by the previous call to 028 * {@link #next()}, or {@code null} if none. 029 */ 030 protected/* @Nullable */Coord previous; 031 032 /** 033 * A fresh iterator. 034 * 035 * @param width 036 * The grid's width. 037 * @param height 038 * The grid's height. 039 */ 040 public BottomLeftToTopRight(int width, int height) { 041 this.width = width; 042 this.height = height; 043 } 044 045 @Override 046 public boolean hasNext() { 047 if (previous == null) 048 return !gridIsEmpty(); 049 else { 050 /* 051 * Previous element is not on leftmost column or not on the 052 * leftmost column's highest cell. 053 */ 054 return previous.x < width - 1 || 0 < previous.y; 055 } 056 } 057 058 @Override 059 public Coord next() { 060 if (previous == null) { 061 if (gridIsEmpty()) 062 throw new NoSuchElementException("Iterator on an empty grid has no next element"); 063 else { 064 previous = Coord.get(0, height - 1); 065 return previous; 066 } 067 } else { 068 if (previous.x == width - 1) { 069 /* On the leftmost column */ 070 if (previous.y == 0) 071 throw new NoSuchElementException( 072 "Bottom left to top right iterator has no more element"); 073 else { 074 previous = Coord.get(0, previous.y - 1); 075 return previous; 076 } 077 078 } else { 079 previous = Coord.get(previous.x + 1, previous.y); 080 return previous; 081 } 082 } 083 } 084 085 /** 086 * @return Whether {@link #above()} would return an element (i.e. not 087 * throw an exception). 088 */ 089 public boolean hasAbove() { 090 return previous != null && 0 < previous.y; 091 } 092 093 /** 094 * @return The point above the last point returned by {@link #next()}. 095 * @throws IllegalStateException 096 * If {@link #next()} wasn't called before. 097 * @throws NoSuchElementException 098 * If there's no point above the last point returned by 099 * {@link #next()}. 100 */ 101 public Coord above() { 102 if (previous == null) 103 throw new IllegalStateException("next() should be called before above()"); 104 else { 105 if (previous.y == 0) 106 throw new NoSuchElementException("There's no element above the first row"); 107 else 108 return Coord.get(previous.x, previous.y - 1); 109 } 110 } 111 112 @Override 113 public void remove() { 114 throw new UnsupportedOperationException(); 115 } 116 117 protected boolean gridIsEmpty() { 118 return width == 0 || height == 0; 119 } 120 121 } 122 123 /** 124 * An iterator that returns cells in a square around a location. Cells are 125 * iterated from bottom left to top right in this square. A square size of 126 * {@code 0} creates an iterator that returns one location (the starting 127 * one); a square of size {@code 1} is an iterator that returns at most 9 128 * locations, (start.x-1,start.y+1), (start.x,start.y+1), ...; a square of 129 * size {@code 2} returns at most ((2*2)+1)*((2*2)+1) = 25 locations, etc.. 130 * 131 * <p> 132 * Instances of this iterator never return a coordinate outside the map. 133 * </p> 134 * 135 * @author smelC 136 */ 137 public static class CenteredSquare implements SquidIterator { 138 139 protected final int width; 140 protected final int height; 141 142 protected/* @Nullable */Coord previous; 143 144 protected final int xstart; 145 protected final int ystart; 146 147 protected final int size; 148 149 protected boolean done; 150 151 /** 152 * An iterator to iterate in the square of size {@code size} around 153 * {@code (x, y)}. 154 * 155 * @param width 156 * The map's width 157 * @param height 158 * The map's height 159 * @param x 160 * The starting x coordinate. 161 * @param y 162 * The starting y coordinate. 163 * @param size 164 * The square's size. Can be {@code 0} but not negative. 165 * @throws IllegalStateException 166 * If {@code width <= 0 || height <= 0 || size < 0}. 167 */ 168 public CenteredSquare(int width, int height, int x, int y, int size) { 169 this.width = width; 170 if (width <= 0) 171 throw new IllegalStateException("Cannot build a centered square iterator over an empty grid"); 172 this.height = height; 173 if (height <= 0) 174 throw new IllegalStateException("Cannot build a centered square iterator over an empty grid"); 175 176 this.xstart = x; 177 this.ystart = y; 178 179 if (size < 0) 180 throw new IllegalStateException("Cannot build a square iterator with a negative size"); 181 182 this.size = size; 183 } 184 185 /** 186 * An iterator to iterate in the square of size {@code size} around 187 * {@code start}. 188 * 189 * @param width 190 * The grid's width 191 * @param height 192 * The grid's height 193 * @param start 194 * The starting coordinate. 195 */ 196 public CenteredSquare(int width, int height, Coord start, int size) { 197 this(width, height, start.x, start.y, size); 198 } 199 200 @Override 201 public boolean hasNext() { 202 return findNext(false) != null; 203 } 204 205 @Override 206 public Coord next() { 207 final Coord next = findNext(true); 208 if (next == null) 209 throw new NoSuchElementException(); 210 return next; 211 } 212 213 @Override 214 public void remove() { 215 throw new UnsupportedOperationException(); 216 } 217 218 protected/* @Nullable */Coord findNext(boolean mute) { 219 while (!done) { 220 final Coord result = findNext0(); 221 if (result != null) { 222 if (isInGrid(result.x, result.y)) { 223 if (mute) 224 previous = result; 225 return result; 226 } 227 /* 228 * We need to record progression, even if mutation isn't 229 * required. This is correct, because this is progression 230 * that isn't observable (skipping cells outside the map). 231 */ 232 previous = result; 233 } 234 } 235 return null; 236 } 237 238 /* 239 * This method doesn't care about validity, findNext(boolean) handles it 240 */ 241 protected/* @Nullable */Coord findNext0() { 242 if (previous == null) { 243 /* Init */ 244 /* We're in SquidLib coordinates here ((0,0) is top left) */ 245 return Coord.get(xstart - size, ystart + size); 246 } 247 248 assert xstart - size <= previous.x && previous.x <= xstart + size; 249 assert ystart - size <= previous.y && previous.y <= ystart + size; 250 251 if (previous.x == xstart + size) { 252 /* Need to go up and left (one column up, go left) */ 253 if (previous.y == ystart - size) { 254 /* We're done */ 255 done = true; 256 return null; 257 } else 258 return Coord.get(xstart - size, previous.y - 1); 259 } else { 260 /* Can go right in the same line */ 261 return Coord.get(previous.x + 1, previous.y); 262 } 263 } 264 265 protected boolean isInGrid(int x, int y) { 266 return 0 <= x && x < width && 0 <= y && y < height; 267 } 268 } 269 270 /** 271 * An iterator that starts from a cell and iterates from the bottom left to 272 * the top right, in the rectangle defined by the given width and height. 273 * Widths and heights are like list-sizes w.r.t indexes. So a rectangle of 274 * width or height 0 is empty, a rectangle of width and height 1 has one 275 * cell, a rectangle of width and height 2 has four cells, etc. 276 * 277 * <p> 278 * Put differently, the rectangle whose bottom left is (x, y) and has width 279 * and height 2, contains the cells (x, y), (x + 1, y), (x, y - 1), and (x + 280 * 1, y - 1); but it does NOT contain (x + 2, y), nor (x + 2, y - 1), nor (x 281 * + 2, y - 2). 282 * </p> 283 * 284 * @author smelC 285 */ 286 public static class RectangleFromBottomLeftToTopRight implements SquidIterator { 287 288 protected final int xstart; 289 protected final int ystart; 290 291 protected final int width; 292 protected final int height; 293 294 /** The last cell returned */ 295 protected Coord previous; 296 297 public RectangleFromBottomLeftToTopRight(Coord start, int width, int height) { 298 this.xstart = start.x; 299 this.ystart = start.y; 300 301 if (width < 0) 302 throw new IllegalStateException( 303 "Width of " + getClass().getSimpleName() + " shouldn't be negative"); 304 this.width = width; 305 if (height < 0) 306 throw new IllegalStateException( 307 "Height of " + getClass().getSimpleName() + " shouldn't be negative"); 308 this.height = height; 309 } 310 311 @Override 312 public boolean hasNext() { 313 return next0() != null; 314 } 315 316 @Override 317 public Coord next() { 318 final Coord result = next0(); 319 if (result == null) 320 throw new NoSuchElementException(); 321 previous = result; 322 return result; 323 } 324 325 @Override 326 public void remove() { 327 throw new UnsupportedOperationException(); 328 } 329 330 protected /* @Nullable */ Coord next0() { 331 if (previous == null) { 332 /* Initialization */ 333 return width == 0 || height == 0 ? null : Coord.get(xstart, ystart); 334 } else { 335 /* We're in SquidLib coordinates: (0,0) is top left */ 336 assert xstart <= previous.x && previous.x < xstart + width; 337 assert previous.y <= ystart && ystart - height < previous.y; 338 339 if (previous.x == xstart + width - 1) { 340 /* Need to go up and left (one column up, go left) */ 341 if (previous.y == ystart - (height - 1)) { 342 /* We're done */ 343 return null; 344 } else 345 /* One line above */ 346 return Coord.get(xstart, previous.y - 1); 347 } else { 348 /* Can go right in the same line */ 349 return Coord.get(previous.x + 1, previous.y); 350 } 351 } 352 } 353 } 354 355 /** 356 * An iterator that iterates around a starting position (counter clockwise). 357 * It can return at most 9 elements. Instances of this iterator only return 358 * coordinates that are valid w.r.t. to the widths and heights given at 359 * creation time (i.e. they do not go off the map). 360 * 361 * @author smelC 362 */ 363 public static class AroundCounterClockWise implements SquidIterator { 364 365 protected final int width; 366 protected final int height; 367 368 protected final int xstart; 369 protected final int ystart; 370 protected Direction prev; 371 372 /** 373 * A fresh iterator, to iterate counter clock wise around {@code start} 374 * starting on {@code start}'s right. 375 * 376 * @param width 377 * The grid's width. 378 * @param height 379 * The grid's height. 380 * @param start 381 */ 382 public AroundCounterClockWise(int width, int height, Coord start) { 383 this(width, height, start.x, start.y); 384 } 385 386 /** 387 * A fresh iterator, to iterate counter clock wise around 388 * {@code (xstart, ystart)} starting on {@code start}'s right. 389 * 390 * @param width 391 * The grid's width. 392 * @param height 393 * The grid's height. 394 * @param xstart 395 * The starting x-coordinate. 396 * @param ystart 397 * The starting y-coordinate. 398 */ 399 public AroundCounterClockWise(int width, int height, int xstart, int ystart) { 400 this.width = width; 401 this.height = height; 402 403 if (xstart < 0 || width <= xstart) 404 throw new IllegalArgumentException( 405 "x-coordinate: " + xstart + " in grid with width " + width); 406 if (ystart < 0 || height <= ystart) 407 throw new IllegalArgumentException( 408 "y-coordinate: " + ystart + " in grid with height " + height); 409 410 this.xstart = xstart; 411 this.ystart = ystart; 412 } 413 414 @Override 415 public boolean hasNext() { 416 return findNext(false) != null; 417 } 418 419 @Override 420 public Coord next() { 421 final Coord result = findNext(true); 422 if (result == null) 423 throw new NoSuchElementException(); 424 return result; 425 } 426 427 @Override 428 public void remove() { 429 throw new UnsupportedOperationException(); 430 } 431 432 /* 433 * Method does not allocate anything if it returns null or if it hits 434 * the Coords cache, which is nice. 435 */ 436 protected/* @Nullable */Coord findNext(boolean mute) { 437 Direction d = prev; 438 while (d != Direction.DOWN_RIGHT) { 439 if (d == null) 440 /* Initialization */ 441 d = Direction.DOWN_RIGHT; 442 d = d.counterClockwise(); 443 final int x = xstart + d.deltaX; 444 final int y = ystart + d.deltaY; 445 if (isInGrid(x, y)) { 446 if (mute) 447 prev = d; 448 return Coord.get(x, y); 449 } 450 } 451 return null; 452 } 453 454 protected boolean isInGrid(int x, int y) { 455 return 0 <= x && x < width && 0 <= y && y < height; 456 } 457 } 458 459 /** 460 * An iterator to iterate from a starting position (exclusive) and going up. 461 * This iterator cycles when reaching the map's bound, but it iterates at 462 * most once on a cell, i.e. it does at most one roll over a column of the 463 * map. 464 * 465 * @author smelC 466 */ 467 public static class VerticalUp implements SquidIterator { 468 469 /** The starting X-coordinate */ 470 protected final int startx; 471 472 /** The starting Y-coordinate */ 473 protected final int starty; 474 475 /* Initially null */ 476 protected Coord prev; 477 478 /** The grid's width */ 479 protected final int width; 480 /** The grid's height */ 481 protected final int height; 482 483 /** 484 * An iterator to iterate vertically, starting AFTER 485 * {@code (startx, starty)}. This iterates cycles when it reaches the 486 * map's bound, but it iterates at most once on a cell, i.e. it does at 487 * most one roll over a column of the map. 488 * 489 * @param startx 490 * The starting X-coordinate. 491 * @param starty 492 * The starting vertical-coordinate. 493 * @param width 494 * The map's width. 495 * @param height 496 * The map's height. 497 */ 498 public VerticalUp(int startx, int starty, int width, int height) { 499 if (startx < 0 || width <= startx) 500 throw new IllegalStateException( 501 "Illegal x-coordinate: " + startx + " (map's width: " + width + ")"); 502 this.startx = startx; 503 if (starty < 0 || height <= starty) 504 throw new IllegalStateException( 505 "Illegal y-coordinate: " + starty + " (map's width: " + height + ")"); 506 this.starty = starty; 507 508 this.width = width; 509 this.height = height; 510 } 511 512 /** 513 * An iterator to iterate vertically, starting AFTER {@code start}. This 514 * iterates cycles when it reaches the map's bound, but it iterates at 515 * most once on a cell, i.e. it does at most one roll over a column of 516 * the map. 517 * 518 * @param start 519 * The starting coordinate. 520 * @param width 521 * The map's width. 522 * @param height 523 * The map's height. 524 */ 525 public VerticalUp(Coord start, int width, int height) { 526 this(start.x, start.y, width, height); 527 } 528 529 @Override 530 public boolean hasNext() { 531 final Coord n = findNext(); 532 if (prev == null) 533 return n != null; 534 else { 535 /* Not done && has next */ 536 return (prev.x != startx || prev.y != starty) && n != null; 537 } 538 } 539 540 @Override 541 public Coord next() { 542 prev = findNext(); 543 if (prev == null) 544 throw new NoSuchElementException(); 545 return prev; 546 } 547 548 @Override 549 public void remove() { 550 throw new UnsupportedOperationException(); 551 } 552 553 protected Coord findNext() { 554 if (prev == null) { 555 /* First iteration */ 556 if (starty == 0) 557 /* Start from the bottom */ 558 return Coord.get(startx, height - 1); 559 else 560 /* Start from the cell above (startx, starty) */ 561 return Coord.get(startx, starty - 1); 562 } else { 563 if (prev.x == startx && prev.y == starty) 564 /* Done iterating */ 565 return null; 566 else if (prev.y == 0) { 567 /* Continue from the bottom */ 568 return Coord.get(startx, height - 1); 569 } else { 570 /* Go up */ 571 assert 0 < prev.y && prev.y < height; 572 final Coord r = Coord.get(startx, prev.y - 1); 573 if (r.y == starty) 574 /* We would return the starting position */ 575 return null; 576 else 577 return r; 578 } 579 } 580 } 581 582 } 583 584 /** 585 * An iterator to iterate from a starting position (inclusive) and going in 586 * one Direction. This iterator stops when reaching the map's bound. 587 * 588 * @author smelC 589 */ 590 public static class Linear implements SquidIterator { 591 592 /** The current X-coordinate */ 593 protected int x; 594 595 /** The Y-coordinate */ 596 protected int y; 597 598 /** The grid's width */ 599 protected final int width; 600 /** The grid's height */ 601 protected final int height; 602 protected Direction direction; 603 protected Linear() 604 { 605 width = 0; 606 height = 0; 607 } 608 public Linear(Direction direction, int startx, int y, int width, int height) { 609 this.direction = direction; 610 this.x = startx; 611 this.y = y; 612 this.width = width; 613 this.height = height; 614 } 615 616 @Override 617 public boolean hasNext() { 618 return next(true) != null; 619 } 620 621 @Override 622 public Coord next() { 623 return next(false); 624 } 625 626 @Override 627 public void remove() { 628 throw new UnsupportedOperationException(); 629 } 630 631 private /* @Nullable */Coord next(boolean peek) { 632 if (height <= y || 0 > y || width <= x || 0 > x) 633 return null; 634 final Coord result = Coord.get(x, y); 635 if (!peek) { 636 x+= direction.deltaX; 637 y+= direction.deltaY; 638 } 639 return result; 640 } 641 } 642 public static class Right extends Linear 643 { 644 public Right(int startx, int y, int width, int height) 645 { 646 super(Direction.RIGHT, startx, y, width, height); 647 } 648 } 649 public static class Left extends Linear 650 { 651 public Left(int startx, int y, int width, int height) 652 { 653 super(Direction.LEFT, startx, y, width, height); 654 } 655 } 656 public static class Up extends Linear 657 { 658 public Up(int startx, int y, int width, int height) 659 { 660 super(Direction.UP, startx, y, width, height); 661 } 662 } 663 public static class Down extends Linear 664 { 665 public Down(int startx, int y, int width, int height) 666 { 667 super(Direction.DOWN, startx, y, width, height); 668 } 669 } 670}