Using Java, fill the ¨you must implement¨ spots... import java.util.Map; import

Question

Using Java, fill the ¨you must implement¨ spots...

import java.util.Map;

import java.util.Iterator;

public interface HashFunction<AnyType>

{

    int hashCode( AnyType x );

}

public class MyHashMap<KeyType,ValueType> implements Iterable<Map.Entry<KeyType,ValueType>>

{

    private HashFunction<KeyType> hash1;

    private HashFunction<KeyType> hash2;

public boolean remove( KeyType k )

      { /* You must implement */ }

  

  

    public ValueType get( KeyType k )

      { /* You must implement */ }

  

    public String toString( )

      { /* You must implement */ }

  

    public Iterator<Map.Entry<KeyType,ValueType>> iterator( )

    {

        return new Iterator<Map.Entry<KeyType,ValueType>>( )

        {

            public boolean hasNext( )

              { /* You must implement */ }

          

            public Map.Entry<KeyType,ValueType> next( )

            {

                final Node<KeyType,ValueType> theCurrent = current;

              

Map.Entry<KeyType,ValueType> nextItem = new Map.Entry<KeyType,ValueType>( )

                { /* You must implement; access theCurrent here */ }

                };          

                // implement the rest of next, returning nextItem eventually,

            }

          

            private void advanceToNewList( )

              { /* You must implement */ }

          

            {  

            /* You must implement instance initialize */

            }

          

            Node<KeyType,ValueType> current;   // current node

            int listNum;                 // current list #

        };

    }

Explanation / Answer

abstract class MapImpl implements Map { private Set theSet; protected abstract Map.Entry makePair( KeyType key, ValueType value ); protected abstract Set makeEmptyKeySet( ); protected abstract Set clonePairSet( Set pairSet ); private Map.Entry makePair( KeyType key ) { return makePair( (KeyType) key, null ); } protected MapImpl( Set s ) { theSet = s; } protected MapImpl( Map m ) { theSet = clonePairSet( m.entrySet( ) ); } /** * Returns the number of keys in this map. * @return the number of keys in this collection. */ public int size( ) { return theSet.size( ); } /** * Tests if this map is empty. * @return true if the size of this map is zero. */ public boolean isEmpty( ) { return theSet.isEmpty( ); } /** * Tests if this map contains a given key. * @param key the key to search for. * @return true if the map contains the key. */ public boolean containsKey( KeyType key ) { return theSet.contains( makePair( key ) ); } /** * Returns the value in the map associated with the key. * @param key the key to search for. * @return the value that matches the key or null * if the key is not found. Since null values are allowed, * checking if the return value is null may not * be a safe way to ascertain if the key is present in the map. */ public ValueType get( KeyType key ) { Map.Entry match = theSet.getMatch( makePair( key ) ); if( match == null ) return null; else return match.getValue( ); } /** * Adds the key value pair to the map, overriding the * original value if the key was already present. * @param key the key to insert. * @param value the value to insert. * @return the old value associated with the key, or * null if the key was not present prior to this call. */ public ValueType put( KeyType key, ValueType value ) { Map.Entry match = theSet.getMatch( makePair( key ) ); if( match != null ) return match.setValue( value ); theSet.add( makePair( key, value ) ); return null; } /** * Remove the key and its value from the map. * @param key the key to remove. * @return the previous value associated with the key, * or null if the key was not present prior to this call. */ public ValueType remove( KeyType key ) { ValueType oldValue = get( key ); if( oldValue != null ) theSet.remove( makePair( key ) ); return oldValue; } /** * Removes all key value pairs from the map. */ public void clear( ) { theSet.clear( ); } /** * Abstract class to model a view (either key or value view). * Implements size and clear methods, but not iterator method. * View delegates to underlying map. */ private abstract class ViewClass extends AbstractCollection { public int size( ) { return MapImpl.this.size( ); } public void clear( ) { MapImpl.this.clear( ); } } /** * Class to model the key set view. * remove is overridden (otherwise a sequential search is used). * iterator gives a KeySetIterator (see Figure 19.81). * getMatch, the nonstandard part of weiss.util.Set is not needed. */ private class KeySetClass extends ViewClass implements Set { public boolean remove( Object key ) { return MapImpl.this.remove( (KeyType) key ) != null; } public Iterator iterator( ) { return new KeySetIterator( ); } public KeyType getMatch( KeyType key ) { throw new UnsupportedOperationException( ); } } /** * Class to model the value collection view. * Default remove which is a sequential search is used. * iterator gives a ValueCollectionIterator (see Figure 19.81). */ private class ValueCollectionClass extends ViewClass { public Iterator iterator( ) { return new ValueCollectionIterator( ); } } /** * Class used to iterate through key set view. * Delegates to an underlying entry set iterator. */ private class KeySetIterator implements Iterator { private Iterator itr = theSet.iterator( ); public boolean hasNext( ) { return itr.hasNext( ); } public void remove( ) { itr.remove( ); } public KeyType next( ) { return itr.next( ).getKey( ); } } /** * Class used to iterate through value collection view. * Delegates to an underlying entry set iterator. */ private class ValueCollectionIterator implements Iterator { private Iterator itr = theSet.iterator( ); public boolean hasNext( ) { return itr.hasNext( ); } public void remove( ) { itr.remove( ); } public ValueType next( ) { return itr.next( ).getValue( ); } } /** * Returns the keys in the map. * These semantics are different from those in java.util because * in this class, changes made to the returned key set do not cause * changes to be reflected in the map. * @return the keys in the map. */ public Set keySet( ) { return new KeySetClass( ); } /** * Returns the values in the map. There may be duplicates. * These semantics are different from those in java.util because * in this class, changes made to the returned value collection * do not cause changes to be reflected in the map. * @return the values in the map. */ public Collection values( ) { return new ValueCollectionClass( ); } /** * Return a set of Map.Entry objects corresponding to * the key/value pairs in the map. * @return the key/value pairs in the map. */ public Set entrySet( ) { return getSet( ); } /** * Return a reference to the underlying set. */ protected Set getSet( ) { return theSet; } protected abstract static class Pair implements Map.Entry { public Pair( KeyType k, ValueType v ) { key = k; value = v; } final public KeyType getKey( ) { return key; } final public ValueType getValue( ) { return value; } final public ValueType setValue( ValueType newValue ) { ValueType oldValue = value; value = newValue; return oldValue; } public String toString( ) { return key + "=" + value; } private KeyType key; private ValueType value; } public String toString( ) { StringBuilder result = new StringBuilder( "{" ); for( Map.Entry e : entrySet( ) ) result.append( e + ", " ); result.replace( result.length() - 2, result.length(), "}" ); return result.toString( ); } }

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.