Coverage Report

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */
 package javax.faces.component;
 
 import java.util.AbstractMap;
 import java.util.AbstractSet;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
 
 /**
  * A Map implementation that stores its contents in a single
  * array.  This approach is significantly faster for small sets of
  * data than the use of a HashMap or Hashtable, though potentially
  * much slower for very large sets.
  * <p>
  * ArrayMap is optimized for many-reads-few-write.  In particular,
  * it reallocates its array on any insertion or deletion.
  * <p>
  * ArrayMap also includes a series of static methods for managing the
  * Object array. These may be used in place of instantiating an
  * ArrayMap for clients that don't need a Map implementation.
  * Clients using these methods must be careful to store the returned
  * Object array on any mutator method.  They also must provide their
  * own synchronization, if needed.  When using these static methods,
  * clients can opt to search for objects by identity (via
  * <code>getByIdentity()</code>) instead of equality, while the static
  * <code>get()</code> method will try identity before equality.  This
  * latter approach is extremely fast but still safe for retrieval of
  * Strings that have all been interned, especially if misses are
  * infrequent (since misses do require a scan using Object.equals()).
  * It's worth remembering that String constants are always interned,
  * as required by the language specification.
  * <p>
  * @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 $
  */
 // -= Simon Lessard =-
 //        Using a single array for both the key and the value leads to many 
 //        problems, especially with type safety. Using parallel arrays or 
 //        a single array containing nodes would be a much cleaner/safer idea.
 // =-= AdamWiner =-=
 //        True, but the whole point of this class is maximal efficiency for
 //        small, transient arrays.  The type safety problems are entirely internal,
 //        not exposed to clients.  Parallel arrays or arrays containing nodes
 //        would be less efficient - if you're willing to allocate bonus objects,
 //        and don't care about efficiency, just use HashMap.
 class _ArrayMap<K, V> extends AbstractMap<K, V> implements Cloneable
 {
     /**
      * Creates an empty ArrayMap, preallocating nothing.
      */
     public _ArrayMap()
     {
         this(0, 1);
     }
 
     /**
      * Creates an ArrayMap, preallocating for a certain size.
      * @param size the number of elements to pre-allocate for
      */
     public _ArrayMap(int size)
     {
         this(size, 1);
     }
 
     /**
      * Creates an ArrayMap, preallocating for a certain size.
      * @param size the number of elements to pre-allocate for
      * @param increment the number of additional elements to
      *     allocate for when overruning
      */
     public _ArrayMap(int size, int increment)
     {
         if ((increment < 1) || (size < 0))
         {
             throw new IllegalArgumentException();
         }
 
         if (size > 0)
         {
             _array = new Object[2 * size];
         }
 
         _increment = increment;
     }
 
     /**
      * Returns the key at a specific index in the map.
      */
     @SuppressWarnings("unchecked")
     public K getKey(int index)
     {
         if ((index < 0) || (index >= size()))
         {
             throw new IndexOutOfBoundsException();
         }
         return (K) _array[index * 2];
     }
 
     /**
      * Returns the value at a specific index in the map.
      */
     @SuppressWarnings("unchecked")
     public V getValue(int index)
     {
         if ((index < 0) || (index >= size()))
         {
             throw new IndexOutOfBoundsException();
         }
         return (V) _array[index * 2 + 1];
     }
 
     /**
      * Gets the object stored with the given key.  Scans first
      * by object identity, then by object equality.
      */
     static public Object get(Object[] array, Object key)
     {
         Object o = getByIdentity(array, key);
         if (o != null)
         {
             return o;
         }
 
         return getByEquality(array, key);
     }
 
     /**
      * Gets the object stored with the given key, using
      * only object identity.
      */
     static public Object getByIdentity(Object[] array, Object key)
     {
         if (array != null)
         {
             int length = array.length;
             for (int i = 0; i < length; i += 2)
             {
                 if (array[i] == key)
                 {
                     return array[i + 1];
                 }
             }
         }
 
         return null;
     }
 
     /**
      * Gets the object stored with the given key, using
      * only object equality.
      */
     static public Object getByEquality(Object[] array, Object key)
     {
         if (array != null)
         {
             int length = array.length;
 
             for (int i = 0; i < length; i += 2)
             {
                 Object targetKey = array[i];
                 if (targetKey == null)
                 {
                     return null;
                 }
                 else if (targetKey.equals(key))
                 {
                     return array[i + 1];
                 }
             }
         }
 
         return null;
     }
 
     /**
      * Adds the key/value pair to the array, returning a
      * new array if necessary.
      */
     static public Object[] put(Object[] array, Object key, Object value)
     {
         if (array != null)
         {
             int length = array.length;
 
             for (int i = 0; i < length; i += 2)
             {
                 Object curKey = array[i];
 
                 if (((curKey != null) && (curKey.equals(key)))
                         || (curKey == key))
                 {
                     array[i + 1] = value;
                     return array;
                 }
             }
         }
 
         return _addToArray(array, key, value, 1);
     }
 
     /**
      * Removes the value for the key from the array, returning a
      * new array if necessary.
      */
     static public Object[] remove(Object[] array, Object key)
     {
         return remove(array, key, true);
     }
 
     /**
      * Removes the value for the key from the array, returning a
      * new array if necessary.
      */
     static public Object[] remove(Object[] array, Object key, boolean reallocate)
     {
         if (array != null)
         {
             int length = array.length;
 
             for (int i = 0; i < length; i += 2)
             {
                 Object curKey = array[i];
 
                 if (((curKey != null) && curKey.equals(key)) || (curKey == key))
                 {
                     Object[] newArray = array;
 
                     if (reallocate)
                     {
                         newArray = new Object[length - 2];
                         System.arraycopy(array, 0, newArray, 0, i);
                     }
 
                     System.arraycopy(array, i + 2, newArray, i, length - i - 2);
 
                     if (!reallocate)
                     {
                         array[length - 1] = null;
                         array[length - 2] = null;
                     }
 
                     return newArray;
                 }
             }
         }
 
         return array;
     }
 
     //
     // GENERIC MAP API
     //
     @Override
     public int size()
     {
         return _size;
     }
 
     @Override
     public boolean containsValue(Object value)
     {
         int entryCount = size() * 2;
         for (int i = 0; i < entryCount; i += 2)
         {
             if (_equals(value, _array[i + 1]))
             {
                 return true;
             }
         }
 
         return false;
     }
 
     @Override
     public boolean containsKey(Object key)
     {
         int entryCount = size() * 2;
         for (int i = 0; i < entryCount; i += 2)
         {
             if (_equals(key, _array[i]))
             {
                 return true;
             }
         }
 
         return false;
     }
 
     /**
      * Returns an enumeration of the keys in this map.
      * the Iterator methods on the returned object to fetch the elements
      * sequentially.
      */
     @SuppressWarnings("unchecked")
     public Iterator<K> keys()
     {
         int size = _size;
 
         if (size == 0)
         {
             return null;
         }
         ArrayList<K> keyList = new ArrayList<K>();
         int i = (size - 1) * 2;
         while (i >= 0)
         {
             keyList.add((K) _array[i]);
             i = i - 2;
         }
         return keyList.iterator();
     }
 
     /**
      * Returns an Iterator of keys in the array.
      */
     public static Iterator<Object> getKeys(Object[] array)
     {
         if (array == null)
         {
             return null;
         }
         ArrayList<Object> keyList = new ArrayList<Object>();
         int i = array.length - 2;
         while (i >= 0)
         {
             keyList.add(array[i]);
             i = i - 2;
         }
         return keyList.iterator();
     }
 
     /**
      * Returns an Iterator of values in the array.
      */
     public static Iterator<Object> getValues(Object[] array)
     {
         if (array == null)
         {
             return null;
         }
         ArrayList<Object> valueList = new ArrayList<Object>();
         int i = array.length - 1;
         while (i >= 0)
         {
             valueList.add(array[i]);
             i = i - 2;
         }
         return valueList.iterator();
     }
 
     /**
      * Clones the map.
      */
     @SuppressWarnings("unchecked")
     @Override
     public Object clone()
     {
         try
         {
             _ArrayMap<K, V> am = (_ArrayMap<K, V>) super.clone();
 
             am._array = _array.clone();
             am._size = _size;
             am._increment = _increment;
             return am;
         }
         catch (CloneNotSupportedException cnse)
         {
             // Should never reach here
             return null;
         }
     }
 
     @Override
     public Set<Map.Entry<K, V>> entrySet()
     {
         if (_entrySet == null)
         {
             _entrySet = new AbstractSet<Map.Entry<K, V>>()
             {
                 @Override
                 public int size()
                 {
                     return _ArrayMap.this.size();
                 }
 
                 @Override
                 public Iterator<Map.Entry<K, V>> iterator()
                 {
                     return new Iterator<Map.Entry<K, V>>()
                     {
                         public boolean hasNext()
                         {
                             return (_index < _ArrayMap.this.size());
                         }
 
                         public void remove()
                         {
                             // remove() removes the last entry returned by next(),
                             // not the one about to be seen;  so that's actually
                             // the entry at (_index - 1).
                             if ((_index == 0) || _removed)
                             {
                                 throw new IllegalStateException();
                             }
 
                             _removed = true;
                             // Shrink the array by one
                             int size = _ArrayMap.this.size();
                             Object[] array = _ArrayMap.this._array;
                             if (size > _index)
                             {
                                 System.arraycopy(array, _index * 2, array,
                                         (_index - 1) * 2, (size - _index) * 2);
                             }
 
                             // Null out the last elements (for GC)
                             array[size * 2 - 2] = null;
                             array[size * 2 - 1] = null;
 
                             _ArrayMap.this._size = size - 1;
 
                             // And push the index back one
                             _index = _index - 1;
                         }
 
                         public Map.Entry<K, V> next()
                         {
                             if (!hasNext())
                             {
                                 throw new NoSuchElementException();
                             }
 
                             final int index = _index;
                             _removed = false;
                             _index = index + 1;
 
                             return new Map.Entry<K, V>()
                             {
                                 public K getKey()
                                 {
                                     return _ArrayMap.this.getKey(index);
                                 }
 
                                 public V getValue()
                                 {
                                     return _ArrayMap.this.getValue(index);
                                 }
 
                                 public V setValue(V value)
                                 {
                                     V oldValue = getValue();
                                     _ArrayMap.this._array[index * 2 + 1] = value;
                                     return oldValue;
                                 }
 
                                 @SuppressWarnings("unchecked")
                                 @Override
                                 public boolean equals(Object o)
                                 {
                                     if (!(o instanceof Map.Entry))
                                     {
                                         return false;
                                     }
                                     Map.Entry<K, V> e = (Map.Entry<K, V>) o;
                                     return _equals(getKey(), e.getKey())
                                             && _equals(getValue(), e.getValue());
                                 }
 
                                 @Override
                                 public int hashCode()
                                 {
                                     Object key = getKey();
                                     Object value = getValue();
                                     return ((key == null) ? 0 : key.hashCode())
                                             ^ ((value == null) ? 0 : value
                                                     .hashCode());
                                 }
                             };
                         }
 
                         private int _index;
                         private boolean _removed;
                     };
                 }
             };
         }
 
         return _entrySet;
     }
 
     @SuppressWarnings("unchecked")
     @Override
     public V get(Object key)
     {
         return (V) getByEquality(_array, key);
         //return getByIdentity(_array, key);
     }
 
     @SuppressWarnings("unchecked")
     public V getByIdentity(Object key)
     {
         return (V) getByIdentity(_array, key);
     }
 
     @SuppressWarnings("unchecked")
     @Override
     public V put(K key, V value)
     {
         if (value == null)
         {
             return remove(key);
         }
 
         Object[] array = _array;
         // Use getByEquality().  In the vast majority
         // of cases, the object isn't there.  So getByIdentity()
         // will fail, and we'll call getByEquality() anyway.
         Object o = getByEquality(array, key);
 
         if (o == null)
         {
             int size = _size * 2;
             if ((array != null) && (size < array.length))
             {
                 array[size] = key;
                 array[size + 1] = value;
             }
             else
             {
                 _array = _addToArray(array, key, value, _increment);
             }
 
             _size = _size + 1;
         }
         else
         {
             // (Actually, I know in this case that the returned array
             // isn't going to change, but that'd be a good way to introduce
             // a bug if we ever to change the implementation)
             _array = put(array, key, value);
         }
 
         return (V) o;
     }
 
     @SuppressWarnings("unchecked")
     @Override
     public V remove(Object key)
     {
         Object[] array = _array;
         Object o = get(array, key);
         if (o != null)
         {
             remove(array, key, false);
             _size = _size - 1;
         }
 
         return (V) o;
     }
 
     /**
      * Removes all elements from the ArrayMap.
      */
     @Override
     public void clear()
     {
         int size = _size;
         if (size > 0)
         {
             size = size * 2;
             for (int i = 0; i < size; i++)
             {
                 _array[i] = null;
             }
 
             _size = 0;
         }
     }
 
     /**
      * Adds the key/value pair to the array, returning a
      * new array if necessary.
      */
     private static Object[] _addToArray(Object[] array, Object key,
             Object value, int increment)
     {
         Object[] newArray = null;
         if (array != null)
         {
             int length = array.length;
             newArray = new Object[length + (2 * increment)];
             System.arraycopy(array, 0, newArray, 2, length);
         }
         else
         {
             newArray = new Object[2 * increment];
         }
 
         newArray[0] = key;
         newArray[1] = value;
         return newArray;
     }
 
     private static boolean _equals(Object a, Object b)
     {
         if (a == null)
         {
             return b == null;
         }
         return a.equals(b);
     }
 
     private Object[] _array;
     private int _size;
     private int _increment;
     private Set<Map.Entry<K, V>> _entrySet;
 }

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