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

1 package weiss.util;
2
3 /**
4 * MapImpl implements the Map on top of a set.
5 * It should be extended by TreeMap and HashMap, with
6 * chained calls to the constructor.
7 */
8 abstract class MapImpl<KeyType,ValueType> implements Map<KeyType,ValueType>
9 {
10 private Set<Map.Entry<KeyType,ValueType>> theSet;
11
12 protected MapImpl( Set<Map.Entry<KeyType,ValueType>> s )
13 { theSet = s; }
14 protected MapImpl( Map<KeyType,ValueType> m )
15 { theSet = clonePairSet( m.entrySet( ) ); }
16
17 protected abstract Map.Entry<KeyType,ValueType>
18 makePair( KeyType key, ValueType value );
19 protected abstract Set<KeyType> makeEmptyKeySet( );
20 protected abstract Set<Map.Entry<KeyType,ValueType>>
21 clonePairSet( Set<Map.Entry<KeyType,ValueType>> pairSet );
22
23 private Map.Entry<KeyType,ValueType> makePair( KeyType key )
24 { return makePair( (KeyType) key, null ); }
25 protected Set<Map.Entry<KeyType,ValueType>> getSet( )
26 { return theSet; }
27
28 public int size( )
29 { return theSet.size( ); }
30 public boolean isEmpty( )
31 { return theSet.isEmpty( ); }
32 public boolean containsKey( KeyType key )
33 { return theSet.contains( makePair( key ) ); }
34 public void clear( )
35 { theSet.clear( ); }
36 public String toString( )
37 {
38 StringBuilder result = new StringBuilder( "{" );
39 for( Map.Entry<KeyType,ValueType> e : entrySet( ) )
40 result.append( e + ", " );
41 result.replace( result.length() - 2, result.length(), "}" );
42 return result.toString( );
43 }
44
45 public ValueType get( KeyType key )
46 { /* Figure 19.79 */ }
47 public ValueType put( KeyType key, ValueType value )
48 { /* Figure 19.79 */ }
49 public ValueType remove( KeyType key )
50 { /* Figure 19.79 */ }
figure 19.77
Abstract MapImpl helper class skeleton (part 1)