Package util

Class IdMap

java.lang.Object
util.IdMap
All Implemented Interfaces:
Serializable, Cloneable, Comparator<Object>

public class IdMap extends Object implements Cloneable, Comparator<Object>, Serializable
Class to manage identifier maps.

With an identifier map a key can be mapped to an identifier (an integer value) and vice versa. In addition, an optional value may be associated with each key/identifier. When being added to the map, the keys are numbered consecutively, starting with 0. That is, the identifiers of the keys always range from 0 to size()-1.

Since:
2006.09.11
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected util.IdMapElem[]
    the array of hash bins
    protected static final int
    the block size for the inverse map array
    protected Comparator<Object>
    the comparator for sorting the map
    protected static final int
    a mask to ensure that the hash values are positive
    protected util.IdMapElem[]
    the inverse map (identifier to key)
    protected float
    the maximum load factor
    protected int
    the maximum number of elements
    protected int
    the mode for reacting to adding an existing key to the map
    static final int
    when adding an existing key: reject key (return negative id)
    static final int
    when adding an existing key: replace old associated value
    protected int
    the current number of elements
  • Constructor Summary

    Constructors
    Constructor
    Description
    Create an identifier map.
    IdMap(int mode)
    Create an identifier map.
    IdMap(int mode, int init)
    Create an identifier map.
    IdMap(int mode, int init, float load)
    Create an identifier map.
  • Method Summary

    Modifier and Type
    Method
    Description
    final int
    add(Object key)
    Add a key to an identifier map.
    final int
    add(Object key, Object value)
    Add a key/value pair to an identifier map.
    final void
    Clear the identifier map, that is, remove all keys/values.
    final Object
    Clone this identifier map.
    final int
    Compare two identifier map elements.
    final Object
    get(int id)
    Look up the key associated with an identifier.
    final int
    get(Object key)
    Look up the identifier associated with a key.
    final int
    Look up the identifier associated with a key.
    final Object
    getKey(int id)
    Look up the key associated with an identifier.
    final int[]
    Get identifier mapping from another identifier map.
    final int[]
    getMapTo(IdMap idmap)
    Get identifier mapping to another identifier map.
    final int
    Get the number of mappings in an identifier map.
    final Object
    getValue(int id)
    Look up the value associated with an identifier.
    final Object
    Look up the value associated with a key.
    final void
    move(int src, int dst)
    Move a key in the identifier map.
    protected final void
    Enlarge the hash bin array and rehash the map elements.
    final int[]
    remove(boolean[] rem)
    Remove several key/value pair from an identifier map.
    final void
    remove(int id)
    Remove a key/value pair from an identifier map.
    final int[]
    remove(int[] ids)
    Remove several key/value pair from an identifier map.
    final void
    Remove a key/value pair from an identifier map.
    protected final void
    remove(util.IdMapElem e)
    Remove an identifier map element.
    final void
    reorder(int[] map)
    Reorder an identifier map.
    final void
    replace(int id, Object key)
    Replace a key in an identifier map.
    final void
    setValue(int id, Object value)
    Set the value associated with an identifier.
    final void
    setValue(Object key, Object value)
    Set the value associated with a key.
    final int
    Get the number of mappings in an identifier map.
    final int[]
    Reorder an identifier map.

    Methods inherited from class java.lang.Object

    equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • REPLACE

      public static final int REPLACE
      when adding an existing key: replace old associated value
      See Also:
    • REJECT

      public static final int REJECT
      when adding an existing key: reject key (return negative id)
      See Also:
    • HASHMASK

      protected static final int HASHMASK
      a mask to ensure that the hash values are positive
      See Also:
    • BLKSIZE

      protected static final int BLKSIZE
      the block size for the inverse map array
      See Also:
    • mode

      protected int mode
      the mode for reacting to adding an existing key to the map
    • load

      protected float load
      the maximum load factor
    • max

      protected int max
      the maximum number of elements
    • size

      protected int size
      the current number of elements
    • bins

      protected util.IdMapElem[] bins
      the array of hash bins
    • imap

      protected util.IdMapElem[] imap
      the inverse map (identifier to key)
    • cmp

      protected transient Comparator<Object> cmp
      the comparator for sorting the map
  • Constructor Details

    • IdMap

      public IdMap(int mode, int init, float load)
      Create an identifier map.
      Parameters:
      mode - the mode for reacting to adding an existing key
      init - the initial size of the map (hash table size)
      load - the maximum load factor for the hash table
      Since:
      2006.09.11 (Christian Borgelt)
    • IdMap

      public IdMap(int mode, int init)
      Create an identifier map.
      Parameters:
      mode - the mode for reacting to adding an existing key
      init - the initial size of the map (hash table size)
      Since:
      2006.09.11 (Christian Borgelt)
    • IdMap

      public IdMap(int mode)
      Create an identifier map.
      Parameters:
      mode - the mode for reacting to adding an existing key
      Since:
      2006.09.11 (Christian Borgelt)
    • IdMap

      public IdMap()
      Create an identifier map.

      Equivalent to IdMap(REPLACE).

      Since:
      2007.04.13 (Christian Borgelt)
  • Method Details

    • clone

      public final Object clone()
      Clone this identifier map.

      The created clone is a deep copy, with the exception of the keys and values that are associated with identifiers.

      Overrides:
      clone in class Object
      Returns:
      a clone of this identifier map
      Since:
      2006.10.06 (Christian Borgelt)
    • clear

      public final void clear()
      Clear the identifier map, that is, remove all keys/values.
      Since:
      2007.01.31 (Christian Borgelt)
    • size

      public final int size()
      Get the number of mappings in an identifier map.
      Returns:
      the number of key/identifier pairs stored
      Since:
      2006.09.11 (Christian Borgelt)
    • getSize

      public final int getSize()
      Get the number of mappings in an identifier map.
      Returns:
      the number of key/identifier pairs stored
      Since:
      2017.06.17 (Christian Borgelt)
    • rehash

      protected final void rehash()
      Enlarge the hash bin array and rehash the map elements.
      Since:
      2006.09.11 (Christian Borgelt)
    • add

      public final int add(Object key)
      Add a key to an identifier map.

      If the key is already present, no new mapping is added, but the identifier already associated with the key is returned, thus automatically avoiding duplicate entries. In addition, a possibly associated value is deleted.

      Parameters:
      key - the key to add to the map
      Returns:
      the identifier assigned to the key
      Since:
      2006.09.11 (Christian Borgelt)
    • add

      public final int add(Object key, Object value)
      Add a key/value pair to an identifier map.

      If the key is already present, no new mapping is added, but the identifier already associated with the key is returned, thus automatically avoiding duplicate entries. In addition, the associated value is replaced.

      Parameters:
      key - the key to add to the map
      value - the value associated with the key
      Returns:
      the identifier assigned to the key
      Since:
      2007.01.31 (Christian Borgelt)
    • get

      public final int get(Object key)
      Look up the identifier associated with a key.
      Parameters:
      key - the key for which to find the associated identifier
      Returns:
      the identifier assigned to the key or -1 if the key is not contained in the map
      Since:
      2006.09.11 (Christian Borgelt)
    • getId

      public final int getId(Object key)
      Look up the identifier associated with a key.
      Parameters:
      key - the key for which to find the associated identifier
      Returns:
      the identifier assigned to the key or -1 if the key is not contained in the map
      Since:
      2017.06.14 (Christian Borgelt)
    • getValue

      public final Object getValue(Object key)
      Look up the value associated with a key.
      Parameters:
      key - the key for which to find the associated value
      Returns:
      the value associated with the identifier
      Since:
      2007.01.31 (Christian Borgelt)
    • get

      public final Object get(int id)
      Look up the key associated with an identifier.
      Parameters:
      id - identifier for which to find the associated key
      Returns:
      the key associated with the identifier
      Since:
      2006.09.11 (Christian Borgelt)
      See Also:
    • getKey

      public final Object getKey(int id)
      Look up the key associated with an identifier.
      Parameters:
      id - identifier for which to find the associated key
      Returns:
      the key associated with the identifier
      Since:
      2006.09.11 (Christian Borgelt)
      See Also:
    • getValue

      public final Object getValue(int id)
      Look up the value associated with an identifier.
      Parameters:
      id - the identifier for which to find the associated value
      Returns:
      the value associated with the identifier
      Since:
      2006.09.11 (Christian Borgelt)
    • setValue

      public final void setValue(Object key, Object value)
      Set the value associated with a key.
      Parameters:
      key - the key for which to find the associated value
      value - the value to associate with the key
      Since:
      2007.01.31 (Christian Borgelt)
    • setValue

      public final void setValue(int id, Object value)
      Set the value associated with an identifier.
      Parameters:
      id - the identifier for which to set the value
      value - the value to associate with the identifier
      Since:
      2007.01.31 (Christian Borgelt)
    • remove

      protected final void remove(util.IdMapElem e)
      Remove an identifier map element.
      Parameters:
      e - the identifier map element to remove
      Since:
      2007.07.15 (Christian Borgelt)
    • remove

      public final void remove(Object key)
      Remove a key/value pair from an identifier map.

      Note that by this operation the identifiers of keys with higher identifiers than the one to be removed will be reduced, in order to preserve consecutive identifiers.

      Parameters:
      key - the key to remove
      Since:
      2006.10.17 (Christian Borgelt)
    • remove

      public final void remove(int id)
      Remove a key/value pair from an identifier map.

      Note that by this operation the identifiers of keys with higher identifiers than the one to be removed will be reduced, in order to preserve consecutive identifiers.

      Parameters:
      id - the identifier of the key to remove
      Since:
      2006.10.17 (Christian Borgelt)
    • remove

      public final int[] remove(int[] ids)
      Remove several key/value pair from an identifier map.
      Parameters:
      ids - the array of identifiers of the keys to remove
      Returns:
      a map from the old (array indices) to the new key identifiers (content of array elements)
      Since:
      2017.06.14 (Christian Borgelt)
    • remove

      public final int[] remove(boolean[] rem)
      Remove several key/value pair from an identifier map.
      Parameters:
      rem - a flag array indicating the keys to remove (array index corresponds to identifier)
      Returns:
      a map from the old (array indices) to the new key identifiers (content of array elements)
      Since:
      2017.06.14 (Christian Borgelt)
    • replace

      public final void replace(int id, Object key)
      Replace a key in an identifier map.

      It is assumed that a key equal to the replacing key (w.r.t. the function equals()) is not associated with another identifier in this map, because otherwise the map gets into an inconsistent state. However, replacing a key with itself or an equal key is harmless and thus permitted.

      Parameters:
      id - the identifier of the key to replace
      key - the key to replace it with
      Since:
      2006.10.06 (Christian Borgelt)
    • move

      public final void move(int src, int dst)
      Move a key in the identifier map.
      Parameters:
      src - the current identifier of the key to move
      dst - the desired new identifier of the key
      Since:
      2007.01.31 (Christian Borgelt)
      See Also:
    • reorder

      public final void reorder(int[] map)
      Reorder an identifier map.

      Permute the identifiers, thus reordering the keys. The desired reordering has to be stated as a permutation of the integer numbers 0 to size()-1, with each entry stating the new value for the identifier that is the array index of the entry (forward map).

      If the reordering map is not such a permutation, the identifier map will get into an inconsistent state that may lead to serious errors.

      Parameters:
      map - an integer array containing a permutation of the integer numbers 0 to size()-1
      Since:
      2006.10.06 (Christian Borgelt)
      See Also:
    • compare

      public final int compare(Object o1, Object o2)
      Compare two identifier map elements.
      Specified by:
      compare in interface Comparator<Object>
      Parameters:
      o1 - first element to compare
      o2 - second element to compare
      Returns:
      a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second
      Since:
      2007.07.26 (Christian Borgelt)
    • sort

      public final int[] sort(Comparator<Object> cmp)
      Reorder an identifier map.
      Parameters:
      cmp - the comparator for the items
      Returns:
      a map from the old indices (array indices) to the new indices (contents of array elements)
      Since:
      2007.07.26 (Christian Borgelt)
    • getMapFrom

      public final int[] getMapFrom(IdMap idmap)
      Get identifier mapping from another identifier map.

      Identifiers that are present only in the identifier map given as an argument are added to this identifier map.

      Parameters:
      idmap - the other identifier map, from which to get the mapping
      Returns:
      an array that is indexed with identifiers referring to the identifier map given as an argument and contains identifiers referring to this identifier map /*------------------------------------------------------------------
    • getMapTo

      public final int[] getMapTo(IdMap idmap)
      Get identifier mapping to another identifier map.

      Identifiers that are present only in this identifier map are added to the identifier map given as an argument.

      Parameters:
      idmap - the other identifier map, to which to get the mapping
      Returns:
      an array that is indexed with identifiers referring to this identifier map and contains identifiers referring to the identifier map given as an argument /*------------------------------------------------------------------