import java.util.*;



public class Map extends List
{

   public int size()
   {
      return(N);
   }

   public boolean isEmpty()
   {
      return(N==0);
   }

   public String get(String k)
   {
      ListElem p;

      for ( p = head; p != null; p = p.next )
      {
	  if ( p.key.equals( k ) )
	     return( p.value );
      }

      return(null);
   }

   public String put(String k, String v)
   {
      ListElem p;
      String   old;

      for ( p = head; p != null; p = p.next )
      {
          if ( p.key.equals( k ) )
	  {
	     old = p.value;
             p.value = v;         // Replace old value

	     return( old );
	  }
      }

      /* -------------------------------
	 Not found, insert new entry
	 ------------------------------- */
      p = new ListElem(k, v);

      insert(p);

      return(null);
   }

   public String remove(String k)
   {
      ListElem p;
      String   old;

      for ( p = head; p != null; p = p.next )
      {
          if ( p.key.equals( k ) )
          {
             old = p.value;

             delete(p);		// Delete element
      
	     return(old);	// Return old value
          }
      }

      return(null);		// Return "not found"
   }


   public Iterable keySet()
   {
      LinkedList<String> r = new LinkedList<String>();   
				     // One of the classes that implements
				     // "Iterable" is LinkedList

      ListElem p;

      for ( p = head; p != null; p = p.next )
      {
          r.add( p.key );
      }

      return(r);             
   }

   public Iterable values()
   {
      LinkedList<String> r = new LinkedList<String>(); 
				     // One of the classes that implements
                                     // "Iterable" is LinkedList

      ListElem p;

      for ( p = head; p != null; p = p.next )
      {
          r.add( p.value );
      }

      return(r);             
   }


   public Iterable entrySet()
   {
      LinkedList<ListElem> r = new LinkedList<ListElem>(); 
				     // One of the classes that implements
                                     // "Iterable" is LinkedList

      ListElem p;

      for ( p = head; p != null; p = p.next )
      {
          r.add( p );
      }

      return(r);             
   }
}