Package net.mtrop.doom.struct.vector

Class AbstractMappedVector<T,K>

java.lang.Object
net.mtrop.doom.struct.vector.AbstractArrayStorage<T>
net.mtrop.doom.struct.vector.AbstractVector<T>
net.mtrop.doom.struct.vector.AbstractMappedVector<T,K>
Type Parameters:
T - the type of Object that this vector contains.
K - the mapped key type that this vector uses to map one object to an index. The key is assumed to be unique.
All Implemented Interfaces:
Iterable<T>, Sizable
public abstract class AbstractMappedVector<T,K> extends AbstractVector<T>
A special type of vector that also as a one-to-one mapping of an object to an index. Changes to the indices of the stored objects trigger re-mappings of the objects that shift positions.

Map lookups are by hash, so they are O(c), c = longest chain in map. O(c) < O(n);

Author:
Matthew Tropiano

  • Field Details

    • indexMap

      protected Map<K,Integer> indexMap
      The key map.

  • Constructor Details

    • AbstractMappedVector

      public AbstractMappedVector()
      Makes a new mapped vector.

    • AbstractMappedVector

      public AbstractMappedVector(int capacity)
      Makes a new mapped vector that doubles every resize.
      Parameters:
      capacity - the initial capacity of this vector. If 0 or less, it is 1.

    • AbstractMappedVector

      public AbstractMappedVector(int capacity, int capacityIncrement)
      Makes a new mapped vector.
      Parameters:
      capacity - the initial capacity of this vector.
      capacityIncrement - what to increase the capacity of this vector by if this reaches the max. if 0 or less, it will double.

    • AbstractMappedVector

      protected AbstractMappedVector(int capacity, int capacityIncrement, boolean constructMap)
      Makes a new mapped vector.
      Parameters:
      capacity - the initial capacity of this vector.
      capacityIncrement - what to increase the capacity of this vector by if this reaches the max. if 0 or less, it will double.
      constructMap - if true, this all create the underlying map. Extenders of this class that want to change the nature of the hash map should call this with false, so that the map isn't created twice.

  • Method Details

    • getMappingKey

      protected abstract K getMappingKey(T object)
      Returns the mapping value to use for mapping an object.
      Parameters:
      object - the object to get a mapping key from.
      Returns:
      a key to use to associate with this object.

    • getIndexUsingKey

      public int getIndexUsingKey(K key)
      Retrieves an object in this mapping using a key.
      Parameters:
      key - the key to use.
      Returns:
      the corresponding index, or -1 if not found.

    • containsKey

      public boolean containsKey(K key)
      Retrieves an object in this mapping using a key.
      Parameters:
      key - the key to use.
      Returns:
      the corresponding index, or -1 if not found.

    • getUsingKey

      public T getUsingKey(K key)
      Retrieves an object in this mapping that corresponds to a particular key.
      Parameters:
      key - the key to use.
      Returns:
      the corresponding object, or null if not found.

    • removeUsingKey

      public T removeUsingKey(K key)
      Removes an object in this mapping that corresponds to a particular key.
      Parameters:
      key - the key to use.
      Returns:
      the removed object, or null if not found.

    • add

      public void add(int index, T object)
      Description copied from class: AbstractVector
      Adds an object at an index. If index is greater than or equal to the size, it will add it at the end. If index is less than 0, it won't add it.
      Overrides:
      add in class AbstractVector<T>
      Parameters:
      index - the index to add this at.
      object - the object to add.

    • removeIndex

      public T removeIndex(int index)
      Description copied from class: AbstractVector
      Removes an object from an index in the vector and shifts everything after it down an index position.
      Overrides:
      removeIndex in class AbstractVector<T>
      Parameters:
      index - the target index.
      Returns:
      null if the index is out of bounds or the object at that index.

    • sort

      public void sort()
      Description copied from class: AbstractVector
      Sorts this vector using NATURAL ORDERING. Calls Arrays.sort(Object[], int, int) on the internal storage array.
      Overrides:
      sort in class AbstractVector<T>

    • sort

      public void sort(Comparator<? super T> comp)
      Description copied from class: AbstractVector
      Sorts this vector using a comparator. Calls Arrays.sort(Object[], int, int, Comparator) on the internal storage array, using the specified comparator.
      Overrides:
      sort in class AbstractVector<T>
      Parameters:
      comp - the comparator to use.

    • sort

      public void sort(int startIndex, int endIndex)
      Description copied from class: AbstractVector
      Sorts this vector using NATURAL ORDERING. Calls Arrays.sort(Object[], int, int) on the internal storage array.
      Overrides:
      sort in class AbstractVector<T>
      Parameters:
      startIndex - the starting index of the sort.
      endIndex - the ending index of the sort, exclusive.

    • sort

      public void sort(Comparator<? super T> comp, int startIndex, int endIndex)
      Description copied from class: AbstractVector
      Sorts this vector using a comparator. Calls Arrays.sort(Object[], int, int, Comparator) on the internal storage array, using the specified comparator.
      Overrides:
      sort in class AbstractVector<T>
      Parameters:
      comp - the comparator to use.
      startIndex - the starting index of the sort.
      endIndex - the ending index of the sort, exclusive.

    • swap

      public void swap(int index0, int index1)
      Description copied from class: AbstractVector
      Swaps the contents of two indices in the vector.

      If index0 is equal to index1, this does nothing.

      If one index is outside the bounds of this vector (less than 0 or greater than or equal to AbstractVector.size()), this throws an exception.

      Overrides:
      swap in class AbstractVector<T>
      Parameters:
      index0 - the first index.
      index1 - the second index.

    • shift

      public void shift(int sourceIndex, int targetIndex)
      Description copied from class: AbstractVector
      Moves the object at an index in this vector to another index, shifting the contents between the two selected indices in this vector back or forward.

      If sourceIndex is equal to targetIndex, this does nothing.

      If one index is outside the bounds of this vector (less than 0 or greater than or equal to AbstractVector.size()), this throws an exception.

      Overrides:
      shift in class AbstractVector<T>
      Parameters:
      sourceIndex - the first index.
      targetIndex - the second index.