cpsc331.collections

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

java.lang.Object

cpsc331.collections.BSTDictionary<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 and Description
BSTDictionary() Constructs an empty BSTDictionary Preconditions: None Postcondition: An empty BSTDictionary (satisfying the above BSTDictionary Invariant) has been created.

Method Summary

Modifier and Type	Method and 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.
V	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

Methods inherited from interface cpsc331.collections.Mapping

defined

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.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.util.NoSuchElementException - if 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 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)

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

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 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 V remove(K k)
         throws 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

Returns:

the former value of this key

Throws:

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 this Mapping includes an ordered pair (k, v) whose first entry is the input key k then this ordered pair is removed and the second entry v (that is, the value associated with this key) is returned as output; no other changes are made. Otherwise a NoSuchElementException is thrown and this Mapping is not changed at all.