Package ej.basictool.map

Class AbstractPackedMap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this map.
    V - the type of mapped values.
    Direct Known Subclasses:
    AbstractWeakPackedMap, IdentityPackedMap, PackedMap
    public abstract class AbstractPackedMap<K,​V>
extends Object
    An object that maps keys to values. A packed map cannot contain duplicate keys; each key can map to at most one value.

    The main goal of this implementation, compared to a standard Map, is to have a small heap footprint. For instance, it doesn't provide direct access to (key,value) entries. This allows to simplify the implementation.

    It uses a single array containing both keys and values that is fitted to the content (enlarged when an entry is added, shrunk when an entry is removed). The array contains first all the keys then all the values. The keys are sorted by their hashcode value. A key is retrieved first using a dichotomic search on its hashcode, then using a linear search within keys having the same hashcode.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected Object[] keysValues
      Keys and values of the map.

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Removes all of the mappings from this map.
      abstract Object clone()
      Returns a shallow copy of this map instance: the keys and values themselves are not cloned.
      boolean containsKey​(Object key)
      Returns true if this map contains a mapping for the specified key.
      protected boolean containsUnwrappedKey​(Object key)
      Returns true if this map contains a mapping for the specified key.
      boolean containsValue​(Object value)
      Returns true if this map maps one or more keys to the specified value.
      boolean equals​(Object o)
      Compares the specified object with this map for equality.
      V get​(Object key)
      Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
      protected int getKeyHashCode​(Object key)
      Gets the hash code of a key.
      protected int getWrappedKeyHashCode​(Object wrappedKey)
      Gets the hash code of a key stored in the packed map.
      int hashCode()
      Returns the hash code value for this map.
      boolean isEmpty()
      Returns true if this map contains no key-value mappings.
      protected abstract boolean isSame​(Object key, Object candidateKey)
      Checks whether two keys are equal or not.
      Set<K> keySet()
      Returns an unmodifiable Set view of the keys contained in this map.
      V put​(K key, V value)
      Associates the specified value with the specified key in this map.
      V remove​(Object key)
      Removes the mapping for a key from this map if it is present.
      int size()
      Returns the number of key-value mappings in this map.
      protected K unwrapKey​(Object wrappedKey)
      Unwraps a wrapped key.
      Collection<V> values()
      Returns an unmodifiable Collection view of the values contained in this map.
      protected Object wrapKey​(K key)
      Wraps a key.

    • Field Detail

      • keysValues

        protected Object[] keysValues
        Keys and values of the map.

    • Constructor Detail

      • AbstractPackedMap

        public AbstractPackedMap()
        Constructs an empty map.

      • AbstractPackedMap

        public AbstractPackedMap​(AbstractPackedMap<K,​V> map)
        Constructs a map with the same mappings as the specified map.
        Parameters:
        map - the map whose mappings are to be placed in this map.
        Throws:
        NullPointerException - if the specified map is null.

    • Method Detail

      • clear

        public void clear()
        Removes all of the mappings from this map. The map will be empty after this call returns.
        Throws:
        UnsupportedOperationException - if the clear operation is not supported by this map

      • clone

        public abstract Object clone()
        Returns a shallow copy of this map instance: the keys and values themselves are not cloned.
        Overrides:
        clone in class Object
        Returns:
        a shallow copy of this map
        See Also:
        Cloneable

      • containsKey

        public boolean containsKey​(Object key)
        Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a mapping for a key same than the given key (see isSame(Object, Object)). (There can be at most one such mapping.)
        Parameters:
        key - key whose presence in this map is to be tested.
        Returns:
        true if this map contains a mapping for the specified key.
        Throws:
        NullPointerException - if the specified key is null.

      • containsValue

        public boolean containsValue​(@Nullable
                             Object value)
        Returns true if this map maps one or more keys to the specified value. More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ? v==null : value.equals(v)). This operation requires time linear in the map size.
        Parameters:
        value - value whose presence in this map is to be tested.
        Returns:
        true if this map maps one or more keys to the specified value.

      • equals

        public boolean equals​(@Nullable
                      Object o)
        Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings.
        Overrides:
        equals in class Object
        Parameters:
        o - object to be compared for equality with this map
        Returns:
        true if the specified object is equal to this map
        See Also:
        Object.hashCode(), HashMap

      • get

        @Nullable
public V get​(Object key)
        Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

        More formally, if this map contains a mapping from a key k to a value v such that key is the same as k (see isSame(Object, Object)), then this method returns v otherwise it returns null. (There can be at most one such mapping.)

        A return value of null does not necessarily indicate that the map contains no mapping for the key: it is also possible that the map explicitly maps the key to null. The containsKey(key) operation may be used to distinguish these two cases.

        Parameters:
        key - the key whose associated value is to be returned.
        Returns:
        the value to which the specified key is mapped, or null if this map contains no mapping for the key.
        Throws:
        NullPointerException - if the specified key is null.

      • hashCode

        public int hashCode()
        Returns the hash code value for this map. The hash code of a map is defined to be the sum of the hash codes of each entry (key-value mapping) in the map. This ensures that m1.equals(m2) implies that m1.hashCode()==m2.hashCode() for any two maps m1 and m2, as required by the general contract of Object.hashCode().
        Overrides:
        hashCode in class Object
        Returns:
        the hash code value for this map.
        See Also:
        Object.equals(Object), equals(Object)

      • isEmpty

        public boolean isEmpty()
        Returns true if this map contains no key-value mappings.
        Returns:
        true if this map contains no key-value mappings

      • keySet

        public Set<K> keySet()
        Returns an unmodifiable Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined. The set cannot be modified and attempts to modify the returned collection, whether direct or via its iterator, result in an UnsupportedOperationException.
        Returns:
        a set view of the keys contained in this map.

      • put

        @Nullable
public V put​(K key,
             V value)
        Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)
        Parameters:
        key - key with which the specified value is to be associated.
        value - value to be associated with the specified key.
        Returns:
        the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)
        Throws:
        NullPointerException - if the specified key is null.

      • getKeyHashCode

        protected int getKeyHashCode​(Object key)
        Gets the hash code of a key.

        By default, returns the hash code of the given object.

        Parameters:
        key - the key.
        Returns:
        the hash code.

      • getWrappedKeyHashCode

        protected int getWrappedKeyHashCode​(Object wrappedKey)
        Gets the hash code of a key stored in the packed map. The given object may not be the actual key because it has been wrapped by wrapKey(Object).

        By default, the given parameter is unwrapped using unwrapKey(Object) then the hash code is computed using getKeyHashCode(Object).

        Parameters:
        wrappedKey - the wrapped key.
        Returns:
        the hash code.

      • wrapKey

        protected Object wrapKey​(K key)
        Wraps a key. The result of this method will be stored in the packed map.

        By default, the key is returned.

        Parameters:
        key - the key to wrap.
        Returns:
        the wrapped key.

      • unwrapKey

        @Nullable
protected K unwrapKey​(Object wrappedKey)
        Unwraps a wrapped key. The given wrapper is an object stored in the packed map (see wrapKey(Object)). The result is the key contained by this wrapper.

        By default, the given object is returned (casted in the right type).

        Beware that the returned key may be null, for instance if the key is wrapped in a weak reference. In this case, to avoid throwing NullPointerException, the subclass must at least check the null parameters in isSame(Object, Object), containsKey(Object) and getKeyHashCode(Object).

        Parameters:
        wrappedKey - the object to unwrap.
        Returns:
        the key.

      • remove

        @Nullable
public V remove​(Object key)
        Removes the mapping for a key from this map if it is present. More formally, if this map contains a mapping for a key that is the same as the given key (see isSame(Object, Object)), that mapping is removed. (The map can contain at most one such mapping.)

        Returns the value to which this map previously associated the key, or null if the map contained no mapping for the key.

        A return value of null does not necessarily indicate that the map contained no mapping for the key it's also possible that the map explicitly mapped the key to null.

        The map will not contain a mapping for the specified key once the call returns.

        Parameters:
        key - key whose mapping is to be removed from the map.
        Returns:
        the previous value associated with key, or null if there was no mapping for key.
        Throws:
        NullPointerException - if the specified key is null.

      • size

        public int size()
        Returns the number of key-value mappings in this map. If the map contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
        Returns:
        the number of key-value mappings in this map

      • values

        public Collection<V> values()
        Returns an unmodifiable Collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection. If the map is modified while an iteration over the collection is in progress, the results of the iteration are undefined. The collection cannot be modified and attempts to modify the returned collection, whether direct or via its iterator, result in an UnsupportedOperationException.
        Returns:
        a collection view of the values contained in this map

      • isSame

        protected abstract boolean isSame​(Object key,
                                  @Nullable
                                  Object candidateKey)
        Checks whether two keys are equal or not. The key must not be null.
        Parameters:
        key - the key searched in the map.
        candidateKey - the key in the map to compare with. Can be null if and only if unwrapKey(Object) implementation can return null.
        Returns:
        true if the two keys are equal, false otherwise.

      • containsUnwrappedKey

        protected boolean containsUnwrappedKey​(@Nullable
                                       Object key)
        Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a mapping for a key same than the given key (see isSame(Object, Object)). (There can be at most one such mapping.)
        Parameters:
        key - key whose presence in this map is to be tested. Can be null if and only if unwrapKey(Object) implementation can return null.
        Returns:
        true if this map contains a mapping for the specified key.
        Throws:
        NullPointerException - if the specified key is null.