Package it.unimi.di.prog2.h22

Class Map<K extends Comparable<K>,V>

java.lang.Object
it.unimi.di.prog2.h22.Map<K,V>
Type Parameters:
K - the type of keys maintained by this map.
V - the type of mapped values.
public class Map<K extends Comparable<K>,V> extends Object
A map from Map to Map.

A map is a collection that associates keys (comparabili) to values; the map cannot contain duplicate keys, which means that each key can be associated to at most one value.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final List<K>
    keys
    A list containing the keys
    private final List<V>
    values
    A list containing the values

  • Constructor Summary

    Constructors
    Constructor
    Description
    Map()
    Creates a new empty map.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear()
    Removes all of the mappings from this map.
    boolean
    containsKey(K key)
    Returns if this map contains the specified key.
    boolean
    containsValue(int value)
    Returns if this map contains the specified value.
    private static <T extends Comparable<T>>
    int
    dichotomicSearch(List<T> haystack, T needle)
    Finds the index (or insertion point) of a string in a list of strings kept in increasing lexicographyc order.
    V
    get(K key)
    Returns the value to which the specified key is mapped.
    boolean
    isEmpty()
    Returns if this map is empty.
    void
    put(K key, V value)
    Associates in this map the new key with the specified value.
    boolean
    remove(K key)
    Removes the mapping for a key from this map if it is present.
    int
    size()
    Returns the size of this map.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • keys

      private final List<K extends Comparable<K>> keys
      A list containing the keys

    • values

      private final List<V> values
      A list containing the values

  • Constructor Details

    • Map

      public Map()
      Creates a new empty map.

  • Method Details

    • size

      public int size()
      Returns the size of this map.
      Returns:
      the number of key-value mappings in this map.

    • isEmpty

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

    • dichotomicSearch

      private static <T extends Comparable<T>> int dichotomicSearch(List<T> haystack, T needle)
      Finds the index (or insertion point) of a string in a list of strings kept in increasing lexicographyc order.

      If the list contains the given string, returns its index. Otherwise, returns -(insertion_point) - 1 where insertion_point is the index of the first string greater than needle; note that this implies that the return value is non-negative iff the list contains the string.

      Type Parameters:
      T - the type of the elements in the haystack.
      Parameters:
      haystack - the not null list of not null strings in increasing degree order.
      needle - the string to look for, must not be null.
      Returns:
      the index of the given string, or -insertion_point - 1 if none is present.
      See Also:

    • containsKey

      public boolean containsKey(K key)
      Returns if this map contains the specified key.
      Parameters:
      key - the key to search for.
      Returns:
      true iff this map contains a key-value mappings with the given key.

    • containsValue

      public boolean containsValue(int value)
      Returns if this map contains the specified value.
      Parameters:
      value - the value to search for.
      Returns:
      true iff this map contains a key-value mappings with the given value.

    • get

      public V get(K key) throws NoSuchElementException
      Returns the value to which the specified key is mapped.
      Parameters:
      key - the key whose associated value is to be returned.
      Returns:
      the value to which the specified key is mapped.
      Throws:
      NoSuchElementException - if this map contains no mapping for the key, or the key is null.

    • put

      public void put(K key, V value)
      Associates in this map the new key with the specified value.
      Parameters:
      key - the key with which the specified value is to be associated.
      value - the value to be associated with the specified key.
      Throws:
      IllegalArgumentException - if the map already contain a mapping for the key.
      NullPointerException - if the key is null.

    • remove

      public boolean remove(K key)
      Removes the mapping for a key from this map if it is present.
      Parameters:
      key - the key whose mapping is to be removed from the map.
      Returns:
      true iff this map contained a mapping for the specified key, and hence is modified by this operation.

    • clear

      public void clear()
      Removes all of the mappings from this map.

    • toString

      public String toString()
      Overrides:
      toString in class Object