001 package edu.nrao.sss.util;
002
003 import java.util.Comparator;
004 import java.util.Map;
005 import java.util.SortedMap;
006 import java.util.SortedSet;
007 import java.util.TreeMap;
008 import java.util.TreeSet;
009
010 /**
011 * A lookup table.
012 * <p>
013 * A lookup table is very similar to a map. The main difference is that to
014 * get a value from a map, you need to specify exactly a key that the map
015 * holds. To get a value from a lookup table, though, all you need to have
016 * is a key that is at least as great as the key for the first entry in the
017 * table. The value returned for any key, K, is the value found in the entry
018 * whose key is less than or equal to K. The entries in a lookup table are
019 * sorted in ascending order of the entries' keys. The definition of
020 * "ascending" depends on the comparator used to construct the table.</p>
021 * <p>
022 * A classic use of a lookup table is a table of marginal income tax rates.
023 * Your marginal tax rate is given by the entry whose income is less than
024 * or equal to your own.</p>
025 * <p>
026 * The keys of this table may be any object that implements the
027 * {@link java.lang.Comparable} interface. Examples of common key types
028 * are numbers, strings, and dates. Via the use of
029 * <a href="http://java.sun.com/j2se/1.5.0/docs/guide/language/generics.html">
030 * generics</a>, this
031 * table is type safe.</p>
032 * <p>
033 * <b>CVS Info:</b>
034 * <table style="margin-left:2em">
035 * <tr><td>$Revision: 161 $</td></tr>
036 * <tr><td>$Date: 2006-12-15 11:48:34 -0700 (Fri, 15 Dec 2006) $</td></tr>
037 * <tr><td>$Author: btruitt $</td></tr>
038 * </table></p>
039 *
040 * @author David M. Harland
041 * @since 2006-07-31
042 */
043 public class LookupTable<K extends Comparable<K>, V>
044 implements Cloneable
045 {
046 private SortedMap<K, V> table;
047
048 /**
049 * Creates a new, empty table, sorted according to the keys' natural order.
050 */
051 public LookupTable()
052 {
053 table = new TreeMap<K, V>();
054 }
055
056 /**
057 * Constructs a new, empty table, sorted according to the given comparator.
058 *
059 * @param c the comparator that will be used to sort this map. A <i>null</i>
060 * value indicates that the keys' natural ordering should be used.
061 */
062 public LookupTable(Comparator<? super K> c)
063 {
064 table = new TreeMap<K, V>(c);
065 }
066
067 /**
068 * Removes all entries from this table.
069 */
070 public void clear()
071 {
072 table.clear();
073 }
074
075 /**
076 * Puts the given key / value pair into this table.
077 * @param key key with which the specified value is to be associated.
078 * @param value value to be associated with the specified key.
079 * @return the value that had been previously mapped to {@code key}.
080 */
081 public V put(K key, V value)
082 {
083 return table.put(key, value);
084 }
085
086 /**
087 * Copies all the mappings from {@code map} into this table.
088 * @param map a source of key / value pairs.
089 */
090 public void putAll(Map<K, V> map)
091 {
092 table.putAll(map);
093 }
094
095 /**
096 * Removes the entry whose key is {@code key} from this table, if present.
097 *
098 * @param key the key whose entry should be removed from this table.
099 *
100 * @return the value that had been associated with {@code key}, or
101 * <i>null</i> if this table had no entry for {@code key}.
102 */
103 public V remove(K key)
104 {
105 return table.remove(key);
106 }
107
108 /**
109 * Removes all entries in this table whose value is {@code value}.
110 * @param value the value to be removed entirely from this table.
111 * @return the number of entries that were removed from this table.
112 */
113 public int removeValue(V value)
114 {
115 int removals = 0;
116
117 for (K key : getKeySetFor(value))
118 {
119 if (remove(key).equals(value))
120 removals++;
121 }
122
123 return removals;
124 }
125
126 /**
127 * Returns <i>true</i> if this table contains an entry whose key is
128 * {@code key}.
129 * @param key a key that may be present in this table.
130 * @return <i>true</i> if this table contains an entry whose key is
131 * {@code key}.
132 */
133 public boolean containsKey(K key)
134 {
135 return table.containsKey(key);
136 }
137
138 /**
139 * Returns <i>true</i> if this table contains one or more entries whose value
140 * is {@code value}.
141 * @param value a value that may be present in this table.
142 * @return <i>true</i> if this table contains one or more entries whose value
143 * is {@code value}.
144 */
145 public boolean containsValue(V value)
146 {
147 return table.containsValue(value);
148 }
149
150 /**
151 * Returns the value associated with the first key that is less than or
152 * equal to {@code key}. The keys of this table are ordered according
153 * to the compartor specified during the construction of this table.
154 * If no comparator was so specified, then the keys are in their
155 * natural order.
156 * <p>
157 * A return value of <i>null</i> means either that {@code key} is less
158 * than the first key in this table, or that the greatest key that is
159 * not greater than {@code key} maps to a value of <i>null</i>.</p>
160 *
161 * @param key the key for which a value is sought.
162 *
163 * @return the value associated with the first key that is less than or
164 * equal to {@code key}.
165 */
166 public V get(K key)
167 {
168 //Quick exit if key is below bottom of table
169 if (key.compareTo(table.firstKey()) < 0)
170 return null;
171
172 //Initialize key to last key in case we run off top of table
173 K correctKey = table.lastKey();
174
175 K prevKey = null;
176
177 //Loop through table's keys, looking for first one that is greater than
178 //or equal to our key. If equal, correctKey is the current key.
179 //If greater than, correctKey was the previous one.
180 for (K tableKey : table.keySet())
181 {
182 int keyCompare = key.compareTo(tableKey);
183
184 if (keyCompare < 1)
185 {
186 correctKey = (keyCompare == 0) ? tableKey : prevKey;
187 break;
188 }
189
190 prevKey = tableKey;
191 }
192
193 return table.get(correctKey);
194 }
195
196 /**
197 * Returns this table's set of keys.
198 * @return this table's set of keys.
199 */
200 public SortedSet<K> getKeySet()
201 {
202 TreeSet<K> result = new TreeSet<K>();
203
204 result.addAll(table.keySet());
205
206 return result;
207 }
208
209 /**
210 * Returns the set of keys under which {@code value} is stored.
211 * @param value a value that might be stored in this table.
212 * @return the set of keys under which {@code value} is stored.
213 */
214 public SortedSet<K> getKeySetFor(V value)
215 {
216 TreeSet<K> result = new TreeSet<K>();
217
218 for (Map.Entry<K, V> tableEntry : table.entrySet())
219 {
220 if (tableEntry.getValue().equals(value))
221 result.add(tableEntry.getKey());
222 }
223
224 return result;
225 }
226
227 /**
228 * Returns the number of entries in this table.
229 * @return the number of entries in this table.
230 */
231 public int size()
232 {
233 return table.size();
234 }
235
236 /**
237 * Returns this table in the form of a sorted map.
238 * The keys and values of the map are references to the keys and
239 * values of this table.
240 *
241 * @return a sorted map expression of this lookup table.
242 */
243 public SortedMap<K,V> toMap()
244 {
245 return new TreeMap<K,V>(table);
246 }
247
248 /**
249 * Returns a text representation of this table.
250 * The form of the returned text is<pre>
251 *
252 * (key1.toString, value1.toString)
253 * ...
254 * (keyN.toString, valueN.toString)</pre>
255 *
256 * @return a text representation of this table.
257 */
258 public String toString()
259 {
260 final String EOL = System.getProperty("line.separator");
261
262 StringBuilder buff = new StringBuilder(EOL);
263
264 for (K key : getKeySet())
265 buff.append('(').append(key.toString())
266 .append(", ").append(get(key).toString())
267 .append(')').append(EOL);
268
269 return buff.toString();
270 }
271
272 /**
273 * Returns a shallow copy of this lookup table.
274 * The returned table is distinct from this one, but shares the actual
275 * instances of the keys and values with this table.
276 * <p>
277 * If anything goes wrong during the cloning procedure,
278 * a {@code RuntimeException} will be thrown.</p>
279 */
280 @SuppressWarnings("unchecked")
281 public LookupTable<K,V> clone()
282 {
283 LookupTable<K,V> clone;
284
285 try
286 {
287 clone = (LookupTable<K,V>)super.clone();
288
289 clone.table = this.toMap();
290 }
291 catch (Exception ex)
292 {
293 throw new RuntimeException(ex);
294 }
295
296 return clone;
297 }
298
299 /**
300 * Returns <i>true</i> if {@code o} is equal to this table.
301 * See {@link java.util.AbstractMap#equals(Object)} for a
302 * description on how the comparison is performed.
303 */
304 @SuppressWarnings("unchecked")
305 public boolean equals(Object o)
306 {
307 //Quick exit if o is null
308 if (o == null)
309 return false;
310
311 //Quick exit if o is this
312 if (o == this)
313 return true;
314
315 //Quick exit if classes are different
316 if (!o.getClass().equals(this.getClass()))
317 return false;
318
319 LookupTable<K,V> other = (LookupTable<K,V>)o;
320
321 //Compare the tables
322 return this.table.equals(other.table);
323 }
324
325 /**
326 * Returns a hash code value for this table.
327 * See {@link java.util.AbstractMap#hashCode()} for a
328 * description on how the comparison is performed.
329 */
330 public int hashCode()
331 {
332 return table.hashCode();
333 }
334
335 //Here for quick manual test
336 /*
337 public static void main(String[] args)
338 {
339 LookupTable<Integer, String> table = new LookupTable<Integer, String>();
340
341 table.put( 0, "F");
342 table.put(60, "D");
343 table.put(70, "C");
344 table.put(80, "B");
345 table.put(90, "A");
346
347 System.out.println();
348 System.out.println("Key Set: " + table.getKeySet());
349 System.out.println("ValueSet: " + table.toMap().values());
350
351 System.out.println();
352 System.out.println("A score of < 0 gives you a grade of " + table.get(-10));
353 for (int i=0; i < 20; i++)
354 {
355 //Random score w/ bias towards score >= 60
356 int score = (int)(Math.random() * 100.0);
357 if (score < 60)
358 score = (int)(Math.random() * 100.0);
359
360 String grade = table.get(score);
361 System.out.println("A score of "+score+" gives you a grade of "+grade);
362 }
363 System.out.println();
364 }
365 */
366 }