Transcript No Slide Title

Set,
TreeSet,
TreeMap,
Comparable,
Comparator
Def: The abstract data type set is a structure
that holds objects and satifies ARC:
Objects can be added.
Objects can be removed.
It can be determined if an object is
contained in the set.
As in the mathematical notion of a set, no
duplicate values are permitted in a set.
See java.util.set interface.
What is the primary difference between the
adt List and the adt Set?
There is no ordering in a set. That is, a class
that implements the Set interface does not
contain a method get(index).
The java.util package contains two classes for
implementing binary search trees:
TreeSet
and
TreeMap
TreeSet
Java.util.TreeSet is a class that implements the
interface Set. Some of the commonly used
methods in TreeSet are:
boolean add(Object obj);
boolean remove(Object obj);
boolean contains(Object obj);
int size();
Iterator iterator();
Object[] toArray();
•When TreeSet.remove( ) and TreeSet.add( ) the
binary search tree ordering property is preserved. The
TreeSet iterator performs inorder traversals of the
tree, delivering values in ascending order.
•This class guarantees log (n) time cost for the basic
operation remove(), add() and contains().
•TreeSet contains a default constructor (with no
arguments) to create an empty tree that will be sorted
by the natural order of objects that are comparable.
•TreeSet contains a constructor with one argument,
Comparator c, to create an empty tree that will be
sorted by the compare( ) method specified in the
Comparator object, c, passed.
What is the difference
between
Comparable and Comparator?
Comparable is an interface that contains one required method in
any class that implements it:
compareTo(Object o ).
This method must return a negative integer, zero, or a positive
integer when this object is less than, equal to, or greater than the
specified object, o. The implementor must also ensure that the
relation is transitive: (x.compareTo(y)>0 &&
y.compareTo(z)>0) implies x.compareTo(z)>0.
It is strongly recommended, but not strictly required that
(x.compareTo(y)==0) == (x.equals(y)).
Example:
public int compareTo(Object o)
{
return ((City)o.getPop( ) - getPop( );
}
Note: Defining compareTo gives one way to
compare objects of your class, allowing sorting
into ascending order by such library methods
as Arrays.sort.
However, for more general sorting, such as in
descending or or alphabetically, another
technique must be used:
implementation of the interface Comparator.
•Comparator requires two methods of its implementer:
compare( ) and equals( ).
•Usually the equals( ) method does not need to be coded,
because you can rely on the equals( ) method inherited
from Object.
Example of a class that implements Comparator:
public class ComparatorForCities implements Comparator{
public int compare (Object o1, Object o2){
String n1 = ((City) o1).getName();
String n2 = ((City) o2).getName();
return n1.compareToIgnoreCase(name2);}
}
•To use a comparator object, pass it to constructors or
methods that take a Comparator argument, that is any
class that implements the interface Comparator.
Example code fragment:
ComparatorForCities cn = new ComparatorForCities( );
City [ ] capitals;
…
Arrays.sort (capitals, cn);
…
int result = cn.compare(city1, city2);
Def: A Map is an adt that associates keys with their values
and finds a value for a given key. Commonly used methods in
java.util.Map are:
•Object put (Object key, Object value); //adds key and
associated value to the map, returning any value previously
associated with key or null.
•Object get (Object key); //returns value associated with key
or null.
•Boolean containsKey (Object key); //returns true if key is
associated with some value, otherwise returns false.
•Int size( ); //returns the number of associated key-value pairs
in the map.
•Set keySet( ); //returns the set of keys in the map.
•Java.util.TreeMap implements java.util.Map.
•TreeMap implements Map as a binary search tree ordered by keys
and contains a default constructor, which requires the keys to be
comparable, and a one argument (Comparator) constructor.
•TreeMap does not contain an iterator method, but keySet( ) may
be used to get the set of keys and then iterate over them.
Example:
TreeMap map = new TreeMap( );
SomeType key;
OtherType value;
Set keys = map.keySet( );
Iterator iter = keys.iterator( );
while (itr.hasNext( ))
{ key = (SomeType)itr.next( );
value = (OtherType)map.get(key); …}
How is a TreeSet different from a
TreeMap?
•TreeMap is more general than TreeSet.
•Although both implement binary search trees, TreeSet values are
compared to each other, while in TreeMap no ordering is
assumed for the values and the tree is arranged according to the
order of the keys.
•TreeSet (according to the Java API) is backed by an instance of
TreeMap, which means it has a TreeMap field in it that does all
the work.
•It is often easier to use a TreeMap