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 = false;
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. Widths
273         * and heights are like list-sizes w.r.t indexes. So a rectangle of width or height 0
274         * is empty, a rectangle of width and height 1 has one cell, a rectangle
275         * 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),
280         * (x, y - 1), and (x + 1, y - 1); but it does NOT contain (x + 2, y), nor
281         * (x + 2, y - 1), nor (x + 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 = null;
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                        }
335                        else {
336                                /* We're in SquidLib coordinates: (0,0) is top left */
337                                assert xstart <= previous.x && previous.x < xstart + width;
338                                assert previous.y <= ystart && ystart - height < previous.y;
339
340                                if (previous.x == xstart + width - 1) {
341                                        /* Need to go up and left (one column up, go left) */
342                                        if (previous.y == ystart - (height - 1) || previous.y == 0) {
343                                                /* We're done */
344                                                return null;
345                                        } else
346                                                /* One line above */
347                                                return Coord.get(xstart, previous.y - 1);
348                                } else {
349                                        /* Can go right in the same line */
350                                        return Coord.get(previous.x + 1, previous.y);
351                                }
352                        }
353                }
354        }
355
356        /**
357         * An iterator that iterates around a starting position (counter clockwise).
358         * It can return at most 9 elements. Instances of this iterator only return
359         * coordinates that are valid w.r.t. to the widths and heights given at
360         * creation time (i.e. they do not go off the map).
361         * 
362         * @author smelC
363         */
364        public static class AroundCounterClockWise implements SquidIterator {
365
366                protected final int width;
367                protected final int height;
368
369                protected final int xstart;
370                protected final int ystart;
371                protected Direction prev;
372
373                /**
374                 * A fresh iterator, to iterate counter clock wise around {@code start}
375                 * starting on {@code start}'s right.
376                 * 
377                 * @param width
378                 *            The grid's width.
379                 * @param height
380                 *            The grid's height.
381                 * @param start
382                 */
383                public AroundCounterClockWise(int width, int height, Coord start) {
384                        this(width, height, start.x, start.y);
385                }
386
387                /**
388                 * A fresh iterator, to iterate counter clock wise around
389                 * {@code (xstart, ystart)} starting on {@code start}'s right.
390                 * 
391                 * @param width
392                 *            The grid's width.
393                 * @param height
394                 *            The grid's height.
395                 * @param xstart
396                 *            The starting x-coordinate.
397                 * @param ystart
398                 *            The starting y-coordinate.
399                 */
400                public AroundCounterClockWise(int width, int height, int xstart, int ystart) {
401                        this.width = width;
402                        this.height = height;
403
404                        if (xstart < 0 || width <= xstart)
405                                throw new IllegalArgumentException(
406                                                "x-coordinate: " + xstart + " in grid with width " + width);
407                        if (ystart < 0 || height <= ystart)
408                                throw new IllegalArgumentException(
409                                                "y-coordinate: " + ystart + " in grid with height " + height);
410
411                        this.xstart = xstart;
412                        this.ystart = ystart;
413                }
414
415                @Override
416                public boolean hasNext() {
417                        return findNext(false) != null;
418                }
419
420                @Override
421                public Coord next() {
422                        final Coord result = findNext(true);
423                        if (result == null)
424                                throw new NoSuchElementException();
425                        return result;
426                }
427
428                @Override
429                public void remove() {
430                        throw new UnsupportedOperationException();
431                }
432
433                /*
434                 * Method does not allocate anything if it returns null or if it hits
435                 * the Coords cache, which is nice.
436                 */
437                protected/* @Nullable */Coord findNext(boolean mute) {
438                        Direction d = prev;
439                        while (d != Direction.DOWN_RIGHT) {
440                                if (d == null)
441                                        /* Initialization */
442                                        d = Direction.DOWN_RIGHT;
443                                d = d.counterClockwise();
444                                final int x = xstart + d.deltaX;
445                                final int y = ystart + d.deltaY;
446                                if (isInGrid(x, y)) {
447                                        if (mute)
448                                                prev = d;
449                                        return Coord.get(x, y);
450                                }
451                        }
452                        return null;
453                }
454
455                protected boolean isInGrid(int x, int y) {
456                        return 0 <= x && x < width && 0 <= y && y < height;
457                }
458        }
459
460        /**
461         * An iterator to iterate from a starting position (exclusive) and going up.
462         * This iterator cycles when reaching the map's bound, but it iterates at
463         * most once on a cell, i.e. it does at most one roll over a column of the
464         * map.
465         * 
466         * @author smelC
467         */
468        public static class VerticalUp implements SquidIterator {
469
470                /** The starting X-coordinate */
471                protected final int startx;
472
473                /** The starting Y-coordinate */
474                protected final int starty;
475
476                /* Initially null */
477                protected Coord prev;
478
479                /** The grid's width */
480                protected final int width;
481                /** The grid's height */
482                protected final int height;
483
484                /**
485                 * An iterator to iterate vertically, starting AFTER
486                 * {@code (startx, starty)}. This iterates cycles when it reaches the
487                 * map's bound, but it iterates at most once on a cell, i.e. it does at
488                 * most one roll over a column of the map.
489                 * 
490                 * @param startx
491                 *            The starting X-coordinate.
492                 * @param starty
493                 *            The starting vertical-coordinate.
494                 * @param width
495                 *            The map's width.
496                 * @param height
497                 *            The map's height.
498                 */
499                public VerticalUp(int startx, int starty, int width, int height) {
500                        if (startx < 0 || width <= startx)
501                                throw new IllegalStateException(
502                                                "Illegal x-coordinate: " + startx + " (map's width: " + width + ")");
503                        this.startx = startx;
504                        if (starty < 0 || height <= starty)
505                                throw new IllegalStateException(
506                                                "Illegal y-coordinate: " + starty + " (map's width: " + height + ")");
507                        this.starty = starty;
508
509                        this.width = width;
510                        this.height = height;
511                }
512
513                /**
514                 * An iterator to iterate vertically, starting AFTER {@code start}. This
515                 * iterates cycles when it reaches the map's bound, but it iterates at
516                 * most once on a cell, i.e. it does at most one roll over a column of
517                 * the map.
518                 * 
519                 * @param start
520                 *            The starting coordinate.
521                 * @param width
522                 *            The map's width.
523                 * @param height
524                 *            The map's height.
525                 */
526                public VerticalUp(Coord start, int width, int height) {
527                        this(start.x, start.y, width, height);
528                }
529
530                @Override
531                public boolean hasNext() {
532                        final Coord n = findNext();
533                        if (prev == null)
534                                return n != null;
535                        else {
536                                /* Not done && has next */
537                                return (prev.x != startx || prev.y != starty) && n != null;
538                        }
539                }
540
541                @Override
542                public Coord next() {
543                        prev = findNext();
544                        if (prev == null)
545                                throw new NoSuchElementException();
546                        return prev;
547                }
548
549                @Override
550                public void remove() {
551                        throw new UnsupportedOperationException();
552                }
553
554                protected Coord findNext() {
555                        if (prev == null) {
556                                /* First iteration */
557                                if (starty == 0)
558                                        /* Start from the bottom */
559                                        return Coord.get(startx, height - 1);
560                                else
561                                        /* Start from the cell above (startx, starty) */
562                                        return Coord.get(startx, starty - 1);
563                        } else {
564                                if (prev.x == startx && prev.y == starty)
565                                        /* Done iterating */
566                                        return null;
567                                else if (prev.y == 0) {
568                                        /* Continue from the bottom */
569                                        return Coord.get(startx, height - 1);
570                                } else {
571                                        /* Go up */
572                                        assert 0 < prev.y && prev.y < height;
573                                        final Coord r = Coord.get(startx, prev.y - 1);
574                                        if (r.y == starty)
575                                                /* We would return the starting position */
576                                                return null;
577                                        else
578                                                return r;
579                                }
580                        }
581                }
582
583        }
584}