Package cpsc331.collections

Class BSTDictionary<K extends java.lang.Comparable<K>,​V>

  • All Implemented Interfaces:
    Dictionary<K,​V>, Mapping<K,​V>
    public class BSTDictionary<K extends java.lang.Comparable<K>,​V>
extends java.lang.Object
implements Dictionary<K,​V>
    Provides an implementation of a Dictionary using a binary search tree.

    • Constructor Summary

      Constructors 
      Constructor Description
      BSTDictionary()
      Constructs an empty BSTDictionary

      Preconditions: None
      Postcondition: An empty BSTDictionary (satisfying the above BSTDictionary Invariant) has been created.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void change​(K k, V v, cpsc331.collections.BSTDictionary.BSTNode x)  
      V get​(K key)
      Returns the value associated with a given key, throwing a NoSuchElementException if no value is currently associated with the given key.
      void remove​(K k)
      Removes the ordered pair with a given input key k, returning a NoSuchElementException and leaving the Mapping unchanged if no such ordered pair exists.
      void set​(K k, V v)
      Sets the value associated with an input key to be an input value — replacing the value formerly associated with this key if one already exists.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • BSTDictionary

        public BSTDictionary()
        Constructs an empty BSTDictionary

        Preconditions: None
        Postcondition: An empty BSTDictionary (satisfying the above BSTDictionary Invariant) has been created.

    • Method Detail

      • get

        public V get​(K key)
      throws java.lang.NullPointerException,
             java.util.NoSuchElementException
        Description copied from interface: Mapping
        Returns the value associated with a given key, throwing a NoSuchElementException if no value is currently associated with the given key.

        Specified by:
        get in interface Mapping<K extends java.lang.Comparable<K>,​V>
        Parameters:
        key - the key whose value is to be returned
        Returns:
        the value of this key
        Throws:
        java.lang.NullPointerException - if the input key is null
        java.util.NoSuchElementException - if the key is not null, but no value is defined for this key

        Precondition:
        1. The Mapping Invariant is satisfied.
        2. A value k with type K has been provided as input.
        Postcondition:
        1. The Mapping Invariant is satisfied.
        2. This Mapping has not been changed.
        3. If k is null then a NullPointerException is thrown.
        4. Otherwise (that is, if k is not null), if this Mapping includes some ordered pair whose first entry is the input key k, then the value v that is the second entry of this ordered pair (that is, the value associated with k) is returned as output. A NoSuchElementException is thrown otherwise.

      • set

        public void set​(K k,
                V v)
         throws java.lang.NullPointerException
        Description copied from interface: Mapping
        Sets the value associated with an input key to be an input value — replacing the value formerly associated with this key if one already exists.

        Specified by:
        set in interface Mapping<K extends java.lang.Comparable<K>,​V>
        Parameters:
        k - the key for which a value is to be defined
        v - the value that is to be defined to this key
        Throws:
        java.lang.NullPointerException - if k is null

        Precondition:
        1. The Mapping Invariant is satisfied.
        2. A value k with type K and v with type V are provided as input.
        Postcondition:
        1. The Mapping Invariant is satisfied.
        2. If k is null then a NullPointerException is thrown.
        3. Otherwise (that is, if k is not null), if this Mapping included an ordered pair whose first entry is the input value k, then this is replaced by the ordered pair (k, v). Otherwise a new ordered pair (k, v) is added. No other changes to this Mapping are made.

      • change

        public void change​(K k,
                   V v,
                   cpsc331.collections.BSTDictionary.BSTNode x)

      • remove

        public void remove​(K k)
            throws java.lang.NullPointerException,
                   java.util.NoSuchElementException
        Description copied from interface: Mapping
        Removes the ordered pair with a given input key k, returning a NoSuchElementException and leaving the Mapping unchanged if no such ordered pair exists.

        Specified by:
        remove in interface Mapping<K extends java.lang.Comparable<K>,​V>
        Parameters:
        k - the key for which a value is to be undefined
        Throws:
        java.lang.NullPointerException - if k is null
        java.util.NoSuchElementException - if no value was defined for this key

        Precondition:
        1. The Dictionary Invariant is satisfied.
        2. A value k with type K is provided as input.
        Postcondition:
        1. The Mapping Invariant is satisfied.
        2. If k is null then a NullPointerException is thrown.
        3. Otherwise (that is, if k is not null) if this Mapping includes an ordered pair (k, v) whose first entry is the input key k then this ordered pair is removed; no other changes are made. Otherwise a NoSuchElementException is thrown and this Mapping is not changed at all.