    001    // Copyright 2007 The Apache Software Foundation
    002    //
    003    // Licensed under the Apache License, Version 2.0 (the "License");
    004    // you may not use this file except in compliance with the License.
    005    // You may obtain a copy of the License at
    006    //
    007    //     http://www.apache.org/licenses/LICENSE-2.0
    008    //
    009    // Unless required by applicable law or agreed to in writing, software
    010    // distributed under the License is distributed on an "AS IS" BASIS,
    011    // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    012    // See the License for the specific language governing permissions and
    013    // limitations under the License.
    014
    015    package org.apache.tapestry5.ioc.util;
    016
    017    import java.io.Serializable;
    018    import java.util.*;
    019
    020    /**
    021     * An mapped collection where the keys are always strings and access to values is case-insensitive. The case of keys in
    022     * the map is <em>maintained</em>, but on any access to a key (directly or indirectly), all key comparisons are
    023     * performed in a case-insensitive manner. The map implementation is intended to support a reasonably finite number
    024     * (dozens or hundreds, not thousands or millions of key/value pairs. Unlike HashMap, it is based on a sorted list of
    025     * entries rather than hash bucket. It is also geared towards a largely static map, one that is created and then used
    026     * without modification.
    027     *
    028     * @param <V> the type of value stored
    029     */
    030    public class CaseInsensitiveMap<V> extends AbstractMap<String, V> implements Serializable
    031    {
    032        private static final long serialVersionUID = 3362718337611953298L;
    033
    034        private static final int NULL_HASH = Integer.MIN_VALUE;
    035
    036        private static final int DEFAULT_SIZE = 20;
    037
    038        private static class CIMEntry<V> implements Map.Entry<String, V>, Serializable
    039        {
    040            private static final long serialVersionUID = 6713986085221148350L;
    041
    042            private String key;
    043
    044            private final int hashCode;
    045
    046            V value;
    047
    048            public CIMEntry(final String key, final int hashCode, V value)
    049            {
    050                this.key = key;
    051                this.hashCode = hashCode;
    052                this.value = value;
    053            }
    054
    055            public String getKey()
    056            {
    057                return key;
    058            }
    059
    060            public V getValue()
    061            {
    062                return value;
    063            }
    064
    065            public V setValue(V value)
    066            {
    067                V result = this.value;
    068
    069                this.value = value;
    070
    071                return result;
    072            }
    073
    074            /**
    075             * Returns true if both keys are null, or if the provided key is the same as, or case-insensitively equal to,
    076             * the entrie's key.
    077             *
    078             * @param key to compare against
    079             * @return true if equal
    080             */
    081            @SuppressWarnings({ "StringEquality" })
    082            boolean matches(String key)
    083            {
    084                return key == this.key || (key != null && key.equalsIgnoreCase(this.key));
    085            }
    086
    087            boolean valueMatches(Object value)
    088            {
    089                return value == this.value || (value != null && value.equals(this.value));
    090            }
    091        }
    092
    093        private class EntrySetIterator implements Iterator
    094        {
    095            int expectedModCount = modCount;
    096
    097            int index;
    098
    099            int current = -1;
    100
    101            public boolean hasNext()
    102            {
    103                return index < size;
    104            }
    105
    106            public Object next()
    107            {
    108                check();
    109
    110                if (index >= size) throw new NoSuchElementException();
    111
    112                current = index++;
    113
    114                return entries[current];
    115            }
    116
    117            public void remove()
    118            {
    119                check();
    120
    121                if (current < 0) throw new NoSuchElementException();
    122
    123                new Position(current, true).remove();
    124
    125                expectedModCount = modCount;
    126            }
    127
    128            private void check()
    129            {
    130                if (expectedModCount != modCount) throw new ConcurrentModificationException();
    131            }
    132        }
    133
    134        @SuppressWarnings("unchecked")
    135        private class EntrySet extends AbstractSet
    136        {
    137            @Override
    138            public Iterator iterator()
    139            {
    140                return new EntrySetIterator();
    141            }
    142
    143            @Override
    144            public int size()
    145            {
    146                return size;
    147            }
    148
    149            @Override
    150            public void clear()
    151            {
    152                CaseInsensitiveMap.this.clear();
    153            }
    154
    155            @Override
    156            public boolean contains(Object o)
    157            {
    158                if (!(o instanceof Map.Entry)) return false;
    159
    160                Map.Entry e = (Map.Entry) o;
    161
    162                Position position = select(e.getKey());
    163
    164                return position.isFound() && position.entry().valueMatches(e.getValue());
    165            }
    166
    167            @Override
    168            public boolean remove(Object o)
    169            {
    170                if (!(o instanceof Map.Entry)) return false;
    171
    172                Map.Entry e = (Map.Entry) o;
    173
    174                Position position = select(e.getKey());
    175
    176                if (position.isFound() && position.entry().valueMatches(e.getValue()))
    177                {
    178                    position.remove();
    179                    return true;
    180                }
    181
    182                return false;
    183            }
    184
    185        }
    186
    187        private class Position
    188        {
    189            private final int cursor;
    190
    191            private final boolean found;
    192
    193            Position(int cursor, boolean found)
    194            {
    195                this.cursor = cursor;
    196                this.found = found;
    197            }
    198
    199            boolean isFound()
    200            {
    201                return found;
    202            }
    203
    204            CIMEntry<V> entry()
    205            {
    206                return entries[cursor];
    207            }
    208
    209            V get()
    210            {
    211                return found ? entries[cursor].value : null;
    212            }
    213
    214            V remove()
    215            {
    216                if (!found) return null;
    217
    218                V result = entries[cursor].value;
    219
    220                // Remove the entry by shifting everything else down.
    221
    222                System.arraycopy(entries, cursor + 1, entries, cursor, size - cursor - 1);
    223
    224                // We shifted down, leaving one (now duplicate) entry behind.
    225
    226                entries[--size] = null;
    227
    228                // A structural change for sure
    229
    230                modCount++;
    231
    232                return result;
    233            }
    234
    235            @SuppressWarnings("unchecked")
    236            V put(String key, int hashCode, V newValue)
    237            {
    238                if (found)
    239                {
    240                    CIMEntry<V> e = entries[cursor];
    241
    242                    V result = e.value;
    243
    244                    // Not a structural change, so no change to modCount
    245
    246                    // Update the key (to maintain case). By definition, the hash code
    247                    // will not change.
    248
    249                    e.key = key;
    250                    e.value = newValue;
    251
    252                    return result;
    253                }
    254
    255                // Not found, we're going to add it.
    256
    257                int newSize = size + 1;
    258
    259                if (newSize == entries.length)
    260                {
    261                    // Time to expand!
    262
    263                    int newCapacity = (size * 3) / 2 + 1;
    264
    265                    CIMEntry<V>[] newEntries = new CIMEntry[newCapacity];
    266
    267                    System.arraycopy(entries, 0, newEntries, 0, cursor);
    268
    269                    System.arraycopy(entries, cursor, newEntries, cursor + 1, size - cursor);
    270
    271                    entries = newEntries;
    272                }
    273                else
    274                {
    275                    // Open up a space for the new entry
    276
    277                    System.arraycopy(entries, cursor, entries, cursor + 1, size - cursor);
    278                }
    279
    280                CIMEntry<V> newEntry = new CIMEntry<V>(key, hashCode, newValue);
    281                entries[cursor] = newEntry;
    282
    283                size++;
    284
    285                // This is definately a structural change
    286
    287                modCount++;
    288
    289                return null;
    290            }
    291
    292        }
    293
    294        // The list of entries. This is kept sorted by hash code. In some cases, there may be different
    295        // keys with the same hash code in adjacent indexes.
    296        private CIMEntry<V>[] entries;
    297
    298        private int size = 0;
    299
    300        // Used by iterators to check for concurrent modifications
    301
    302        private transient int modCount = 0;
    303
    304        private transient Set<Map.Entry<String, V>> entrySet;
    305
    306        public CaseInsensitiveMap()
    307        {
    308            this(DEFAULT_SIZE);
    309        }
    310
    311        @SuppressWarnings("unchecked")
    312        public CaseInsensitiveMap(int size)
    313        {
    314            entries = new CIMEntry[Math.max(size, 3)];
    315        }
    316
    317        public CaseInsensitiveMap(Map<String, ? extends V> map)
    318        {
    319            this(map.size());
    320
    321            for (Map.Entry<String, ? extends V> entry : map.entrySet())
    322            {
    323                put(entry.getKey(), entry.getValue());
    324            }
    325        }
    326
    327        @Override
    328        public void clear()
    329        {
    330            for (int i = 0; i < size; i++)
    331                entries[i] = null;
    332
    333            size = 0;
    334            modCount++;
    335        }
    336
    337        @Override
    338        public boolean isEmpty()
    339        {
    340            return size == 0;
    341        }
    342
    343        @Override
    344        public int size()
    345        {
    346            return size;
    347        }
    348
    349        @SuppressWarnings("unchecked")
    350        @Override
    351        public V put(String key, V value)
    352        {
    353            int hashCode = caseInsenitiveHashCode(key);
    354
    355            return select(key, hashCode).put(key, hashCode, value);
    356        }
    357
    358        @Override
    359        public boolean containsKey(Object key)
    360        {
    361            return select(key).isFound();
    362        }
    363
    364        @Override
    365        public V get(Object key)
    366        {
    367            return select(key).get();
    368        }
    369
    370        @Override
    371        public V remove(Object key)
    372        {
    373            return select(key).remove();
    374        }
    375
    376        @SuppressWarnings("unchecked")
    377        @Override
    378        public Set<Map.Entry<String, V>> entrySet()
    379        {
    380            if (entrySet == null) entrySet = new EntrySet();
    381
    382            return entrySet;
    383        }
    384
    385        private Position select(Object key)
    386        {
    387            if (key == null || key instanceof String)
    388            {
    389                String keyString = (String) key;
    390                return select(keyString, caseInsenitiveHashCode(keyString));
    391            }
    392
    393            return new Position(0, false);
    394        }
    395
    396        /**
    397         * Searches the elements for the index of the indicated key and (case insensitive) hash code. Sets the _cursor and
    398         * _found attributes.
    399         */
    400        private Position select(String key, int hashCode)
    401        {
    402            if (size == 0) return new Position(0, false);
    403
    404            int low = 0;
    405            int high = size - 1;
    406
    407            int cursor;
    408
    409            while (low <= high)
    410            {
    411                cursor = (low + high) >> 1;
    412
    413                CIMEntry e = entries[cursor];
    414
    415                if (e.hashCode < hashCode)
    416                {
    417                    low = cursor + 1;
    418                    continue;
    419                }
    420
    421                if (e.hashCode > hashCode)
    422                {
    423                    high = cursor - 1;
    424                    continue;
    425                }
    426
    427                return tunePosition(key, hashCode, cursor);
    428            }
    429
    430            return new Position(low, false);
    431        }
    432
    433        /**
    434         * select() has located a matching hashCode, but there's an outlying possibility that multiple keys share the same
    435         * hashCode. Backup the cursor until we get to locate the initial hashCode match, then march forward until the key
    436         * is located, or the hashCode stops matching.
    437         *
    438         * @param key
    439         * @param hashCode
    440         */
    441        private Position tunePosition(String key, int hashCode, int cursor)
    442        {
    443            boolean found = false;
    444
    445            while (cursor > 0)
    446            {
    447                if (entries[cursor - 1].hashCode != hashCode) break;
    448
    449                cursor--;
    450            }
    451
    452            while (true)
    453            {
    454                if (entries[cursor].matches(key))
    455                {
    456                    found = true;
    457                    break;
    458                }
    459
    460                // Advance to the next entry.
    461
    462                cursor++;
    463
    464                // If out of entries,
    465                if (cursor >= size || entries[cursor].hashCode != hashCode) break;
    466            }
    467
    468            return new Position(cursor, found);
    469        }
    470
    471        static int caseInsenitiveHashCode(String input)
    472        {
    473            if (input == null) return NULL_HASH;
    474
    475            int length = input.length();
    476            int hash = 0;
    477
    478            // This should end up more or less equal to input.toLowerCase().hashCode(), unless String
    479            // changes its implementation. Let's hope this is reasonably fast.
    480
    481            for (int i = 0; i < length; i++)
    482            {
    483                int ch = input.charAt(i);
    484
    485                int caselessCh = Character.toLowerCase(ch);
    486
    487                hash = 31 * hash + caselessCh;
    488            }
    489
    490            return hash;
    491        }
    492
    493    }