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