scg/ch14/dictionary/Dictionary

From FANG

Jump to: navigation, search

001 package scg.ch14.dictionary;
002 
003 import java.util.ArrayList;
004 import java.util.Collections;
005 import java.util.Scanner;
006 
007 import scg.ch14.util.AttributeValuePair;
008 import scg.ch14.util.ReadAndWrite;
009 
010 /**
011  * A {@link Dictionary} file is a collection of lines of the form<br />
012  * alias=command
013  *
014  * <p>The file is read (ignoring leading and trailing spaces)
015  */
016 public class Dictionary {
017   /** the entries for the Dictionary */
018   ArrayList<AttributeValuePair> allEntries;
019 
020   /**
021    * Construct a new, empty, Dictionary
022    */
023   public Dictionary() {
024     allEntries = new ArrayList<AttributeValuePair>();
025   }
026 
027   /**
028    * Read the dictionary from the file. Each entry is on a single line
029    * with an = between the alias and the word.
030    *
031    * @param  scanner  open file reader to process
032    */
033   public Dictionary(Scanner scanner) {
034     this();
035     while (scanner.hasNextLine()) {
036       String attribute = ReadAndWrite.readAttribute(scanner);
037       /* throw away */ ReadAndWrite.readMatch(scanner, "=");
038       String value = ReadAndWrite.readValue(scanner);
039       if (attribute.length() != 0) {
040         allEntries.add(new AttributeValuePair(attribute, value));
041       }
042     }
043     Collections.sort(allEntries);
044   }
045 
046   /**
047    * Get the value in the dictionary associated with the given key; will
048    * return null if there is not matching entry.
049    *
050    * @param   key  the key of the entry for which to find a value
051    *
052    * @return  value associated with key if key is in dictionary; null
053    *          otherwise
054    */
055   public String get(String key) {
056     String value = null;
057     int ndx = indexOfKey(key);
058     if (ndx >= 0) {
059       value = allEntries.get(ndx).getValue();
060     }
061     return value;
062   }
063 
064   /**
065    * Does the {@link Dictionary} contain the given key?
066    *
067    * @param   key  key to lookup
068    *
069    * @return  true if there is an entry with the given key; false
070    *          otherwise
071    */
072   public boolean hasKey(String key) {
073     return (indexOfKey(key) >= 0);
074   }
075 
076   /**
077    * Add the key, value pair to the {@link Dictionary} if the key is not
078    * already found there. Replace the value of the entry for key with
079    * the new value if it is already in the dictionary.
080    *
081    * @param   key    the key for being able to lookup the entry
082    * @param   value  the value to set for the key
083    *
084    * @return  the previous value associated with the key or null if
085    *          there was no previous value
086    */
087   public String put(String key, String value) {
088     String previousValue = get(key);
089     int ndx = indexOfKey(key);
090     if (ndx >= 0) {
091       allEntries.get(ndx).setValue(value);
092     } else {
093       allEntries.add(new AttributeValuePair(key, value));
094       Collections.sort(allEntries);
095     }
096     return previousValue;
097   }
098 
099   /**
100    * Generate a string representation of the {@link Dictionary}.
101    */
102   @Override
103   public String toString() {
104     String retval = "";
105     String separator = "";
106     for (int i = 0; i != allEntries.size(); ++i) {
107       AttributeValuePair curr = allEntries.get(i);
108       retval += separator + curr.getAttribute() + " = " +
109         curr.getValue();
110       separator = "\n";
111     }
112     return retval;
113   }
114 
115   /**
116    * Binary search for index of entry with the given key. The algorithm
117    * is to track the range [lowerNdx, upperNdx), the range where the
118    * matching index must be (if there is one). When there are no Entry
119    * in the range, then we know there is no match.
120    *
121    * <p>Each time through the loop, get the middle index between the
122    * extremes of the range. Compare middle entry to matchKey; if middle
123    * smaller, bump lower up to mid + 1 (ignore the one that didn't
124    * match); if middle bigger, bump upper down to mid (which ignores the
125    * one that didn't match) and if mid matches, set return value and get
126    * out.
127    *
128    * <p>The invariant remains in force because the list is sorted. Thus
129    * if mid is small, then key must be above it in the list; if mid is
130    * big, then key must be below it in the list. The loop ends because
131    * each time through rangeSize(lowerNdx, upperNdx) is at least one
132    * smaller than it was; it must go down to 0 or smaller in a finite
133    * number of loops.
134    *
135    * @param   matchKey  the key to match.
136    *
137    * @return  -1 if not found, otherwise the index of the matching
138    *          {@link AttributeValuePair}
139    */
140   private int indexOfKey(String matchKey) {
141     int matchingNdx = -1;
142     int lowerNdx = 0;
143     int upperNdx = allEntries.size();
144     // invariant: if matchKey is in allEntries then
145     // matchNdx is on the range [lowerNdx, upperNdx).
146     while (rangeSize(lowerNdx, upperNdx) > 0) {// any remaining entries?
147       int midNdx = (lowerNdx + upperNdx) / 2;
148       int compareMidToMatch = allEntries.get(midNdx).getAttribute()
149         .compareTo(matchKey);
150       if (compareMidToMatch > 0) {
151         // allEntries[midNdx] < matchKey; search upper half of remaining
152         upperNdx = midNdx;
153       } else if (compareMidToMatch == 0) {
154         // allEntries[midNdx] == matchKey; return midNdx
155         matchingNdx = midNdx;
156         break;
157       } else {// if (compareMidToMatch > 0
158         // matchKey < allEntries[midNdx]; search lower half of remaining
159         lowerNdx = midNdx + 1;
160       }
161     }
162     return matchingNdx;
163   }
164 
165   /**
166    * Return the number of entries in the index range
167    * [lowerNdx-upperNdx). Notice that the index range is not symetric!
168    *
169    * @param   lowerNdx  the lower bound of the index range
170    * @param   upperNdx  the upper (excluded) bound of the index rang
171    *
172    * @return  size of the range [lowerNdx-upperNdx) (interval notation).
173    */
174   private int rangeSize(int lowerNdx, int upperNdx) {
175     return (upperNdx - lowerNdx);
176   }
177 }
178 
179 //Uploaded on Mon Mar 29 21:42:00 EDT 2010


Download/View scg/ch14/dictionary/Dictionary.java

Retrieved from "http://wiki.fangengine.org/index.php/scg/ch14/dictionary/Dictionary"



Views
Personal tools
Add to del.icio.usAdd to diggAdd to FacebookAdd to favoritesAdd to GoogleAdd to MySpaceAdd to PrintAdd to SlashdotAdd to StumbleUponAdd to Twitter

Games
Games