Class BinarySearchST<Key extends java.lang.Comparable<Key>,Value>

java.lang.Object

BinarySearchST<Key,Value>

public class BinarySearchST<Key extends java.lang.Comparable<Key>,Value>
extends java.lang.Object

This is an implementation of a symbol table whose keys are comparable. The keys are kept in increasing order in an array. The corresponding values are kept in a parallel array. Following our usual convention for symbol tables, the keys are pairwise distinct.

For additional documentation, see Section 3.1 of "Algorithms, 4th Edition" (p.378 of paper edition), by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
BinarySearchST() Costructor.
BinarySearchST(int capacity) Costructor.

Method Summary

Methods

Modifier and Type	Method and Description
Key	ceiling(Key key) Returns the smallest key that is greater than or equal to the given key.
boolean	contains(Key key) Is the key in this symbol table?
void	delete(Key key) Remove key (and the corresponding value) from this symbol table.
void	deleteMax() Delete the maximum key and its associated value from this symbol table.
void	deleteMin() Delete the minimum key and its associated value from this symbol table.
Key	floor(Key key) Returns the greatest key that is smaller than or equal to the given key.
Value	get(Key key) Returns the value associated with the given key, or null if no such key.
boolean	isEmpty() Is this symbol table empty?
java.lang.Iterable<Key>	keys() Returns an iterable queue containing all keys in this symbol table.
java.lang.Iterable<Key>	keys(Key lo, Key hi) Returns an iterable queue containing all keys of this symbol table that belong to the closed interval [lo, hi].
static void	main(java.lang.String[] args) Test client.
Key	max() Returns the greatest key in this table.
Key	min() Returns the smallest key in this table.
void	put(Key key, Value val) Search for key in this symbol table.
int	rank(Key key) Returns the number of keys in the table that are strictly smaller than the given key.
Key	select(int k) Returns a key that is strictly greater than (exactly) k other keys in the table.
int	size() Returns the number of (key,value) pairs in this symbol table.
int	size(Key lo, Key hi) Number of keys in the closed interval [lo, hi].

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearchST

public BinarySearchST()

Costructor. Creates an empty symbol table with default initial capacity.

BinarySearchST

public BinarySearchST(int capacity)

Costructor. Creates an empty symbol table with given initial capacity.

Method Detail

contains

public boolean contains(Key key)

Is the key in this symbol table?

size

public int size()

Returns the number of (key,value) pairs in this symbol table.

isEmpty

public boolean isEmpty()

Is this symbol table empty?

get

public Value get(Key key)

Returns the value associated with the given key, or null if no such key. Argument key must be nonnull.

rank

public int rank(Key key)

Returns the number of keys in the table that are strictly smaller than the given key. (This is the heart of binary search method.) Argument key must be nonnull.

put

public void put(Key key,
       Value val)

Search for key in this symbol table. If key is in the table, update the corresponing value. Otherwise, add the (key,val) pair to the table.

delete

public void delete(Key key)

Remove key (and the corresponding value) from this symbol table. If key is not in the table, do nothing.

deleteMin

public void deleteMin()

Delete the minimum key and its associated value from this symbol table. The symbol table must be nonempty.

deleteMax

public void deleteMax()

Delete the maximum key and its associated value from this symbol table.

min

public Key min()

Returns the smallest key in this table. Returns null if the table is empty.

max

public Key max()

Returns the greatest key in this table. Returns null if the table is empty.

select

public Key select(int k)

Returns a key that is strictly greater than (exactly) k other keys in the table. Returns null if k < 0. Returns null if k is greater that or equal to the total number of keys in the table.

floor

public Key floor(Key key)

Returns the greatest key that is smaller than or equal to the given key. If there is no such key in the table (i.e., if the given key is smaller than any key in the table), returns null.

ceiling

public Key ceiling(Key key)

Returns the smallest key that is greater than or equal to the given key. If there is no such key in the table (i.e., if the given key is greater than any key in the table), returns null.

size

public int size(Key lo,
       Key hi)

Number of keys in the closed interval [lo, hi]. Returns the number of keys in this symbol table that belong to the closed interval [lo, hi]. Arguments lo and hi must be nonnull.

keys

public java.lang.Iterable<Key> keys()

Returns an iterable queue containing all keys in this symbol table.

keys

public java.lang.Iterable<Key> keys(Key lo,
                           Key hi)

Returns an iterable queue containing all keys of this symbol table that belong to the closed interval [lo, hi]. Arguments lo and hi must be both nonnull or both null. In the latter case, return empty queue.

main

public static void main(java.lang.String[] args)

Test client. Reads a sequence of strings from the standard input. Builds a symbol table whose keys are the strings read. The value of each string is its position in the input stream (0 for the first string, 1 for the second, and so on). Then prints all the (key,value) pairs.