api/src/main/java/javax/faces/component/_ArrayMap.java

/*
 * 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;
}