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. |