import java.util.*;

public class ListMap<K, V> implements Map<K, V>
{
   public ListEntry<K, V>  head;
   public int N;

   /* ============================================================
      Constructor: make an empty list (= an empty map)
      ============================================================ */
   public ListMap()
   {
      head = null;   // Start with empty list
      N = 0;
   }

   // *************************************************
   // List help function
   //
   //    delete(p): delete Entry p
   // *************************************************
   public void delete(ListEntry<K, V> p)
   {
      ListEntry<K, V> prevElem, nextElem;

      if ( N == 0 )
      {
         return ;                 // Nothing to delete
      }
      else if ( N == 1 )          // Delete last element ==> empty list
      {
         head = null;
      }
      else if ( p.prev == null )  // Delete FIRST element
      {
         System.out.println("Delete: " + p.getKey());

         nextElem = p.next;
         nextElem.prev = null;

         head = nextElem;  // The second is the new "first element"
      }
      else if ( p.next == null )  // Delete LAST element
      {
         System.out.println("Delete: " + p.getKey());

         prevElem = p.prev;
         prevElem.next = null;
      }
      else				// Delete a "middle element"
      {
         System.out.println("Delete: " + p.getKey());

         prevElem = p.prev;
         nextElem = p.next;

         nextElem.prev = p.prev;
         prevElem.next = p.next;
      }

      N--;
   }

   // *************************************************
   // List help function
   //
   //    insert(p): insert at head
   // *************************************************
   public void insert(ListEntry<K, V> p)
   {
      if ( N == 0 )        // Insert in empty list
      {
         p.next = null;
         p.prev = null;

         head = p;
      }
      else
      {
         p.next = head;
         p.prev = null;
         head.prev = p;
         head = p;
      }

      N++;
   }


   // *****************************************************************
   //  Map functions
   // *****************************************************************

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

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

   public V get(K k)
   {
      ListEntry<K, V> p;

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

      return(null);
   }

   public V put(K k, V v)
   {
      ListEntry<K, V> p;
      V old;

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

	     return( old );
	  }
      }

      /* -------------------------------
	 Not found, insert new entry
	 ------------------------------- */
      p = new ListEntry<K, V> (k, v);

      insert(p);

      return(null);
   }

   public V remove(K k)
   {
      ListEntry<K, V> p;
      V old;

      for ( p = head; p != null; p = p.next )
      {
          if ( p.getKey().equals( k ) )
          {
             old = p.getValue();    // Save old value for return

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

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


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

      ListEntry<K, V> p;

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

      return(r);             
   }

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

      ListEntry<K, V> p;

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

      return(r);             
   }


   public Collection<Entry<K, V>> entrySet()
   {
      LinkedList<Entry<K, V>> r 
		= new LinkedList<Entry<K, V>>(); 
				     // One of the classes that implements
                                     // "Collection" is LinkedList

      ListEntry<K, V> p;

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

      return(r);             
   }


   public String toString()
   {
      String output = "{";

      ListEntry<K, V> p;

      for ( p = head; p != null; p = p.next )
      {
          output = output + p + " ";
      }

      output += "}";
      return output;
   }
}