searchTree

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

java.lang.Object

searchTree.EmptyTree<K,V>

All Implemented Interfaces:

Tree<K,V>

public class EmptyTree<K extends java.lang.Comparable<K>,V>
extends java.lang.Object
implements Tree<K,V>

This class is used to represent the empty search tree: a search tree that contains no entries. This class is a singleton class: since all empty search trees are the same, there is no need for multiple instances of this class. Instead, a single instance of the class is created and made available through the static field SINGLETON. The constructor is private, preventing other code from mistakenly creating additional instances of the class.

Method Summary

Modifier and Type	Method and Description
void	addKeysToCollection(java.util.Collection<K> c) Add all keys bound in this tree to the collection c.
Tree<K,V>	delete(K key) Delete any binding the key has in this tree.
static <K extends java.lang.Comparable<K>,V> EmptyTree<K,V>	getInstance()
NonEmptyTree<K,V>	insert(K key, V value) Insert/update the Tree with a new key:value pair.
K	max() Return the maximum key in the subtree
K	min() Return the minimum key in the subtree
V	search(K key) Find the value that this key is bound to in this tree.
int	size() Return number of keys that are bound in this tree.
Tree<K,V>	subTree(K fromKey, K toKey) Returns a Tree containing all entries between fromKey and toKey, inclusive

Methods inherited from class java.lang.Object

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

Method Detail

getInstance

public static <K extends java.lang.Comparable<K>,V> EmptyTree<K,V> getInstance()

search

public V search(K key)

Description copied from interface: Tree

Find the value that this key is bound to in this tree.

Specified by:

search in interface Tree<K extends java.lang.Comparable<K>,V>

Parameters:

key - -- Key to search for

Returns:

-- value associated with the key by this Tree, or null if the key does not have an association in this tree.

insert

public NonEmptyTree<K,V> insert(K key,
                                V value)

Description copied from interface: Tree

Insert/update the Tree with a new key:value pair. If the key already exists in the tree, update the value associated with it. If the key doesn't exist, insert the new key value pair. This method returns a reference to an Tree that represents the updated value. In many, but not all cases, the method may just return a reference to this. This method is annotated @CheckReturnValue because you have to pay attention to the return value; if you simply invoke insert on a Tree and ignore the return value, your code is almost certainly wrong.

Specified by:

insert in interface Tree<K extends java.lang.Comparable<K>,V>

Parameters:

key - -- Key

value - -- Value that the key maps to

Returns:

-- updated tree

delete

public Tree<K,V> delete(K key)

Description copied from interface: Tree

Delete any binding the key has in this tree. If the key isn't bound, this is a no-op This method returns a reference to an Tree that represents the updated value. In many, but not all cases, the method may just return a reference to this. This method is annotated @CheckReturnValue because you have to pay attention to the return value; if you simply invoke delete on a Tree and ignore the return value, your code is almost certainly wrong.

Specified by:

delete in interface Tree<K extends java.lang.Comparable<K>,V>

Parameters:

key - -- Key

Returns:

-- updated tree

max

public K max()
      throws searchTree.TreeIsEmptyException

Description copied from interface: Tree

Return the maximum key in the subtree

Specified by:

max in interface Tree<K extends java.lang.Comparable<K>,V>

Returns:

maximum key

Throws:

TreeIsEmptyException - if the tree is empty

min

public K min()
      throws searchTree.TreeIsEmptyException

Description copied from interface: Tree

Return the minimum key in the subtree

Specified by:

min in interface Tree<K extends java.lang.Comparable<K>,V>

Returns:

minimum key

Throws:

TreeIsEmptyException - if the tree is empty

size

public int size()

Description copied from interface: Tree

Return number of keys that are bound in this tree.

Specified by:

size in interface Tree<K extends java.lang.Comparable<K>,V>

Returns:

number of keys that are bound in this tree.

addKeysToCollection

public void addKeysToCollection(java.util.Collection<K> c)

Description copied from interface: Tree

Add all keys bound in this tree to the collection c. The elements must be added in their sorted order.

Specified by:

addKeysToCollection in interface Tree<K extends java.lang.Comparable<K>,V>

Parameters:

c - - A list that acts as an accumulator for keys. Keys are inserted in the list in increasing order. You may not use any sorting method or Collections.sort to keep the list sorted.

subTree

public Tree<K,V> subTree(K fromKey,
                         K toKey)

Description copied from interface: Tree

Returns a Tree containing all entries between fromKey and toKey, inclusive

Specified by:

subTree in interface Tree<K extends java.lang.Comparable<K>,V>

Parameters:

fromKey - - Lower bound value for keys in subtree

toKey - - Upper bound value for keys in subtree

Returns:

Tree containing all entries between fromKey and toKey, inclusive