Package com.zybooks.dsaj.map

Class SortedTableMap<K,V>

java.lang.Object
com.zybooks.dsaj.map.AbstractMap<K,V>
com.zybooks.dsaj.map.AbstractSortedMap<K,V>
com.zybooks.dsaj.map.SortedTableMap<K,V>
Type Parameters:
K - The key type (keys must be unique and comparable)
V - The value type
All Implemented Interfaces:
Map<K,V>, SortedMap<K,V>
public class SortedTableMap<K,V> extends AbstractSortedMap<K,V>
An implementation of a map using a sorted table. All accessors run in O(log n) worst-case time, other than subMap, which runs in O(s + log n) where s is the size of the resulting submap, and the complete iterations that run in O(n) time.

  • Nested Class Summary

    Nested classes/interfaces inherited from class com.zybooks.dsaj.map.AbstractMap

    AbstractMap.MapEntry<K,V>

  • Constructor Summary

    Constructors
    Constructor
    Description
    SortedTableMap()
    Constructs an empty map using the natural ordering of keys.
    SortedTableMap(Comparator<K> comp)
    Constructs an empty map using the given comparator to order keys.

  • Method Summary

    Modifier and Type
    Method
    Description
    Entry<K,V>
    ceilingEntry(K key)
    Returns the entry with least key greater than or equal to given key (or null if no such key exists).
    Iterable<Entry<K,V>>
    entrySet()
    Returns an iterable collection of all key-value entries of the map.
    Entry<K,V>
    firstEntry()
    Returns the entry having the least key (or null if map is empty).
    Entry<K,V>
    floorEntry(K key)
    Returns the entry with greatest key less than or equal to given key (or null if no such key exists).
    V
    get(K key)
    Returns the value associated with the specified key, or null if no such entry exists.
    Entry<K,V>
    higherEntry(K key)
    Returns the entry with least key strictly greater than given key (or null if no such key exists).
    Entry<K,V>
    lastEntry()
    Returns the entry having the greatest key (or null if map is empty).
    Entry<K,V>
    lowerEntry(K key)
    Returns the entry with greatest key strictly less than given key (or null if no such key exists).
    V
    put(K key, V value)
    Associates the given value with the given key.
    V
    remove(K key)
    Removes the entry with the specified key, if present, and returns its associated value.
    int
    size()
    Returns the number of entries in the map.
    Iterable<Entry<K,V>>
    subMap(K fromKey, K toKey)
    Returns an iterable containing all keys in the range from fromKey inclusive to toKey exclusive.

    Methods inherited from class com.zybooks.dsaj.map.AbstractSortedMap

    compare, compare, compare, compare

    Methods inherited from class com.zybooks.dsaj.map.AbstractMap

    isEmpty, keySet, values

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface com.zybooks.dsaj.map.Map

    isEmpty, keySet, values

  • Constructor Details

    • SortedTableMap

      public SortedTableMap()
      Constructs an empty map using the natural ordering of keys.

    • SortedTableMap

      public SortedTableMap(Comparator<K> comp)
      Constructs an empty map using the given comparator to order keys.
      Parameters:
      comp - comparator defining the order of keys in the map

  • Method Details

    • size

      public int size()
      Returns the number of entries in the map.
      Returns:
      number of entries in the map

    • get

      public V get(K key)
      Returns the value associated with the specified key, or null if no such entry exists.
      Parameters:
      key - the key whose associated value is to be returned
      Returns:
      the associated value, or null if no such entry exists

    • put

      public V put(K key, V value)
      Associates the given value with the given key. If an entry with the key was already in the map, this replaced the previous value with the new one and returns the old value. Otherwise, a new entry is added and null is returned.
      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 the key (or null, if no such entry)

    • remove

      public V remove(K key)
      Removes the entry with the specified key, if present, and returns its associated value. Otherwise does nothing and returns null.
      Parameters:
      key - the key whose entry is to be removed from the map
      Returns:
      the previous value associated with the removed key, or null if no such entry exists

    • firstEntry

      public Entry<K,V> firstEntry()
      Returns the entry having the least key (or null if map is empty).
      Returns:
      entry with least key (or null if map is empty)

    • lastEntry

      public Entry<K,V> lastEntry()
      Returns the entry having the greatest key (or null if map is empty).
      Returns:
      entry with greatest key (or null if map is empty)

    • ceilingEntry

      public Entry<K,V> ceilingEntry(K key)
      Returns the entry with least key greater than or equal to given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with least key greater than or equal to given (or null if no such entry)

    • floorEntry

      public Entry<K,V> floorEntry(K key)
      Returns the entry with greatest key less than or equal to given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with greatest key less than or equal to given (or null if no such entry)

    • lowerEntry

      public Entry<K,V> lowerEntry(K key)
      Returns the entry with greatest key strictly less than given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with greatest key strictly less than given (or null if no such entry)

    • higherEntry

      public Entry<K,V> higherEntry(K key)
      Returns the entry with least key strictly greater than given key (or null if no such key exists).
      Parameters:
      key - the target key
      Returns:
      entry with least key strictly greater than given (or null if no such entry)

    • entrySet

      public Iterable<Entry<K,V>> entrySet()
      Returns an iterable collection of all key-value entries of the map.
      Returns:
      iterable collection of the map's entries

    • subMap

      public Iterable<Entry<K,V>> subMap(K fromKey, K toKey)
      Returns an iterable containing all keys in the range from fromKey inclusive to toKey exclusive.
      Parameters:
      fromKey - the low end of the submap
      toKey - the high end of the submap
      Returns:
      iterable with keys in desired range