Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page
Chapter Sixteen listings: 13 classes and 2 interfaces

public interface Item
{
     /** Return the Scheme value of the Item, which is the current 
      *  value if a variable, the evaluation if a function call. */

     public Item getValue();


     /** Return the way the Item is presented to the user 
      *  on the screen. */

     public String toString();
}
//#############################################################



public class WordUnit implements Item
{
     public WordUnit (String given)               { }
     public Item getValue()           {return null; }
     public String toString()         {return null; }
}


public class Real implements Item
{
     public Real (double given)                   { }
     public Item getValue()           {return null; }
     public String toString()         {return null; }
}


public class List implements Item
{
     public Item getValue()           {return null; }
     public String toString()         {return null; }
}


public class TextString implements Item
{
     private String itsValue;


     public TextString (String given)
     {    itsValue = given;
     }    //======================


     public Item getValue()
     {    return this;
     }    //======================


     public String toString()
     {    return itsValue;
     }    //======================
}     


public class BadInput extends RuntimeException
{
     public BadInput ()
     {    super();
     }    //======================


     public BadInput (String message)
     {    super (message);
     }    //======================
}     


public interface Mapping // simplified Map, specific to this book
{
     /** Put this key/value pair in this Mapping if id is not null.  
      *  If some existing key/value pair has key.equals(id), 
      *  replace the value, otherwise add the key/value pair.  
      *  Return the previous value, or null if there was none. */

     public Object put (Object id, Object value);


     /** Tell whether a key/value pair satisfies key.equals(id). */

     public boolean containsKey (Object id);


     /** Return the value in the key/value pair where     
      *  key.equals(id).  Return null if no such key/value pair. */

     public Object get (Object id);


     /** Take out the key/value pair where key.equals(id), if any.  
      *  Return the existing value, or null if there was none.  */

     public Object remove (Object id);


     /** Tell whether this data structure has no elements. */

     public boolean isEmpty();


     /** Tell how many elements are in this data structure. */

     public int size();


     /** Return an object that can be used to list all the
      *  elements in this data structure one at a time. */

     public java.util.Iterator iterator();
}  


public class MapEntry implements java.util.Map.Entry
{
     private final Object itsKey;
     private final Object itsValue;


     public MapEntry (Object key, Object value)
     {    itsKey = key;
          itsValue = value;
     }    //======================


     public boolean equals (MapEntry given)
     {    return given != null
                   && (this.itsKey == given.itsKey 
                      || (this.itsKey != null 
                         && this.itsKey.equals (given.itsKey)))
                   && (this.itsValue == given.itsValue 
                      || (this.itsValue != null 
                         && this.itsValue.equals (given.itsValue)));
     }    //======================


     public Object getKey()
     {    return itsKey;
     }    //======================


     public Object getValue()
     {    return itsValue;
     }    //======================


     public Object setValue (Object ob)
     {    throw new UnsupportedOperationException ("can't setValue");
     }    //======================
}     


public class ArrayMap implements Mapping
{
     private MapEntry[] itsItem = new MapEntry [100];
     private int itsSize = 0;  // only has the default constructor


     /** Tell whether the data structure has no entries. */

     public boolean isEmpty()
     {    return itsSize == 0;
     }    //======================


     /** Tell whether a key/value pair satisfies key.equals(id). */

     public boolean containsKey (Object id)
     {    return lookUp (id) >= 0;
     }    //======================


     /** Return the value in the key/value pair for which
      *  key.equals(id).  Return null if no such key/value pair. */

     public Object get (Object id)
     {    int loc = lookUp (id);
          return (loc < 0)  ?  null  :  itsItem[loc].getValue();
     }    //======================


     /** Return the index of the key/value pair for which
      *  key.equals(id).  Return -1 if no such key/value pair. */

     private int lookUp (Object id)
     {    int k = itsSize - 1;
          while (k >= 0 && ! itsItem[k].getKey().equals (id))
               k--;
          return k;  // -1 if the object is not in the list
     }    //======================


     public int size()
     {    return itsSize;
     }    //======================


     public Object put (Object id, Object value)
     {    if (id == null)
               return null;
               int loc = lookUp (id);
          if (loc >= 0)
          {    Object valueToReturn = itsItem[loc].getValue();
               itsItem[loc] = new MapEntry (id, value);
               return valueToReturn;
          }
          itsItem[itsSize] = new MapEntry (id, value);
          itsSize++;
          return null;
     }    //======================


     public Object remove (Object id)
     {    int loc = lookUp (id);
          if (loc < 0)
               return null;
          Object valueToReturn = itsItem[loc].getValue();
          itsItem[loc] = itsItem[itsSize - 1];
          itsSize--;
          return valueToReturn;
     }    //======================


     public java.util.Iterator iterator()
     {    return new MapIt (this);
     }    //=======================


     private static class MapIt implements java.util.Iterator 
     {
          private int itsPos = 0;
          private ArrayMap itsMap;


          public MapIt (ArrayMap given)  // given will not be null
          {    itsMap = given;
          }    //======================


          /** Return true if the Iterator can produce another one.*/

          public boolean hasNext()
          {    return itsPos < itsMap.itsSize;
          }    //======================


          /** Return the next element in the sequence, if any. */

          public Object next()
          {    if ( ! hasNext())
                    throw new java.util.NoSuchElementException 
                             ("iterator has no next element!");
               itsPos++;
               return itsMap.itsItem [itsPos - 1];
          }    //======================


          /** Remove the element last returned by a call of next().*/

          public void remove()
          {    throw new UnsupportedOperationException ("no remove!");
          }    //======================
     }     
}     


import javax.swing.JOptionPane;

class MapDriver 
{
     public static void main (String [ ] args)
     {    JOptionPane.showMessageDialog (null,
                    "Repeatedly enter a word, then its definition.");
          WordProcessor.processManyWords (new SchemeMap());
          System.exit (0);
     }    //======================
}     
//########################################################



public class WordProcessor
{
     public static void processManyWords (Mapping odds)
     {    String word = JOptionPane.showInputDialog ("word?");
          while (word != null && word.length() > 0)
          {    String definition = JOptionPane.showInputDialog 
                         ("definition in/out?  ENTER key to see it: ");
               if (definition == null || definition.length() == 0)
                    System.out.println ("its definition is currently "
                                        + (String) odds.get (word));
               else if (odds.containsKey (word))
                    System.out.println (word + " had the definition "  
                                        + (String) odds.remove (word));
               else
               {    odds.put (word, definition);
                    System.out.println ("added " + word + " to the map; "
                                        + odds.size() + " entries.");
               }
               word = JOptionPane.showInputDialog ("word?");
          }
     }    //======================
}     



public class SchemeMap extends ArrayMap
{     // nothing is needed inside this name-changing class
}


public class NodeMap implements Mapping
{
     private MapEntry itsData;         // trailer node logic
     private NodeMap  itsNext;


     private NodeMap (MapEntry data, NodeMap next)
     {    itsData = data;
          itsNext = next;
     }    //======================


     public NodeMap()
     {    itsData = null;
          itsNext = null;
     }    //======================


     public boolean isEmpty()
     {    return itsNext == null;
     }    //======================


     public boolean containsKey (Object id)
     {    return ! lookUp (id).isEmpty();
     }    //======================


     public Object get (Object id)
     {    NodeMap loc = lookUp (id);
          return loc.isEmpty() ?  null  :  loc.itsData.getValue();
     }    //======================


     /** Return the node containing the key/value pair for which
      *  key.equals(id).  Return the trailer node if no such 
      *  key/value pair exists. */

     private NodeMap lookUp (Object id)
     {    return this.isEmpty() || this.itsData.getKey().equals (id)
                      ?  this  :  this.itsNext.lookUp (id);
     }    //======================


     public int size()
     {    return  this.isEmpty()  ?  0  :  1 + this.itsNext.size();
     }    //======================


     public Object put (Object id, Object value)
     {    if (id == null)   // we ignore a null key
               return null;
          NodeMap loc = lookUp (id);
          if (loc.isEmpty())
          {    this.itsNext = new NodeMap (this.itsData, this.itsNext);
               this.itsData = new MapEntry (id, value);
               return null;
          }
          Object valueToReturn = loc.itsData.getValue();
          loc.itsData = new MapEntry (id, value);
          return valueToReturn;
     }    //======================


     public Object remove (Object id)
     {    NodeMap loc = lookUp (id);
          if (loc.isEmpty())
               return null;
          Object valueToReturn = loc.itsData.getValue();
          loc.itsData = loc.itsNext.itsData;
          loc.itsNext = loc.itsNext.itsNext;
          return valueToReturn;
     }    //======================


     public NodeMap (Mapping given)
      {   java.util.Iterator it = given.iterator();
          if ( ! it.hasNext())
               return;
          itsData = (MapEntry) it.next();  // the first data value
          itsNext = new NodeMap();         // the new trailer node
          while (it.hasNext())
               itsNext = new NodeMap ((MapEntry) it.next(), itsNext);
     }    //=======================


     public java.util.Iterator iterator()
     {    return new MapIt (this);
     }    //======================


     private static class MapIt implements java.util.Iterator
     {
          private NodeMap itsPos;


          public MapIt (NodeMap given) // given will not be null 
          {    itsPos = given;
          }    //======================


          public boolean hasNext()
          {    return itsPos.itsNext != null;
          }    //======================


          public Object next()
          {    if ( ! hasNext())
                    throw new java.util.NoSuchElementException 
                             ("iterator has no next element!");
               Object valueToReturn = itsPos.itsData;
               itsPos = itsPos.itsNext;
               return valueToReturn;
          }    //======================


          public void remove() 
          {    throw new UnsupportedOperationException ("no remove!");
          }    //======================
     }     
}     


public class BinarySearchListMap implements Mapping // incomplete
{
     private Node[] itsItem;
     private int itsSize = 0;


     public Object put (Object id, Object value)
     {    if (id == null)                                          //1
               return null;  // Mappings ignore a null key         //2
          Node start = itsItem [lastLessEqual ((Comparable) id)];  //3
          Node loc = firstGreaterEqual ((Comparable) id, start);   //4
          if (loc.itsNext == null 
                          || ! loc.itsData.getKey().equals (id))
          {    itsSize++;                                          //7
               loc.itsNext = new Node (loc.itsData, loc.itsNext);  //8
               loc.itsData = new MapEntry (id, value);             //9
               return null;                                        //10
          }                                                        //11
          Object valueToReturn = loc.itsData.getValue();           //12
          loc.itsData = new MapEntry (id, value);                  //13
          return valueToReturn;                                    //14
     }    //======================


     /** Create a Mapping that contains the data values produced
      *  by the iterator.  Precondition:  The iterator produces
      *  MapEntry objects in ascending order of keys. */

     public BinarySearchListMap (java.util.Iterator it)
     {    Node header = new Node (null, null);                     //15
          Node p = header;                                         //16
          while (it.hasNext())                                     //17
          {    p.itsNext = new Node ((MapEntry) it.next(), null);  //18
               itsSize++;                                          //19
               p = p.itsNext;                                      //20
          }                                                        //21
          p.itsNext = new Node (null, null);  // trailer node      //22
          createArrayContainingEveryFourthOne (header.itsNext);    //23
     }     //======================


     private static class Node 
     {    public MapEntry itsData;
          public Node itsNext;

          public Node (MapEntry data, Node next)
          {    itsData = data;                                     //24
               itsNext = next;                                     //25
          }     //======================
     }


     private int lastLessEqual (Comparable id) { return 0; }
     private Node firstGreaterEqual (Comparable id, Node start) {return null; }
     private void createArrayContainingEveryFourthOne (Node p) { }
}     


public class IndexedMap implements Mapping // incomplete 
{
     private MapEntry[] itsItem = new MapEntry [100000]; // all null 

     /** All methods throw a RuntimeException if the given id is 
      *  not an Integer object with intValue() in 0...999999. */


     /** Tell whether a key/value pair satisfies key.equals(id). */

     public boolean containsKey (Object id)
     {    int k = ((Integer) id).intValue();
          return itsItem[k] != null;
     }    //======================


     /** Return the value in the key/value pair for which
      *  key.equals(id).  Return null if no such key/value pair. */

     public Object get (Object id)
     {    int k = ((Integer) id).intValue();
          return itsItem[k] != null ? itsItem[k].getValue() : null;
     }    //======================
}     


public class ChainedHashMap implements Mapping  // some methods stubbed
{
     private Node[] itsItem = new Node[100000]; // all null 
     private int itsSize = 0;


     /** Tell whether the Mapping contains any data values. */

     public boolean isEmpty()
     {    return itsSize == 0;
     }    //======================


     /** Tell whether a key/value pair satisfies key.equals(id). */

     public boolean containsKey (Object id)
     {    if (id == null)
               return false;
          int index = Math.abs (id.hashCode()) % itsItem.length;
          return lookUp (id, itsItem[index]) != null;
     }    //======================


     /** Return the value in the key/value pair for which
      *  key.equals(id).  Return null if no such key/value pair. */

     public Object get (Object id)
     {    if (id == null)
               return null;
          int index = Math.abs (id.hashCode()) % itsItem.length;
          Node p = lookUp (id, itsItem[index]);
          return (p == null)  ?  null  :  p.itsData.getValue();
     }    //======================


     /** Return the Node containing the key/value pair for which
      *  key.equals(id).  Return null if no such key/value pair. */

     private static Node lookUp (Object id, Node list)
     {    return (list == null)  ?  null
                  : list.itsData.getKey().equals (id)  ?  list
                        : lookUp (id, list.itsNext);
     }    //======================


     private static class Node
     {
          public MapEntry itsData;
          public Node itsNext;

          public Node (MapEntry data, Node next)
          {    itsData = data;
               itsNext = next;
          }
     }    //======================


     public int size()
     {    return itsSize;
     }    //======================


     public Object put (Object id, Object value) 
     {    if (id == null)
               return null;
          int index = Math.abs (id.hashCode()) % itsItem.length;
          Node loc = lookUp (id, itsItem[index]);
          if (loc != null)
          {    Object valueToReturn = loc.itsData.getValue();
               loc.itsData = new MapEntry (id, value);
               return valueToReturn;
          }
          itsItem[index] = new Node (new MapEntry (id, value), 
                                     itsItem[index]);
          itsSize++;
          return null;
     }    //======================


     public Object remove (Object id)
     {    return null;  // stubbed
     }    //======================


     public java.util.Iterator iterator()
     {    return null;  // stubbed
     }    //======================
}     


public class OpenHashMap implements Mapping
{
     private MapEntry[] itsItem = new MapEntry[100000]; // all null
     private int itsSize = 0;


     public boolean containsKey (Object id)
     {    if (id == null)
               return false;
          int index = Math.abs (id.hashCode()) % itsItem.length; 
          int jump  = Math.abs (id.hashCode()) % 13 + 1;
          while (itsItem[index] != null 
                          && ! id.equals (itsItem[index].getKey())
               index = (index + jump) % itsItem.length;
          return itsItem[index] != null;
     }    //======================
}     


public class List implements Item
{
     public static final List EMPTY = new List (null, null);
     private static SchemeMap theDefs = new SchemeMap();
     private static SchemeMap theSpecials = addThemAll();
     /////////////////////////////////
     private final Item itsFirst;
     private final List itsRest;


     public List (Item first, List rest)
     {    itsFirst = first;
          itsRest  = rest;
     }    //======================


     private static SchemeMap addThemAll()
     {    SchemeMap result = new SchemeMap();
          result.put (new WordUnit ("set!"), new Real (1));
          result.put (new WordUnit ("define"), new Real (2));
          result.put (new WordUnit ("+"), new Real (3));
          // many more will be added later
          return result;
     }    //======================


     public Item getValue()
     {    if (this.isEmpty())
               return EMPTY;
          Real index = (Real) theSpecials.get (this.first());
          return index != null ? this.rest().specialValue (index)
                               : this.normalValue();
     }    //======================


     public Item first()
     {    return itsFirst;
     }    //======================


     public List rest()
     {    return itsRest;
     }    //======================


     public boolean isEmpty()
     {    return itsRest == null;
     }    //======================


     public String toString()
     {    if (this.isEmpty())
               return "empty";
          String result = "(";
          List p;
          for (p = this;  ! p.itsRest.isEmpty();  p = p.itsRest)
               result += p.itsFirst.toString() + " ";
          return result + p.itsFirst.toString() + ")";
     }    //======================


     /** Find the definition of the function, evaluate the 
      *  function call, and return the calculated value. */

     private Item normalValue()
     {    List def = (List) theDefs.get (this.itsFirst);
          if (def == null)
               throw new BadInput (this.itsFirst.toString()
                                   + " is not a function name");
          List actuals = this.itsRest.allValues();
          ((List) def.itsFirst).itsRest.assignValues (actuals);
          return def.itsRest.itsFirst.getValue();
     }    //======================


     private List allValues()  
     {    return this.isEmpty()  ?  EMPTY  :  new List 
                   (this.itsFirst.getValue(), this.itsRest.allValues());
     }    //======================


     private void assignValues (List actuals)  
          // Protecting against different lengths is an exercise
     {    if ( ! this.isEmpty())
          {    WordUnit parameter = (WordUnit) this.itsFirst;
               parameter.setVariableValue (actuals.itsFirst);
               this.itsRest.assignValues (actuals.itsRest);
          }
     }    //======================
}     

All information Copyright (c)1999 - Dr. William C. Jones, Jr.
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved.