2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
|
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);
}
} //======================
}
|
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |