Class Map3<K,V>

java.lang.Object
components.map.MapSecondary<K,V>
components.map.Map3<K,V>
Type Parameters:
K - type of Map domain (key) entries
V - type of Map range (associated value) entries
All Implemented Interfaces:
Map<K,V>, MapKernel<K,V>, Standard<Map<K,V>>, Iterable<Map.Pair<K,V>>
public class Map3<K,V> extends MapSecondary<K,V>
Map represented as a BinaryTree (maintained as a binary search tree) of pairs with implementations of primary methods.
Mathematical Definitions:
IS_TOTAL_PREORDER (
 r: binary relation on K
) : boolean is
for all x, y, z: K
 ((r(x, y) or r(y, x))  and
  (if (r(x, y) and r(y, z)) then r(x, z)))

IS_BST(
 tree: binary tree of (K, V),
 r: binary relation on K
): boolean satisfies
[tree satisfies the binary search tree ordering property according to the
 relation r on the keys of its (K, V) labels and has no duplicate key
 values among its (K, V) labels]
Representation Invariant (concrete invariant of $this):
IS_TOTAL_PREORDER([relation computed by $this.order.compare method]  and
IS_BST($this.pairsTree, $this.order)
Abstraction Relation (interpretation mapping between $this and this):
this = labels($this.pairsTree)

  • Constructor Details

    • Map3

      public Map3()
      No-argument constructor: uses Comparable's compareTo order if available; otherwise, compares hashCodes.

    • Map3

      public Map3(Comparator<K> order)
      Constructor using given Comparator's compare order.
      Parameters:
      order - the order for the BST

  • Method Details

    • newInstance

      public final Map<K,V> newInstance()
      Description copied from interface: Standard
      Returns a new object with the same dynamic type as this, having an initial value. If the type T has a no-argument constructor, then the value of the new returned object satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then the value of the new returned object satisfies the contract of the constructor call that was used to initialize this .
      Returns:
      new object "like" this with an initial value

    • clear

      public final void clear()
      Description copied from interface: Standard
      Resets this to an initial value. If the type T has a no-argument constructor, then this satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then this satisfies the contract of the constructor call that was used to initialize #this.

    • transferFrom

      public final void transferFrom(Map<K,V> source)
      Description copied from interface: Standard
      Sets this to the incoming value of source, and resets source to an initial value; the declaration notwithstanding, the dynamic type of source must be the same as the dynamic type of this. If the type T has a no-argument constructor, then source satisfies the contract of the no-argument constructor for T. If T does not have a no-argument constructor, then source satisfies the contract of the constructor call that was used to initialize #source.
      Parameters:
      source - object whose value is to be transferred

    • add

      public final void add(K key, V value)
      Description copied from interface: MapKernel
      Adds the pair (key, value) to this.
      Parameters:
      key - the key to be added
      value - the associated value to be added

    • remove

      public final Map.Pair<K,V> remove(K key)
      Description copied from interface: MapKernel
      Removes the pair whose first component is key and returns it.
      Parameters:
      key - the key to be removed
      Returns:
      the pair removed

    • removeAny

      public final Map.Pair<K,V> removeAny()
      Description copied from interface: MapKernel
      Removes and returns an arbitrary pair from this.
      Returns:
      the pair removed from this

    • value

      public final V value(K key)
      Description copied from interface: MapKernel
      Reports the value associated with key in this.
      Parameters:
      key - the key whose associated value is to be reported
      Returns:
      the value associated with key

    • hasKey

      public final boolean hasKey(K key)
      Description copied from interface: MapKernel
      Reports whether there is a pair in this whose first component is key.
      Parameters:
      key - the key to be checked
      Returns:
      true iff there is a pair in this whose first component is key

    • size

      public final int size()
      Description copied from interface: MapKernel
      Reports size of this.
      Returns:
      the number of pairs in this

    • iterator

      public final Iterator<Map.Pair<K,V>> iterator()