001package squidpony.squidgrid; 002 003import squidpony.squidmath.*; 004 005import java.util.*; 006 007/** 008 * A data structure that seems to be re-implemented often for games, this associates Coord positions and generic I 009 * identities with generic E elements. You can get an element from a SpatialMap with either an identity or a position, 010 * change the position of an element without changing its value or identity, modify an element given its identity and 011 * a new value, and perform analogues to most of the features of the Map interface, though this does not implement Map 012 * because it essentially has two key types and one value type. You can also iterate through the values in insertion 013 * order, where insertion order should be stable even when elements are moved or modified (the relevant key is the 014 * identity, which is never changed in this class). Uses two OrderedMap fields internally. 015 * Created by Tommy Ettinger on 1/2/2016. 016 */ 017public class SpatialMap<I, E> implements Iterable<E> { 018 019 public static class SpatialTriple<I,E> 020 { 021 public Coord position; 022 public I id; 023 public E element; 024 025 public SpatialTriple() 026 { 027 position = Coord.get(0,0); 028 id = null; 029 element = null; 030 } 031 public SpatialTriple(Coord position, I id, E element) { 032 this.position = position; 033 this.id = id; 034 this.element = element; 035 } 036 037 @Override 038 public boolean equals(Object o) { 039 if (this == o) return true; 040 if (o == null || getClass() != o.getClass()) return false; 041 042 SpatialTriple<?, ?> that = (SpatialTriple<?, ?>) o; 043 044 if (position != null ? !position.equals(that.position) : that.position != null) return false; 045 if (id != null ? !id.equals(that.id) : that.id != null) return false; 046 return element != null ? element.equals(that.element) : that.element == null; 047 048 } 049 050 @Override 051 public int hashCode() { 052 int result = position != null ? position.hashCode() : 0; 053 result = 31 * result + (id != null ? id.hashCode() : 0); 054 result = 31 * result + (element != null ? element.hashCode() : 0); 055 return result; 056 } 057 } 058 059 protected OrderedMap<I, SpatialTriple<I, E>> itemMapping; 060 protected OrderedMap<Coord, SpatialTriple<I, E>> positionMapping; 061 062 /** 063 * Constructs a SpatialMap with capacity 32. 064 */ 065 public SpatialMap() 066 { 067 itemMapping = new OrderedMap<>(32); 068 positionMapping = new OrderedMap<>(32); 069 } 070 071 /** 072 * Constructs a SpatialMap with the given capacity 073 * @param capacity the capacity for each of the internal OrderedMaps 074 */ 075 public SpatialMap(int capacity) 076 { 077 itemMapping = new OrderedMap<>(capacity); 078 positionMapping = new OrderedMap<>(capacity); 079 } 080 081 /** 082 * Constructs a SpatialMap given arrays of Coord, identity, and element; all 3 arrays should have the same length, 083 * since this will use only up to the minimum length of these arrays for how many it adds. Each unique id will be 084 * added with the corresponding element at the corresponding Coord position if that position is not already filled. 085 * @param coords a starting array of Coord positions; indices here correspond to the other parameters 086 * @param ids a starting array of identities; indices here correspond to the other parameters 087 * @param elements a starting array of elements; indices here correspond to the other parameters 088 */ 089 public SpatialMap(Coord[] coords, I[] ids, E[] elements) 090 { 091 itemMapping = new OrderedMap<>( 092 Math.min(coords.length, Math.min(ids.length, elements.length))); 093 positionMapping = new OrderedMap<>( 094 Math.min(coords.length, Math.min(ids.length, elements.length))); 095 096 for (int i = 0; i < coords.length && i < ids.length && i < elements.length; i++) { 097 add(coords[i], ids[i], elements[i]); 098 } 099 } 100 101 /** 102 * Constructs a SpatialMap given collections of Coord, identity, and element; all 3 collections should have the same 103 * length, since this will use only up to the minimum length of these collections for how many it adds. Each unique 104 * id will be added with the corresponding element at the corresponding Coord position if that position is not 105 * already filled. 106 * @param coords a starting collection of Coord positions; indices here correspond to the other parameters 107 * @param ids a starting collection of identities; indices here correspond to the other parameters 108 * @param elements a starting collection of elements; indices here correspond to the other parameters 109 */ 110 public SpatialMap(Collection<Coord> coords, Collection<I> ids, Collection<E> elements) 111 { 112 itemMapping = new OrderedMap<>( 113 Math.min(coords.size(), Math.min(ids.size(), elements.size()))); 114 positionMapping = new OrderedMap<>( 115 Math.min(coords.size(), Math.min(ids.size(), elements.size()))); 116 if(itemMapping.size() <= 0) 117 return; 118 Iterator<Coord> cs = coords.iterator(); 119 Iterator<I> is = ids.iterator(); 120 Iterator<E> es = elements.iterator(); 121 Coord c = cs.next(); 122 I i = is.next(); 123 E e = es.next(); 124 for (; cs.hasNext() && is.hasNext() && es.hasNext(); c = cs.next(), i = is.next(), e = es.next()) { 125 add(c, i, e); 126 } 127 } 128 129 /** 130 * Adds a new element with the given identity and Coord position. If the position is already occupied by an element 131 * in this data structure, does nothing. If the identity is already used, this also does nothing. If the identity 132 * and position are both unused, this adds element to the data structure. 133 * <br> 134 * You should strongly avoid calling remove() and add() to change an element; prefer modify() and move(). 135 * @param coord the Coord position to place the element at; should be empty 136 * @param id the identity to associate the element with; should be unused 137 * @param element the element to add 138 */ 139 public void add(Coord coord, I id, E element) 140 { 141 if(itemMapping.containsKey(id)) 142 return; 143 if(!positionMapping.containsKey(coord)) 144 { 145 SpatialTriple<I, E> triple = new SpatialTriple<>(coord, id, element); 146 itemMapping.put(id, triple); 147 positionMapping.put(coord, triple); 148 } 149 } 150 151 /** 152 * Inserts a new element with the given identity and Coord position, potentially overwriting an existing element. 153 * <br> 154 * If you want to alter an existing element, use modify() or move(). 155 * @param coord the Coord position to place the element at; should be empty 156 * @param id the identity to associate the element with; should be unused 157 * @param element the element to add 158 */ 159 public void put(Coord coord, I id, E element) 160 { 161 SpatialTriple<I, E> triple = new SpatialTriple<>(coord, id, element); 162 itemMapping.remove(id); 163 positionMapping.remove(coord); 164 itemMapping.put(id, triple); 165 positionMapping.put(coord, triple); 166 } 167 168 /** 169 * Inserts a SpatialTriple into this SpatialMap without changing it, potentially overwriting an existing element. 170 * SpatialTriple objects can be obtained by the triples() or tripleIterator() methods, and can also be constructed 171 * on their own. 172 * <br> 173 * If you want to alter an existing element, use modify() or move(). 174 * @param triple a SpatialTriple (an inner class of SpatialMap) with the same type parameters as this class 175 */ 176 public void put(SpatialTriple<I, E> triple) 177 { 178 itemMapping.remove(triple.id); 179 positionMapping.remove(triple.position); 180 itemMapping.put(triple.id, triple); 181 positionMapping.put(triple.position, triple); 182 } 183 184 /** 185 * Changes the element's value associated with id. The key id should exist before calling this; if there is no 186 * matching id, this returns null. 187 * @param id the identity of the element to modify 188 * @param newValue the element value to replace the previous element with. 189 * @return the previous element value associated with id 190 */ 191 public E modify(I id, E newValue) 192 { 193 SpatialTriple<I, E> gotten = itemMapping.get(id); 194 if(gotten != null) { 195 E previous = gotten.element; 196 gotten.element = newValue; 197 return previous; 198 } 199 return null; 200 } 201 /** 202 * Changes the element's value associated with pos. The key pos should exist before calling this; if there is no 203 * matching position, this returns null. 204 * @param pos the position of the element to modify 205 * @param newValue the element value to replace the previous element with. 206 * @return the previous element value associated with id 207 */ 208 public E positionalModify(Coord pos, E newValue) 209 { 210 SpatialTriple<I, E> gotten = positionMapping.get(pos); 211 if(gotten != null) { 212 E previous = gotten.element; 213 gotten.element = newValue; 214 return previous; 215 } 216 return null; 217 } 218 219 /** 220 * Move an element from one position to another; moves whatever is at the Coord position previous to the new Coord 221 * position target. The element will not be present at its original position if target is unoccupied, but nothing 222 * will change if target is occupied. 223 * @param previous the starting Coord position of an element to move 224 * @param target the Coord position to move the element to 225 * @return the moved element if movement was successful or null otherwise 226 */ 227 public E move(Coord previous, Coord target) 228 { 229 if(positionMapping.containsKey(previous) && !positionMapping.containsKey(target)) { 230 SpatialTriple<I, E> gotten = positionMapping.remove(previous); 231 gotten.position = target; 232 positionMapping.put(target, gotten); 233 return gotten.element; 234 } 235 return null; 236 } 237 238 /** 239 * Move an element, picked by its identity, to a new Coord position. Finds the element using only the id, and does 240 * not need the previous position. The target position must be empty for this to move successfully, and the id must 241 * exist in this data structure for this to move anything. 242 * @param id the identity of the element to move 243 * @param target the Coord position to move the element to 244 * @return the moved element if movement was successful or null otherwise 245 */ 246 public E move(I id, Coord target) 247 { 248 if(itemMapping.containsKey(id) && !positionMapping.containsKey(target)) { 249 SpatialTriple<I, E> gotten = itemMapping.get(id); 250 positionMapping.remove(gotten.position); 251 gotten.position = target; 252 positionMapping.put(target, gotten); 253 return gotten.element; 254 } 255 return null; 256 } 257 258 /** 259 * Removes the element at the given position from all storage in this data structure. 260 * <br> 261 * You should strongly avoid calling remove() and add() to change an element; prefer modify() and move(). 262 * @param coord the position of the element to remove 263 * @return the value of the element that was removed or null if nothing was present at the position 264 */ 265 public E remove(Coord coord) 266 { 267 SpatialTriple<I, E> gotten = positionMapping.remove(coord); 268 if(gotten != null) { 269 itemMapping.remove(gotten.id); 270 return gotten.element; 271 } 272 return null; 273 } 274 /** 275 * Removes the element with the given identity from all storage in this data structure. 276 * <br> 277 * You should strongly avoid calling remove() and add() to change an element; prefer modify() and move(). 278 * @param id the identity of the element to remove 279 * @return the value of the element that was removed or null if nothing was present at the position 280 */ 281 public E remove(I id) 282 { 283 SpatialTriple<I, E> gotten = itemMapping.remove(id); 284 if(gotten != null) { 285 positionMapping.remove(gotten.position); 286 return gotten.element; 287 } 288 return null; 289 } 290 291 /** 292 * Checks whether this contains the given element. Slower than containsKey and containsPosition (linear time). 293 * @param o an Object that should be an element if you expect this to possibly return true 294 * @return true if o is contained as an element in this data structure 295 */ 296 public boolean containsValue(Object o) 297 { 298 if(o == null) 299 { 300 for(SpatialTriple<I,E> v : itemMapping.values()) 301 { 302 if(v != null && v.element == null) 303 return true; 304 } 305 } 306 else { 307 for (SpatialTriple<I, E> v : itemMapping.values()) { 308 if (v != null && v.element != null && v.element.equals(o)) 309 return true; 310 } 311 } 312 return false; 313 } 314 /** 315 * Checks whether this contains the given identity key. 316 * @param o an Object that should be of the generic I type if you expect this to possibly return true 317 * @return true if o is an identity key that can be used with this data structure 318 */ 319 public boolean containsKey(Object o) 320 { 321 return itemMapping.containsKey(o); 322 } 323 /** 324 * Checks whether this contains anything at the given position. 325 * @param o an Object that should be a Coord if you expect this to possibly return true 326 * @return true if o is a Coord that is associated with some element in this data structure 327 */ 328 public boolean containsPosition(Object o) 329 { 330 return positionMapping.containsKey(o); 331 } 332 333 /** 334 * Gets the element at the given Coord position. 335 * @param c the position to get an element from 336 * @return the element if it exists or null otherwise 337 */ 338 public E get(Coord c) 339 { 340 SpatialTriple<I, E> gotten = positionMapping.get(c); 341 if(gotten != null) 342 return gotten.element; 343 return null; 344 } 345 346 /** 347 * Gets the element with the given identity. 348 * @param i the identity of the element to get 349 * @return the element if it exists or null otherwise 350 */ 351 public E get(I i) 352 { 353 SpatialTriple<I, E> gotten = itemMapping.get(i); 354 if(gotten != null) 355 return gotten.element; 356 return null; 357 } 358 359 /** 360 * Gets the position of the element with the given identity. 361 * @param i the identity of the element to get a position from 362 * @return the position of the element if it exists or null otherwise 363 */ 364 public Coord getPosition(I i) 365 { 366 SpatialTriple<I, E> gotten = itemMapping.get(i); 367 if(gotten != null) 368 return gotten.position; 369 return null; 370 } 371 372 /** 373 * Gets the identity of the element at the given Coord position. 374 * @param c the position to get an identity from 375 * @return the identity of the element if it exists at the given position or null otherwise 376 */ 377 public I getIdentity(Coord c) 378 { 379 SpatialTriple<I, E> gotten = positionMapping.get(c); 380 if(gotten != null) 381 return gotten.id; 382 return null; 383 } 384 385 /** 386 * Get a Set of all positions used for values in this data structure, returning a OrderedSet (defensively copying 387 * the key set used internally) for its stable iteration order. 388 * @return a OrderedSet of Coord corresponding to the positions present in this data structure. 389 */ 390 public OrderedSet<Coord> positions() 391 { 392 return new OrderedSet<>(positionMapping.keySet()); 393 } 394 /** 395 * Get a Set of all identities used for values in this data structure, returning a OrderedSet (defensively 396 * copying the key set used internally) for its stable iteration order. 397 * @return a OrderedSet of I corresponding to the identities present in this data structure. 398 */ 399 public OrderedSet<I> identities() 400 { 401 return new OrderedSet<>(itemMapping.keySet()); 402 } 403 404 /** 405 * Gets all data stored in this as a collection of values similar to Map.Entry, but containing a Coord, I, and E 406 * value for each entry, in insertion order. The type is SpatialTriple, defined in a nested class. 407 * @return a Collection of SpatialTriple of I, E 408 */ 409 public Collection<SpatialTriple<I, E>> triples() 410 { 411 return itemMapping.values(); 412 } 413 414 /** 415 * Given an Iterable (such as a List, Set, or other Collection) of Coord, gets all elements in this SpatialMap that 416 * share a position with one of the Coord objects in positions and returns them as an ArrayList of elements. 417 * @param positions an Iterable (such as a List or Set) of Coord 418 * @return an ArrayList, possibly empty, of elements that share a position with a Coord in positions 419 */ 420 public ArrayList<E> getManyPositions(Iterable<Coord> positions) 421 { 422 ArrayList<E> gotten = new ArrayList<>(); 423 SpatialTriple<I, E> ie; 424 for(Coord p : positions) 425 { 426 if((ie = positionMapping.get(p)) != null) 427 gotten.add(ie.element); 428 } 429 return gotten; 430 } 431 432 /** 433 * Given an Iterable (such as a List, Set, or other Collection) of I, gets all elements in this SpatialMap that 434 * share an identity with one of the I objects in identities and returns them as an ArrayList of elements. 435 * @param identities an Iterable (such as a List or Set) of I 436 * @return an ArrayList, possibly empty, of elements that share an Identity with an I in identities 437 */ 438 public ArrayList<E> getManyIdentities(Iterable<I> identities) 439 { 440 ArrayList<E> gotten = new ArrayList<>(); 441 SpatialTriple<I, E> ie; 442 for(I i : identities) 443 { 444 if((ie = itemMapping.get(i)) != null) 445 gotten.add(ie.element); 446 } 447 return gotten; 448 } 449 450 /** 451 * Given an array of Coord, gets all elements in this SpatialMap that share a position with one of the Coord objects 452 * in positions and returns them as an ArrayList of elements. 453 * @param positions an array of Coord 454 * @return an ArrayList, possibly empty, of elements that share a position with a Coord in positions 455 */ 456 public ArrayList<E> getManyPositions(Coord[] positions) 457 { 458 ArrayList<E> gotten = new ArrayList<>(positions.length); 459 SpatialTriple<I, E> ie; 460 for(Coord p : positions) 461 { 462 if((ie = positionMapping.get(p)) != null) 463 gotten.add(ie.element); 464 } 465 return gotten; 466 } 467 /** 468 * Given an array of I, gets all elements in this SpatialMap that share an identity with one of the I objects in 469 * identities and returns them as an ArrayList of elements. 470 * @param identities an array of I 471 * @return an ArrayList, possibly empty, of elements that share an Identity with an I in identities 472 */ 473 public ArrayList<E> getManyIdentities(I[] identities) 474 { 475 ArrayList<E> gotten = new ArrayList<>(identities.length); 476 SpatialTriple<I, E> ie; 477 for(I i : identities) 478 { 479 if((ie = itemMapping.get(i)) != null) 480 gotten.add(ie.element); 481 } 482 return gotten; 483 } 484 485 public E randomElement(IRNG rng) 486 { 487 if(itemMapping.isEmpty()) 488 return null; 489 return itemMapping.randomValue(rng).element; 490 } 491 492 public Coord randomPosition(IRNG rng) 493 { 494 if(positionMapping.isEmpty()) 495 return null; 496 return positionMapping.randomKey(rng); 497 } 498 public I randomIdentity(IRNG rng) 499 { 500 if(itemMapping.isEmpty()) 501 return null; 502 return itemMapping.randomKey(rng); 503 } 504 505 public SpatialTriple<I, E> randomEntry(IRNG rng) 506 { 507 if(itemMapping.isEmpty()) 508 return null; 509 return itemMapping.randomValue(rng); 510 } 511 512 /** 513 * Given the size and position of a rectangular area, creates a new SpatialMap from this one that refers only to the 514 * subsection of this SpatialMap shared with the rectangular area. Will not include any elements from this 515 * SpatialMap with positions beyond the bounds of the given rectangular area, and will include all elements from 516 * this that are in the area. 517 * @param x the minimum x-coordinate of the rectangular area 518 * @param y the minimum y-coordinate of the rectangular area 519 * @param width the total width of the rectangular area 520 * @param height the total height of the rectangular area 521 * @return a new SpatialMap that refers to a subsection of this one 522 */ 523 public SpatialMap<I, E> rectangleSection(int x, int y, int width, int height) 524 { 525 SpatialMap<I, E> next = new SpatialMap<>(positionMapping.size()); 526 Coord tmp; 527 for(SpatialTriple<I, E> ie : positionMapping.values()) 528 { 529 tmp = ie.position; 530 if(tmp.x >= x && tmp.y >= y && tmp.x + width > x && tmp.y + height > y) 531 next.put(ie); 532 } 533 return next; 534 } 535 536 /** 537 * Given the center position, Radius to determine measurement, and maximum distance from the center, creates a new 538 * SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the 539 * given distance from the center as measured by measurement. Will not include any elements from this SpatialMap 540 * with positions beyond the bounds of the given area, and will include all elements from this that are in the area. 541 * @param x the center x-coordinate of the area 542 * @param y the center y-coordinate of the area 543 * @param measurement a Radius enum, such as Radius.CIRCLE or Radius.DIAMOND, that calculates distance 544 * @param distance the maximum distance from the center to include in the area 545 * @return a new SpatialMap that refers to a subsection of this one 546 */ 547 public SpatialMap<I, E> radiusSection(int x, int y, Radius measurement, int distance) 548 { 549 SpatialMap<I, E> next = new SpatialMap<>(positionMapping.size()); 550 Coord tmp; 551 for(SpatialTriple<I, E> ie : positionMapping.values()) 552 { 553 tmp = ie.position; 554 if(measurement.inRange(x, y, tmp.x, tmp.y, 0, distance)) 555 next.put(ie); 556 } 557 return next; 558 } 559 560 /** 561 * Given the center position and maximum distance from the center, creates a new SpatialMap from this one that 562 * refers only to the subsection of this SpatialMap shared with the area within the given distance from the center, 563 * measured with Euclidean distance to produce a circle shape. Will not include any elements from this SpatialMap 564 * with positions beyond the bounds of the given area, and will include all elements from this that are in the area. 565 * @param x the center x-coordinate of the area 566 * @param y the center y-coordinate of the area 567 * @param radius the maximum distance from the center to include in the area, using Euclidean distance 568 * @return a new SpatialMap that refers to a subsection of this one 569 */ 570 public SpatialMap<I, E> circleSection(int x, int y, int radius) 571 { 572 return radiusSection(x, y, Radius.CIRCLE, radius); 573 } 574 575 public void clear() 576 { 577 itemMapping.clear(); 578 positionMapping.clear(); 579 } 580 public boolean isEmpty() 581 { 582 return itemMapping.isEmpty(); 583 } 584 public int size() 585 { 586 return itemMapping.size(); 587 } 588 public Object[] toArray() 589 { 590 Object[] contents = itemMapping.values().toArray(); 591 for (int i = 0; i < contents.length; i++) { 592 contents[i] = ((SpatialTriple<?,?>)contents[i]).element; 593 } 594 return contents; 595 } 596 597 /** 598 * Replaces the contents of the given array with the elements this holds, in insertion order, until either this 599 * data structure or the array has been exhausted. 600 * @param a the array to replace; should usually have the same length as this data structure's size. 601 * @return an array of elements that should be the same as the changed array originally passed as a parameter. 602 */ 603 public E[] toArray(E[] a) 604 { 605 Collection<SpatialTriple<I,E>> contents = itemMapping.values(); 606 int i = 0; 607 for (SpatialTriple<I,E> triple : contents) { 608 if(i < a.length) 609 a[i] = triple.element; 610 else 611 break; 612 i++; 613 } 614 return a; 615 } 616 617 /** 618 * Iterates through values in insertion order. 619 * @return an Iterator of generic type E 620 */ 621 @Override 622 public Iterator<E> iterator() 623 { 624 final Iterator<SpatialTriple<I, E>> it = itemMapping.values().iterator(); 625 return new Iterator<E>() { 626 @Override 627 public boolean hasNext() { 628 return it.hasNext(); 629 } 630 631 @Override 632 public E next() { 633 SpatialTriple<I,E> triple = it.next(); 634 if(triple != null) 635 return triple.element; 636 return null; 637 } 638 639 @Override 640 public void remove() { 641 throw new UnsupportedOperationException(); 642 } 643 }; 644 } 645 646 /** 647 * Iterates through values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion 648 * order. The type is SpatialTriple, defined in a nested class. 649 * @return an Iterator of SpatialTriple of I, E 650 */ 651 public Iterator<SpatialTriple<I, E>> tripleIterator() 652 { 653 return itemMapping.values().iterator(); 654 } 655 /** 656 * Iterates through positions in insertion order; has less predictable iteration order than the other iterators. 657 * @return an Iterator of Coord 658 */ 659 public Iterator<Coord> positionIterator() 660 { 661 return positionMapping.keySet().iterator(); 662 } 663 /** 664 * Iterates through identity keys in insertion order. 665 * @return an Iterator of generic type I 666 */ 667 public Iterator<I> identityIterator() 668 { 669 return itemMapping.keySet().iterator(); 670 } 671 672 /** 673 * Iterates through positions in a rectangular region (starting at a minimum of x, y and extending to the specified 674 * width and height) in left-to-right, then top-to-bottom order (the same as reading a page of text). 675 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 676 * @return an Iterator of Coord 677 */ 678 public Iterator<Coord> rectanglePositionIterator(int x, int y, int width, int height) 679 { 680 return new RectangularIterator(x, y, width, height); 681 } 682 683 /** 684 * Iterates through positions in a region defined by a Radius (starting at a minimum of x - distance, y - distance 685 * and extending to x + distance, y + distance but skipping any positions where the Radius considers a position 686 * further from x, y than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). 687 * You can use Radius.SQUARE to make a square region (which could also be made with rectanglePositionIterator()), 688 * Radius.DIAMOND to make a, well, diamond-shaped region, or Radius.CIRCLE to make a circle (which could also be 689 * made with circlePositionIterator). 690 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 691 * @return an Iterator of Coord 692 */ 693 public Iterator<Coord> radiusPositionIterator(int x, int y, Radius measurement, int distance) 694 { 695 return new RadiusIterator(x, y, measurement, distance); 696 } 697 /** 698 * Iterates through positions in a circular region (starting at a minimum of x - distance, y - distance and 699 * extending to x + distance, y + distance but skipping any positions where the Euclidean distance from x,y to the 700 * position is more than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). 701 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 702 * @return an Iterator of Coord 703 */ 704 public Iterator<Coord> circlePositionIterator(int x, int y, int distance) 705 { 706 return new RadiusIterator(x, y, Radius.CIRCLE, distance); 707 } 708 709 private class RectangularIterator implements Iterator<Coord> 710 { 711 int x, y, width, height, idx, 712 poolWidth = Coord.getCacheWidth(), poolHeight = Coord.getCacheHeight(); 713 Set<Coord> positions; 714 Coord temp; 715 RectangularIterator(int x, int y, int width, int height) 716 { 717 this.x = x; 718 this.y = y; 719 this.width = width; 720 this.height = height; 721 idx = -1; 722 positions = positionMapping.keySet(); 723 } 724 725 @Override 726 public boolean hasNext() { 727 if (idx < width * height - 1) { 728 Coord t2; 729 int n = idx; 730 do { 731 n = findNext(n); 732 if (idx < 0) 733 return n >= 0; 734 else { 735 if(x + n % width >= 0 && x + n % width < poolWidth 736 && y + n / width >= 0 && y + n / width < poolHeight) 737 t2 = Coord.get(x + n % width, y + n / width); 738 else t2 = Coord.get(-1, -1); 739 } 740 } while (!positions.contains(t2)); 741 /* Not done && has next */ 742 return n >= 0; 743 } 744 return false; 745 } 746 747 748 @Override 749 public Coord next() { 750 do { 751 idx = findNext(idx); 752 if (idx < 0) 753 throw new NoSuchElementException(); 754 if(x + idx % width >= 0 && x + idx % width < poolWidth 755 && y + idx / width >= 0 && y + idx / width < poolHeight) 756 temp = Coord.get(x + idx % width, y + idx / width); 757 else temp = Coord.get(-1, -1); 758 } while (!positions.contains(temp)); 759 return temp; 760 } 761 762 @Override 763 public void remove() { 764 throw new UnsupportedOperationException(); 765 } 766 767 private int findNext(final int idx) { 768 if (idx < 0) { 769 /* First iteration */ 770 return 0; 771 } else { 772 if (idx >= width * height - 1) 773 { 774 /* Done iterating */ 775 return -1; 776 } else { 777 return idx + 1; 778 } 779 } 780 } 781 } 782 783 private class RadiusIterator implements Iterator<Coord> 784 { 785 int x, y, width, height, distance, idx, 786 poolWidth = Coord.getCacheWidth(), poolHeight = Coord.getCacheHeight(); 787 Set<Coord> positions; 788 Coord temp; 789 Radius measurement; 790 RadiusIterator(int x, int y, Radius measurement, int distance) 791 { 792 this.x = x; 793 this.y = y; 794 width = 1 + distance * 2; 795 height = 1 + distance * 2; 796 this.distance = distance; 797 this.measurement = measurement; 798 idx = -1; 799 positions = positionMapping.keySet(); 800 } 801 802 @Override 803 public boolean hasNext() { 804 if (idx < width * height - 1) { 805 Coord t2; 806 int n = idx; 807 do { 808 n = findNext(n); 809 if (idx < 0) 810 return n >= 0; 811 else { 812 if(x - distance + n % width >= 0 && x - distance + n % width < poolWidth 813 && y - distance + n / width >= 0 && y - distance + n / width < poolHeight && 814 measurement.radius(x, y, 815 x - distance + n % width, y - distance + n / width) <= distance) 816 t2 = Coord.get(x - distance + n % width, y - distance + n / width); 817 else t2 = Coord.get(-1, -1); 818 } 819 } while (!positions.contains(t2)); 820 /* Not done && has next */ 821 return n >= 0; 822 } 823 return false; 824 } 825 826 827 @Override 828 public Coord next() { 829 do { 830 idx = findNext(idx); 831 if (idx < 0) 832 throw new NoSuchElementException(); 833 if(x - distance + idx % width >= 0 && x - distance + idx % width < poolWidth 834 && y - distance + idx / width >= 0 && y - distance + idx / width < poolHeight && 835 measurement.radius(x, y, 836 x - distance + idx % width, y - distance + idx / width) <= distance) 837 temp = Coord.get(x - distance + idx % width, y - distance + idx / width); 838 else temp = Coord.get(-1, -1); 839 } while (!positions.contains(temp)); 840 return temp; 841 } 842 843 @Override 844 public void remove() { 845 throw new UnsupportedOperationException(); 846 } 847 848 private int findNext(final int idx) { 849 if (idx < 0) { 850 /* First iteration */ 851 return 0; 852 } else { 853 if (idx >= width * height - 1) 854 { 855 /* Done iterating */ 856 return -1; 857 } else { 858 return idx + 1; 859 } 860 } 861 } 862 } 863 864 @Override 865 public boolean equals(Object o) { 866 if (this == o) return true; 867 if (o == null || getClass() != o.getClass()) return false; 868 869 SpatialMap<?, ?> that = (SpatialMap<?, ?>) o; 870 871 if (itemMapping != null ? !itemMapping.equals(that.itemMapping) : that.itemMapping != null) return false; 872 return positionMapping != null ? positionMapping.equals(that.positionMapping) : that.positionMapping == null; 873 874 } 875 876 @Override 877 public int hashCode() { 878 int result = itemMapping != null ? itemMapping.hashCode() : 0; 879 result = 31 * result + (positionMapping != null ? positionMapping.hashCode() : 0); 880 return result; 881 } 882 883 @Override 884 public String toString() { 885 return "SpatialMap{" + 886 "itemMapping=" + itemMapping + 887 ", positionMapping=" + positionMapping + 888 '}'; 889 } 890 891}