001package squidpony.squidgrid; 002 003import squidpony.squidmath.Coord; 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 LinkedHashMap 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 LinkedHashMap<I, SpatialTriple<I, E>> itemMapping; 060 protected LinkedHashMap<Coord, SpatialTriple<I, E>> positionMapping; 061 062 /** 063 * Constructs a SpatialMap with capacity 32. 064 */ 065 public SpatialMap() 066 { 067 itemMapping = new LinkedHashMap<>(32); 068 positionMapping = new LinkedHashMap<>(32); 069 } 070 071 /** 072 * Constructs a SpatialMap with the given capacity 073 * @param capacity the capacity for each of the internal LinkedHashMaps 074 */ 075 public SpatialMap(int capacity) 076 { 077 itemMapping = new LinkedHashMap<>(capacity); 078 positionMapping = new LinkedHashMap<>(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 LinkedHashMap<>( 092 Math.min(coords.length, Math.min(ids.length, elements.length))); 093 positionMapping = new LinkedHashMap<>( 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 LinkedHashMap<>( 113 Math.min(coords.size(), Math.min(ids.size(), elements.size()))); 114 positionMapping = new LinkedHashMap<>( 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 LinkedHashSet (defensively copying 387 * the key set used internally) for its stable iteration order. 388 * @return a LinkedHashSet of Coord corresponding to the positions present in this data structure. 389 */ 390 public LinkedHashSet<Coord> positions() 391 { 392 return new LinkedHashSet<>(positionMapping.keySet()); 393 } 394 /** 395 * Get a Set of all identities used for values in this data structure, returning a LinkedHashSet (defensively 396 * copying the key set used internally) for its stable iteration order. 397 * @return a LinkedHashSet of I corresponding to the identities present in this data structure. 398 */ 399 public LinkedHashSet<I> identities() 400 { 401 return new LinkedHashSet<>(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 /** 486 * Given the size and position of a rectangular area, creates a new SpatialMap from this one that refers only to the 487 * subsection of this SpatialMap shared with the rectangular area. Will not include any elements from this 488 * SpatialMap with positions beyond the bounds of the given rectangular area, and will include all elements from 489 * this that are in the area. 490 * @param x the minimum x-coordinate of the rectangular area 491 * @param y the minimum y-coordinate of the rectangular area 492 * @param width the total width of the rectangular area 493 * @param height the total height of the rectangular area 494 * @return a new SpatialMap that refers to a subsection of this one 495 */ 496 public SpatialMap<I, E> rectangleSection(int x, int y, int width, int height) 497 { 498 SpatialMap<I, E> next = new SpatialMap<>(positionMapping.size()); 499 Coord tmp; 500 for(SpatialTriple<I, E> ie : positionMapping.values()) 501 { 502 tmp = ie.position; 503 if(tmp.x >= x && tmp.y >= y && tmp.x + width > x && tmp.y + height > y) 504 next.put(ie); 505 } 506 return next; 507 } 508 509 /** 510 * Given the center position, Radius to determine measurement, and maximum distance from the center, creates a new 511 * SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the 512 * given distance from the center as measured by measurement. Will not include any elements from this SpatialMap 513 * with positions beyond the bounds of the given area, and will include all elements from this that are in the area. 514 * @param x the center x-coordinate of the area 515 * @param y the center y-coordinate of the area 516 * @param measurement a Radius enum, such as Radius.CIRCLE or Radius.DIAMOND, that calculates distance 517 * @param distance the maximum distance from the center to include in the area 518 * @return a new SpatialMap that refers to a subsection of this one 519 */ 520 public SpatialMap<I, E> radiusSection(int x, int y, Radius measurement, int distance) 521 { 522 SpatialMap<I, E> next = new SpatialMap<>(positionMapping.size()); 523 Coord tmp; 524 for(SpatialTriple<I, E> ie : positionMapping.values()) 525 { 526 tmp = ie.position; 527 if(measurement.inRange(x, y, tmp.x, tmp.y, 0, distance)) 528 next.put(ie); 529 } 530 return next; 531 } 532 533 /** 534 * Given the center position and maximum distance from the center, creates a new SpatialMap from this one that 535 * refers only to the subsection of this SpatialMap shared with the area within the given distance from the center, 536 * measured with Euclidean distance to produce a circle shape. Will not include any elements from this SpatialMap 537 * with positions beyond the bounds of the given area, and will include all elements from this that are in the area. 538 * @param x the center x-coordinate of the area 539 * @param y the center y-coordinate of the area 540 * @param radius the maximum distance from the center to include in the area, using Euclidean distance 541 * @return a new SpatialMap that refers to a subsection of this one 542 */ 543 public SpatialMap<I, E> circleSection(int x, int y, int radius) 544 { 545 return radiusSection(x, y, Radius.CIRCLE, radius); 546 } 547 548 public void clear() 549 { 550 itemMapping.clear(); 551 positionMapping.clear(); 552 } 553 public boolean isEmpty() 554 { 555 return itemMapping.isEmpty(); 556 } 557 public int size() 558 { 559 return itemMapping.size(); 560 } 561 public Object[] toArray() 562 { 563 Object[] contents = itemMapping.values().toArray(); 564 for (int i = 0; i < contents.length; i++) { 565 contents[i] = ((SpatialTriple<?,?>)contents[i]).element; 566 } 567 return contents; 568 } 569 570 /** 571 * Replaces the contents of the given array with the elements this holds, in insertion order, until either this 572 * data structure or the array has been exhausted. 573 * @param a the array to replace; should usually have the same length as this data structure's size. 574 * @return an array of elements that should be the same as the changed array originally passed as a parameter. 575 */ 576 public E[] toArray(E[] a) 577 { 578 Collection<SpatialTriple<I,E>> contents = itemMapping.values(); 579 int i = 0; 580 for (SpatialTriple<I,E> triple : contents) { 581 if(i < a.length) 582 a[i] = triple.element; 583 else 584 break; 585 i++; 586 } 587 return a; 588 } 589 590 /** 591 * Iterates through values in insertion order. 592 * @return an Iterator of generic type E 593 */ 594 @Override 595 public Iterator<E> iterator() 596 { 597 final Iterator<SpatialTriple<I, E>> it = itemMapping.values().iterator(); 598 return new Iterator<E>() { 599 @Override 600 public boolean hasNext() { 601 return it.hasNext(); 602 } 603 604 @Override 605 public E next() { 606 SpatialTriple<I,E> triple = it.next(); 607 if(triple != null) 608 return triple.element; 609 return null; 610 } 611 612 @Override 613 public void remove() { 614 throw new UnsupportedOperationException(); 615 } 616 }; 617 } 618 619 /** 620 * Iterates through values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion 621 * order. The type is SpatialTriple, defined in a nested class. 622 * @return an Iterator of SpatialTriple of I, E 623 */ 624 public Iterator<SpatialTriple<I, E>> tripleIterator() 625 { 626 return itemMapping.values().iterator(); 627 } 628 /** 629 * Iterates through positions in insertion order; has less predictable iteration order than the other iterators. 630 * @return an Iterator of Coord 631 */ 632 public Iterator<Coord> positionIterator() 633 { 634 return positionMapping.keySet().iterator(); 635 } 636 /** 637 * Iterates through identity keys in insertion order. 638 * @return an Iterator of generic type I 639 */ 640 public Iterator<I> identityIterator() 641 { 642 return itemMapping.keySet().iterator(); 643 } 644 645 /** 646 * Iterates through positions in a rectangular region (starting at a minimum of x, y and extending to the specified 647 * width and height) in left-to-right, then top-to-bottom order (the same as reading a page of text). 648 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 649 * @return an Iterator of Coord 650 */ 651 public Iterator<Coord> rectanglePositionIterator(int x, int y, int width, int height) 652 { 653 return new RectangularIterator(x, y, width, height); 654 } 655 656 /** 657 * Iterates through positions in a region defined by a Radius (starting at a minimum of x - distance, y - distance 658 * and extending to x + distance, y + distance but skipping any positions where the Radius considers a position 659 * further from x, y than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). 660 * You can use Radius.SQUARE to make a square region (which could also be made with rectanglePositionIterator()), 661 * Radius.DIAMOND to make a, well, diamond-shaped region, or Radius.CIRCLE to make a circle (which could also be 662 * made with circlePositionIterator). 663 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 664 * @return an Iterator of Coord 665 */ 666 public Iterator<Coord> radiusPositionIterator(int x, int y, Radius measurement, int distance) 667 { 668 return new RadiusIterator(x, y, measurement, distance); 669 } 670 /** 671 * Iterates through positions in a circular region (starting at a minimum of x - distance, y - distance and 672 * extending to x + distance, y + distance but skipping any positions where the Euclidean distance from x,y to the 673 * position is more than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). 674 * Any Coords this returns should be viable arguments to get() if you want a corresponding element. 675 * @return an Iterator of Coord 676 */ 677 public Iterator<Coord> circlePositionIterator(int x, int y, int distance) 678 { 679 return new RadiusIterator(x, y, Radius.CIRCLE, distance); 680 } 681 682 private class RectangularIterator implements Iterator<Coord> 683 { 684 int x, y, width, height, idx, 685 poolWidth = Coord.getCacheWidth(), poolHeight = Coord.getCacheHeight(); 686 Set<Coord> positions; 687 Coord temp; 688 RectangularIterator(int x, int y, int width, int height) 689 { 690 this.x = x; 691 this.y = y; 692 this.width = width; 693 this.height = height; 694 idx = -1; 695 positions = positionMapping.keySet(); 696 } 697 698 @Override 699 public boolean hasNext() { 700 if (idx < width * height - 1) { 701 Coord t2; 702 int n = idx; 703 do { 704 n = findNext(n); 705 if (idx < 0) 706 return n >= 0; 707 else { 708 if(x + n % width >= 0 && x + n % width < poolWidth 709 && y + n / width >= 0 && y + n / width < poolHeight) 710 t2 = Coord.get(x + n % width, y + n / width); 711 else t2 = Coord.get(-1, -1); 712 } 713 } while (!positions.contains(t2)); 714 /* Not done && has next */ 715 return n >= 0; 716 } 717 return false; 718 } 719 720 721 @Override 722 public Coord next() { 723 do { 724 idx = findNext(idx); 725 if (idx < 0) 726 throw new NoSuchElementException(); 727 if(x + idx % width >= 0 && x + idx % width < poolWidth 728 && y + idx / width >= 0 && y + idx / width < poolHeight) 729 temp = Coord.get(x + idx % width, y + idx / width); 730 else temp = Coord.get(-1, -1); 731 } while (!positions.contains(temp)); 732 return temp; 733 } 734 735 @Override 736 public void remove() { 737 throw new UnsupportedOperationException(); 738 } 739 740 private int findNext(final int idx) { 741 if (idx < 0) { 742 /* First iteration */ 743 return 0; 744 } else { 745 if (idx >= width * height - 1) 746 { 747 /* Done iterating */ 748 return -1; 749 } else { 750 return idx + 1; 751 } 752 } 753 } 754 } 755 756 private class RadiusIterator implements Iterator<Coord> 757 { 758 int x, y, width, height, distance, idx, 759 poolWidth = Coord.getCacheWidth(), poolHeight = Coord.getCacheHeight(); 760 Set<Coord> positions; 761 Coord temp; 762 Radius measurement; 763 RadiusIterator(int x, int y, Radius measurement, int distance) 764 { 765 this.x = x; 766 this.y = y; 767 width = 1 + distance * 2; 768 height = 1 + distance * 2; 769 this.distance = distance; 770 this.measurement = measurement; 771 idx = -1; 772 positions = positionMapping.keySet(); 773 } 774 775 @Override 776 public boolean hasNext() { 777 if (idx < width * height - 1) { 778 Coord t2; 779 int n = idx; 780 do { 781 n = findNext(n); 782 if (idx < 0) 783 return n >= 0; 784 else { 785 if(x - distance + n % width >= 0 && x - distance + n % width < poolWidth 786 && y - distance + n / width >= 0 && y - distance + n / width < poolHeight && 787 measurement.radius(x, y, 788 x - distance + n % width, y - distance + n / width) <= distance) 789 t2 = Coord.get(x - distance + n % width, y - distance + n / width); 790 else t2 = Coord.get(-1, -1); 791 } 792 } while (!positions.contains(t2)); 793 /* Not done && has next */ 794 return n >= 0; 795 } 796 return false; 797 } 798 799 800 @Override 801 public Coord next() { 802 do { 803 idx = findNext(idx); 804 if (idx < 0) 805 throw new NoSuchElementException(); 806 if(x - distance + idx % width >= 0 && x - distance + idx % width < poolWidth 807 && y - distance + idx / width >= 0 && y - distance + idx / width < poolHeight && 808 measurement.radius(x, y, 809 x - distance + idx % width, y - distance + idx / width) <= distance) 810 temp = Coord.get(x - distance + idx % width, y - distance + idx / width); 811 else temp = Coord.get(-1, -1); 812 } while (!positions.contains(temp)); 813 return temp; 814 } 815 816 @Override 817 public void remove() { 818 throw new UnsupportedOperationException(); 819 } 820 821 private int findNext(final int idx) { 822 if (idx < 0) { 823 /* First iteration */ 824 return 0; 825 } else { 826 if (idx >= width * height - 1) 827 { 828 /* Done iterating */ 829 return -1; 830 } else { 831 return idx + 1; 832 } 833 } 834 } 835 } 836 837 @Override 838 public boolean equals(Object o) { 839 if (this == o) return true; 840 if (o == null || getClass() != o.getClass()) return false; 841 842 SpatialMap<?, ?> that = (SpatialMap<?, ?>) o; 843 844 if (itemMapping != null ? !itemMapping.equals(that.itemMapping) : that.itemMapping != null) return false; 845 return positionMapping != null ? positionMapping.equals(that.positionMapping) : that.positionMapping == null; 846 847 } 848 849 @Override 850 public int hashCode() { 851 int result = itemMapping != null ? itemMapping.hashCode() : 0; 852 result = 31 * result + (positionMapping != null ? positionMapping.hashCode() : 0); 853 return result; 854 } 855 856 @Override 857 public String toString() { 858 return "SpatialMap{" + 859 "itemMapping=" + itemMapping + 860 ", positionMapping=" + positionMapping + 861 '}'; 862 } 863 864}