# SmallMap.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 org.apache.pdfbox.util;

    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.LinkedHashSet;
    import java.util.List;
    import java.util.Map;
    import java.util.Set;

    /**
     * Map implementation with a smallest possible memory usage.
     * It should only be used for maps with small number of items
     * (e.g. &lt;30) since most operations have an O(n) complexity.
     * Thus it should be used in cases with large number of map
     * objects, each having only few items.
     *
     * <p><code>null</code> is not supported for keys or values.</p>
     */
    public class SmallMap<K, V> implements Map<K, V>
    {
        /**
         * stores key-value pair as 2 objects; key first; in case of empty map this might be <code>null</code>
         */
        private Object[] mapArr;

        /** Creates empty map. */
        public SmallMap()
        {
        }

        /** Creates map filled with entries from provided map. */
        public SmallMap(Map<? extends K, ? extends V> initMap)
        {
            putAll(initMap);
        }

        /**
         * Returns index of key within map-array or <code>-1</code>
         * if key is not found (or key is <code>null</code>).
         */
        private int findKey(Object key)
        {
            if (isEmpty() || (key==null))
            {
                return -1;
            }

            for ( int aIdx = 0; aIdx < mapArr.length; aIdx+=2 )
            {
                if (key.equals(mapArr[aIdx]))
                {
                    return aIdx;
                }
            }

            return -1;
        }

        /**
         * Returns index of value within map-array or <code>-1</code>
         * if value is not found (or value is <code>null</code>).
         */
        private int findValue(Object value)
        {
            if (isEmpty() || (value==null))
            {
                return -1;
            }

            for ( int aIdx = 1; aIdx < mapArr.length; aIdx+=2 )
            {
                if (value.equals(mapArr[aIdx]))
                {
                    return aIdx;
                }
            }

            return -1;
        }

        @Override
        public int size()
        {
            return mapArr == null ? 0 : mapArr.length >> 1;
        }

        @Override
        public boolean isEmpty()
        {
            return (mapArr == null) || (mapArr.length == 0);
        }

        @Override
        public boolean containsKey(Object key)
        {
            return findKey(key) >= 0;
        }

        @Override
        public boolean containsValue(Object value)
        {
            return findValue(value) >= 0;
        }

        @SuppressWarnings("unchecked")
        @Override
        public V get(Object key)
        {
            int kIdx = findKey(key);

            return kIdx < 0 ? null : (V) mapArr[kIdx+1];
        }

        @Override
        public V put(K key, V value)
        {
            if ((key == null) || (value == null))
            {
                throw new NullPointerException( "Key or value must not be null.");
            }

            if (mapArr == null)
            {
                mapArr = new Object[] { key, value };
                return null;
            }
            else
            {
                int kIdx = findKey(key);

                if (kIdx < 0)
                {
                    // key unknown
                    int oldLen = mapArr.length;
                    Object[] newMapArr = new Object[oldLen+2];
                    System.arraycopy(mapArr, 0, newMapArr, 0, oldLen);
                    newMapArr[oldLen] = key;
                    newMapArr[oldLen+1] = value;
                    mapArr = newMapArr;
                    return null;
                }
                else
                {
                    // key exists; replace value
                    @SuppressWarnings("unchecked")
                    V oldValue = (V) mapArr[kIdx+1];
                    mapArr[kIdx+1] = value;
                    return oldValue;
                }
            }
        }

        @Override
        public V remove(Object key)
        {
            int kIdx = findKey(key);

            if (kIdx < 0)
            {
                // not found
                return null;
            }

            @SuppressWarnings("unchecked")
            V oldValue = (V) mapArr[kIdx+1];
            int oldLen = mapArr.length;

            if (oldLen == 2)
            {
                // was last entry
                mapArr = null;
            }
            else
            {
                Object[] newMapArr = new Object[oldLen-2];
                System.arraycopy(mapArr, 0, newMapArr, 0, kIdx);
                System.arraycopy(mapArr, kIdx+2, newMapArr, kIdx, oldLen - kIdx - 2);
                mapArr = newMapArr;
            }

            return oldValue;
        }

        @Override
        public final void putAll(Map<? extends K, ? extends V> otherMap)
        {
            if ((mapArr == null) || (mapArr.length == 0))
            {
                // existing map is empty
                mapArr = new Object[otherMap.size() << 1];
                int aIdx = 0;
                for (Entry<? extends K, ? extends V> entry : otherMap.entrySet())
                {
                    if ((entry.getKey() == null) || (entry.getValue() == null))
                    {
                        throw new NullPointerException( "Key or value must not be null.");
                    }

                    mapArr[aIdx++] = entry.getKey();
                    mapArr[aIdx++] = entry.getValue();
                }
            }
            else
            {
                int oldLen = mapArr.length;
                // first increase array size to hold all to put entries as if they have unknown keys
                // reduce after adding all to the required size
                Object[] newMapArr = new Object[oldLen+(otherMap.size() << 1)];
                System.arraycopy(mapArr, 0, newMapArr, 0, oldLen);

                int newIdx = oldLen;
                for (Entry<? extends K, ? extends V> entry : otherMap.entrySet())
                {
                    if ((entry.getKey() == null) || (entry.getValue() == null))
                    {
                        throw new NullPointerException( "Key or value must not be null.");
                    }

                    int existKeyIdx = findKey(entry.getKey());

                    if (existKeyIdx >= 0)
                    {
                        // existing key
                        newMapArr[existKeyIdx+1] = entry.getValue();
                    }
                    else
                    {
                        // new key
                        newMapArr[newIdx++] = entry.getKey();
                        newMapArr[newIdx++] = entry.getValue();
                    }
                }

                if (newIdx < newMapArr.length)
                {
                    Object[] reducedMapArr = new Object[newIdx];
                    System.arraycopy(newMapArr, 0, reducedMapArr, 0, newIdx);
                    newMapArr = reducedMapArr;
                }

                mapArr = newMapArr;
            }
        }

        @Override
        public void clear()
        {
            mapArr = null;
        }

        /**
         * Returns a set view of the keys contained in this map.
         *
         * <p>The current implementation does not allow changes to the
         * returned key set (which would have to be reflected in the
         * underlying map.</p>
         */
        @SuppressWarnings("unchecked")
        @Override
        public Set<K> keySet()
        {
            if (isEmpty())
            {
                return Collections.emptySet();
            }

            Set<K> keys = new LinkedHashSet<>();
            for (int kIdx = 0; kIdx < mapArr.length; kIdx+=2)
            {
                keys.add((K)mapArr[kIdx]);
            }
            return Collections.unmodifiableSet( keys );
        }

        /**
         * Returns a collection of the values contained in this map.
         *
         * <p>The current implementation does not allow changes to the
         * returned collection (which would have to be reflected in the
         * underlying map.</p>
         */
        @SuppressWarnings("unchecked")
        @Override
        public Collection<V> values()
        {
            if (isEmpty())
            {
                return Collections.emptySet();
            }

            List<V> values = new ArrayList<>(mapArr.length >> 1);
            for (int vIdx = 1; vIdx < mapArr.length; vIdx+=2)
            {
                values.add((V)mapArr[vIdx]);
            }
            return Collections.unmodifiableList( values );
        }

        private class SmallMapEntry implements Entry<K, V>
        {
            private final int keyIdx;

            SmallMapEntry(int keyInMapIdx)
            {
                keyIdx = keyInMapIdx;
            }

            @SuppressWarnings("unchecked")
            @Override
            public K getKey()
            {
                return (K)mapArr[keyIdx];
            }

            @SuppressWarnings("unchecked")
            @Override
            public V getValue()
            {
                return (V)mapArr[keyIdx+1];
            }

            @Override
            public V setValue(V value)
            {
                if (value == null)
                {
                    throw new NullPointerException( "Key or value must not be null.");
                }

                V oldValue = getValue();
                mapArr[keyIdx+1] = value;
                return oldValue;
            }

            @Override
            public int hashCode()
            {
                return getKey().hashCode();
            }

            @Override
            public boolean equals(Object obj)
            {
                if (!(obj instanceof SmallMap.SmallMapEntry))
                {
                    return false;
                }
                @SuppressWarnings("unchecked")
                SmallMapEntry other = (SmallMapEntry) obj;

                return getKey().equals(other.getKey()) && getValue().equals(other.getValue());
            }
        }

        @Override
        public Set<java.util.Map.Entry<K, V>> entrySet()
        {
            if (isEmpty())
            {
                return Collections.emptySet();
            }

            Set<java.util.Map.Entry<K, V>> entries = new LinkedHashSet<>();
            for (int kIdx = 0; kIdx < mapArr.length; kIdx+=2)
            {
                entries.add(new SmallMapEntry(kIdx));
            }
            return Collections.unmodifiableSet( entries );
        }

    }