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