Package squidpony.squidgrid

Class SpatialMap<I,​E>

java.lang.Object
squidpony.squidgrid.SpatialMap<I,​E>
All Implemented Interfaces:
Iterable<E>
public class SpatialMap<I,​E>
extends Object
implements Iterable<E>
A data structure that seems to be re-implemented often for games, this associates Coord positions and generic I identities with generic E elements. You can get an element from a SpatialMap with either an identity or a position, change the position of an element without changing its value or identity, modify an element given its identity and a new value, and perform analogues to most of the features of the Map interface, though this does not implement Map because it essentially has two key types and one value type. You can also iterate through the values in insertion order, where insertion order should be stable even when elements are moved or modified (the relevant key is the identity, which is never changed in this class). Uses two OrderedMap fields internally. Created by Tommy Ettinger on 1/2/2016.

  • Nested Class Summary

    Nested Classes 
    Modifier and Type Class Description
    static class  SpatialMap.SpatialTriple<I,​E>  

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected OrderedMap<I,​SpatialMap.SpatialTriple<I,​E>> itemMapping  
    protected OrderedMap<Coord,​SpatialMap.SpatialTriple<I,​E>> positionMapping  

  • Constructor Summary

    Constructors 
    Constructor Description
    SpatialMap()
    Constructs a SpatialMap with capacity 32.
    SpatialMap​(int capacity)
    Constructs a SpatialMap with the given capacity
    SpatialMap​(Collection<Coord> coords, Collection<I> ids, Collection<E> elements)
    Constructs a SpatialMap given collections of Coord, identity, and element; all 3 collections should have the same length, since this will use only up to the minimum length of these collections for how many it adds.
    SpatialMap​(Coord[] coords, I[] ids, E[] elements)
    Constructs a SpatialMap given arrays of Coord, identity, and element; all 3 arrays should have the same length, since this will use only up to the minimum length of these arrays for how many it adds.

  • Method Summary

    Modifier and Type Method Description
    void add​(Coord coord, I id, E element)
    Adds a new element with the given identity and Coord position.
    Iterator<Coord> circlePositionIterator​(int x, int y, int distance)
    Iterates through positions in a circular region (starting at a minimum of x - distance, y - distance and extending to x + distance, y + distance but skipping any positions where the Euclidean distance from x,y to the position is more than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text).
    SpatialMap<I,​E> circleSection​(int x, int y, int radius)
    Given the center position and maximum distance from the center, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the given distance from the center, measured with Euclidean distance to produce a circle shape.
    void clear()  
    boolean containsKey​(Object o)
    Checks whether this contains the given identity key.
    boolean containsPosition​(Object o)
    Checks whether this contains anything at the given position.
    boolean containsValue​(Object o)
    Checks whether this contains the given element.
    boolean equals​(Object o)  
    E get​(I i)
    Gets the element with the given identity.
    E get​(Coord c)
    Gets the element at the given Coord position.
    I getIdentity​(Coord c)
    Gets the identity of the element at the given Coord position.
    ArrayList<E> getManyIdentities​(I[] identities)
    Given an array of I, gets all elements in this SpatialMap that share an identity with one of the I objects in identities and returns them as an ArrayList of elements.
    ArrayList<E> getManyIdentities​(Iterable<I> identities)
    Given an Iterable (such as a List, Set, or other Collection) of I, gets all elements in this SpatialMap that share an identity with one of the I objects in identities and returns them as an ArrayList of elements.
    ArrayList<E> getManyPositions​(Iterable<Coord> positions)
    Given an Iterable (such as a List, Set, or other Collection) of Coord, gets all elements in this SpatialMap that share a position with one of the Coord objects in positions and returns them as an ArrayList of elements.
    ArrayList<E> getManyPositions​(Coord[] positions)
    Given an array of Coord, gets all elements in this SpatialMap that share a position with one of the Coord objects in positions and returns them as an ArrayList of elements.
    Coord getPosition​(I i)
    Gets the position of the element with the given identity.
    int hashCode()  
    OrderedSet<I> identities()
    Get a Set of all identities used for values in this data structure, returning a OrderedSet (defensively copying the key set used internally) for its stable iteration order.
    Iterator<I> identityIterator()
    Iterates through identity keys in insertion order.
    boolean isEmpty()  
    Iterator<E> iterator()
    Iterates through values in insertion order.
    E modify​(I id, E newValue)
    Changes the element's value associated with id.
    E move​(I id, Coord target)
    Move an element, picked by its identity, to a new Coord position.
    E move​(Coord previous, Coord target)
    Move an element from one position to another; moves whatever is at the Coord position previous to the new Coord position target.
    E positionalModify​(Coord pos, E newValue)
    Changes the element's value associated with pos.
    Iterator<Coord> positionIterator()
    Iterates through positions in insertion order; has less predictable iteration order than the other iterators.
    OrderedSet<Coord> positions()
    Get a Set of all positions used for values in this data structure, returning a OrderedSet (defensively copying the key set used internally) for its stable iteration order.
    void put​(SpatialMap.SpatialTriple<I,​E> triple)
    Inserts a SpatialTriple into this SpatialMap without changing it, potentially overwriting an existing element.
    void put​(Coord coord, I id, E element)
    Inserts a new element with the given identity and Coord position, potentially overwriting an existing element.
    Iterator<Coord> radiusPositionIterator​(int x, int y, Radius measurement, int distance)
    Iterates through positions in a region defined by a Radius (starting at a minimum of x - distance, y - distance and extending to x + distance, y + distance but skipping any positions where the Radius considers a position further from x, y than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text).
    SpatialMap<I,​E> radiusSection​(int x, int y, Radius measurement, int distance)
    Given the center position, Radius to determine measurement, and maximum distance from the center, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the given distance from the center as measured by measurement.
    E randomElement​(IRNG rng)  
    SpatialMap.SpatialTriple<I,​E> randomEntry​(IRNG rng)  
    I randomIdentity​(IRNG rng)  
    Coord randomPosition​(IRNG rng)  
    Iterator<Coord> rectanglePositionIterator​(int x, int y, int width, int height)
    Iterates through positions in a rectangular region (starting at a minimum of x, y and extending to the specified width and height) in left-to-right, then top-to-bottom order (the same as reading a page of text).
    SpatialMap<I,​E> rectangleSection​(int x, int y, int width, int height)
    Given the size and position of a rectangular area, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the rectangular area.
    E remove​(I id)
    Removes the element with the given identity from all storage in this data structure.
    E remove​(Coord coord)
    Removes the element at the given position from all storage in this data structure.
    int size()  
    Object[] toArray()  
    E[] toArray​(E[] a)
    Replaces the contents of the given array with the elements this holds, in insertion order, until either this data structure or the array has been exhausted.
    String toString()  
    Iterator<SpatialMap.SpatialTriple<I,​E>> tripleIterator()
    Iterates through values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion order.
    Collection<SpatialMap.SpatialTriple<I,​E>> triples()
    Gets all data stored in this as a collection of values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion order.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Field Details

  • Constructor Details

    • SpatialMap

      public SpatialMap()
      Constructs a SpatialMap with capacity 32.

    • SpatialMap

      public SpatialMap​(int capacity)
      Constructs a SpatialMap with the given capacity
      Parameters:
      capacity - the capacity for each of the internal OrderedMaps

    • SpatialMap

      public SpatialMap​(Coord[] coords, I[] ids, E[] elements)
      Constructs a SpatialMap given arrays of Coord, identity, and element; all 3 arrays should have the same length, since this will use only up to the minimum length of these arrays for how many it adds. Each unique id will be added with the corresponding element at the corresponding Coord position if that position is not already filled.
      Parameters:
      coords - a starting array of Coord positions; indices here correspond to the other parameters
      ids - a starting array of identities; indices here correspond to the other parameters
      elements - a starting array of elements; indices here correspond to the other parameters

    • SpatialMap

      public SpatialMap​(Collection<Coord> coords, Collection<I> ids, Collection<E> elements)
      Constructs a SpatialMap given collections of Coord, identity, and element; all 3 collections should have the same length, since this will use only up to the minimum length of these collections for how many it adds. Each unique id will be added with the corresponding element at the corresponding Coord position if that position is not already filled.
      Parameters:
      coords - a starting collection of Coord positions; indices here correspond to the other parameters
      ids - a starting collection of identities; indices here correspond to the other parameters
      elements - a starting collection of elements; indices here correspond to the other parameters

  • Method Details

    • add

      public void add​(Coord coord, I id, E element)
      Adds a new element with the given identity and Coord position. If the position is already occupied by an element in this data structure, does nothing. If the identity is already used, this also does nothing. If the identity and position are both unused, this adds element to the data structure.
      You should strongly avoid calling remove() and add() to change an element; prefer modify() and move().
      Parameters:
      coord - the Coord position to place the element at; should be empty
      id - the identity to associate the element with; should be unused
      element - the element to add

    • put

      public void put​(Coord coord, I id, E element)
      Inserts a new element with the given identity and Coord position, potentially overwriting an existing element.
      If you want to alter an existing element, use modify() or move().
      Parameters:
      coord - the Coord position to place the element at; should be empty
      id - the identity to associate the element with; should be unused
      element - the element to add

    • put

      public void put​(SpatialMap.SpatialTriple<I,​E> triple)
      Inserts a SpatialTriple into this SpatialMap without changing it, potentially overwriting an existing element. SpatialTriple objects can be obtained by the triples() or tripleIterator() methods, and can also be constructed on their own.
      If you want to alter an existing element, use modify() or move().
      Parameters:
      triple - a SpatialTriple (an inner class of SpatialMap) with the same type parameters as this class

    • modify

      public E modify​(I id, E newValue)
      Changes the element's value associated with id. The key id should exist before calling this; if there is no matching id, this returns null.
      Parameters:
      id - the identity of the element to modify
      newValue - the element value to replace the previous element with.
      Returns:
      the previous element value associated with id

    • positionalModify

      public E positionalModify​(Coord pos, E newValue)
      Changes the element's value associated with pos. The key pos should exist before calling this; if there is no matching position, this returns null.
      Parameters:
      pos - the position of the element to modify
      newValue - the element value to replace the previous element with.
      Returns:
      the previous element value associated with id

    • move

      public E move​(Coord previous, Coord target)
      Move an element from one position to another; moves whatever is at the Coord position previous to the new Coord position target. The element will not be present at its original position if target is unoccupied, but nothing will change if target is occupied.
      Parameters:
      previous - the starting Coord position of an element to move
      target - the Coord position to move the element to
      Returns:
      the moved element if movement was successful or null otherwise

    • move

      public E move​(I id, Coord target)
      Move an element, picked by its identity, to a new Coord position. Finds the element using only the id, and does not need the previous position. The target position must be empty for this to move successfully, and the id must exist in this data structure for this to move anything.
      Parameters:
      id - the identity of the element to move
      target - the Coord position to move the element to
      Returns:
      the moved element if movement was successful or null otherwise

    • remove

      public E remove​(Coord coord)
      Removes the element at the given position from all storage in this data structure.
      You should strongly avoid calling remove() and add() to change an element; prefer modify() and move().
      Parameters:
      coord - the position of the element to remove
      Returns:
      the value of the element that was removed or null if nothing was present at the position

    • remove

      public E remove​(I id)
      Removes the element with the given identity from all storage in this data structure.
      You should strongly avoid calling remove() and add() to change an element; prefer modify() and move().
      Parameters:
      id - the identity of the element to remove
      Returns:
      the value of the element that was removed or null if nothing was present at the position

    • containsValue

      public boolean containsValue​(Object o)
      Checks whether this contains the given element. Slower than containsKey and containsPosition (linear time).
      Parameters:
      o - an Object that should be an element if you expect this to possibly return true
      Returns:
      true if o is contained as an element in this data structure

    • containsKey

      public boolean containsKey​(Object o)
      Checks whether this contains the given identity key.
      Parameters:
      o - an Object that should be of the generic I type if you expect this to possibly return true
      Returns:
      true if o is an identity key that can be used with this data structure

    • containsPosition

      public boolean containsPosition​(Object o)
      Checks whether this contains anything at the given position.
      Parameters:
      o - an Object that should be a Coord if you expect this to possibly return true
      Returns:
      true if o is a Coord that is associated with some element in this data structure

    • get

      public E get​(Coord c)
      Gets the element at the given Coord position.
      Parameters:
      c - the position to get an element from
      Returns:
      the element if it exists or null otherwise

    • get

      public E get​(I i)
      Gets the element with the given identity.
      Parameters:
      i - the identity of the element to get
      Returns:
      the element if it exists or null otherwise

    • getPosition

      public Coord getPosition​(I i)
      Gets the position of the element with the given identity.
      Parameters:
      i - the identity of the element to get a position from
      Returns:
      the position of the element if it exists or null otherwise

    • getIdentity

      public I getIdentity​(Coord c)
      Gets the identity of the element at the given Coord position.
      Parameters:
      c - the position to get an identity from
      Returns:
      the identity of the element if it exists at the given position or null otherwise

    • positions

      public OrderedSet<Coord> positions()
      Get a Set of all positions used for values in this data structure, returning a OrderedSet (defensively copying the key set used internally) for its stable iteration order.
      Returns:
      a OrderedSet of Coord corresponding to the positions present in this data structure.

    • identities

      public OrderedSet<I> identities()
      Get a Set of all identities used for values in this data structure, returning a OrderedSet (defensively copying the key set used internally) for its stable iteration order.
      Returns:
      a OrderedSet of I corresponding to the identities present in this data structure.

    • triples

      public Collection<SpatialMap.SpatialTriple<I,​E>> triples()
      Gets all data stored in this as a collection of values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion order. The type is SpatialTriple, defined in a nested class.
      Returns:
      a Collection of SpatialTriple of I, E

    • getManyPositions

      public ArrayList<E> getManyPositions​(Iterable<Coord> positions)
      Given an Iterable (such as a List, Set, or other Collection) of Coord, gets all elements in this SpatialMap that share a position with one of the Coord objects in positions and returns them as an ArrayList of elements.
      Parameters:
      positions - an Iterable (such as a List or Set) of Coord
      Returns:
      an ArrayList, possibly empty, of elements that share a position with a Coord in positions

    • getManyIdentities

      public ArrayList<E> getManyIdentities​(Iterable<I> identities)
      Given an Iterable (such as a List, Set, or other Collection) of I, gets all elements in this SpatialMap that share an identity with one of the I objects in identities and returns them as an ArrayList of elements.
      Parameters:
      identities - an Iterable (such as a List or Set) of I
      Returns:
      an ArrayList, possibly empty, of elements that share an Identity with an I in identities

    • getManyPositions

      public ArrayList<E> getManyPositions​(Coord[] positions)
      Given an array of Coord, gets all elements in this SpatialMap that share a position with one of the Coord objects in positions and returns them as an ArrayList of elements.
      Parameters:
      positions - an array of Coord
      Returns:
      an ArrayList, possibly empty, of elements that share a position with a Coord in positions

    • getManyIdentities

      public ArrayList<E> getManyIdentities​(I[] identities)
      Given an array of I, gets all elements in this SpatialMap that share an identity with one of the I objects in identities and returns them as an ArrayList of elements.
      Parameters:
      identities - an array of I
      Returns:
      an ArrayList, possibly empty, of elements that share an Identity with an I in identities

    • randomElement

      public E randomElement​(IRNG rng)

    • randomPosition

      public Coord randomPosition​(IRNG rng)

    • randomIdentity

      public I randomIdentity​(IRNG rng)

    • randomEntry

      public SpatialMap.SpatialTriple<I,​E> randomEntry​(IRNG rng)

    • rectangleSection

      public SpatialMap<I,​E> rectangleSection​(int x, int y, int width, int height)
      Given the size and position of a rectangular area, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the rectangular area. Will not include any elements from this SpatialMap with positions beyond the bounds of the given rectangular area, and will include all elements from this that are in the area.
      Parameters:
      x - the minimum x-coordinate of the rectangular area
      y - the minimum y-coordinate of the rectangular area
      width - the total width of the rectangular area
      height - the total height of the rectangular area
      Returns:
      a new SpatialMap that refers to a subsection of this one

    • radiusSection

      public SpatialMap<I,​E> radiusSection​(int x, int y, Radius measurement, int distance)
      Given the center position, Radius to determine measurement, and maximum distance from the center, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the given distance from the center as measured by measurement. Will not include any elements from this SpatialMap with positions beyond the bounds of the given area, and will include all elements from this that are in the area.
      Parameters:
      x - the center x-coordinate of the area
      y - the center y-coordinate of the area
      measurement - a Radius enum, such as Radius.CIRCLE or Radius.DIAMOND, that calculates distance
      distance - the maximum distance from the center to include in the area
      Returns:
      a new SpatialMap that refers to a subsection of this one

    • circleSection

      public SpatialMap<I,​E> circleSection​(int x, int y, int radius)
      Given the center position and maximum distance from the center, creates a new SpatialMap from this one that refers only to the subsection of this SpatialMap shared with the area within the given distance from the center, measured with Euclidean distance to produce a circle shape. Will not include any elements from this SpatialMap with positions beyond the bounds of the given area, and will include all elements from this that are in the area.
      Parameters:
      x - the center x-coordinate of the area
      y - the center y-coordinate of the area
      radius - the maximum distance from the center to include in the area, using Euclidean distance
      Returns:
      a new SpatialMap that refers to a subsection of this one

    • clear

      public void clear()

    • isEmpty

      public boolean isEmpty()

    • size

      public int size()

    • toArray

      public Object[] toArray()

    • toArray

      public E[] toArray​(E[] a)
      Replaces the contents of the given array with the elements this holds, in insertion order, until either this data structure or the array has been exhausted.
      Parameters:
      a - the array to replace; should usually have the same length as this data structure's size.
      Returns:
      an array of elements that should be the same as the changed array originally passed as a parameter.

    • iterator

      public Iterator<E> iterator()
      Iterates through values in insertion order.
      Specified by:
      iterator in interface Iterable<I>
      Returns:
      an Iterator of generic type E

    • tripleIterator

      public Iterator<SpatialMap.SpatialTriple<I,​E>> tripleIterator()
      Iterates through values similar to Map.Entry, but containing a Coord, I, and E value for each entry, in insertion order. The type is SpatialTriple, defined in a nested class.
      Returns:
      an Iterator of SpatialTriple of I, E

    • positionIterator

      public Iterator<Coord> positionIterator()
      Iterates through positions in insertion order; has less predictable iteration order than the other iterators.
      Returns:
      an Iterator of Coord

    • identityIterator

      public Iterator<I> identityIterator()
      Iterates through identity keys in insertion order.
      Returns:
      an Iterator of generic type I

    • rectanglePositionIterator

      public Iterator<Coord> rectanglePositionIterator​(int x, int y, int width, int height)
      Iterates through positions in a rectangular region (starting at a minimum of x, y and extending to the specified width and height) in left-to-right, then top-to-bottom order (the same as reading a page of text). Any Coords this returns should be viable arguments to get() if you want a corresponding element.
      Returns:
      an Iterator of Coord

    • radiusPositionIterator

      public Iterator<Coord> radiusPositionIterator​(int x, int y, Radius measurement, int distance)
      Iterates through positions in a region defined by a Radius (starting at a minimum of x - distance, y - distance and extending to x + distance, y + distance but skipping any positions where the Radius considers a position further from x, y than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). You can use Radius.SQUARE to make a square region (which could also be made with rectanglePositionIterator()), Radius.DIAMOND to make a, well, diamond-shaped region, or Radius.CIRCLE to make a circle (which could also be made with circlePositionIterator). Any Coords this returns should be viable arguments to get() if you want a corresponding element.
      Returns:
      an Iterator of Coord

    • circlePositionIterator

      public Iterator<Coord> circlePositionIterator​(int x, int y, int distance)
      Iterates through positions in a circular region (starting at a minimum of x - distance, y - distance and extending to x + distance, y + distance but skipping any positions where the Euclidean distance from x,y to the position is more than distance) in left-to-right, then top-to-bottom order (the same as reading a page of text). Any Coords this returns should be viable arguments to get() if you want a corresponding element.
      Returns:
      an Iterator of Coord

    • equals

      public boolean equals​(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object