Binary search trees - Data Structures and Problem Solving Using Java - page 755

1 package weiss.util;
2
3 public class TreeMap<KeyType,ValueType> extends MapImpl<KeyType,ValueType>
4 {
5 public TreeMap( )
6 { super( new TreeSet<Map.Entry<KeyType,ValueType>>( ) ); }
7 public TreeMap( Map<KeyType,ValueType> other )
8 { super( other ); }
9 public TreeMap( Comparator<? super KeyType> comparator )
10 {
11 super( new TreeSet<Map.Entry<KeyType,ValueType>>( ) );
12 keyCmp = comparator;

13 }
14
15 public Comparator<? super KeyType> comparator( )
16 { return keyCmp; }
17
18 protected Map.Entry<KeyType,ValueType> makePair( KeyType key, ValueType value )
19 { return new Pair( key, value ); }
20
21 protected Set<KeyType> makeEmptyKeySet( )
22 { return new TreeSet<KeyType>( keyCmp ); }
23
24 protected Set<Map.Entry<KeyType,ValueType>>
25 clonePairSet( Set<Map.Entry<KeyType,ValueType>> pairSet )
26 { return new TreeSet<Map.Entry<KeyType,ValueType>>( pairSet ); }
27
28 private final class Pair extends MapImpl.Pair<KeyType,ValueType>
29 implements Comparable<Map.Entry<KeyType,ValueType>>
30 {
31 public Pair( KeyType k, ValueType v )
32 { super( k ,v ); }
33
34 public int compareTo( Map.Entry<KeyType,ValueType> other )
35 {
36 if( keyCmp != null )

return keyCmp.compare( getKey( ), other.getKey( ) ); 37

else 38

return (( Comparable) getKey( ) ).compareTo( other.getKey( ) ); 39

40 }
41 }
42
43

private Comparator<? super KeyType> keyCmp;

44 }

figure 19.82
TreeMap implementation