View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.myfaces.trinidad.util;
20  
21  import java.util.AbstractMap;
22  import java.util.AbstractSet;
23  import java.util.ArrayList;
24  import java.util.Iterator;
25  import java.util.Map;
26  import java.util.NoSuchElementException;
27  import java.util.Set;
28  
29  
30  
31  /**
32   * A Map implementation that stores its contents in a single
33   * array.  This approach is significantly faster for small sets of
34   * data than the use of a HashMap or Hashtable, though potentially
35   * much slower for very large sets.
36   * <p>
37   * ArrayMap is optimized for many-reads-few-write.  In particular,
38   * it reallocates its array on any insertion or deletion.
39   * <p>
40   * ArrayMap also includes a series of static methods for managing the
41   * Object array. These may be used in place of instantiating an
42   * ArrayMap for clients that don't need a Map implementation.
43   * Clients using these methods must be careful to store the returned
44   * Object array on any mutator method.  They also must provide their
45   * own synchronization, if needed.  When using these static methods,
46   * clients can opt to search for objects by identity (via
47   * <code>getByIdentity()</code>) instead of equality, while the static
48   * <code>get()</code> method will try identity before equality.  This
49   * latter approach is extremely fast but still safe for retrieval of
50   * Strings that have all been interned, especially if misses are
51   * infrequent (since misses do require a scan using Object.equals()).
52   * It's worth remembering that String constants are always interned,
53   * as required by the language specification.
54   * <p>
55   * @version $Name:  $ ($Revision: adfrt/faces/adf-faces-api/src/main/java/oracle/adf/view/faces/util/ArrayMap.java#0 $) $Date: 10-nov-2005.19:08:36 $
56   */
57  // -= Simon Lessard =-
58  //        Using a single array for both the key and the value leads to many 
59  //        problems, especially with type safety. Using parallel arrays or 
60  //        a single array containing nodes would be a much cleaner/safer idea.
61  // =-= AdamWiner =-=
62  //        True, but the whole point of this class is maximal efficiency for
63  //        small, transient arrays.  The type safety problems are entirely internal,
64  //        not exposed to clients.  Parallel arrays or arrays containing nodes
65  //        would be less efficient - if you're willing to allocate bonus objects,
66  //        and don't care about efficiency, just use HashMap.
67  public class ArrayMap<K,V> extends AbstractMap<K,V> implements Cloneable
68  {
69    /**
70     * Creates an empty ArrayMap, preallocating nothing.
71     */
72    public ArrayMap()
73    {
74      this(0, 1);
75    }
76  
77    /**
78     * Creates an ArrayMap, preallocating for a certain size.
79     * @param size the number of elements to pre-allocate for
80     */
81    public ArrayMap(int size)
82    {
83      this(size, 1);
84    }
85  
86    /**
87     * Creates an ArrayMap, preallocating for a certain size.
88     * @param size the number of elements to pre-allocate for
89     * @param increment the number of additional elements to
90     *     allocate for when overruning
91     */
92    public ArrayMap(int size, int increment)
93    {    if ((increment < 1) || (size < 0))
94        throw new IllegalArgumentException();
95  
96      if (size > 0)
97        _array = new Object[2 * size];
98  
99      _increment = increment;
100   }
101 
102   /**
103    * Returns the key at a specific index in the map.
104    */
105   @SuppressWarnings("unchecked")
106   public K getKey(int index)
107   {
108     if ((index < 0) || (index >= size()))
109       throw new IndexOutOfBoundsException();
110     return (K) _array[index * 2];
111   }
112 
113 
114   /**
115    * Returns the value at a specific index in the map.
116    */
117   @SuppressWarnings("unchecked")
118   public V getValue(int index)
119   {
120     if ((index < 0) || (index >= size()))
121       throw new IndexOutOfBoundsException();
122     return (V) _array[index * 2 + 1];
123   }
124 
125   /**
126    * Gets the object stored with the given key.  Scans first
127    * by object identity, then by object equality.
128    */
129   static public Object get(Object[] array, Object key)
130   {
131     Object o = getByIdentity(array, key);
132     if (o != null)
133       return o;
134 
135     return getByEquality(array, key);
136   }
137 
138 
139   /**
140    * Gets the object stored with the given key, using
141    * only object identity.
142    */
143   static public Object getByIdentity(Object[] array, Object key)
144   {
145     if (array != null)
146     {
147       int length = array.length;
148       for (int i = 0; i < length; i += 2)
149       {
150         if (array[i] == key)
151           return array[i + 1];
152       }
153     }
154 
155     return null;
156   }
157 
158 
159   /**
160    * Gets the object stored with the given key, using
161    * only object equality.
162    */
163   static public Object getByEquality(Object[] array, Object key)
164   {
165     if (array != null)
166     {
167       int length = array.length;
168 
169       for (int i = 0; i < length; i += 2)
170       {
171         Object targetKey = array[i];
172         if (targetKey == null)
173           return null;
174         else if (targetKey.equals(key))
175           return array[i + 1];
176       }
177     }
178 
179     return null;
180   }
181 
182 
183 
184   /**
185    * Adds the key/value pair to the array, returning a
186    * new array if necessary.
187    */
188   static public Object[] put(Object[] array, Object key, Object value)
189   {
190     if (array != null)
191     {
192       int length = array.length;
193 
194       for (int i = 0; i < length; i+=2)
195       {
196         Object curKey = array[i];
197 
198         if (((curKey != null) && (curKey.equals(key))) || (curKey == key))
199         {
200           array[i + 1] = value;
201           return array;
202         }
203       }
204     }
205 
206     return _addToArray(array, key, value, 1);
207   }
208 
209 
210   /**
211    * Removes the value for the key from the array, returning a
212    * new array if necessary.
213    */
214   static public Object[] remove(Object[] array, Object key)
215   {
216     return remove(array, key, true);
217   }
218 
219 
220   /**
221    * Removes the value for the key from the array, returning a
222    * new array if necessary.
223    */
224   static public Object[] remove(Object[] array, Object key,
225                                 boolean reallocate)
226   {
227     if (array != null)
228     {
229       int length = array.length;
230 
231       for (int i = 0; i < length; i+=2)
232       {
233         Object curKey = array[i];
234 
235         if (((curKey != null) && curKey.equals(key)) || (curKey == key))
236         {
237           Object[] newArray = array;
238 
239           if (reallocate)
240           {
241             newArray = new Object[length - 2];
242             System.arraycopy(array, 0, newArray, 0, i);
243           }
244 
245           System.arraycopy(array, i + 2, newArray, i, length - i - 2);
246 
247           if (!reallocate)
248           {
249             array[length - 1] = null;
250             array[length - 2] = null;
251           }
252 
253           return newArray;
254         }
255       }
256     }
257 
258     return array;
259   }
260 
261   //
262   // GENERIC MAP API
263   //
264   @Override
265   public int size()
266   {
267     return _size;
268   }
269 
270   @Override
271   public boolean containsValue(Object value)
272   {
273     int entryCount = size() * 2;
274     for (int i = 0; i < entryCount; i += 2)
275     {
276       if (_equals(value, _array[i + 1]))
277         return true;
278     }
279 
280     return false;
281   }
282 
283 
284   @Override
285   public boolean containsKey(Object key)
286   {
287     int entryCount = size() * 2;
288     for (int i = 0; i < entryCount; i += 2)
289     {
290       if (_equals(key, _array[i]))
291         return true;
292     }
293 
294     return false;
295   }
296 
297   /**
298    * Returns an enumeration of the keys in this map.
299    * the Iterator methods on the returned object to fetch the elements
300    * sequentially.
301    */
302   @SuppressWarnings("unchecked")
303   public Iterator<K> keys()
304   {
305     int size = _size;
306 
307     if (size == 0)
308       return null;
309       ArrayList<K> keyList = new ArrayList<K>();
310       int i = (size-1)*2;
311       while(i>=0)
312       {
313         keyList.add((K) _array[i]);
314         i=i-2;
315       }
316       return keyList.iterator();
317   }
318 
319   /**
320    * Returns an Iterator of keys in the array.
321    */
322   public static Iterator<Object> getKeys(Object[] array)
323   {
324     if (array == null)
325       return null;
326       ArrayList<Object> keyList = new ArrayList<Object>();
327       int i = array.length-2;
328       while(i>=0)
329       {
330         keyList.add(array[i]);
331         i=i-2;
332       }
333       return keyList.iterator();
334   }
335 
336 
337   /**
338    * Returns an Iterator of values in the array.
339    */
340   public static Iterator<Object> getValues(Object[] array)
341   {
342     if (array == null)
343       return null;
344       ArrayList<Object> valueList = new ArrayList<Object>();
345       int i = array.length-1;
346       while(i>=0)
347       {
348         valueList.add(array[i]);
349         i=i-2;
350       }
351       return valueList.iterator();
352   }
353 
354 
355   /**
356    * Clones the map.
357    */
358   @SuppressWarnings("unchecked")
359   @Override
360   public Object clone()
361   {
362     try
363     {
364       ArrayMap<K, V> am = (ArrayMap<K, V>) super.clone();
365 
366       am._array     = _array.clone();
367       am._size      = _size;
368       am._increment = _increment;
369       return am;
370     }
371     catch (CloneNotSupportedException cnse)
372     {
373       // Should never reach here
374       return null;
375     }
376   }
377 
378   @Override
379   public Set<Map.Entry<K,V>> entrySet()
380   {
381     if (_entrySet == null)
382     {
383       _entrySet = new AbstractSet<Map.Entry<K,V>>()
384       {
385         @Override
386         public int size()
387         {
388           return ArrayMap.this.size();
389         }
390 
391         @Override
392         public Iterator<Map.Entry<K,V>> iterator()
393         {
394           return new Iterator<Map.Entry<K,V>>()
395           {
396             public boolean hasNext()
397             {
398               return (_index < ArrayMap.this.size());
399             }
400 
401             public void remove()
402             {
403               // remove() removes the last entry returned by next(),
404               // not the one about to be seen;  so that's actually
405               // the entry at (_index - 1).
406               if ((_index == 0) || _removed)
407                 throw new IllegalStateException();
408 
409               _removed = true;
410               // Shrink the array by one
411               int size = ArrayMap.this.size();
412               Object[] array = ArrayMap.this._array;
413               if (size > _index)
414               {
415                 System.arraycopy(array,
416                                  _index * 2,
417                                  array,
418                                  (_index - 1) * 2,
419                                  (size - _index) * 2);
420               }
421 
422               // Null out the last elements (for GC)
423               array[size * 2 - 2] = null;
424               array[size * 2 - 1] = null;
425 
426               ArrayMap.this._size = size - 1;
427 
428               // And push the index back one
429               _index = _index - 1;
430             }
431 
432             public Map.Entry<K,V> next()
433             {
434               if (!hasNext())
435                 throw new NoSuchElementException();
436 
437               final int index = _index;
438               _removed = false;
439               _index = index + 1;
440 
441               return new Map.Entry<K,V>()
442               {
443                 public K getKey()
444                 {
445                   return ArrayMap.this.getKey(index);
446                 }
447 
448                 public V getValue()
449                 {
450                   return ArrayMap.this.getValue(index);
451                 }
452 
453                 public V setValue(V value)
454                 {
455                   V oldValue = getValue();
456                   ArrayMap.this._array[index * 2 + 1] = value;
457                   return oldValue;
458                 }
459 
460                 @SuppressWarnings("unchecked")
461                 @Override
462                 public boolean equals(Object o)
463                 {
464                   if (!(o instanceof Map.Entry))
465                     return false;
466                   Map.Entry<K,V> e = (Map.Entry<K,V>)o;
467                   return _equals(getKey(), e.getKey()) &&
468                          _equals(getValue(), e.getValue());
469                 }
470 
471                 @Override
472                 public int hashCode()
473                 {
474                   Object key = getKey();
475                   Object value = getValue();
476                   return ((key   == null)   ? 0 :   key.hashCode()) ^
477                          ((value == null)   ? 0 : value.hashCode());
478                 }
479               };
480             }
481 
482 
483             private int _index;
484             private boolean _removed;
485           };
486         }
487       };
488     }
489 
490     return _entrySet;
491   }
492 
493   @SuppressWarnings("unchecked")
494   @Override
495   public V get(Object key)
496   {
497     return (V) getByEquality(_array, key);
498     //return getByIdentity(_array, key);
499   }
500 
501   @SuppressWarnings("unchecked")
502   public V getByIdentity(Object key)
503   {
504     return (V) getByIdentity(_array, key);
505   }
506 
507   @SuppressWarnings("unchecked")
508   @Override
509   public V put(K key, V value)
510   {
511     if (value == null)
512       return remove(key);
513 
514     Object[] array = _array;
515     // Use getByEquality().  In the vast majority
516     // of cases, the object isn't there.  So getByIdentity()
517     // will fail, and we'll call getByEquality() anyway.
518     Object o = getByEquality(array, key);
519 
520     if (o == null)
521     {
522       int size = _size * 2;
523       if ((array != null) && (size < array.length))
524       {
525         array[size]     = key;
526         array[size + 1] = value;
527       }
528       else
529       {
530         _array = _addToArray(array, key, value, _increment);
531       }
532 
533       _size = _size + 1;
534     }
535     else
536     {
537       // (Actually, I know in this case that the returned array
538       // isn't going to change, but that'd be a good way to introduce
539       // a bug if we ever to change the implementation)
540       _array = put(array, key, value);
541     }
542 
543     return (V) o;
544   }
545 
546   @SuppressWarnings("unchecked")
547   @Override
548   public V remove(Object key)
549   {
550     Object[] array = _array;
551     Object o = get(array, key);
552     if (o != null)
553     {
554       remove(array, key, false);
555       _size = _size - 1;
556     }
557 
558     return (V) o;
559   }
560 
561 
562   /**
563    * Removes all elements from the ArrayMap.
564    */
565   @Override
566   public void clear()
567   {
568     int size = _size;
569     if (size > 0)
570     {
571       size = size * 2;
572       for (int i = 0; i < size; i++)
573         _array[i] = null;
574 
575       _size = 0;
576     }
577   }
578 
579 
580   /**
581    * Adds the key/value pair to the array, returning a
582    * new array if necessary.
583    */
584   private static Object[] _addToArray(Object[] array,
585                                       Object key,
586                                       Object value,
587                                       int    increment)
588   {
589     Object[] newArray = null;
590     if (array != null)
591     {
592       int length = array.length;
593       newArray = new Object[length + (2 * increment)];
594       System.arraycopy(array, 0, newArray, 2, length);
595     }
596     else
597     {
598       newArray = new Object[2 * increment];
599     }
600 
601     newArray[0] = key;
602     newArray[1] = value;
603     return newArray;
604   }
605 
606   private static boolean _equals(Object a, Object b)
607   {
608     if (a == null)
609       return b == null;
610     return a.equals(b);
611   }
612 
613 
614   private Object[] _array;
615   private int      _size;
616   private int      _increment;
617   private Set<Map.Entry<K,V>> _entrySet;
618 }