1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package net.wotonomy.foundation.internal;
20
21 import java.util.*;
22
23 /***
24 * A queue based implementation of the Map interface. This class provides for
25 * all the opertions of a map, but keeps the entries in the same sequence as
26 * originally added. The first entry placed in the map will be the first
27 * entry retreived during iteration: first-in, first-out (FIFO). <BR><BR>
28 *
29 * Keys cannot be duplicated. If an entry is made using a key that already
30 * exists, the value for that key will be replaced with that new value. There
31 * are no such restrictions on the values. The values may be null. <BR><BR>
32 *
33 * Some convenience methods are provided for the queue type operations. The
34 * first key can be retreived as well as the last key. A key can be used
35 * to retreive its corresponding value from the map. A value can also be used
36 * to retreive its key from the map, however, since there may be multiple values
37 * of the same equality, the first key found will be returned. <BR><BR>
38 *
39 * @author rglista@blacksmith.com
40 * @author mpowers@blacksmith.com
41 * @date $Date: 2006-02-18 22:41:36 +0000 (Sat, 18 Feb 2006) $
42 * @revision $Revision: 899 $
43 */
44 public class QueueMap implements Map
45 {
46 List values;
47 List keys;
48 Map keyToValue;
49
50 /***
51 * Creates an empty QueueMap.
52 */
53 public QueueMap()
54 {
55 values = new LinkedList();
56 keys = new LinkedList();
57 keyToValue = new HashMap();
58 }
59
60 /***
61 * Creates a QueueMap and places the entries from the passed in map into this map.
62 * The order of the entries is based on however the iterator iteratated through
63 * the map entries.
64 * @param t A map object.
65 */
66 public QueueMap( Map t )
67 {
68 values = new ArrayList();
69 keys = new ArrayList();
70 keyToValue = new HashMap();
71
72 putAll( t );
73 }
74
75 /***
76 * Removes all the entries from this map.
77 */
78 public void clear()
79 {
80 values.clear();
81 keys.clear();
82 keyToValue.clear();
83 }
84
85 /***
86 * Tests to see if the key is contained in the map. If the key is present in
87 * the map, then TRUE is returned, otherwise FALSE is returned. The equals()
88 * operation is used to determine equality.
89 * @return True if the map contains the given key, false otherwise.
90 */
91 public boolean containsKey( Object key )
92 {
93 return keyToValue.containsKey( key );
94 }
95
96 /***
97 * Tests to see if the value is contained in the map. If the value is present in
98 * the map, then TRUE is returned, otherwise FALSE is returned. The equals()
99 * operation is used to determine equality. The value can be null and will
100 * return TRUE if null is a value in the map. If TRUE is returned, then there
101 * may be more than one values in the map.
102 * @return True if the map contains the given value, false otherwise.
103 */
104 public boolean containsValue( Object value )
105 {
106 return keyToValue.containsValue( value );
107 }
108
109 /***
110 * Returns a set view of the mappings contained in this map. Each element
111 * in the returned set is a <tt>Map.Entry</tt>. The returned set is NOT backed
112 * by the map, so changes to the map are NOT reflected in the set, and vice-versa.
113 * The returned set is independent of this Map and its underlying structure.
114 *
115 * @return a set view of the mappings contained in this map.
116 */
117 public Set entrySet()
118 {
119 Set result = new HashSet(keys.size(), 1F);
120
121 for ( int i = 0; i < keys.size(); i++ )
122 {
123 result.add( new KeyValuePair( keys.get(i), values.get(i) ) );
124 }
125
126 return result;
127 }
128
129 /***
130 * Compares the specified object with this map for equality. Returns
131 * <tt>true</tt> if the given object is also a map and the two Maps
132 * represent the same mappings. More formally, two maps <tt>t1</tt> and
133 * <tt>t2</tt> represent the same mappings if
134 * <tt>t1.entrySet().equals(t2.entrySet())</tt>. This ensures that the
135 * <tt>equals</tt> method works properly across different implementations
136 * of the <tt>Map</tt> interface.
137 *
138 * @param o object to be compared for equality with this map.
139 * @return <tt>true</tt> if the specified object is equal to this map.
140 */
141 public boolean equals( Object o )
142 {
143 return keyToValue.equals( o );
144 }
145
146 /***
147 * Returns the corresponding value for the given key. The returned value may be
148 * null as that is a legal value in this map. However, if the key is not
149 * contained in this map then null is also returned. Use the containsKey()
150 * method to distinguish between the two cases.
151 * @param key A key into the map.
152 * @return The value corresponding to the key (can be null), or null if the key
153 * is not contained in the map.
154 */
155 public Object get( Object key )
156 {
157 return keyToValue.get( key );
158 }
159
160 /***
161 * Returns the hash code value for this map. The hash code of a map
162 * is defined to be the sum of the hashCodes of each entry in the map's
163 * entrySet view. This ensures that <tt>t1.equals(t2)</tt> implies
164 * that <tt>t1.hashCode()==t2.hashCode()</tt> for any two maps
165 * <tt>t1</tt> and <tt>t2</tt>, as required by the general
166 * contract of Object.hashCode.
167 *
168 * @return the hash code value for this map.
169 */
170 public int hashCode()
171 {
172 return keyToValue.hashCode();
173 }
174
175 /***
176 * Returns true is this map contains no key-value mappings.
177 * @return True is this map contains no entries, false otherwise.
178 */
179 public boolean isEmpty()
180 {
181 return keyToValue.isEmpty();
182 }
183
184 /***
185 * Returns the keys used in the map. There is no order implied in the returned
186 * set and may be different than the the order in which they were inserted.
187 * @return A Set containing all the keys used in the map.
188 */
189 public Set keySet()
190 {
191 Set result = new HashSet(keys.size(), 1F);
192
193 for ( int i = 0; i < keys.size(); i++ )
194 {
195 result.add( keys.get(i) );
196 }
197
198 return result;
199 }
200
201 /***
202 * Places the key/value entry into the map at the end position. If the key
203 * already exists in the map, then its value is replaced by the new given
204 * value. The mapping does not change order in this case. The specified
205 * key cannot be null.
206 * @param key The key to place into the map, cannot be null.
207 * @param value The value to associate with the key, may be null.
208 * @return Null if the key is new, the replaced value if the key already
209 * existed. (Note: If the key was null, then null is returned.)
210 */
211 public Object put( Object key, Object value )
212 {
213 if ( key == null ) return null;
214
215 if ( keys.contains( key ) )
216 {
217 values.remove( keys.indexOf( key ) );
218 values.add( keys.indexOf( key ), value );
219 }
220 else
221 {
222 values.add( value );
223 keys.add( key );
224 }
225
226 return keyToValue.put( key, value );
227 }
228
229 /***
230 * Places all the entries from this given map into this map. If the keys
231 * already exist, then there values are replaced.
232 * @param t A map of key/value entries.
233 */
234 public void putAll( Map t )
235 {
236 if ( t == null )
237 {
238
239 return;
240 }
241
242
243 for ( Iterator it = t.keySet().iterator(); it.hasNext(); )
244 {
245 Object aKey = it.next();
246 put( aKey, t.get( aKey ) );
247 }
248 }
249
250 /***
251 * Remove the mapping of the key and associated value from this map.
252 * Note: null is a valid value in the map.
253 * @param key A key to remove from the map, cannot be null.
254 * @return The value of the removed mapping, null if the mapping did not exist.
255 * Null could also be returned if the associated value of the key was null.
256 */
257 public Object remove( Object key )
258 {
259 if ( key == null ) return null;
260
261 Object value = null;
262
263 if ( containsKey( key ) )
264 {
265 value = keyToValue.remove( key );
266 int i = values.indexOf( value );
267 if ( i != -1 )
268 {
269 keys.remove( i );
270 values.remove( i );
271 }
272 }
273
274 return value;
275 }
276
277 /***
278 * Returns the number of key/value pairs in this map.
279 * @return The number of pairs.
280 */
281 public int size()
282 {
283 return values.size();
284 }
285
286 /***
287 * Returns an ordered list of keys from the map. The order is the same
288 * as the added order of the mapped items.<br>
289 * NOTE: The returned list is the underlying keys list used by this class.
290 * If modification are to be made to this list, it should be cloned first.
291 * @return An ordered list of keys.
292 */
293 public List keys()
294 {
295 return keys;
296 }
297
298 /***
299 * Returns an ordered list of values from the map. The order is the same
300 * as the added order of the mapped items.
301 * NOTE: The returned list is the underlying keys list used by this class.
302 * If modification are to be made to this list, it should be cloned first.
303 * @return An ordered list of values.
304 */
305 public Collection values()
306 {
307 return values;
308 }
309
310 /***
311 * Returns the corresponding value for the given key. The returned value may be
312 * null as that is a legal value in this map. However, if the key is not
313 * contained in this map then null is also returned. Use the containsKey()
314 * method to distinguish between the two cases.
315 * @param key A key into the map.
316 * @return The value corresponding to the key (can be null), or null if the key
317 * is not contained in the map.
318 */
319 public Object getValueForKey( Object key )
320 {
321 return keyToValue.get( key );
322 }
323
324 /***
325 * Returns the associated key for this value. Since there may be more than one
326 * of the same value in the map, this returns the first key associated with this
327 * value. Null is returned if the value is not in the map.
328 * @param value A value that is contained in this map.
329 * @return A first key that corresponds to this value.
330 */
331 public Object getKeyForValue( Object value )
332 {
333 int i = values.indexOf( value );
334 if ( i != -1 )
335 {
336 return keys.get( i );
337 }
338 return null;
339 }
340
341 /***
342 * Returns the first key in the map. If the map is empty, then null is
343 * returned.
344 * @return The first key in the map, null if there are no mappings.
345 */
346 public Object getFirstKey()
347 {
348 if ( keys.size() < 1 )
349 {
350 return null;
351 }
352 return keys.get(0);
353 }
354
355 /***
356 * Returns the last key in the map. If the map is empty, then null is
357 * returned.
358 * @return The last key in the map, null if there are no mappings.
359 */
360 public Object getLastKey()
361 {
362 if ( keys.size() < 1 )
363 {
364 return null;
365 }
366 return keys.get( keys.size() -1 );
367 }
368
369 /***
370 * This class contains a key/value pair. The key must be a valid object,
371 * it cannot be null. The value can be a valid object or null.
372 */
373 static public class KeyValuePair implements Map.Entry
374 {
375 Object key;
376 Object value;
377
378 /***
379 * Default constructor. The constructor takes the key and value as parameters.
380 * Since the key cannot be null, it must be specified during initialization.
381 * The value can be null.
382 * @param key The key object of this pair. The key cannot be null.
383 * @param value The value object of this pair. The value can be null.
384 */
385 public KeyValuePair( Object aKey, Object aValue )
386 {
387 key = aKey;
388 value = aValue;
389 }
390
391 /***
392 * Returns the key object of this pair.
393 * @return The key object.
394 */
395 public Object getKey()
396 {
397 return key;
398 }
399
400 /***
401 * Returns the the value object of this pair. May be null.
402 * @return The value object.
403 */
404 public Object getValue()
405 {
406 return value;
407 }
408
409 /***
410 * Sets the value object of this pair. May be an object or null.
411 * @param aValue The value object to place into this pair.
412 */
413 public Object setValue( Object aValue )
414 {
415 Object result = value;
416 value = aValue;
417 return result;
418 }
419
420 public boolean equals( Object o )
421 {
422 if ( o instanceof KeyValuePair )
423 {
424 KeyValuePair p = (KeyValuePair) o;
425 if ( ( key.equals( p.getKey() ) ) && ( value.equals( p.getValue() ) ) )
426 {
427 return true;
428 }
429 }
430 return false;
431 }
432 }
433
434 /***
435 * Returns a string reprsentation of this class. The contents of the
436 * map are placed in the string in its proper order.
437 */
438 public String toString()
439 {
440 int max = size() - 1;
441 StringBuffer buf = new StringBuffer();
442
443 buf.append("{");
444 for (int j = 0; j <= max; j++)
445 {
446 buf.append(keys.get(j) + "=" + values.get(j));
447 if (j < max)
448 {
449 buf.append(", ");
450 }
451 }
452 buf.append("}");
453
454 return buf.toString();
455 }
456
457
458 public static void main( String[] argv )
459 {
460 QueueMap qMap;
461
462 qMap = new QueueMap();
463 for (int i = 0; i < 5; i++)
464 {
465 qMap.put(Integer.toString(i), Integer.toString(i));
466 }
467 System.out.println("\nMap = " + qMap);
468 System.out.println("Keys = " + qMap.keys());
469 System.out.println("Values = " + qMap.values());
470
471 qMap = new QueueMap();
472 for (int i = 0; i < 5; i++)
473 {
474 qMap.put(Integer.toString(i), "A");
475 }
476 System.out.println("\nMap = " + qMap);
477 System.out.println("Keys = " + qMap.keys());
478 System.out.println("Values = " + qMap.values());
479
480 qMap = new QueueMap();
481 for (int i = 0; i < 5; i++)
482 {
483 qMap.put(Integer.toString(i), null);
484 }
485 System.out.println("\nMap = " + qMap);
486 System.out.println("Keys = " + qMap.keys());
487 System.out.println("Values = " + qMap.values());
488
489 Map aMap = new HashMap();
490 for (int i = 0; i < 5; i++)
491 {
492 aMap.put(Integer.toString(i), Integer.toString(i));
493 }
494 qMap = new QueueMap( aMap );
495 System.out.println("\nHashMap = " + aMap);
496 System.out.println("Map = " + qMap);
497 System.out.println("Keys = " + qMap.keys());
498 System.out.println("Values = " + qMap.values());
499
500 qMap = new QueueMap();
501 qMap.put( "Test1", "String1" );
502 qMap.put( "Test2", "String2" );
503 qMap.put( "Test3", "String3" );
504 qMap.put( "Test4", "String4" );
505 qMap.put( "Test5", "String5" );
506 System.out.println("\nStandard Test, Map = " + qMap);
507 qMap.put( "Test6", "String6" );
508 qMap.put( "Test7", "String7" );
509 System.out.println("Put New Test, Map = " + qMap);
510 qMap.put( "Test2", "New String2" );
511 qMap.put( "Test6", "New String6" );
512 System.out.println("Put Existing Test, Map = " + qMap);
513 qMap.put( "Test5", null );
514 qMap.put( "Test8", null );
515 System.out.println("Put Null Test, Map = " + qMap);
516 qMap.remove( "Test1" );
517 qMap.remove( "Test3" );
518 qMap.remove( "Test5" );
519 qMap.remove( "Test9" );
520 System.out.println("Remove Test, Map = " + qMap);
521 System.out.println(" Keys = " + qMap.keys());
522 System.out.println(" Values = " + qMap.values());
523 qMap.clear();
524 qMap.put( "Test10", "String10" );
525 qMap.put( "Test11", "String11" );
526 qMap.put( "Test12", "String12" );
527 System.out.println("Clear Test, Map = " + qMap);
528
529 aMap = new HashMap();
530 aMap.put( "Test10", "String10" );
531 aMap.put( "Test11", "String11" );
532 aMap.put( "Test12", "String12" );
533 System.out.println("Equality Test, Equal = " + qMap.equals( aMap ));
534 }
535
536 }
537
538